Index: include/clang/Basic/DiagnosticGroups.td =================================================================== --- include/clang/Basic/DiagnosticGroups.td +++ include/clang/Basic/DiagnosticGroups.td @@ -161,6 +161,7 @@ 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">; Index: include/clang/Basic/DiagnosticSemaKinds.td =================================================================== --- include/clang/Basic/DiagnosticSemaKinds.td +++ include/clang/Basic/DiagnosticSemaKinds.td @@ -30,6 +30,10 @@ "been assigned">, InGroup>, 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, DefaultIgnore; + // Constant expressions def err_expr_not_ice : Error< "expression is not an %select{integer|integral}0 constant expression">; Index: lib/Lex/Pragma.cpp =================================================================== --- lib/Lex/Pragma.cpp +++ lib/Lex/Pragma.cpp @@ -926,12 +926,20 @@ #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 }; Index: lib/Sema/AnalysisBasedWarnings.cpp =================================================================== --- lib/Sema/AnalysisBasedWarnings.cpp +++ lib/Sema/AnalysisBasedWarnings.cpp @@ -78,6 +78,86 @@ } //===----------------------------------------------------------------------===// +// 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 &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(I->getAs()->getStmt()); + if (CE && CE->getCalleeDecl() && + CE->getCalleeDecl()->getCanonicalDecl() == FD) { + if (const CXXMemberCallExpr *MCE = dyn_cast(CE)) { + if (isa(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 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. //===----------------------------------------------------------------------===// @@ -1770,6 +1850,16 @@ 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(D)) { + CheckRecursiveFunction(S, FD, Body, AC); + } + } + // Collect statistics about the CFG if it was built. if (S.CollectStats && AC.isCFGBuilt()) { ++NumFunctionsAnalyzed; Index: test/SemaCXX/warn-infinite-recursion.cpp =================================================================== --- test/SemaCXX/warn-infinite-recursion.cpp +++ test/SemaCXX/warn-infinite-recursion.cpp @@ -0,0 +1,129 @@ +// 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 +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 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 sum() { + return value + sum(); +} + +template<> +int sum<1>() { return 1; } + +template +int calculate_value() { + if (x != y) + return sum(); // 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 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(); + DoStuff<(First + Last)/2, Last>(); + } + return 0; +} +int stuff = DoStuff<0, 1>();