Index: clangd/ClangdServer.cpp =================================================================== --- clangd/ClangdServer.cpp +++ clangd/ClangdServer.cpp @@ -355,11 +355,11 @@ void ClangdServer::findDefinitions(PathRef File, Position Pos, Callback> CB) { auto FS = FSProvider.getFileSystem(); - auto Action = [Pos, FS](Callback> CB, - llvm::Expected InpAST) { + auto Action = [Pos, FS, this](Callback> CB, + llvm::Expected 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))); Index: clangd/XRefs.h =================================================================== --- clangd/XRefs.h +++ clangd/XRefs.h @@ -15,13 +15,15 @@ #include "ClangdUnit.h" #include "Protocol.h" +#include "index/Index.h" #include namespace clang { namespace clangd { /// Get definition of symbol at a specified \p Pos. -std::vector findDefinitions(ParsedAST &AST, Position Pos); +std::vector findDefinitions(ParsedAST &AST, Position Pos, + const SymbolIndex *Index = nullptr); /// Returns highlights for all usages of a symbol at \p Pos. std::vector findDocumentHighlights(ParsedAST &AST, Index: clangd/XRefs.cpp =================================================================== --- clangd/XRefs.cpp +++ clangd/XRefs.cpp @@ -14,6 +14,7 @@ #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 { @@ -34,6 +35,33 @@ 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 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; @@ -128,6 +156,38 @@ } }; +struct IdentifiedSymbol { + std::vector Decls; + std::vector 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 +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 makeLocation(ParsedAST &AST, const SourceRange &ValSourceRange) { const SourceManager &SourceMgr = AST.getASTContext().getSourceManager(); @@ -145,24 +205,29 @@ 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; - } + auto FilePath = getAbsoluteFilePath(F, SourceMgr); + if (!FilePath) { + log("failed to get path!"); + return llvm::None; } - - L.uri = URIForFile(FilePath.str()); + L.uri = URIForFile(*FilePath); L.range = R; return L; } +// Get the symbol ID for a declaration, if possible. +llvm::Optional getSymbolID(const Decl *D) { + llvm::SmallString<128> USR; + if (index::generateUSRForDecl(D, USR)) { + return None; + } + return SymbolID(USR); +} + } // namespace -std::vector findDefinitions(ParsedAST &AST, Position Pos) { +std::vector findDefinitions(ParsedAST &AST, Position Pos, + const SymbolIndex *Index) { const SourceManager &SourceMgr = AST.getASTContext().getSourceManager(); SourceLocation SourceLocationBeg = getBeginningOfIdentifier(AST, Pos, SourceMgr.getMainFileID()); @@ -179,32 +244,97 @@ 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; + // Identified symbols at a specific position. + auto Symbols = getSymbolAtPosition(AST, SourceLocationBeg); - indexTopLevelDecls(AST.getASTContext(), AST.getTopLevelDecls(), - DeclMacrosFinder, IndexOpts); - - std::vector Decls = DeclMacrosFinder.takeDecls(); - std::vector 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 Def; + llvm::Optional Decl; + }; + llvm::DenseMap 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; @@ -280,23 +410,16 @@ 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 SelectedDecls = DeclMacrosFinder.takeDecls(); + auto Symbols = getSymbolAtPosition(AST, SourceLocationBeg); + std::vector 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); @@ -409,25 +532,14 @@ const SourceManager &SourceMgr = AST.getASTContext().getSourceManager(); SourceLocation SourceLocationBeg = getBeginningOfIdentifier(AST, Pos, SourceMgr.getMainFileID()); - DeclarationAndMacrosFinder DeclMacrosFinder(llvm::errs(), SourceLocationBeg, - AST.getASTContext(), - AST.getPreprocessor()); + // Identified symbols at a specific position. + auto Symbols = getSymbolAtPosition(AST, SourceLocationBeg); - index::IndexingOptions IndexOpts; - IndexOpts.SystemSymbolFilter = - index::IndexingOptions::SystemSymbolFilterKind::All; - IndexOpts.IndexFunctionLocals = true; - - indexTopLevelDecls(AST.getASTContext(), AST.getTopLevelDecls(), - DeclMacrosFinder, IndexOpts); + if (!Symbols.Macros.empty()) + return getHoverContents(Symbols.Macros[0].Name); - std::vector Macros = DeclMacrosFinder.takeMacroInfos(); - if (!Macros.empty()) - return getHoverContents(Macros[0].Name); - - std::vector Decls = DeclMacrosFinder.takeDecls(); - if (!Decls.empty()) - return getHoverContents(Decls[0]); + if (!Symbols.Decls.empty()) + return getHoverContents(Symbols.Decls[0]); return Hover(); } Index: clangd/index/FileIndex.h =================================================================== --- clangd/index/FileIndex.h +++ clangd/index/FileIndex.h @@ -71,6 +71,10 @@ 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 Index: clangd/index/FileIndex.cpp =================================================================== --- clangd/index/FileIndex.cpp +++ clangd/index/FileIndex.cpp @@ -13,12 +13,9 @@ namespace clang { namespace clangd { -namespace { -/// Retrieves namespace and class level symbols in \p Decls. -std::unique_ptr indexAST(ASTContext &Ctx, - std::shared_ptr PP, - llvm::ArrayRef 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 @@ -29,21 +26,18 @@ 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(); - *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 Slab) { std::lock_guard Lock(Mutex); if (!Slab) @@ -79,8 +73,8 @@ if (!AST) { FSymbols.update(Path, nullptr); } else { - auto Slab = indexAST(AST->getASTContext(), AST->getPreprocessorPtr(), - AST->getTopLevelDecls()); + auto Slab = llvm::make_unique(); + *Slab = indexAST(AST); FSymbols.update(Path, std::move(Slab)); } auto Symbols = FSymbols.allSymbols(); Index: unittests/clangd/XRefsTests.cpp =================================================================== --- unittests/clangd/XRefsTests.cpp +++ unittests/clangd/XRefsTests.cpp @@ -13,11 +13,14 @@ #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 { @@ -37,17 +40,33 @@ }; // 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( + new vfs::InMemoryFileSystem()); + VFS->addFile(MainPath, 0, llvm::MemoryBuffer::getMemBuffer(MainCode)); + VFS->addFile(HeaderPath, 0, llvm::MemoryBuffer::getMemBuffer(HeaderCode)); + std::vector Cmd = {"clang", "-xc++", MainPath.c_str()}; + if (!HeaderCode.empty()) { + std::vector 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(), - vfs::getRealFileSystem()); + std::make_shared(), VFS); assert(AST.hasValue()); return std::move(*AST); } +std::unique_ptr 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 &> @@ -106,6 +125,65 @@ 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