[clangd] Merge index-provided completions with those from Sema.

[sammccall]

Summary

• we match on USR, and do a field-by-field merge if both have results
• scoring is post-merge, with both sets of information available (for now, sema priority is used if available, static score for index results)
• limit is applied to the complete result set (previously index ignored limit)
• CompletionItem is only produces for the returned results
• If the user doesn't type a scope, we send the scopeless query to the index for global completion.

This needs tests for the new functionality, but I thought you could take a look
while I work on that. It passes the existing tests, and works in VSCode.

[ioeric]

Overall looks good! Some ideas about code structure inlined.

clangd/CodeComplete.cpp

327 ↗

(On Diff #130173)

Does the recorder still do fuzzy-matching?

339 ↗

(On Diff #130173)

It seems that CCContext can change during ProcessCodeCompleteResults. It's unclear what the implication is for codeCompletionString at the end.

434 ↗

(On Diff #130173)

Maybe dropped()?

679 ↗

(On Diff #130173)

The overall behavior looks good. And the comments really help understand the code! As chatted offline, we might want to break down this function, and a class that book-keeps all the states might be helpful.

734 ↗

(On Diff #130173)

I think we already only query namespace scopes now?

747 ↗

(On Diff #130173)

As discussed offline, we want to defer unqualified completion support (IIRC?) until we have enough information about visible scopes (i.e. after D42073).

782 ↗

(On Diff #130173)

It would be a bit more natural if the decision of building CCS is hidden in the candidate. Maybe pass in a callback for creating CCS from a sema result and let candidate decide whether to create CCS or not? This would also get rid of the constraint for build.

789 ↗

(On Diff #130173)

Would it make sense to move the score construction into build, by passing in necessary information in Candidate.second?

[sammccall]

Addressed review comments, except for "refactor into class" which is still todo.
Added explicit check of code completion context kind.
Added tests (mostly updating existing ones).

[sammccall]

Converted the big codeComplete function to a CodeCompleteFlow class

[ioeric]

LGTM

clangd/CodeComplete.cpp

743 ↗

(On Diff #130440)

InComplete can probably be output variable of queryIndex and addCandidate instead of a state?

[hokein]

looks good to me too, just a few nits.

clangd/CodeComplete.cpp

308 ↗

(On Diff #130440)

add return None to make compiler happier? I think it might trigger -Wreturn-type warning.

341 ↗

(On Diff #130440)

I'd suggesting rename the variable Sema to another name, since Sema is already a class name (although naming is hard).

845 ↗

(On Diff #130440)

consider using llvm::set_difference here?

[sammccall]

Oops, I forgot to submit comments with my last update.
I don't think there's anything surprising so I'll land this, but let me know if you want any changes!

clangd/CodeComplete.cpp

743 ↗

(On Diff #130440)

Certainly it can (it needs to be an out-param, because these functions already have primary return values). Just as these could all be free functions :-)

I tried it out - I find the out-params are a bit messy/hard to read, and they'd need to be added to mergeResults, queryIndex and addCandidate. It adds quite a lot of noise, and I'm not sure on balance emphasizing the flow of IsIncomplete is worth obscuring the flow of the results themselves. If you disagree, let me know (or just change it!)

339 ↗

(On Diff #130173)

This function is only ever called once, but this isn't documented anywhere :-\
Added an assert.

734 ↗

(On Diff #130173)

Nope, we never check the completion context kind, and I think I've seen cases where we end up completing when it's inappropriate.

Fixed this (see the new allowIndex() check) and removed the fixme.

747 ↗

(On Diff #130173)

Done - we now complete only symbols in the global scope.
I added two FIXMEs describing how we can progressively make this better over time. Do they match your understanding?

782 ↗

(On Diff #130173)

I agree, but trying this out I found it equally hard to read, and not as decoupled as I'd hope.
So as discussed offline, sticking with the ugly-and-direct approach :-)

[sammccall]

clangd/CodeComplete.cpp

308 ↗

(On Diff #130440)

added llvm_unreachable.

845 ↗

(On Diff #130440)

The value type is different: Symbol vs Symbol*

clang-tools-extra/trunk/clangd/CodeComplete.cpp

 #include "CodeComplete.h"
 #include "CodeCompletionStrings.h"
 #include "Compiler.h"
 #include "FuzzyMatch.h"
 #include "Logger.h"
 #include "index/Index.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/FrontendActions.h"
+#include "clang/Index/USRGeneration.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "clang/Sema/Sema.h"
 #include "llvm/Support/Format.h"
 #include <queue>
 
 namespace clang {
 namespace clangd {
 namespace {
for (const auto &Chunk : CCS) {
     default:
       Result += Chunk.Text;
       break;
     }
   }
   return Result;
 }
 
-/// A scored code completion result.
-/// It may be promoted to a CompletionItem if it's among the top-ranked results.
-///
-/// We score candidates by multiplying the symbolScore ("quality" of the result)
-/// with the filterScore (how well it matched the query).
-/// This is sensitive to the distribution of both component scores!
-struct CompletionCandidate {
-  CompletionCandidate(CodeCompletionResult &Result, float FilterScore)
-      : Result(&Result) {
-    Scores.symbolScore = score(Result);  // Higher is better.
-    Scores.filterScore = FilterScore;    // 0-1, higher is better.
-    Scores.finalScore = Scores.symbolScore * Scores.filterScore;
-  }
-
-  CodeCompletionResult *Result;
-  CompletionItemScores Scores;
+// Produces an integer that sorts in the same order as F.
+// That is: a < b <==> encodeFloat(a) < encodeFloat(b).
+uint32_t encodeFloat(float F) {
+  static_assert(std::numeric_limits<float>::is_iec559, "");
+  static_assert(sizeof(float) == sizeof(uint32_t), "");
+  constexpr uint32_t TopBit = ~(~uint32_t{0} >> 1);
 
-  // Comparison reflects rank: better candidates are smaller.
-  bool operator<(const CompletionCandidate &C) const {
-    if (Scores.finalScore != C.Scores.finalScore)
-      return Scores.finalScore > C.Scores.finalScore;
-    return *Result < *C.Result;
-  }
+  // Get the bits of the float. Endianness is the same as for integers.
+  uint32_t U;
+  memcpy(&U, &F, sizeof(float));
+  // IEEE 754 floats compare like sign-magnitude integers.
+  if (U & TopBit)    // Negative float.
+    return 0 - U;    // Map onto the low half of integers, order reversed.
+  return U + TopBit; // Positive floats map onto the high half of integers.
 
-  // Returns a string that sorts in the same order as operator<, for LSP.
-  // Conceptually, this is [-Score, Name]. We convert -Score to an integer, and
-  // hex-encode it for readability. Example: [0.5, "foo"] -> "41000000foo"
-  std::string sortText() const {
-    std::string S, NameStorage;
-    llvm::raw_string_ostream OS(S);
-    write_hex(OS, encodeFloat(-Scores.finalScore), llvm::HexPrintStyle::Lower,
-              /*Width=*/2 * sizeof(Scores.finalScore));
-    OS << Result->getOrderedName(NameStorage);
-    return OS.str();
-  }
+// Returns a string that sorts in the same order as (-Score, Name), for LSP.
+std::string sortText(float Score, llvm::StringRef Name) {
+  // We convert -Score to an integer, and hex-encode for readability.
+  // Example: [0.5, "foo"] -> "41000000foo"
+  std::string S;
+  write_hex(OS, encodeFloat(-Score), llvm::HexPrintStyle::Lower,
+            /*Width=*/2 * sizeof(Score));
+  OS << Name;
+  OS.flush();
+  return S;
 
-private:
-  static float score(const CodeCompletionResult &Result) {
+/// A code completion result, in clang-native form.
+/// It may be promoted to a CompletionItem if it's among the top-ranked results.
+struct CompletionCandidate {
+  llvm::StringRef Name; // Used for filtering and sorting.
+  // We may have a result from Sema, from the index, or both.
+  const CodeCompletionResult *SemaResult = nullptr;
+  const Symbol *IndexResult = nullptr;
+
+  // Computes the "symbol quality" score for this completion. Higher is better.
+  float score() const {
+    // For now we just use the Sema priority, mapping it onto a 0-1 interval.
+    if (!SemaResult) // FIXME(sammccall): better scoring for index results.
+      return 0.3;    // fixed mediocre score for index-only results.
+
     // Priority 80 is a really bad score.
-    float Score = 1 - std::min<float>(80, Result.Priority) / 80;
+    float Score = 1 - std::min<float>(80, SemaResult->Priority) / 80;
 
-    switch (static_cast<CXAvailabilityKind>(Result.Availability)) {
+    switch (static_cast<CXAvailabilityKind>(SemaResult->Availability)) {
     case CXAvailability_Available:
       // No penalty.
       break;
     case CXAvailability_Deprecated:
       Score *= 0.1f;
       break;
     case CXAvailability_NotAccessible:
     case CXAvailability_NotAvailable:
       Score = 0;
       break;
     }
     return Score;
   }
 
-  // Produces an integer that sorts in the same order as F.
-  // That is: a < b <==> encodeFloat(a) < encodeFloat(b).
-  static uint32_t encodeFloat(float F) {
-    static_assert(std::numeric_limits<float>::is_iec559, "");
-    static_assert(sizeof(float) == sizeof(uint32_t), "");
-    constexpr uint32_t TopBit = ~(~uint32_t{0} >> 1);
+  // Builds an LSP completion item.
+  CompletionItem build(const CompletionItemScores &Scores,
+                       const CodeCompleteOptions &Opts,
+                       CodeCompletionString *SemaCCS) const {
+    assert(bool(SemaResult) == bool(SemaCCS));
+    CompletionItem I;
+    if (SemaResult) {
+      I.kind = toCompletionItemKind(SemaResult->Kind, SemaResult->CursorKind);
+      getLabelAndInsertText(*SemaCCS, &I.label, &I.insertText,
+                            Opts.EnableSnippets);
+      I.filterText = getFilterText(*SemaCCS);
+      I.documentation = getDocumentation(*SemaCCS);
+      I.detail = getDetail(*SemaCCS);
+    }
+    if (IndexResult) {
+      if (I.kind == CompletionItemKind::Missing)
+        I.kind = toCompletionItemKind(IndexResult->SymInfo.Kind);
+      // FIXME: reintroduce a way to show the index source for debugging.
+      if (I.label.empty())
+        I.label = IndexResult->CompletionLabel;
+      if (I.filterText.empty())
+        I.filterText = IndexResult->Name;
 
-    // Get the bits of the float. Endianness is the same as for integers.
-    uint32_t U;
-    memcpy(&U, &F, sizeof(float));
-    // IEEE 754 floats compare like sign-magnitude integers.
-    if (U & TopBit)    // Negative float.
-      return 0 - U;    // Map onto the low half of integers, order reversed.
-    return U + TopBit; // Positive floats map onto the high half of integers.
+      // FIXME(ioeric): support inserting/replacing scope qualifiers.
+      if (I.insertText.empty())
+        I.insertText = Opts.EnableSnippets
+                           ? IndexResult->CompletionSnippetInsertText
+                           : IndexResult->CompletionPlainInsertText;
+
+      if (auto *D = IndexResult->Detail) {
+        if (I.documentation.empty())
+          I.documentation = D->Documentation;
+        if (I.detail.empty())
+          I.detail = D->CompletionDetail;
+      }
+    }
+    I.scoreInfo = Scores;
+    I.sortText = sortText(Scores.finalScore, Name);
+    I.insertTextFormat = Opts.EnableSnippets ? InsertTextFormat::Snippet
+                                             : InsertTextFormat::PlainText;
+    return I;
   }
 };
 
+// Determine the symbol ID for a Sema code completion result, if possible.
+llvm::Optional<SymbolID> getSymbolID(const CodeCompletionResult &R) {
+  switch (R.Kind) {
+  case CodeCompletionResult::RK_Declaration:
+  case CodeCompletionResult::RK_Pattern: {
+    llvm::SmallString<128> USR;
+    if (/*Ignore=*/clang::index::generateUSRForDecl(R.Declaration, USR))
+      return None;
+    return SymbolID(USR);
+  }
+  case CodeCompletionResult::RK_Macro:
+    // FIXME: Macros do have USRs, but the CCR doesn't contain enough info.
+  case CodeCompletionResult::RK_Keyword:
+    return None;
+  }
+  llvm_unreachable("unknown CodeCompletionResult kind");
+}
+
 /// \brief Information about the scope specifier in the qualified-id code
 /// completion (e.g. "ns::ab?").
 struct SpecifiedScope {
   /// The scope specifier as written. For example, for completion "ns::ab?", the
   /// written scope specifier is "ns".
   std::string Written;
   // If this scope specifier is recognized in Sema (e.g. as a namespace
   // context), this will be set to the fully qualfied name of the corresponding
   // context.
   std::string Resolved;
-};
 
-/// \brief Information from sema about (parital) symbol names to be completed.
-/// For example, for completion "ns::ab^", this stores the scope specifier
-/// "ns::" and the completion filter text "ab".
-struct NameToComplete {
-  // The partial identifier being completed, without qualifier.
-  std::string Filter;
-
-  /// This is set if the completion is for qualified IDs, e.g. "abc::x^".
-  llvm::Optional<SpecifiedScope> SSInfo;
+  llvm::StringRef forIndex() {
+    llvm::StringRef Chosen = Resolved.empty() ? Written : Resolved;
+    return Chosen.trim(':');
+  }
 };
 
-SpecifiedScope extraCompletionScope(Sema &S, const CXXScopeSpec &SS);
-
-class CompletionItemsCollector : public CodeCompleteConsumer {
-public:
-  CompletionItemsCollector(const CodeCompleteOptions &CodeCompleteOpts,
-                           CompletionList &Items, NameToComplete &CompletedName)
-      : CodeCompleteConsumer(CodeCompleteOpts.getClangCompleteOpts(),
+// The CompletionRecorder captures Sema code-complete output, including context.
+// It filters out ignored results (but doesn't apply fuzzy-filtering yet).
+// It doesn't do scoring or conversion to CompletionItem yet, as we want to
+// merge with index results first.
+struct CompletionRecorder : public CodeCompleteConsumer {
+  CompletionRecorder(const CodeCompleteOptions &Opts)
+      : CodeCompleteConsumer(Opts.getClangCompleteOpts(),
                              /*OutputIsBinary=*/false),
-        ClangdOpts(CodeCompleteOpts), Items(Items),
-        Allocator(std::make_shared<clang::GlobalCodeCompletionAllocator>()),
-        CCTUInfo(Allocator), CompletedName(CompletedName),
-        EnableSnippets(CodeCompleteOpts.EnableSnippets) {}
+        CCContext(CodeCompletionContext::CCC_Other), Opts(Opts),
+        CCAllocator(std::make_shared<GlobalCodeCompletionAllocator>()),
+        CCTUInfo(CCAllocator) {}
+  std::vector<CodeCompletionResult> Results;
+  CodeCompletionContext CCContext;
+  Sema *CCSema = nullptr; // Sema that created the results.
+  // FIXME: Sema is scary. Can we store ASTContext and Preprocessor, instead?
 
-  void ProcessCodeCompleteResults(Sema &S, CodeCompletionContext Context,
-                                  CodeCompletionResult *Results,
+  void ProcessCodeCompleteResults(class Sema &S, CodeCompletionContext Context,
+                                  CodeCompletionResult *InResults,
                                   unsigned NumResults) override final {
-    FuzzyMatcher Filter(S.getPreprocessor().getCodeCompletionFilter());
-    if (auto SS = Context.getCXXScopeSpecifier())
-      CompletedName.SSInfo = extraCompletionScope(S, **SS);
+    // Record the completion context.
+    assert(!CCSema && "ProcessCodeCompleteResults called multiple times!");
+    CCSema = &S;
+    CCContext = Context;
 
-    CompletedName.Filter = S.getPreprocessor().getCodeCompletionFilter();
-    std::priority_queue<CompletionCandidate> Candidates;
+    // Retain the results we might want.
     for (unsigned I = 0; I < NumResults; ++I) {
-      auto &Result = Results[I];
-      // We drop hidden items, as they cannot be found by the lookup after
-      // inserting the corresponding completion item and only produce noise and
-      // duplicates in the completion list. However, there is one exception. If
-      // Result has a Qualifier which is non-informative, we can refer to an
-      // item by adding that qualifier, so we don't filter out this item.
+      auto &Result = InResults[I];
+      // Drop hidden items which cannot be found by lookup after completion.
+      // Exception: some items can be named by using a qualifier.
       if (Result.Hidden && (!Result.Qualifier || Result.QualifierIsInformative))
         continue;
-      if (!ClangdOpts.IncludeIneligibleResults &&
+      if (!Opts.IncludeIneligibleResults &&
           (Result.Availability == CXAvailability_NotAvailable ||
            Result.Availability == CXAvailability_NotAccessible))
         continue;
-      auto FilterScore = fuzzyMatch(S, Context, Filter, Result);
-      if (!FilterScore)
-        continue;
-      Candidates.emplace(Result, *FilterScore);
-      if (ClangdOpts.Limit && Candidates.size() > ClangdOpts.Limit) {
-        Candidates.pop();
-        Items.isIncomplete = true;
-      }
-    }
-    while (!Candidates.empty()) {
-      auto &Candidate = Candidates.top();
-      const auto *CCS = Candidate.Result->CreateCodeCompletionString(
-          S, Context, *Allocator, CCTUInfo,
-          CodeCompleteOpts.IncludeBriefComments);
-      assert(CCS && "Expected the CodeCompletionString to be non-null");
-      Items.items.push_back(ProcessCodeCompleteResult(Candidate, *CCS));
-      Candidates.pop();
-    }
-    std::reverse(Items.items.begin(), Items.items.end());
-  }
-
-  GlobalCodeCompletionAllocator &getAllocator() override { return *Allocator; }
+      Results.push_back(Result);
 
+  CodeCompletionAllocator &getAllocator() override { return *CCAllocator; }
   CodeCompletionTUInfo &getCodeCompletionTUInfo() override { return CCTUInfo; }
 
-private:
-  llvm::Optional<float> fuzzyMatch(Sema &S, const CodeCompletionContext &CCCtx,
-                                   FuzzyMatcher &Filter,
-                                   CodeCompletionResult Result) {
+  // Returns the filtering/sorting name for Result, which must be from Results.
+  // Returned string is owned by this recorder (or the AST).
+  llvm::StringRef getName(const CodeCompletionResult &Result) {
     switch (Result.Kind) {
     case CodeCompletionResult::RK_Declaration:
       if (auto *ID = Result.Declaration->getIdentifier())
-        return Filter.match(ID->getName());
+        return ID->getName();
       break;
     case CodeCompletionResult::RK_Keyword:
-      return Filter.match(Result.Keyword);
+      return Result.Keyword;
     case CodeCompletionResult::RK_Macro:
-      return Filter.match(Result.Macro->getName());
+      return Result.Macro->getName();
     case CodeCompletionResult::RK_Pattern:
-      return Filter.match(Result.Pattern->getTypedText());
+      return Result.Pattern->getTypedText();
     }
-    auto *CCS = Result.CreateCodeCompletionString(
-        S, CCCtx, *Allocator, CCTUInfo, /*IncludeBriefComments=*/false);
-    return Filter.match(CCS->getTypedText());
+    auto *CCS = codeCompletionString(Result, /*IncludeBriefComments=*/false);
+    return CCS->getTypedText();
   }
 
-  CompletionItem
-  ProcessCodeCompleteResult(const CompletionCandidate &Candidate,
-                            const CodeCompletionString &CCS) const {
+  // Build a CodeCompletion string for R, which must be from Results.
+  // The CCS will be owned by this recorder.
+  CodeCompletionString *codeCompletionString(const CodeCompletionResult &R,
+                                             bool IncludeBriefComments) {
+    // CodeCompletionResult doesn't seem to be const-correct. We own it, anyway.
+    return const_cast<CodeCompletionResult &>(R).CreateCodeCompletionString(
+        *CCSema, CCContext, *CCAllocator, CCTUInfo, IncludeBriefComments);
+  }
 
-    // Adjust this to InsertTextFormat::Snippet iff we encounter a
-    // CK_Placeholder chunk in SnippetCompletionItemsCollector.
-    CompletionItem Item;
-
-    Item.documentation = getDocumentation(CCS);
-    Item.sortText = Candidate.sortText();
-    Item.scoreInfo = Candidate.Scores;
-
-    Item.detail = getDetail(CCS);
-    Item.filterText = getFilterText(CCS);
-    getLabelAndInsertText(CCS, &Item.label, &Item.insertText, EnableSnippets);
+private:
+  CodeCompleteOptions Opts;
+  std::shared_ptr<GlobalCodeCompletionAllocator> CCAllocator;
+  CodeCompletionTUInfo CCTUInfo;
+};
 
-    Item.insertTextFormat = EnableSnippets ? InsertTextFormat::Snippet
-                                           : InsertTextFormat::PlainText;
+// Tracks a bounded number of candidates with the best scores.
+class TopN {
+public:
+  using value_type = std::pair<CompletionCandidate, CompletionItemScores>;
+  static constexpr size_t Unbounded = std::numeric_limits<size_t>::max();
+
+  TopN(size_t N) : N(N) {}
 
-    // Fill in the kind field of the CompletionItem.
-    Item.kind = toCompletionItemKind(Candidate.Result->Kind,
-                                     Candidate.Result->CursorKind);
+  // Adds a candidate to the set.
+  // Returns true if a candidate was dropped to get back under N.
+  bool push(value_type &&V) {
+    bool Dropped = false;
+    if (Heap.size() >= N) {
+      Dropped = true;
+      if (N > 0 && greater(V, Heap.front())) {
+        std::pop_heap(Heap.begin(), Heap.end(), greater);
+        Heap.back() = std::move(V);
+        std::push_heap(Heap.begin(), Heap.end(), greater);
+      }
+    } else {
+      Heap.push_back(std::move(V));
+      std::push_heap(Heap.begin(), Heap.end(), greater);
+    }
+    assert(Heap.size() <= N);
+    assert(std::is_heap(Heap.begin(), Heap.end(), greater));
+    return Dropped;
+  }
 
-    return Item;
+  // Returns candidates from best to worst.
+  std::vector<value_type> items() && {
+    std::sort_heap(Heap.begin(), Heap.end(), greater);
+    assert(Heap.size() <= N);
+    return std::move(Heap);
   }
 
-  CodeCompleteOptions ClangdOpts;
-  CompletionList &Items;
-  std::shared_ptr<clang::GlobalCodeCompletionAllocator> Allocator;
-  CodeCompletionTUInfo CCTUInfo;
-  NameToComplete &CompletedName;
-  bool EnableSnippets;
-}; // CompletionItemsCollector
+private:
+  static bool greater(const value_type &L, const value_type &R) {
+    if (L.second.finalScore != R.second.finalScore)
+      return L.second.finalScore > R.second.finalScore;
+    return L.first.Name < R.first.Name; // Earlier name is better.
+  }
+
+  const size_t N;
+  std::vector<value_type> Heap; // Min-heap, comparator is greater().
+};
 
 class SignatureHelpCollector final : public CodeCompleteConsumer {
 
 public:
   SignatureHelpCollector(const clang::CodeCompleteOptions &CodeCompleteOpts,
                          SignatureHelp &SigHelp)
       : CodeCompleteConsumer(CodeCompleteOpts, /*OutputIsBinary=*/false),
         SigHelp(SigHelp),
private:
   }
 
   SignatureHelp &SigHelp;
   std::shared_ptr<clang::GlobalCodeCompletionAllocator> Allocator;
   CodeCompletionTUInfo CCTUInfo;
 
 }; // SignatureHelpCollector
 
-bool invokeCodeComplete(const Context &Ctx,
-                        std::unique_ptr<CodeCompleteConsumer> Consumer,
-                        const clang::CodeCompleteOptions &Options,
-                        PathRef FileName,
-                        const tooling::CompileCommand &Command,
-                        PrecompiledPreamble const *Preamble, StringRef Contents,
-                        Position Pos, IntrusiveRefCntPtr<vfs::FileSystem> VFS,
-                        std::shared_ptr<PCHContainerOperations> PCHs) {
+struct SemaCompleteInput {
+  PathRef FileName;
+  const tooling::CompileCommand &Command;
+  PrecompiledPreamble const *Preamble;
+  StringRef Contents;
+  Position Pos;
+  IntrusiveRefCntPtr<vfs::FileSystem> VFS;
+  std::shared_ptr<PCHContainerOperations> PCHs;
+};
+
+// Invokes Sema code completion on a file.
+// Callback will be invoked once completion is done, but before cleaning up.
+bool semaCodeComplete(const Context &Ctx,
+                      const SemaCompleteInput &Input,
+                      llvm::function_ref<void()> Callback = nullptr) {
   std::vector<const char *> ArgStrs;
-  for (const auto &S : Command.CommandLine)
+  for (const auto &S : Input.Command.CommandLine)
     ArgStrs.push_back(S.c_str());
 
-  VFS->setCurrentWorkingDirectory(Command.Directory);
+  Input.VFS->setCurrentWorkingDirectory(Input.Command.Directory);
 
   IgnoreDiagnostics DummyDiagsConsumer;
   auto CI = createInvocationFromCommandLine(
       ArgStrs,
       CompilerInstance::createDiagnostics(new DiagnosticOptions,
                                           &DummyDiagsConsumer, false),
-      VFS);
+      Input.VFS);
   assert(CI && "Couldn't create CompilerInvocation");
   CI->getFrontendOpts().DisableFree = false;
 
   std::unique_ptr<llvm::MemoryBuffer> ContentsBuffer =
-      llvm::MemoryBuffer::getMemBufferCopy(Contents, FileName);
+      llvm::MemoryBuffer::getMemBufferCopy(Input.Contents, Input.FileName);
 
   // We reuse the preamble whether it's valid or not. This is a
   // correctness/performance tradeoff: building without a preamble is slow, and
   // completion is latency-sensitive.
-  if (Preamble) {
+  if (Input.Preamble) {
     auto Bounds =
         ComputePreambleBounds(*CI->getLangOpts(), ContentsBuffer.get(), 0);
     // FIXME(ibiryukov): Remove this call to CanReuse() after we'll fix
     // clients relying on getting stats for preamble files during code
     // completion.
     // Note that results of CanReuse() are ignored, see the comment above.
-    Preamble->CanReuse(*CI, ContentsBuffer.get(), Bounds, VFS.get());
+    Input.Preamble->CanReuse(*CI, ContentsBuffer.get(), Bounds,
+                             Input.VFS.get());
   }
   auto Clang = prepareCompilerInstance(
-      std::move(CI), Preamble, std::move(ContentsBuffer), std::move(PCHs),
-      std::move(VFS), DummyDiagsConsumer);
+      std::move(CI), Input.Preamble, std::move(ContentsBuffer),
+      std::move(Input.PCHs), std::move(Input.VFS), DummyDiagsConsumer);
   auto &DiagOpts = Clang->getDiagnosticOpts();
   DiagOpts.IgnoreWarnings = true;
 
   auto &FrontendOpts = Clang->getFrontendOpts();
   FrontendOpts.SkipFunctionBodies = true;
   FrontendOpts.CodeCompleteOpts = Options;
-  FrontendOpts.CodeCompletionAt.FileName = FileName;
-  FrontendOpts.CodeCompletionAt.Line = Pos.line + 1;
-  FrontendOpts.CodeCompletionAt.Column = Pos.character + 1;
+  FrontendOpts.CodeCompletionAt.FileName = Input.FileName;
+  FrontendOpts.CodeCompletionAt.Line = Input.Pos.line + 1;
+  FrontendOpts.CodeCompletionAt.Column = Input.Pos.character + 1;
 
   Clang->setCodeCompletionConsumer(Consumer.release());
 
   SyntaxOnlyAction Action;
   if (!Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0])) {
-    log(Ctx,
-        "BeginSourceFile() failed when running codeComplete for " + FileName);
+    log(Ctx, "BeginSourceFile() failed when running codeComplete for " +
+                 Input.FileName);
     return false;
   }
   if (!Action.Execute()) {
-    log(Ctx, "Execute() failed when running codeComplete for " + FileName);
+    log(Ctx,
+        "Execute() failed when running codeComplete for " + Input.FileName);
     return false;
   }
 
+  if (Callback)
+    Callback();
   Action.EndSourceFile();
 
   return true;
 }
 
-CompletionItem indexCompletionItem(const Symbol &Sym, llvm::StringRef Filter,
-                                   const SpecifiedScope &SSInfo,
-                                   llvm::StringRef DebuggingLabel = "") {
-  CompletionItem Item;
-  Item.kind = toCompletionItemKind(Sym.SymInfo.Kind);
-  // Add DebuggingLabel to the completion results if DebuggingLabel is not
-  // empty.
-  //
-  // For symbols from static index, there are prefix "[G]" in the
-  // results (which is used for debugging purpose).
-  // So completion list will be like:
-  //   clang::symbol_from_dynamic_index
-  //   [G]clang::symbol_from_static_index
-  //
-  // FIXME: Find out a better way to show the index source.
-  if (!DebuggingLabel.empty()) {
-    llvm::raw_string_ostream Label(Item.label);
-    Label << llvm::format("[%s]%s", DebuggingLabel.str().c_str(),
-                          Sym.Name.str().c_str());
-  } else {
-    Item.label = Sym.Name;
-  }
-  // FIXME(ioeric): support inserting/replacing scope qualifiers.
-
-  // FIXME(ioeric): support snippets.
-  Item.insertText = Sym.CompletionPlainInsertText;
-  Item.insertTextFormat = InsertTextFormat::PlainText;
-  Item.filterText = Sym.Name;
-
-  // FIXME(ioeric): sort symbols appropriately.
-  Item.sortText = "";
-
-  if (Sym.Detail) {
-    Item.documentation = Sym.Detail->Documentation;
-    Item.detail = Sym.Detail->CompletionDetail;
-  }
-
-  return Item;
-}
-
-void completeWithIndex(const Context &Ctx, const SymbolIndex &Index,
-                       llvm::StringRef Code, const SpecifiedScope &SSInfo,
-                       llvm::StringRef Filter, CompletionList *Items,
-                       llvm::StringRef DebuggingLabel = "") {
-  FuzzyFindRequest Req;
-  Req.Query = Filter;
-  // FIXME(ioeric): add more possible scopes based on using namespaces and
-  // containing namespaces.
-  StringRef Scope = SSInfo.Resolved.empty() ? SSInfo.Written : SSInfo.Resolved;
-  Req.Scopes = {Scope.trim(':').str()};
-
-  Items->isIncomplete |= !Index.fuzzyFind(Ctx, Req, [&](const Symbol &Sym) {
-    Items->items.push_back(
-        indexCompletionItem(Sym, Filter, SSInfo, DebuggingLabel));
-  });
-}
-
-SpecifiedScope extraCompletionScope(Sema &S, const CXXScopeSpec &SS) {
+SpecifiedScope getSpecifiedScope(Sema &S, const CXXScopeSpec &SS) {
   SpecifiedScope Info;
   auto &SM = S.getSourceManager();
   auto SpecifierRange = SS.getRange();
   Info.Written = Lexer::getSourceText(
       CharSourceRange::getCharRange(SpecifierRange), SM, clang::LangOptions());
   if (SS.isValid()) {
     DeclContext *DC = S.computeDeclContext(SS);
     if (auto *NS = llvm::dyn_cast<NamespaceDecl>(DC)) {
       Info.Resolved = NS->getQualifiedNameAsString();
     } else if (llvm::dyn_cast<TranslationUnitDecl>(DC) != nullptr) {
       Info.Resolved = "::";
       // Sema does not include the suffix "::" in the range of SS, so we add
       // it back here.
       Info.Written = "::";
     }
   }
   return Info;
 }
 
+// Should we perform index-based completion in this context?
+// FIXME: consider allowing completion, but restricting the result types.
+bool allowIndex(enum CodeCompletionContext::Kind K) {
+  switch (K) {
+  case CodeCompletionContext::CCC_TopLevel:
+  case CodeCompletionContext::CCC_ObjCInterface:
+  case CodeCompletionContext::CCC_ObjCImplementation:
+  case CodeCompletionContext::CCC_ObjCIvarList:
+  case CodeCompletionContext::CCC_ClassStructUnion:
+  case CodeCompletionContext::CCC_Statement:
+  case CodeCompletionContext::CCC_Expression:
+  case CodeCompletionContext::CCC_ObjCMessageReceiver:
+  case CodeCompletionContext::CCC_EnumTag:
+  case CodeCompletionContext::CCC_UnionTag:
+  case CodeCompletionContext::CCC_ClassOrStructTag:
+  case CodeCompletionContext::CCC_ObjCProtocolName:
+  case CodeCompletionContext::CCC_Namespace:
+  case CodeCompletionContext::CCC_Type:
+  case CodeCompletionContext::CCC_Name: // FIXME: why does ns::^ give this?
+  case CodeCompletionContext::CCC_PotentiallyQualifiedName:
+  case CodeCompletionContext::CCC_ParenthesizedExpression:
+  case CodeCompletionContext::CCC_ObjCInterfaceName:
+  case CodeCompletionContext::CCC_ObjCCategoryName:
+    return true;
+  case CodeCompletionContext::CCC_Other: // Be conservative.
+  case CodeCompletionContext::CCC_OtherWithMacros:
+  case CodeCompletionContext::CCC_DotMemberAccess:
+  case CodeCompletionContext::CCC_ArrowMemberAccess:
+  case CodeCompletionContext::CCC_ObjCPropertyAccess:
+  case CodeCompletionContext::CCC_MacroName:
+  case CodeCompletionContext::CCC_MacroNameUse:
+  case CodeCompletionContext::CCC_PreprocessorExpression:
+  case CodeCompletionContext::CCC_PreprocessorDirective:
+  case CodeCompletionContext::CCC_NaturalLanguage:
+  case CodeCompletionContext::CCC_SelectorName:
+  case CodeCompletionContext::CCC_TypeQualifiers:
+  case CodeCompletionContext::CCC_ObjCInstanceMessage:
+  case CodeCompletionContext::CCC_ObjCClassMessage:
+  case CodeCompletionContext::CCC_Recovery:
+    return false;
+  }
+  llvm_unreachable("unknown code completion context");
+}
+
 } // namespace
 
 clang::CodeCompleteOptions CodeCompleteOptions::getClangCompleteOpts() const {
   clang::CodeCompleteOptions Result;
   Result.IncludeCodePatterns = EnableSnippets && IncludeCodePatterns;
   Result.IncludeMacros = IncludeMacros;
   Result.IncludeGlobals = true;
   Result.IncludeBriefComments = IncludeBriefComments;
 
   // When an is used, Sema is responsible for completing the main file,
   // the index can provide results from the preamble.
   // Tell Sema not to deserialize the preamble to look for results.
   Result.LoadExternal = !Index;
 
   return Result;
 }
 
+// Runs Sema-based (AST) and Index-based completion, returns merged results.
+//
+// There are a few tricky considerations:
+//   - the AST provides information needed for the index query (e.g. which
+//     namespaces to search in). So Sema must start first.
+//   - we only want to return the top results (Opts.Limit).
+//     Building CompletionItems for everything else is wasteful, so we want to
+//     preserve the "native" format until we're done with scoring.
+//   - the data underlying Sema completion items is owned by the AST and various
+//     other arenas, which must stay alive for us to build CompletionItems.
+//   - we may get duplicate results from Sema and the Index, we need to merge.
+//
+// So we start Sema completion first, but defer its cleanup until we're done.
+// We use the Sema context information to query the index.
+// Then we merge the two result sets, producing items that are Sema/Index/Both.
+// These items are scored, and the top N are synthesized into the LSP response.
+// Finally, we can clean up the data structures created by Sema completion.
+//
+// Main collaborators are:
+//   - semaCodeComplete sets up the compiler machinery to run code completion.
+//   - CompletionRecorder captures Sema completion results, including context.
+//   - SymbolIndex (Opts.Index) provides index completion results as Symbols
+//   - CompletionCandidates are the result of merging Sema and Index results.
+//     Each candidate points to an underlying CodeCompletionResult (Sema), a
+//     Symbol (Index), or both. It computes the result quality score.
+//     CompletionCandidate also does conversion to CompletionItem (at the end).
+//   - FuzzyMatcher scores how the candidate matches the partial identifier.
+//     This score is combined with the result quality score for the final score.
+//   - TopN determines the results with the best score.
+class CodeCompleteFlow {
+  const Context &Ctx;
+  const CodeCompleteOptions &Opts;
+  // Sema takes ownership of Recorder. Recorder is valid until Sema cleanup.
+  std::unique_ptr<CompletionRecorder> RecorderOwner;
+  CompletionRecorder &Recorder;
+  int NSema = 0, NIndex = 0, NBoth = 0; // Counters for logging.
+  bool Incomplete = false; // Would more be available with a higher limit?
+  llvm::Optional<FuzzyMatcher> Filter; // Initialized once Sema runs.
+
+public:
+  // A CodeCompleteFlow object is only useful for calling run() exactly once.
+  CodeCompleteFlow(const Context &Ctx, const CodeCompleteOptions &Opts)
+      : Ctx(Ctx), Opts(Opts), RecorderOwner(new CompletionRecorder(Opts)),
+        Recorder(*RecorderOwner) {}
+
+  CompletionList run(const SemaCompleteInput &SemaCCInput) && {
+    // We run Sema code completion first. It builds an AST and calculates:
+    //   - completion results based on the AST. These are saved for merging.
+    //   - partial identifier and context. We need these for the index query.
+    CompletionList Output;
+    semaCodeComplete(Ctx, std::move(RecorderOwner), Opts.getClangCompleteOpts(),
+                     SemaCCInput, [&] {
+                       if (Recorder.CCSema)
+                         Output = runWithSema();
+                       else
+                         log(Ctx, "Code complete: no Sema callback, 0 results");
+                     });
+
+    log(Ctx,
+        llvm::formatv("Code complete: {0} results from Sema, {1} from Index, "
+                      "{2} matched, {3} returned{4}.",
+                      NSema, NIndex, NBoth, Output.items.size(),
+                      Output.isIncomplete ? " (incomplete)" : ""));
+    assert(!Opts.Limit || Output.items.size() <= Opts.Limit);
+    // We don't assert that isIncomplete means we hit a limit.
+    // Indexes may choose to impose their own limits even if we don't have one.
+    return Output;
+  }
+
+private:
+  // This is called by run() once Sema code completion is done, but before the
+  // Sema data structures are torn down. It does all the real work.
+  CompletionList runWithSema() {
+    Filter = FuzzyMatcher(
+        Recorder.CCSema->getPreprocessor().getCodeCompletionFilter());
+    // Sema provides the needed context to query the index.
+    // FIXME: in addition to querying for extra/overlapping symbols, we should
+    //        explicitly request symbols corresponding to Sema results.
+    //        We can use their signals even if the index can't suggest them.
+    // We must copy index results to preserve them, but there are at most Limit.
+    auto IndexResults = queryIndex();
+    // Merge Sema and Index results, score them, and pick the winners.
+    auto Top = mergeResults(Recorder.Results, IndexResults);
+    // Convert the results to the desired LSP structs.
+    CompletionList Output;
+    for (auto &C : Top)
+      Output.items.push_back(toCompletionItem(C.first, C.second));
+    Output.isIncomplete = Incomplete;
+    return Output;
+  }
+
+  SymbolSlab queryIndex() {
+    if (!Opts.Index || !allowIndex(Recorder.CCContext.getKind()))
+      return SymbolSlab();
+    SymbolSlab::Builder ResultsBuilder;
+    // Build the query.
+    FuzzyFindRequest Req;
+    Req.Query = Filter->pattern();
+    // If the user typed a scope, e.g. a::b::xxx(), restrict to that scope.
+    // FIXME(ioeric): add scopes based on using directives and enclosing ns.
+    if (auto SS = Recorder.CCContext.getCXXScopeSpecifier())
+      Req.Scopes = {getSpecifiedScope(*Recorder.CCSema, **SS).forIndex()};
+    else
+      // Unless the user typed a ns qualifier, complete in global scope only.
+      // FIXME: once we know what namespaces are in scope (D42073), use those.
+      // FIXME: once we can insert namespace qualifiers and use the in-scope
+      //        namespaces for scoring, search in all namespaces.
+      Req.Scopes = {""};
+    // Run the query against the index.
+    Incomplete |= !Opts.Index->fuzzyFind(
+        Ctx, Req, [&](const Symbol &Sym) { ResultsBuilder.insert(Sym); });
+    return std::move(ResultsBuilder).build();
+  }
+
+  // Merges the Sema and Index results where possible, scores them, and
+  // returns the top results from best to worst.
+  std::vector<std::pair<CompletionCandidate, CompletionItemScores>>
+  mergeResults(const std::vector<CodeCompletionResult> &SemaResults,
+               const SymbolSlab &IndexResults) {
+    // We only keep the best N results at any time, in "native" format.
+    TopN Top(Opts.Limit == 0 ? TopN::Unbounded : Opts.Limit);
+    llvm::DenseSet<const Symbol *> UsedIndexResults;
+    auto CorrespondingIndexResult =
+        [&](const CodeCompletionResult &SemaResult) -> const Symbol * {
+      if (auto SymID = getSymbolID(SemaResult)) {
+        auto I = IndexResults.find(*SymID);
+        if (I != IndexResults.end()) {
+          UsedIndexResults.insert(&*I);
+          return &*I;
+        }
+      }
+      return nullptr;
+    };
+    // Emit all Sema results, merging them with Index results if possible.
+    for (auto &SemaResult : Recorder.Results)
+      addCandidate(Top, &SemaResult, CorrespondingIndexResult(SemaResult));
+    // Now emit any Index-only results.
+    for (const auto &IndexResult : IndexResults) {
+      if (UsedIndexResults.count(&IndexResult))
+        continue;
+      addCandidate(Top, /*SemaResult=*/nullptr, &IndexResult);
+    }
+    return std::move(Top).items();
+  }
+
+  // Scores a candidate and adds it to the TopN structure.
+  void addCandidate(TopN &Candidates, const CodeCompletionResult *SemaResult,
+                    const Symbol *IndexResult) {
+    CompletionCandidate C;
+    C.SemaResult = SemaResult;
+    C.IndexResult = IndexResult;
+    C.Name = IndexResult ? IndexResult->Name : Recorder.getName(*SemaResult);
+
+    CompletionItemScores Scores;
+    if (auto FuzzyScore = Filter->match(C.Name))
+      Scores.filterScore = *FuzzyScore;
+    else
+      return;
+    Scores.symbolScore = C.score();
+    // We score candidates by multiplying symbolScore ("quality" of the result)
+    // with filterScore (how well it matched the query).
+    // This is sensitive to the distribution of both component scores!
+    Scores.finalScore = Scores.filterScore * Scores.symbolScore;
+
+    NSema += bool(SemaResult);
+    NIndex += bool(IndexResult);
+    NBoth += SemaResult && IndexResult;
+    Incomplete |= Candidates.push({C, Scores});
+  }
+
+  CompletionItem toCompletionItem(const CompletionCandidate &Candidate,
+                                  const CompletionItemScores &Scores) {
+    CodeCompletionString *SemaCCS = nullptr;
+    if (auto *SR = Candidate.SemaResult)
+      SemaCCS = Recorder.codeCompletionString(*SR, Opts.IncludeBriefComments);
+    return Candidate.build(Scores, Opts, SemaCCS);
+  }
+};
+
 CompletionList codeComplete(const Context &Ctx, PathRef FileName,
                             const tooling::CompileCommand &Command,
                             PrecompiledPreamble const *Preamble,
                             StringRef Contents, Position Pos,
                             IntrusiveRefCntPtr<vfs::FileSystem> VFS,
                             std::shared_ptr<PCHContainerOperations> PCHs,
                             CodeCompleteOptions Opts) {
-  CompletionList Results;
-  NameToComplete CompletedName;
-  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.
-  // FIXME: merge with Sema results, and respect limits.
-  if (CompletedName.SSInfo && Opts.Index)
-    completeWithIndex(Ctx, *Opts.Index, Contents, *CompletedName.SSInfo,
-                      CompletedName.Filter, &Results, /*DebuggingLabel=*/"I");
-  return Results;
+  return CodeCompleteFlow(Ctx, Opts).run(
+      {FileName, Command, Preamble, Contents, Pos, VFS, PCHs});
 }
 
 SignatureHelp signatureHelp(const Context &Ctx, PathRef FileName,
                             const tooling::CompileCommand &Command,
                             PrecompiledPreamble const *Preamble,
                             StringRef Contents, Position Pos,
                             IntrusiveRefCntPtr<vfs::FileSystem> VFS,
                             std::shared_ptr<PCHContainerOperations> PCHs) {
   SignatureHelp Result;
   clang::CodeCompleteOptions Options;
   Options.IncludeGlobals = false;
   Options.IncludeMacros = false;
   Options.IncludeCodePatterns = false;
   Options.IncludeBriefComments = true;
-  invokeCodeComplete(Ctx,
-                     llvm::make_unique<SignatureHelpCollector>(Options, Result),
-                     Options, FileName, Command, Preamble, Contents, Pos,
-                     std::move(VFS), std::move(PCHs));
+  semaCodeComplete(
+      Ctx, llvm::make_unique<SignatureHelpCollector>(Options, Result), Options,
+      {FileName, Command, Preamble, Contents, Pos, std::move(VFS),
+       std::move(PCHs)});
   return Result;
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/clangd/FuzzyMatch.h

 public:
   // Characters beyond MaxPat are ignored.
   FuzzyMatcher(llvm::StringRef Pattern);
 
   // If Word matches the pattern, return a score in [0,1] (higher is better).
   // Characters beyond MaxWord are ignored.
   llvm::Optional<float> match(llvm::StringRef Word);
 
-  bool empty() { return PatN == 0; }
+  llvm::StringRef pattern() const { return llvm::StringRef(Pat, PatN); }
+  bool empty() const { return PatN == 0; }
 
   // Dump internal state from the last match() to the stream, for debugging.
   // Returns the pattern with [] around matched characters, e.g.
   //   [u_p] + "unique_ptr" --> "[u]nique[_p]tr"
   llvm::SmallString<256> dumpLast(llvm::raw_ostream &) const;
 
 private:
   // We truncate the pattern and the word to bound the cost of matching.

clang-tools-extra/trunk/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);

 MATCHER_P(PlainText, Text, "") {
   return arg.insertTextFormat == clangd::InsertTextFormat::PlainText &&
          arg.insertText == Text;
 }
 MATCHER_P(Snippet, Text, "") {
   return arg.insertTextFormat == clangd::InsertTextFormat::Snippet &&
          arg.insertText == Text;
 }
-MATCHER(FilterContainsName, "") {
+MATCHER(NameContainsFilter, "") {
   if (arg.filterText.empty())
     return true;
   return llvm::StringRef(arg.insertText).contains(arg.filterText);
 }
 // Shorthand for Contains(Named(Name)).
 Matcher<const std::vector<CompletionItem> &> Has(std::string Name) {
   return Contains(Named(std::move(Name)));
 }
CompletionList completions(StringRef Text,
   auto File = getVirtualTestFilePath("foo.cpp");
   Annotations Test(Text);
   Server.addDocument(Context::empty(), File, Test.code()).wait();
   auto CompletionList =
       Server.codeComplete(Context::empty(), File, Test.point(), Opts)
           .get()
           .second.Value;
   // Sanity-check that filterText is valid.
-  EXPECT_THAT(CompletionList.items, Each(FilterContainsName()));
+  EXPECT_THAT(CompletionList.items, Each(NameContainsFilter()));
   return CompletionList;
 }
 
+std::string replace(StringRef Haystack, StringRef Needle, StringRef Repl) {
+  std::string Result;
+  raw_string_ostream OS(Result);
+  std::pair<StringRef, StringRef> Split;
+  for (Split = Haystack.split(Needle); !Split.second.empty();
+       Split = Split.first.split(Needle))
+    OS << Split.first << Repl;
+  Result += Split.first;
+  OS.flush();
+  return Result;
+}
+
 // Helpers to produce fake index symbols for memIndex() or completions().
-Symbol sym(StringRef QName, index::SymbolKind Kind) {
+// USRFormat is a regex replacement string for the unqualified part of the USR.
+Symbol sym(StringRef QName, index::SymbolKind Kind, StringRef USRFormat) {
   Symbol Sym;
-  Sym.ID = SymbolID(QName);
+  std::string USR = "c:"; // We synthesize a few simple cases of USRs by hand!
   size_t Pos = QName.rfind("::");
   if (Pos == llvm::StringRef::npos) {
     Sym.Name = QName;
     Sym.Scope = "";
   } else {
     Sym.Name = QName.substr(Pos + 2);
     Sym.Scope = QName.substr(0, Pos);
+    USR += "@N@" + replace(Sym.Scope, "::", "@N@"); // ns:: -> @N@ns
   }
+  USR += Regex("^.*$").sub(USRFormat, Sym.Name); // e.g. func -> @F@func#
+  Sym.ID = SymbolID(USR);
   Sym.CompletionPlainInsertText = Sym.Name;
+  Sym.CompletionSnippetInsertText = Sym.Name;
   Sym.CompletionLabel = Sym.Name;
   Sym.SymInfo.Kind = Kind;
   return Sym;
 }
-Symbol func(StringRef Name) { return sym(Name, index::SymbolKind::Function); }
-Symbol cls(StringRef Name) { return sym(Name, index::SymbolKind::Class); }
-Symbol var(StringRef Name) { return sym(Name, index::SymbolKind::Variable); }
+Symbol func(StringRef Name) { // Assumes the function has no args.
+  return sym(Name, index::SymbolKind::Function, "@F@\\0#"); // no args
+}
+Symbol cls(StringRef Name) {
+  return sym(Name, index::SymbolKind::Class, "@S@\\0@S@\\0");
+}
+Symbol var(StringRef Name) {
+  return sym(Name, index::SymbolKind::Variable, "@\\0");
+}
 
 TEST(CompletionTest, Limit) {
   clangd::CodeCompleteOptions Opts;
   Opts.Limit = 2;
   auto Results = completions(R"cpp(
 struct ClassWithMembers {
   int AAA();
   int BBB();
auto Results = completions(
         struct LocalClass {};
 
         /// Doc for local_var.
         int local_var;
 
         ClassWithMembers().^
       }
       )cpp",
-      /*IndexSymbols=*/{}, Opts);
+      {cls("IndexClass"), var("index_var"), func("index_func")}, Opts);
 
   // Class members. The only items that must be present in after-dot
   // completion.
   EXPECT_THAT(
       Results.items,
       AllOf(Has(Opts.EnableSnippets ? "method()" : "method"), Has("field")));
   EXPECT_IFF(Opts.IncludeIneligibleResults, Results.items,
              Has("private_field"));
   // Global items.
-  EXPECT_THAT(Results.items, Not(AnyOf(Has("global_var"), Has("global_func"),
-                                       Has("global_func()"), Has("GlobalClass"),
-                                       Has("MACRO"), Has("LocalClass"))));
+  EXPECT_THAT(
+      Results.items,
+      Not(AnyOf(Has("global_var"), Has("index_var"), Has("global_func"),
+                Has("global_func()"), Has("index_func"), Has("GlobalClass"),
+                Has("IndexClass"), Has("MACRO"), Has("LocalClass"))));
   // There should be no code patterns (aka snippets) in after-dot
   // completion. At least there aren't any we're aware of.
   EXPECT_THAT(Results.items, Not(Contains(Kind(CompletionItemKind::Snippet))));
   // Check documentation.
   EXPECT_IFF(Opts.IncludeBriefComments, Results.items,
              Contains(IsDocumented()));
 }
 
auto Results = completions(
         struct LocalClass {};
 
         /// Doc for local_var.
         int local_var;
 
         ^
       }
       )cpp",
-      /*IndexSymbols=*/{}, Opts);
+      {cls("IndexClass"), var("index_var"), func("index_func")}, Opts);
 
   // Class members. Should never be present in global completions.
   EXPECT_THAT(Results.items,
               Not(AnyOf(Has("method"), Has("method()"), Has("field"))));
   // Global items.
   EXPECT_THAT(Results.items,
-              AllOf(Has("global_var"),
+              AllOf(Has("global_var"), Has("index_var"),
                     Has(Opts.EnableSnippets ? "global_func()" : "global_func"),
-                    Has("GlobalClass")));
+                    Has("index_func" /* our fake symbol doesn't include () */),
+                    Has("GlobalClass"), Has("IndexClass")));
   // A macro.
   EXPECT_IFF(Opts.IncludeMacros, Results.items, Has("MACRO"));
   // Local items. Must be present always.
   EXPECT_THAT(Results.items,
               AllOf(Has("local_var"), Has("LocalClass"),
                     Contains(Kind(CompletionItemKind::Snippet))));
   // Check documentation.
   EXPECT_IFF(Opts.IncludeBriefComments, Results.items,
auto Results = completions(
       )cpp",
       /*IndexSymbols=*/{}, Opts);
   EXPECT_THAT(Results.items,
               HasSubsequence(Snippet("a"),
                              Snippet("f(${1:int i}, ${2:const float f})")));
 }
 
 TEST(CompletionTest, Kinds) {
-  auto Results = completions(R"cpp(
+  auto Results = completions(
+      R"cpp(
           #define MACRO X
           int variable;
           struct Struct {};
           int function();
           int X = ^
-  )cpp");
-  EXPECT_THAT(Results.items, Has("function", CompletionItemKind::Function));
-  EXPECT_THAT(Results.items, Has("variable", CompletionItemKind::Variable));
-  EXPECT_THAT(Results.items, Has("int", CompletionItemKind::Keyword));
-  EXPECT_THAT(Results.items, Has("Struct", CompletionItemKind::Class));
-  EXPECT_THAT(Results.items, Has("MACRO", CompletionItemKind::Text));
+      )cpp",
+      {func("indexFunction"), var("indexVariable"), cls("indexClass")});
+  EXPECT_THAT(Results.items,
+              AllOf(Has("function", CompletionItemKind::Function),
+                    Has("variable", CompletionItemKind::Variable),
+                    Has("int", CompletionItemKind::Keyword),
+                    Has("Struct", CompletionItemKind::Class),
+                    Has("MACRO", CompletionItemKind::Text),
+                    Has("indexFunction", CompletionItemKind::Function),
+                    Has("indexVariable", CompletionItemKind::Variable),
+                    Has("indexClass", CompletionItemKind::Class)));
 
   Results = completions("nam^");
   EXPECT_THAT(Results.items, Has("namespace", CompletionItemKind::Snippet));
 }
 
 TEST(CompletionTest, NoDuplicates) {
-  auto Items = completions(R"cpp(
-struct Adapter {
+  auto Results = completions(
+      R"cpp(
+          class Adapter {
             void method();
           };
 
           void Adapter::method() {
             Adapter^
           }
-  )cpp")
-                   .items;
+      )cpp",
+      {cls("Adapter")});
 
   // Make sure there are no duplicate entries of 'Adapter'.
-  EXPECT_THAT(Items, ElementsAre(Named("Adapter"), Named("~Adapter")));
-}
-
-TEST(CompletionTest, FuzzyRanking) {
-  auto Items = completions(R"cpp(
-      struct fake { int BigBang, Babble, Ball; };
-      int main() { fake().bb^ }")cpp").items;
-  // BigBang is a better match than Babble. Ball doesn't match at all.
-  EXPECT_THAT(Items, ElementsAre(Named("BigBang"), Named("Babble")));
+  EXPECT_THAT(Results.items, ElementsAre(Named("Adapter"), Named("~Adapter")));
 }
 
-TEST(CompletionTest, NoIndex) {
-  auto Results = completions(R"cpp(
-      namespace ns { class Local {}; }
-      void f() { ns::^ }
-  )cpp");
-  EXPECT_THAT(Results.items, Has("Local"));
-}
-
-TEST(CompletionTest, StaticAndDynamicIndex) {
-  clangd::CodeCompleteOptions Opts;
-  auto StaticIdx = memIndex({cls("ns::XYZ")});
-  auto DynamicIdx = memIndex({func("ns::foo")});
-  auto Merge = mergeIndex(DynamicIdx.get(), StaticIdx.get());
-  Opts.Index = Merge.get();
-
+TEST(CompletionTest, ScopedNoIndex) {
   auto Results = completions(
       R"cpp(
-          void f() { ::ns::^ }
-      )cpp",
-      /*IndexSymbols=*/{}, Opts);
-  EXPECT_THAT(Results.items, Contains(Labeled("[I]XYZ")));
-  EXPECT_THAT(Results.items, Contains(Labeled("[I]foo")));
+          namespace fake { int BigBang, Babble, Ball; };
+          int main() { fake::bb^ }
+      ")cpp");
+  // BigBang is a better match than Babble. Ball doesn't match at all.
+  EXPECT_THAT(Results.items, ElementsAre(Named("BigBang"), Named("Babble")));
 }
 
-TEST(CompletionTest, IndexScope) {
+TEST(CompletionTest, Scoped) {
   auto Results = completions(
       R"cpp(
-          namespace ns { int local; }
-          void f() { ns::^ }
-      )cpp",
-      {cls("ns::XYZ"), cls("nx::XYZ"), func("ns::foo")});
-  EXPECT_THAT(Results.items,
-              UnorderedElementsAre(Named("XYZ"), Named("foo"), Named("local")));
+          namespace fake { int Babble, Ball; };
+          int main() { fake::bb^ }
+      ")cpp",
+      {var("fake::BigBang")});
+  EXPECT_THAT(Results.items, ElementsAre(Named("BigBang"), Named("Babble")));
 }
 
-TEST(CompletionTest, IndexBasedWithFilter) {
+TEST(CompletionTest, ScopedWithFilter) {
   auto Results = completions(
       R"cpp(
           void f() { ns::x^ }
       )cpp",
       {cls("ns::XYZ"), func("ns::foo")});
   EXPECT_THAT(Results.items,
               UnorderedElementsAre(AllOf(Named("XYZ"), Filter("XYZ"))));
 }
 
-TEST(CompletionTest, IndexGlobalQualified) {
+TEST(CompletionTest, GlobalQualified) {
   auto Results = completions(
       R"cpp(
           void f() { ::^ }
       )cpp",
       {cls("XYZ")});
   EXPECT_THAT(Results.items, AllOf(Has("XYZ", CompletionItemKind::Class),
                                    Has("f", CompletionItemKind::Function)));
 }
 
-TEST(CompletionTest, IndexFullyQualifiedScope) {
+TEST(CompletionTest, FullyQualified) {
   auto Results = completions(
       R"cpp(
+          namespace ns { void bar(); }
           void f() { ::ns::^ }
       )cpp",
       {cls("ns::XYZ")});
-  EXPECT_THAT(Results.items, Has("XYZ", CompletionItemKind::Class));
+  EXPECT_THAT(Results.items, AllOf(Has("XYZ", CompletionItemKind::Class),
+                                   Has("bar", CompletionItemKind::Function)));
+}
+
+TEST(CompletionTest, SemaIndexMerge) {
+  auto Results = completions(
+      R"cpp(
+          namespace ns { int local; void both(); }
+          void f() { ::ns::^ }
+      )cpp",
+      {func("ns::both"), cls("ns::Index")});
+  // We get results from both index and sema, with no duplicates.
+  EXPECT_THAT(
+      Results.items,
+      UnorderedElementsAre(Named("local"), Named("Index"), Named("both")));
 }
 
 TEST(CompletionTest, IndexSuppressesPreambleCompletions) {
   MockFSProvider FS;
   MockCompilationDatabase CDB;
   IgnoreDiagnostics DiagConsumer;
   ClangdServer Server(CDB, DiagConsumer, FS, getDefaultAsyncThreadsCount(),
                       /*StorePreamblesInMemory=*/true);