[clangd] Implement textDocument/implementation (Xref layer)

[usaxena95]

Summary

Implements textdocument/implementation (https://microsoft.github.io/language-server-protocol/specification#textDocument_implementation)

There is no clear semantic in LSP, but VSCode has some documentation about the behaviour: "For an interface, this shows all the implementors of that interface and for abstract methods, this shows all concrete implementations of that method."

This currently shows all concrete methods that overrides a virtual function.

[usaxena95]

Addressed comments.

[thakis]

The test seems to crash everywhere: http://45.33.8.238/linux/33205/step_9.txt http://45.33.8.238/win/28127/step_9.txt

Please revert, then investigate.

Also, it looks (at least on phab) like it wasn't reviewed (?)

[usaxena95]

This was reviewed in https://reviews.llvm.org/D91626
Somehow phabricator attached the commit to this old patch.
I tried to address the failures. Are you seeing failures at the HEAD ?

[usaxena95]

I will revert this commit and investigate. Sorry for the trouble.

clang-tools-extra/clangd/XRefs.h

 /// Returns highlights for all usages of a symbol at \p Pos.
 std::vector<DocumentHighlight> findDocumentHighlights(ParsedAST &AST,
                                                       Position Pos);
 
 struct ReferencesResult {
   std::vector<Location> References;
   bool HasMore = false;
 };
+
+/// Returns implementations of the virtual function at a specified \p Pos.
+std::vector<LocatedSymbol> findImplementations(ParsedAST &AST, Position Pos,
+                                               const SymbolIndex *Index);
+
 /// Returns references of the symbol at a specified \p Pos.
 /// \p Limit limits the number of results returned (0 means no limit).
 ReferencesResult findReferences(ParsedAST &AST, Position Pos, uint32_t Limit,
                                 const SymbolIndex *Index = nullptr);
 
 /// Get info about symbols at \p Pos.
 std::vector<SymbolDetails> getSymbolInfo(ParsedAST &AST, Position Pos);
 

clang-tools-extra/clangd/XRefs.cpp

std::vector<DocumentHighlight> findDocumentHighlights(ParsedAST &AST,
 
   unsigned Offset =
       AST.getSourceManager().getDecomposedSpellingLoc(*CurLoc).second;
   SelectionTree::createEach(AST.getASTContext(), AST.getTokens(), Offset,
                             Offset, TryTree);
   return Result;
 }
 
+std::vector<LocatedSymbol> findImplementations(ParsedAST &AST, Position Pos,
+                                               const SymbolIndex *Index) {
+  std::vector<LocatedSymbol> Results;
+  // We rely on index to find the implementations in subclasses.
+  if (!Index)
+    return Results;
+  const SourceManager &SM = AST.getSourceManager();
+  auto MainFilePath =
+      getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);
+  if (!MainFilePath) {
+    elog("Failed to get a path for the main file, so no implementations.");
+    return Results;
+  }
+  auto CurLoc = sourceLocationInMainFile(SM, Pos);
+
+  DeclRelationSet Relations =
+      DeclRelation::TemplatePattern | DeclRelation::Alias;
+  RelationsRequest Req;
+  Req.Predicate = RelationKind::OverriddenBy;
+  for (const NamedDecl *ND : getDeclAtPosition(AST, *CurLoc, Relations))
+    if (const CXXMethodDecl *CXXMD = llvm::dyn_cast<CXXMethodDecl>(ND))
+      if (CXXMD->isVirtual())
+        Req.Subjects.insert(getSymbolID(ND));
+
+  if (Req.Subjects.empty())
+    return Results;
+  Index->relations(Req, [&](const SymbolID &Subject, const Symbol &Object) {
+    if (auto DeclLoc =
+            indexToLSPLocation(Object.CanonicalDeclaration, *MainFilePath)) {
+      LocatedSymbol Loc;
+      Loc.Name = Object.Name.str();
+      Loc.PreferredDeclaration = *DeclLoc;
+      auto DefLoc = indexToLSPLocation(Object.Definition, *MainFilePath);
+      Loc.Definition = DefLoc ? *DefLoc : *DeclLoc;
+      Results.push_back(Loc);
+    }
+  });
+  return Results;
+}
+
 ReferencesResult findReferences(ParsedAST &AST, Position Pos, uint32_t Limit,
                                 const SymbolIndex *Index) {
   if (!Limit)
     Limit = std::numeric_limits<uint32_t>::max();
   ReferencesResult Results;
   const SourceManager &SM = AST.getSourceManager();
   auto MainFilePath =
       getCanonicalPath(SM.getFileEntryForID(SM.getMainFileID()), SM);

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

 namespace {
 
 using ::testing::ElementsAre;
 using ::testing::Eq;
 using ::testing::IsEmpty;
 using ::testing::Matcher;
 using ::testing::UnorderedElementsAre;
 using ::testing::UnorderedElementsAreArray;
+using ::testing::UnorderedPointwise;
 
 MATCHER_P2(FileRange, File, Range, "") {
   return Location{URIForFile::canonicalize(File, testRoot()), Range} == arg;
 }
 MATCHER(DeclRange, "") {
   const LocatedSymbol &Sym = ::testing::get<0>(arg);
   const Range &Range = ::testing::get<1>(arg);
   return Sym.PreferredDeclaration.range == Range;
)cpp",
       };
       template <typename T>
       struct Derived : Base<T> {
         using Base<T>::w^aldo;
       };
     )cpp",
   };
 
-  for (const auto* Case : Tests) {
+  for (const auto *Case : Tests) {
     SCOPED_TRACE(Case);
     auto T = Annotations(Case);
     auto AST = TestTU::withCode(T.code()).build();
     EXPECT_THAT(locateSymbolAt(AST, T.point()),
-                ::testing::UnorderedPointwise(DeclRange(), T.ranges()));
+                UnorderedPointwise(DeclRange(), T.ranges()));
   }
 }
 
 TEST(LocateSymbol, RelPathsInCompileCommand) {
   // The source is in "/clangd-test/src".
   // We build in "/clangd-test/build".
 
   Annotations SourceAnnotations(R"cpp(
if (const auto *Tok = findNearbyIdentifier(*Word, AST.getTokens()))
                                        Tok->location(), Tok->endLocation()));
     if (T.ranges().empty())
       EXPECT_THAT(Nearby, Eq(llvm::None)) << Test;
     else
       EXPECT_EQ(Nearby, T.range()) << Test;
   }
 }
 
+TEST(FindImplementations, Inheritance) {
+  llvm::StringRef Test = R"cpp(
+    struct Base {
+      virtual void F$1^oo();
+    };
+    struct Child1 : Base {
+      void $1[[Fo$3^o]]() override;
+      virtual void B$2^ar();
+    };
+    struct Child2 : Child1 {
+      void $3[[Foo]]() override;
+      void $2[[Bar]]() override;
+    };
+    void FromReference() {
+      Base* B;
+      B->Fo$1^o();
+      &Base::Fo$1^o;
+      Child1 * C1;
+      C1->B$2^ar();
+      C1->Fo$3^o();
+    }    
+  )cpp";
+
+  Annotations Code(Test);
+  auto TU = TestTU::withCode(Code.code());
+  auto AST = TU.build();
+  for (const std::string &Label : {"1", "2", "3"}) {
+    for (const auto &Point : Code.points(Label)) {
+      EXPECT_THAT(findImplementations(AST, Point, TU.index().get()),
+                  UnorderedPointwise(DeclRange(), Code.ranges(Label)))
+          << Code.code() << " at " << Point << " for Label " << Label;
+    }
+  }
+}
+
+TEST(FindImplementations, CaptureDefintion) {
+  llvm::StringRef Test = R"cpp(
+    struct Base {
+      virtual void F^oo();
+    };
+    struct Child1 : Base {
+      void $Decl[[Foo]]() override;
+    };
+    struct Child2 : Base {
+      void $Child2[[Foo]]() override;
+    };
+    void Child1::$Def[[Foo]]() { /* Definition */ }
+  )cpp";
+  Annotations Code(Test);
+  auto TU = TestTU::withCode(Code.code());
+  auto AST = TU.build();
+  EXPECT_THAT(findImplementations(AST, Code.point(), TU.index().get()),
+              UnorderedElementsAre(
+                  Sym("Foo", Code.range("Decl"), Code.range("Def")),
+                  Sym("Foo", Code.range("Child2"), Code.range("Child2"))))
+      << Test;
+}
+
 TEST(FindReferences, WithinAST) {
   const char *Tests[] = {
       R"cpp(// Local variable
         int main() {
           int [[foo]];
           [[^foo]] = 2;
           int test1 = [[foo]];
         }