Fix stack crash in classIsDerivedFrom triggered by clang-tidy

[datacompboy]

Summary

Protect classIsDerivedFrom from run-out-of-stack crash and infinity loop.

Rewrite recursion to loop-over-stack and add checks for complexity to avoid crash on deep definition or infinify recursion.

This fixes https://github.com/llvm/llvm-project/issues/55614

[njames93]

Do you know of any other instances where this issue could surface?

Please can you add a line to the Improved Checks section in clang-tools-extra/docs/ReleaseNotes.rst about this fix. Make sure it is in alphabetical order.

clang-tools-extra/test/clang-tidy/infrastructure/recursive-templates.cpp

2

Can you narrow down the check list to just include a check is causing the crash.
Also given we are only ensuring there is no crash, we don't need to invoke FileCheck. clang-tidy will return non-zero if it crashes, causing the whole test to fail.

8

This is different to the reproducer in the bug report as it doesn't have an instantiation of the struct in this test, unlike the bug report.

11–13

Definitely unrelated to this check and could safely be removed.

[datacompboy]

In D126077#3530189, @njames93 wrote:

Do you know of any other instances where this issue could surface?

I didn't found any other cases where isDerivedFrom used directly, only in couple of internal checks, none of which are part of clang distribution.

Please can you add a line to the Improved Checks section in clang-tools-extra/docs/ReleaseNotes.rst about this fix. Make sure it is in alphabetical order.

I removed test case from the clang-tidy and made a unit-test instead, so it's not affecting this section.
Do you think it worth to include in any other release notes sections?

clang-tools-extra/test/clang-tidy/infrastructure/recursive-templates.cpp

+// Regression test: shouldn't crash.
+// RUN: clang-tidy %s -checks='*' -- | FileCheck %s
+template<typename T> struct t1;
+template<typename T> struct t2: t1< T > {};
+template<typename T> struct t1: t2< T > {};
+
+int main() {
+  return 0;
+}
+
+namespace i {
+}
+// CHECK: warning: namespace 'i' not terminated with a closing comment [llvm-namespace-comment]
+

clang/lib/ASTMatchers/ASTMatchFinder.cpp

 // of performance vs. memory consumption by running matcher
 // that match on every statement over a very large codebase.
 //
 // FIXME: Do some performance optimization in general and
 // revisit this number; also, put up micro-benchmarks that we can
 // optimize this on.
 static const unsigned MaxMemoizationEntries = 10000;
 
+// The maximum number of steps thru ancestors allowed to run before
+// give up. The limit could only be hit by infinity / too deep
+// recursion or very complicated automatically generated types
+// inheritance.
+static const unsigned MaxDerivationComplexity = 10000;
+
 enum class MatchType {
   Ancestors,
 
   Descendants,
   Child,
 };
 
 // We use memoization to avoid running the same matcher on the same
if (auto *ClassTemplate = dyn_cast_or_null<ClassTemplateDecl>(
       return ClassTemplate->getTemplatedDecl();
 
   return nullptr;
 }
 
 // Returns true if the given C++ class is directly or indirectly derived
 // from a base type with the given name.  A class is not considered to be
 // derived from itself.
-bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *Declaration,
+bool MatchASTVisitor::classIsDerivedFrom(const CXXRecordDecl *DeclarationIn,
                                          const Matcher<NamedDecl> &Base,
                                          BoundNodesTreeBuilder *Builder,
                                          bool Directly) {
+  SmallVector<const CXXRecordDecl *> DeclarationsStack;
+  int iterations = 0;
+  DeclarationsStack.push_back(DeclarationIn);
+  while (!DeclarationsStack.empty()) {
+    const CXXRecordDecl *Declaration = DeclarationsStack.pop_back_val();
+    if (++iterations > MaxDerivationComplexity ||
+        DeclarationsStack.size() > MaxDerivationComplexity) {
+      // This can happen in case of too deep derivation chain or recursion.
+      return false;
+    }
     if (!Declaration->hasDefinition())
       return false;
     for (const auto &It : Declaration->bases()) {
       const Type *TypeNode = It.getType().getTypePtr();
 
       if (typeHasMatchingAlias(TypeNode, Base, Builder))
         return true;
 
       // FIXME: Going to the primary template here isn't really correct, but
       // unfortunately we accept a Decl matcher for the base class not a Type
       // matcher, so it's the best thing we can do with our current interface.
       CXXRecordDecl *ClassDecl = getAsCXXRecordDeclOrPrimaryTemplate(TypeNode);
       if (!ClassDecl)
         continue;
       if (ClassDecl == Declaration) {
         // This can happen for recursive template definitions.
         continue;
       }
       BoundNodesTreeBuilder Result(*Builder);
       if (Base.matches(*ClassDecl, this, &Result)) {
         *Builder = std::move(Result);
         return true;
       }
-    if (!Directly && classIsDerivedFrom(ClassDecl, Base, Builder, Directly))
-      return true;
+      if (!Directly) {
+        DeclarationsStack.push_back(ClassDecl);
+      }
+    }
   }
   return false;
 }
 
 // Returns true if the given Objective-C class is directly or indirectly
 // derived from a matching base class. A class is not considered to be derived
 // from itself.
 bool MatchASTVisitor::objcClassIsDerivedFrom(