[clangd] Using index for GoToDefinition.

[hokein]

Summary

This patch adds index support for GoToDefinition -- when we don't get the
definition from local AST, we query our index (Static&Dynamic) index to
get it.

Since we currently collect top-level symbol in the index, it doesn't support all
cases (e.g. class members), we will extend the index to include more symbols in
the future.

Note: the newly-added test fails because of a DynamicIndex issue -- the symbol is
overwritten instead of merging.

[sammccall]

clangd/XRefs.cpp

250

the approach could some documentation - I find it hard to follow the code.

This function is probably too big by now and should be split up - but without understanding the goal I can't suggest how.

256

this seems suspicious to me - if we can't find an AST based location for the symbol, why would that mean giving up without consulting the index?

264

isn't the condition here something else - that there's at least one declaration that isn't a definition?

267

why are we ignoring the index if it's not a definition (and therefore preferring the AST one?)

289

Here we're returning exactly one candidate per symbol we identified as a candidate. There are other choices - why this one?

clangd/XRefs.h

26

nit: drop the second const here? we don't normally bother to mark by-value parameters as const (particularly not in declarations)

unittests/clangd/XRefsTests.cpp

128

We have a findDefinitionsHelper to avoid all this boilerplate.
Can you extend/overload it it to work with index?

[sammccall]

clangd/XRefs.cpp

250

Having read the code in more detail, I'd suggest a structure like:

• we identify the symbols being searched for
• for each, we have a definition slot and a non-definition slot
• initially we populate one of the slots with our preferred declaration from the AST (if location is available)
• then we query the index and overwrite either/both slots with returned info
• finally, we return populated slots for all symbols, definition first

(It's not clear how to order the returned symbols if there are multiple. When can this happen?)

[hokein]

Refine the patch and address all review comments.

[hokein]

I have updated the patch according to offline discussion -- for each symbol, we will return both decl and def locations (if available, def first) as they seems to be most sensible to users. We always prefer location from AST over Index when conflicts.

clangd/XRefs.cpp

289

Yeah, this was one definition location per symbol, made a change according to our discussion.

[sammccall]

Thanks for the changes! I still find the logic quite confusing. Happy to chat offline if useful.

clangd/XRefs.cpp

164

this is a nice abstraction - consider hiding the DeclarationAndMacrosFinder inside it!

249–250

So now you're early-out if there are macros.
This means if you have

void log(string s) { cout << s; }
#define LOG log
LOG("hello");

You'll offer only line 2 as an option, and not line 1.
I'm not sure that's bad, but it's non-obvious - I think it's the thing that the comment should call out.
e.g. "If the cursor is on a macro, go to the macro's definition without trying to resolve the code it expands to"
(The current comment just echoes the code)

249–250

I'm not sure this line adds anything unless you are more specific about what "typical" means, maybe just drop it.

(nit: go to, not goto)

256

because it's more up-to-date?

257

why do you not use GetDefinition(D) as the definition, in the case where it's not equal to D?

258

nit: canonical

260

first why?

269

nit: the body of this loop handles building the query and getting the AST locations, but they're interleaved in a confusing way - please separate them, or even make these two separate loops.

In the latter case you could put QueryRequest inside the if(Index) block, which would be easier to follow.

271

why are we skipping the AST location if we can't generate a USR?

297

remove this log message or make it more useful :-)

309

(The double-nested lambda is somewhat hard to read, can this just be a top-level function? That's what's needed to share it, right?)

532–533

can you also use getSymbolAtPosition here?

unittests/clangd/XRefsTests.cpp

43–57

this is too complicated, please find a way to make it simpler.
Take a look in TestFS.h for the filesystem stuff.

44

why allow BaseName to be chosen?

45

why do you need to pass in the FS? The FS shouldn't need to be the same between the index and AST.

53

why do this conditionally?

64

can we reuse FileIndex instead of reimplementing it?

145

combine these into buildIndex? Having multiple ASTs floating around in the test seems confusing...

[hokein]

Address review comments:

• clarify the flow of go to definition.
• simplify the test code.
• some function move-out stuff.

[hokein]

Thanks for the useful comments! I refined the patch, and it becomes a bit larger (including some moving stuff).

clangd/XRefs.cpp

164

Inlining DeclarationAndMacrosFinder implementation inside this function would hurt the code readability, I'd leave it as it is. Now all client sides are using this function instead of DeclarationAndMacrosFinder.

249–250

This is a non-functional change.

