[clangd] Heuristically resolve dependent method calls

[nridge]

Summary

The heuristic is to look in the definition of the primary template,
which is what you want in the vast majority of cases.

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

[nridge]

Add github issue number

[nridge]

Fix typo

[sammccall]

Awesome, thanks, I'd been hoping to get around to this! LG with some naming/structure nits.
This doesn't handle references into smart pointers (details below), but feel free to do that in this patch, separately, or not at all.

clang-tools-extra/clangd/FindTarget.cpp

81–82

while here, I think UnresolvedUsingValueDecl and UnresolvedUsingTypenameDecl can be added here :-)

217

If I'm understanding the AST correctly, this drops the operator-> case, where the base is a smart-pointer.

e.g. void run(unique_ptr<Action<T>> X) { X->go(); }

There are potentially two reasons then that x->go is a *dependent* memberexpr:

• operator-> probably returns T*, but unique_ptr might be specialized (you don't handle this)
• we probably want the primary Action<T>::go, but Action might be specialized (you do handle this)

So it might be worth trying to get the pointee type (if the base type is a TemplateSpecializationType, look up operator-> in the primary template, and replace the base with its return type).
If you don't want to do this yet, we should leave a comment (like FIXME: handle unique_ptr<T> by looking up operator-> in the primary template)

255

In the long term, I'm not sure this comment will be as useful as one saying something like:
"Dependent name references like vector<T>::size() can't be definitively resolved, but the using the definition from the primary template is probably better than giving up"

278

can we make this function return the decls, and make the callers call add() in a loop?

That way this function could be reused for the operator-> lookup, and could be a standalone helper function outside this class. (Maybe eventually exposed in AST.h, as I can imagine it being useful in other places, but static in this file seems fine)

278

with multiple lookup results we could add all, discard all, or pick one arbitrarily.

I'm not sure what the best policy is, but it's worth pointing out in a comment what the cases are and what the choice is.

I think this should only affects overloads, where returning all seems reasonable (resolution would be way too much work).

Can you add a test?

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

470

nit: dependent method (just so it's easier to search for)

501

could you add a test for the operator-> case too, even if we don't handle it yet? (in which case with a FIXME)

Something like:

template <typename T> struct unique_ptr<T> { T* operator->(); };
template <typename T> struct S { void [[foo]](); }
template <typename T> void test(unique_ptr<S<T>>& V) { V->f^oo(); }

[nridge]

unique_ptr is harder to get to work than it might appear at first blush :)

Looking at the gcc 6 libstdc++ implementation as an example: the declared return type of operator-> is not T*, but unique_ptr<T>::pointer. The declaration of that is in turn:

typedef typename _Pointer::type pointer;

The definition of _Pointer is in turn:

// use SFINAE to determine whether _Del::pointer exists
class _Pointer
{
  template<typename _Up>
  static typename _Up::pointer __test(typename _Up::pointer*);

  template<typename _Up>
  static _Tp* __test(...);

  typedef typename remove_reference<_Dp>::type _Del;

public:
  typedef decltype(__test<_Del>(0)) type;
};

Writing heuristics that see through all that might be possible, and I'm happy to explore it, but definitely in a follow-up.

[nridge]

Address review comments

[nridge]

Fix a typo and address one remaining comment

[nridge]

clang-tools-extra/clangd/FindTarget.cpp

278

Note, the additions to LocateSymbol.Ambiguous provide test coverage for this.

[thakis]

Tests fail on Windows: http://45.33.8.238/win/3976/step_9.txt

Probably needs the usual -fno-delayed-template-parsing workaround, see other clangd tests.

[nridge]

In D71240#1782763, @thakis wrote:

Probably needs the usual -fno-delayed-template-parsing workaround, see other clangd tests.

Thanks for the suggestion! Fix at https://reviews.llvm.org/D71444

[nridge]

In D71240#1782828, @nridge wrote:

In D71240#1782763, @thakis wrote:

Probably needs the usual -fno-delayed-template-parsing workaround, see other clangd tests.

Thanks for the suggestion! Fix at https://reviews.llvm.org/D71444

Committed in https://reviews.llvm.org/rG4f732a3d49ac.

clang-tools-extra/clangd/FindTarget.cpp

 //      template<class X> using pvec = vector<x*>; pvec<int> x;
 //    There's no Decl `pvec<int>`, we must choose `pvec<X>` or `vector<int*>`
 //    and both are lossy. We must know upfront what the caller ultimately wants.
 //
 // FIXME: improve common dependent scope using name lookup in primary templates.
 // e.g. template<typename T> int foo() { return std::vector<T>().size(); }
 // formally size() is unresolved, but the primary template is a good guess.
 // This affects:
 //  - DependentTemplateSpecializationType,
-//  - DependentScopeMemberExpr
-//  - DependentScopeDeclRefExpr
 //  - DependentNameType
 struct TargetFinder {
   using RelSet = DeclRelationSet;
   using Rel = DeclRelation;
   llvm::SmallDenseMap<const Decl *, RelSet> Decls;
   RelSet Flags;
 
   static const Decl *getTemplatePattern(const Decl *D) {
     if (const CXXRecordDecl *CRD = dyn_cast<CXXRecordDecl>(D)) {
struct Visitor : public ConstStmtVisitor<Visitor> {
         for (const DesignatedInitExpr::Designator &D :
              llvm::reverse(DIE->designators()))
           if (D.isFieldDesignator()) {
             Outer.add(D.getField(), Flags);
             // We don't know which designator was intended, we assume the outer.
             break;
           }
       }
+      void
+      VisitCXXDependentScopeMemberExpr(const CXXDependentScopeMemberExpr *E) {
+        const Type *BaseType = E->getBaseType().getTypePtrOrNull();
+        if (E->isArrow()) {
+          if (!BaseType || !BaseType->isPointerType()) {
+            return;
+          }
+          BaseType = BaseType->getAs<PointerType>()
+                         ->getPointeeType()
+                         .getTypePtrOrNull();
+        }
+        addMembersReferencedViaDependentName(BaseType, E->getMember(),
+                                             /*IsNonstaticMember=*/true);
+      }
+      void VisitDependentScopeDeclRefExpr(const DependentScopeDeclRefExpr *E) {
+        addMembersReferencedViaDependentName(E->getQualifier()->getAsType(),
+                                             E->getDeclName(),
+                                             /*IsNonstaticMember=*/false);
+      }
       void VisitObjCIvarRefExpr(const ObjCIvarRefExpr *OIRE) {
         Outer.add(OIRE->getDecl(), Flags);
       }
       void VisitObjCMessageExpr(const ObjCMessageExpr *OME) {
         Outer.add(OME->getMethodDecl(), Flags);
       }
       void VisitObjCPropertyRefExpr(const ObjCPropertyRefExpr *OPRE) {
         if (OPRE->isExplicitProperty())
           Outer.add(OPRE->getExplicitProperty(), Flags);
         else {
           if (OPRE->isMessagingGetter())
             Outer.add(OPRE->getImplicitPropertyGetter(), Flags);
           if (OPRE->isMessagingSetter())
             Outer.add(OPRE->getImplicitPropertySetter(), Flags);
         }
       }
       void VisitObjCProtocolExpr(const ObjCProtocolExpr *OPE) {
         Outer.add(OPE->getProtocol(), Flags);
       }
+
+      void addMembersReferencedViaDependentName(const Type *T,
+                                                const DeclarationName &Name,
+                                                bool IsNonstaticMember) {
+        // This code was adapted in part from indexDependentReference() in
+        // IndexBody.cpp.
+        if (!T)
+          return;
+        if (auto *ICNT = T->getAs<InjectedClassNameType>()) {
+          T = ICNT->getInjectedSpecializationType().getTypePtrOrNull();
+        }
+        auto *TST = T->getAs<TemplateSpecializationType>();
+        if (!TST)
+          return;
+        const ClassTemplateDecl *TD = dyn_cast_or_null<ClassTemplateDecl>(
+            TST->getTemplateName().getAsTemplateDecl());
+        if (!TD)
+          return;
+        CXXRecordDecl *RD = TD->getTemplatedDecl();
+        if (!RD->hasDefinition())
+          return;
+        RD = RD->getDefinition();
+        std::vector<const NamedDecl *> Decls =
+            RD->lookupDependentName(Name, [=](const NamedDecl *D) {
+              return IsNonstaticMember ? D->isCXXInstanceMember()
+                                       : !D->isCXXInstanceMember();
+            });
+        for (const NamedDecl *D : Decls) {
+          Outer.add(D, Flags);
+        }
+      }
     };
     Visitor(*this, Flags).Visit(S);
   }
 
   void add(QualType T, RelSet Flags) {
     if (T.isNull())
       return;
     debug(T, Flags);

clang-tools-extra/clangd/XRefs.cpp

auto References = findRefs(
                             Pos, SM, AST.getLangOpts())),
                         Relations),
       AST);
 
   // FIXME: we may get multiple DocumentHighlights with the same location and
   // different kinds, deduplicate them.
   std::vector<DocumentHighlight> Result;
   for (const auto &Ref : References) {
-    if (auto Range = getTokenRange(AST.getSourceManager(),
-                                   AST.getLangOpts(), Ref.Loc)) {
+    if (auto Range =
+            getTokenRange(AST.getSourceManager(), AST.getLangOpts(), Ref.Loc)) {
       DocumentHighlight DH;
       DH.range = *Range;
       if (Ref.Role & index::SymbolRoleSet(index::SymbolRole::Write))
         DH.kind = DocumentHighlightKind::Write;
       else if (Ref.Role & index::SymbolRoleSet(index::SymbolRole::Read))
         DH.kind = DocumentHighlightKind::Read;
       else
         DH.kind = DocumentHighlightKind::Text;

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

const char *Tests[] = {
       )cpp",
 
       R"cpp(// Declaration of partial template specialization
         template <typename T>
         struct $decl[[Foo]] {};
 
         template <typename T>
         struct Fo^o<T*> {};
+      )cpp",
+
+      R"cpp(// Heuristic resolution of method
+        template <typename T>
+        struct S {
+          void [[bar]]() {}
+        };
+
+        template <typename T>
+        void foo(S<T> arg) {
+          arg.ba^r();
+        }
+      )cpp",
+
+      R"cpp(// Heuristic resolution of method via this->
+        template <typename T>
+        struct S {
+          void [[foo]]() {
+            this->fo^o();
+          }
+        };
+      )cpp",
+
+      R"cpp(// Heuristic resolution of static method
+        template <typename T>
+        struct S {
+          static void [[bar]]() {}
+        };
+
+        template <typename T>
+        void foo() {
+          S<T>::ba^r();
+        }
       )cpp"};
   for (const char *Test : Tests) {
     Annotations T(Test);
     llvm::Optional<Range> WantDecl;
     llvm::Optional<Range> WantDef;
     if (!T.ranges().empty())
       WantDecl = WantDef = T.range();
     if (!T.ranges("decl").empty())
       WantDecl = T.range("decl");
void call() {
       $4^g($5^f());
       g($6^str);
       Foo ab$7^c;
       Foo ab$8^cd("asdf");
       Foo foox = Fo$9^o("asdf");
       Foo abcde$10^("asdf");
       Foo foox2 = Foo$11^("asdf");
     }
+
+    template <typename T>
+    struct S {
+      void $NonstaticOverload1[[bar]](int);
+      void $NonstaticOverload2[[bar]](float);
+
+      static void $StaticOverload1[[baz]](int);
+      static void $StaticOverload2[[baz]](int);
+    };
+
+    template <typename T, typename U>
+    void dependent_call(S<T> s, U u) {
+      s.ba$12^r(u);
+      S<T>::ba$13^z(u);
+    }
   )cpp");
   auto AST = TestTU::withCode(T.code()).build();
   // Ordered assertions are deliberate: we expect a predictable order.
   EXPECT_THAT(locateSymbolAt(AST, T.point("1")), ElementsAre(Sym("str")));
   EXPECT_THAT(locateSymbolAt(AST, T.point("2")), ElementsAre(Sym("str")));
   EXPECT_THAT(locateSymbolAt(AST, T.point("3")), ElementsAre(Sym("f")));
   EXPECT_THAT(locateSymbolAt(AST, T.point("4")), ElementsAre(Sym("g")));
   EXPECT_THAT(locateSymbolAt(AST, T.point("5")), ElementsAre(Sym("f")));
   EXPECT_THAT(locateSymbolAt(AST, T.point("6")), ElementsAre(Sym("str")));
   // FIXME: Target the constructor as well.
   EXPECT_THAT(locateSymbolAt(AST, T.point("7")), ElementsAre(Sym("abc")));
   // FIXME: Target the constructor as well.
   EXPECT_THAT(locateSymbolAt(AST, T.point("8")), ElementsAre(Sym("abcd")));
   // FIXME: Target the constructor as well.
   EXPECT_THAT(locateSymbolAt(AST, T.point("9")), ElementsAre(Sym("Foo")));
   EXPECT_THAT(locateSymbolAt(AST, T.point("10")),
               ElementsAre(Sym("Foo", T.range("ConstructorLoc"))));
   EXPECT_THAT(locateSymbolAt(AST, T.point("11")),
               ElementsAre(Sym("Foo", T.range("ConstructorLoc"))));
+  // These assertions are unordered because the order comes from
+  // CXXRecordDecl::lookupDependentName() which doesn't appear to provide
+  // an order guarantee.
+  EXPECT_THAT(locateSymbolAt(AST, T.point("12")),
+              UnorderedElementsAre(Sym("bar", T.range("NonstaticOverload1")),
+                                   Sym("bar", T.range("NonstaticOverload2"))));
+  EXPECT_THAT(locateSymbolAt(AST, T.point("13")),
+              UnorderedElementsAre(Sym("baz", T.range("StaticOverload1")),
+                                   Sym("baz", T.range("StaticOverload2"))));
 }
 
 TEST(LocateSymbol, TemplateTypedefs) {
   auto T = Annotations(R"cpp(
     template <class T> struct function {};
     template <class T> using callback = function<T()>;
 
     c^allback<int> foo;