Add new warning to Clang to detect when all code paths in a function has a call back to the function.

[rtrieu]

Summary

Implement a warning to detect when a function will call itself recursively on every code path. If a program ever calls such a function, the function will attempt to call itself until it runs out of stack space.

This warning searches the CFG to determine if every codepath results in a self call. In addition to the test for this warning, several other tests needed to be fixed, and a pragma to prevent this warning where Clang really wants a stack overflow.

Testing with this warning has already caught several buggy functions. Common mistakes include: incorrect namespaces, wrapper classes not forwarding calls properly, similarly named member function and data member, and failing to call an overload of the same function. When run outside of template instantiations, all true positives. In template instantiations, only 25% true positive. Therefore, this warning is disabled in template instantiations. An example of such a false positive is in the test cases.

[rtrieu]

Warn on non-templated member functions of templated classes.

[rtrieu]

Fix misspelling of function.

[silvas]

Have you measured the compile-time overhead of this check?

Also, the randomly strewn -Wno-infinite-recursion around the test suite is kind of worrying. Can those tests just be changed (in separate commits) to preserve what they are testing but not have spurious infinite recursion? I can't imagine that infinite recursion is somehow essential to what they are testing.

At a higher level, is this really needed as a compiler warning? I mean, it's nice and all to detect these things statically, but is this really something that needs to be happening on every build? Could we just do this in the static analyzer? In practice, I can't imagine any of these being hard to debug "while developing", since they will always result in a stack overflow the second they are called (and then you just look at the core file (or the debugger that your IDE attached) to see which function it was) (also, maybe Asan would intervene before the stack overflow and give you a nice pretty error report?). So essentially it seems like this is finding bugs in code that has no test coverage and has never been executed in practice; that kind of "cleaning out crusty unused parts of the codebase" seems like it would be better left to the static analyzer. Or do these kinds of infinite recursion things come up so often during development that having it be a warning is a big time-saver for developers?

[rsmith]

lib/Sema/AnalysisBasedWarnings.cpp

85–87

These names are a bit confusing. They seem to mean:

Unknown: no paths to here have been visited
AfterFunctionCall: no paths to here have been found that don't recurse
Reachable: paths to here have been found that don't recurse

How about FoundNoPath, FoundPath, FoundPathWithNoRecursiveCall or similar?

96–97

Once you set the exit block to Reachable, you can bail out of the traversal early.

107

Compare canonical declarations here.

108–109

If the function is non-virtual, you should warn even if the object argument is different.

[rtrieu]

Switch -Winfinite-recursion to DefaultIgnore, in line with the other CFG warnings. This allows the other tests to be reverted. Also made the suggested changes from Richard Smith.

[rtrieu]

Ping.

[rsmith]

LGTM with minor tweaks.

I'm still not sure we've got the function template specialization case right, but I think this adds most of the value as-is, and I think you're right to blacklist an area with known false positives over not having the warning at all.

lib/Lex/Pragma.cpp

934–936

Somewhat unrelated to your patch, but this looks broken (at -O1 or above). How about replacing this with:

static void DebugOverflowStack() {
  void (*volatile Self)() = DebugOverflowStack;
  self();
}

That should both suppress your warning (and presumably the MSVC warning) and make this function work reliably.

lib/Sema/AnalysisBasedWarnings.cpp

90–93

For new code, please follow the coding style's formatting rules (checkForFunctionCall, States, State, ExitID, and " &" not "& ").

96–99

Maybe

if (States[ID] >= State)
  return;

States[ID] = State;
// ...

[rtrieu]

r197849 has the fix to allow the overflow to work in optimized code
r197853 is the commit for the warning

include/clang/Basic/DiagnosticGroups.td

 def BitwiseOpParentheses: DiagGroup<"bitwise-op-parentheses">;
 def LogicalOpParentheses: DiagGroup<"logical-op-parentheses">;
 def LogicalNotParentheses: DiagGroup<"logical-not-parentheses">;
 def ShiftOpParentheses: DiagGroup<"shift-op-parentheses">;
 def OverloadedShiftOpParentheses: DiagGroup<"overloaded-shift-op-parentheses">;
 def DanglingElse: DiagGroup<"dangling-else">;
 def DanglingField : DiagGroup<"dangling-field">;
 def DistributedObjectModifiers : DiagGroup<"distributed-object-modifiers">;
+def InfiniteRecursion : DiagGroup<"infinite-recursion">;
 def GNUImaginaryConstant : DiagGroup<"gnu-imaginary-constant">;
 def IgnoredQualifiers : DiagGroup<"ignored-qualifiers">;
 def : DiagGroup<"import">;
 def IncompatiblePointerTypesDiscardsQualifiers 
   : DiagGroup<"incompatible-pointer-types-discards-qualifiers">;
 def IncompatiblePointerTypes
   : DiagGroup<"incompatible-pointer-types",
     [IncompatiblePointerTypesDiscardsQualifiers]>;

include/clang/Basic/DiagnosticSemaKinds.td

def warn_redundant_loop_iteration : Warning<
   InGroup<LoopAnalysis>, DefaultIgnore;
 def note_loop_iteration_here : Note<"%select{decremented|incremented}0 here">;
 
 def warn_duplicate_enum_values : Warning<
   "element %0 has been implicitly assigned %1 which another element has "
   "been assigned">, InGroup<DiagGroup<"duplicate-enum">>, DefaultIgnore;
 def note_duplicate_element : Note<"element %0 also has value %1">;
 
+def warn_infinite_recursive_function : Warning<
+  "all paths through this function will call itself">,
+  InGroup<InfiniteRecursion>, DefaultIgnore;
+
 // Constant expressions
 def err_expr_not_ice : Error<
   "expression is not an %select{integer|integral}0 constant expression">;
 def ext_expr_not_ice : Extension<
   "expression is not an %select{integer|integral}0 constant expression; "
   "folding it to a constant is a GNU extension">, InGroup<GNUFoldingConstant>;
 def err_typecheck_converted_constant_expression : Error<
   "value of type %0 is not implicitly convertible to %1">;

lib/Lex/Pragma.cpp

void HandleCaptured(Preprocessor &PP) {
     PP.EnterTokenStream(Toks, 1, /*DisableMacroExpansion=*/true,
                         /*OwnsTokens=*/false);
   }
 
 // Disable MSVC warning about runtime stack overflow.
 #ifdef _MSC_VER
     #pragma warning(disable : 4717)
 #endif
+// Disable Clang's warning about infinite recursion.
+#ifdef __clang__
+    #pragma clang diagnostic push
+    #pragma clang diagnostic ignored "-Winfinite-recursion"
+#endif
   void DebugOverflowStack() {
     DebugOverflowStack();
   }
 #ifdef _MSC_VER
     #pragma warning(default : 4717)
 #endif
+#ifdef __clang__
+    #pragma clang diagnostic pop
+#endif
 
 };
 
 /// PragmaDiagnosticHandler - e.g. '\#pragma GCC diagnostic ignored "-Wformat"'
 struct PragmaDiagnosticHandler : public PragmaHandler {
 private:
   const char *Namespace;
 public:

lib/Sema/AnalysisBasedWarnings.cpp

 
 /// CheckUnreachable - Check for unreachable code.
 static void CheckUnreachable(Sema &S, AnalysisDeclContext &AC) {
   UnreachableCodeHandler UC(S);
   reachable_code::FindUnreachableCode(AC, UC);
 }
 
 //===----------------------------------------------------------------------===//
+// Check for infinite self-recursion in functions
+//===----------------------------------------------------------------------===//
+
+enum RecursiveState {
+  FoundNoPath,
+  FoundPath,
+  FoundPathWithNoRecursiveCall
+};
+
+static void CheckForFunctionCall(Sema &S, const FunctionDecl *FD,
+                                 CFGBlock& Block, unsigned exitID,
+                                 llvm::SmallVectorImpl<RecursiveState> &states,
+                                 RecursiveState state) {
+  unsigned ID = Block.getBlockID();
+
+  if (states[ID] < state)
+    states[ID] = state;
+  else
+    return;
+
+  if (ID == exitID && state == FoundPathWithNoRecursiveCall)
+    return;
+
+  if (state == FoundPathWithNoRecursiveCall) {
+    for (CFGBlock::iterator I = Block.begin(), E = Block.end(); I != E; ++I) {
+      if (I->getKind() != CFGElement::Statement)
+        continue;
+
+      const CallExpr *CE = dyn_cast<CallExpr>(I->getAs<CFGStmt>()->getStmt());
+      if (CE && CE->getCalleeDecl() &&
+          CE->getCalleeDecl()->getCanonicalDecl() == FD) {
+        if (const CXXMemberCallExpr *MCE = dyn_cast<CXXMemberCallExpr>(CE)) {
+          if (isa<CXXThisExpr>(MCE->getImplicitObjectArgument()) ||
+              !MCE->getMethodDecl()->isVirtual()) {
+            state = FoundPath;
+            break;
+          }
+        } else {
+          state = FoundPath;
+          break;
+        }
+      }
+    }
+  }
+
+  for (CFGBlock::succ_iterator I = Block.succ_begin(), E = Block.succ_end();
+       I != E; ++I)
+    if (*I)
+      CheckForFunctionCall(S, FD, **I, exitID, states, state);
+}
+
+static void CheckRecursiveFunction(Sema &S, const FunctionDecl *FD,
+                                   const Stmt *Body,
+                                   AnalysisDeclContext &AC) {
+  FD = FD->getCanonicalDecl();
+
+  // Only run on non-templated functions and non-templated members of
+  // templated classes.
+  if (FD->getTemplatedKind() != FunctionDecl::TK_NonTemplate &&
+      FD->getTemplatedKind() != FunctionDecl::TK_MemberSpecialization)
+    return;
+
+  CFG *cfg = AC.getCFG();
+  if (cfg == 0) return;
+
+  if (cfg->getExit().pred_empty())
+    return;
+
+  llvm::SmallVector<RecursiveState, 16> states(cfg->getNumBlockIDs(),
+                                               FoundNoPath);
+  CheckForFunctionCall(S, FD, cfg->getEntry(), cfg->getExit().getBlockID(),
+                       states, FoundPathWithNoRecursiveCall);
+
+  // Check that the exit block is reachable.  This prevents triggering the
+  // warning on functions that do not terminate.
+  if (states[cfg->getExit().getBlockID()] == FoundPath)
+    S.Diag(Body->getLocStart(), diag::warn_infinite_recursive_function);
+}
+
+//===----------------------------------------------------------------------===//
 // Check for missing return value.
 //===----------------------------------------------------------------------===//
 
 enum ControlFlowKind {
   UnknownFallThrough,
   NeverFallThrough,
   MaybeFallThrough,
   AlwaysFallThrough,
if (FallThroughDiagFull || FallThroughDiagPerFunction) {
     DiagnoseSwitchLabelsFallthrough(S, AC, !FallThroughDiagFull);
   }
 
   if (S.getLangOpts().ObjCARCWeak &&
       Diags.getDiagnosticLevel(diag::warn_arc_repeated_use_of_weak,
                                D->getLocStart()) != DiagnosticsEngine::Ignored)
     diagnoseRepeatedUseOfWeak(S, fscope, D, AC.getParentMap());
 
+
+  // Check for infinite self-recursion in functions
+  if (Diags.getDiagnosticLevel(diag::warn_infinite_recursive_function,
+                               D->getLocStart())
+      != DiagnosticsEngine::Ignored) {
+    if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
+      CheckRecursiveFunction(S, FD, Body, AC);
+    }
+  }
+
   // Collect statistics about the CFG if it was built.
   if (S.CollectStats && AC.isCFGBuilt()) {
     ++NumFunctionsAnalyzed;
     if (CFG *cfg = AC.getCFG()) {
       // If we successfully built a CFG for this context, record some more
       // detail information about it.
       NumCFGBlocks += cfg->getNumBlockIDs();
       MaxCFGBlocksPerFunction = std::max(MaxCFGBlocksPerFunction,

test/SemaCXX/warn-infinite-recursion.cpp

+// RUN: %clang_cc1 %s -fsyntax-only -verify -Winfinite-recursion
+
+void a() {  // expected-warning{{call itself}}
+  a();
+}
+
+void b(int x) {  // expected-warning{{call itself}}
+  if (x)
+    b(x);
+  else
+    b(x+1);
+}
+
+void c(int x) {
+  if (x)
+    c(5);
+}
+
+void d(int x) {  // expected-warning{{call itself}}
+  if (x)
+    ++x;
+  return d(x);
+}
+
+// Doesn't warn on mutually recursive functions
+void e();
+void f();
+
+void e() { f(); }
+void f() { e(); }
+
+// Don't warn on infinite loops
+void g() {
+  while (true)
+    g();
+
+  g();
+}
+
+void h(int x) {
+  while (x < 5) {
+    h(x+1);
+  }
+}
+
+void i(int x) {  // expected-warning{{call itself}}
+  while (x < 5) {
+    --x;
+  }
+  i(0);
+}
+
+int j() {  // expected-warning{{call itself}}
+  return 5 + j();
+}
+
+class S {
+  static void a();
+  void b();
+};
+
+void S::a() {  // expected-warning{{call itself}}
+  return a();
+}
+
+void S::b() {  // expected-warning{{call itself}}
+  int i = 0;
+  do {
+    ++i;
+    b();
+  } while (i > 5);
+}
+
+template<class member>
+struct T {
+  member m;
+  void a() { return a(); }  // expected-warning{{call itself}}
+  static void b() { return b(); }  // expected-warning{{call itself}}
+};
+
+void test_T() {
+  T<int> foo;
+  foo.a();  // expected-note{{in instantiation}}
+  foo.b();  // expected-note{{in instantiation}}
+}
+
+class U {
+  U* u;
+  void Fun() {  // expected-warning{{call itself}}
+    u->Fun();
+  }
+};
+
+// No warnings on templated functions
+// sum<0>() is instantiated, does recursively call itself, but never runs.
+template <int value>
+int sum() {
+  return value + sum<value/2>();
+}
+
+template<>
+int sum<1>() { return 1; }
+
+template<int x, int y>
+int calculate_value() {
+  if (x != y)
+    return sum<x - y>();  // This instantiates sum<0>() even if never called.
+  else
+    return 0;
+}
+
+int value = calculate_value<1,1>();
+
+void DoSomethingHere();
+
+// DoStuff<0,0>() is instantiated, but never called.
+template<int First, int Last>
+int DoStuff() {
+  if (First + 1 == Last) {
+    // This branch gets removed during <0, 0> instantiation in so CFG for this
+    // function goes straight to the else branch.
+    DoSomethingHere();
+  } else {
+    DoStuff<First, (First + Last)/2>();
+    DoStuff<(First + Last)/2, Last>();
+  }
+  return 0;
+}
+int stuff = DoStuff<0, 1>();