c - 如何获得使用递归的警告？

Question

嵌入式软件开发的一些规则集和指南完全禁止递归。我将 arm-none-eabi-gcc 与基于 ARM Cortex-M4 的微 Controller 一起使用。

我正在寻找一个静态分析工具，它会警告我有关代码中递归的使用。我对这些工具没有什么经验。是否可以为此使用 clang-tidy 或 clang 静态分析器？如果是，我如何配置它们以警告递归？

(快速浏览一下 gcc option summary 告诉我仅靠 gcc 无法做到这一点。)

注意:

• 请不要告诉我“只是不要递归”。代码库很大而且不是我一个人的。我希望能够证明其中没有递归。
  (这就像说“只是不要取消引用空指针”。虽然没有人故意这样做，但存在工具是为了验证它不会发生。)

Answer 1

这可以使用 Clang 生成的调用图数据来解决。

第 1 步。使用 clang 生成调用图信息:

clang -S -emit-llvm SourceFile.c -o - | opt -analyze -print-callgraph 

(来自 Generate calling graph for C++ code，将 -dot-callgraph 替换为 -print-callgraph。)

对于这样的输入:

void a(){}
void b(){a();}
void c(){a(); b();}
void d(){a(); c();}
void e(){e();}

这将产生:

CallGraph Root is: <<null function: 0x0x7fdef25036c0>>
Call graph node <<null function>><<0x7fdef25036c0>>  #uses=0
  CS<0x0> calls function 'a'
  CS<0x0> calls function 'b'
  CS<0x0> calls function 'c'
  CS<0x0> calls function 'd'

Call graph node for function: 'a'<<0x7fdef2503750>>  #uses=4

Call graph node for function: 'b'<<0x7fdef25037d0>>  #uses=2
  CS<0x7fdef2500a38> calls function 'a'

Call graph node for function: 'c'<<0x7fdef2503870>>  #uses=2
  CS<0x7fdef2500cb8> calls function 'a'
  CS<0x7fdef2500d28> calls function 'b'

Call graph node for function: 'd'<<0x7fdef2503970>>  #uses=1
  CS<0x7fdef2500fe8> calls function 'a'
  CS<0x7fdef2501058> calls function 'c'

Call graph node for function: 'e'<<0x7f8912d03c10>>  #uses=2
  CS<0x7f8912d01318> calls function 'e'

(在 C++ 中，可以使用 c++filt 清理错乱的函数名称；模板变得丑陋但可行。)有了这些数据，就可以勾勒出如何检测递归:

第 2 步。将调用图数据解析为最喜欢的脚本语言以形成调用图的表示形式。

class Graph(object):

  _callees = []

  def add_callee(self, f):
    self._callees.append(f)
    # etc

第 3 步。对于每个函数，走图寻找对该函数的调用。有点像这样:

def walkGraph(node,f,stack):
  for callee in node._callees:
    if f == callee:
      print('Recursion!')
      dumpStack(stack,f)
    else:
      walkGraph(callee,f,stack.append(node))