[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

115–116

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

253

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)

298

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"

321

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)

321

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)

513

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

321

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

std::string S = N.getNodeKind().asStringRef();
     llvm::raw_string_ostream OS(S);
     OS << ": ";
     N.print(OS, PrintingPolicy(LangOptions()));
   }
   std::replace(S.begin(), S.end(), '\n', ' ');
   return S;
 }
 
+// Given a dependent type and a member name, heuristically resolve the
+// name to one or more declarations.
+// The current heuristic is simply to look up the name in the primary
+// template. This is a heuristic because the template could potentially
+// have specializations that declare different members.
+// Multiple declarations could be returned if the name is overloaded
+// (e.g. an overloaded method in the primary template).
+// This heuristic will give the desired answer in many cases, e.g.
+// for a call to vector<T>::size().
+std::vector<const NamedDecl *>
+getMembersReferencedViaDependentName(const Type *T, const DeclarationName &Name,
+                                     bool IsNonstaticMember) {
+  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();
+  return RD->lookupDependentName(Name, [=](const NamedDecl *D) {
+    return IsNonstaticMember ? D->isCXXInstanceMember()
+                             : !D->isCXXInstanceMember();
+  });
+}
+
 // TargetFinder locates the entities that an AST node refers to.
 //
 // Typically this is (possibly) one declaration and (possibly) one type, but
 // may be more:
 //  - for ambiguous nodes like OverloadExpr
 //  - if we want to include e.g. both typedefs and the underlying type
 //
 // This is organized as a set of mutually recursive helpers for particular node

 //      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
+//  - UnresolvedUsingValueDecl
+//  - UnresolvedUsingTypenameDecl
 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()) {
+          // FIXME: Handle smart pointer types by looking up operator->
+          // in the primary template.
+          if (!BaseType || !BaseType->isPointerType()) {
+            return;
+          }
+          BaseType = BaseType->getAs<PointerType>()
+                         ->getPointeeType()
+                         .getTypePtrOrNull();
+        }
+        for (const NamedDecl *D :
+             getMembersReferencedViaDependentName(BaseType, E->getMember(),
+                                                  /*IsNonstaticMember=*/true)) {
+          Outer.add(D, Flags);
+        }
+      }
+      void VisitDependentScopeDeclRefExpr(const DependentScopeDeclRefExpr *E) {
+        for (const NamedDecl *D : getMembersReferencedViaDependentName(
+                 E->getQualifier()->getAsType(), E->getDeclName(),
+                 /*IsNonstaticMember=*/false)) {
+          Outer.add(D, Flags);
+        }
+      }
       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);
       }
     };
     Visitor(*this, Flags).Visit(S);
   }
 
   void add(QualType T, RelSet Flags) {
     if (T.isNull())
       return;
     debug(T, Flags);
     struct Visitor : public TypeVisitor<Visitor> {
       TargetFinder &Outer;
       RelSet Flags;
       Visitor(TargetFinder &Outer, RelSet Flags) : Outer(Outer), Flags(Flags) {}
 
       void VisitTagType(const TagType *TT) {
         Outer.add(TT->getAsTagDecl(), Flags);
       }
       void VisitDecltypeType(const DecltypeType *DTT) {
         Outer.add(DTT->getUnderlyingType(), Flags | Rel::Underlying);
       }
       void VisitDeducedType(const DeducedType *DT) {
         // FIXME: In practice this doesn't work: the AutoType you find inside
         // TypeLoc never has a deduced type. https://llvm.org/PR42914
         Outer.add(DT->getDeducedType(), Flags | Rel::Underlying);
       }
       void VisitTypedefType(const TypedefType *TT) {
         Outer.add(TT->getDecl(), Flags);
       }
       void
       VisitTemplateSpecializationType(const TemplateSpecializationType *TST) {
         // Have to handle these case-by-case.
 
         // templated type aliases: there's no specialized/instantiated using
         // decl to point to. So try to find a decl for the underlying type
         // (after substitution), and failing that point to the (templated) using
         // decl.
         if (TST->isTypeAlias()) {

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 dependent 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 dependent method via this->
+        template <typename T>
+        struct S {
+          void [[foo]]() {
+            this->fo^o();
+          }
+        };
+      )cpp",
+
+      R"cpp(// Heuristic resolution of dependent static method
+        template <typename T>
+        struct S {
+          static void [[bar]]() {}
+        };
+
+        template <typename T>
+        void foo() {
+          S<T>::ba^r();
+        }
+      )cpp",
+
+      R"cpp(// FIXME: Heuristic resolution of dependent method
+            // invoked via smart pointer
+        template <typename> struct S { void foo(); };
+        template <typename T> struct unique_ptr {
+          T* operator->();
+        };
+        template <typename T>
+        void test(unique_ptr<S<T>>& V) {
+          V->fo^o();
+        }
       )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]](float);
+    };
+
+    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;