[clangd] Cache include fixes for diagnostics caused by the same unresolved name or incomplete type.

[ioeric]

Summary

Multiple diagnostics can be caused by the same unresolved name or incomplete type,
especially if the code is copy-pasted without #includes. The cache can avoid making
repetitive index requests, and thus reduce latency and allow more diagnostics to be
fixed (we limit the number of index requests for each parse).

[sammccall]

clangd/IncludeFixer.cpp

130 ↗

(On Diff #186849)

oops - this seems broken (in both the old and new form). Symbol is a shallow reference, and it's not valid after lookup() returns.

We can fix here or separately... one option to fix is the ResolvedSymbol struct suggested above.

(The fuzzyFind case looks ok)

clangd/IncludeFixer.h

85 ↗

(On Diff #186849)

This seems pretty messy (the assumption that Fix depends only on the index lookup).
It saves some code now at the expense of being magic. If we want to e.g. insert qualifiers too, I worry it's going to (stop us || return incorrect cached results || lead to unneccesary cache misses) depending on what we do.

What would we need to store to calculate Fix?
Maybe a struct ResolvedSymbol with {scope, name, inserted header}? (or even the edit to insert the header)
If it's not hugely complicated, that seems both cleaner and more extensible - wdyt?

90 ↗

(On Diff #186849)

DenseMap<SymbolID, ...>?

[sammccall]

(big thumbs up to the caching overall of course!)

[ioeric]

• address review comments

[ioeric]

clangd/IncludeFixer.h

85 ↗

(On Diff #186849)

Yeah, surely this was too hacky ;)

Instead of a new struct, how about simply storing SymbolSlabs? We are already building symbol slabs for fuzzy find results. And there are some helpers that take only Symbol. WDYT?

[sammccall]

SymbolSlab is much cleaner, nice!

clangd/IncludeFixer.cpp

122 ↗

(On Diff #187205)

extract a function that maps SymbolID -> const SymbolSlab& and takes care of the caching?
(likewise for fuzzyfind)

clangd/IncludeFixer.h

87 ↗

(On Diff #187205)

nit: maybe drop the parenthetical here? I think it's more confusing than enlightening.

("assuming" can mean either "and we assume" or "if" in this context. Also it's not clear there's a better behavior even if results did change and queries are free.)

[ioeric]

• pulled cached index queries into functions

clang-tools-extra/trunk/clangd/IncludeFixer.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/StringMap.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
public:
   /// 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 all symbols. Fixes are deduplicated.
-  std::vector<Fix> fixesForSymbols(llvm::ArrayRef<Symbol> Syms) const;
+  std::vector<Fix> fixesForSymbols(const SymbolSlab &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;
   };
private:
   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;
+
+  // There can be multiple diagnostics that are caused by the same unresolved
+  // name or incomplete type in one parse, especially when code is
+  // copy-and-pasted without #includes. We cache the index results based on
+  // index requests.
+  mutable llvm::StringMap<SymbolSlab> FuzzyFindCache;
+  mutable llvm::DenseMap<SymbolID, SymbolSlab> LookupCache;
+  // Returns None if the number of index requests has reached the limit.
+  llvm::Optional<const SymbolSlab *>
+  fuzzyFindCached(const FuzzyFindRequest &Req) const;
+  llvm::Optional<const SymbolSlab *> lookupCached(const SymbolID &ID) const;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDE_FIXER_H

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

 #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/Optional.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FormatVariadic.h"
 #include <vector>
 
 namespace clang {
 namespace clangd {
 

 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) {
std::vector<Fix> IncludeFixer::fixIncompleteType(const Type &T) const {
   std::string TypeName = printQualifiedName(*TD);
   trace::Span Tracer("Fix include for incomplete type");
   SPAN_ATTACH(Tracer, "type", TypeName);
   vlog("Trying to fix include for incomplete type {0}", TypeName);
 
   auto ID = getSymbolID(TD);
   if (!ID)
     return {};
-  ++IndexRequestCount;
-  // FIXME: consider batching the requests for all diagnostics.
-  // FIXME: consider caching the lookup results.
-  LookupRequest Req;
-  Req.IDs.insert(*ID);
-  llvm::Optional<Symbol> Matched;
-  Index.lookup(Req, [&](const Symbol &Sym) {
-    if (Matched)
-      return;
-    Matched = Sym;
-  });
-
-  if (!Matched || Matched->IncludeHeaders.empty() || !Matched->Definition ||
-      Matched->CanonicalDeclaration.FileURI != Matched->Definition.FileURI)
+  llvm::Optional<const SymbolSlab *> Symbols = lookupCached(*ID);
+  if (!Symbols)
     return {};
-  return fixesForSymbols({*Matched});
+  const SymbolSlab &Syms = **Symbols;
+  std::vector<Fix> Fixes;
+  if (!Syms.empty()) {
+    auto &Matched = *Syms.begin();
+    if (!Matched.IncludeHeaders.empty() && Matched.Definition &&
+        Matched.CanonicalDeclaration.FileURI == Matched.Definition.FileURI)
+      Fixes = fixesForSymbols(Syms);
+  }
+  return Fixes;
 }
 
-std::vector<Fix>
-IncludeFixer::fixesForSymbols(llvm::ArrayRef<Symbol> Syms) const {
+std::vector<Fix> IncludeFixer::fixesForSymbols(const SymbolSlab &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)
std::vector<Fix> IncludeFixer::fixUnresolvedName() const {
 
   FuzzyFindRequest Req;
   Req.AnyScope = false;
   Req.Query = Unresolved.Name;
   Req.Scopes = Scopes;
   Req.RestrictForCodeCompletion = true;
   Req.Limit = 100;
 
+  if (llvm::Optional<const SymbolSlab *> Syms = fuzzyFindCached(Req))
+    return fixesForSymbols(**Syms);
+
+  return {};
+}
+
+
+llvm::Optional<const SymbolSlab *>
+IncludeFixer::fuzzyFindCached(const FuzzyFindRequest &Req) const {
+  auto ReqStr = llvm::formatv("{0}", toJSON(Req)).str();
+  auto I = FuzzyFindCache.find(ReqStr);
+  if (I != FuzzyFindCache.end())
+    return &I->second;
+
+  if (IndexRequestCount >= IndexRequestLimit)
+    return llvm::None;
+  IndexRequestCount++;
+
   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()));
+  auto E = FuzzyFindCache.try_emplace(ReqStr, std::move(Syms));
+  return &E.first->second;
+}
+
+llvm::Optional<const SymbolSlab *>
+IncludeFixer::lookupCached(const SymbolID &ID) const {
+  LookupRequest Req;
+  Req.IDs.insert(ID);
+
+  auto I = LookupCache.find(ID);
+  if (I != LookupCache.end())
+    return &I->second;
+
+  if (IndexRequestCount >= IndexRequestLimit)
+    return llvm::None;
+  IndexRequestCount++;
+
+  // FIXME: consider batching the requests for all diagnostics.
+  SymbolSlab::Builder Matches;
+  Index.lookup(Req, [&](const Symbol &Sym) { Matches.insert(Sym); });
+  auto Syms = std::move(Matches).build();
+
+  std::vector<Fix> Fixes;
+  if (!Syms.empty()) {
+    auto &Matched = *Syms.begin();
+    if (!Matched.IncludeHeaders.empty() && Matched.Definition &&
+        Matched.CanonicalDeclaration.FileURI == Matched.Definition.FileURI)
+      Fixes = fixesForSymbols(Syms);
+  }
+  auto E = LookupCache.try_emplace(ID, std::move(Syms));
+  return &E.first->second;
 }
 
 } // namespace clangd
 } // namespace clang

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

auto Index = buildIndexWithSymbol(
       SymbolWithHeader{"na::X", "unittest:///a.h", "\"a.h\""});
   TU.ExternalIndex = Index.get();
 
   EXPECT_THAT(
       TU.build().getDiagnostics(),
       UnorderedElementsAre(Diag(Test.range(), "no member named 'xy' in 'X'")));
 }
 
+TEST(IncludeFixerTest, UseCachedIndexResults) {
+  // As index results for the identical request are cached, more than 5 fixes
+  // are generated.
+  Annotations Test(R"cpp(
+$insert[[]]void foo() {
+  $x1[[X]] x;
+  $x2[[X]] x;
+  $x3[[X]] x;
+  $x4[[X]] x;
+  $x5[[X]] x;
+  $x6[[X]] x;
+  $x7[[X]] x;
+}
+
+class X;
+void bar(X *x) {
+  x$a1[[->]]f();
+  x$a2[[->]]f();
+  x$a3[[->]]f();
+  x$a4[[->]]f();
+  x$a5[[->]]f();
+  x$a6[[->]]f();
+  x$a7[[->]]f();
+}
+  )cpp");
+  auto TU = TestTU::withCode(Test.code());
+  auto Index =
+      buildIndexWithSymbol(SymbolWithHeader{"X", "unittest:///a.h", "\"a.h\""});
+  TU.ExternalIndex = Index.get();
+
+  auto Parsed = TU.build();
+  for (const auto &D : Parsed.getDiagnostics()) {
+    EXPECT_EQ(D.Fixes.size(), 1u);
+    EXPECT_EQ(D.Fixes[0].Message,
+              std::string("Add include \"a.h\" for symbol X"));
+  }
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang