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 ↗

(On Diff #431003)

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 ↗

(On Diff #431003)

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 ↗

(On Diff #431003)

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/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(

clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp

TEST(TypeMatcher, MatchesClassType) {
 
   EXPECT_TRUE(
     matches("class A { public: A *a; class B {}; };", TypeAHasClassB));
 
   EXPECT_TRUE(matchesC("struct S {}; void f(void) { struct S s; }",
                        varDecl(hasType(namedDecl(hasName("S"))))));
 }
 
+TEST(TypeMatcherDeathTest, isDerivedRecursion) {
+  EXPECT_TRUE(notMatches(
+      "template<typename T> struct t1;"
+      "template<typename T> struct t2: t1< T > {};"
+      "template<typename T> struct t1: t2< T > {};",
+      cxxRecordDecl(isDerivedFrom("::T"))));
+}
+
 TEST(TypeMatcher, MatchesDeclTypes) {
   // TypedefType -> TypedefNameDecl
   EXPECT_TRUE(matches("typedef int I; void f(I i);",
                       parmVarDecl(hasType(namedDecl(hasName("I"))))));
   // ObjCObjectPointerType
   EXPECT_TRUE(matchesObjC("@interface Foo @end void f(Foo *f);",
                           parmVarDecl(hasType(objcObjectPointerType()))));
   // ObjCObjectPointerType -> ObjCInterfaceType -> ObjCInterfaceDecl