For the above example, only line 2 will be offered. This is expected behavior IMO -- when we go to definition on a macro, users would expect the macro definition.

257

Done. Added a comment.

260

because this is go to definition, so it is sensible to return the definition as the first result, right?

309

Moved it to XRef.h, and also replace the one in findsymbols.

532–533

Yeah, I just missed this.

unittests/clangd/XRefsTests.cpp

44

The same reason (allowed us to use the same FS between the index and AST).

45

I intended to use one FS for index and AST, because we'd like to test the AST case which includes the index header file, but it turns out this is not needed and add complexity of the testcode, removed it.

53

It is unnecessary if no header code is provided. And -include option would affect the test somehow, if we do it unconditionally, it breaks one of the existing test cases (no location was found). I haven't digged into the reason...

cpp
int [[i]];
#define ADDRESSOF(X) &X;
int *j = ADDRESSOF(^i);

64

Shared the implementation from FileIndex.

[sammccall]

A few more nits (and some ideas for further restructuring the merge logic).
Otherwise LG, let's land this!

clangd/XRefs.cpp

249–250

Ah, so these cases can't both happen (we even have an assert elsewhere).

Still, we can treat them as independent, and it seems simpler: you can remove the if statement, the comment for the if statement, and the early return.

255

up-to-update -> up-to-date

260

Again, I don't think "definition" in LSP is being used in its technical c++ sense.
No issue with the behavior here, but I think the comment should be "we think that's what the user wants most often" or something - it's good to know the reasoning in case we want to change the behavior in the future.

268

OK, as discussed offline the bit that remains confusing is why this isn't a map.
The reason is that some symbols don't have USRs and therefore no symbol IDs.

In practice we don't really expect multiple symbol results at all, so what about one of:

• map<Optional<SymbolID>, CandidateLocations>
• map<SymbolID, CandidateLocations> and use SymbolID("") as a sentinel

I slightly prefer the latter because it minimizes the invasiveness of handling this rare/unimportant case.

309

