Index: clang-tools-extra/trunk/clangd/ClangdServer.h =================================================================== --- clang-tools-extra/trunk/clangd/ClangdServer.h +++ clang-tools-extra/trunk/clangd/ClangdServer.h @@ -75,6 +75,9 @@ /// If true, ClangdServer builds a dynamic in-memory index for symbols in /// opened files and uses the index to augment code completion results. bool BuildDynamicSymbolIndex = false; + /// Use a heavier and faster in-memory index implementation. + /// FIXME: we should make this true if it isn't too slow to build!. + bool HeavyweightDynamicSymbolIndex = false; /// URI schemes to use when building the dynamic index. /// If empty, the default schemes in SymbolCollector will be used. Index: clang-tools-extra/trunk/clangd/ClangdServer.cpp =================================================================== --- clang-tools-extra/trunk/clangd/ClangdServer.cpp +++ clang-tools-extra/trunk/clangd/ClangdServer.cpp @@ -105,8 +105,10 @@ : CDB(CDB), DiagConsumer(DiagConsumer), FSProvider(FSProvider), ResourceDir(Opts.ResourceDir ? Opts.ResourceDir->str() : getStandardResourceDir()), - DynamicIdx(Opts.BuildDynamicSymbolIndex ? new FileIndex(Opts.URISchemes) - : nullptr), + DynamicIdx(Opts.BuildDynamicSymbolIndex + ? new FileIndex(Opts.URISchemes, + Opts.HeavyweightDynamicSymbolIndex) + : nullptr), PCHs(std::make_shared()), // Pass a callback into `WorkScheduler` to extract symbols from a newly // parsed file and rebuild the file index synchronously each time an AST Index: clang-tools-extra/trunk/clangd/index/Background.cpp =================================================================== --- clang-tools-extra/trunk/clangd/index/Background.cpp +++ clang-tools-extra/trunk/clangd/index/Background.cpp @@ -183,7 +183,7 @@ // FIXME: this should rebuild once-in-a-while, not after every file. // At that point we should use Dex, too. vlog("Rebuilding automatic index"); - reset(IndexedSymbols.buildMemIndex()); + reset(IndexedSymbols.buildIndex(IndexType::Light)); return Error::success(); } Index: clang-tools-extra/trunk/clangd/index/FileIndex.h =================================================================== --- clang-tools-extra/trunk/clangd/index/FileIndex.h +++ clang-tools-extra/trunk/clangd/index/FileIndex.h @@ -26,6 +26,14 @@ namespace clang { namespace clangd { +/// Select between in-memory index implementations, which have tradeoffs. +enum class IndexType { + // MemIndex is trivially cheap to build, but has poor query performance. + Light, + // Dex is relatively expensive to build and uses more memory, but is fast. + Heavy, +}; + /// 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. @@ -47,7 +55,8 @@ std::unique_ptr Refs); // The index keeps the symbols alive. - std::unique_ptr buildMemIndex(); + std::unique_ptr + buildIndex(IndexType, ArrayRef URISchemes = {}); private: mutable std::mutex Mutex; @@ -64,7 +73,7 @@ public: /// If URISchemes is empty, the default schemes in SymbolCollector will be /// used. - FileIndex(std::vector URISchemes = {}); + FileIndex(std::vector URISchemes = {}, bool UseDex = true); /// Update preamble symbols of file \p Path with all declarations in \p AST /// and macros in \p PP. @@ -76,6 +85,7 @@ void updateMain(PathRef Path, ParsedAST &AST); private: + bool UseDex; // FIXME: this should be always on. std::vector URISchemes; // Contains information from each file's preamble only. Index: clang-tools-extra/trunk/clangd/index/FileIndex.cpp =================================================================== --- clang-tools-extra/trunk/clangd/index/FileIndex.cpp +++ clang-tools-extra/trunk/clangd/index/FileIndex.cpp @@ -13,6 +13,7 @@ #include "SymbolCollector.h" #include "index/Index.h" #include "index/Merge.h" +#include "index/dex/Dex.h" #include "clang/Index/IndexingAction.h" #include "clang/Lex/MacroInfo.h" #include "clang/Lex/Preprocessor.h" @@ -98,7 +99,8 @@ FileToRefs[Path] = std::move(Refs); } -std::unique_ptr FileSymbols::buildMemIndex() { +std::unique_ptr +FileSymbols::buildIndex(IndexType Type, ArrayRef URISchemes) { std::vector> SymbolSlabs; std::vector> RefSlabs; { @@ -144,18 +146,27 @@ StorageSize += RefSlab->bytes(); // Index must keep the slabs and contiguous ranges alive. - return llvm::make_unique( - llvm::make_pointee_range(AllSymbols), std::move(AllRefs), - std::make_tuple(std::move(SymbolSlabs), std::move(RefSlabs), - std::move(RefsStorage)), - StorageSize); + switch (Type) { + case IndexType::Light: + return llvm::make_unique( + llvm::make_pointee_range(AllSymbols), std::move(AllRefs), + std::make_tuple(std::move(SymbolSlabs), std::move(RefSlabs), + std::move(RefsStorage)), + StorageSize); + case IndexType::Heavy: + return llvm::make_unique( + llvm::make_pointee_range(AllSymbols), std::move(AllRefs), + std::make_tuple(std::move(SymbolSlabs), std::move(RefSlabs), + std::move(RefsStorage)), + StorageSize, std::move(URISchemes)); + } } -FileIndex::FileIndex(std::vector URISchemes) - : MergedIndex(&MainFileIndex, &PreambleIndex), +FileIndex::FileIndex(std::vector URISchemes, bool UseDex) + : MergedIndex(&MainFileIndex, &PreambleIndex), UseDex(UseDex), URISchemes(std::move(URISchemes)), - PreambleIndex(PreambleSymbols.buildMemIndex()), - MainFileIndex(MainFileSymbols.buildMemIndex()) {} + PreambleIndex(llvm::make_unique()), + MainFileIndex(llvm::make_unique()) {} void FileIndex::updatePreamble(PathRef Path, ASTContext &AST, std::shared_ptr PP) { @@ -163,7 +174,8 @@ PreambleSymbols.update(Path, llvm::make_unique(std::move(Symbols)), llvm::make_unique()); - PreambleIndex.reset(PreambleSymbols.buildMemIndex()); + PreambleIndex.reset(PreambleSymbols.buildIndex( + UseDex ? IndexType::Heavy : IndexType::Light, URISchemes)); } void FileIndex::updateMain(PathRef Path, ParsedAST &AST) { @@ -171,7 +183,7 @@ MainFileSymbols.update( Path, llvm::make_unique(std::move(Contents.first)), llvm::make_unique(std::move(Contents.second))); - MainFileIndex.reset(MainFileSymbols.buildMemIndex()); + MainFileIndex.reset(MainFileSymbols.buildIndex(IndexType::Light, URISchemes)); } } // namespace clangd Index: clang-tools-extra/trunk/clangd/index/dex/Dex.h =================================================================== --- clang-tools-extra/trunk/clangd/index/dex/Dex.h +++ clang-tools-extra/trunk/clangd/index/dex/Dex.h @@ -52,8 +52,10 @@ SymbolCollector::Options Opts; URISchemes = Opts.URISchemes; } + llvm::DenseSet SeenIDs; for (auto &&Sym : Symbols) - this->Symbols.push_back(&Sym); + if (SeenIDs.insert(Sym.ID).second) + this->Symbols.push_back(&Sym); for (auto &&Ref : Refs) this->Refs.try_emplace(Ref.first, Ref.second); buildIndex(); Index: clang-tools-extra/trunk/clangd/tool/ClangdMain.cpp =================================================================== --- clang-tools-extra/trunk/clangd/tool/ClangdMain.cpp +++ clang-tools-extra/trunk/clangd/tool/ClangdMain.cpp @@ -29,11 +29,11 @@ using namespace clang; using namespace clang::clangd; -// FIXME: remove this option when Dex is stable enough. +// FIXME: remove this option when Dex is cheap enough. static llvm::cl::opt UseDex("use-dex-index", - llvm::cl::desc("Use experimental Dex static index."), - llvm::cl::init(true), llvm::cl::Hidden); + llvm::cl::desc("Use experimental Dex dynamic index."), + llvm::cl::init(false), llvm::cl::Hidden); static llvm::cl::opt CompileCommandsDir( "compile-commands-dir", @@ -286,6 +286,7 @@ if (!ResourceDir.empty()) Opts.ResourceDir = ResourceDir; Opts.BuildDynamicSymbolIndex = EnableIndex; + Opts.HeavyweightDynamicSymbolIndex = UseDex; std::unique_ptr StaticIdx; std::future AsyncIndexLoad; // Block exit while loading the index. if (EnableIndex && !IndexFile.empty()) { @@ -293,7 +294,7 @@ SwapIndex *Placeholder; StaticIdx.reset(Placeholder = new SwapIndex(llvm::make_unique())); AsyncIndexLoad = runAsync([Placeholder, &Opts] { - if (auto Idx = loadIndex(IndexFile, Opts.URISchemes, UseDex)) + if (auto Idx = loadIndex(IndexFile, Opts.URISchemes, /*UseDex=*/true)) Placeholder->reset(std::move(Idx)); }); if (RunSynchronously) Index: clang-tools-extra/trunk/unittests/clangd/DexTests.cpp =================================================================== --- clang-tools-extra/trunk/unittests/clangd/DexTests.cpp +++ clang-tools-extra/trunk/unittests/clangd/DexTests.cpp @@ -492,19 +492,13 @@ "other::A")); } -// FIXME(kbobyrev): This test is different for Dex and MemIndex: while -// MemIndex manages response deduplication, Dex simply returns all matched -// symbols which means there might be equivalent symbols in the response. -// Before drop-in replacement of MemIndex with Dex happens, FileIndex -// should handle deduplication instead. TEST(DexTest, DexDeduplicate) { std::vector Symbols = {symbol("1"), symbol("2"), symbol("3"), symbol("2") /* duplicate */}; FuzzyFindRequest Req; Req.Query = "2"; Dex I(Symbols, RefSlab(), URISchemes); - EXPECT_FALSE(Req.Limit); - EXPECT_THAT(match(I, Req), ElementsAre("2", "2")); + EXPECT_THAT(match(I, Req), ElementsAre("2")); } TEST(DexTest, DexLimitedNumMatches) { Index: clang-tools-extra/trunk/unittests/clangd/FileIndexTests.cpp =================================================================== --- clang-tools-extra/trunk/unittests/clangd/FileIndexTests.cpp +++ clang-tools-extra/trunk/unittests/clangd/FileIndexTests.cpp @@ -82,12 +82,12 @@ TEST(FileSymbolsTest, UpdateAndGet) { FileSymbols FS; - EXPECT_THAT(runFuzzyFind(*FS.buildMemIndex(), ""), IsEmpty()); + EXPECT_THAT(runFuzzyFind(*FS.buildIndex(IndexType::Light), ""), IsEmpty()); FS.update("f1", numSlab(1, 3), refSlab(SymbolID("1"), "f1.cc")); - EXPECT_THAT(runFuzzyFind(*FS.buildMemIndex(), ""), + EXPECT_THAT(runFuzzyFind(*FS.buildIndex(IndexType::Light), ""), UnorderedElementsAre(QName("1"), QName("2"), QName("3"))); - EXPECT_THAT(getRefs(*FS.buildMemIndex(), SymbolID("1")), + EXPECT_THAT(getRefs(*FS.buildIndex(IndexType::Light), SymbolID("1")), RefsAre({FileURI("f1.cc")})); } @@ -95,9 +95,10 @@ FileSymbols FS; FS.update("f1", numSlab(1, 3), nullptr); FS.update("f2", numSlab(3, 5), nullptr); - EXPECT_THAT(runFuzzyFind(*FS.buildMemIndex(), ""), - UnorderedElementsAre(QName("1"), QName("2"), QName("3"), - QName("4"), QName("5"))); + for (auto Type : {IndexType::Light, IndexType::Heavy}) + EXPECT_THAT(runFuzzyFind(*FS.buildIndex(Type), ""), + UnorderedElementsAre(QName("1"), QName("2"), QName("3"), + QName("4"), QName("5"))); } TEST(FileSymbolsTest, SnapshotAliveAfterRemove) { @@ -106,13 +107,13 @@ SymbolID ID("1"); FS.update("f1", numSlab(1, 3), refSlab(ID, "f1.cc")); - auto Symbols = FS.buildMemIndex(); + auto Symbols = FS.buildIndex(IndexType::Light); EXPECT_THAT(runFuzzyFind(*Symbols, ""), UnorderedElementsAre(QName("1"), QName("2"), QName("3"))); EXPECT_THAT(getRefs(*Symbols, ID), RefsAre({FileURI("f1.cc")})); FS.update("f1", nullptr, nullptr); - auto Empty = FS.buildMemIndex(); + auto Empty = FS.buildIndex(IndexType::Light); EXPECT_THAT(runFuzzyFind(*Empty, ""), IsEmpty()); EXPECT_THAT(getRefs(*Empty, ID), ElementsAre()); Index: clang-tools-extra/trunk/unittests/clangd/TestTU.cpp =================================================================== --- clang-tools-extra/trunk/unittests/clangd/TestTU.cpp +++ clang-tools-extra/trunk/unittests/clangd/TestTU.cpp @@ -50,7 +50,8 @@ std::unique_ptr TestTU::index() const { auto AST = build(); - auto Idx = llvm::make_unique(); + auto Idx = llvm::make_unique( + /*URISchemes=*/std::vector{}, /*UseDex=*/true); Idx->updatePreamble(Filename, AST.getASTContext(), AST.getPreprocessorPtr()); Idx->updateMain(Filename, AST); return std::move(Idx);