[clangd] Avoid recursion in TargetFinder::add()

[nridge]

Summary

Fixes https://github.com/clangd/clangd/issues/633

[nridge]

clang-tools-extra/clangd/unittests/FindTargetTests.cpp

790

This test case is not strictly related to the bug, but it adds test coverage for a scenario that I think is important, and that could be broken if we took a different approach to fixing this bug (see my comments on the issue for details).

[njames93]

clang-tools-extra/clangd/FindTarget.cpp

333

Whats the purpose in tracking this? Is the Decls lookup not enough?

361–364

Couldn't this just be a map lookup?

[nridge]

clang-tools-extra/clangd/FindTarget.cpp

333

No, because the possibly-recursive call is here, but we only insert into Decls here.

361–364

Yup, good point!

[nridge]

Use map lookup instead of iteration

[kadircet]

clang-tools-extra/clangd/FindTarget.cpp

376

rather than introducing a new member for CurrentlyProcessing, can't we just get away with checking the decl we are going to jump on here (and probably in namespace alias case) are the same (or maybe a parameter to add function indicating the parent/previous)?

it is definitely cleaner to have a member rather than checking individually but we have other types of ast nodes we can be currently processing (statements, nested namespecifiers etc. and they are not covered by this member. so it is a little bit confusing conceptually.

[kadircet]

oh and also thanks a lot for all the investigation and fix of the issue!

[nridge]

clang-tools-extra/clangd/FindTarget.cpp

376

It takes a few steps to get back the recursive declaration:

• we start with the original declaration D
• we cast it to TypedefNameDecl here, call getUnderlyingType() and call add(QualType)
• in add(QualType), we construct a TypeVisitor and call Visit()
• the visitor gets into VisitDependentNameType(), calls getMembersReferencedViaDependentName(), and that gets us back the same declaration D which we call add(Decl) on

So, we'd have to propagate the "previous decl" into add(QualType) and make it a member of the TypeVisitor at least, to be able to check there.

[sammccall]

Doh, I really thought we'd get away without an explicit recursion guard here.
But the example is compelling, so this seems like the right approach. Unfortunately, I think we're going to end up needing to add allocations too...

clang-tools-extra/clangd/FindTarget.cpp

333

I don't think a single pointer is going to cut it here - can't we construct a mutually-recursive example so that the "wrong" decl is on always on top of the stack and we never bail out?

We probably want a SmallDenseMap Seen or something? (And then we no longer need to look up in the actual result set).

Couple of related refinements:

• Currently when we reach the same node via multiple flag paths, we take the union of the flags. (I'm not sure this is *great* behavior, but the API is pretty limiting). To be consistent with that here, we should store the flags for seen too, and union them when updating, and only bail out if we added no new flags. (This will almost never matter in practice, but it'd be nice not to worry)
• You could consider making the key type void* instead of decl* and also break loops with no decls in them. But this can certainly wait until we find such a loop!

333

No, because the possibly-recursive call is here, but we only insert into Decls here.

This is just for implementation convenience, we could reverse the order by rearranging the code somehow. However this seems fragile to me - I'm thinking about the cases where we reassign D in the function of the body here, and so end up reporting some other declaration instead (which may not be in the cycle).
So I think I like the solution in this patch better.

[nridge]

Address review comments

clang-tools-extra/clangd/FindTarget.h

public:
   DeclRelationSet &operator|=(DeclRelationSet Other) {
     S |= Other.S;
     return *this;
   }
   DeclRelationSet &operator&=(DeclRelationSet Other) {
     S &= Other.S;
     return *this;
   }
+  bool contains(DeclRelationSet Other) const {
+    return (S & Other.S) == Other.S;
+  }
   friend llvm::raw_ostream &operator<<(llvm::raw_ostream &, DeclRelationSet);
 };
 // The above operators can't be looked up if both sides are enums.
 // over.match.oper.html#3.2
 inline DeclRelationSet operator|(DeclRelation L, DeclRelation R) {
   return DeclRelationSet(L) | DeclRelationSet(R);
 }
 inline DeclRelationSet operator&(DeclRelation L, DeclRelation R) {

clang-tools-extra/clangd/FindTarget.cpp

 struct TargetFinder {
   using RelSet = DeclRelationSet;
   using Rel = DeclRelation;
 
 private:
   llvm::SmallDenseMap<const NamedDecl *,
                       std::pair<RelSet, /*InsertionOrder*/ size_t>>
       Decls;
+  llvm::SmallDenseMap<const Decl *, RelSet> Seen;
   RelSet Flags;
 
   template <typename T> void debug(T &Node, RelSet Flags) {
     dlog("visit [{0}] {1}", Flags, nodeToString(DynTypedNode::create(Node)));
   }
 
   void report(const NamedDecl *D, RelSet Flags) {
     dlog("--> [{0}] {1}", Flags, nodeToString(DynTypedNode::create(*D)));
llvm::SmallVector<std::pair<const NamedDecl *, RelSet>, 1> takeDecls() const {
     for (const auto &Elem : Decls)
       Result[Elem.second.second] = {Elem.first, Elem.second.first};
     return Result;
   }
 
   void add(const Decl *Dcl, RelSet Flags) {
     const NamedDecl *D = llvm::dyn_cast_or_null<NamedDecl>(Dcl);
     if (!D)
       return;
     debug(*D, Flags);
+
+    // Avoid recursion (which can arise in the presence of heuristic
+    // resolution of dependent names) by exiting early if we have
+    // already seen this decl with all flags in Flags.
+    auto Res = Seen.try_emplace(D);
+    if (!Res.second && Res.first->second.contains(Flags))
+      return;
+    Res.first->second |= Flags;
+
     if (const UsingDirectiveDecl *UDD = llvm::dyn_cast<UsingDirectiveDecl>(D))
       D = UDD->getNominatedNamespaceAsWritten();
 
     if (const TypedefNameDecl *TND = dyn_cast<TypedefNameDecl>(D)) {
       add(TND->getUnderlyingType(), Flags | Rel::Underlying);
       Flags |= Rel::Alias; // continue with the alias.
     } else if (const UsingDecl *UD = dyn_cast<UsingDecl>(D)) {
       // no Underlying as this is a non-renaming alias.
       for (const UsingShadowDecl *S : UD->shadows())
         add(S->getUnderlyingDecl(), Flags);
       Flags |= Rel::Alias; // continue with the alias.
     } else if (const auto *NAD = dyn_cast<NamespaceAliasDecl>(D)) {
       add(NAD->getUnderlyingDecl(), Flags | Rel::Underlying);

clang-tools-extra/clangd/unittests/FindTargetTests.cpp

Code = R"cpp(
 
         template <typename T>
         void foo(typename A<T>::template [[B]]<int>);
       )cpp";
   EXPECT_DECLS("DependentTemplateSpecializationTypeLoc",
                "template <typename> struct B");
 }
 
+TEST_F(TargetDeclTest, TypedefCascade) {
+  Code = R"cpp(
+        struct C {
+          using type = int;
+        };
+        struct B {
+          using type = C::type;
+        };
+        struct A {
+          using type = B::type;
+        };
+        A::[[type]] waldo;
+  )cpp";
+  EXPECT_DECLS("TypedefTypeLoc",
+               {"using type = int", Rel::Alias | Rel::Underlying},
+               {"using type = C::type", Rel::Alias | Rel::Underlying},
+               {"using type = B::type", Rel::Alias});
+}
+
+TEST_F(TargetDeclTest, RecursiveTemplate) {
+  Flags.push_back("-std=c++20"); // the test case uses concepts
+
+  Code = R"cpp(
+        template <typename T>
+        concept Leaf = false;
+
+        template <typename Tree>
+        struct descend_left {
+          using type = typename descend_left<typename Tree::left>::[[type]];
+        };
+
+        template <Leaf Tree>
+        struct descend_left<Tree> {
+          using type = typename Tree::value;
+        };
+  )cpp";
+  EXPECT_DECLS("DependentNameTypeLoc",
+               {"using type = typename descend_left<typename Tree::left>::type",
+                Rel::Alias | Rel::Underlying});
+}
+
 TEST_F(TargetDeclTest, ObjC) {
   Flags = {"-xobjective-c"};
   Code = R"cpp(
     @interface Foo {}
     -(void)bar;
     @end
     void test(Foo *f) {
       [f [[bar]] ];