This is pretty weird in terms of layering I think :-(
The function is pretty trivial, but depends on a bunch of random stuff.
Can we move it back (and live with the duplication) until we come up with a good home?

clangd/index/FileIndex.h

26

nit: prefer to remove \brief in favor of formatting the comment so the summary gets extracted.

26

This isn't the main interface of the file.
Move to the bottom, and note that this is exposed to assist in unit tests?

[hokein]

Address review comments.

[hokein]

Thanks for the review!

clangd/XRefs.cpp

309

Reverted it, made it local in this file and added a FIXME.

clangd/ClangdServer.cpp

void ClangdServer::dumpAST(PathRef File,
   };
 
   WorkScheduler.runWithAST("DumpAST", File, Bind(Action, std::move(Callback)));
 }
 
 void ClangdServer::findDefinitions(PathRef File, Position Pos,
                                    Callback<std::vector<Location>> CB) {
   auto FS = FSProvider.getFileSystem();
-  auto Action = [Pos, FS](Callback<std::vector<Location>> CB,
+  auto Action = [Pos, FS, this](Callback<std::vector<Location>> CB,
                                 llvm::Expected<InputsAndAST> InpAST) {
     if (!InpAST)
       return CB(InpAST.takeError());
-    CB(clangd::findDefinitions(InpAST->AST, Pos));
+    CB(clangd::findDefinitions(InpAST->AST, Pos, this->FileIdx.get()));
   };
 
   WorkScheduler.runWithAST("Definitions", File, Bind(Action, std::move(CB)));
 }
 
 llvm::Optional<Path> ClangdServer::switchSourceHeader(PathRef Path) {
 
   StringRef SourceExtensions[] = {".cpp", ".c", ".cc", ".cxx",

clangd/XRefs.h

 // Features that traverse references between symbols.
 //
 //===---------------------------------------------------------------------===//
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_XREFS_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_XREFS_H
 
 #include "ClangdUnit.h"
 #include "Protocol.h"
+#include "index/Index.h"
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
 /// Get definition of symbol at a specified \p Pos.
-std::vector<Location> findDefinitions(ParsedAST &AST, Position Pos);
+std::vector<Location> findDefinitions(ParsedAST &AST, Position Pos,
+                                      const SymbolIndex *Index = nullptr);
 
 /// Returns highlights for all usages of a symbol at \p Pos.
 std::vector<DocumentHighlight> findDocumentHighlights(ParsedAST &AST,
                                                       Position Pos);
 
 /// Get the hover information when hovering at \p Pos.
 Hover getHover(ParsedAST &AST, Position Pos);
 
 } // namespace clangd
 } // namespace clang
 #endif

clangd/XRefs.cpp

 //===--- XRefs.cpp ----------------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===---------------------------------------------------------------------===//
 #include "XRefs.h"
 #include "AST.h"
 #include "Logger.h"
 #include "SourceCode.h"
 #include "URI.h"
 #include "clang/AST/DeclTemplate.h"
 #include "clang/Index/IndexDataConsumer.h"
 #include "clang/Index/IndexingAction.h"
+#include "clang/Index/USRGeneration.h"
 #include "llvm/Support/Path.h"
 namespace clang {
 namespace clangd {
 using namespace llvm;
 namespace {
 
 // Get the definition from a given declaration `D`.
 // Return nullptr if no definition is found, or the declaration type of `D` is
 // not supported.
 const Decl *GetDefinition(const Decl *D) {
   assert(D);
   if (const auto *TD = dyn_cast<TagDecl>(D))
     return TD->getDefinition();
   else if (const auto *VD = dyn_cast<VarDecl>(D))
     return VD->getDefinition();
   else if (const auto *FD = dyn_cast<FunctionDecl>(D))
     return FD->getDefinition();
   return nullptr;
 }
 
+// Convert a SymbolLocation to LSP's Location.
+// HintPath is used to resolve the path of URI.
+// FIXME: figure out a good home for it, and share the implementation with
+// FindSymbols.
+llvm::Optional<Location> ToLSPLocation(const SymbolLocation &Loc,
+                                       llvm::StringRef HintPath) {
+  if (!Loc)
+    return llvm::None;
+  auto Uri = URI::parse(Loc.FileURI);
+  if (!Uri) {
+    log("Could not parse URI: " + Loc.FileURI);
+    return llvm::None;
+  }
+  auto Path = URI::resolve(*Uri, HintPath);
+  if (!Path) {
+    log("Could not resolve URI: " + Loc.FileURI);
+    return llvm::None;
+  }
+  Location LSPLoc;
+  LSPLoc.uri = URIForFile(*Path);
+  LSPLoc.range.start.line = Loc.Start.Line;
+  LSPLoc.range.start.character = Loc.Start.Column;
+  LSPLoc.range.end.line = Loc.End.Line;
+  LSPLoc.range.end.character = Loc.End.Column;
+  return LSPLoc;
+}
+
 struct MacroDecl {
   StringRef Name;
   const MacroInfo *Info;
 };
 
 /// Finds declarations locations that a given source location refers to.
 class DeclarationAndMacrosFinder : public index::IndexDataConsumer {
   std::vector<const Decl *> Decls;
if (!Lexer::getRawToken(Mgr.getSpellingLoc(SearchedLocation), Result, Mgr,
           MacroInfos.push_back(MacroDecl{IdentifierInfo->getName(), MacroInf});
           assert(Decls.empty());
         }
       }
     }
   }
 };
 
+struct IdentifiedSymbol {
+  std::vector<const Decl *> Decls;
+  std::vector<MacroDecl> Macros;
+};
+
+IdentifiedSymbol getSymbolAtPosition(ParsedAST &AST, SourceLocation Pos) {
+  auto DeclMacrosFinder = DeclarationAndMacrosFinder(
+      llvm::errs(), Pos, AST.getASTContext(), AST.getPreprocessor());
+  index::IndexingOptions IndexOpts;
+  IndexOpts.SystemSymbolFilter =
+      index::IndexingOptions::SystemSymbolFilterKind::All;
+  IndexOpts.IndexFunctionLocals = true;
+  indexTopLevelDecls(AST.getASTContext(), AST.getTopLevelDecls(),
+                     DeclMacrosFinder, IndexOpts);
+
+  return {DeclMacrosFinder.takeDecls(), DeclMacrosFinder.takeMacroInfos()};
+}
+
+llvm::Optional<std::string>
+getAbsoluteFilePath(const FileEntry *F, const SourceManager &SourceMgr) {
+  SmallString<64> FilePath = F->tryGetRealPathName();
+  if (FilePath.empty())
+    FilePath = F->getName();
+  if (!llvm::sys::path::is_absolute(FilePath)) {
+    if (!SourceMgr.getFileManager().makeAbsolutePath(FilePath)) {
+      log("Could not turn relative path to absolute: " + FilePath);
+      return llvm::None;
+    }
+  }
+  return FilePath.str().str();
+}
+
 llvm::Optional<Location>
 makeLocation(ParsedAST &AST, const SourceRange &ValSourceRange) {
   const SourceManager &SourceMgr = AST.getASTContext().getSourceManager();
   const LangOptions &LangOpts = AST.getASTContext().getLangOpts();
   SourceLocation LocStart = ValSourceRange.getBegin();
 
   const FileEntry *F =
       SourceMgr.getFileEntryForID(SourceMgr.getFileID(LocStart));
   if (!F)
     return llvm::None;
   SourceLocation LocEnd = Lexer::getLocForEndOfToken(ValSourceRange.getEnd(), 0,
                                                      SourceMgr, LangOpts);
   Position Begin = sourceLocToPosition(SourceMgr, LocStart);
   Position End = sourceLocToPosition(SourceMgr, LocEnd);
   Range R = {Begin, End};
   Location L;
 
-  SmallString<64> FilePath = F->tryGetRealPathName();
-  if (FilePath.empty())
-    FilePath = F->getName();
-  if (!llvm::sys::path::is_absolute(FilePath)) {
-    if (!SourceMgr.getFileManager().makeAbsolutePath(FilePath)) {
-      log("Could not turn relative path to absolute: " + FilePath);
-      return llvm::None;
-    }
-  }
-
-  L.uri = URIForFile(FilePath.str());
+  auto FilePath = getAbsoluteFilePath(F, SourceMgr);
+  if (!FilePath) {
+    log("failed to get path!");
+  L.uri = URIForFile(*FilePath);
   L.range = R;
   return L;
 }
 
+// Get the symbol ID for a declaration, if possible.
+llvm::Optional<SymbolID> getSymbolID(const Decl *D) {
+  llvm::SmallString<128> USR;
+  if (index::generateUSRForDecl(D, USR)) {
+    return None;
+  }
+  return SymbolID(USR);
+}
+
 } // namespace
 
-std::vector<Location> findDefinitions(ParsedAST &AST, Position Pos) {
+std::vector<Location> findDefinitions(ParsedAST &AST, Position Pos,
+                                      const SymbolIndex *Index) {
   const SourceManager &SourceMgr = AST.getASTContext().getSourceManager();
   SourceLocation SourceLocationBeg =
       getBeginningOfIdentifier(AST, Pos, SourceMgr.getMainFileID());
 
   std::vector<Location> Result;
   // Handle goto definition for #include.
   for (auto &IncludeLoc : AST.getInclusionLocations()) {
     Range R = IncludeLoc.first;
     Position Pos = sourceLocToPosition(SourceMgr, SourceLocationBeg);
 
     if (R.contains(Pos))
       Result.push_back(Location{URIForFile{IncludeLoc.second}, {}});
   }
   if (!Result.empty())
     return Result;
 
-  DeclarationAndMacrosFinder DeclMacrosFinder(llvm::errs(), SourceLocationBeg,
-                                              AST.getASTContext(),
-                                              AST.getPreprocessor());
-  index::IndexingOptions IndexOpts;
-  IndexOpts.SystemSymbolFilter =
-      index::IndexingOptions::SystemSymbolFilterKind::All;
-  IndexOpts.IndexFunctionLocals = true;
-
-  indexTopLevelDecls(AST.getASTContext(), AST.getTopLevelDecls(),
-                     DeclMacrosFinder, IndexOpts);
+  // Identified symbols at a specific position.
+  auto Symbols = getSymbolAtPosition(AST, SourceLocationBeg);
 
-  std::vector<const Decl *> Decls = DeclMacrosFinder.takeDecls();
-  std::vector<MacroDecl> MacroInfos = DeclMacrosFinder.takeMacroInfos();
-
-  for (auto D : Decls) {
-    auto Loc = findNameLoc(D);
+  for (auto Item : Symbols.Macros) {
+    auto Loc = Item.Info->getDefinitionLoc();
     auto L = makeLocation(AST, SourceRange(Loc, Loc));
     if (L)
       Result.push_back(*L);
   }
 
-  for (auto Item : MacroInfos) {
-    auto Loc = Item.Info->getDefinitionLoc();
+  // Declaration and definition are different terms in C-family languages, and
+  // LSP only defines the "GoToDefinition" specification, so we try to perform
+  // the "most sensible" GoTo operation:
+  //
+  //  - We use the location from AST and index (if available) to provide the
+  //    final results. When there are duplicate results, we prefer AST over
+  //    index because AST is more up-to-date.
+  //
+  //  - For each symbol, we will return a location of the canonical declaration
+  //    (e.g. function declaration in header), and a location of definition if
+  //    they are available.
+  //
+  // So the work flow:
+  //
+  //   1. Identify the symbols being search for by traversing the AST.
+  //   2. Populate one of the locations with the AST location.
+  //   3. Use the AST information to query the index, and populate the index
+  //      location (if available).
+  //   4. Return all populated locations for all symbols, definition first (
+  //      which  we think is the users wants most often).
+  struct CandidateLocation {
+    llvm::Optional<Location> Def;
+    llvm::Optional<Location> Decl;
+  };
+  llvm::DenseMap<SymbolID, CandidateLocation> ResultCandidates;
+
+  // Emit all symbol locations (declaration or definition) from AST.
+  for (const auto *D : Symbols.Decls) {
+    // Fake key for symbols don't have USR (no SymbolID).
+    // Ideally, there should be a USR for each identified symbols. Symbols
+    // without USR are rare and unimportant cases, we use the a fake holder to
+    // minimize the invasiveness of these cases.
+    SymbolID Key("");
+    if (auto ID = getSymbolID(D))
+      Key = *ID;
+
+    auto &Candidate = ResultCandidates[Key];
+    auto Loc = findNameLoc(D);
     auto L = makeLocation(AST, SourceRange(Loc, Loc));
-    if (L)
-      Result.push_back(*L);
+    // The declaration in the identified symbols is a definition if possible
+    // otherwise it is declaration.
+    bool IsDef = GetDefinition(D) == D;
+    // Populate one of the slots with location for the AST.
+    if (!IsDef)
+      Candidate.Decl = L;
+    else
+      Candidate.Def = L;
+  }
+
+  if (Index) {
+    LookupRequest QueryRequest;
+    // Build request for index query, using SymbolID.
+    for (auto It : ResultCandidates)
+      QueryRequest.IDs.insert(It.first);
+    std::string HintPath;
+    const FileEntry *FE =
+        SourceMgr.getFileEntryForID(SourceMgr.getMainFileID());
+    if (auto Path = getAbsoluteFilePath(FE, SourceMgr))
+      HintPath = *Path;
+    // Query the index and populate the empty slot.
+    Index->lookup(
+        QueryRequest, [&HintPath, &ResultCandidates](const Symbol &Sym) {
+          auto It = ResultCandidates.find(Sym.ID);
+          assert(It != ResultCandidates.end());
+          auto &Value = It->second;
+
+          if (!Value.Def)
+            Value.Def = ToLSPLocation(Sym.Definition, HintPath);
+          if (!Value.Decl)
+            Value.Decl = ToLSPLocation(Sym.CanonicalDeclaration, HintPath);
+        });
+  }
+
+  // Populate the results, definition first.
+  for (auto It : ResultCandidates) {
+    const auto &Candidate = It.second;
+    if (Candidate.Def)
+      Result.push_back(*Candidate.Def);
+    if (Candidate.Decl &&
+        Candidate.Decl != Candidate.Def) // Decl and Def might be the same
+      Result.push_back(*Candidate.Decl);
   }
 
   return Result;
 }
 
 namespace {
 
 /// Finds document highlights that a given list of declarations refers to.

 } // namespace
 
 std::vector<DocumentHighlight> findDocumentHighlights(ParsedAST &AST,
                                                       Position Pos) {
   const SourceManager &SourceMgr = AST.getASTContext().getSourceManager();
   SourceLocation SourceLocationBeg =
       getBeginningOfIdentifier(AST, Pos, SourceMgr.getMainFileID());
 
-  DeclarationAndMacrosFinder DeclMacrosFinder(llvm::errs(), SourceLocationBeg,
-                                              AST.getASTContext(),
-                                              AST.getPreprocessor());
-  index::IndexingOptions IndexOpts;
-  IndexOpts.SystemSymbolFilter =
-      index::IndexingOptions::SystemSymbolFilterKind::All;
-  IndexOpts.IndexFunctionLocals = true;
-
-  // Macro occurences are not currently handled.
-  indexTopLevelDecls(AST.getASTContext(), AST.getTopLevelDecls(),
-                     DeclMacrosFinder, IndexOpts);
-
-  std::vector<const Decl *> SelectedDecls = DeclMacrosFinder.takeDecls();
+  auto Symbols = getSymbolAtPosition(AST, SourceLocationBeg);
+  std::vector<const Decl *> SelectedDecls = Symbols.Decls;
 
   DocumentHighlightsFinder DocHighlightsFinder(
       llvm::errs(), AST.getASTContext(), AST.getPreprocessor(), SelectedDecls);
 
+  index::IndexingOptions IndexOpts;
+  IndexOpts.SystemSymbolFilter =
+      index::IndexingOptions::SystemSymbolFilterKind::All;
+  IndexOpts.IndexFunctionLocals = true;
   indexTopLevelDecls(AST.getASTContext(), AST.getTopLevelDecls(),
                      DocHighlightsFinder, IndexOpts);
 
   return DocHighlightsFinder.takeHighlights();
 }
 
 static PrintingPolicy PrintingPolicyForDecls(PrintingPolicy Base) {
   PrintingPolicy Policy(Base);
static Hover getHoverContents(StringRef MacroName) {
 
   H.contents.value = "#define ";
   H.contents.value += MacroName;
 
   return H;
 }
 
 Hover getHover(ParsedAST &AST, Position Pos) {
   const SourceManager &SourceMgr = AST.getASTContext().getSourceManager();
   SourceLocation SourceLocationBeg =
       getBeginningOfIdentifier(AST, Pos, SourceMgr.getMainFileID());
-  DeclarationAndMacrosFinder DeclMacrosFinder(llvm::errs(), SourceLocationBeg,
-                                              AST.getASTContext(),
-                                              AST.getPreprocessor());
-
-  index::IndexingOptions IndexOpts;
-  IndexOpts.SystemSymbolFilter =
-      index::IndexingOptions::SystemSymbolFilterKind::All;
-  IndexOpts.IndexFunctionLocals = true;
+  // Identified symbols at a specific position.
+  auto Symbols = getSymbolAtPosition(AST, SourceLocationBeg);
 
-  indexTopLevelDecls(AST.getASTContext(), AST.getTopLevelDecls(),
-                     DeclMacrosFinder, IndexOpts);
+  if (!Symbols.Macros.empty())
+    return getHoverContents(Symbols.Macros[0].Name);
 
-  std::vector<MacroDecl> Macros = DeclMacrosFinder.takeMacroInfos();
-  if (!Macros.empty())
-    return getHoverContents(Macros[0].Name);
-
-  std::vector<const Decl *> Decls = DeclMacrosFinder.takeDecls();
-  if (!Decls.empty())
-    return getHoverContents(Decls[0]);
+  if (!Symbols.Decls.empty())
+    return getHoverContents(Symbols.Decls[0]);
 
   return Hover();
 }
 
 } // namespace clangd
 } // namespace clang

clangd/index/FileIndex.h

 
 #include "../ClangdUnit.h"
 #include "Index.h"
 #include "MemIndex.h"
 
 namespace clang {
 namespace clangd {
 
 /// \brief A container of Symbols from several source files. It can be updated
 /// at source-file granularity, replacing all symbols from one file with a new
 /// set.
 ///
 /// This implements a snapshot semantics for symbols in a file. Each update to a
 /// file will create a new snapshot for all symbols in the file. Snapshots are
 /// managed with shared pointers that are shared between this class and the
 /// users. For each file, this class only stores a pointer pointing to the
 /// newest snapshot, and an outdated snapshot is deleted by the last owner of
public:
   void lookup(const LookupRequest &Req,
               llvm::function_ref<void(const Symbol &)> Callback) const override;
 
 private:
   FileSymbols FSymbols;
   MemIndex Index;
 };
 
+/// Retrieves namespace and class level symbols in \p AST.
+/// Exposed to assist in unit tests.
+SymbolSlab indexAST(ParsedAST *AST);
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H

clangd/index/FileIndex.cpp

 //===--- FileIndex.cpp - Indexes for files. ------------------------ C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "FileIndex.h"
 #include "SymbolCollector.h"
 #include "clang/Index/IndexingAction.h"
 
 namespace clang {
 namespace clangd {
-namespace {
 
-/// Retrieves namespace and class level symbols in \p Decls.
-std::unique_ptr<SymbolSlab> indexAST(ASTContext &Ctx,
-                                     std::shared_ptr<Preprocessor> PP,
-                                     llvm::ArrayRef<const Decl *> Decls) {
+SymbolSlab indexAST(ParsedAST *AST) {
+  assert(AST && "AST must not be nullptr!");
   SymbolCollector::Options CollectorOpts;
   // FIXME(ioeric): we might also want to collect include headers. We would need
   // to make sure all includes are canonicalized (with CanonicalIncludes), which
   // is not trivial given the current way of collecting symbols: we only have
   // AST at this point, but we also need preprocessor callbacks (e.g.
   // CommentHandler for IWYU pragma) to canonicalize includes.
   CollectorOpts.CollectIncludePath = false;
   CollectorOpts.CountReferences = false;
 
   SymbolCollector Collector(std::move(CollectorOpts));
-  Collector.setPreprocessor(std::move(PP));
+  Collector.setPreprocessor(AST->getPreprocessorPtr());
   index::IndexingOptions IndexOpts;
   // We only need declarations, because we don't count references.
   IndexOpts.SystemSymbolFilter =
       index::IndexingOptions::SystemSymbolFilterKind::DeclarationsOnly;
   IndexOpts.IndexFunctionLocals = false;
 
-  index::indexTopLevelDecls(Ctx, Decls, Collector, IndexOpts);
-  auto Symbols = llvm::make_unique<SymbolSlab>();
-  *Symbols = Collector.takeSymbols();
-  return Symbols;
+  index::indexTopLevelDecls(AST->getASTContext(), AST->getTopLevelDecls(),
+                            Collector, IndexOpts);
+  return Collector.takeSymbols();
 }
 
-} // namespace
-
 void FileSymbols::update(PathRef Path, std::unique_ptr<SymbolSlab> Slab) {
   std::lock_guard<std::mutex> Lock(Mutex);
   if (!Slab)
     FileToSlabs.erase(Path);
   else
     FileToSlabs[Path] = std::move(Slab);
 }
 
std::shared_ptr<std::vector<const Symbol *>> FileSymbols::allSymbols() {
   // pointers.
   return {std::move(Snap), Pointers};
 }
 
 void FileIndex::update(PathRef Path, ParsedAST *AST) {
   if (!AST) {
     FSymbols.update(Path, nullptr);
   } else {
-    auto Slab = indexAST(AST->getASTContext(), AST->getPreprocessorPtr(),
-                         AST->getTopLevelDecls());
+    auto Slab = llvm::make_unique<SymbolSlab>();
+    *Slab = indexAST(AST);
     FSymbols.update(Path, std::move(Slab));
   }
   auto Symbols = FSymbols.allSymbols();
   Index.build(std::move(Symbols));
 }
 
 bool FileIndex::fuzzyFind(
     const FuzzyFindRequest &Req,

unittests/clangd/XRefsTests.cpp

 //===-- XRefsTests.cpp  ---------------------------*- C++ -*--------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 #include "Annotations.h"
 #include "ClangdUnit.h"
 #include "Compiler.h"
 #include "Matchers.h"
 #include "SyncAPI.h"
 #include "TestFS.h"
 #include "XRefs.h"
+#include "gmock/gmock.h"
+#include "index/FileIndex.h"
+#include "index/SymbolCollector.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Frontend/PCHContainerOperations.h"
 #include "clang/Frontend/Utils.h"
+#include "clang/Index/IndexingAction.h"
 #include "llvm/Support/Path.h"
-#include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace clangd {
 using namespace llvm;
 
 namespace {
 using testing::ElementsAre;
 using testing::Field;
 using testing::IsEmpty;
 using testing::Matcher;
 using testing::UnorderedElementsAreArray;
 
 class IgnoreDiagnostics : public DiagnosticsConsumer {
   void onDiagnosticsReady(PathRef File,
                           std::vector<Diag> Diagnostics) override {}
 };
 
 // FIXME: this is duplicated with FileIndexTests. Share it.
-ParsedAST build(StringRef Code) {
-  auto CI = createInvocationFromCommandLine(
-      {"clang", "-xc++", testPath("Foo.cpp").c_str()});
-  auto Buf = MemoryBuffer::getMemBuffer(Code);
+ParsedAST build(StringRef MainCode, StringRef HeaderCode = "") {
+  auto HeaderPath = testPath("foo.h");
+  auto MainPath = testPath("foo.cpp");
+  llvm::IntrusiveRefCntPtr<vfs::InMemoryFileSystem> VFS(
+      new vfs::InMemoryFileSystem());
+  VFS->addFile(MainPath, 0, llvm::MemoryBuffer::getMemBuffer(MainCode));
+  VFS->addFile(HeaderPath, 0, llvm::MemoryBuffer::getMemBuffer(HeaderCode));
+  std::vector<const char *> Cmd = {"clang", "-xc++", MainPath.c_str()};
+  if (!HeaderCode.empty()) {
+    std::vector<const char *> args = {"-include", HeaderPath.c_str()};
+    Cmd.insert(Cmd.begin() + 1, args.begin(), args.end());
+  }
+  auto CI = createInvocationFromCommandLine(Cmd);
+
+  auto Buf = MemoryBuffer::getMemBuffer(MainCode);
   auto AST = ParsedAST::Build(std::move(CI), nullptr, std::move(Buf),
-                              std::make_shared<PCHContainerOperations>(),
-                              vfs::getRealFileSystem());
+                              std::make_shared<PCHContainerOperations>(), VFS);
   assert(AST.hasValue());
   return std::move(*AST);
 }
 
+std::unique_ptr<SymbolIndex> buildIndex(StringRef MainCode,
+                                        StringRef HeaderCode) {
+  auto AST = build(MainCode, HeaderCode);
+  return MemIndex::build(indexAST(&AST));
+}
+
 // Extracts ranges from an annotated example, and constructs a matcher for a
 // highlight set. Ranges should be named $read/$write as appropriate.
 Matcher<const std::vector<DocumentHighlight> &>
 HighlightsFrom(const Annotations &Test) {
   std::vector<DocumentHighlight> Expected;
   auto Add = [&](const Range &R, DocumentHighlightKind K) {
     Expected.emplace_back();
     Expected.back().range = R;
for (const char *Test : Tests) {
     auto AST = build(T.code());
     EXPECT_THAT(findDocumentHighlights(AST, T.point()), HighlightsFrom(T))
         << Test;
   }
 }
 
 MATCHER_P(RangeIs, R, "") { return arg.range == R; }
 
+TEST(GoToDefinition, WithIndex) {
+  Annotations SymbolHeader(R"cpp(
+        class $forward[[Forward]];
+        class $foo[[Foo]] {};
+
+        void $f1[[f1]]();
+
+        inline void $f2[[f2]]() {}
+      )cpp");
+  Annotations SymbolCpp(R"cpp(
+      class $forward[[forward]] {};
+      void  $f1[[f1]]() {}
+    )cpp");
+
+  auto Index = buildIndex(SymbolCpp.code(), SymbolHeader.code());
+  auto runFindDefinitionsWithIndex = [&Index](const Annotations &Main) {
+    auto AST = build(/*MainCode=*/Main.code(),
+                     /*HeaderCode=*/"");
+    return clangd::findDefinitions(AST, Main.point(), Index.get());
+  };
+
+  Annotations Test(R"cpp(// only declaration in AST.
+        void [[f1]]();
+        int main() {
+          ^f1();
+        }
+      )cpp");
+  EXPECT_THAT(runFindDefinitionsWithIndex(Test),
+              testing::ElementsAreArray(
+                  {RangeIs(SymbolCpp.range("f1")), RangeIs(Test.range())}));
+
+  Test = Annotations(R"cpp(// definition in AST.
+        void [[f1]]() {}
+        int main() {
+          ^f1();
+        }
+      )cpp");
+  EXPECT_THAT(runFindDefinitionsWithIndex(Test),
+              testing::ElementsAreArray(
+                  {RangeIs(Test.range()), RangeIs(SymbolHeader.range("f1"))}));
+
+  Test = Annotations(R"cpp(// forward declaration in AST.
+        class [[Foo]];
+        F^oo* create();
+      )cpp");
+  EXPECT_THAT(runFindDefinitionsWithIndex(Test),
+              testing::ElementsAreArray(
+                  {RangeIs(SymbolHeader.range("foo")), RangeIs(Test.range())}));
+
+  Test = Annotations(R"cpp(// defintion in AST.
+        class [[Forward]] {};
+        F^orward create();
+      )cpp");
+  EXPECT_THAT(runFindDefinitionsWithIndex(Test),
+              testing::ElementsAreArray({
+                  RangeIs(Test.range()), RangeIs(SymbolHeader.range("forward")),
+              }));
+}
+
 TEST(GoToDefinition, All) {
   const char *Tests[] = {
       R"cpp(// Local variable
         int main() {
           int [[bonjour]];
           ^bonjour = 2;
           int test1 = bonjour;
         }