[PATCH] D126077: Fix stack crash in classIsDerivedFrom triggered by clang-tidy

[Anton Fedorov via Phabricator via cfe-commits]

datacompboy created this revision.
datacompboy added reviewers: bixia, aartbik.
Herald added a project: All.
datacompboy requested review of this revision.
Herald added projects: clang, clang-tools-extra.
Herald added a subscriber: cfe-commits.

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


Repository:
  rG LLVM Github Monorepo

https://reviews.llvm.org/D126077

Files:
  clang-tools-extra/test/clang-tidy/infrastructure/recursive-templates.cpp
  clang/lib/ASTMatchers/ASTMatchFinder.cpp

Index: clang/lib/ASTMatchers/ASTMatchFinder.cpp
===
--- clang/lib/ASTMatchers/ASTMatchFinder.cpp
+++ clang/lib/ASTMatchers/ASTMatchFinder.cpp
@@ -44,6 +44,12 @@
 // optimize this on.
 static const unsigned MaxMemoizationEntries = 1;
 
+// 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 = 1;
+
 enum class MatchType {
   Ancestors,
 
@@ -1357,35 +1363,47 @@
 // 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 &Base,
  BoundNodesTreeBuilder *Builder,
  bool Directly) {
-  if (!Declaration->hasDefinition())
-return false;
-  for (const auto &It : Declaration->bases()) {
-const Type *TypeNode = It.getType().getTypePtr();
+  SmallVector 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;
+  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;
+  // 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) {
+DeclarationsStack.push_back(ClassDecl);
+  }
 }
-if (!Directly && classIsDerivedFrom(ClassDecl, Base, Builder, Directly))
-  return true;
   }
   return false;
 }
Index: clang-tools-extra/test/clang-tidy/infrastructure/recursive-templates.cpp
===
--- /dev/null
+++ clang-tools-extra/test/clang-tidy/infrastructure/recursive-templates.cpp
@@ -0,0 +1,14 @@
+// Regression test: shouldn't crash.
+// RUN: clang-tidy %s -checks='*' -- | FileCheck %s
+template struct t1;
+template struct t2: t1< T > {};
+template struct t1: t2< T > {};
+
+int main() {
+  return 0;
+}
+
+namespace i {
+}
+// CHECK: warning: namespace 'i' not terminated with a closing comment [llvm-namespace-comment]
+
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://

[PATCH] D126077: Fix stack crash in classIsDerivedFrom triggered by clang-tidy

[Anton Fedorov via Phabricator via cfe-commits]

datacompboy updated this revision to Diff 431339.

Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D126077

Files:
  clang/lib/ASTMatchers/ASTMatchFinder.cpp
  clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp

Index: clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
===
--- clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
+++ clang/unittests/ASTMatchers/ASTMatchersTraversalTest.cpp
@@ -168,6 +168,14 @@
varDecl(hasType(namedDecl(hasName("S"));
 }
 
+TEST(TypeMatcherDeathTest, isDerivedRecursion) {
+  EXPECT_TRUE(notMatches(
+  "template struct t1;"
+  "template struct t2: t1< T > {};"
+  "template struct t1: t2< T > {};",
+  cxxRecordDecl(isDerivedFrom("::T";
+}
+
 TEST(TypeMatcher, MatchesDeclTypes) {
   // TypedefType -> TypedefNameDecl
   EXPECT_TRUE(matches("typedef int I; void f(I i);",
Index: clang/lib/ASTMatchers/ASTMatchFinder.cpp
===
--- clang/lib/ASTMatchers/ASTMatchFinder.cpp
+++ clang/lib/ASTMatchers/ASTMatchFinder.cpp
@@ -44,6 +44,12 @@
 // optimize this on.
 static const unsigned MaxMemoizationEntries = 1;
 
+// 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 = 1;
+
 enum class MatchType {
   Ancestors,
 
@@ -1357,35 +1363,47 @@
 // 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 &Base,
  BoundNodesTreeBuilder *Builder,
  bool Directly) {
-  if (!Declaration->hasDefinition())
-return false;
-  for (const auto &It : Declaration->bases()) {
-const Type *TypeNode = It.getType().getTypePtr();
+  SmallVector 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;
+  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;
+  // 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) {
+DeclarationsStack.push_back(ClassDecl);
+  }
 }
-if (!Directly && classIsDerivedFrom(ClassDecl, Base, Builder, Directly))
-  return true;
   }
   return false;
 }
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D126077: Fix stack crash in classIsDerivedFrom triggered by clang-tidy

[Anton Fedorov via Phabricator via cfe-commits]

datacompboy added a comment.

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?


Repository:
  rG LLVM Github Monorepo

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

https://reviews.llvm.org/D126077

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits