Как проверить, что функция всегда возвращает значение (иначе "не падает с конца")?

Question

Я строю дидактический компилятор, и я хотел бы проверить, будет ли функция всегда возвращать значение.Я намерен сделать это на этапе семантического анализа (поскольку это не охватывается грамматикой языка).

Из всех операторов управления потоком этот дидактический язык имеет только if, else иwhile заявления (таким образом, нет do while, for, switch дел и т. Д.).Обратите внимание, что else if также возможно.Ниже приведены все допустимые примеры фрагментов:

a)

if (condition) {
    // non-returning commands
}
return value

b)

if (condition) {
    return value
}
return anotherValue

c)

if (condition) {
    return value1
} else {
    return value2
}
// No return value needed here

Имеюискал много об этом, но не смог найти псевдоалгоритм, который я мог бы понять.Я искал тестирование пути программного обеспечения, тестирование белого ящика, а также другие связанные вопросы переполнения стека, такие как this и this .

Я слышал, что этоможно решить с помощью графиков, а также с помощью стека, но я не знаю, как реализовать эти стратегии.

Любая помощь с псевдокодом будет очень полезна!

(и если это имеет значение,Я реализую свой компилятор в Swift)

Answer 1

Итак, после 5 часов размышлений о том, как это реализовать, я нашел достойное решение (по крайней мере, до сих пор не смог его сломать).Я провел большую часть времени в Интернете (без удачи), чем на самом деле думал о проблеме и пытался решить ее самостоятельно.

Ниже приведена моя реализация (в Swift 4.2, но синтаксис довольнолегко подобрать), используя график:

final class SemanticAnalyzer {
    private var currentNode: Node!
    private var rootNode: Node!

    final class Node {
        var nodes: [Node] = []
        var returnsExplicitly = false
        let parent: Node?
        var elseNode: Node!
        var alwaysReturns: Bool { return returnsExplicitly || elseNode?.validate() == true }

        init(parent: Node?) {
            self.parent = parent
        }

        func validate() -> Bool {
            if alwaysReturns {
                return true
            } else {
                return nodes.isEmpty ? false : nodes.allSatisfy { $0.alwaysReturns }
            }
        }
    }

    /// Initializes the components of the semantic analyzer.
    func startAnalyzing() {
        rootNode = Node(parent: nil)
        currentNode = rootNode
    }

    /// Execute when an `if` statement is found.
    func handleIfStatementFound() {
        let ifNode = Node(parent: currentNode)
        let elseNode = Node(parent: currentNode)
        // Assigning is not necessary if the current node returns explicitly.
        // But assigning is not allowed if the else node always returns, so we check if the current node always returns.
        if !currentNode.alwaysReturns {
            currentNode.elseNode = elseNode
        }
        currentNode.nodes += [ ifNode, elseNode ]
        currentNode = ifNode
    }

    /// Execute when an `else` statement is found.
    func handleElseStatementFound() {
        currentNode = currentNode.elseNode
    }

    /// Execute when a branch scope is closed.
    func handleBranchClosing() {
        currentNode = currentNode.parent! // If we're in a branch, the parent node is never nil
    }

    /// Execute when a function return statement is found.
    func handleReturnStatementFound() {
        currentNode.returnsExplicitly = true
    }

    /// Determine whether the function analyzed always returns a value.
    ///
    /// - Returns: whether the root node validates.
    func validate() -> Bool {
        return rootNode.validate()
    }
}

В основном, это то, что он делает:

1. Когда он находит оператор if, создайте 2 новых узла и укажитетекущий узел для них обоих (как в узле двоичного дерева).
2. Когда найден оператор else, мы просто переключаем текущий узел на другой узел, созданный ранее в операторе if.
3. Когда ветвь закрыта (например, в символе if оператора }), он переключает текущий узел на родительский узел.
4. Когда он находит оператор функции return,можно предположить, что текущий узел всегда будет иметь возвращаемое значение.

Наконец, чтобы проверить узел, либо узел имеет явное возвращаемое значение, либо все узлы должны быть действительными.

Это работает свложенные операторы if / else, а также ветви без возвращаемых значений.

Answer 2

Если у вас есть график потока управления, проверить, что функция всегда возвращает, так же просто, как проверить, что неявный возврат в конце функции недоступен.Таким образом, поскольку существует множество анализов и оптимизаций, в которых вам нужен CFG, было бы неплохо создать его.

Тем не менее, даже без графика потока управления это свойство довольно простое.проверить, предполагая некоторые общие ограничения (в частности, что вы в порядке, когда что-то вроде if(cond) return x; if(!cond) return y; рассматривается как падение конца, даже если это эквивалентно if(cond) return x; else return y;, что было бы допустимо).Я также предполагаю, что нет goto, потому что вы не указали его в своем списке операторов потока управления (я не делаю предположений относительно break и continue, потому что они появляются только внутри циклов, и циклы не имеют значения).1008 *

Нам просто нужно рассмотреть случаи того, как будет выглядеть юридический блок (то есть тот, который всегда достигает возврата):

Таким образом, пустой блок явно не будет разрешен, потому что он не можетдостичь возврата, если он пуст.Будет разрешен блок, который непосредственно (т.е. не внутри цикла if или) содержит возврат (и если он не находится в конце блока, все после возврата в блоке будет недоступно, что также может потребоваться)превращается в ошибку или предупреждение).

Петли не имеют значения.То есть, если ваш блок содержит цикл, он все равно должен иметь возврат вне цикла, даже если цикл содержит возврат, потому что условие цикла может быть ложным, поэтому нам не нужно дажепроверь что внутри петли.Это не было бы верно для циклов do-while, но у вас их нет.

Если блок содержит непосредственно if с else и блоком then, и else-блок всегда достигает возврата, этот блок также всегда достигает возврата.В этом случае все после if - else недоступно.В противном случае if не имеет значения, как циклы.

Так что в псевдокоде это будет:

alwaysReturns( {} ) = false
alwaysReturns( {return exp; ...rest} ) = true
alwaysReturns( { if(exp) thenBlock else elseBlock; ...rest}) =
    (alwaysReturns(thenBlock) && alwaysReturns(elseBlock)) || alwaysReturns(rest)
alwaysReturns( {otherStatement; ...rest} ) = alwaysReturns(rest)