[clangd] Use identifiers in file as completion candidates when build is not ready.

Summary:
o Lex the code to get the identifiers and put them into a "symbol" index.
o Adds a new completion mode without compilation/sema into code completion workflow.
o Make IncludeInserter work even when no compile command is present, by avoiding
inserting non-verbatim headers.

Reviewers: sammccall

Reviewed By: sammccall

Subscribers: ilya-biryukov, MaskRay, jkorous, arphaman, kadircet, jdoerfert, cfe-commits

Tags: #clang

Differential Revision: https://reviews.llvm.org/D60126

llvm-svn: 358159

14 files changed, 299 insertions, 85 deletions

diff --git a/clang-tools-extra/clangd/ClangdServer.cpp b/clang-tools-extra/clangd/ClangdServer.cpp
index b2b11aa9481..345c8b665ed 100644
--- a/clang-tools-extra/clangd/ClangdServer.cpp
+++ b/clang-tools-extra/clangd/ClangdServer.cpp
@@ -23,7 +23,6 @@
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Lex/Preprocessor.h"
-#include "clang/Sema/CodeCompleteConsumer.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "clang/Tooling/Refactoring/RefactoringResultConsumer.h"
@@ -187,28 +186,23 @@ void ClangdServer::codeComplete(PathRef File, Position Pos,
       return CB(IP.takeError());
     if (isCancelled())
       return CB(llvm::make_error<CancelledError>());
-    if (!IP->Preamble) {
-      vlog("File {0} is not ready for code completion. Enter fallback mode.",
-           File);
-      CodeCompleteResult CCR;
-      CCR.Context = CodeCompletionContext::CCC_Recovery;
-
-      // FIXME: perform simple completion e.g. using identifiers in the current
-      // file and symbols in the index.
-      // FIXME: let clients know that we've entered fallback mode.
-
-      return CB(std::move(CCR));
-    }
 
     llvm::Optional<SpeculativeFuzzyFind> SpecFuzzyFind;
-    if (CodeCompleteOpts.Index && CodeCompleteOpts.SpeculativeIndexRequest) {
-      SpecFuzzyFind.emplace();
-      {
-        std::lock_guard<std::mutex> Lock(CachedCompletionFuzzyFindRequestMutex);
-        SpecFuzzyFind->CachedReq = CachedCompletionFuzzyFindRequestByFile[File];
+    if (!IP->Preamble) {
+      // No speculation in Fallback mode, as it's supposed to be much faster
+      // without compiling.
+      vlog("Build for file {0} is not ready. Enter fallback mode.", File);
+    } else {
+      if (CodeCompleteOpts.Index && CodeCompleteOpts.SpeculativeIndexRequest) {
+        SpecFuzzyFind.emplace();
+        {
+          std::lock_guard<std::mutex> Lock(
+              CachedCompletionFuzzyFindRequestMutex);
+          SpecFuzzyFind->CachedReq =
+              CachedCompletionFuzzyFindRequestByFile[File];
+        }
       }
     }
-
     // FIXME(ibiryukov): even if Preamble is non-null, we may want to check
     // both the old and the new version in case only one of them matches.
     CodeCompleteResult Result = clangd::codeComplete(
diff --git a/clang-tools-extra/clangd/ClangdUnit.cpp b/clang-tools-extra/clangd/ClangdUnit.cpp
index 7c611877595..473edb6ff2f 100644
--- a/clang-tools-extra/clangd/ClangdUnit.cpp
+++ b/clang-tools-extra/clangd/ClangdUnit.cpp
@@ -311,7 +311,7 @@ ParsedAST::build(std::unique_ptr<CompilerInvocation> CI,
     auto Style = getFormatStyleForFile(MainInput.getFile(), Content, VFS.get());
     auto Inserter = std::make_shared<IncludeInserter>(
         MainInput.getFile(), Content, Style, BuildDir.get(),
-        Clang->getPreprocessor().getHeaderSearchInfo());
+        &Clang->getPreprocessor().getHeaderSearchInfo());
     if (Preamble) {
       for (const auto &Inc : Preamble->Includes.MainFileIncludes)
         Inserter->addExisting(Inc);
diff --git a/clang-tools-extra/clangd/CodeComplete.cpp b/clang-tools-extra/clangd/CodeComplete.cpp
index 55154f92a01..968e9407103 100644
--- a/clang-tools-extra/clangd/CodeComplete.cpp
+++ b/clang-tools-extra/clangd/CodeComplete.cpp
@@ -35,6 +35,7 @@
 #include "URI.h"
 #include "index/Index.h"
 #include "index/Symbol.h"
+#include "index/SymbolOrigin.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/Basic/CharInfo.h"
@@ -181,6 +182,12 @@ std::string getOptionalParameters(const CodeCompletionString &CCS,
   return Result;
 }
 
+// Identifier code completion result.
+struct RawIdentifier {
+  llvm::StringRef Name;
+  unsigned References; // # of usages in file.
+};
+
 /// 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 {
@@ -188,6 +195,7 @@ struct CompletionCandidate {
   // We may have a result from Sema, from the index, or both.
   const CodeCompletionResult *SemaResult = nullptr;
   const Symbol *IndexResult = nullptr;
+  const RawIdentifier *IdentifierResult = nullptr;
   llvm::SmallVector<llvm::StringRef, 1> RankedIncludeHeaders;
 
   // Returns a token identifying the overload set this is part of.
@@ -216,17 +224,20 @@ struct CompletionCandidate {
         return 0;
       }
     }
-    assert(SemaResult);
-    // We need to make sure we're consistent with the IndexResult case!
-    const NamedDecl *D = SemaResult->Declaration;
-    if (!D || !D->isFunctionOrFunctionTemplate())
-      return 0;
-    {
-      llvm::raw_svector_ostream OS(Scratch);
-      D->printQualifiedName(OS);
+    if (SemaResult) {
+      // We need to make sure we're consistent with the IndexResult case!
+      const NamedDecl *D = SemaResult->Declaration;
+      if (!D || !D->isFunctionOrFunctionTemplate())
+        return 0;
+      {
+        llvm::raw_svector_ostream OS(Scratch);
+        D->printQualifiedName(OS);
+      }
+      return llvm::hash_combine(Scratch,
+                                headerToInsertIfAllowed(Opts).getValueOr(""));
     }
-    return llvm::hash_combine(Scratch,
-                              headerToInsertIfAllowed(Opts).getValueOr(""));
+    assert(IdentifierResult);
+    return 0;
   }
 
   // The best header to include if include insertion is allowed.
@@ -267,7 +278,7 @@ struct ScoredBundleGreater {
 // computed from the first candidate, in the constructor.
 // Others vary per candidate, so add() must be called for remaining candidates.
 struct CodeCompletionBuilder {
-  CodeCompletionBuilder(ASTContext &ASTCtx, const CompletionCandidate &C,
+  CodeCompletionBuilder(ASTContext *ASTCtx, const CompletionCandidate &C,
                         CodeCompletionString *SemaCCS,
                         llvm::ArrayRef<std::string> QueryScopes,
                         const IncludeInserter &Includes,
@@ -278,6 +289,7 @@ struct CodeCompletionBuilder {
         EnableFunctionArgSnippets(Opts.EnableFunctionArgSnippets) {
     add(C, SemaCCS);
     if (C.SemaResult) {
+      assert(ASTCtx);
       Completion.Origin |= SymbolOrigin::AST;
       Completion.Name = llvm::StringRef(SemaCCS->getTypedText());
       if (Completion.Scope.empty()) {
@@ -296,8 +308,8 @@ struct CodeCompletionBuilder {
           Completion.Name.back() == '/')
         Completion.Kind = CompletionItemKind::Folder;
       for (const auto &FixIt : C.SemaResult->FixIts) {
-        Completion.FixIts.push_back(
-            toTextEdit(FixIt, ASTCtx.getSourceManager(), ASTCtx.getLangOpts()));
+        Completion.FixIts.push_back(toTextEdit(
+            FixIt, ASTCtx->getSourceManager(), ASTCtx->getLangOpts()));
       }
       llvm::sort(Completion.FixIts, [](const TextEdit &X, const TextEdit &Y) {
         return std::tie(X.range.start.line, X.range.start.character) <
@@ -328,6 +340,11 @@ struct CodeCompletionBuilder {
       }
       Completion.Deprecated |= (C.IndexResult->Flags & Symbol::Deprecated);
     }
+    if (C.IdentifierResult) {
+      Completion.Origin |= SymbolOrigin::Identifier;
+      Completion.Kind = CompletionItemKind::Text;
+      Completion.Name = C.IdentifierResult->Name;
+    }
 
     // Turn absolute path into a literal string that can be #included.
     auto Inserted = [&](llvm::StringRef Header)
@@ -382,7 +399,7 @@ struct CodeCompletionBuilder {
       if (C.IndexResult)
         Completion.Documentation = C.IndexResult->Documentation;
       else if (C.SemaResult)
-        Completion.Documentation = getDocComment(ASTCtx, *C.SemaResult,
+        Completion.Documentation = getDocComment(*ASTCtx, *C.SemaResult,
                                                  /*CommentsFromHeader=*/false);
     }
   }
@@ -477,7 +494,8 @@ private:
     return "(…)";
   }
 
-  ASTContext &ASTCtx;
+  // ASTCtx can be nullptr if not run with sema.
+  ASTContext *ASTCtx;
   CodeCompletion Completion;
   llvm::SmallVector<BundledEntry, 1> Bundled;
   bool ExtractDocumentation;
@@ -1155,10 +1173,13 @@ class CodeCompleteFlow {
 
   // Sema takes ownership of Recorder. Recorder is valid until Sema cleanup.
   CompletionRecorder *Recorder = nullptr;
-  int NSema = 0, NIndex = 0, NBoth = 0; // Counters for logging.
-  bool Incomplete = false;       // Would more be available with a higher limit?
+  CodeCompletionContext::Kind CCContextKind = CodeCompletionContext::CCC_Other;
+  // Counters for logging.
+  int NSema = 0, NIndex = 0, NSemaAndIndex = 0, NIdent = 0;
+  bool Incomplete = false; // Would more be available with a higher limit?
   CompletionPrefix HeuristicPrefix;
   llvm::Optional<FuzzyMatcher> Filter;  // Initialized once Sema runs.
+  Range ReplacedRange;
   std::vector<std::string> QueryScopes; // Initialized once Sema runs.
   // Initialized once QueryScopes is initialized, if there are scopes.
   llvm::Optional<ScopeDistance> ScopeProximity;
@@ -1200,6 +1221,7 @@ public:
     CodeCompleteResult Output;
     auto RecorderOwner = llvm::make_unique<CompletionRecorder>(Opts, [&]() {
       assert(Recorder && "Recorder is not set");
+      CCContextKind = Recorder->CCContext.getKind();
       auto Style = getFormatStyleForFile(
           SemaCCInput.FileName, SemaCCInput.Contents, SemaCCInput.VFS.get());
       // If preprocessor was run, inclusions from preprocessor callback should
@@ -1207,7 +1229,7 @@ public:
       Inserter.emplace(
           SemaCCInput.FileName, SemaCCInput.Contents, Style,
           SemaCCInput.Command.Directory,
-          Recorder->CCSema->getPreprocessor().getHeaderSearchInfo());
+          &Recorder->CCSema->getPreprocessor().getHeaderSearchInfo());
       for (const auto &Inc : Includes.MainFileIncludes)
         Inserter->addExisting(Inc);
 
@@ -1233,10 +1255,10 @@ public:
       Output = runWithSema();
       Inserter.reset(); // Make sure this doesn't out-live Clang.
       SPAN_ATTACH(Tracer, "sema_completion_kind",
-                  getCompletionKindString(Recorder->CCContext.getKind()));
+                  getCompletionKindString(CCContextKind));
       log("Code complete: sema context {0}, query scopes [{1}] (AnyScope={2}), "
           "expected type {3}",
-          getCompletionKindString(Recorder->CCContext.getKind()),
+          getCompletionKindString(CCContextKind),
           llvm::join(QueryScopes.begin(), QueryScopes.end(), ","), AllScopes,
           PreferredType ? Recorder->CCContext.getPreferredType().getAsString()
                         : "<none>");
@@ -1249,12 +1271,13 @@ public:
 
     SPAN_ATTACH(Tracer, "sema_results", NSema);
     SPAN_ATTACH(Tracer, "index_results", NIndex);
-    SPAN_ATTACH(Tracer, "merged_results", NBoth);
+    SPAN_ATTACH(Tracer, "merged_results", NSemaAndIndex);
+    SPAN_ATTACH(Tracer, "identifier_results", NIdent);
     SPAN_ATTACH(Tracer, "returned_results", int64_t(Output.Completions.size()));
     SPAN_ATTACH(Tracer, "incomplete", Output.HasMore);
     log("Code complete: {0} results from Sema, {1} from Index, "
-        "{2} matched, {3} returned{4}.",
-        NSema, NIndex, NBoth, Output.Completions.size(),
+        "{2} matched, {3} from identifiers, {4} returned{5}.",
+        NSema, NIndex, NSemaAndIndex, NIdent, Output.Completions.size(),
         Output.HasMore ? " (incomplete)" : "");
     assert(!Opts.Limit || Output.Completions.size() <= Opts.Limit);
     // We don't assert that isIncomplete means we hit a limit.
@@ -1262,26 +1285,68 @@ public:
     return Output;
   }
 
+  CodeCompleteResult
+  runWithoutSema(llvm::StringRef Content, size_t Offset,
+                 llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> VFS) && {
+    auto CCPrefix = guessCompletionPrefix(Content, Offset);
+    // Fill in fields normally set by runWithSema()
+    CCContextKind = CodeCompletionContext::CCC_Recovery;
+    Filter = FuzzyMatcher(CCPrefix.Name);
+    auto Pos = offsetToPosition(Content, Offset);
+    ReplacedRange.start = ReplacedRange.end = Pos;
+    ReplacedRange.start.character -= CCPrefix.Name.size();
+
+    llvm::StringMap<SourceParams> ProxSources;
+    ProxSources[FileName].Cost = 0;
+    FileProximity.emplace(ProxSources);
+
+    // FIXME: collect typed scope specifier and potentially parse the enclosing
+    // namespaces.
+    // FIXME: initialize ScopeProximity when scopes are added.
+
+    auto Style = getFormatStyleForFile(FileName, Content, VFS.get());
+    // This will only insert verbatim headers.
+    Inserter.emplace(FileName, Content, Style,
+                     /*BuildDir=*/"", /*HeaderSearchInfo=*/nullptr);
+
+    auto Identifiers = collectIdentifiers(Content, Style);
+    std::vector<RawIdentifier> IdentifierResults;
+    for (const auto &IDAndCount : Identifiers) {
+      RawIdentifier ID;
+      ID.Name = IDAndCount.first();
+      ID.References = IDAndCount.second;
+      // Avoid treating typed filter as an identifier.
+      if (ID.Name == CCPrefix.Name)
+        --ID.References;
+      if (ID.References > 0)
+        IdentifierResults.push_back(std::move(ID));
+    }
+
+    // FIXME: add results from Opts.Index when we know more about scopes (e.g.
+    // typed scope specifier).
+    return toCodeCompleteResult(mergeResults(
+        /*SemaResults=*/{}, /*IndexResults*/ {}, IdentifierResults));
+  }
+
 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.
   CodeCompleteResult runWithSema() {
     const auto &CodeCompletionRange = CharSourceRange::getCharRange(
         Recorder->CCSema->getPreprocessor().getCodeCompletionTokenRange());
-    Range TextEditRange;
     // When we are getting completions with an empty identifier, for example
     //    std::vector<int> asdf;
     //    asdf.^;
     // Then the range will be invalid and we will be doing insertion, use
     // current cursor position in such cases as range.
     if (CodeCompletionRange.isValid()) {
-      TextEditRange = halfOpenToRange(Recorder->CCSema->getSourceManager(),
+      ReplacedRange = halfOpenToRange(Recorder->CCSema->getSourceManager(),
                                       CodeCompletionRange);
     } else {
       const auto &Pos = sourceLocToPosition(
           Recorder->CCSema->getSourceManager(),
           Recorder->CCSema->getPreprocessor().getCodeCompletionLoc());
-      TextEditRange.start = TextEditRange.end = Pos;
+      ReplacedRange.start = ReplacedRange.end = Pos;
     }
     Filter = FuzzyMatcher(
         Recorder->CCSema->getPreprocessor().getCodeCompletionFilter());
@@ -1302,18 +1367,23 @@ private:
                             : SymbolSlab();
     trace::Span Tracer("Populate CodeCompleteResult");
     // Merge Sema and Index results, score them, and pick the winners.
-    auto Top = mergeResults(Recorder->Results, IndexResults);
+    auto Top =
+        mergeResults(Recorder->Results, IndexResults, /*Identifiers*/ {});
+    return toCodeCompleteResult(Top);
+  }
+
+  CodeCompleteResult
+  toCodeCompleteResult(const std::vector<ScoredBundle> &Scored) {
     CodeCompleteResult Output;
 
     // Convert the results to final form, assembling the expensive strings.
-    for (auto &C : Top) {
+    for (auto &C : Scored) {
       Output.Completions.push_back(toCodeCompletion(C.first));
       Output.Completions.back().Score = C.second;
-      Output.Completions.back().CompletionTokenRange = TextEditRange;
+      Output.Completions.back().CompletionTokenRange = ReplacedRange;
     }
     Output.HasMore = Incomplete;
-    Output.Context = Recorder->CCContext.getKind();
-
+    Output.Context = CCContextKind;
     return Output;
   }
 
@@ -1357,22 +1427,33 @@ private:
   }
 
   // Merges Sema and Index results where possible, to form CompletionCandidates.
+  // \p Identifiers is raw idenfiers that can also be completion condidates.
+  // Identifiers are not merged with results from index or sema.
   // Groups overloads if desired, to form CompletionCandidate::Bundles. The
   // bundles are scored and top results are returned, best to worst.
   std::vector<ScoredBundle>
   mergeResults(const std::vector<CodeCompletionResult> &SemaResults,
-               const SymbolSlab &IndexResults) {
+               const SymbolSlab &IndexResults,
+               const std::vector<RawIdentifier> &IdentifierResults) {
     trace::Span Tracer("Merge and score results");
     std::vector<CompletionCandidate::Bundle> Bundles;
     llvm::DenseMap<size_t, size_t> BundleLookup;
     auto AddToBundles = [&](const CodeCompletionResult *SemaResult,
-                            const Symbol *IndexResult) {
+                            const Symbol *IndexResult,
+                            const RawIdentifier *IdentifierResult = nullptr) {
       CompletionCandidate C;
       C.SemaResult = SemaResult;
       C.IndexResult = IndexResult;
-      if (C.IndexResult)
+      C.IdentifierResult = IdentifierResult;
+      if (C.IndexResult) {
+        C.Name = IndexResult->Name;
         C.RankedIncludeHeaders = getRankedIncludes(*C.IndexResult);
-      C.Name = IndexResult ? IndexResult->Name : Recorder->getName(*SemaResult);
+      } else if (C.SemaResult) {
+        C.Name = Recorder->getName(*SemaResult);
+      } else {
+        assert(IdentifierResult);
+        C.Name = IdentifierResult->Name;
+      }
       if (auto OverloadSet = C.overloadSet(Opts)) {
         auto Ret = BundleLookup.try_emplace(OverloadSet, Bundles.size());
         if (Ret.second)
@@ -1397,7 +1478,7 @@ private:
       return nullptr;
     };
     // Emit all Sema results, merging them with Index results if possible.
-    for (auto &SemaResult : Recorder->Results)
+    for (auto &SemaResult : SemaResults)
       AddToBundles(&SemaResult, CorrespondingIndexResult(SemaResult));
     // Now emit any Index-only results.
     for (const auto &IndexResult : IndexResults) {
@@ -1405,6 +1486,9 @@ private:
         continue;
       AddToBundles(/*SemaResult=*/nullptr, &IndexResult);
     }
+    // Emit identifier results.
+    for (const auto &Ident : IdentifierResults)
+      AddToBundles(/*SemaResult=*/nullptr, /*IndexResult=*/nullptr, &Ident);
     // We only keep the best N results at any time, in "native" format.
     TopN<ScoredBundle, ScoredBundleGreater> Top(
         Opts.Limit == 0 ? std::numeric_limits<size_t>::max() : Opts.Limit);
@@ -1427,7 +1511,7 @@ private:
                     CompletionCandidate::Bundle Bundle) {
     SymbolQualitySignals Quality;
     SymbolRelevanceSignals Relevance;
-    Relevance.Context = Recorder->CCContext.getKind();
+    Relevance.Context = CCContextKind;
     Relevance.Query = SymbolRelevanceSignals::CodeComplete;
     Relevance.FileProximityMatch = FileProximity.getPointer();
     if (ScopeProximity)
@@ -1468,6 +1552,11 @@ private:
         }
         Origin |= SymbolOrigin::AST;
       }
+      if (Candidate.IdentifierResult) {
+        Quality.References = Candidate.IdentifierResult->References;
+        Relevance.Scope = SymbolRelevanceSignals::FileScope;
+        Origin |= SymbolOrigin::Identifier;
+      }
     }
 
     CodeCompletion::Scores Scores;
@@ -1485,7 +1574,8 @@ private:
 
     NSema += bool(Origin & SymbolOrigin::AST);
     NIndex += FromIndex;
-    NBoth += bool(Origin & SymbolOrigin::AST) && FromIndex;
+    NSemaAndIndex += bool(Origin & SymbolOrigin::AST) && FromIndex;
+    NIdent += bool(Origin & SymbolOrigin::Identifier);
     if (Candidates.push({std::move(Bundle), Scores}))
       Incomplete = true;
   }
@@ -1497,9 +1587,9 @@ private:
           Item.SemaResult ? Recorder->codeCompletionString(*Item.SemaResult)
                           : nullptr;
       if (!Builder)
-        Builder.emplace(Recorder->CCSema->getASTContext(), Item, SemaCCS,
-                        QueryScopes, *Inserter, FileName,
-                        Recorder->CCContext.getKind(), Opts);
+        Builder.emplace(Recorder ? &Recorder->CCSema->getASTContext() : nullptr,
+                        Item, SemaCCS, QueryScopes, *Inserter, FileName,
+                        CCContextKind, Opts);
       else
         Builder->add(Item, SemaCCS);
     }
@@ -1568,10 +1658,12 @@ codeComplete(PathRef FileName, const tooling::CompileCommand &Command,
     elog("Code completion position was invalid {0}", Offset.takeError());
     return CodeCompleteResult();
   }
-  return CodeCompleteFlow(FileName,
-                          Preamble ? Preamble->Includes : IncludeStructure(),
-                          SpecFuzzyFind, Opts)
-      .run({FileName, Command, Preamble, Contents, *Offset, VFS});
+  auto Flow = CodeCompleteFlow(
+      FileName, Preamble ? Preamble->Includes : IncludeStructure(),
+      SpecFuzzyFind, Opts);
+  return Preamble ? std::move(Flow).run(
+                        {FileName, Command, Preamble, Contents, *Offset, VFS})
+                  : std::move(Flow).runWithoutSema(Contents, *Offset, VFS);
 }
 
 SignatureHelp signatureHelp(PathRef FileName,
diff --git a/clang-tools-extra/clangd/CodeComplete.h b/clang-tools-extra/clangd/CodeComplete.h
index e1110dccc0d..9d43107a01e 100644
--- a/clang-tools-extra/clangd/CodeComplete.h
+++ b/clang-tools-extra/clangd/CodeComplete.h
@@ -225,7 +225,11 @@ struct SpeculativeFuzzyFind {
   std::future<SymbolSlab> Result;
 };
 
-/// Get code completions at a specified \p Pos in \p FileName.
+/// Gets code completions at a specified \p Pos in \p FileName.
+///
+/// If \p Preamble is nullptr, this runs code completion without compiling the
+/// code.
+///
 /// If \p SpecFuzzyFind is set, a speculative and asynchronous fuzzy find index
 /// request (based on cached request) will be run before parsing sema. In case
 /// the speculative result is used by code completion (e.g. speculation failed),
diff --git a/clang-tools-extra/clangd/Headers.cpp b/clang-tools-extra/clangd/Headers.cpp
index a5759a4ef7c..d4c304fe63b 100644
--- a/clang-tools-extra/clangd/Headers.cpp
+++ b/clang-tools-extra/clangd/Headers.cpp
@@ -175,6 +175,8 @@ void IncludeInserter::addExisting(const Inclusion &Inc) {
 bool IncludeInserter::shouldInsertInclude(
     const HeaderFile &DeclaringHeader, const HeaderFile &InsertedHeader) const {
   assert(DeclaringHeader.valid() && InsertedHeader.valid());
+  if (!HeaderSearchInfo && !InsertedHeader.Verbatim)
+    return false;
   if (FileName == DeclaringHeader.File || FileName == InsertedHeader.File)
     return false;
   auto Included = [&](llvm::StringRef Header) {
@@ -190,7 +192,9 @@ IncludeInserter::calculateIncludePath(const HeaderFile &DeclaringHeader,
   if (InsertedHeader.Verbatim)
     return InsertedHeader.File;
   bool IsSystem = false;
-  std::string Suggested = HeaderSearchInfo.suggestPathToFileForDiagnostics(
+  if (!HeaderSearchInfo)
+    return "\"" + InsertedHeader.File + "\"";
+  std::string Suggested = HeaderSearchInfo->suggestPathToFileForDiagnostics(
       InsertedHeader.File, BuildDir, &IsSystem);
   if (IsSystem)
     Suggested = "<" + Suggested + ">";
diff --git a/clang-tools-extra/clangd/Headers.h b/clang-tools-extra/clangd/Headers.h
index ab44191dc6b..a129b884b05 100644
--- a/clang-tools-extra/clangd/Headers.h
+++ b/clang-tools-extra/clangd/Headers.h
@@ -119,9 +119,12 @@ collectIncludeStructureCallback(const SourceManager &SM, IncludeStructure *Out);
 // Calculates insertion edit for including a new header in a file.
 class IncludeInserter {
 public:
+  // If \p HeaderSearchInfo is nullptr (e.g. when compile command is
+  // infeasible), this will only try to insert verbatim headers, and
+  // include path of non-verbatim header will not be shortened.
   IncludeInserter(StringRef FileName, StringRef Code,
                   const format::FormatStyle &Style, StringRef BuildDir,
-                  HeaderSearch &HeaderSearchInfo)
+                  HeaderSearch *HeaderSearchInfo)
       : FileName(FileName), Code(Code), BuildDir(BuildDir),
         HeaderSearchInfo(HeaderSearchInfo),
         Inserter(FileName, Code, Style.IncludeStyle) {}
@@ -162,7 +165,7 @@ private:
   StringRef FileName;
   StringRef Code;
   StringRef BuildDir;
-  HeaderSearch &HeaderSearchInfo;
+  HeaderSearch *HeaderSearchInfo = nullptr;
   llvm::StringSet<> IncludedHeaders; // Both written and resolved.
   tooling::HeaderIncludes Inserter;  // Computers insertion replacement.
 };
diff --git a/clang-tools-extra/clangd/SourceCode.cpp b/clang-tools-extra/clangd/SourceCode.cpp
index 656ab1dc3c1..d90b04a8a87 100644
--- a/clang-tools-extra/clangd/SourceCode.cpp
+++ b/clang-tools-extra/clangd/SourceCode.cpp
@@ -391,5 +391,29 @@ cleanupAndFormat(StringRef Code, const tooling::Replacements &Replaces,
   return formatReplacements(Code, std::move(*CleanReplaces), Style);
 }
 
+llvm::StringMap<unsigned> collectIdentifiers(llvm::StringRef Content,
+                                             const format::FormatStyle &Style) {
+  SourceManagerForFile FileSM("dummy.cpp", Content);
+  auto &SM = FileSM.get();
+  auto FID = SM.getMainFileID();
+  Lexer Lex(FID, SM.getBuffer(FID), SM, format::getFormattingLangOpts(Style));
+  Token Tok;
+
+  llvm::StringMap<unsigned> Identifiers;
+  while (!Lex.LexFromRawLexer(Tok)) {
+    switch (Tok.getKind()) {
+    case tok::identifier:
+      ++Identifiers[Tok.getIdentifierInfo()->getName()];
+      break;
+    case tok::raw_identifier:
+      ++Identifiers[Tok.getRawIdentifier()];
+      break;
+    default:
+      continue;
+    }
+  }
+  return Identifiers;
+}
+
 } // namespace clangd
 } // namespace clang
diff --git a/clang-tools-extra/clangd/SourceCode.h b/clang-tools-extra/clangd/SourceCode.h
index 55289e00719..45593768023 100644
--- a/clang-tools-extra/clangd/SourceCode.h
+++ b/clang-tools-extra/clangd/SourceCode.h
@@ -156,6 +156,10 @@ llvm::Expected<tooling::Replacements>
 cleanupAndFormat(StringRef Code, const tooling::Replacements &Replaces,
                  const format::FormatStyle &Style);
 
+/// Collects identifiers with counts in the source code.
+llvm::StringMap<unsigned> collectIdentifiers(llvm::StringRef Content,
+                                             const format::FormatStyle &Style);
+
 } // namespace clangd
 } // namespace clang
 #endif
diff --git a/clang-tools-extra/clangd/index/SymbolOrigin.cpp b/clang-tools-extra/clangd/index/SymbolOrigin.cpp
index 93fc69f0613..e98308a2dbd 100644
--- a/clang-tools-extra/clangd/index/SymbolOrigin.cpp
+++ b/clang-tools-extra/clangd/index/SymbolOrigin.cpp
@@ -14,7 +14,7 @@ namespace clangd {
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, SymbolOrigin O) {
   if (O == SymbolOrigin::Unknown)
     return OS << "unknown";
-  constexpr static char Sigils[] = "ADSM4567";
+  constexpr static char Sigils[] = "ADSMI567";
   for (unsigned I = 0; I < sizeof(Sigils); ++I)
     if (static_cast<uint8_t>(O) & 1u << I)
       OS << Sigils[I];
diff --git a/clang-tools-extra/clangd/index/SymbolOrigin.h b/clang-tools-extra/clangd/index/SymbolOrigin.h
index 4541e4c71cb..953f871d5ea 100644
--- a/clang-tools-extra/clangd/index/SymbolOrigin.h
+++ b/clang-tools-extra/clangd/index/SymbolOrigin.h
@@ -20,10 +20,11 @@ namespace clangd {
 // This is a bitfield as information can be combined from several sources.
 enum class SymbolOrigin : uint8_t {
   Unknown = 0,
-  AST = 1 << 0,     // Directly from the AST (indexes should not set this).
-  Dynamic = 1 << 1, // From the dynamic index of opened files.
-  Static = 1 << 2,  // From the static, externally-built index.
-  Merge = 1 << 3,   // A non-trivial index merge was performed.
+  AST = 1 << 0,        // Directly from the AST (indexes should not set this).
+  Dynamic = 1 << 1,    // From the dynamic index of opened files.
+  Static = 1 << 2,     // From the static, externally-built index.
+  Merge = 1 << 3,      // A non-trivial index merge was performed.
+  Identifier = 1 << 4, // Raw identifiers in file.
   // Remaining bits reserved for index implementations.
 };
 
diff --git a/clang-tools-extra/unittests/clangd/ClangdTests.cpp b/clang-tools-extra/unittests/clangd/ClangdTests.cpp
index d428064862b..0deeb2e6317 100644
--- a/clang-tools-extra/unittests/clangd/ClangdTests.cpp
+++ b/clang-tools-extra/unittests/clangd/ClangdTests.cpp
@@ -535,12 +535,12 @@ TEST_F(ClangdVFSTest, InvalidCompileCommand) {
   EXPECT_ERROR(runLocateSymbolAt(Server, FooCpp, Position()));
   EXPECT_ERROR(runFindDocumentHighlights(Server, FooCpp, Position()));
   EXPECT_ERROR(runRename(Server, FooCpp, Position(), "new_name"));
-  // FIXME: codeComplete and signatureHelp should also return errors when they
-  // can't parse the file.
+  // Identifier-based fallback completion.
   EXPECT_THAT(cantFail(runCodeComplete(Server, FooCpp, Position(),
                                        clangd::CodeCompleteOptions()))
                   .Completions,
-              IsEmpty());
+              ElementsAre(Field(&CodeCompletion::Name, "int"),
+                          Field(&CodeCompletion::Name, "main")));
   auto SigHelp = runSignatureHelp(Server, FooCpp, Position());
   ASSERT_TRUE(bool(SigHelp)) << "signatureHelp returned an error";
   EXPECT_THAT(SigHelp->signatures, IsEmpty());
@@ -1066,10 +1066,11 @@ TEST_F(ClangdVFSTest, FallbackWhenPreambleIsNotReady) {
   ClangdServer Server(CDB, FS, DiagConsumer, ClangdServer::optsForTest());
 
   auto FooCpp = testPath("foo.cpp");
-  Annotations Code(R"cpp(
+   Annotations Code(R"cpp(
+    namespace ns { int xyz; }
+    using namespace ns;
     int main() {
-      int xyz;
-      xy^
+       xy^
     })cpp");
   FS.Files[FooCpp] = FooCpp;
 
@@ -1081,17 +1082,21 @@ TEST_F(ClangdVFSTest, FallbackWhenPreambleIsNotReady) {
   Server.addDocument(FooCpp, Code.code());
   ASSERT_TRUE(Server.blockUntilIdleForTest());
   auto Res = cantFail(runCodeComplete(Server, FooCpp, Code.point(), Opts));
-  EXPECT_THAT(Res.Completions, IsEmpty());
   EXPECT_EQ(Res.Context, CodeCompletionContext::CCC_Recovery);
+  // Identifier-based fallback completion doesn't know about "symbol" scope.
+  EXPECT_THAT(Res.Completions,
+              ElementsAre(AllOf(Field(&CodeCompletion::Name, "xyz"),
+                                Field(&CodeCompletion::Scope, ""))));
 
   // Make the compile command work again.
   CDB.ExtraClangFlags = {"-std=c++11"};
   Server.addDocument(FooCpp, Code.code());
   ASSERT_TRUE(Server.blockUntilIdleForTest());
   EXPECT_THAT(cantFail(runCodeComplete(Server, FooCpp, Code.point(),
-                                       Opts))
+                                       clangd::CodeCompleteOptions()))
                   .Completions,
-              ElementsAre(Field(&CodeCompletion::Name, "xyz")));
+              ElementsAre(AllOf(Field(&CodeCompletion::Name, "xyz"),
+                                Field(&CodeCompletion::Scope, "ns::"))));
 }
 
 } // namespace
diff --git a/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp b/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp
index f60ed1c8426..4118fea325c 100644
--- a/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp
+++ b/clang-tools-extra/unittests/clangd/CodeCompleteTests.cpp
@@ -20,6 +20,7 @@
 #include "TestTU.h"
 #include "index/MemIndex.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
+#include "clang/Tooling/CompilationDatabase.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Testing/Support/Error.h"
 #include "gmock/gmock.h"
@@ -138,6 +139,25 @@ CodeCompleteResult completions(llvm::StringRef Text,
                      FilePath);
 }
 
+// Builds a server and runs code completion.
+// If IndexSymbols is non-empty, an index will be built and passed to opts.
+CodeCompleteResult completionsNoCompile(llvm::StringRef Text,
+                                        std::vector<Symbol> IndexSymbols = {},
+                                        clangd::CodeCompleteOptions Opts = {},
+                                        PathRef FilePath = "foo.cpp") {
+  std::unique_ptr<SymbolIndex> OverrideIndex;
+  if (!IndexSymbols.empty()) {
+    assert(!Opts.Index && "both Index and IndexSymbols given!");
+    OverrideIndex = memIndex(std::move(IndexSymbols));
+    Opts.Index = OverrideIndex.get();
+  }
+
+  MockFSProvider FS;
+  Annotations Test(Text);
+  return codeComplete(FilePath, tooling::CompileCommand(), /*Preamble=*/nullptr,
+                      Test.code(), Test.point(), FS.getFileSystem(), Opts);
+}
+
 Symbol withReferences(int N, Symbol S) {
   S.References = N;
   return S;
@@ -2401,6 +2421,33 @@ TEST(CompletionTest, NamespaceDoubleInsertion) {
               UnorderedElementsAre(AllOf(Qualifier(""), Named("ABCDE"))));
 }
 
+TEST(NoCompileCompletionTest, Basic) {
+  auto Results = completionsNoCompile(R"cpp(
+    void func() {
+      int xyz;
+      int abc;
+      ^
+    }
+  )cpp");
+  EXPECT_THAT(Results.Completions,
+              UnorderedElementsAre(Named("void"), Named("func"), Named("int"),
+                                   Named("xyz"), Named("abc")));
+}
+
+TEST(NoCompileCompletionTest, WithFilter) {
+  auto Results = completionsNoCompile(R"cpp(
+    void func() {
+      int sym1;
+      int sym2;
+      int xyz1;
+      int xyz2;
+      sy^
+    }
+  )cpp");
+  EXPECT_THAT(Results.Completions,
+              UnorderedElementsAre(Named("sym1"), Named("sym2")));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang
diff --git a/clang-tools-extra/unittests/clangd/HeadersTests.cpp b/clang-tools-extra/unittests/clangd/HeadersTests.cpp
index ab1311e2e60..2c96d40a9d4 100644
--- a/clang-tools-extra/unittests/clangd/HeadersTests.cpp
+++ b/clang-tools-extra/unittests/clangd/HeadersTests.cpp
@@ -90,7 +90,7 @@ protected:
 
     IncludeInserter Inserter(MainFile, /*Code=*/"", format::getLLVMStyle(),
                              CDB.getCompileCommand(MainFile)->Directory,
-                             Clang->getPreprocessor().getHeaderSearchInfo());
+                             &Clang->getPreprocessor().getHeaderSearchInfo());
     for (const auto &Inc : Inclusions)
       Inserter.addExisting(Inc);
     auto Declaring = ToHeaderFile(Original);
@@ -110,7 +110,7 @@ protected:
 
     IncludeInserter Inserter(MainFile, /*Code=*/"", format::getLLVMStyle(),
                              CDB.getCompileCommand(MainFile)->Directory,
-                             Clang->getPreprocessor().getHeaderSearchInfo());
+                             &Clang->getPreprocessor().getHeaderSearchInfo());
     auto Edit = Inserter.insert(VerbatimHeader);
     Action.EndSourceFile();
     return Edit;
@@ -252,6 +252,24 @@ TEST_F(HeadersTest, PreferInserted) {
   EXPECT_TRUE(StringRef(Edit->newText).contains("<y>"));
 }
 
+TEST(Headers, NoHeaderSearchInfo) {
+  std::string MainFile = testPath("main.cpp");
+  IncludeInserter Inserter(MainFile, /*Code=*/"", format::getLLVMStyle(),
+                           /*BuildDir=*/"", /*HeaderSearchInfo=*/nullptr);
+
+  auto HeaderPath = testPath("sub/bar.h");
+  auto Declaring = HeaderFile{HeaderPath, /*Verbatim=*/false};
+  auto Inserting = HeaderFile{HeaderPath, /*Verbatim=*/false};
+  auto Verbatim = HeaderFile{"<x>", /*Verbatim=*/true};
+
+  EXPECT_EQ(Inserter.calculateIncludePath(Declaring, Inserting),
+            "\"" + HeaderPath + "\"");
+  EXPECT_EQ(Inserter.shouldInsertInclude(Declaring, Inserting), false);
+
+  EXPECT_EQ(Inserter.calculateIncludePath(Declaring, Verbatim), "<x>");
+  EXPECT_EQ(Inserter.shouldInsertInclude(Declaring, Verbatim), true);
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang
diff --git a/clang-tools-extra/unittests/clangd/SourceCodeTests.cpp b/clang-tools-extra/unittests/clangd/SourceCodeTests.cpp
index e38eaa33b6c..965deefc3a5 100644
--- a/clang-tools-extra/unittests/clangd/SourceCodeTests.cpp
+++ b/clang-tools-extra/unittests/clangd/SourceCodeTests.cpp
@@ -9,6 +9,7 @@
 #include "Context.h"
 #include "Protocol.h"
 #include "SourceCode.h"
+#include "clang/Format/Format.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/raw_os_ostream.h"
 #include "llvm/Testing/Support/Error.h"
@@ -304,6 +305,23 @@ TEST(SourceCodeTests, SourceLocationInMainFile) {
   }
 }
 
+TEST(SourceCodeTests, CollectIdentifiers) {
+  auto Style = format::getLLVMStyle();
+  auto IDs = collectIdentifiers(R"cpp(
+  #include "a.h"
+  void foo() { int xyz; int abc = xyz; return foo(); }
+  )cpp",
+                                Style);
+  EXPECT_EQ(IDs.size(), 7u);
+  EXPECT_EQ(IDs["include"], 1u);
+  EXPECT_EQ(IDs["void"], 1u);
+  EXPECT_EQ(IDs["int"], 2u);
+  EXPECT_EQ(IDs["xyz"], 2u);
+  EXPECT_EQ(IDs["abc"], 1u);
+  EXPECT_EQ(IDs["return"], 1u);
+  EXPECT_EQ(IDs["foo"], 2u);
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang