lebedev.ri updated this revision to Diff 244509.
lebedev.ri marked 8 inline comments as done.
lebedev.ri added a comment.

In D72362#1874690 <https://reviews.llvm.org/D72362#1874690>, @aaron.ballman 
wrote:

> LGTM aside from some nits.


Thank you for the review!
Nits addressed.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362

Files:
  clang-tools-extra/clang-tidy/misc/CMakeLists.txt
  clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp
  clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp
  clang-tools-extra/clang-tidy/misc/NoRecursionCheck.h
  clang-tools-extra/docs/ReleaseNotes.rst
  clang-tools-extra/docs/clang-tidy/checks/list.rst
  clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst
  clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp

Index: clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp
===================================================================
--- /dev/null
+++ clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp
@@ -0,0 +1,179 @@
+// 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 within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-5]]:6: note: example recursive call chain, 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 the recursive call chain; 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 within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-6]]:6: note: example recursive call chain, 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 the recursive call chain; 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 within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-7]]:6: note: example recursive call chain, 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 the recursive call chain; 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 within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-10]]:6: warning: function 'conditionally_executed' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-12]]:6: note: example recursive call chain, 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 the recursive call chain; 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 within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-9]]:6: note: example recursive call chain, 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 the recursive call chain; 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 within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-16]]:6: warning: function 'conditionally_executed_choice_0' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-18]]:6: note: example recursive call chain, 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 the recursive call chain; there may be other cycles
+// CHECK-NOTES: :[[@LINE-17]]:6: warning: function 'conditionally_executed_choice_1' is within a recursive call chain [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 within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-14]]:13: warning: function 'conditionally_executed_depth1' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-11]]:13: note: example recursive call chain, 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 the recursive call chain; there may be other cycles
+// CHECK-NOTES: :[[@LINE-16]]:13: warning: function 'conditionally_executed_depth0' is within a recursive call chain [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 within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-10]]:6: warning: function 'bar' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-13]]:5: note: example recursive call chain, 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 the recursive call chain; there may be other cycles
+
+int recursion_through_function_ptr() {
+  auto *ptr = &recursion_through_function_ptr;
+  if (external_oracle())
+    return ptr();
+  return 0;
+}
+
+int recursion_through_lambda() {
+  auto zz = []() {
+    if (external_oracle())
+      return recursion_through_lambda();
+    return 0;
+  };
+  return zz();
+}
+
+// CHECK-NOTES: :[[@LINE-9]]:5: warning: function 'recursion_through_lambda' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-9]]:13: note: example recursive call chain, starting from function 'operator()'
+// CHECK-NOTES: :[[@LINE-8]]:14: note: Frame #1: function 'operator()' calls function 'recursion_through_lambda' here:
+// CHECK-NOTES: :[[@LINE-6]]:10: note: Frame #2: function 'recursion_through_lambda' calls function 'operator()' here:
+// CHECK-NOTES: :[[@LINE-7]]:10: note: ... which was the starting point of the recursive call chain; there may be other cycles
+// CHECK-NOTES: :[[@LINE-13]]:13: warning: function 'operator()' is within a recursive call chain [misc-no-recursion]
+
+struct recursion_through_destructor {
+  ~recursion_through_destructor() {
+    if (external_oracle()) {
+      recursion_through_destructor variable;
+      // variable goes out of scope, it's destructor runs, and we are back here.
+    }
+  }
+};
Index: clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst
===================================================================
--- /dev/null
+++ clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst
@@ -0,0 +1,18 @@
+.. title:: clang-tidy - misc-no-recursion
+
+misc-no-recursion
+=================
+
+Finds strongly connected functions (by analyzing the call graph for
+SCC's (Strongly Connected Components) that are loops),
+diagnoses each function in the cycle,
+and displays one example of a possible call graph loop (recursion).
+
+References:
+* CERT C++ Coding Standard rule `DCL56-CPP. Avoid cycles during initialization of static objects <https://wiki.sei.cmu.edu/confluence/display/cplusplus/DCL56-CPP.+Avoid+cycles+during+initialization+of+static+objects>`_.
+* JPL Institutional Coding Standard for the C Programming Language (JPL DOCID D-60411) rule `2.4 Do not use direct or indirect recursion`.
+* OpenCL Specification, Version 1.2 rule `6.9 Restrictions: i. Recursion is not supported. <https://www.khronos.org/registry/OpenCL/specs/opencl-1.2.pdf>`_.
+
+Limitations:
+* The check does not handle calls done through function pointers
+* The check does not handle C++ destructors
Index: clang-tools-extra/docs/clang-tidy/checks/list.rst
===================================================================
--- clang-tools-extra/docs/clang-tidy/checks/list.rst
+++ clang-tools-extra/docs/clang-tidy/checks/list.rst
@@ -189,6 +189,7 @@
    `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"
Index: clang-tools-extra/docs/ReleaseNotes.rst
===================================================================
--- clang-tools-extra/docs/ReleaseNotes.rst
+++ clang-tools-extra/docs/ReleaseNotes.rst
@@ -93,6 +93,11 @@
 
   Finds implementations of -dealloc in Objective-C categories.
 
+- New :doc:`misc-no-recursion
+  <clang-tidy/checks/misc-no-recursion>` check.
+
+  Finds recursive functions and diagnoses them.
+
 New check aliases
 ^^^^^^^^^^^^^^^^^
 
Index: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.h
===================================================================
--- /dev/null
+++ clang-tools-extra/clang-tidy/misc/NoRecursionCheck.h
@@ -0,0 +1,42 @@
+//===--- 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
Index: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp
===================================================================
--- /dev/null
+++ clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp
@@ -0,0 +1,276 @@
+//===--- 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 ImmutableSmallSet {
+  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;
+
+  ImmutableSmallSet() = delete;
+  ImmutableSmallSet(const ImmutableSmallSet &) = delete;
+  ImmutableSmallSet(ImmutableSmallSet &&) = delete;
+  T &operator=(const ImmutableSmallSet &) = delete;
+  T &operator=(ImmutableSmallSet &&) = delete;
+
+  // WARNING: Storage *must* outlive us if we decide that the size is small.
+  ImmutableSmallSet(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;
+    }
+
+    return Set.count(V);
+  }
+};
+
+/// Much like SmallSetVector, but with one difference:
+/// when the size is \p SmallSize or less, when checking whether an element is
+/// already in the set or not, we perform linear search over the vector,
+/// but if the size is larger than \p SmallSize, we look in set.
+/// FIXME: upstream this into SetVector/SmallSetVector itself.
+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 ImmutableSmallSet<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 within a recursive call chain")
+        << cast<NamedDecl>(D);
+  }
+
+  // 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 recursive call chain, starting from function %0",
+       DiagnosticIDs::Note)
+      << cast<NamedDecl>(CycleEntryFn);
+  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) << cast<NamedDecl>(CurrDecl);
+  }
+
+  diag(CyclicCallStack.back().CallExpr->getBeginLoc(),
+       "... which was the starting point of the recursive call chain; 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));
+
+  // 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
Index: clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp
===================================================================
--- clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp
+++ clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp
@@ -12,6 +12,7 @@
 #include "DefinitionsInHeadersCheck.h"
 #include "MisplacedConstCheck.h"
 #include "NewDeleteOverloadsCheck.h"
+#include "NoRecursionCheck.h"
 #include "NonCopyableObjects.h"
 #include "NonPrivateMemberVariablesInClassesCheck.h"
 #include "RedundantExpressionCheck.h"
@@ -35,6 +36,7 @@
     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>(
Index: clang-tools-extra/clang-tidy/misc/CMakeLists.txt
===================================================================
--- clang-tools-extra/clang-tidy/misc/CMakeLists.txt
+++ clang-tools-extra/clang-tidy/misc/CMakeLists.txt
@@ -5,6 +5,7 @@
   MiscTidyModule.cpp
   MisplacedConstCheck.cpp
   NewDeleteOverloadsCheck.cpp
+  NoRecursionCheck.cpp
   NonCopyableObjects.cpp
   NonPrivateMemberVariablesInClassesCheck.cpp
   RedundantExpressionCheck.cpp
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

Reply via email to