[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

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

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

DenseMap<SymbolID, ...>?

[sammccall]

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

[ioeric]

• address review comments

[ioeric]

clangd/IncludeFixer.h

85

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

136–137

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

clangd/IncludeFixer.h

86

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

clangd/IncludeFixer.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/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
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. As fixes are purely dependent on index
+  // requests and index results at this point, we can cache fixes by index
+  // requests to avoid repetitive index queries (assuming index results are
+  // consistent during the single AST parse).
+  mutable llvm::StringMap<std::vector<Fix>> FuzzyReqToFixesCache;
+  mutable llvm::StringMap<std::vector<Fix>> LookupIDToFixesCache;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INCLUDE_FIXER_H

clangd/IncludeFixer.cpp

 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);
+
+  std::string IDStr = ID->str();
+  auto I = LookupIDToFixesCache.find(IDStr);
+  if (I != LookupIDToFixesCache.end())
+    return I->second;
+
+  if (IndexRequestCount++ >= IndexRequestLimit)
+    return {};
+  // FIXME: consider batching the requests for all diagnostics.
   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)
-    return {};
-  return fixesForSymbols({*Matched});
+  std::vector<Fix> Fixes;
+  if (Matched && !Matched->IncludeHeaders.empty() && Matched->Definition &&
+      Matched->CanonicalDeclaration.FileURI == Matched->Definition.FileURI)
+    Fixes = fixesForSymbols({*Matched});
+  LookupIDToFixesCache[IDStr] = Fixes;
+  return Fixes;
 }
 
 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);
std::vector<Fix> IncludeFixer::fixUnresolvedName() const {
 
   FuzzyFindRequest Req;
   Req.AnyScope = false;
   Req.Query = Unresolved.Name;
   Req.Scopes = Scopes;
   Req.RestrictForCodeCompletion = true;
   Req.Limit = 100;
 
+  auto ReqStr = llvm::formatv("{0}", toJSON(Req)).str();
+  auto I = FuzzyReqToFixesCache.find(ReqStr);
+  if (I != FuzzyReqToFixesCache.end())
+    return I->second;
+
+  if (IndexRequestCount++ >= IndexRequestLimit)
+    return {};
+
   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 Fixes = fixesForSymbols(std::vector<Symbol>(Syms.begin(), Syms.end()));
+
+  FuzzyReqToFixesCache[ReqStr] = Fixes;
+  return Fixes;
 }
 
 } // namespace clangd
 } // namespace clang

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