[clangd] Merge results from static/dynamic index.

[sammccall]

Summary

We now hide the static/dynamic split from the code completion, behind a
new implementation of the SymbolIndex interface. This will reduce the
complexity of the sema/index merging that needs to be done by
CodeComplete, at a fairly small cost in flexibility.

[hokein]

clangd/index/Merge.cpp

30

Maybe add another FIXME, saying filer out symbols in static index, but are removed in dynamic index?

35

IIUC, Dyn is a local variable, which holds all the underlying data of Symbol, the Symbol returned in the callback of fuzzyFind would be invalid after the fuzzyFind(..) function call is finished.

Our previous assumption is that Symbol is valid as long as the SymbolIndex exists?

76

Don't we need CompletionDetail?

[sammccall]

Fixed bug where we wrote into the underlying index's symbols.
Extended testcase.
Added documentation around contracts.

[sammccall]

clangd/index/Merge.cpp

30

Done (function-level comment, because it's not a localized fix)

35

Our previous assumption is that Symbol is valid as long as the SymbolIndex exists?

No, it's only valid for the callback. Valid for the life of the index would make life hard for remote indexes.
Added documentation to SymbolIndex.

76

Sure. I was assuming it wasn't optional (should be present and match if USR matches), but i'm not 100% sure.

76

This was a bug. It'd be caught by marking Symbol::Detail const. Added a TODO.

[hokein]

looks good.

clangd/index/Merge.cpp

35

I see, that makes sense.

clangd/CMakeLists.txt

add_clang_library(clangDaemon
   Protocol.cpp
   ProtocolHandlers.cpp
   SourceCode.cpp
   Trace.cpp
   XRefs.cpp
   index/FileIndex.cpp
   index/Index.cpp
   index/MemIndex.cpp
+  index/Merge.cpp
   index/SymbolCollector.cpp
   index/SymbolYAML.cpp
 
   LINK_LIBS
   clangAST
   clangASTMatchers
   clangBasic
   clangFormat

clangd/ClangdServer.h

private:
 
   std::future<Context>
   scheduleCancelRebuild(Context Ctx, std::shared_ptr<CppFile> Resources);
 
   GlobalCompilationDatabase &CDB;
   DiagnosticsConsumer &DiagConsumer;
   FileSystemProvider &FSProvider;
   DraftStore DraftMgr;
-  /// If set, this manages index for symbols in opened files.
+  // The index used to look up symbols. This could be:
+  //   - null (all index functionality is optional)
+  //   - the dynamic index owned by ClangdServer (FileIdx)
+  //   - the static index passed to the constructor
+  //   - a merged view of a static and dynamic index (MergedIndex)
+  SymbolIndex *Index;
+  // If present, an up-to-date of symbols in open files. Read via Index.
   std::unique_ptr<FileIndex> FileIdx;
-  /// If set, this provides static index for project-wide global symbols.
-  /// clangd global code completion result will come from the static index and
-  /// the `FileIdx` above.
-  /// No owned, the life time is managed by clangd embedders.
-  SymbolIndex *StaticIdx;
+  // If present, a merged view of FileIdx and an external index. Read via Index.
+  std::unique_ptr<SymbolIndex> MergedIndex;
   CppFileCollection Units;
   std::string ResourceDir;
   // If set, this represents the workspace path.
   llvm::Optional<std::string> RootPath;
   std::shared_ptr<PCHContainerOperations> PCHs;
   bool StorePreamblesInMemory;
   /// Used to serialize diagnostic callbacks.
   /// FIXME(ibiryukov): get rid of an extra map and put all version counters

clangd/ClangdServer.cpp

 //===--- ClangdServer.cpp - Main clangd server code --------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===-------------------------------------------------------------------===//
 
 #include "ClangdServer.h"
 #include "CodeComplete.h"
 #include "SourceCode.h"
 #include "XRefs.h"
+#include "index/Merge.h"
 #include "clang/Format/Format.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "clang/Tooling/Refactoring/RefactoringResultConsumer.h"
 #include "clang/Tooling/Refactoring/Rename/RenamingAction.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/Support/Errc.h"
ClangdServer::ClangdServer(GlobalCompilationDatabase &CDB,
                            DiagnosticsConsumer &DiagConsumer,
                            FileSystemProvider &FSProvider,
                            unsigned AsyncThreadsCount,
                            bool StorePreamblesInMemory,
                            bool BuildDynamicSymbolIndex, SymbolIndex *StaticIdx,
                            llvm::Optional<StringRef> ResourceDir)
     : CDB(CDB), DiagConsumer(DiagConsumer), FSProvider(FSProvider),
       FileIdx(BuildDynamicSymbolIndex ? new FileIndex() : nullptr),
-      StaticIdx(StaticIdx),
       // Pass a callback into `Units` to extract symbols from a newly parsed
       // file and rebuild the file index synchronously each time an AST is
       // parsed.
       // FIXME(ioeric): this can be slow and we may be able to index on less
       // critical paths.
       Units(FileIdx
                 ? [this](const Context &Ctx, PathRef Path,
                          ParsedAST *AST) { FileIdx->update(Ctx, Path, AST); }
                 : ASTParsedCallback()),
       ResourceDir(ResourceDir ? ResourceDir->str() : getStandardResourceDir()),
       PCHs(std::make_shared<PCHContainerOperations>()),
       StorePreamblesInMemory(StorePreamblesInMemory),
-      WorkScheduler(AsyncThreadsCount) {}
+      WorkScheduler(AsyncThreadsCount) {
+  if (FileIdx && StaticIdx) {
+    MergedIndex = mergeIndex(FileIdx.get(), StaticIdx);
+    Index = MergedIndex.get();
+  } else if (FileIdx)
+    Index = FileIdx.get();
+  else if (StaticIdx)
+    Index = StaticIdx;
+  else
+    Index = nullptr;
+}
 
 void ClangdServer::setRootPath(PathRef RootPath) {
   std::string NewRootPath = llvm::sys::path::convert_to_slash(
       RootPath, llvm::sys::path::Style::posix);
   if (llvm::sys::fs::is_directory(NewRootPath))
     this->RootPath = NewRootPath;
 }
 
void ClangdServer::codeComplete(
   // Remember the current Preamble and use it when async task starts executing.
   // At the point when async task starts executing, we may have a different
   // Preamble in Resources. However, we assume the Preamble that we obtain here
   // is reusable in completion more often.
   std::shared_ptr<const PreambleData> Preamble =
       Resources->getPossiblyStalePreamble();
   // Copy completion options for passing them to async task handler.
   auto CodeCompleteOpts = Opts;
-  if (FileIdx)
-    CodeCompleteOpts.Index = FileIdx.get();
-  if (StaticIdx)
-    CodeCompleteOpts.StaticIndex = StaticIdx;
+  if (!CodeCompleteOpts.Index) // Respect overridden index.
+    CodeCompleteOpts.Index = Index;
 
   // Copy File, as it is a PathRef that will go out of scope before Task is
   // executed.
   Path FileStr = File;
   // Copy PCHs to avoid accessing this->PCHs concurrently
   std::shared_ptr<PCHContainerOperations> PCHs = this->PCHs;
   // A task that will be run asynchronously.
   auto Task =

clangd/CodeComplete.h

struct CodeCompleteOptions {
   size_t Limit = 0;
 
   // Populated internally by clangd, do not set.
   /// If `Index` is set, it is used to augment the code completion
   /// results.
   /// FIXME(ioeric): we might want a better way to pass the index around inside
   /// clangd.
   const SymbolIndex *Index = nullptr;
-
-  // Populated internally by clangd, do not set.
-  /// Static index for project-wide global symbols.
-  const SymbolIndex *StaticIndex = nullptr;
 };
 
 /// Get code completions at a specified \p Pos in \p FileName.
 CompletionList codeComplete(const Context &Ctx, PathRef FileName,
                             const tooling::CompileCommand &Command,
                             PrecompiledPreamble const *Preamble,
                             StringRef Contents, Position Pos,
                             IntrusiveRefCntPtr<vfs::FileSystem> VFS,

clangd/CodeComplete.cpp

CompletionList codeComplete(const Context &Ctx, PathRef FileName,
   auto Consumer =
       llvm::make_unique<CompletionItemsCollector>(Opts, Results, CompletedName);
   invokeCodeComplete(Ctx, std::move(Consumer), Opts.getClangCompleteOpts(),
                      FileName, Command, Preamble, Contents, Pos, std::move(VFS),
                      std::move(PCHs));
 
   // Got scope specifier (ns::f^) for code completion from sema, try to query
   // global symbols from indexes.
-  if (CompletedName.SSInfo) {
-    // FIXME: figure out a good algorithm to merge symbols from different
-    // sources (dynamic index, static index, AST symbols from clang's completion
-    // engine).
-    if (Opts.Index)
-      completeWithIndex(Ctx, *Opts.Index, Contents, *CompletedName.SSInfo,
-                        CompletedName.Filter, &Results, /*DebuggingLabel=*/"D");
-    if (Opts.StaticIndex)
-      completeWithIndex(Ctx, *Opts.StaticIndex, Contents, *CompletedName.SSInfo,
-                        CompletedName.Filter, &Results, /*DebuggingLabel=*/"S");
-  }
+  // FIXME: merge with Sema results, and respect limits.
+  if (CompletedName.SSInfo && Opts.Index)
+                      CompletedName.Filter, &Results, /*DebuggingLabel=*/"I");
   return Results;
 }
 
 SignatureHelp signatureHelp(const Context &Ctx, PathRef FileName,
                             const tooling::CompileCommand &Command,
                             PrecompiledPreamble const *Preamble,
                             StringRef Contents, Position Pos,
                             IntrusiveRefCntPtr<vfs::FileSystem> VFS,

clangd/index/Index.h

 namespace clang {
 namespace clangd {
 
 // The class presents a C++ symbol, e.g. class, function.
 //
 // WARNING: Symbols do not own much of their underlying data - typically strings
 // are owned by a SymbolSlab. They should be treated as non-owning references.
 // Copies are shallow.
-// When adding new unowned data fields to Symbol, remember to update
-// SymbolSlab::Builder in Index.cpp to copy them to the slab's storage.
+// When adding new unowned data fields to Symbol, remember to update:
+//   - SymbolSlab::Builder in Index.cpp, to copy them to the slab's storage.
+//   - mergeSymbol in Merge.cpp, to properly combine two Symbols.
 struct Symbol {
   // The ID of the symbol.
   SymbolID ID;
   // The symbol information, like symbol kind.
   index::SymbolInfo SymInfo;
   // The unqualified name of the symbol, e.g. "bar" (for "n1::n2::bar").
   llvm::StringRef Name;
   // The scope (e.g. namespace) of the symbol, e.g. "n1::n2" (for
struct Details {
     // Documentation including comment for the symbol declaration.
     llvm::StringRef Documentation;
     // This is what goes into the LSP detail field in a completion item. For
     // example, the result type of a function.
     llvm::StringRef CompletionDetail;
   };
 
   // Optional details of the symbol.
-  Details *Detail = nullptr;
+  Details *Detail = nullptr; // FIXME: should be const
 
   // FIXME: add definition location of the symbol.
   // FIXME: add all occurrences support.
   // FIXME: add extra fields for index scoring signals.
 };
 
 // An immutable symbol container that stores a set of symbols.
 // The container will maintain the lifetime of the symbols.
struct FuzzyFindRequest {
   /// \brief If this is non-empty, symbols must be in at least one of the scopes
   /// (e.g. namespaces) excluding nested scopes. For example, if a scope "xyz"
   /// is provided, the matched symbols must be defined in scope "xyz" but not
   /// "xyz::abc".
   ///
   /// A scope must be fully qualified without leading or trailing "::" e.g.
   /// "n1::n2". "" is interpreted as the global namespace, and "::" is invalid.
   std::vector<std::string> Scopes;
-  /// \brief The maxinum number of candidates to return.
+  /// \brief The number of top candidates to return. The index may choose to
+  /// return more than this, e.g. if it doesn't know which candidates are best.
   size_t MaxCandidateCount = UINT_MAX;
 };
 
 /// \brief Interface for symbol indexes that can be used for searching or
 /// matching symbols among a set of symbols based on names or unique IDs.
 class SymbolIndex {
 public:
   virtual ~SymbolIndex() = default;
 
   /// \brief Matches symbols in the index fuzzily and applies \p Callback on
   /// each matched symbol before returning.
+  /// If returned Symbols are used outside Callback, they must be deep-copied!
   ///
   /// Returns true if the result list is complete, false if it was truncated due
   /// to MaxCandidateCount
   virtual bool
   fuzzyFind(const Context &Ctx, const FuzzyFindRequest &Req,
             llvm::function_ref<void(const Symbol &)> Callback) const = 0;
 
   // FIXME: add interfaces for more index use cases:
   //  - Symbol getSymbolInfo(SymbolID);
   //  - getAllOccurrences(SymbolID);
 };
 
 } // namespace clangd
 } // namespace clang
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H

clangd/index/Merge.h

+//===--- Merge.h ------------------------------------------------*- C++-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===---------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_MERGE_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_MERGE_H
+#include "Index.h"
+namespace clang {
+namespace clangd {
+
+// Merge symbols L and R, preferring data from L in case of conflict.
+// The two symbols must have the same ID.
+// Returned symbol may contain data owned by either source.
+Symbol mergeSymbol(const Symbol &L, const Symbol &R, Symbol::Details *Scratch);
+
+// mergedIndex returns a composite index based on two provided Indexes:
+//  - the Dynamic index covers few files, but is relatively up-to-date.
+//  - the Static index covers a bigger set of files, but is relatively stale.
+// The returned index attempts to combine results, and avoid duplicates.
+std::unique_ptr<SymbolIndex> mergeIndex(const SymbolIndex *Dynamic,
+                                        const SymbolIndex *Static);
+
+} // namespace clangd
+} // namespace clang
+#endif

clangd/index/Merge.cpp

+//===--- Merge.h ------------------------------------------------*- C++-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===---------------------------------------------------------------------===//
+#include "Merge.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/raw_ostream.h"
+namespace clang {
+namespace clangd {
+namespace {
+using namespace llvm;
+
+class MergedIndex : public SymbolIndex {
+ public:
+   MergedIndex(const SymbolIndex *Dynamic, const SymbolIndex *Static)
+       : Dynamic(Dynamic), Static(Static) {}
+
+   // FIXME: Deleted symbols in dirty files are still returned (from Static).
+   //        To identify these eliminate these, we should:
+   //          - find the generating file from each Symbol which is Static-only
+   //          - ask Dynamic if it has that file (needs new SymbolIndex method)
+   //          - if so, drop the Symbol.
+   bool fuzzyFind(const Context &Ctx, const FuzzyFindRequest &Req,
+                  function_ref<void(const Symbol &)> Callback) const override {
+     // We can't step through both sources in parallel. So:
+     //  1) query all dynamic symbols, slurping results into a slab
+     //  2) query the static symbols, for each one:
+     //    a) if it's not in the dynamic slab, yield it directly
+     //    b) if it's in the dynamic slab, merge it and yield the result
+     //  3) now yield all the dynamic symbols we haven't processed.
+     bool More = false; // We'll be incomplete if either source was.
+     SymbolSlab::Builder DynB;
+     More |=
+         Dynamic->fuzzyFind(Ctx, Req, [&](const Symbol &S) { DynB.insert(S); });
+     SymbolSlab Dyn = std::move(DynB).build();
+
+     DenseSet<SymbolID> SeenDynamicSymbols;
+     Symbol::Details Scratch;
+     More |= Static->fuzzyFind(Ctx, Req, [&](const Symbol &S) {
+       auto DynS = Dyn.find(S.ID);
+       if (DynS == Dyn.end())
+         return Callback(S);
+       SeenDynamicSymbols.insert(S.ID);
+       Callback(mergeSymbol(*DynS, S, &Scratch));
+     });
+     for (const Symbol &S : Dyn)
+       if (!SeenDynamicSymbols.count(S.ID))
+         Callback(S);
+     return More;
+  }
+
+private:
+  const SymbolIndex *Dynamic, *Static;
+};
+}
+
+Symbol
+mergeSymbol(const Symbol &L, const Symbol &R, Symbol::Details *Scratch) {
+  assert(L.ID == R.ID);
+  Symbol S = L;
+  // For each optional field, fill it from R if missing in L.
+  // (It might be missing in R too, but that's a no-op).
+  if (S.CanonicalDeclaration.FilePath == "")
+    S.CanonicalDeclaration = R.CanonicalDeclaration;
+  if (S.CompletionLabel == "")
+    S.CompletionLabel = R.CompletionLabel;
+  if (S.CompletionFilterText == "")
+    S.CompletionFilterText = R.CompletionFilterText;
+  if (S.CompletionPlainInsertText == "")
+    S.CompletionPlainInsertText = R.CompletionPlainInsertText;
+  if (S.CompletionSnippetInsertText == "")
+    S.CompletionSnippetInsertText = R.CompletionSnippetInsertText;
+
+  if (L.Detail && R.Detail) {
+    // Copy into scratch space so we can merge.
+    *Scratch = *L.Detail;
+    if (Scratch->Documentation == "")
+      Scratch->Documentation = R.Detail->Documentation;
+    if (Scratch->CompletionDetail == "")
+      Scratch->CompletionDetail = R.Detail->CompletionDetail;
+    S.Detail = Scratch;
+  } else if (L.Detail)
+    S.Detail = L.Detail;
+  else if (R.Detail)
+    S.Detail = R.Detail;
+  return S;
+}
+
+std::unique_ptr<SymbolIndex> mergeIndex(const SymbolIndex *Dynamic,
+                                        const SymbolIndex *Static) {
+  return llvm::make_unique<MergedIndex>(Dynamic, Static);
+}
+} // namespace clangd
+} // namespace clang

unittests/clangd/CodeCompleteTests.cpp

 #include "CodeComplete.h"
 #include "Compiler.h"
 #include "Context.h"
 #include "Matchers.h"
 #include "Protocol.h"
 #include "SourceCode.h"
 #include "TestFS.h"
 #include "index/MemIndex.h"
+#include "index/Merge.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace clangd {
 // Let GMock print completion items and signature help.
 void PrintTo(const CompletionItem &I, std::ostream *O) {
   llvm::raw_os_ostream OS(*O);
)cpp",
                              Opts);
   EXPECT_THAT(Results.items, Has("Local"));
 }
 
 TEST(CompletionTest, StaticAndDynamicIndex) {
   clangd::CodeCompleteOptions Opts;
   auto StaticIdx =
       simpleIndexFromSymbols({{"ns::XYZ", index::SymbolKind::Class}});
-  Opts.StaticIndex = StaticIdx.get();
   auto DynamicIdx =
       simpleIndexFromSymbols({{"ns::foo", index::SymbolKind::Function}});
-  Opts.Index = DynamicIdx.get();
+  auto Merge = mergeIndex(DynamicIdx.get(), StaticIdx.get());
+  Opts.Index = Merge.get();
 
   auto Results = completions(R"cpp(
       void f() { ::ns::^ }
   )cpp",
                              Opts);
-  EXPECT_THAT(Results.items, Contains(Labeled("[S]XYZ")));
-  EXPECT_THAT(Results.items, Contains(Labeled("[D]foo")));
+  EXPECT_THAT(Results.items, Contains(Labeled("[I]XYZ")));
+  EXPECT_THAT(Results.items, Contains(Labeled("[I]foo")));
 }
 
 TEST(CompletionTest, SimpleIndexBased) {
   clangd::CodeCompleteOptions Opts;
   auto I = simpleIndexFromSymbols({{"ns::XYZ", index::SymbolKind::Class},
                                    {"nx::XYZ", index::SymbolKind::Class},
                                    {"ns::foo", index::SymbolKind::Function}});
   Opts.Index = I.get();

unittests/clangd/IndexTests.cpp

 //===-- IndexTests.cpp  -------------------------------*- C++ -*-----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "index/Index.h"
 #include "index/MemIndex.h"
+#include "index/Merge.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 using testing::UnorderedElementsAre;
 using testing::Pointee;
 
 namespace clang {
 namespace clangd {
TEST(MemIndexTest, IgnoreCases) {
   I.build(generateSymbols({"ns::ABC", "ns::abc"}));
   FuzzyFindRequest Req;
   Req.Query = "AB";
   Req.Scopes = {"ns"};
   auto Matches = match(I, Req);
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("ns::ABC", "ns::abc"));
 }
 
+TEST(MergeTest, MergeIndex) {
+  MemIndex I, J;
+  I.build(generateSymbols({"ns::A", "ns::B"}));
+  J.build(generateSymbols({"ns::B", "ns::C"}));
+  FuzzyFindRequest Req;
+  Req.Scopes = {"ns"};
+  EXPECT_THAT(match(*mergeIndex(&I, &J), Req),
+              UnorderedElementsAre("ns::A", "ns::B", "ns::C"));
+}
+
+TEST(MergeTest, Merge) {
+  Symbol L, R;
+  L.ID = R.ID = SymbolID("hello");
+  L.Name = R.Name = "Foo";                    // same in both
+  L.CanonicalDeclaration.FilePath = "left.h"; // differs
+  R.CanonicalDeclaration.FilePath = "right.h";
+  L.CompletionPlainInsertText = "f00";        // present in left only
+  R.CompletionSnippetInsertText = "f0{$1:0}"; // present in right only
+  Symbol::Details DetL, DetR;
+  DetL.CompletionDetail = "DetL";
+  DetR.CompletionDetail = "DetR";
+  DetR.Documentation = "--doc--";
+  L.Detail = &DetL;
+  R.Detail = &DetR;
+
+  Symbol::Details Scratch;
+  Symbol M = mergeSymbol(L, R, &Scratch);
+  EXPECT_EQ(M.Name, "Foo");
+  EXPECT_EQ(M.CanonicalDeclaration.FilePath, "left.h");
+  EXPECT_EQ(M.CompletionPlainInsertText, "f00");
+  EXPECT_EQ(M.CompletionSnippetInsertText, "f0{$1:0}");
+  ASSERT_TRUE(M.Detail);
+  EXPECT_EQ(M.Detail->CompletionDetail, "DetL");
+  EXPECT_EQ(M.Detail->Documentation, "--doc--");
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang