[clangd] Suggest adding missing includes for typos (like include-fixer).

[ioeric]

Summary

This adds include-fixer feature into clangd based on D56903. Clangd now captures
diagnostics caused by typos and attach include insertion fixes to potentially
fix the typo.

[ioeric]

• revert unintended change

[ioeric]

• Rebase on D56903.

[ioeric]

• Rebase on D56903

[ioeric]

• Rebase on origin/master

[ioeric]

Ping

[sammccall]

clangd/IncludeFixer.cpp

74 ↗

(On Diff #183845)

"default" looks a bit scary - could still end up with false positives.
Can we cover a few of the most common cases (even if we know they're not exhaustive) to start with?

203 ↗

(On Diff #183845)

a comment that we never return a valid correction to try to recover, our suggested fixes always require a rebuild.

209 ↗

(On Diff #183845)

why do we do this here rather than compute the scopes/name already in CorrectTypo()?

Passing around more of these AST objects and doing the computations later seems a bit more fragile.

227 ↗

(On Diff #183845)

limit?

233 ↗

(On Diff #183845)

why put these into a slab and then build fixes later, rather than build the fixes immediately?

241 ↗

(On Diff #183845)

Doesn't seem worth special casing this, below code will work fine.

246 ↗

(On Diff #183845)

the fixes can overlap: distinct symbols may be defined in the same header.
Common case: function overloads.

At some level we "just want to deduplicate" these.
It's slightly complicated because of the tricky way we calculate the edits.
Maybe the best thing is to pass in all the symbols to fixesForSymbol() instead of just one.

One thing to keep in mind is a future where we want to pull in results across namespaces: the fixes for "include 'a.h' for x::Foo" and "include 'a.h' for y::Foo" need to be distinct because of the different added qualifiers.
So it'd be good to end up with an explicit e.g. map<header_to_include, Fix> to deduplicate, then we can just change the key to pair<header_to_include, qualifier_to_insert>

clangd/IncludeFixer.h

35 ↗

(On Diff #183845)

Having to inject the whole compiler into the include fixer doesn't seem right. Apart from the huge scope, we're also going to register parts of the include fixer with the compiler.

A few observations:

• all we actually need here is Sema and the SM (available through Sema)
• it's only the typo recorder that needs access to Sema
• the typo recorder gets fed the Sema instance (ExternalSemaSource::InitializeSema)
• the fact that fixTypo() needs to access the typo recorder doesn't seem necessary

So I'd suggest changing this function to return a *new* ExternalSemaSource that stashes the last typo in this IncludeFixer object directly.

e.g.

llvm::IntrusiveRefCntPtr<ExternalSemaSource> typoRecorder() {
  return new TypoRecorder(LastTypo);
}
private:
  Optional<TypoRecord> LastTypo;
  class TypoRecorder : public ExternalSemaSource {
    Sema *S;
    Optional<TypoRecord> &Out;
    InitializeSema(Sema& S) { this->S = &S; }
    CorrectTypo(...) {
      assert(S);
      ...
      Out = ...;
    }
  }

46 ↗

(On Diff #183845)

This would be a reasonable place to document what the feature is and how it works :-)

e.g.

/// Returns an ExternalSemaSource that records failed name lookups in Sema.
/// This allows IncludeFixer to suggest inserting headers that define those names.

59 ↗

(On Diff #183845)

So an annoying naming thing: I find the use of "typo" to describe this feature really confusing. There's no actual typo, and conflating Sema's typo-correction fixes (which allow the parse to recover) and our generated fixes (which requires changing the source and rebuilding) breaks my brain a bit.

I'd suggest calling this "unresolved name" throughout, except when specifically referring to the mechanism by which we observe unresolved names.
e.g. TypoRecorder -> UnresolvedNameRecorder etc.

68 ↗

(On Diff #183845)

I think TypoRecorder can be merely declared here, and defined in the CC file?

[ioeric]

• address review comments.

[ioeric]

clangd/IncludeFixer.cpp

209 ↗

(On Diff #183845)

Because not all typos will result in diagnostics. Computing scopes could be expensive, so we would only want to do that when necessary. For example, sema can perform typo corrections for both x and y in x::y, while only one diagnostic (for either x or y) would be generated.

233 ↗

(On Diff #183845)

good point.

clangd/IncludeFixer.h

35 ↗

(On Diff #183845)

Great idea. Thanks!

I've done most of the suggested refactoring.

the fact that fixTypo() needs to access the typo recorder doesn't seem necessary.

Do you mean access to *Sema*? The IncludeFixer still needs sema because we don't want to run Lookup for each typo sema encounters. We only want to do that for typos that make it to diagnostics. See my response to the other comment about this for details.

[sammccall]

clangd/IncludeFixer.cpp

82 ↗

(On Diff #185031)

you never seem to clear LastUnresolvedName - I guess you at least want to clear it after using it.
It would be more robust to clear after every diagnostic - would this work?

161 ↗

(On Diff #185031)

note that if you have symbols in different scopes from the same header, you're only generating one fix and it will only mention one of the symbols.

It's fine to decide this case doesn't matter, but it's worth adding a comment.
(Alternatively, using a set of pair<inserted-header, qualified-name> to track dupes would avoid this)

186 ↗

(On Diff #185031)

SemaPtr?

199 ↗

(On Diff #185031)

The FIXME makes sense, but it's not clear to me what the code below it does or how it relates to the comment.

maybe separate with a blank line and then "Extract the typed scope" or so?

228 ↗

(On Diff #185031)

nit: recover

233 ↗

(On Diff #185031)

unused

209 ↗

(On Diff #183845)

If the goal is to make the scope computation lazy, CorrectTypo can store them as a std::function<std::vector<string>()> - that way we can still group the related code and dependencies together.

This function can capture the Sema instance by pointer - this deserves a comment that sema must be alive to access the scopes.

clangd/IncludeFixer.h

60 ↗

(On Diff #185031)

nit: the comment on Loc and LookupKind don't say anything, remove them?

61 ↗

(On Diff #185031)

please use real names for these fields (EnclosingScope, SpecifiedScope?)

Maybe it would help documenting here to have a more complete example e.g.

namespace ns { int Y = foo::x }

Name is x
Loc is points at x (or f?)
EnclosingScope is ns::
SpecifiedScope is either ns::foo:: or foo:: (depending how 'foo' was resolved)

72 ↗

(On Diff #185031)

nit: why take a parameter here, when it's always *LastUnresolvedName?

35 ↗

(On Diff #183845)

Yes, I meant Sema here. I think we can avoid IncludeFixer holding a reference to Sema directly.

59 ↗

(On Diff #183845)

I don't think this is done: there are still 20+ references to "typo" in this patch.
I think they should all be changed, apart from the implementation of CorrectTypo() and a comment explaining the use of this mechanism.
Happy to discuss if you don't think this is a good idea, though!

[ioeric]

• address review comments

[sammccall]

Great stuff! Sorry for the delay here.

clangd/IncludeFixer.h

59 ↗

(On Diff #185546)

nit: this isn't really a callback, I think.
Just "Lazily get the possible scopes of the unresolved name"?

64 ↗

(On Diff #185546)

"i.e. typo" is confusing here, as these aren't actually typos

[ioeric]

• Merge remote-tracking branch 'origin/master' into typo
• address review comments

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

if (Preamble) {
         Inserter->addExisting(Inc);
     }
     FixIncludes.emplace(MainInput.getFile(), Inserter, *Index,
                         /*IndexRequestLimit=*/5);
     ASTDiags.contributeFixes([&FixIncludes](DiagnosticsEngine::Level DiagLevl,
                                             const clang::Diagnostic &Info) {
       return FixIncludes->fix(DiagLevl, Info);
     });
+    Clang->setExternalSemaSource(FixIncludes->unresolvedNameRecorder());
   }
 
   // Copy over the includes from the preamble, then combine with the
   // non-preamble includes below.
   auto Includes = Preamble ? Preamble->Includes : IncludeStructure{};
   // Replay the preamble includes so that clang-tidy checks can see them.
   if (Preamble)
     ReplayPreamble::attach(Includes, *Clang);
buildAST(PathRef FileName, std::unique_ptr<CompilerInvocation> Invocation,
   if (Preamble && Preamble->StatCache)
     VFS = Preamble->StatCache->getConsumingFS(std::move(VFS));
   if (VFS->setCurrentWorkingDirectory(Inputs.CompileCommand.Directory)) {
     log("Couldn't set working directory when building the preamble.");
     // We proceed anyway, our lit-tests rely on results for non-existing working
     // dirs.
   }
 
-  return ParsedAST::build(
-      llvm::make_unique<CompilerInvocation>(*Invocation), Preamble,
-      llvm::MemoryBuffer::getMemBufferCopy(Inputs.Contents), PCHs,
-      std::move(VFS), Inputs.Index ? Inputs.Index : nullptr, Inputs.Opts);
+  return ParsedAST::build(llvm::make_unique<CompilerInvocation>(*Invocation),
+                          Preamble,
+                          llvm::MemoryBuffer::getMemBufferCopy(Inputs.Contents),
+                          PCHs, std::move(VFS), Inputs.Index, Inputs.Opts);
 }
 
 SourceLocation getBeginningOfIdentifier(ParsedAST &Unit, const Position &Pos,
                                         const FileID FID) {
   const ASTContext &AST = Unit.getASTContext();
   const SourceManager &SourceMgr = AST.getSourceManager();
   auto Offset = positionToOffset(SourceMgr.getBufferData(FID), Pos);
   if (!Offset) {

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

 //===--- IncludeFixer.h ------------------------------------------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDE_FIXER_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDE_FIXER_H
 
 #include "Diagnostics.h"
 #include "Headers.h"
 #include "index/Index.h"
 #include "clang/AST/Type.h"
 #include "clang/Basic/Diagnostic.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Sema/ExternalSemaSource.h"
+#include "clang/Sema/Sema.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/IntrusiveRefCntPtr.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringRef.h"
 #include <memory>
 
 namespace clang {
 namespace clangd {
 
 /// Attempts to recover from error diagnostics by suggesting include insertion
 /// fixes. For example, member access into incomplete type can be fixes by
 /// include headers with the definition.
 class IncludeFixer {
 public:
   IncludeFixer(llvm::StringRef File, std::shared_ptr<IncludeInserter> Inserter,
                const SymbolIndex &Index, unsigned IndexRequestLimit)
       : File(File), Inserter(std::move(Inserter)), Index(Index),
         IndexRequestLimit(IndexRequestLimit) {}
 
   /// Returns include insertions that can potentially recover the diagnostic.
   std::vector<Fix> fix(DiagnosticsEngine::Level DiagLevel,
                        const clang::Diagnostic &Info) const;
 
+  /// Returns an ExternalSemaSource that records failed name lookups in Sema.
+  /// This allows IncludeFixer to suggest inserting headers that define those
+  /// names.
+  llvm::IntrusiveRefCntPtr<ExternalSemaSource> unresolvedNameRecorder();
+
 private:
   /// Attempts to recover diagnostic caused by an incomplete type \p T.
   std::vector<Fix> fixIncompleteType(const Type &T) const;
 
-  /// Generates header insertion fixes for \p Sym.
-  std::vector<Fix> fixesForSymbol(const Symbol &Sym) const;
+  /// Generates header insertion fixes for all symbols. Fixes are deduplicated.
+  std::vector<Fix> fixesForSymbols(llvm::ArrayRef<Symbol> Syms) const;
+
+  struct UnresolvedName {
+    std::string Name;   // E.g. "X" in foo::X.
+    SourceLocation Loc; // Start location of the unresolved name.
+    // Lazily get the possible scopes of the unresolved name. `Sema` must be
+    // alive when this is called.
+    std::function<std::vector<std::string>()> GetScopes;
+  };
+
+  /// Records the last unresolved name seen by Sema.
+  class UnresolvedNameRecorder;
+
+  /// Attempts to fix the unresolved name associated with the current
+  /// diagnostic. We assume a diagnostic is caused by a unresolved name when
+  /// they have the same source location and the unresolved name is the last
+  /// one we've seen during the Sema run.
+  std::vector<Fix> fixUnresolvedName() const;
 
   std::string File;
   std::shared_ptr<IncludeInserter> Inserter;
   const SymbolIndex &Index;
   const unsigned IndexRequestLimit; // Make at most 5 index requests.
   mutable unsigned IndexRequestCount = 0;
+
+  // These collect the last unresolved name so that we can associate it with the
+  // diagnostic.
+  llvm::Optional<UnresolvedName> LastUnresolvedName;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDE_FIXER_H

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

 //===--- IncludeFixer.cpp ----------------------------------------*- C++-*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "IncludeFixer.h"
 #include "AST.h"
 #include "Diagnostics.h"
 #include "Logger.h"
 #include "SourceCode.h"
 #include "Trace.h"
 #include "index/Index.h"
 #include "clang/AST/Decl.h"
+#include "clang/AST/DeclBase.h"
+#include "clang/AST/NestedNameSpecifier.h"
 #include "clang/AST/Type.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/DiagnosticSema.h"
+#include "clang/Sema/DeclSpec.h"
+#include "clang/Sema/Lookup.h"
+#include "clang/Sema/Scope.h"
+#include "clang/Sema/Sema.h"
+#include "clang/Sema/TypoCorrection.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/None.h"
+#include "llvm/ADT/StringSet.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FormatVariadic.h"
+#include <vector>
 
 namespace clang {
 namespace clangd {
 
+namespace {
+
+// Collects contexts visited during a Sema name lookup.
+class VisitedContextCollector : public VisibleDeclConsumer {
+public:
+  void EnteredContext(DeclContext *Ctx) override { Visited.push_back(Ctx); }
+
+  void FoundDecl(NamedDecl *ND, NamedDecl *Hiding, DeclContext *Ctx,
+                 bool InBaseClass) override {}
+
+  std::vector<DeclContext *> takeVisitedContexts() {
+    return std::move(Visited);
+  }
+
+private:
+  std::vector<DeclContext *> Visited;
+};
+
+} // namespace
+
 std::vector<Fix> IncludeFixer::fix(DiagnosticsEngine::Level DiagLevel,
                                    const clang::Diagnostic &Info) const {
   if (IndexRequestCount >= IndexRequestLimit)
     return {}; // Avoid querying index too many times in a single parse.
   switch (Info.getID()) {
   case diag::err_incomplete_type:
   case diag::err_incomplete_member_access:
   case diag::err_incomplete_base_class:
     // Incomplete type diagnostics should have a QualType argument for the
     // incomplete type.
     for (unsigned Idx = 0; Idx < Info.getNumArgs(); ++Idx) {
       if (Info.getArgKind(Idx) == DiagnosticsEngine::ak_qualtype) {
         auto QT = QualType::getFromOpaquePtr((void *)Info.getRawArg(Idx));
         if (const Type *T = QT.getTypePtrOrNull())
           if (T->isIncompleteType())
             return fixIncompleteType(*T);
       }
     }
+    break;
+  case diag::err_unknown_typename:
+  case diag::err_unknown_typename_suggest:
+  case diag::err_typename_nested_not_found:
+  case diag::err_no_template:
+  case diag::err_no_template_suggest:
+    if (LastUnresolvedName) {
+      // Try to fix unresolved name caused by missing declaraion.
+      // E.g.
+      //   clang::SourceManager SM;
+      //          ~~~~~~~~~~~~~
+      //          UnresolvedName
+      //   or
+      //   namespace clang {  SourceManager SM; }
+      //                      ~~~~~~~~~~~~~
+      //                      UnresolvedName
+      // We only attempt to recover a diagnostic if it has the same location as
+      // the last seen unresolved name.
+      if (DiagLevel >= DiagnosticsEngine::Error &&
+          LastUnresolvedName->Loc == Info.getLocation())
+        return fixUnresolvedName();
+    }
   }
   return {};
 }
 
 std::vector<Fix> IncludeFixer::fixIncompleteType(const Type &T) const {
   // Only handle incomplete TagDecl type.
   const TagDecl *TD = T.getAsTagDecl();
   if (!TD)
Index.lookup(Req, [&](const Symbol &Sym) {
     if (Matched)
       return;
     Matched = Sym;
   });
 
   if (!Matched || Matched->IncludeHeaders.empty() || !Matched->Definition ||
       Matched->CanonicalDeclaration.FileURI != Matched->Definition.FileURI)
     return {};
-  return fixesForSymbol(*Matched);
+  return fixesForSymbols({*Matched});
 }
 
-std::vector<Fix> IncludeFixer::fixesForSymbol(const Symbol &Sym) const {
-  auto Inserted = [&](llvm::StringRef Header)
+std::vector<Fix>
+IncludeFixer::fixesForSymbols(llvm::ArrayRef<Symbol> Syms) const {
+  auto Inserted = [&](const Symbol &Sym, llvm::StringRef Header)
       -> llvm::Expected<std::pair<std::string, bool>> {
     auto ResolvedDeclaring =
         toHeaderFile(Sym.CanonicalDeclaration.FileURI, File);
     if (!ResolvedDeclaring)
       return ResolvedDeclaring.takeError();
     auto ResolvedInserted = toHeaderFile(Header, File);
     if (!ResolvedInserted)
       return ResolvedInserted.takeError();
     return std::make_pair(
         Inserter->calculateIncludePath(*ResolvedDeclaring, *ResolvedInserted),
         Inserter->shouldInsertInclude(*ResolvedDeclaring, *ResolvedInserted));
   };
 
   std::vector<Fix> Fixes;
+  // Deduplicate fixes by include headers. This doesn't distiguish symbols in
+  // different scopes from the same header, but this case should be rare and is
+  // thus ignored.
+  llvm::StringSet<> InsertedHeaders;
+  for (const auto &Sym : Syms) {
     for (const auto &Inc : getRankedIncludes(Sym)) {
-    if (auto ToInclude = Inserted(Inc)) {
-      if (ToInclude->second)
+      if (auto ToInclude = Inserted(Sym, Inc)) {
+        if (ToInclude->second) {
+          auto I = InsertedHeaders.try_emplace(ToInclude->first);
+          if (!I.second)
+            continue;
           if (auto Edit = Inserter->insert(ToInclude->first))
             Fixes.push_back(
                 Fix{llvm::formatv("Add include {0} for symbol {1}{2}",
                                   ToInclude->first, Sym.Scope, Sym.Name),
                     {std::move(*Edit)}});
+        }
       } else {
-      vlog("Failed to calculate include insertion for {0} into {1}: {2}", File,
-           Inc, ToInclude.takeError());
+        vlog("Failed to calculate include insertion for {0} into {1}: {2}",
+             File, Inc, ToInclude.takeError());
+      }
     }
   }
   return Fixes;
 }
+class IncludeFixer::UnresolvedNameRecorder : public ExternalSemaSource {
+public:
+  UnresolvedNameRecorder(llvm::Optional<UnresolvedName> &LastUnresolvedName)
+      : LastUnresolvedName(LastUnresolvedName) {}
+
+  void InitializeSema(Sema &S) override { this->SemaPtr = &S; }
+
+  // Captures the latest typo and treat it as an unresolved name that can
+  // potentially be fixed by adding #includes.
+  TypoCorrection CorrectTypo(const DeclarationNameInfo &Typo, int LookupKind,
+                             Scope *S, CXXScopeSpec *SS,
+                             CorrectionCandidateCallback &CCC,
+                             DeclContext *MemberContext, bool EnteringContext,
+                             const ObjCObjectPointerType *OPT) override {
+    assert(SemaPtr && "Sema must have been set.");
+    if (SemaPtr->isSFINAEContext())
+      return TypoCorrection();
+    if (!SemaPtr->SourceMgr.isWrittenInMainFile(Typo.getLoc()))
+      return clang::TypoCorrection();
+
+    assert(S && "Enclosing scope must be set.");
+
+    UnresolvedName Unresolved;
+    Unresolved.Name = Typo.getAsString();
+    Unresolved.Loc = Typo.getBeginLoc();
+
+    // FIXME: support invalid scope before a type name. In the following
+    // example, namespace "clang::tidy::" hasn't been declared/imported.
+    //    namespace clang {
+    //    void f() {
+    //      tidy::Check c;
+    //      ~~~~
+    //      // or
+    //      clang::tidy::Check c;
+    //             ~~~~
+    //    }
+    //    }
+    // For both cases, the typo and the diagnostic are both on "tidy", and no
+    // diagnostic is generated for "Check". However, what we want to fix is
+    // "clang::tidy::Check".
+
+    // Extract the typed scope. This is not done lazily because `SS` can get
+    // out of scope and it's relatively cheap.
+    llvm::Optional<std::string> SpecifiedScope;
+    if (SS && SS->isNotEmpty()) { // "::" or "ns::"
+      if (auto *Nested = SS->getScopeRep()) {
+        if (Nested->getKind() == NestedNameSpecifier::Global)
+          SpecifiedScope = "";
+        else if (const auto *NS = Nested->getAsNamespace())
+          SpecifiedScope = printNamespaceScope(*NS);
+        else
+          // We don't fix symbols in scopes that are not top-level e.g. class
+          // members, as we don't collect includes for them.
+          return TypoCorrection();
+      }
+    }
+
+    auto *Sem = SemaPtr; // Avoid capturing `this`.
+    Unresolved.GetScopes = [Sem, SpecifiedScope, S, LookupKind]() {
+      std::vector<std::string> Scopes;
+      if (SpecifiedScope) {
+        Scopes.push_back(*SpecifiedScope);
+      } else {
+        // No scope qualifier is specified. Collect all accessible scopes in the
+        // context.
+        VisitedContextCollector Collector;
+        Sem->LookupVisibleDecls(
+            S, static_cast<Sema::LookupNameKind>(LookupKind), Collector,
+            /*IncludeGlobalScope=*/false,
+            /*LoadExternal=*/false);
+
+        Scopes.push_back("");
+        for (const auto *Ctx : Collector.takeVisitedContexts())
+          if (isa<NamespaceDecl>(Ctx))
+            Scopes.push_back(printNamespaceScope(*Ctx));
+      }
+      return Scopes;
+    };
+    LastUnresolvedName = std::move(Unresolved);
+
+    // Never return a valid correction to try to recover. Our suggested fixes
+    // always require a rebuild.
+    return TypoCorrection();
+  }
+
+private:
+  Sema *SemaPtr = nullptr;
+
+  llvm::Optional<UnresolvedName> &LastUnresolvedName;
+};
+
+llvm::IntrusiveRefCntPtr<ExternalSemaSource>
+IncludeFixer::unresolvedNameRecorder() {
+  return new UnresolvedNameRecorder(LastUnresolvedName);
+}
+
+std::vector<Fix> IncludeFixer::fixUnresolvedName() const {
+  assert(LastUnresolvedName.hasValue());
+  auto &Unresolved = *LastUnresolvedName;
+  std::vector<std::string> Scopes = Unresolved.GetScopes();
+  vlog("Trying to fix unresolved name \"{0}\" in scopes: [{1}]",
+       Unresolved.Name, llvm::join(Scopes.begin(), Scopes.end(), ", "));
+
+  FuzzyFindRequest Req;
+  Req.AnyScope = false;
+  Req.Query = Unresolved.Name;
+  Req.Scopes = Scopes;
+  Req.RestrictForCodeCompletion = true;
+  Req.Limit = 100;
+
+  SymbolSlab::Builder Matches;
+  Index.fuzzyFind(Req, [&](const Symbol &Sym) {
+    if (Sym.Name != Req.Query)
+      return;
+    if (!Sym.IncludeHeaders.empty())
+      Matches.insert(Sym);
+  });
+  auto Syms = std::move(Matches).build();
+  return fixesForSymbols(std::vector<Symbol>(Syms.begin(), Syms.end()));
+}
 
 } // namespace clangd
 } // namespace clang

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

 ///
 /// If P.character exceeds the line length, returns the offset at end-of-line.
 /// (If !AllowColumnsBeyondLineLength, then returns an error instead).
 /// If the line number is out of range, returns an error.
 ///
 /// The returned value is in the range [0, Code.size()].
 llvm::Expected<size_t>
 positionToOffset(llvm::StringRef Code, Position P,
-                 bool AllowColumnsBeyondLineLength = true);
 
 /// Turn an offset in Code into a [line, column] pair.
 /// The offset must be in range [0, Code.size()].
 Position offsetToPosition(llvm::StringRef Code, size_t Offset);
 
 /// Turn a SourceLocation into a [line, column] pair.
 /// FIXME: This should return an error if the location is invalid.
 Position sourceLocToPosition(const SourceManager &SM, SourceLocation Loc);

 // Converts a half-open clang source range to an LSP range.
 // Note that clang also uses closed source ranges, which this can't handle!
 Range halfOpenToRange(const SourceManager &SM, CharSourceRange R);
 
 // Converts an offset to a clang line/column (1-based, columns are bytes).
 // The offset must be in range [0, Code.size()].
 // Prefer to use SourceManager if one is available.
 std::pair<size_t, size_t> offsetToClangLineColumn(llvm::StringRef Code,
-                                                  size_t Offset);
 
 /// From "a::b::c", return {"a::b::", "c"}. Scope is empty if there's no
 /// qualifier.
 std::pair<llvm::StringRef, llvm::StringRef>
 splitQualifiedName(llvm::StringRef QName);
 
 TextEdit replacementToEdit(StringRef Code, const tooling::Replacement &R);
 
 std::vector<TextEdit> replacementsToEdits(StringRef Code,
-                                          const tooling::Replacements &Repls);
 
 TextEdit toTextEdit(const FixItHint &FixIt, const SourceManager &M,
-                    const LangOptions &L);
 
 /// Get the canonical path of \p F.  This means:
 ///
 ///   - Absolute path
 ///   - Symlinks resolved
 ///   - No "." or ".." component
 ///   - No duplicate or trailing directory separator
 ///
 /// This function should be used when paths needs to be used outside the
 /// component that generate it, so that paths are normalized as much as
 /// possible.
 llvm::Optional<std::string> getCanonicalPath(const FileEntry *F,
-                                             const SourceManager &SourceMgr);
 
 bool isRangeConsecutive(const Range &Left, const Range &Right);
 
 format::FormatStyle getFormatStyleForFile(llvm::StringRef File,
                                           llvm::StringRef Content,
                                           llvm::vfs::FileSystem *FS);
 
 // Cleanup and format the given replacements.
 llvm::Expected<tooling::Replacements>
 cleanupAndFormat(StringRef Code, const tooling::Replacements &Replaces,
                  const format::FormatStyle &Style);
 
 } // namespace clangd
 } // namespace clang
 #endif

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

 using testing::IsEmpty;
 using testing::Pair;
 using testing::UnorderedElementsAre;
 
 testing::Matcher<const Diag &> WithFix(testing::Matcher<Fix> FixMatcher) {
   return Field(&Diag::Fixes, ElementsAre(FixMatcher));
 }
 
+testing::Matcher<const Diag &> WithFix(testing::Matcher<Fix> FixMatcher1,
+                                       testing::Matcher<Fix> FixMatcher2) {
+  return Field(&Diag::Fixes, UnorderedElementsAre(FixMatcher1, FixMatcher2));
+}
+
 testing::Matcher<const Diag &> WithNote(testing::Matcher<Note> NoteMatcher) {
   return Field(&Diag::Notes, ElementsAre(NoteMatcher));
 }
 
 MATCHER_P2(Diag, Range, Message,
            "Diag at " + llvm::to_string(Range) + " = [" + Message + "]") {
   return arg.Range == Range && arg.Message == Message;
 }
#endif
              });
 
   EXPECT_THAT(
       LSPDiags,
       ElementsAre(Pair(EqualToLSPDiag(MainLSP), ElementsAre(EqualToFix(F))),
                   Pair(EqualToLSPDiag(NoteInMainLSP), IsEmpty())));
 }
 
+struct SymbolWithHeader {
+  std::string QName;
+  std::string DeclaringFile;
+  std::string IncludeHeader;
+};
+
+std::unique_ptr<SymbolIndex>
+buildIndexWithSymbol(llvm::ArrayRef<SymbolWithHeader> Syms) {
+  SymbolSlab::Builder Slab;
+  for (const auto &S : Syms) {
+    Symbol Sym = cls(S.QName);
+    Sym.Flags |= Symbol::IndexedForCodeCompletion;
+    Sym.CanonicalDeclaration.FileURI = S.DeclaringFile.c_str();
+    Sym.Definition.FileURI = S.DeclaringFile.c_str();
+    Sym.IncludeHeaders.emplace_back(S.IncludeHeader, 1);
+    Slab.insert(Sym);
+  }
+  return MemIndex::build(std::move(Slab).build(), RefSlab());
+}
+
 TEST(IncludeFixerTest, IncompleteType) {
   Annotations Test(R"cpp(
 $insert[[]]namespace ns {
   class X;
 }
 class Y : $base[[public ns::X]] {};
 int main() {
   ns::X *x;
   x$access[[->]]f();
 }
   )cpp");
   auto TU = TestTU::withCode(Test.code());
-  Symbol Sym = cls("ns::X");
-  Sym.Flags |= Symbol::IndexedForCodeCompletion;
-  Sym.CanonicalDeclaration.FileURI = "unittest:///x.h";
-  Sym.Definition.FileURI = "unittest:///x.h";
-  Sym.IncludeHeaders.emplace_back("\"x.h\"", 1);
-
-  SymbolSlab::Builder Slab;
-  Slab.insert(Sym);
-  auto Index = MemIndex::build(std::move(Slab).build(), RefSlab());
+  auto Index = buildIndexWithSymbol(
+      {SymbolWithHeader{"ns::X", "unittest:///x.h", "\"x.h\""}});
   TU.ExternalIndex = Index.get();
 
   EXPECT_THAT(
       TU.build().getDiagnostics(),
       UnorderedElementsAre(
           AllOf(Diag(Test.range("base"), "base class has incomplete type"),
                 WithFix(Fix(Test.range("insert"), "#include \"x.h\"\n",
                             "Add include \"x.h\" for symbol ns::X"))),
int main() {
 
   EXPECT_THAT(TU.build().getDiagnostics(),
               UnorderedElementsAre(
                   Diag(Test.range("base"), "base class has incomplete type"),
                   Diag(Test.range("access"),
                        "member access into incomplete type 'ns::X'")));
 }
 
+TEST(IncludeFixerTest, Typo) {
+  Annotations Test(R"cpp(
+$insert[[]]namespace ns {
+void foo() {
+  $unqualified[[X]] x;
+}
+}
+void bar() {
+  ns::$qualified[[X]] x; // ns:: is valid.
+  ::$global[[Global]] glob;
+}
+  )cpp");
+  auto TU = TestTU::withCode(Test.code());
+  auto Index = buildIndexWithSymbol(
+      {SymbolWithHeader{"ns::X", "unittest:///x.h", "\"x.h\""},
+       SymbolWithHeader{"Global", "unittest:///global.h", "\"global.h\""}});
+  TU.ExternalIndex = Index.get();
+
+  EXPECT_THAT(
+      TU.build().getDiagnostics(),
+      UnorderedElementsAre(
+          AllOf(Diag(Test.range("unqualified"), "unknown type name 'X'"),
+                WithFix(Fix(Test.range("insert"), "#include \"x.h\"\n",
+                            "Add include \"x.h\" for symbol ns::X"))),
+          AllOf(Diag(Test.range("qualified"),
+                     "no type named 'X' in namespace 'ns'"),
+                WithFix(Fix(Test.range("insert"), "#include \"x.h\"\n",
+                            "Add include \"x.h\" for symbol ns::X"))),
+          AllOf(Diag(Test.range("global"),
+                     "no type named 'Global' in the global namespace"),
+                WithFix(Fix(Test.range("insert"), "#include \"global.h\"\n",
+                            "Add include \"global.h\" for symbol Global")))));
+}
+
+TEST(IncludeFixerTest, MultipleMatchedSymbols) {
+  Annotations Test(R"cpp(
+$insert[[]]namespace na {
+namespace nb {
+void foo() {
+  $unqualified[[X]] x;
+}
+}
+}
+  )cpp");
+  auto TU = TestTU::withCode(Test.code());
+  auto Index = buildIndexWithSymbol(
+      {SymbolWithHeader{"na::X", "unittest:///a.h", "\"a.h\""},
+       SymbolWithHeader{"na::nb::X", "unittest:///b.h", "\"b.h\""}});
+  TU.ExternalIndex = Index.get();
+
+  EXPECT_THAT(TU.build().getDiagnostics(),
+              UnorderedElementsAre(AllOf(
+                  Diag(Test.range("unqualified"), "unknown type name 'X'"),
+                  WithFix(Fix(Test.range("insert"), "#include \"a.h\"\n",
+                              "Add include \"a.h\" for symbol na::X"),
+                          Fix(Test.range("insert"), "#include \"b.h\"\n",
+                              "Add include \"b.h\" for symbol na::nb::X")))));
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang