[clangd] Add cache for FID to Header mappings

[kadircet]

Summary

Depends on D98242

[sammccall]

Some performance measurements...
(workload is PreambleCallback for clangd/XRefs.cpp in sync mode with a fixed baseline of 99b01cf28db9db1a3ec0e25367bd325b7aca6d43, opt build without asserts)

baseline: 1.21s
baseline+D98242: 1.25s
baseline+D98242+D98329: 1.21s
baseline+D98371: 1.02s

So this patch does indeed help, and cancels out the extra work done in D98242 with this workload at least.
Nevertheless I think the speedups from D98371 clearly justify the more invasive approach to caching, so we should do something like that instead. (We don't need both as it caches at a slightly higher level).

clang-tools-extra/clangd/index/SymbolCollector.cpp

792

this is correct but subtle: if we get to here we know the symbol does not have any special handling so it's safe to cache with the file Id alone

[kadircet]

abandoning in favor of D98371

clang-tools-extra/clangd/index/SymbolCollector.h

 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Index/IndexDataConsumer.h"
 #include "clang/Index/IndexSymbol.h"
 #include "clang/Sema/CodeCompleteConsumer.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Support/Regex.h"
 #include <functional>
+#include <string>
 
 namespace clang {
 namespace clangd {
 
 /// Collect declarations (symbols) from an AST.
 /// It collects most declarations except:
 /// - Implicit declarations
 /// - Anonymous declarations (anonymous enum/class/struct, etc)
private:
   // Heuristically headers that only want to be included via an umbrella.
   static bool isDontIncludeMeHeader(llvm::StringRef);
 
   // All Symbols collected from the AST.
   SymbolSlab::Builder Symbols;
   // File IDs for Symbol.IncludeHeaders.
   // The final spelling is calculated in finish().
   llvm::DenseMap<SymbolID, FileID> IncludeFiles;
+  // Caches FileID to header mappings, values are either verbatim headers or
+  // URIs. None in case of a bad header, e.g. not include-guarded.
+  llvm::DenseMap<FileID, llvm::Optional<std::string>> HeaderToInclude;
   void setIncludeLocation(const Symbol &S, SourceLocation);
   // Indexed macros, to be erased if they turned out to be include guards.
   llvm::DenseSet<const IdentifierInfo *> IndexedMacros;
   // All refs collected from the AST. It includes:
   //   1) symbols declared in the preamble and referenced from the main file (
   //     which is not a header), or
   //   2) symbols declared and referenced from the main file (which is a header)
   RefSlab::Builder Refs;

clang-tools-extra/clangd/index/SymbolCollector.cpp

if (Canonical.startswith("<") || Canonical.startswith("\"")) {
       if (Canonical == "<utility>" && S.Name == "move" &&
           S.Signature.contains(','))
         Canonical = "<algorithm>";
       return Canonical.str();
     }
     if (Canonical != Filename)
       return toURI(SM, Canonical, Opts);
   }
+  auto FIDMapping = HeaderToInclude.find(FID);
+  if (FIDMapping != HeaderToInclude.end())
+    return FIDMapping->second;
   if (!isSelfContainedHeader(FID)) {
     // A .inc or .def file is often included into a real header to define
     // symbols (e.g. LLVM tablegen files).
     if (Filename.endswith(".inc") || Filename.endswith(".def"))
-      return getIncludeHeader(S, SM.getFileID(SM.getIncludeLoc(FID)));
+      return HeaderToInclude[FID] =
+                 getIncludeHeader(S, SM.getFileID(SM.getIncludeLoc(FID)));
     // Conservatively refuse to insert #includes to files without guards.
-    return llvm::None;
+    return HeaderToInclude[FID] = llvm::None;
   }
   // Store system includes as verbatim. This enables making use of the same
   // index in different environments, e.g. a system header like <linux/dlm.h>
   // might resolve to different absolute paths, but the path relative to sysroot
   // will be the same.
   bool IsSystem = false;
   auto ShorterInclude =
       PP->getHeaderSearchInfo().suggestPathToFileForDiagnostics(FE, "",
                                                                 &IsSystem);
   if (IsSystem)
-    return "<" + ShorterInclude + ">";
+    return HeaderToInclude[FID] = "<" + ShorterInclude + ">";
   // Standard case: just insert the file itself.
-  return toURI(SM, Filename, Opts);
+  return HeaderToInclude[FID] = toURI(SM, Filename, Opts);
 }
 
 bool SymbolCollector::isSelfContainedHeader(FileID FID) {
   // The real computation (which will be memoized).
   auto Compute = [&] {
     const SourceManager &SM = ASTCtx->getSourceManager();
     const FileEntry *FE = SM.getFileEntryForID(FID);
     if (!FE)