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

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.

Reviewers: sammccall

Reviewed By: sammccall

Subscribers: cfe-commits, kadircet, arphaman, mgrang, jkorous, MaskRay, javed.absar, ilya-biryukov, mgorny

Tags: #clang

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

git-svn-id: https://llvm.org/svn/llvm-project/clang-tools-extra/trunk@353380 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 329 insertions, 34 deletions

diff --git a/clangd/ClangdUnit.cpp b/clangd/ClangdUnit.cpp
index cb7fae5f..09ab772d 100644
--- a/clangd/ClangdUnit.cpp
+++ b/clangd/ClangdUnit.cpp
@@ -322,6 +322,7 @@ ParsedAST::build(std::unique_ptr<CompilerInvocation> CI,
                                             const clang::Diagnostic &Info) {
       return FixIncludes->fix(DiagLevl, Info);
     });
+    Clang->setExternalSemaSource(FixIncludes->unresolvedNameRecorder());
   }
 
   // Copy over the includes from the preamble, then combine with the
@@ -565,10 +566,10 @@ buildAST(PathRef FileName, std::unique_ptr<CompilerInvocation> Invocation,
     // 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,
diff --git a/clangd/IncludeFixer.cpp b/clangd/IncludeFixer.cpp
index 0f498884..adcb51a4 100644
--- a/clangd/IncludeFixer.cpp
+++ b/clangd/IncludeFixer.cpp
@@ -14,16 +14,47 @@
 #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)
@@ -42,6 +73,28 @@ std::vector<Fix> IncludeFixer::fix(DiagnosticsEngine::Level DiagLevel,
             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 {};
 }
@@ -74,11 +127,12 @@ std::vector<Fix> IncludeFixer::fixIncompleteType(const Type &T) const {
   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);
@@ -93,21 +147,151 @@ std::vector<Fix> IncludeFixer::fixesForSymbol(const Symbol &Sym) const {
   };
 
   std::vector<Fix> Fixes;
-  for (const auto &Inc : getRankedIncludes(Sym)) {
-    if (auto ToInclude = Inserted(Inc)) {
-      if (ToInclude->second)
-        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());
+  // 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(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());
+      }
     }
   }
   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
diff --git a/clangd/IncludeFixer.h b/clangd/IncludeFixer.h
index 740710cf..da292b56 100644
--- a/clangd/IncludeFixer.h
+++ b/clangd/IncludeFixer.h
@@ -14,6 +14,13 @@
 #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>
 
@@ -34,18 +41,44 @@ public:
   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
diff --git a/clangd/SourceCode.h b/clangd/SourceCode.h
index e6ce8c3b..82d94928 100644
--- a/clangd/SourceCode.h
+++ b/clangd/SourceCode.h
@@ -47,7 +47,7 @@ size_t lspLength(StringRef Code);
 /// The returned value is in the range [0, Code.size()].
 llvm::Expected<size_t>
 positionToOffset(llvm::StringRef Code, Position P,
-                 bool AllowColumnsBeyondLineLength = true);
+               bool AllowColumnsBeyondLineLength = true);
 
 /// Turn an offset in Code into a [line, column] pair.
 /// The offset must be in range [0, Code.size()].
@@ -110,7 +110,7 @@ Range halfOpenToRange(const SourceManager &SM, CharSourceRange R);
 // 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);
+                                                size_t Offset);
 
 /// From "a::b::c", return {"a::b::", "c"}. Scope is empty if there's no
 /// qualifier.
@@ -120,10 +120,10 @@ splitQualifiedName(llvm::StringRef QName);
 TextEdit replacementToEdit(StringRef Code, const tooling::Replacement &R);
 
 std::vector<TextEdit> replacementsToEdits(StringRef Code,
-                                          const tooling::Replacements &Repls);
+                                        const tooling::Replacements &Repls);
 
 TextEdit toTextEdit(const FixItHint &FixIt, const SourceManager &M,
-                    const LangOptions &L);
+                  const LangOptions &L);
 
 /// Get the canonical path of \p F.  This means:
 ///
@@ -136,7 +136,7 @@ TextEdit toTextEdit(const FixItHint &FixIt, const SourceManager &M,
 /// component that generate it, so that paths are normalized as much as
 /// possible.
 llvm::Optional<std::string> getCanonicalPath(const FileEntry *F,
-                                             const SourceManager &SourceMgr);
+                                           const SourceManager &SourceMgr);
 
 bool isRangeConsecutive(const Range &Left, const Range &Right);
 
diff --git a/unittests/clangd/DiagnosticsTests.cpp b/unittests/clangd/DiagnosticsTests.cpp
index ca544013..e9f24315 100644
--- a/unittests/clangd/DiagnosticsTests.cpp
+++ b/unittests/clangd/DiagnosticsTests.cpp
@@ -30,6 +30,11 @@ 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));
 }
@@ -281,6 +286,26 @@ main.cpp:2:3: error: something terrible happened)");
                   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 {
@@ -293,15 +318,8 @@ int main() {
 }
   )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(
@@ -346,6 +364,65 @@ int main() {
                        "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