[ASTMatchers] Fix classIsDerivedFrom for recusrive cases (#67307)

By ensuring the base is only visited once. This avoids infinite
recursion and expontential running times in some corner cases.

See the added tests for examples.

Apart from the cases that caused infinite recursion and used to crash,
this change is an NFC and results of the matchers are the same.

1 files changed, 74 insertions, 0 deletions

diff --git a/clang/unittests/ASTMatchers/ASTMatchersNodeTest.cpp b/clang/unittests/ASTMatchers/ASTMatchersNodeTest.cpp
index 7a6d6ef..8f0dd56 100644
--- a/clang/unittests/ASTMatchers/ASTMatchersNodeTest.cpp
+++ b/clang/unittests/ASTMatchers/ASTMatchersNodeTest.cpp
@@ -2369,6 +2369,80 @@ TEST_P(ASTMatchersTest, LambdaCaptureTest_BindsToCaptureOfReferenceType) {
                        "}", matcher));
 }
 
+TEST_P(ASTMatchersTest, IsDerivedFromRecursion) {
+  if (!GetParam().isCXX11OrLater())
+    return;
+
+  // Check we don't crash on cycles in the traversal and inheritance hierarchy.
+  // Clang will normally enforce there are no cycles, but matchers opted to
+  // traverse primary template for dependent specializations, spuriously
+  // creating the cycles.
+  DeclarationMatcher matcher = cxxRecordDecl(isDerivedFrom("X"));
+  EXPECT_TRUE(notMatches(R"cpp(
+      template <typename T1, typename T2>
+      struct M;
+
+      template <typename T1>
+      struct M<T1, void> {};
+
+      template <typename T1, typename T2>
+      struct L : M<T1, T2> {};
+
+      template <typename T1, typename T2>
+      struct M : L<M<T1, T2>, M<T1, T2>> {};
+  )cpp",
+                         matcher));
+
+  // Check the running time is not exponential. The number of subojects to
+  // traverse grows as fibonacci numbers even though the number of bases to
+  // traverse is quadratic.
+  // The test will hang if implementation of matchers traverses all subojects.
+  EXPECT_TRUE(notMatches(R"cpp(
+    template <class T> struct A0 {};
+    template <class T> struct A1 : A0<T> {};
+    template <class T> struct A2 : A1<T>, A0<T> {};
+    template <class T> struct A3 : A2<T>, A1<T> {};
+    template <class T> struct A4 : A3<T>, A2<T> {};
+    template <class T> struct A5 : A4<T>, A3<T> {};
+    template <class T> struct A6 : A5<T>, A4<T> {};
+    template <class T> struct A7 : A6<T>, A5<T> {};
+    template <class T> struct A8 : A7<T>, A6<T> {};
+    template <class T> struct A9 : A8<T>, A7<T> {};
+    template <class T> struct A10 : A9<T>, A8<T> {};
+    template <class T> struct A11 : A10<T>, A9<T> {};
+    template <class T> struct A12 : A11<T>, A10<T> {};
+    template <class T> struct A13 : A12<T>, A11<T> {};
+    template <class T> struct A14 : A13<T>, A12<T> {};
+    template <class T> struct A15 : A14<T>, A13<T> {};
+    template <class T> struct A16 : A15<T>, A14<T> {};
+    template <class T> struct A17 : A16<T>, A15<T> {};
+    template <class T> struct A18 : A17<T>, A16<T> {};
+    template <class T> struct A19 : A18<T>, A17<T> {};
+    template <class T> struct A20 : A19<T>, A18<T> {};
+    template <class T> struct A21 : A20<T>, A19<T> {};
+    template <class T> struct A22 : A21<T>, A20<T> {};
+    template <class T> struct A23 : A22<T>, A21<T> {};
+    template <class T> struct A24 : A23<T>, A22<T> {};
+    template <class T> struct A25 : A24<T>, A23<T> {};
+    template <class T> struct A26 : A25<T>, A24<T> {};
+    template <class T> struct A27 : A26<T>, A25<T> {};
+    template <class T> struct A28 : A27<T>, A26<T> {};
+    template <class T> struct A29 : A28<T>, A27<T> {};
+    template <class T> struct A30 : A29<T>, A28<T> {};
+    template <class T> struct A31 : A30<T>, A29<T> {};
+    template <class T> struct A32 : A31<T>, A30<T> {};
+    template <class T> struct A33 : A32<T>, A31<T> {};
+    template <class T> struct A34 : A33<T>, A32<T> {};
+    template <class T> struct A35 : A34<T>, A33<T> {};
+    template <class T> struct A36 : A35<T>, A34<T> {};
+    template <class T> struct A37 : A36<T>, A35<T> {};
+    template <class T> struct A38 : A37<T>, A36<T> {};
+    template <class T> struct A39 : A38<T>, A37<T> {};
+    template <class T> struct A40 : A39<T>, A38<T> {};
+)cpp",
+                         matcher));
+}
+
 TEST(ASTMatchersTestObjC, ObjCMessageCalees) {
   StatementMatcher MessagingFoo =
       objcMessageExpr(callee(objcMethodDecl(hasName("foo"))));