[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

15

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

35

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

clangd/Position.h

1

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

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

LSP has struct (not in protocol yet)

fine for these to be FIXME

111

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

conversionfunction might be rather operator, not sure

121

LSP has enum constant, not in protocol.h yet

131

destructor seems more like an operator or method

280

qualified

282

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

283

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

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

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

310

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

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

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

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

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

373

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

the partial identifier that is being completed, without qualifiers

380

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–401

nit: auto seems a lot easier to read here?

[ilya-biryukov]

Here are a few more comments.

clangd/CodeComplete.cpp

329

NIT: FIXME(ioeric)?

334

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

380

NIT: FIXME(ioeric)?

847

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

clangd/CodeComplete.h

64

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

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

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

283

This is moved to a standalone function extractCompletionScope.

310

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

334

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

NameToComplete sounds reasonable.

847

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

clangd/CodeComplete.h

64

@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

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

clangd/CodeComplete.h

64

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

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

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

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

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

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 :)

clangd/CMakeLists.txt

add_clang_library(clangDaemon
   Context.cpp
   Compiler.cpp
   DraftStore.cpp
   FuzzyMatch.cpp
   GlobalCompilationDatabase.cpp
   JSONExpr.cpp
   JSONRPCDispatcher.cpp
   Logger.cpp
+  Position.cpp
   Protocol.cpp
   ProtocolHandlers.cpp
   Trace.cpp
   index/FileSymbols.cpp
   index/Index.cpp
   index/MemIndex.cpp
   index/SymbolCollector.cpp
   index/SymbolYAML.cpp

clangd/ClangdLSPServer.cpp

 //===--- ClangdLSPServer.cpp - LSP server ------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===---------------------------------------------------------------------===//
 
 #include "ClangdLSPServer.h"
 #include "JSONRPCDispatcher.h"
+#include "Position.h"
 #include "llvm/Support/FormatVariadic.h"
 
 using namespace clang::clangd;
 using namespace clang;
 
 namespace {
 
 TextEdit replacementToEdit(StringRef Code, const tooling::Replacement &R) {

clangd/ClangdServer.h

 #include <mutex>
 #include <string>
 #include <thread>
 #include <type_traits>
 #include <utility>
 
 namespace clang {
 class PCHContainerOperations;
-
 namespace clangd {
 
-/// Turn a [line, column] pair into an offset in Code.
-size_t positionToOffset(StringRef Code, Position P);
-
-/// Turn an offset in Code into a [line, column] pair.
-Position offsetToPosition(StringRef Code, size_t Offset);
-
 /// A tag supplied by the FileSytemProvider.
 typedef std::string VFSTag;
 
 /// A value of an arbitrary type and VFSTag that was supplied by the
 /// FileSystemProvider when this value was computed.
 template <class T> class Tagged {
 public:
   // MSVC requires future<> arguments to be default-constructible.

clangd/ClangdServer.cpp

 //===--- ClangdServer.cpp - Main clangd server code --------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===-------------------------------------------------------------------===//
 
 #include "ClangdServer.h"
+#include "Position.h"
 #include "clang/Format/Format.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "clang/Tooling/Refactoring/RefactoringResultConsumer.h"
 #include "clang/Tooling/Refactoring/Rename/RenamingAction.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/Support/Errc.h"
void handle(tooling::AtomicChanges SourceReplacements) override {
     Result = std::move(SourceReplacements);
   }
 
   Optional<Expected<tooling::AtomicChanges>> Result;
 };
 
 } // namespace
 
-size_t clangd::positionToOffset(StringRef Code, Position P) {
-  size_t Offset = 0;
-  for (int I = 0; I != P.line; ++I) {
-    // FIXME: \r\n
-    // FIXME: UTF-8
-    size_t F = Code.find('\n', Offset);
-    if (F == StringRef::npos)
-      return 0; // FIXME: Is this reasonable?
-    Offset = F + 1;
-  }
-  return (Offset == 0 ? 0 : (Offset - 1)) + P.character;
-}
-
-/// Turn an offset in Code into a [line, column] pair.
-Position clangd::offsetToPosition(StringRef Code, size_t Offset) {
-  StringRef JustBefore = Code.substr(0, Offset);
-  // FIXME: \r\n
-  // FIXME: UTF-8
-  int Lines = JustBefore.count('\n');
-  int Cols = JustBefore.size() - JustBefore.rfind('\n') - 1;
-  return {Lines, Cols};
-}
-
 Tagged<IntrusiveRefCntPtr<vfs::FileSystem>>
 RealFileSystemProvider::getTaggedFileSystem(PathRef File) {
   return make_tagged(vfs::getRealFileSystem(), VFSTag());
 }
 
 unsigned clangd::getDefaultAsyncThreadsCount() {
   unsigned HardwareConcurrency = std::thread::hardware_concurrency();
   // C++ standard says that hardware_concurrency()

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.
+  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,

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 "Position.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 {
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 getKindOfSymbol(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;
+  case SK::Struct:
+  case SK::Class:
+  case SK::Protocol:
+  case SK::Extension:
+  case SK::Union:
+    return CompletionItemKind::Class;
+  case SK::TypeAlias:
+  case SK::Using:
+    return CompletionItemKind::Reference;
+  case SK::Function:
+  case SK::ConversionFunction:
+    return CompletionItemKind::Function;
+  case SK::Variable:
+  case SK::Parameter:
+    return CompletionItemKind::Variable;
+  case SK::Field:
+    return CompletionItemKind::Field;
+  case SK::EnumConstant:
+    return CompletionItemKind::Value;
+  case SK::InstanceMethod:
+  case SK::ClassMethod:
+  case SK::StaticMethod:
+    return CompletionItemKind::Method;
+  case SK::InstanceProperty:
+  case SK::ClassProperty:
+  case SK::StaticProperty:
+    return CompletionItemKind::Property;
+  case SK::Constructor:
+  case SK::Destructor:
+    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 qualfiied-id code
+/// completion (e.g. "ns::ab?").
+struct ScopeSpecifierInfo {
+  static ScopeSpecifierInfo create(Sema &S, const CXXScopeSpec &SS) {
+    ScopeSpecifierInfo Info;
+    auto &SM = S.getSourceManager();
+    auto SpecifierRange = SS.getRange();
+    Info.WrittenSpecifier =
+        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.SpecifiedContextName = NS->getQualifiedNameAsString();
+      } else if (auto *TU = llvm::dyn_cast<TranslationUnitDecl>(DC)) {
+        Info.SpecifiedContextName = "::";
+        // Sema does not include the suffix "::" in the range of SS, so we add
+        // it back here.
+        Info.WrittenSpecifier = "::";
+      }
+    }
+
+    Info.SpecifierBeginOffset = SM.getFileOffset(SpecifierRange.getBegin());
+    Info.SpecifierEndOffset = SM.getFileOffset(SpecifierRange.getEnd());
+    return Info;
+  }
+
+  // The range of scope specifier as written. This does not include the
+  // filter text following the specifier. For example, for completion at
+  // "ns::ab?", the range will be "ns".
+  unsigned int SpecifierBeginOffset;
+  unsigned int SpecifierEndOffset;
+
+  // The scope specifier as written. For example, for completion "ns::ab?",
+  // the written scope specifier is "ns".
+  std::string WrittenSpecifier;
+  // 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 SpecifiedContextName;
+};
+
+CompletionItem symbolToCompletionItem(const Symbol &Sym, llvm::StringRef Code,
+                                      const ScopeSpecifierInfo &SSInfo) {
+  CompletionItem Item;
+  bool FullyQualified =
+      llvm::StringRef(SSInfo.WrittenSpecifier).startswith("::");
+  if (FullyQualified)
+    Item.label = "::";
+  // FIXME: use more symbol information (e.g. documentation, label) to populate
+  // the completion item.
+  Item.label += Sym.QualifiedName;
+  Item.kind = getKindOfSymbol(Sym.SymInfo.Kind);
+  Item.insertTextFormat = InsertTextFormat::PlainText;
+  // FIXME: sort symbols appropriately.
+  Item.sortText = "";
+
+  TextEdit Edit;
+  Edit.newText =
+      FullyQualified ? ("::" + Sym.QualifiedName) : Sym.QualifiedName;
+  Edit.range.start =
+      offsetToPosition(Code, SSInfo.SpecifierBeginOffset);
+  Edit.range.end = offsetToPosition(Code, SSInfo.SpecifierEndOffset);
+  Item.textEdit = std::move(Edit);
+  return Item;
+}
+
+void qualifiedIdCompletionWithIndex(const Context &Ctx,
+                                    const SymbolIndex &Index,
+                                    llvm::StringRef Code,
+                                    const ScopeSpecifierInfo &SSInfo,
+                                    llvm::StringRef Filter,
+                                    CompletionList *Items) {
+  FuzzyFindRequest Req;
+  Req.Query = SSInfo.SpecifiedContextName.empty() ? SSInfo.WrittenSpecifier
+                                                  : SSInfo.SpecifiedContextName;
+  if (!llvm::StringRef(Req.Query).endswith("::"))
+    Req.Query += "::";
+  // FIXME: for now we simply cancatenate specifier with the typed filter. We
+  // might want to fix the specifier prefix if it is a recognized context (e.g.
+  // a known namespace in the AST).
+  if (!Filter.empty())
+    Req.Query += Filter;
+
+  // Global qualifier means all symbols.
+  if (Req.Query == "::")
+    Req.Query = "";
+
+  Items->isIncomplete = !Index.fuzzyFind(Ctx, Req, [&](const Symbol &Sym) {
+    Items->items.push_back(symbolToCompletionItem(Sym, Code, SSInfo));
+  });
+}
+
+/// brief Collects information about an invocation of sema code completion.
+struct SemaCompletionInfo {
+  /// Code completion filter.
+  std::string Filter;
+
+  /// This is set if the completion is for qualified IDs, e.g. "abc::x^".
+  llvm::Optional<ScopeSpecifierInfo> SSInfo;
+  // FIXME: add more information for other completion cases that we care about.
+  // For example, non-qualified id completion.
+};
+
 class CompletionItemsCollector : public CodeCompleteConsumer {
 public:
   CompletionItemsCollector(const CodeCompleteOptions &CodeCompleteOpts,
-                           CompletionList &Items)
+                           CompletionList &Items, SemaCompletionInfo &SCInfo)
       : CodeCompleteConsumer(CodeCompleteOpts.getClangCompleteOpts(),
                              /*OutputIsBinary=*/false),
         ClangdOpts(CodeCompleteOpts), Items(Items),
         Allocator(std::make_shared<clang::GlobalCodeCompletionAllocator>()),
-        CCTUInfo(Allocator) {}
+        CCTUInfo(Allocator), SCInfo(SCInfo) {}
 
   void ProcessCodeCompleteResults(Sema &S, CodeCompletionContext Context,
                                   CodeCompletionResult *Results,
                                   unsigned NumResults) override final {
-    StringRef Filter = S.getPreprocessor().getCodeCompletionFilter();
+    if (llvm::Optional<const CXXScopeSpec *> SS =
+            Context.getCXXScopeSpecifier())
+      SCInfo.SSInfo = ScopeSpecifierInfo::create(S, **SS);
+
+    SCInfo.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 (!SCInfo.Filter.empty() &&
+          !fuzzyMatch(S, Context, SCInfo.Filter, Result))
         continue;
       Candidates.emplace(Result);
       if (ClangdOpts.Limit && Candidates.size() > ClangdOpts.Limit) {
         Candidates.pop();
         Items.isIncomplete = true;
       }
     }
     while (!Candidates.empty()) {
private:
 
   virtual void ProcessChunks(const CodeCompletionString &CCS,
                              CompletionItem &Item) const = 0;
 
   CodeCompleteOptions ClangdOpts;
   CompletionList &Items;
   std::shared_ptr<clang::GlobalCodeCompletionAllocator> Allocator;
   CodeCompletionTUInfo CCTUInfo;
-
+  SemaCompletionInfo &SCInfo;
 }; // 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,
+                                    SemaCompletionInfo &SCInfo)
+      : CompletionItemsCollector(CodeCompleteOpts, Items, SCInfo) {}
 
 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,
+                                  SemaCompletionInfo &SCInfo)
+      : CompletionItemsCollector(CodeCompleteOpts, Items, SCInfo) {}
 
 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.

 
 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;
+  SemaCompletionInfo SCInfo;
   if (Opts.EnableSnippets) {
-    Consumer =
-        llvm::make_unique<SnippetCompletionItemsCollector>(Opts, Results);
+    Consumer = llvm::make_unique<SnippetCompletionItemsCollector>(Opts, Results,
+                                                                  SCInfo);
   } else {
-    Consumer =
-        llvm::make_unique<PlainTextCompletionItemsCollector>(Opts, Results);
+    Consumer = llvm::make_unique<PlainTextCompletionItemsCollector>(
+        Opts, Results, SCInfo);
   }
   invokeCodeComplete(Ctx, std::move(Consumer), Opts.getClangCompleteOpts(),
                      FileName, Command, Preamble, Contents, Pos, std::move(VFS),
                      std::move(PCHs));
+  if (Opts.Index && SCInfo.SSInfo) {
+    // FIXME: log warning with logger if sema code completion have collected
+    // results.
+    Results.items.clear();
+    qualifiedIdCompletionWithIndex(Ctx, *Opts.Index, Contents, *SCInfo.SSInfo,
+                                   SCInfo.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,

clangd/Position.h

+//===--- Position.h - Positions in code. -------------------------*- C++-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_POSITION_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_POSITION_H
+
+#include "Protocol.h"
+
+namespace clang {
+namespace clangd {
+
+/// Turn a [line, column] pair into an offset in Code.
+size_t positionToOffset(llvm::StringRef Code, Position P);
+
+/// Turn an offset in Code into a [line, column] pair.
+Position offsetToPosition(llvm::StringRef Code, size_t Offset);
+
+} // namespace clangd
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_POSITION_H

clangd/Position.cpp

+//===--- Position.cpp - Positions in code. -------------------------*- +-*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Position.h"
+
+namespace clang {
+namespace clangd {
+
+size_t positionToOffset(llvm::StringRef Code, Position P) {
+  size_t Offset = 0;
+  for (int I = 0; I != P.line; ++I) {
+    // FIXME: \r\n
+    // FIXME: UTF-8
+    size_t F = Code.find('\n', Offset);
+    if (F == llvm::StringRef::npos)
+      return 0; // FIXME: Is this reasonable?
+    Offset = F + 1;
+  }
+  return (Offset == 0 ? 0 : (Offset - 1)) + P.character;
+}
+
+/// Turn an offset in Code into a [line, column] pair.
+Position offsetToPosition(llvm::StringRef Code, size_t Offset) {
+  llvm::StringRef JustBefore = Code.substr(0, Offset);
+  // FIXME: \r\n
+  // FIXME: UTF-8
+  int Lines = JustBefore.count('\n');
+  int Cols = JustBefore.size() - JustBefore.rfind('\n') - 1;
+  return {Lines, Cols};
+}
+
+
+} // namespace clangd
+} // namespace clang

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

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

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 {
   std::string LoweredQuery = llvm::StringRef(Req.Query).lower();
   unsigned Matched = 0;
   {
     std::lock_guard<std::mutex> Lock(Mutex);
     for (const auto Pair : Index) {
       const Symbol *Sym = Pair.second;
       // Find all symbols that contain the query, igoring cases.

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 "Position.h"
 #include "Protocol.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.
 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_P(Edit, Text, "") {
+  return arg.textEdit.hasValue() && arg.textEdit.getValue().newText == Text;
+}
+MATCHER_P2(Edit, Text, Range, "") {
+  return arg.textEdit.hasValue() && arg.textEdit.getValue().newText == Text &&
+         arg.textEdit.getValue().range == Range;
+}
 // Shorthand for Contains(Named(Name)).
 Matcher<const std::vector<CompletionItem> &> Has(std::string Name) {
   return Contains(Named(std::move(Name)));
 }
 Matcher<const std::vector<CompletionItem> &> Has(std::string Name,
                                                  CompletionItemKind K) {
   return Contains(AllOf(Named(std::move(Name)), Kind(K)));
 }
+// Shorthand for Contains(Edit(Name)).
+Matcher<const std::vector<CompletionItem> &> HasEdit(std::string Name) {
+  return Contains(Edit(std::move(Name)));
+}
+Matcher<const std::vector<CompletionItem> &> HasEdit(std::string Name,
+                                                     CompletionItemKind K) {
+  return Contains(AllOf(Edit(std::move(Name)), Kind(K)));
+}
+Matcher<const std::vector<CompletionItem> &>
+HasEditWithRange(std::string Name, Range R) {
+  return Contains(Edit(std::move(Name), std::move(R)));
+}
 MATCHER(IsDocumented, "") { return !arg.documentation.empty(); }
 
 CompletionList completions(StringRef Text,
                            clangd::CodeCompleteOptions Opts = {}) {
   MockFSProvider FS;
   MockCompilationDatabase CDB;
   IgnoreDiagnostics DiagConsumer;
   ClangdServer Server(CDB, DiagConsumer, FS, getDefaultAsyncThreadsCount(),
TEST(CompletionTest, Kinds) {
 
   clangd::CodeCompleteOptions Opts;
   Opts.EnableSnippets = true; // Needed for code patterns.
 
   Results = completions("nam^");
   EXPECT_THAT(Results.items, Has("namespace", CompletionItemKind::Snippet));
 }
 
+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);
+    Sym.QualifiedName = Pair.first;
+    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},
+                              {"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, HasEdit("ns::XYZ", CompletionItemKind::Class));
+  EXPECT_THAT(Results.items, HasEdit("ns::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, HasEdit("ns::XYZ", CompletionItemKind::Class));
+  EXPECT_THAT(Results.items, Not(HasEdit("ns::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, HasEdit("::XYZ", CompletionItemKind::Class));
+}
+
+TEST(CompletionTest, EditRangeGlobal) {
+  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, HasEditWithRange("::XYZ", {{1, 17}, {1, 17}}));
+}
+
+TEST(CompletionTest, EditRangeQualified) {
+  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);
+  // "::" is not in the buffer.
+  EXPECT_THAT(Results.items, HasEditWithRange("ns::XYZ", {{1, 17}, {1, 19}}));
+}
+
+TEST(CompletionTest, EditRangeQualifiedWithFilter) {
+  clangd::CodeCompleteOptions Opts;
+  auto I = simpleIndexFromSymbols({{"ns::XYZ", index::SymbolKind::Class}});
+  Opts.Index = I.get();
+
+  auto Results = completions(R"cpp(
+      void f() { ns::X^ }
+  )cpp",
+                             Opts);
+  // Filter is not in the buffer.
+  EXPECT_THAT(Results.items, HasEditWithRange("ns::XYZ", {{1, 17}, {1, 19}}));
+}
+
+TEST(CompletionTest, RecognizedSpecifierAndRange) {
+  clangd::CodeCompleteOptions Opts;
+  auto I = simpleIndexFromSymbols({{"ns::XYZ", index::SymbolKind::Class}});
+  Opts.Index = I.get();
+
+  auto Results = completions(R"cpp(
+      namespace ns {}
+      void f() { ns::X^ }
+  )cpp",
+                             Opts);
+  // Filter is not in the buffer.
+  EXPECT_THAT(Results.items, HasEditWithRange("ns::XYZ", {{2, 17}, {2, 19}}));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang