swift - 如何检查一个函数是否总是返回一个值(也就是 "doesn' t fall off the end”)？

Question

我正在构建一个教学编译器，我想检查函数是否总是返回一个值。我打算在语义分析步骤中执行此操作(因为这不在语言语法中)。

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

一)

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

二)

if (condition) {
    return value
}
return anotherValue

c)

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

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

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

任何有关伪代码的帮助都会非常有帮助!

(如果重要的话，我正在用 Swift 实现我的编译器)

Answer 1

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

就是说，即使没有控制流图，假设有一些常见的限制(特别是您可以接受 if(cond) return x; if(!cond) return y; 被视为末尾下降，即使它等同于 if(cond) return x; else return y;，这是允许的)。我还假设没有 goto 因为你没有在你的控制流语句列表中列出它(我没有对 break 和 continue 做任何假设因为那些只出现在循环中，而循环无关紧要)。

我们只需要考虑合法区 block (即总是返回的区 block )的情况:

所以空 block 显然是不允许的，因为如果它是空的，它就无法返回。直接(即不在 if 或循环内)包含返回的 block 将被允许(如果它不在 block 的末尾， block 中 return 之后的所有内容都将无法访问，您可能还想变成错误或警告)。

循环无关紧要。也就是说，如果你的 block 包含一个循环，即使循环包含一个返回，它仍然必须有一个返回 outside 因为循环条件可能为假，所以我们不需要甚至检查循环内的内容。对于 do-while 循环，情况并非如此，但您没有这些。

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