如何检查一个函数总是 return 一个值（又名 "doesn't fall off the end"）？

Question

我正在构建一个教学编译器，我想检查函数是否总是 return 一个值。我打算在语义分析步骤中这样做（因为这不在语言语法中）。

在所有流程控制语句中，这种教学语言只有 if、else 和 while 语句（因此没有 do while、for, switch 例等）。请注意 else if 也是可能的。以下是所有有效的示例片段：

一）

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

我对此进行了很多搜索，但找不到我可以理解的伪算法。我搜索了软件路径测试、白盒测试以及其他相关的 Stack Overflow 问题，例如 this and this.

我听说这可以使用图形来解决，也可以使用堆栈来解决，但我不知道如何实施这些策略。

任何有关伪代码的帮助都将非常有帮助！

（如果重要的话，我正在 Swift 中实现我的编译器）

Answer 1

如果您有控制流图，检查函数是否始终 returns 就像检查函数末尾的隐式 return 是否不可访问一样简单。因此，由于在您需要 CFG 的地方有大量的分析和优化，因此构建一个 CFG 并不是一个坏主意。

就是说，即使没有控制流图，这个属性也可以很直接地检查假设一些常见的限制（特别是你可以接受像 if(cond) return x; if(!cond) return y; 这样的东西被视为下降尽管它等同于 if(cond) return x; else return y;，但这是允许的）。我还假设没有 goto 因为你没有在你的控制流语句列表中列出它（我没有对 break 和 continue 做任何假设因为它们只出现在循环和循环中没关系）。

我们只需要考虑合法块（即总是达到 return 的块）的情况：

所以空块显然是不允许的，因为如果它是空的，它就无法到达 return。直接（即不在 if 或循环内）包含 return 的块将被允许（如果它不在块的末尾，块中 return 之后的所有内容都将是无法访问，您可能还想将其转换为错误或警告）。

循环无关紧要。也就是说，如果你的块包含一个循环，它仍然必须有一个 return outside 即使循环包含一个 return 因为循环条件可能是错误的，所以我们甚至不需要检查循环内的内容。这对于 do-while 循环不是真的，但你没有那些。

如果块直接包含一个 if 和一个 else 并且 then-block 和 else-block 总是到达 return，这个块也总是到达 return。在这种情况下，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)

Answer 2

所以，经过 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 { [=10=].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()
    }
}

基本上它的作用是：

当它找到一个 if 语句时，创建 2 个新节点并将当前节点指向它们（如在二叉树节点中）。
当找到else语句时，我们只是将当前节点切换到之前在if语句中创建的else节点。
当分支关闭时（例如在if语句的}字符中），它将当前节点切换到父节点。
当它找到函数 return 语句时，它可以假定当前节点将始终具有 return 值。

最后，要验证一个节点，要么该节点具有明确的 return 值，要么所有节点都必须有效。

这适用于嵌套的 if/else 语句，以及根本没有 return 值的分支。

如何检查一个函数总是 return 一个值（又名 "doesn't fall off the end"）？

How to check that a function always return a value (aka "doesn't fall off the end")?

compiler-construction

swift