[clang-tidy] misc-no-recursion: a new check

[lebedev.ri]

Summary

Recursion is a powerful tool, but like any tool
without care it can be dangerous. For example,
if the recursion is unbounded, you will
eventually run out of stack and crash.

You can of course track the recursion depth
but if it is hardcoded, there can always be some
other environment when that depth is too large,
so said magic number would need to be env-dependent.
But then your program's behavior is suddenly more env-dependent.

Also, recursion, while it does not outright stop optimization,
recursive calls are less great than normal calls,
for example they hinder inlining.

Recursion is banned in some coding guidelines:

• SEI CERT DCL56-CPP. Avoid cycles during initialization of static objects
• JPL 2.4 Do not use direct or indirect recursion.
• I'd say it is frowned upon in LLVM, although not banned

And is plain unsupported in some cases:

• OpenCL 1.2, 6.9 Restrictions: i. Recursion is not supported.

So there's clearly a lot of reasons why one might want to
avoid recursion, and replace it with worklist handling.
It would be great to have a enforcement for it though.

This implements such a check.
Here we detect both direct and indirect recursive calls,
although since clang-tidy (unlike clang static analyzer)
is CTU-unaware, if the recursion transcends a single standalone TU,
we will naturally not find it :/

The algorithm is pretty straight-forward:

1. Build call-graph for the entire TU. For that, the existing clang::CallGraph is re-used, although it had to be modified to also track the location of the call.
2. Then, the hard problem: how do we detect recursion? Since we have a graph, let's just do the sane thing, and look for Strongly Connected Function Declarations - widely known as SCC. For that LLVM provides llvm::scc_iterator, which is internally an Tarjan's DFS algorithm, and is used throught LLVM, so this should be as performant as possible.
3. Now that we've got SCC's, we discard those that don't contain loops. Note that there may be more than one loop in SCC!
4. For each loopy SCC, we call out each function, and print a single example call graph that shows recursion -- it didn't seem worthwhile enumerating every possible loop in SCC, although i suppose it could be implemented.
   • To come up with that call graph cycle example, we start at first SCC node, see which callee of the node is within SCC (and is thus known to be in cycle), and recurse into it until we hit the callee that is already in call stack.

[Eugene.Zelenko]

It'll be reasonable to add CERT alias.

clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp

214

true

clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst

9

It'll be reasonable to add links to relevant coding guidelines.

[lebedev.ri]

In D72362#1808825, @Eugene.Zelenko wrote:

It'll be reasonable to add CERT alias.

I'm not sure about that.
This diagnoses any potential recursion,
while CERT is much more specific than that.
(Avoid cycles during initialization of static objects)

[lebedev.ri]

s/1/true/

[JonasToth]

So that is were the CTU question comes from? :)

clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp

22

That should be in the CallGraph code, adding a private operator overload does not feel right.

32

That stuff, too.

68

Why smart?

74

That method name looks confusing. isEmpty()? If not, why?

243

That should be a Note:

288

Please merge these two notes into one.

clang-tools-extra/clang-tidy/misc/NoRecursionCheck.h

29

nit: the private stuff is usually at the bottom in the other clang-tidy code. not sure if there is something in the coding standard though.

clang-tools-extra/docs/ReleaseNotes.rst

73

The technical details should not be in the release notes. Just that it finds recursion and diagnoses it.

clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp

128

Does the check find recursion through function pointers? (Probably not? Should be noted as limitation).

Please add cases from lambdas. And cases where recursion happens in templates / only with one of multiple instantiations.

[lebedev.ri]

Thanks for taking a look.
Some deflective replies inline.

clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp

22

I didn't want to put this into callgraph, because this
cements the fact that we do not care about sourceloc,
which may not be true for other users.
I can put it there, but if told so by it's code owners (@NoQ ?)

32

(same reasoning)

68

Because if it's just named ImmutableSet, why should it not just be a using ImmutableSet = DenseSet; const ImmutableSet ......?
This denotes it's different behaviour when in small-size mode and in non-small-size mode.

74

See how it's used, e.g. in count(), see SmallSet also.

243

I'm intentionally emitting it as a warning.

If i // NOLINT the main warning, does that not silence the related Notes?
I don't want NOLINTing the "main" function to silence the report for the rest of the functions in SCC.

[bader]

Does it make sense to implement such diagnostics in clang Sema, considering that OpenCL does not allow recursion?
We implemented similar diagnostics for SYCL programming model and would be like to upstream it to clang later (https://github.com/intel/llvm/commit/4efe9fcf2dc6f6150b5b477b0f8320ea13a7f596). Can we somehow leverage this work for the compiler?

[lebedev.ri]

In D72362#1817599, @bader wrote:

Does it make sense to implement such diagnostics in clang Sema, considering that OpenCL does not allow recursion?
We implemented similar diagnostics for SYCL programming model and would be like to upstream it to clang later (https://github.com/intel/llvm/commit/4efe9fcf2dc6f6150b5b477b0f8320ea13a7f596). Can we somehow leverage this work for the compiler?

Implementing it elsewhere will be more restrictive in the future - somehow i suspect
it will be easier to make clang-tidy CTU-aware rather than clang sema.

That being said, is SYCL inherently single-TU, does it not support
linking multiple separately compiled object files together?

[bader]

In D72362#1817682, @lebedev.ri wrote:

In D72362#1817599, @bader wrote:

Does it make sense to implement such diagnostics in clang Sema, considering that OpenCL does not allow recursion?
We implemented similar diagnostics for SYCL programming model and would be like to upstream it to clang later (https://github.com/intel/llvm/commit/4efe9fcf2dc6f6150b5b477b0f8320ea13a7f596). Can we somehow leverage this work for the compiler?

Implementing it elsewhere will be more restrictive in the future - somehow i suspect
it will be easier to make clang-tidy CTU-aware rather than clang sema.

That being said, is SYCL inherently single-TU, does it not support
linking multiple separately compiled object files together?

SYCL doesn't require multi-TU support. AFAIK, ComputeCPP implementation is signle-TU. +@Naghasan to confirm/clarify.
The open source implementation I referred to, does support linking separately compiled object files, but still I think detecting single-TU recursion in clang is very useful.
Is it possible to have both: intra-TU diagnostics in clang and inter-TU diagnostics in clang-tidy tool? Share any infrastructure (e.g. recursion detection)?

[lebedev.ri]

In D72362#1819243, @bader wrote:

In D72362#1817682, @lebedev.ri wrote:

In D72362#1817599, @bader wrote:

Does it make sense to implement such diagnostics in clang Sema, considering that OpenCL does not allow recursion?
We implemented similar diagnostics for SYCL programming model and would be like to upstream it to clang later (https://github.com/intel/llvm/commit/4efe9fcf2dc6f6150b5b477b0f8320ea13a7f596). Can we somehow leverage this work for the compiler?

Implementing it elsewhere will be more restrictive in the future - somehow i suspect
it will be easier to make clang-tidy CTU-aware rather than clang sema.

That being said, is SYCL inherently single-TU, does it not support
linking multiple separately compiled object files together?

SYCL doesn't require multi-TU support. AFAIK, ComputeCPP implementation is signle-TU. +@Naghasan to confirm/clarify.
The open source implementation I referred to, does support linking separately compiled object files, but still I think detecting single-TU recursion in clang is very useful.
Is it possible to have both: intra-TU diagnostics in clang and inter-TU diagnostics in clang-tidy tool? Share any infrastructure (e.g. recursion detection)?

Feel free to post that as an RFC to cfe-dev. If the feedback is favorable, i suspect i can rework this code somehow.

[bader]

@lebedev.ri, thanks for the suggestion. We will investigate this option when we ready to upload clang diagnostics patch.

[NoQ]

CallGraph changes look nice, i don't see any immediate problems and it's a nice-to-have thing that other users may benefit from (the static analyzer wouldn't though, it's only interested in topological sorting order on the graph). I guess you could have as well stored a CallExpr with the CallRecord.

Note that there are certain problems with the call graph itself that are caused by how our very AST is structured. Hopefully they won't cause you too much trouble. I outlined some of them in the inline comments.

clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp

22

Does this need to be operator==? It looks like DenseMap uses DenseMapInfo::isEqual instead, maybe just call it "isEqual" to avoid confusion?

32

So what exactly happens if you link together two different translation units with different specializations of DenseMapInfo<CallRecord> and start passing such dense maps from one TU to the other?

(ODR violations are definitely not my specialty)

clang/lib/Analysis/CallGraph.cpp

96–101 ↗

(On Diff #236843)

Note that you're missing out on destructors. They aren't in the call graph because they aren't in the AST to begin with. Like, declarations are there of course, but expressions are mostly missing. A destructor may call another function that will in turn destroy an object of the same type (maybe even the same object), causing recursion.

(side note: we're missing out on destructors too)

103–106 ↗

(On Diff #236843)

Note that if a function void foo(int x = boo()) { ... } is invoked as void bar() { foo(); foo(); }, you'd get two different-in-every-way call records from the same function bar() to the same function boo() with the same source location (the location of call-expression boo() within the ParmVarDecl for x). I'm legit curious if this is a problem for your checker.

[lebedev.ri]

@NoQ Thank you for taking a look!

Rebased, addressed most of the review notes (some tests could be added), split callgraph changes into a separate review.

clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp

22

Now that i store Expr* in CallGraphNode::CallRecord,
this comparison operator appears to be automatically provided,
which means we really should provide our own to avoid confusing behavior
as compared to the DenseMap behavior.
So i'd say yes.

32

A good question, for another time.

clang/lib/Analysis/CallGraph.cpp

103–106 ↗

(On Diff #236843)

Test case added (is this how you'd imagine it to be a problem?).
I'm not sure what you mean by a problem, it is diagnosed at least.

[NoQ]

clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp

153

Aha, yeah, the warning is present, i guess that part is correct, but look how your note function 'bar' calls function 'boo' here: doesn't really point into the body of 'bar'. In this case it still makes sense because it's easy to see that 'foo' is called from 'bar', but the chain of default arguments may be arbitrarily long (what if 'boo' has yet another default argument?). You might want to add a separate facility just to handle this edge case.

[lebedev.ri]

Fixup disclaimer printing, NFC.

clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp

153

To make this more readable, the diag is:

/builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:138:5: warning: function 'boo' is part of call graph loop [misc-no-recursion]
int boo();
    ^
/builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:140:6: warning: function 'bar' is part of call graph loop [misc-no-recursion]
void bar() {
     ^
/builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:138:5: note: Example call graph loop, starting from function 'boo'
int boo();
    ^
/builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:145:3: note: Frame #1: function 'boo' calls function 'bar' here:
  bar();
  ^
/builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:139:18: note: Frame #2: function 'bar' calls function 'boo' here:
void foo(int x = boo()) {}
                 ^

Am i looking at this wrong, or all the info is present?

[lebedev.ri]

clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp

153

Edit: right, bar->foo edge is not shown there.

[NoQ]

clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp

153

Yup. And, well, semantically it's kind of correct, because it's not foo() that calls boo(), but it's bar()'s responsiblity to call boo() directly before calling foo(). So it's more like a three-way relationship:

misc-no-recursion.cpp.tmp.cpp:139:18: note: Frame #1: function 'bar' calls function 'boo' here:
void foo(int x = boo()) {}
                 ^
misc-no-recursion.cpp.tmp.cpp:141:7: note: ...in order to compute default argument for function 'foo' here:
  foo();
      ^

So i'd imagine CallRecords potentially containing arbitrarily long chains of backreferences from a default argument initializer to the respective CXXDefaultArgExpr that we're currently visiting (which may in turn be part of another default argument initializer, given that those are arbitrary expressions).

(it's of course up to you whether you want to deal with this immediately or later, i'm just ranting, don't mind me)

[aaron.ballman]

clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp

29

"Smart" is not a descriptive term. This seems like it's an ImmutableSmallSet?

65

No else after return.

71

Same complaint here about Smart -- should probably just be a SmallSetVector.

204

I think "call graph loop" is a bit much for a diagnostic -- how about %0 is within a recursive call chain or something along those lines?

205

Drop the call to getName() and remove the single quotes from the diagnostic around %0, and just pass in the NamedDecl -- the diagnostics engine will do the right thing (and it gives better names for strange things like operators).

231

Example -> example

I think "call graph group" might be a bit much for a diagnostic -- how about example recursive call chain, starting from %0

233

Same here (and elsewhere, I'll stop commenting on them).

250–251

Diagnostic text should not be full sentences.

... which was the starting point of the recursive call chain; there may be other cycles

260

Remove commented out code.

clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst

9

Agreed.

[lebedev.ri]

Ping.

@aaron.ballman thank you for taking a look!
Addressed review notes.

clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp

29

I was really trying to convey the fact that it can either be in small-sized mode (linear search over vector),
or in set mode (constructed with a large size, search in set).
But then, SmallVector also can be in small-sized mode (stack allocation), and large-sized mode (heap).
So here i guess ImmutableSmallSet name should work..

71

There already is a SmallSetVector, and it does have different semantics,
i've added a code comment explaining their differences, PTAL.

For now, i'd prefer to keep this as-is, but afterwards i suspect
i might be able to "upstream" this into SmallSetVector itself,
thus getting rid of SmartSmallSetVector.

Let me know if this makes sense?

204

Sure, that should be fine too.

205

Nice!

clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst

9

Is this better?

clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp

128

This indeed gets blinded by function pointers, test added.

As for lambdas, i'm not sure what specifically you mean?
The lambda itself can't be recursive i think?
https://godbolt.org/z/GYLRnB

153

I agree that this isn't perfect, but i'm not very sure how that information could be added to the call stack.
I think i'll leave this as-is for now..

[aaron.ballman]

LGTM aside from some nits.

clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp

71

Okay, that's reasonable enough. Can you add a FIXME suggesting that plan in the code?

clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst

7

call graph -> the call graph

And you should probably spell out SCC.

9

Looks great!

9

call graph -> a call graph

clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp

128

There are techniques to make lambdas recursive, but maybe we don't need to catch those (at least not initially). e.g., https://riptutorial.com/cplusplus/example/8508/recursive-lambdas

[lebedev.ri]

In D72362#1874690, @aaron.ballman wrote:

LGTM aside from some nits.

Thank you for the review!
Nits addressed.

clang-tools-extra/clang-tidy/misc/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangTidyMiscModule
   DefinitionsInHeadersCheck.cpp
   MiscTidyModule.cpp
   MisplacedConstCheck.cpp
   NewDeleteOverloadsCheck.cpp
+  NoRecursionCheck.cpp
   NonCopyableObjects.cpp
   NonPrivateMemberVariablesInClassesCheck.cpp
   RedundantExpressionCheck.cpp
   StaticAssertCheck.cpp
   ThrowByValueCatchByReferenceCheck.cpp
   UnconventionalAssignOperatorCheck.cpp
   UniqueptrResetReleaseCheck.cpp
   UnusedAliasDeclsCheck.cpp

clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp

 //===--- MiscTidyModule.cpp - clang-tidy ----------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "../ClangTidy.h"
 #include "../ClangTidyModule.h"
 #include "../ClangTidyModuleRegistry.h"
 #include "DefinitionsInHeadersCheck.h"
 #include "MisplacedConstCheck.h"
 #include "NewDeleteOverloadsCheck.h"
+#include "NoRecursionCheck.h"
 #include "NonCopyableObjects.h"
 #include "NonPrivateMemberVariablesInClassesCheck.h"
 #include "RedundantExpressionCheck.h"
 #include "StaticAssertCheck.h"
 #include "ThrowByValueCatchByReferenceCheck.h"
 #include "UnconventionalAssignOperatorCheck.h"
 #include "UniqueptrResetReleaseCheck.h"
 #include "UnusedAliasDeclsCheck.h"
 #include "UnusedParametersCheck.h"
 #include "UnusedUsingDeclsCheck.h"
 
 namespace clang {
 namespace tidy {
 namespace misc {
 
 class MiscModule : public ClangTidyModule {
 public:
   void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<DefinitionsInHeadersCheck>(
         "misc-definitions-in-headers");
     CheckFactories.registerCheck<MisplacedConstCheck>("misc-misplaced-const");
     CheckFactories.registerCheck<NewDeleteOverloadsCheck>(
         "misc-new-delete-overloads");
+    CheckFactories.registerCheck<NoRecursionCheck>("misc-no-recursion");
     CheckFactories.registerCheck<NonCopyableObjectsCheck>(
         "misc-non-copyable-objects");
     CheckFactories.registerCheck<NonPrivateMemberVariablesInClassesCheck>(
         "misc-non-private-member-variables-in-classes");
     CheckFactories.registerCheck<RedundantExpressionCheck>(
         "misc-redundant-expression");
     CheckFactories.registerCheck<StaticAssertCheck>("misc-static-assert");
     CheckFactories.registerCheck<ThrowByValueCatchByReferenceCheck>(

clang-tools-extra/clang-tidy/misc/NoRecursionCheck.h

+//===--- NoRecursionCheck.h - clang-tidy ------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_NORECURSIONCHECK_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_NORECURSIONCHECK_H
+
+#include "../ClangTidyCheck.h"
+
+namespace clang {
+
+class CallGraphNode;
+
+namespace tidy {
+namespace misc {
+
+/// Finds strongly connected functions (by analyzing call graph for SCC's
+/// that are loops), diagnoses each function in the cycle,
+/// and displays one example of possible call graph loop (recursion).
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/misc-no-recursion.html
+class NoRecursionCheck : public ClangTidyCheck {
+public:
+  NoRecursionCheck(StringRef Name, ClangTidyContext *Context)
+      : ClangTidyCheck(Name, Context) {}
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+
+private:
+  void handleSCC(ArrayRef<CallGraphNode *> SCC);
+};
+
+} // namespace misc
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_NORECURSIONCHECK_H

clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp

+//===--- NoRecursionCheck.cpp - clang-tidy --------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "NoRecursionCheck.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Analysis/CallGraph.h"
+#include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/SCCIterator.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace misc {
+
+namespace {
+
+// Much like SmallSet, with two differences:
+// 1. It can *only* be constructed from an ArrayRef<>. If the element count
+//    is small, there is no copy and said storage *must* outlive us.
+// 2. it is immutable, the way it was constructed it will stay.
+template <typename T, unsigned SmallSize> class ImmutableSmartSet {
+  ArrayRef<T> Vector;
+  llvm::DenseSet<T> Set;
+
+  static_assert(SmallSize <= 32, "N should be small");
+
+  bool isSmall() const { return Set.empty(); }
+
+public:
+  using size_type = size_t;
+
+  ImmutableSmartSet() = delete;
+  ImmutableSmartSet(const ImmutableSmartSet &) = delete;
+  ImmutableSmartSet(ImmutableSmartSet &&) = delete;
+  T &operator=(const ImmutableSmartSet &) = delete;
+  T &operator=(ImmutableSmartSet &&) = delete;
+
+  // WARNING: Storage *must* outlive us if we decide that the size is small.
+  ImmutableSmartSet(ArrayRef<T> Storage) {
+    // Is size small-enough to just keep using the existing storage?
+    if (Storage.size() <= SmallSize) {
+      Vector = Storage;
+      return;
+    }
+
+    // We've decided that it isn't performant to keep using vector.
+    // Let's migrate the data into Set.
+    Set.reserve(Storage.size());
+    Set.insert(Storage.begin(), Storage.end());
+  }
+
+  /// count - Return 1 if the element is in the set, 0 otherwise.
+  size_type count(const T &V) const {
+    if (isSmall()) {
+      // Since the collection is small, just do a linear search.
+      return llvm::find(Vector, V) == Vector.end() ? 0 : 1;
+    } else {
+      return Set.count(V);
+    }
+  }
+};
+
+template <typename T, unsigned SmallSize> class SmartSmallSetVector {
+public:
+  using size_type = size_t;
+
+private:
+  SmallVector<T, SmallSize> Vector;
+  llvm::DenseSet<T> Set;
+
+  static_assert(SmallSize <= 32, "N should be small");
+
+  // Are we still using Vector for uniqness tracking?
+  bool isSmall() const { return Set.empty(); }
+
+  // Will one more entry cause Vector to switch away from small-size storage?
+  bool entiretyOfVectorSmallSizeIsOccupied() const {
+    assert(isSmall() && Vector.size() <= SmallSize &&
+           "Shouldn't ask if we have already [should have] migrated into Set.");
+    return Vector.size() == SmallSize;
+  }
+
+  void populateSet() {
+    assert(Set.empty() && "Should not have already utilized the Set.");
+    // Magical growth factor prediction - to how many elements do we expect to
+    // sanely grow after switching away from small-size storage?
+    const size_t NewMaxElts = 4 * Vector.size();
+    Vector.reserve(NewMaxElts);
+    Set.reserve(NewMaxElts);
+    Set.insert(Vector.begin(), Vector.end());
+  }
+
+  /// count - Return 1 if the element is in the set, 0 otherwise.
+  size_type count(const T &V) const {
+    if (isSmall()) {
+      // Since the collection is small, just do a linear search.
+      return llvm::find(Vector, V) == Vector.end() ? 0 : 1;
+    }
+    // Look-up in the Set.
+    return Set.count(V);
+  }
+
+  bool setInsert(const T &V) {
+    if (count(V) != 0)
+      return false; // Already exists.
+    // Does not exist, Can/need to record it.
+    if (isSmall()) { // Are we still using Vector for uniqness tracking?
+      // Will one more entry fit within small-sized Vector?
+      if (!entiretyOfVectorSmallSizeIsOccupied())
+        return true; // We'll insert into vector right afterwards anyway.
+      // Time to switch to Set.
+      populateSet();
+    }
+    // Set time!
+    // Note that this must be after `populateSet()` might have been called.
+    bool SetInsertionSucceeded = Set.insert(V).second;
+    (void)SetInsertionSucceeded;
+    assert(SetInsertionSucceeded && "We did check that no such value existed");
+    return true;
+  }
+
+public:
+  /// Insert a new element into the SmartSmallSetVector.
+  /// \returns true if the element was inserted into the SmartSmallSetVector.
+  bool insert(const T &X) {
+    bool result = setInsert(X);
+    if (result)
+      Vector.push_back(X);
+    return result;
+  }
+
+  /// Clear the SmartSmallSetVector and return the underlying vector.
+  decltype(Vector) takeVector() {
+    Set.clear();
+    return std::move(Vector);
+  }
+};
+
+constexpr unsigned SmallCallStackSize = 16;
+constexpr unsigned SmallSCCSize = 32;
+
+using CallStackTy =
+    llvm::SmallVector<CallGraphNode::CallRecord, SmallCallStackSize>;
+
+// In given SCC, find *some* call stack that will be cyclic.
+// This will only find *one* such stack, it might not be the smallest one,
+// and there may be other loops.
+CallStackTy PathfindSomeCycle(ArrayRef<CallGraphNode *> SCC) {
+  // We'll need to be able to performantly look up whether some CallGraphNode
+  // is in SCC or not, so cache all the SCC elements in a set.
+  const ImmutableSmartSet<CallGraphNode *, SmallSCCSize> SCCElts(SCC);
+
+  // Is node N part if the current SCC?
+  auto NodeIsPartOfSCC = [&SCCElts](CallGraphNode *N) {
+    return SCCElts.count(N) != 0;
+  };
+
+  // Track the call stack that will cause a cycle.
+  SmartSmallSetVector<CallGraphNode::CallRecord, SmallCallStackSize>
+      CallStackSet;
+
+  // Arbitrairly take the first element of SCC as entry point.
+  CallGraphNode::CallRecord EntryNode(SCC.front(), /*CallExpr=*/nullptr);
+  // Continue recursing into subsequent callees that are part of this SCC,
+  // and are thus known to be part of the call graph loop, until loop forms.
+  CallGraphNode::CallRecord *Node = &EntryNode;
+  while (true) {
+    // Did we see this node before?
+    if (!CallStackSet.insert(*Node))
+      break; // Cycle completed! Note that didn't insert the node into stack!
+    // Else, perform depth-first traversal: out of all callees, pick first one
+    // that is part of this SCC. This is not guaranteed to yield shortest cycle.
+    Node = llvm::find_if(Node->Callee->callees(), NodeIsPartOfSCC);
+  }
+
+  // Note that we failed to insert the last node, that completes the cycle.
+  // But we really want to have it. So insert it manually into stack only.
+  CallStackTy CallStack = CallStackSet.takeVector();
+  CallStack.emplace_back(*Node);
+
+  return CallStack;
+}
+
+} // namespace
+
+void NoRecursionCheck::registerMatchers(MatchFinder *Finder) {
+  Finder->addMatcher(translationUnitDecl().bind("TUDecl"), this);
+}
+
+void NoRecursionCheck::handleSCC(ArrayRef<CallGraphNode *> SCC) {
+  assert(!SCC.empty() && "Empty SCC does not make sense.");
+
+  // First of all, call out every stongly connected function.
+  for (CallGraphNode *N : SCC) {
+    Decl *D = N->getDecl();
+    diag(D->getLocation(), "function '%0' is part of call graph loop")
+        << cast<NamedDecl>(D)->getName();
+  }
+
+  // Now, SCC only tells us about strongly connected function declarations in
+  // the call graph. It doesn't *really* tell us about the cycles they form.
+  // And there may be more than one cycle in SCC.
+  // So let's form a call stack that eventually exposes *some* cycle.
+  const CallStackTy EventuallyCyclicCallStack = PathfindSomeCycle(SCC);
+  assert(!EventuallyCyclicCallStack.empty() && "We should've found the cycle");
+
+  // While last node of the call stack does cause a loop, due to the way we
+  // pathfind the cycle, the loop does not nessesairly begin at the first node
+  // of the call stack, so drop front nodes of the call stack until it does.
+  const auto CyclicCallStack =
+      ArrayRef<CallGraphNode::CallRecord>(EventuallyCyclicCallStack)
+          .drop_until([LastNode = EventuallyCyclicCallStack.back()](
+                          CallGraphNode::CallRecord FrontNode) {
+            return FrontNode == LastNode;
+          });
+  assert(CyclicCallStack.size() >= 2 && "Cycle requires at least 2 frames");
+
+  // Which function we decided to be the entry point that lead to the recursion?
+  Decl *CycleEntryFn = CyclicCallStack.front().Callee->getDecl();
+  // And now, for ease of understanding, let's print the call sequence that
+  // forms the cycle in question.
+  diag(CycleEntryFn->getLocation(),
+       "Example call graph loop, starting from function '%0'",
+       DiagnosticIDs::Note)
+      << cast<NamedDecl>(CycleEntryFn)->getName();
+  for (int CurFrame = 1, NumFrames = CyclicCallStack.size();
+       CurFrame != NumFrames; ++CurFrame) {
+    CallGraphNode::CallRecord PrevNode = CyclicCallStack[CurFrame - 1];
+    CallGraphNode::CallRecord CurrNode = CyclicCallStack[CurFrame];
+
+    Decl *PrevDecl = PrevNode.Callee->getDecl();
+    Decl *CurrDecl = CurrNode.Callee->getDecl();
+
+    diag(CurrNode.CallExpr->getBeginLoc(),
+         "Frame #%0: function '%1' calls function '%2' here:",
+         DiagnosticIDs::Note)
+        << CurFrame << cast<NamedDecl>(PrevDecl)->getName()
+        << cast<NamedDecl>(CurrDecl)->getName();
+  }
+
+  diag(CyclicCallStack.back().CallExpr->getBeginLoc(),
+       "... which was the starting point of this call graph\n"
+       "This report is non-exhaustive. There may be other cycles.",
+       DiagnosticIDs::Note);
+}
+
+void NoRecursionCheck::check(const MatchFinder::MatchResult &Result) {
+  // Build call graph for the entire translation unit.
+  const auto *TU = Result.Nodes.getNodeAs<TranslationUnitDecl>("TUDecl");
+  CallGraph CG;
+  CG.addToCallGraph(const_cast<TranslationUnitDecl *>(TU));
+  // CG.viewGraph();
+
+  // Look for cycles in call graph,
+  // by looking for Strongly Connected Comonents (SCC's)
+  for (llvm::scc_iterator<CallGraph *> SCCI = llvm::scc_begin(&CG),
+                                       SCCE = llvm::scc_end(&CG);
+       SCCI != SCCE; ++SCCI) {
+    if (!SCCI.hasLoop()) // We only care about cycles, not standalone nodes.
+      continue;
+    handleSCC(*SCCI);
+  }
+}
+
+} // namespace misc
+} // namespace tidy
+} // namespace clang

clang-tools-extra/docs/ReleaseNotes.rst

 The improvements are...
 
 Improvements to clang-tidy
 --------------------------
 
 New checks
 ^^^^^^^^^^
 
 - New :doc:`bugprone-misplaced-pointer-arithmetic-in-alloc
   <clang-tidy/checks/bugprone-misplaced-pointer-arithmetic-in-alloc>` check.
 
   Finds cases where an integer expression is added to or subtracted from the
   result of a memory allocation function (``malloc()``, ``calloc()``,
   ``realloc()``, ``alloca()``) instead of its argument.
 
 - New :doc:`bugprone-reserved-identifier
   <clang-tidy/checks/bugprone-reserved-identifier>` check.
 
   Checks for usages of identifiers reserved for use by the implementation.
   
 - New :doc:`cert-oop57-cpp
   <clang-tidy/checks/cert-oop57-cpp>` check.
   
   Flags use of the `C` standard library functions ``memset``, ``memcpy`` and
   ``memcmp`` and similar derivatives on non-trivial types.
 
+- New :doc:`misc-no-recursion
+  <clang-tidy/checks/misc-no-recursion>` check.
+
+  Finds recursive functions and diagnoses them.
+
 New check aliases
 ^^^^^^^^^^^^^^^^^
 
 - New alias :doc:`cert-dcl37-c
   <clang-tidy/checks/cert-dcl37-c>` to
   :doc:`bugprone-reserved-identifier
   <clang-tidy/checks/bugprone-reserved-identifier>` was added.
 

clang-tools-extra/docs/clang-tidy/checks/list.rst

.. csv-table::
    `llvm-include-order <llvm-include-order.html>`_, "Yes"
    `llvm-namespace-comment <llvm-namespace-comment.html>`_,
    `llvm-prefer-isa-or-dyn-cast-in-conditionals <llvm-prefer-isa-or-dyn-cast-in-conditionals.html>`_, "Yes"
    `llvm-prefer-register-over-unsigned <llvm-prefer-register-over-unsigned.html>`_, "Yes"
    `llvm-twine-local <llvm-twine-local.html>`_, "Yes"
    `misc-definitions-in-headers <misc-definitions-in-headers.html>`_, "Yes"
    `misc-misplaced-const <misc-misplaced-const.html>`_,
    `misc-new-delete-overloads <misc-new-delete-overloads.html>`_,
+   `misc-no-recursion <misc-no-recursion>`_,
    `misc-non-copyable-objects <misc-non-copyable-objects.html>`_,
    `misc-non-private-member-variables-in-classes <misc-non-private-member-variables-in-classes.html>`_,
    `misc-redundant-expression <misc-redundant-expression.html>`_, "Yes"
    `misc-static-assert <misc-static-assert.html>`_, "Yes"
    `misc-throw-by-value-catch-by-reference <misc-throw-by-value-catch-by-reference.html>`_,
    `misc-unconventional-assign-operator <misc-unconventional-assign-operator.html>`_,
    `misc-uniqueptr-reset-release <misc-uniqueptr-reset-release.html>`_, "Yes"
    `misc-unused-alias-decls <misc-unused-alias-decls.html>`_, "Yes"

clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst

+.. title:: clang-tidy - misc-no-recursion
+
+misc-no-recursion
+=================
+
+Finds strongly connected functions (by analyzing call graph for SCC's
+that are loops), diagnoses each function in the cycle,
+and displays one example of possible call graph loop (recursion).

clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp

+// RUN: %check_clang_tidy %s misc-no-recursion %t
+
+// We don't have the definition of this function,
+// so we can't tell anything about it..
+void external();
+
+// This function is obviously not recursive.
+void no_recursion() {
+}
+
+// Since we don't know what `external()` does,
+// we don't know if this is recursive or not.
+void maybe_no_recursion() {
+  external();
+}
+
+// Function calls itself - obviously a recursion.
+void endless_recursion() {
+  endless_recursion();
+}
+
+// CHECK-NOTES: :[[@LINE-4]]:6: warning: function 'endless_recursion' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-5]]:6: note: Example call graph loop, starting from function 'endless_recursion'
+// CHECK-NOTES: :[[@LINE-5]]:3: note: Frame #1: function 'endless_recursion' calls function 'endless_recursion' here:
+// CHECK-NOTES: :[[@LINE-6]]:3: note: ... which was the starting point of this call graph
+// CHECK-NOTES: :[[@LINE-7]]:3: note: This report is non-exhaustive. There may be other cycles.
+
+bool external_oracle();
+bool another_external_oracle();
+
+// Function calls itself if some external function said so - recursion.
+void maybe_endless_recursion() {
+  if (external_oracle())
+    maybe_endless_recursion();
+}
+
+// CHECK-NOTES: :[[@LINE-5]]:6: warning: function 'maybe_endless_recursion' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-6]]:6: note: Example call graph loop, starting from function 'maybe_endless_recursion'
+// CHECK-NOTES: :[[@LINE-5]]:5: note: Frame #1: function 'maybe_endless_recursion' calls function 'maybe_endless_recursion' here:
+// CHECK-NOTES: :[[@LINE-6]]:5: note: ... which was the starting point of this call graph
+// CHECK-NOTES: :[[@LINE-7]]:5: note: This report is non-exhaustive. There may be other cycles.
+
+// Obviously-constrained recursion.
+void recursive_countdown(unsigned x) {
+  if (x == 0)
+    return;
+  recursive_countdown(x - 1);
+}
+
+// CHECK-NOTES: :[[@LINE-6]]:6: warning: function 'recursive_countdown' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-7]]:6: note: Example call graph loop, starting from function 'recursive_countdown'
+// CHECK-NOTES: :[[@LINE-5]]:3: note: Frame #1: function 'recursive_countdown' calls function 'recursive_countdown' here:
+// CHECK-NOTES: :[[@LINE-6]]:3: note: ... which was the starting point of this call graph
+// CHECK-NOTES: :[[@LINE-7]]:3: note: This report is non-exhaustive. There may be other cycles.
+
+void indirect_recursion();
+void conditionally_executed() {
+  if (external_oracle())
+    indirect_recursion();
+}
+void indirect_recursion() {
+  if (external_oracle())
+    conditionally_executed();
+}
+
+// CHECK-NOTES: :[[@LINE-10]]:6: warning: function 'indirect_recursion' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-10]]:6: warning: function 'conditionally_executed' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-12]]:6: note: Example call graph loop, starting from function 'indirect_recursion'
+// CHECK-NOTES: :[[@LINE-6]]:5: note: Frame #1: function 'indirect_recursion' calls function 'conditionally_executed' here:
+// CHECK-NOTES: :[[@LINE-11]]:5: note: Frame #2: function 'conditionally_executed' calls function 'indirect_recursion' here:
+// CHECK-NOTES: :[[@LINE-12]]:5: note: ... which was the starting point of this call graph
+// CHECK-NOTES: :[[@LINE-13]]:5: note: This report is non-exhaustive. There may be other cycles.
+
+void taint();
+void maybe_selfrecursion_with_two_backedges() {
+  if (external_oracle())
+    maybe_selfrecursion_with_two_backedges();
+  taint();
+  if (another_external_oracle())
+    maybe_selfrecursion_with_two_backedges();
+}
+
+// CHECK-NOTES: :[[@LINE-8]]:6: warning: function 'maybe_selfrecursion_with_two_backedges' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-9]]:6: note: Example call graph loop, starting from function 'maybe_selfrecursion_with_two_backedges'
+// CHECK-NOTES: :[[@LINE-8]]:5: note: Frame #1: function 'maybe_selfrecursion_with_two_backedges' calls function 'maybe_selfrecursion_with_two_backedges' here:
+// CHECK-NOTES: :[[@LINE-9]]:5: note: ... which was the starting point of this call graph
+// CHECK-NOTES: :[[@LINE-10]]:5: note: This report is non-exhaustive. There may be other cycles.
+
+void indirect_recursion_with_alternatives();
+void conditionally_executed_choice_0() {
+  if (external_oracle())
+    indirect_recursion_with_alternatives();
+}
+void conditionally_executed_choice_1() {
+  if (external_oracle())
+    indirect_recursion_with_alternatives();
+}
+void indirect_recursion_with_alternatives() {
+  if (external_oracle())
+    conditionally_executed_choice_0();
+  else
+    conditionally_executed_choice_1();
+}
+
+// CHECK-NOTES: :[[@LINE-16]]:6: warning: function 'indirect_recursion_with_alternatives' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-16]]:6: warning: function 'conditionally_executed_choice_0' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-18]]:6: note: Example call graph loop, starting from function 'indirect_recursion_with_alternatives'
+// CHECK-NOTES: :[[@LINE-8]]:5: note: Frame #1: function 'indirect_recursion_with_alternatives' calls function 'conditionally_executed_choice_0' here:
+// CHECK-NOTES: :[[@LINE-17]]:5: note: Frame #2: function 'conditionally_executed_choice_0' calls function 'indirect_recursion_with_alternatives' here:
+// CHECK-NOTES: :[[@LINE-18]]:5: note: ... which was the starting point of this call graph
+// CHECK-NOTES: :[[@LINE-19]]:5: note: This report is non-exhaustive. There may be other cycles.
+// CHECK-NOTES: :[[@LINE-18]]:6: warning: function 'conditionally_executed_choice_1' is part of call graph loop [misc-no-recursion]
+
+static void indirect_recursion_with_depth2();
+static void conditionally_executed_depth1() {
+  if (external_oracle())
+    indirect_recursion_with_depth2();
+}
+static void conditionally_executed_depth0() {
+  if (external_oracle())
+    conditionally_executed_depth1();
+}
+void indirect_recursion_with_depth2() {
+  if (external_oracle())
+    conditionally_executed_depth0();
+}
+
+// CHECK-NOTES: :[[@LINE-14]]:13: warning: function 'indirect_recursion_with_depth2' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-14]]:13: warning: function 'conditionally_executed_depth1' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-11]]:13: note: Example call graph loop, starting from function 'conditionally_executed_depth0'
+// CHECK-NOTES: :[[@LINE-10]]:5: note: Frame #1: function 'conditionally_executed_depth0' calls function 'conditionally_executed_depth1' here:
+// CHECK-NOTES: :[[@LINE-15]]:5: note: Frame #2: function 'conditionally_executed_depth1' calls function 'indirect_recursion_with_depth2' here:
+// CHECK-NOTES: :[[@LINE-8]]:5: note: Frame #3: function 'indirect_recursion_with_depth2' calls function 'conditionally_executed_depth0' here:
+// CHECK-NOTES: :[[@LINE-9]]:5: note: ... which was the starting point of this call graph
+// CHECK-NOTES: :[[@LINE-10]]:5: note: This report is non-exhaustive. There may be other cycles.
+// CHECK-NOTES: :[[@LINE-17]]:13: warning: function 'conditionally_executed_depth0' is part of call graph loop [misc-no-recursion]
+
+int boo();
+void foo(int x = boo()) {}
+void bar() {
+  foo();
+  foo();
+}
+int boo() {
+  bar();
+  return 0;
+}
+
+// CHECK-NOTES: :[[@LINE-11]]:5: warning: function 'boo' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-10]]:6: warning: function 'bar' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-13]]:5: note: Example call graph loop, starting from function 'boo'
+// CHECK-NOTES: :[[@LINE-7]]:3: note: Frame #1: function 'boo' calls function 'bar' here:
+// CHECK-NOTES: :[[@LINE-14]]:18: note: Frame #2: function 'bar' calls function 'boo' here:
+// CHECK-NOTES: :[[@LINE-15]]:18: note: ... which was the starting point of this call graph
+// CHECK-NOTES: :[[@LINE-16]]:18: note: This report is non-exhaustive. There may be other cycles.