[clangd] Index-based code completion.

[ioeric]

Summary

Use symbol index to populate completion results for qualfified IDs e.g. "nx::A^".

[ioeric]

• Merge remote-tracking branch 'origin/master' into index-completion
• Fix merge with origin/master.

[sammccall]

A few drive-by comments, will look deeper if I have time but don't wait for me.

clangd/Position.cpp

34 ↗

(On Diff #127118)

This is deep magic (how it handles npos) and I'd like to replace it with something more explicit

15 ↗

(On Diff #127096)

This is kind of note-to-self, but there are things to fix here

• this seems to handle \r\n fine, no FIXME needed
• UTF8 comment should be // FIXME: we're counting UTF8 bytes, LSP wants UTF16 code units
• we should return Code.size() when we don't find a \n
• we should cap the normal return value at Code.size()
• Offset is weird - it should consistently point after the \n (init to 0, Offset = F + 1), so -1 at the end seems like a bug

clangd/Position.h

1 ↗

(On Diff #127096)

This seems like a really specific name - one possible generalization is "utilities that examine source code directly" - SourceCode.h?
This is just a hunch that we might have some more such logic around preambles, language detection, etc.

[sammccall]

Hope you don't mind me piling on... let me know!
Mostly readability, but i'd also like to reduce the scope w.r.t namespace completion.

clangd/CodeComplete.cpp

90 ↗

(On Diff #127118)

toCompletionItemKind?

getKindOfSymbol doesn't match either the input or output, and they have very similar names...

(yes, the names above are bad too - feel free to fix them!)

103 ↗

(On Diff #127118)

LSP has struct (not in protocol yet)

fine for these to be FIXME

111 ↗

(On Diff #127118)

this seems wrong? I would have thought references are similar to c++ references?
can't find anything in LSP either way.

TypeAlias seems like it could default to class, for Using is complicated (would need to look at the subtype) - maybe just unknown?

114 ↗

(On Diff #127118)

conversionfunction might be rather operator, not sure

121 ↗

(On Diff #127118)

LSP has enum constant, not in protocol.h yet

131 ↗

(On Diff #127118)

destructor seems more like an operator or method

280 ↗

(On Diff #127118)

qualified

282 ↗

(On Diff #127118)

nit: 'info' is just noise. Specifier is vague too - consider calling this SpecifiedScope, putting the emphasis on the user interaction.

283 ↗

(On Diff #127118)

There's a lot of sema/ast details here, wedged in the middle of the code that deals with candidates and scoring. Can you forward declare this, and move this implementation and the other details somewhere lower?

283 ↗

(On Diff #127118)

"create" doesn't give any more semantics than a constructor would.

Maybe extractCompletionScope? (This could also be a free function)

310 ↗

(On Diff #127118)

The written/resolved distinction is tangled up with the various fields relating to the written form.

Could you pull out a struct here like:
struct SourceRange {size_t Begin; size_t End; std::string Text}

(This might be a reasonable candidate for `SourceCode.h)

Then this struct can become struct ScopeSpecifier { SourceRange Written, std::string Resolved }

322 ↗

(On Diff #127118)

nit: symbol is impossibly vague here - since we're always talking about symbols and it's hard to know you mean index::Symbol.

I'd call this indexCompletionItem, but just toCompletionItem seems fine too

325 ↗

(On Diff #127118)

as discussed offline: fuzzy matching and rewriting qualifiers is a can of worms.
I'd suggest we don't open it yet: just complete the symbols from exactly the typed scope.
Next we can work on making global completion work (empty qualifier can complete any namespace's symbols).
Finally we'll see if we need to tackle fuzzy-matching the parent namespace.

Among other things, this means that the first step doesn't have to rewrite qualifiers at all, the second only needs to insert them, and we defer thorny cases until the third.

347 ↗

(On Diff #127118)

we're a bit lax about the "method name should start with a verb" rule, but this one I actually found hard to parse.

completeWithIndex? (since there's no unqualified case yet, and there's no need to guess about how the code would be structured at this point)

362 ↗

(On Diff #127118)

suggest we do this in a structured way instead:
Index::fuzzyFind query has a vector<string> of namespaces to look up in

373 ↗

(On Diff #127118)

Please look for names that will tell the reader what the role of this thing is, and only add comments that provide extra information.

SemaCompletionInfo accurately describes most of the types in this file!

Best i can come up with is NameToComplete or LeadingText - not great :-(

375 ↗

(On Diff #127118)

the partial identifier that is being completed, without qualifiers

380 ↗

(On Diff #127118)

It's not clear what's to fix here - isn't non-qualified ID completion already represented by {Filter, None}?
(Feel free just to remove the comment if it's not clear what's to be done)

397 ↗

(On Diff #127118)

nit: auto seems a lot easier to read here?

[ilya-biryukov]

Here are a few more comments.

clangd/CodeComplete.cpp

329 ↗

(On Diff #127118)

NIT: FIXME(ioeric)?

334 ↗

(On Diff #127118)

NIT: FIXME(ioeric)?
Also, why not provide some sortText here? Like a qualified name. Because we're currently missing scores?

380 ↗

(On Diff #127118)

NIT: FIXME(ioeric)?

847 ↗

(On Diff #127096)

NIT: FIXME(ioeric)?
Also, what's missing to resolve this FIXME in this commit?

clangd/CodeComplete.h

64 ↗

(On Diff #127118)

Given the comment, maybe we want to pass it as a separate parameter instead?

[ioeric]

• Address comments in CodeComplete.cpp
• Split index changes into a separate patch.
• Merged with patch D41351.
• Remove Position.* files.

[ioeric]

Thanks for the review!

clangd/CodeComplete.cpp

111 ↗

(On Diff #127118)

TypeAlias could be more than class I think? And they are references (to types) to some extend. Anyhow, this is copied from the conversion function above. I'll leave a FIXME for now.

114 ↗

(On Diff #127118)

Operator is not in the protocol either. I leave a FIXME and will clean it up in followup.

283 ↗

(On Diff #127118)

This is moved to a standalone function extractCompletionScope.

310 ↗

(On Diff #127118)

Got rid of ranges as we don't need any them in this revision.

334 ↗

(On Diff #127118)

Does sortText have to be non-empty? I thought the empty string would make all candidates equally scored?

I think we want either sensible score or (for now) no score at all.

373 ↗

(On Diff #127118)

NameToComplete sounds reasonable.

847 ↗

(On Diff #127096)

Didn't realize logger is ready to use. Switched to use logger.

clangd/CodeComplete.h

64 ↗

(On Diff #127118)

@sammccall suggested this approach in the previous prototype patch. I also ended up preferring this approach because:

1. it doesn't require changing ClangdServer interfaces, and the dynamic index should be built by ClangdServer and thus doesn't make sense to be a parameter.
2. it enables unit tests to use customized dummy indexes.
3. we might take another (static) index in the future, and it seems easier to pass it in via the options than adding another parameter.

[ioeric]

• Merged with origin/master
• Merged with D41351

[ioeric]

• Fixed a bug when completing scope that starts with '::'.
• Diff base on origin/master

[ilya-biryukov]

clangd/CodeComplete.cpp

334 ↗

(On Diff #127118)

LS says that if sortText is empty, label should be used. We're probably fine here, you're right.

clangd/CodeComplete.h

64 ↗

(On Diff #127118)

1. it doesn't require changing ClangdServer interfaces, and the dynamic index should be built by ClangdServer and thus doesn't make sense to be a parameter.

We do have it as a parameter to codeComplete method, the fact that it's wrapped in a struct does not make much difference.
ClangdServer should probably accept it in a constructor instead if we want to override some stuff via the dynamic index instead.

2. it enables unit tests to use customized dummy indexes.

unit-testing code can easily wrap any interface, this shouldn't be a problem.

3. we might take another (static) index in the future, and it seems easier to pass it in via the options than adding another parameter.

I'm looking at CodeCompleteOptions as a configurable user preference rather than a struct, containing all required inputs of codeComplete. I don't think SymbolIndex is in line with other fields that this struct contains.

[sammccall]

clangd/CodeComplete.cpp

111 ↗

(On Diff #127118)

Yeah, this is the problem I was alluding to before - LSP encourages us to be very specific in completion kinds - but we can't always be. Class seems like the best guess to me, but FIXME is also fine for now.

283 ↗

(On Diff #127118)

Thanks for extracting the function. These index-related details are still out of place - they split the two chunks of code that mostly do sema-based completion.
Can you move indexCompletionItem, completeWithIndex, and the implementation of extractCompletionScope below? I'd suggest immediately above codeComplete().

clangd/CodeComplete.h

64 ↗

(On Diff #127118)

So yeah, this is my fault...
I do agree it's unfortunate to have a non-user-specified param in the CodeComplete options. It's tricky - from the perspective of this module the index really is such an option, and we want to propagate it around like one. We just don't (currently) want to encourage its use as an API to clangdserver.

codeComplete currently has 9(!) arguments. Different people will have different reactions to this, mine is to do almost anything to avoid a 10th :-)

unit-testing code can easily wrap any interface, this shouldn't be a problem.

This doesn't match my experience at all. Can you suggest how to test this logic without adding parameters to at least ClangdServer::codeComplete and the codeComplete test helpers?

ClangdServer should probably accept it in a constructor instead if we want to override some stuff via the dynamic index instead.

As of today, the dynamic index is the only index clangd supports. There's nothing to accept in the constructor, it's entirely owned by ClangdServer.

[ilya-biryukov]

LGTM. I still think that we should move the SymbolIndex out of the struct, but don't want to block this patch.

clangd/CodeComplete.h

64 ↗

(On Diff #127118)

codeComplete currently has 9(!) arguments. Different people will have different reactions to this, mine is to do almost anything to avoid a 10th :-)

I do agree this is unfortunate and I'm not at all opposed to cleaning that up. By removing parameters that we don't need or grouping them into a struct that has saner default parameters or in a different way. Both 9 and 10 seem equally bad to me.

My point is that SymbolIndex should not be part of CodeCompleteOptions only because it makes it easier to pass it around.

This doesn't match my experience at all. Can you suggest how to test this logic without adding parameters to at least ClangdServer::codeComplete and the codeComplete test helpers?

Exactly, I would go with the test helper.

As of today, the dynamic index is the only index clangd supports. There's nothing to accept in the constructor, it's entirely owned by ClangdServer.

We do have implementations of the index in the tests that we pass around.

That being said, I don't want this change to be blocked by my opinion on this matter. This is a minor thing, compared to all the other changes in the patch. Just wanted to make a point that this field totally feels out of place.

[ioeric]

• Move implementations around to make code easier to read.

[ioeric]

• Add a FIXME for Index in code completion options.

[ioeric]

clangd/CodeComplete.h

64 ↗

(On Diff #127118)

Thanks for the feedback! I added a FIXME for this. I am happy to clean this up when we have a saner way to config code completion in clangd :)

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

 //===---------------------------------------------------------------------===//
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_CODECOMPLETE_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_CODECOMPLETE_H
 
 #include "Context.h"
 #include "Logger.h"
 #include "Path.h"
 #include "Protocol.h"
+#include "index/Index.h"
 #include "clang/Frontend/PrecompiledPreamble.h"
 #include "clang/Sema/CodeCompleteOptions.h"
 #include "clang/Tooling/CompilationDatabase.h"
 
 namespace clang {
 class PCHContainerOperations;
 namespace clangd {
 
struct CodeCompleteOptions {
 
   /// Include results that are not legal completions in the current context.
   /// For example, private members are usually inaccessible.
   bool IncludeIneligibleResults = false;
 
   /// Limit the number of results returned (0 means no limit).
   /// If more results are available, we set CompletionList.isIncomplete.
   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;
 };
 
 /// 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,

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

 //
 // Signature help works in a similar way as code completion, but it is simpler
 // as there are typically fewer candidates.
 //
 //===---------------------------------------------------------------------===//
 
 #include "CodeComplete.h"
 #include "Compiler.h"
+#include "Logger.h"
+#include "index/Index.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/FrontendActions.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "clang/Sema/Sema.h"
 #include <queue>
 
 namespace clang {
 namespace clangd {
 namespace {
 
-CompletionItemKind getKindOfDecl(CXCursorKind CursorKind) {
+CompletionItemKind toCompletionItemKind(CXCursorKind CursorKind) {
   switch (CursorKind) {
   case CXCursor_MacroInstantiation:
   case CXCursor_MacroDefinition:
     return CompletionItemKind::Text;
   case CXCursor_CXXMethod:
+  case CXCursor_Destructor:
     return CompletionItemKind::Method;
   case CXCursor_FunctionDecl:
   case CXCursor_FunctionTemplate:
     return CompletionItemKind::Function;
   case CXCursor_Constructor:
-  case CXCursor_Destructor:
     return CompletionItemKind::Constructor;
   case CXCursor_FieldDecl:
     return CompletionItemKind::Field;
   case CXCursor_VarDecl:
   case CXCursor_ParmDecl:
     return CompletionItemKind::Variable;
-  case CXCursor_ClassDecl:
+  // FIXME(ioeric): use LSP struct instead of class when it is suppoted in the
+  // protocol.
   case CXCursor_StructDecl:
+  case CXCursor_ClassDecl:
   case CXCursor_UnionDecl:
   case CXCursor_ClassTemplate:
   case CXCursor_ClassTemplatePartialSpecialization:
     return CompletionItemKind::Class;
   case CXCursor_Namespace:
   case CXCursor_NamespaceAlias:
   case CXCursor_NamespaceRef:
     return CompletionItemKind::Module;
   case CXCursor_EnumConstantDecl:
     return CompletionItemKind::Value;
   case CXCursor_EnumDecl:
     return CompletionItemKind::Enum;
+  // FIXME(ioeric): figure out whether reference is the right type for aliases.
   case CXCursor_TypeAliasDecl:
   case CXCursor_TypeAliasTemplateDecl:
   case CXCursor_TypedefDecl:
   case CXCursor_MemberRef:
   case CXCursor_TypeRef:
     return CompletionItemKind::Reference;
   default:
     return CompletionItemKind::Missing;
   }
 }
 
-CompletionItemKind getKind(CodeCompletionResult::ResultKind ResKind,
-                           CXCursorKind CursorKind) {
+CompletionItemKind
+toCompletionItemKind(CodeCompletionResult::ResultKind ResKind,
   switch (ResKind) {
   case CodeCompletionResult::RK_Declaration:
-    return getKindOfDecl(CursorKind);
+    return toCompletionItemKind(CursorKind);
   case CodeCompletionResult::RK_Keyword:
     return CompletionItemKind::Keyword;
   case CodeCompletionResult::RK_Macro:
     return CompletionItemKind::Text; // unfortunately, there's no 'Macro'
                                      // completion items in LSP.
   case CodeCompletionResult::RK_Pattern:
     return CompletionItemKind::Snippet;
   }
   llvm_unreachable("Unhandled CodeCompletionResult::ResultKind.");
 }
 
+CompletionItemKind toCompletionItemKind(index::SymbolKind Kind) {
+  using SK = index::SymbolKind;
+  switch (Kind) {
+  case SK::Unknown:
+    return CompletionItemKind::Missing;
+  case SK::Module:
+  case SK::Namespace:
+  case SK::NamespaceAlias:
+    return CompletionItemKind::Module;
+  case SK::Macro:
+    return CompletionItemKind::Text;
+  case SK::Enum:
+    return CompletionItemKind::Enum;
+  // FIXME(ioeric): use LSP struct instead of class when it is suppoted in the
+  // protocol.
+  case SK::Struct:
+  case SK::Class:
+  case SK::Protocol:
+  case SK::Extension:
+  case SK::Union:
+    return CompletionItemKind::Class;
+  // FIXME(ioeric): figure out whether reference is the right type for aliases.
+  case SK::TypeAlias:
+  case SK::Using:
+    return CompletionItemKind::Reference;
+  case SK::Function:
+  // FIXME(ioeric): this should probably be an operator. This should be fixed
+  // when `Operator` is support type in the protocol.
+  case SK::ConversionFunction:
+    return CompletionItemKind::Function;
+  case SK::Variable:
+  case SK::Parameter:
+    return CompletionItemKind::Variable;
+  case SK::Field:
+    return CompletionItemKind::Field;
+  // FIXME(ioeric): use LSP enum constant when it is supported in the protocol.
+  case SK::EnumConstant:
+    return CompletionItemKind::Value;
+  case SK::InstanceMethod:
+  case SK::ClassMethod:
+  case SK::StaticMethod:
+  case SK::Destructor:
+    return CompletionItemKind::Method;
+  case SK::InstanceProperty:
+  case SK::ClassProperty:
+  case SK::StaticProperty:
+    return CompletionItemKind::Property;
+  case SK::Constructor:
+    return CompletionItemKind::Constructor;
+  }
+  llvm_unreachable("Unhandled clang::index::SymbolKind.");
+}
+
 std::string escapeSnippet(const llvm::StringRef Text) {
   std::string Result;
   Result.reserve(Text.size()); // Assume '$', '}' and '\\' are rare.
   for (const auto Character : Text) {
     if (Character == '$' || Character == '}' || Character == '\\')
       Result.push_back('\\');
     Result.push_back(Character);
   }
static uint32_t encodeFloat(float F) {
     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.
   }
 };
 
+/// \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;
+};
+
+SpecifiedScope extraCompletionScope(Sema &S, const CXXScopeSpec &SS);
+
 class CompletionItemsCollector : public CodeCompleteConsumer {
 public:
   CompletionItemsCollector(const CodeCompleteOptions &CodeCompleteOpts,
-                           CompletionList &Items)
+                           CompletionList &Items, NameToComplete &CompletedName)
       : CodeCompleteConsumer(CodeCompleteOpts.getClangCompleteOpts(),
                              /*OutputIsBinary=*/false),
         ClangdOpts(CodeCompleteOpts), Items(Items),
         Allocator(std::make_shared<clang::GlobalCodeCompletionAllocator>()),
-        CCTUInfo(Allocator) {}
+        CCTUInfo(Allocator), CompletedName(CompletedName) {}
 
   void ProcessCodeCompleteResults(Sema &S, CodeCompletionContext Context,
                                   CodeCompletionResult *Results,
                                   unsigned NumResults) override final {
-    StringRef Filter = S.getPreprocessor().getCodeCompletionFilter();
+    if (auto SS = Context.getCXXScopeSpecifier())
+      CompletedName.SSInfo = extraCompletionScope(S, **SS);
+
+    CompletedName.Filter = S.getPreprocessor().getCodeCompletionFilter();
     std::priority_queue<CompletionCandidate> Candidates;
     for (unsigned I = 0; I < NumResults; ++I) {
       auto &Result = Results[I];
       if (!ClangdOpts.IncludeIneligibleResults &&
           (Result.Availability == CXAvailability_NotAvailable ||
            Result.Availability == CXAvailability_NotAccessible))
         continue;
-      if (!Filter.empty() && !fuzzyMatch(S, Context, Filter, Result))
+      if (!CompletedName.Filter.empty() &&
+          !fuzzyMatch(S, Context, CompletedName.Filter, Result))
         continue;
       Candidates.emplace(Result);
       if (ClangdOpts.Limit && Candidates.size() > ClangdOpts.Limit) {
         Candidates.pop();
         Items.isIncomplete = true;
       }
     }
     while (!Candidates.empty()) {
ProcessCodeCompleteResult(const CompletionCandidate &Candidate,
     Item.documentation = getDocumentation(CCS);
     Item.sortText = Candidate.sortText();
 
     // Fill in the label, detail, insertText and filterText fields of the
     // CompletionItem.
     ProcessChunks(CCS, Item);
 
     // Fill in the kind field of the CompletionItem.
-    Item.kind = getKind(Candidate.Result->Kind, Candidate.Result->CursorKind);
+    Item.kind = toCompletionItemKind(Candidate.Result->Kind,
+                                     Candidate.Result->CursorKind);
 
     return Item;
   }
 
   virtual void ProcessChunks(const CodeCompletionString &CCS,
                              CompletionItem &Item) const = 0;
 
   CodeCompleteOptions ClangdOpts;
   CompletionList &Items;
   std::shared_ptr<clang::GlobalCodeCompletionAllocator> Allocator;
   CodeCompletionTUInfo CCTUInfo;
-
+  NameToComplete &CompletedName;
 }; // CompletionItemsCollector
 
 bool isInformativeQualifierChunk(CodeCompletionString::Chunk const &Chunk) {
   return Chunk.Kind == CodeCompletionString::CK_Informative &&
          StringRef(Chunk.Text).endswith("::");
 }
 
 class PlainTextCompletionItemsCollector final
     : public CompletionItemsCollector {
 
 public:
   PlainTextCompletionItemsCollector(const CodeCompleteOptions &CodeCompleteOpts,
-                                    CompletionList &Items)
-      : CompletionItemsCollector(CodeCompleteOpts, Items) {}
+                                    CompletionList &Items,
+                                    NameToComplete &CompletedName)
+      : CompletionItemsCollector(CodeCompleteOpts, Items, CompletedName) {}
 
 private:
   void ProcessChunks(const CodeCompletionString &CCS,
                      CompletionItem &Item) const override {
     for (const auto &Chunk : CCS) {
       // Informative qualifier chunks only clutter completion results, skip
       // them.
       if (isInformativeQualifierChunk(Chunk))
void ProcessChunks(const CodeCompletionString &CCS,
     }
   }
 }; // PlainTextCompletionItemsCollector
 
 class SnippetCompletionItemsCollector final : public CompletionItemsCollector {
 
 public:
   SnippetCompletionItemsCollector(const CodeCompleteOptions &CodeCompleteOpts,
-                                  CompletionList &Items)
-      : CompletionItemsCollector(CodeCompleteOpts, Items) {}
+                                  CompletionList &Items,
+                                  NameToComplete &CompletedName)
+      : CompletionItemsCollector(CodeCompleteOpts, Items, CompletedName) {}
 
 private:
   void ProcessChunks(const CodeCompletionString &CCS,
                      CompletionItem &Item) const override {
     unsigned ArgCount = 0;
     for (const auto &Chunk : CCS) {
       // Informative qualifier chunks only clutter completion results, skip
       // them.
if (!Action.Execute()) {
     return false;
   }
 
   Action.EndSourceFile();
 
   return true;
 }
 
+CompletionItem indexCompletionItem(const Symbol &Sym, llvm::StringRef Filter,
+                                   const SpecifiedScope &SSInfo) {
+  CompletionItem Item;
+  Item.kind = toCompletionItemKind(Sym.SymInfo.Kind);
+  Item.label = Sym.Name;
+  // FIXME(ioeric): support inserting/replacing scope qualifiers.
+  Item.insertText = Sym.Name;
+  // FIXME(ioeric): support snippets.
+  Item.insertTextFormat = InsertTextFormat::PlainText;
+  Item.filterText = Filter;
+
+  // FIXME(ioeric): sort symbols appropriately.
+  Item.sortText = "";
+
+  // FIXME(ioeric): use more symbol information (e.g. documentation, label) to
+  // populate the completion item.
+
+  return Item;
+}
+
+void completeWithIndex(const Context &Ctx, const SymbolIndex &Index,
+                       llvm::StringRef Code, const SpecifiedScope &SSInfo,
+                       llvm::StringRef Filter, CompletionList *Items) {
+  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));
+  });
+}
+
+SpecifiedScope extraCompletionScope(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 (auto *TU = llvm::dyn_cast<TranslationUnitDecl>(DC)) {
+      Info.Resolved = "::";
+      // Sema does not include the suffix "::" in the range of SS, so we add
+      // it back here.
+      Info.Written = "::";
+    }
+  }
+  return Info;
+}
+
 } // namespace
 
 clang::CodeCompleteOptions CodeCompleteOptions::getClangCompleteOpts() const {
   clang::CodeCompleteOptions Result;
   Result.IncludeCodePatterns = EnableSnippets && IncludeCodePatterns;
   Result.IncludeMacros = IncludeMacros;
   Result.IncludeGlobals = IncludeGlobals;
   Result.IncludeBriefComments = IncludeBriefComments;
 
+  // Enable index-based code completion when Index is provided.
+  Result.IncludeNamespaceLevelDecls = !Index;
+
   return Result;
 }
 
 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;
   std::unique_ptr<CodeCompleteConsumer> Consumer;
+  NameToComplete CompletedName;
   if (Opts.EnableSnippets) {
-    Consumer =
-        llvm::make_unique<SnippetCompletionItemsCollector>(Opts, Results);
+    Consumer = llvm::make_unique<SnippetCompletionItemsCollector>(
+        Opts, Results, CompletedName);
   } else {
-    Consumer =
-        llvm::make_unique<PlainTextCompletionItemsCollector>(Opts, Results);
+    Consumer = llvm::make_unique<PlainTextCompletionItemsCollector>(
+        Opts, Results, CompletedName);
   }
   invokeCodeComplete(Ctx, std::move(Consumer), Opts.getClangCompleteOpts(),
                      FileName, Command, Preamble, Contents, Pos, std::move(VFS),
                      std::move(PCHs));
+  if (Opts.Index && CompletedName.SSInfo) {
+    log(Ctx, "WARNING: Got completion results from sema for completion on "
+             "qualified ID while symbol index is provided.");
+    Results.items.clear();
+    completeWithIndex(Ctx, *Opts.Index, Contents, *CompletedName.SSInfo,
+                      CompletedName.Filter, &Results);
+  }
   return Results;
 }
 
 SignatureHelp signatureHelp(const Context &Ctx, PathRef FileName,
                             const tooling::CompileCommand &Command,
                             PrecompiledPreamble const *Preamble,
                             StringRef Contents, Position Pos,
                             IntrusiveRefCntPtr<vfs::FileSystem> VFS,

clang-tools-extra/trunk/clangd/index/FileIndex.h

private:
   llvm::StringMap<std::shared_ptr<SymbolSlab>> FileToSlabs;
 };
 
 /// \brief This manages symbls from files and an in-memory index on all symbols.
 class FileIndex : public SymbolIndex {
 public:
   /// \brief Update symbols in \p Path with symbols in \p AST. If \p AST is
   /// nullptr, this removes all symbols in the file
-  void update(Context &Ctx, PathRef Path, ParsedAST *AST);
+  void update(const Context &Ctx, PathRef Path, ParsedAST *AST);
 
-  bool fuzzyFind(Context &Ctx, const FuzzyFindRequest &Req,
+  bool fuzzyFind(const Context &Ctx, const FuzzyFindRequest &Req,
                  std::function<void(const Symbol &)> Callback) const override;
 
 private:
   FileSymbols FSymbols;
   MemIndex Index;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_FILEINDEX_H

clang-tools-extra/trunk/clangd/index/FileIndex.cpp

auto Snap = std::make_shared<Snapshot>();
     }
   }
   auto *Pointers = &Snap->Pointers;
   // Use aliasing constructor to keep the snapshot alive along with the
   // pointers.
   return {std::move(Snap), Pointers};
 }
 
-void FileIndex::update(Context &Ctx, PathRef Path, ParsedAST *AST) {
+void FileIndex::update(const Context &Ctx, PathRef Path, ParsedAST *AST) {
   if (!AST) {
     FSymbols.update(Path, nullptr);
   } else {
     auto Slab = indexAST(AST->getASTContext(), AST->getTopLevelDecls());
     FSymbols.update(Path, std::move(Slab));
   }
   auto Symbols = FSymbols.allSymbols();
   Index.build(std::move(Symbols));
 }
 
-bool FileIndex::fuzzyFind(Context &Ctx, const FuzzyFindRequest &Req,
+bool FileIndex::fuzzyFind(const Context &Ctx, const FuzzyFindRequest &Req,
                           std::function<void(const Symbol &)> Callback) const {
   return Index.fuzzyFind(Ctx, Req, std::move(Callback));
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/clangd/index/Index.h

public:
   virtual ~SymbolIndex() = default;
 
   /// \brief Matches symbols in the index fuzzily and applies \p Callback on
   /// each matched symbol before returning.
   ///
   /// Returns true if the result list is complete, false if it was truncated due
   /// to MaxCandidateCount
   virtual bool
-  fuzzyFind(Context &Ctx, const FuzzyFindRequest &Req,
+  fuzzyFind(const Context &Ctx, const FuzzyFindRequest &Req,
             std::function<void(const Symbol &)> Callback) const = 0;
 
   // FIXME: add interfaces for more index use cases:
   //  - Symbol getSymbolInfo(SymbolID);
   //  - getAllOccurrences(SymbolID);
 };
 
 } // namespace clangd

clang-tools-extra/trunk/clangd/index/MemIndex.h

 /// \brief This implements an index for a (relatively small) set of symbols that
 /// can be easily managed in memory.
 class MemIndex : public SymbolIndex {
 public:
   /// \brief (Re-)Build index for `Symbols`. All symbol pointers must remain
   /// accessible as long as `Symbols` is kept alive.
   void build(std::shared_ptr<std::vector<const Symbol *>> Symbols);
 
-  bool fuzzyFind(Context &Ctx, const FuzzyFindRequest &Req,
+  bool fuzzyFind(const Context &Ctx, const FuzzyFindRequest &Req,
                  std::function<void(const Symbol &)> Callback) const override;
 
 private:
   std::shared_ptr<std::vector<const Symbol *>> Symbols;
   // Index is a set of symbols that are deduplicated by symbol IDs.
   // FIXME: build smarter index structure.
   llvm::DenseMap<SymbolID, const Symbol *> Index;
   mutable std::mutex Mutex;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_MEMINDEX_H

clang-tools-extra/trunk/clangd/index/MemIndex.cpp

void MemIndex::build(std::shared_ptr<std::vector<const Symbol *>> Syms) {
   // Swap out the old symbols and index.
   {
     std::lock_guard<std::mutex> Lock(Mutex);
     Index = std::move(TempIndex);
     Symbols = std::move(Syms); // Relase old symbols.
   }
 }
 
-bool MemIndex::fuzzyFind(Context &Ctx, const FuzzyFindRequest &Req,
+bool MemIndex::fuzzyFind(const Context &Ctx, const FuzzyFindRequest &Req,
                          std::function<void(const Symbol &)> Callback) const {
   assert(!StringRef(Req.Query).contains("::") &&
          "There must be no :: in query.");
 
   unsigned Matched = 0;
   {
     std::lock_guard<std::mutex> Lock(Mutex);
     for (const auto Pair : Index) {

clang-tools-extra/trunk/unittests/clangd/CodeCompleteTests.cpp

 //===-- CodeCompleteTests.cpp -----------------------------------*- 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 "Compiler.h"
 #include "Context.h"
 #include "Matchers.h"
 #include "Protocol.h"
 #include "SourceCode.h"
 #include "TestFS.h"
+#include "index/MemIndex.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);
StringWithPos parseTextMarker(StringRef Text) {
   auto MarkerPos = offsetToPosition(WithoutMarker, MarkerOffset);
   return {std::move(WithoutMarker), MarkerPos};
 }
 
 // GMock helpers for matching completion items.
 MATCHER_P(Named, Name, "") { return arg.insertText == Name; }
 MATCHER_P(Labeled, Label, "") { return arg.label == Label; }
 MATCHER_P(Kind, K, "") { return arg.kind == K; }
+MATCHER_P(Filter, F, "") { return arg.filterText == F; }
 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;
 }
TEST(SignatureHelpTest, ActiveArg) {
   )cpp");
   EXPECT_THAT(Results.signatures,
               ElementsAre(Sig("baz(int a, int b, int c) -> int",
                               {"int a", "int b", "int c"})));
   EXPECT_EQ(0, Results.activeSignature);
   EXPECT_EQ(1, Results.activeParameter);
 }
 
+std::unique_ptr<SymbolIndex> simpleIndexFromSymbols(
+    std::vector<std::pair<std::string, index::SymbolKind>> Symbols) {
+  auto I = llvm::make_unique<MemIndex>();
+  struct Snapshot {
+    SymbolSlab Slab;
+    std::vector<const Symbol *> Pointers;
+  };
+  auto Snap = std::make_shared<Snapshot>();
+  for (const auto &Pair : Symbols) {
+    Symbol Sym;
+    Sym.ID = SymbolID(Pair.first);
+    llvm::StringRef QName = Pair.first;
+    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);
+    }
+    Sym.SymInfo.Kind = Pair.second;
+    Snap->Slab.insert(std::move(Sym));
+  }
+  for (auto &Iter : Snap->Slab)
+    Snap->Pointers.push_back(&Iter.second);
+  auto S = std::shared_ptr<std::vector<const Symbol *>>(std::move(Snap),
+                                                        &Snap->Pointers);
+  I->build(std::move(S));
+  return I;
+}
+
+TEST(CompletionTest, NoIndex) {
+  clangd::CodeCompleteOptions Opts;
+  Opts.Index = nullptr;
+
+  auto Results = completions(R"cpp(
+      namespace ns { class No {}; }
+      void f() { ns::^ }
+  )cpp",
+                             Opts);
+  EXPECT_THAT(Results.items, Has("No"));
+}
+
+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();
+
+  auto Results = completions(R"cpp(
+      namespace ns { class No {}; }
+      void f() { ns::^ }
+  )cpp",
+                             Opts);
+  EXPECT_THAT(Results.items, Has("XYZ", CompletionItemKind::Class));
+  EXPECT_THAT(Results.items, Has("foo", CompletionItemKind::Function));
+  EXPECT_THAT(Results.items, Not(Has("No")));
+}
+
+TEST(CompletionTest, IndexBasedWithFilter) {
+  clangd::CodeCompleteOptions Opts;
+  auto I = simpleIndexFromSymbols({{"ns::XYZ", index::SymbolKind::Class},
+                                   {"ns::foo", index::SymbolKind::Function}});
+  Opts.Index = I.get();
+
+  auto Results = completions(R"cpp(
+      void f() { ns::x^ }
+  )cpp",
+                             Opts);
+  EXPECT_THAT(Results.items, Contains(AllOf(Named("XYZ"), Filter("x"))));
+  EXPECT_THAT(Results.items, Not(Has("foo")));
+}
+
+TEST(CompletionTest, GlobalQualified) {
+  clangd::CodeCompleteOptions Opts;
+  auto I = simpleIndexFromSymbols({{"XYZ", index::SymbolKind::Class}});
+  Opts.Index = I.get();
+
+  auto Results = completions(R"cpp(
+      void f() { ::^ }
+  )cpp",
+                             Opts);
+  EXPECT_THAT(Results.items, Has("XYZ", CompletionItemKind::Class));
+}
+
+TEST(CompletionTest, FullyQualifiedScope) {
+  clangd::CodeCompleteOptions Opts;
+  auto I = simpleIndexFromSymbols({{"ns::XYZ", index::SymbolKind::Class}});
+  Opts.Index = I.get();
+
+  auto Results = completions(R"cpp(
+      void f() { ::ns::^ }
+  )cpp",
+                             Opts);
+  EXPECT_THAT(Results.items, Has("XYZ", CompletionItemKind::Class));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/unittests/clangd/IndexTests.cpp

TEST(MemIndexTest, MatchQualifiedNamesWithoutSpecificScope) {
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::xyz", "b::yz", "yz"));
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithGlobalScope) {
   MemIndex I;
   I.build(generateSymbols({"a::xyz", "b::yz", "yz"}));
   FuzzyFindRequest Req;
   Req.Query = "y";
-  Req.Scopes.push_back("");
+  Req.Scopes = {""};
   auto Matches = match(I, Req);
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("yz"));
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithOneScope) {
   MemIndex I;
   I.build(generateSymbols({"a::xyz", "a::yy", "a::xz", "b::yz", "yz"}));
   FuzzyFindRequest Req;
   Req.Query = "y";
-  Req.Scopes.push_back("a");
+  Req.Scopes = {"a"};
   auto Matches = match(I, Req);
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::xyz", "a::yy"));
 }
 
 TEST(MemIndexTest, MatchQualifiedNamesWithMultipleScopes) {
   MemIndex I;
   I.build(generateSymbols({"a::xyz", "a::yy", "a::xz", "b::yz", "yz"}));
   FuzzyFindRequest Req;
   Req.Query = "y";
-  Req.Scopes.push_back("a");
-  Req.Scopes.push_back("b");
+  Req.Scopes = {"a", "b"};
   auto Matches = match(I, Req);
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::xyz", "a::yy", "b::yz"));
 }
 
 TEST(MemIndexTest, NoMatchNestedScopes) {
   MemIndex I;
   I.build(generateSymbols({"a::xyz", "a::b::yy"}));
   FuzzyFindRequest Req;
   Req.Query = "y";
-  Req.Scopes.push_back("a");
+  Req.Scopes = {"a"};
   auto Matches = match(I, Req);
   EXPECT_THAT(match(I, Req), UnorderedElementsAre("a::xyz"));
 }
 
 } // namespace
 } // namespace clangd
 } // namespace clang