[clangd] Use flags from open files when opening headers they include

[sammccall]

Summary

Currently our strategy for getting header compile flags is something like:

A) look for flags for the header in compile_commands.json

This basically never works, build systems don't generate this info.

B) try to match to an impl file in compile_commands.json and use its flags

This only (mostly) works if the headers are in the same project.

C) give up and use fallback flags

This kind of works for stdlib in the default configuration, and
otherwise doesn't.

Obviously there are big gaps here.

This patch inserts a new attempt between A and B: if the header is
transitively included by any open file (whether same project or not),
then we use its compile command.

This doesn't make any attempt to solve some related problems:

• parsing non-self-contained header files in context (importing PP state)
• using the compile flags of non-opened candidate files found in the index

Fixes https://github.com/clangd/clangd/issues/123
Fixes https://github.com/clangd/clangd/issues/695
See https://github.com/clangd/clangd/issues/519

[sammccall]

Record memory usage

[hokein]

thanks, this looks great.

clang-tools-extra/clangd/TUScheduler.cpp

187

I'm a bit confused, I don't get the meaning of the "This could also naturally live in the index", what lives in the index? my best guess is the include structure captured in background index.

202

maybe it is just me, it took me a while to understand the meaning of "invalidates the preamble" -- switching proxies usually indicates the change of CMD of the header, thus the preamble of the header is invalidated, is that right?

clang-tools-extra/clangd/Headers.h

 // When we build the preamble, we capture and store its include structure along
 // with the preamble data. When we use the preamble, we can copy its
 // IncludeStructure and use another collectIncludeStructureCallback() to fill
 // in any non-preamble inclusions.
 class IncludeStructure {
 public:
   std::vector<Inclusion> MainFileIncludes;
 
+  // Return all transitively reachable files.
+  llvm::ArrayRef<std::string> allHeaders() const { return RealPathNames; }
+
   // Return all transitively reachable files, and their minimum include depth.
   // All transitive includes (absolute paths), with their minimum include depth.
   // Root --> 0, #included file --> 1, etc.
   // Root is clang's name for a file, which may not be absolute.
   // Usually it should be SM.getFileEntryForID(SM.getMainFileID())->getName().
   llvm::StringMap<unsigned> includeDepth(llvm::StringRef Root) const;
 
   // This updates IncludeDepth(), but not MainFileIncludes.

clang-tools-extra/clangd/TUScheduler.h

 private:
   /// This class stores per-file data in the Files map.
   struct FileData;
 
 public:
   /// Responsible for retaining and rebuilding idle ASTs. An implementation is
   /// an LRU cache.
   class ASTCache;
+  /// Tracks headers included by open files, to get known-good compile commands.
+  class HeaderIncluderCache;
 
   // The file being built/processed in the current thread. This is a hack in
   // order to get the file name into the index implementations. Do not depend on
   // this inside clangd.
   // FIXME: remove this when there is proper index support via build system
   // integration.
   // FIXME: move to ClangdServer via createProcessingContext.
   static llvm::Optional<llvm::StringRef> getFileBeingProcessedInContext();
 
   void profile(MemoryTree &MT) const;
 
 private:
   void runWithSemaphore(llvm::StringRef Name, llvm::StringRef Path,
                         llvm::unique_function<void()> Action, Semaphore &Sem);
 
   const GlobalCompilationDatabase &CDB;
   Options Opts;
   std::unique_ptr<ParsingCallbacks> Callbacks; // not nullptr
   Semaphore Barrier;
   Semaphore QuickRunBarrier;
   llvm::StringMap<std::unique_ptr<FileData>> Files;
   std::unique_ptr<ASTCache> IdleASTs;
+  std::unique_ptr<HeaderIncluderCache> HeaderIncluders;
   // None when running tasks synchronously and non-None when running tasks
   // asynchronously.
   llvm::Optional<AsyncTaskRunner> PreambleTasks;
   llvm::Optional<AsyncTaskRunner> WorkerThreads;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clang-tools-extra/clangd/TUScheduler.cpp

 #include "llvm/ADT/FunctionExtras.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Allocator.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Threading.h"
 #include <algorithm>
+#include <atomic>
 #include <chrono>
 #include <condition_variable>
 #include <functional>
 #include <memory>
 #include <mutex>
 #include <queue>
 #include <string>
 #include <thread>
private:
 
   std::mutex Mut;
   unsigned MaxRetainedASTs;
   /// Items sorted in LRU order, i.e. first item is the most recently accessed
   /// one.
   std::vector<KVPair> LRU; /* GUARDED_BY(Mut) */
 };
 
+/// A map from header files to an opened "proxy" file that includes them.
+/// If you open the header, the compile command from the proxy file is used.
+///
+/// This inclusion information could also naturally live in the index, but there
+/// are advantages to using open files instead:
+///  - it's easier to achieve a *stable* choice of proxy, which is important
+///    to avoid invalidating the preamble
+///  - context-sensitive flags for libraries with multiple configurations
+///    (e.g. C++ stdlib sensitivity to -std version)
+///  - predictable behavior, e.g. guarantees that go-to-def landing on a header
+///    will have a suitable command available
+///  - fewer scaling problems to solve (project include graphs are big!)
+///
+/// Implementation details:
+/// - We only record this for mainfiles where the command was trustworthy
+///   (i.e. not inferred). This avoids a bad inference "infecting" other files.
+/// - Once we've picked a proxy file for a header, we stick with it until the
+///   proxy file is invalidated *and* a new candidate proxy file is built.
+///   Switching proxies is expensive, as the compile flags will (probably)
+///   change and therefore we'll end up rebuilding the header's preamble.
+/// - We don't capture the actual compile command, but just the filename we
+///   should query to get it. This avoids getting out of sync with the CDB.
+///
+/// All methods are threadsafe. In practice, update() comes from preamble
+/// threads, remove()s mostly from the main thread, and get() from ASTWorker.
+/// Writes are rare and reads are cheap, so we don't expect much contention.
+class TUScheduler::HeaderIncluderCache {
+  // We should be be a little careful how we store the include graph of open
+  // files, as each can have a large number of transitive headers.
+  // This representation is O(unique transitive source files).
+  llvm::BumpPtrAllocator Arena;
+  struct Association {
+    llvm::StringRef MainFile;
+    // Circular-linked-list of associations with the same mainFile.
+    // Null indicates that the mainfile was removed.
+    Association *Next;
+  };
+  llvm::StringMap<Association, llvm::BumpPtrAllocator &> HeaderToMain;
+  llvm::StringMap<Association *, llvm::BumpPtrAllocator &> MainToFirst;
+  std::atomic<size_t> UsedBytes; // Updated after writes.
+  mutable std::mutex Mu;
+
+  void invalidate(Association *First) {
+    Association *Current = First;
+    do {
+      Association *Next = Current->Next;
+      Current->Next = nullptr;
+      Current = Next;
+    } while (Current != First);
+  }
+
+  // Create the circular list and return the head of it.
+  Association *associate(llvm::StringRef MainFile,
+                         llvm::ArrayRef<std::string> Headers) {
+    Association *First = nullptr, *Prev = nullptr;
+    for (const std::string &Header : Headers) {
+      auto &Assoc = HeaderToMain[Header];
+      if (Assoc.Next)
+        continue; // Already has a valid association.
+
+      Assoc.MainFile = MainFile;
+      Assoc.Next = Prev;
+      Prev = &Assoc;
+      if (!First)
+        First = &Assoc;
+    }
+    if (First)
+      First->Next = Prev;
+    return First;
+  }
+
+  void updateMemoryUsage() {
+    auto StringMapHeap = [](const auto &Map) {
+      // StringMap stores the hashtable on the heap.
+      // It contains pointers to the entries, and a hashcode for each.
+      return Map.getNumBuckets() * (sizeof(void *) + sizeof(unsigned));
+    };
+    size_t Usage = Arena.getTotalMemory() + StringMapHeap(MainToFirst) +
+                   StringMapHeap(HeaderToMain) + sizeof(*this);
+    UsedBytes.store(Usage, std::memory_order_release);
+  }
+
+public:
+  HeaderIncluderCache() : HeaderToMain(Arena), MainToFirst(Arena) {
+    updateMemoryUsage();
+  }
+
+  // Associate each header with MainFile (unless already associated).
+  // Headers not in the list will have their associations removed.
+  void update(PathRef MainFile, llvm::ArrayRef<std::string> Headers) {
+    std::lock_guard<std::mutex> Lock(Mu);
+    auto It = MainToFirst.try_emplace(MainFile, nullptr);
+    Association *&First = It.first->second;
+    if (First)
+      invalidate(First);
+    First = associate(It.first->first(), Headers);
+    updateMemoryUsage();
+  }
+
+  // Mark MainFile as gone.
+  // This will *not* disassociate headers with MainFile immediately, but they
+  // will be eligible for association with other files that get update()d.
+  void remove(PathRef MainFile) {
+    std::lock_guard<std::mutex> Lock(Mu);
+    Association *&First = MainToFirst[MainFile];
+    if (First)
+      invalidate(First);
+  }
+
+  /// Get the mainfile associated with Header, or the empty string if none.
+  std::string get(PathRef Header) const {
+    std::lock_guard<std::mutex> Lock(Mu);
+    return HeaderToMain.lookup(Header).MainFile.str();
+  }
+
+  size_t getUsedBytes() const {
+    return UsedBytes.load(std::memory_order_acquire);
+  }
+};
+
 namespace {
+
+bool isReliable(const tooling::CompileCommand &Cmd) {
+  return Cmd.Heuristic.empty();
+}
+
 /// Threadsafe manager for updating a TUStatus and emitting it after each
 /// update.
 class SynchronizedTUStatus {
 public:
   SynchronizedTUStatus(PathRef FileName, ParsingCallbacks &Callbacks)
       : FileName(FileName), Callbacks(Callbacks) {}
 
   void update(llvm::function_ref<void(TUStatus &)> Mutator) {

 /// Responsible for building preambles. Whenever the thread is idle and the
 /// preamble is outdated, it starts to build a fresh preamble from the latest
 /// inputs. If RunSync is true, preambles are built synchronously in update()
 /// instead.
 class PreambleThread {
 public:
   PreambleThread(llvm::StringRef FileName, ParsingCallbacks &Callbacks,
                  bool StorePreambleInMemory, bool RunSync,
-                 SynchronizedTUStatus &Status, ASTWorker &AW)
+                 SynchronizedTUStatus &Status,
+                 TUScheduler::HeaderIncluderCache &HeaderIncluders,
+                 ASTWorker &AW)
       : FileName(FileName), Callbacks(Callbacks),
         StoreInMemory(StorePreambleInMemory), RunSync(RunSync), Status(Status),
-        ASTPeer(AW) {}
+        ASTPeer(AW), HeaderIncluders(HeaderIncluders) {}
 
   /// It isn't guaranteed that each requested version will be built. If there
   /// are multiple update requests while building a preamble, only the last one
   /// will be built.
   void update(std::unique_ptr<CompilerInvocation> CI, ParseInputs PI,
               std::vector<Diag> CIDiags, WantDiagnostics WantDiags) {
     Request Req = {std::move(CI), std::move(PI), std::move(CIDiags), WantDiags,
                    Context::current().clone()};
private:
 
   const Path FileName;
   ParsingCallbacks &Callbacks;
   const bool StoreInMemory;
   const bool RunSync;
 
   SynchronizedTUStatus &Status;
   ASTWorker &ASTPeer;
+  TUScheduler::HeaderIncluderCache &HeaderIncluders;
 };
 
 class ASTWorkerHandle;
 
 /// Owns one instance of the AST, schedules updates and reads of it.
 /// Also responsible for building and providing access to the preamble.
 /// Each ASTWorker processes the async requests sent to it on a separate
 /// dedicated thread.
 /// The ASTWorker that manages the AST is shared by both the processing thread
 /// and the TUScheduler. The TUScheduler should discard an ASTWorker when
 /// remove() is called, but its thread may be busy and we don't want to block.
 /// So the workers are accessed via an ASTWorkerHandle. Destroying the handle
 /// signals the worker to exit its run loop and gives up shared ownership of the
 /// worker.
 class ASTWorker {
   friend class ASTWorkerHandle;
   ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB,
-            TUScheduler::ASTCache &LRUCache, Semaphore &Barrier, bool RunSync,
-            const TUScheduler::Options &Opts, ParsingCallbacks &Callbacks);
+            TUScheduler::ASTCache &LRUCache,
+            TUScheduler::HeaderIncluderCache &HeaderIncluders,
+            Semaphore &Barrier, bool RunSync, const TUScheduler::Options &Opts,
+            ParsingCallbacks &Callbacks);
 
 public:
   /// Create a new ASTWorker and return a handle to it.
   /// The processing thread is spawned using \p Tasks. However, when \p Tasks
   /// is null, all requests will be processed on the calling thread
   /// synchronously instead. \p Barrier is acquired when processing each
   /// request, it is used to limit the number of actively running threads.
-  static ASTWorkerHandle create(PathRef FileName,
-                                const GlobalCompilationDatabase &CDB,
-                                TUScheduler::ASTCache &IdleASTs,
-                                AsyncTaskRunner *Tasks, Semaphore &Barrier,
-                                const TUScheduler::Options &Opts,
-                                ParsingCallbacks &Callbacks);
+  static ASTWorkerHandle
+  create(PathRef FileName, const GlobalCompilationDatabase &CDB,
+         TUScheduler::HeaderIncluderCache &HeaderIncluders,
+         const TUScheduler::Options &Opts, ParsingCallbacks &Callbacks);
   ~ASTWorker();
 
   void update(ParseInputs Inputs, WantDiagnostics, bool ContentChanged);
   void
   runWithAST(llvm::StringRef Name,
              llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action,
              TUScheduler::ASTActionInvalidation);
   bool blockUntilIdle(Deadline Timeout) const;
struct Request {
     llvm::Optional<Context> QueueCtx;
     llvm::Optional<UpdateType> Update;
     TUScheduler::ASTActionInvalidation InvalidationPolicy;
     Canceler Invalidate;
   };
 
   /// Handles retention of ASTs.
   TUScheduler::ASTCache &IdleASTs;
+  TUScheduler::HeaderIncluderCache &HeaderIncluders;
   const bool RunSync;
   /// Time to wait after an update to see whether another update obsoletes it.
   const DebouncePolicy UpdateDebounce;
   /// File that ASTWorker is responsible for.
   const Path FileName;
   /// Callback to create processing contexts for tasks.
   const std::function<Context(llvm::StringRef)> ContextProvider;
   const GlobalCompilationDatabase &CDB;
public:
   /// be schedule via the returned reference, i.e. only reads of the preamble
   /// are possible.
   std::shared_ptr<const ASTWorker> lock() { return Worker; }
 
 private:
   std::shared_ptr<ASTWorker> Worker;
 };
 
-ASTWorkerHandle ASTWorker::create(PathRef FileName,
-                                  const GlobalCompilationDatabase &CDB,
-                                  TUScheduler::ASTCache &IdleASTs,
-                                  AsyncTaskRunner *Tasks, Semaphore &Barrier,
-                                  const TUScheduler::Options &Opts,
-                                  ParsingCallbacks &Callbacks) {
-  std::shared_ptr<ASTWorker> Worker(new ASTWorker(
-      FileName, CDB, IdleASTs, Barrier, /*RunSync=*/!Tasks, Opts, Callbacks));
+ASTWorkerHandle
+ASTWorker::create(PathRef FileName, const GlobalCompilationDatabase &CDB,
+                  TUScheduler::HeaderIncluderCache &HeaderIncluders,
+  std::shared_ptr<ASTWorker> Worker(
+      new ASTWorker(FileName, CDB, IdleASTs, HeaderIncluders, Barrier,
+                    /*RunSync=*/!Tasks, Opts, Callbacks));
   if (Tasks) {
     Tasks->runAsync("ASTWorker:" + llvm::sys::path::filename(FileName),
                     [Worker]() { Worker->run(); });
     Tasks->runAsync("PreambleWorker:" + llvm::sys::path::filename(FileName),
                     [Worker]() { Worker->PreamblePeer.run(); });
   }
 
   return ASTWorkerHandle(std::move(Worker));
 }
 
 ASTWorker::ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB,
-                     TUScheduler::ASTCache &LRUCache, Semaphore &Barrier,
-                     bool RunSync, const TUScheduler::Options &Opts,
+                     TUScheduler::ASTCache &LRUCache,
+                     TUScheduler::HeaderIncluderCache &HeaderIncluders,
+                     Semaphore &Barrier, bool RunSync,
+                     const TUScheduler::Options &Opts,
                      ParsingCallbacks &Callbacks)
-    : IdleASTs(LRUCache), RunSync(RunSync), UpdateDebounce(Opts.UpdateDebounce),
-      FileName(FileName), ContextProvider(Opts.ContextProvider), CDB(CDB),
-      Callbacks(Callbacks), Barrier(Barrier), Done(false),
-      Status(FileName, Callbacks),
+    : IdleASTs(LRUCache), HeaderIncluders(HeaderIncluders), RunSync(RunSync),
+      UpdateDebounce(Opts.UpdateDebounce), FileName(FileName),
+      ContextProvider(Opts.ContextProvider), CDB(CDB), Callbacks(Callbacks),
+      Barrier(Barrier), Done(false), Status(FileName, Callbacks),
       PreamblePeer(FileName, Callbacks, Opts.StorePreamblesInMemory, RunSync,
-                   Status, *this) {
+                   Status, HeaderIncluders, *this) {
   // Set a fallback command because compile command can be accessed before
   // `Inputs` is initialized. Other fields are only used after initialization
   // from client inputs.
   FileInputs.CompileCommand = CDB.getFallbackCommand(FileName);
 }
 
 ASTWorker::~ASTWorker() {
   // Make sure we remove the cached AST, if any.
void ASTWorker::update(ParseInputs Inputs, WantDiagnostics WantDiags,
                        bool ContentChanged) {
   std::string TaskName = llvm::formatv("Update ({0})", Inputs.Version);
   auto Task = [=]() mutable {
     // Get the actual command as `Inputs` does not have a command.
     // FIXME: some build systems like Bazel will take time to preparing
     // environment to build the file, it would be nice if we could emit a
     // "PreparingBuild" status to inform users, it is non-trivial given the
     // current implementation.
-    if (auto Cmd = CDB.getCompileCommand(FileName))
-      Inputs.CompileCommand = *Cmd;
+    auto Cmd = CDB.getCompileCommand(FileName);
+    // If we don't have a reliable command for this file, it may be a header.
+    // Try to find a file that includes it, to borrow its command.
+    if (!Cmd || !isReliable(*Cmd)) {
+      std::string ProxyFile = HeaderIncluders.get(FileName);
+      if (!ProxyFile.empty()) {
+        auto ProxyCmd = CDB.getCompileCommand(ProxyFile);
+        if (!ProxyCmd || !isReliable(*ProxyCmd)) {
+          // This command is supposed to be reliable! It's probably gone.
+          HeaderIncluders.remove(ProxyFile);
+        } else {
+          // We have a reliable command for an including file, use it.
+          Cmd = tooling::transferCompileCommand(std::move(*ProxyCmd), FileName);
+        }
+      }
+    }
+    if (Cmd)
+      Inputs.CompileCommand = std::move(*Cmd);
     else
-      // FIXME: consider using old command if it's not a fallback one.
       Inputs.CompileCommand = CDB.getFallbackCommand(FileName);
 
     bool InputsAreTheSame =
         std::tie(FileInputs.CompileCommand, FileInputs.Contents) ==
         std::tie(Inputs.CompileCommand, Inputs.Contents);
     // Cached AST is invalidated.
     if (!InputsAreTheSame) {
       IdleASTs.take(this);
void PreambleThread::build(Request Req) {
   LatestBuild = clang::clangd::buildPreamble(
       FileName, *Req.CI, Inputs, StoreInMemory,
       [this, Version(Inputs.Version)](ASTContext &Ctx,
                                       std::shared_ptr<clang::Preprocessor> PP,
                                       const CanonicalIncludes &CanonIncludes) {
         Callbacks.onPreambleAST(FileName, Version, Ctx, std::move(PP),
                                 CanonIncludes);
       });
+  if (LatestBuild && isReliable(LatestBuild->CompileCommand))
+    HeaderIncluders.update(FileName, LatestBuild->Includes.allHeaders());
 }
 
 void ASTWorker::updatePreamble(std::unique_ptr<CompilerInvocation> CI,
                                ParseInputs PI,
                                std::shared_ptr<const PreambleData> Preamble,
                                std::vector<Diag> CIDiags,
                                WantDiagnostics WantDiags) {
   std::string TaskName = llvm::formatv("Build AST for ({0})", PI.Version);

 TUScheduler::TUScheduler(const GlobalCompilationDatabase &CDB,
                          const Options &Opts,
                          std::unique_ptr<ParsingCallbacks> Callbacks)
     : CDB(CDB), Opts(Opts),
       Callbacks(Callbacks ? move(Callbacks)
                           : std::make_unique<ParsingCallbacks>()),
       Barrier(Opts.AsyncThreadsCount), QuickRunBarrier(Opts.AsyncThreadsCount),
       IdleASTs(
-          std::make_unique<ASTCache>(Opts.RetentionPolicy.MaxRetainedASTs)) {
+          std::make_unique<ASTCache>(Opts.RetentionPolicy.MaxRetainedASTs)),
+      HeaderIncluders(std::make_unique<HeaderIncluderCache>()) {
   // Avoid null checks everywhere.
   if (!Opts.ContextProvider) {
     this->Opts.ContextProvider = [](llvm::StringRef) {
       return Context::current().clone();
     };
   }
   if (0 < Opts.AsyncThreadsCount) {
     PreambleTasks.emplace();

 bool TUScheduler::update(PathRef File, ParseInputs Inputs,
                          WantDiagnostics WantDiags) {
   std::unique_ptr<FileData> &FD = Files[File];
   bool NewFile = FD == nullptr;
   bool ContentChanged = false;
   if (!FD) {
     // Create a new worker to process the AST-related tasks.
     ASTWorkerHandle Worker =
-        ASTWorker::create(File, CDB, *IdleASTs,
+        ASTWorker::create(File, CDB, *IdleASTs, *HeaderIncluders,
                           WorkerThreads ? WorkerThreads.getPointer() : nullptr,
                           Barrier, Opts, *Callbacks);
     FD = std::unique_ptr<FileData>(
         new FileData{Inputs.Contents, std::move(Worker)});
     ContentChanged = true;
   } else if (FD->Contents != Inputs.Contents) {
     ContentChanged = true;
     FD->Contents = Inputs.Contents;
   }
   FD->Worker->update(std::move(Inputs), WantDiags, ContentChanged);
   return NewFile;
 }
 
 void TUScheduler::remove(PathRef File) {
   bool Removed = Files.erase(File);
   if (!Removed)
     elog("Trying to remove file from TUScheduler that is not tracked: {0}",
          File);
+  // We don't call HeaderIncluders.remove(File) here.
+  // If we did, we'd avoid potentially stale header/mainfile associations.
+  // However, it would mean that closing a mainfile could invalidate the
+  // preamble of several open headers.
 }
 
 llvm::StringMap<std::string> TUScheduler::getAllFileContents() const {
   llvm::StringMap<std::string> Results;
   for (auto &It : Files)
     Results.try_emplace(It.getKey(), It.getValue()->Contents);
   return Results;
 }

 
 void TUScheduler::profile(MemoryTree &MT) const {
   for (const auto &Elem : fileStats()) {
     MT.detail(Elem.first())
         .child("preamble")
         .addUsage(Opts.StorePreamblesInMemory ? Elem.second.UsedBytesPreamble
                                               : 0);
     MT.detail(Elem.first()).child("ast").addUsage(Elem.second.UsedBytesAST);
+    MT.child("header_includer_cache").addUsage(HeaderIncluders->getUsedBytes());
   }
 }
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/test/memory_tree.test

 # CHECK-NEXT:             "_total": {{[0-9]+}}
 # CHECK-NEXT:           },
 # CHECK-NEXT:           "preamble": {
 # CHECK-NEXT:             "_self": {{[0-9]+}},
 # CHECK-NEXT:             "_total": {{[0-9]+}}
 # CHECK-NEXT:           }
 # CHECK-NEXT:         },
 # CHECK-NEXT:         "_self": {{[0-9]+}},
-# CHECK-NEXT:         "_total": {{[0-9]+}}
-# CHECK-NEXT:       }
-# CHECK-NEXT:     }
-# CHECK-NEXT:   }
+# CHECK-NEXT:         "_total": {{[0-9]+}},
+# CHECK-NEXT:         "header_includer_cache": {
+# CHECK-NEXT:           "_self": {{[0-9]+}},
+# CHECK-NEXT:           "_total": {{[0-9]+}}
+# CHECK-NEXT:         }
+# CHECK-NEXT:       }
+# CHECK-NEXT:     }
+# CHECK-NEXT:   }
 ---
 {"jsonrpc":"2.0","id":3,"method":"shutdown"}
 ---
 {"jsonrpc":"2.0","method":"exit"}
 

clang-tools-extra/clangd/unittests/TUSchedulerTests.cpp

 //===-- TUSchedulerTests.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 "Annotations.h"
 #include "ClangdServer.h"
 #include "Diagnostics.h"
+#include "GlobalCompilationDatabase.h"
 #include "Matchers.h"
 #include "ParsedAST.h"
 #include "Preamble.h"
 #include "TUScheduler.h"
 #include "TestFS.h"
 #include "TestIndex.h"
 #include "support/Cancellation.h"
 #include "support/Context.h"

 #include <memory>
 #include <string>
 #include <utility>
 
 namespace clang {
 namespace clangd {
 namespace {
 
+using ::testing::AllOf;
 using ::testing::AnyOf;
+using ::testing::Contains;
 using ::testing::Each;
 using ::testing::ElementsAre;
 using ::testing::Eq;
 using ::testing::Field;
 using ::testing::IsEmpty;
+using ::testing::Not;
 using ::testing::Pair;
 using ::testing::Pointee;
 using ::testing::SizeIs;
 using ::testing::UnorderedElementsAre;
 
 MATCHER_P2(TUState, PreambleActivity, ASTActivity, "") {
   if (arg.PreambleActivity != PreambleActivity) {
     *result_listener << "preamblestate is "
S.runWithAST("test", File, [&](Expected<InputsAndAST> AST) {
     EXPECT_THAT(AST->AST.preambleVersion(), InputsV0);
     EXPECT_THAT(AST->Inputs.Version, InputsV1.str());
     RunASTAction.notify();
   });
   RunASTAction.wait();
   Ready.notify();
 }
 
+// If a header file is missing from the CDB (or inferred using heuristics), and
+// it's included by another open file, then we parse it using that files flags.
+TEST_F(TUSchedulerTests, IncluderCache) {
+  static std::string Main = testPath("main.cpp"), Main2 = testPath("main2.cpp"),
+                     Main3 = testPath("main3.cpp"),
+                     NoCmd = testPath("no_cmd.h"),
+                     Unreliable = testPath("unreliable.h"),
+                     OK = testPath("ok.h"),
+                     NotIncluded = testPath("not_included.h");
+  class NoHeadersCDB : public GlobalCompilationDatabase {
+    llvm::Optional<tooling::CompileCommand>
+    getCompileCommand(PathRef File) const override {
+      if (File == NoCmd || File == NotIncluded)
+        return llvm::None;
+      auto Basic = getFallbackCommand(File);
+      Basic.Heuristic.clear();
+      if (File == Unreliable) {
+        Basic.Heuristic = "not reliable";
+      } else if (File == Main) {
+        Basic.CommandLine.push_back("-DMAIN");
+      } else if (File == Main2) {
+        Basic.CommandLine.push_back("-DMAIN2");
+      } else if (File == Main3) {
+        Basic.CommandLine.push_back("-DMAIN3");
+      }
+      return Basic;
+    }
+  } CDB;
+  TUScheduler S(CDB, optsForTest());
+  auto GetFlags = [&](PathRef Header) {
+    S.update(Header, getInputs(Header, ";"), WantDiagnostics::Yes);
+    EXPECT_TRUE(S.blockUntilIdle(timeoutSeconds(10)));
+    tooling::CompileCommand Cmd;
+    S.runWithPreamble("GetFlags", Header, TUScheduler::StaleOrAbsent,
+                      [&](llvm::Expected<InputsAndPreamble> Inputs) {
+                        ASSERT_FALSE(!Inputs) << Inputs.takeError();
+                        Cmd = std::move(Inputs->Command);
+                      });
+    EXPECT_TRUE(S.blockUntilIdle(timeoutSeconds(10)));
+    return Cmd.CommandLine;
+  };
+
+  for (const auto &Path : {NoCmd, Unreliable, OK, NotIncluded})
+    FS.Files[Path] = ";";
+
+  // Initially these files have normal commands from the CDB.
+  EXPECT_THAT(GetFlags(Main), Contains("-DMAIN")) << "sanity check";
+  EXPECT_THAT(GetFlags(NoCmd), Not(Contains("-DMAIN"))) << "no includes yet";
+
+  // Now make Main include the others, and some should pick up its flags.
+  const char *AllIncludes = R"cpp(
+    #include "no_cmd.h"
+    #include "ok.h"
+    #include "unreliable.h"
+  )cpp";
+  S.update(Main, getInputs(Main, AllIncludes), WantDiagnostics::Yes);
+  EXPECT_TRUE(S.blockUntilIdle(timeoutSeconds(10)));
+  EXPECT_THAT(GetFlags(NoCmd), Contains("-DMAIN"))
+      << "Included from main file, has no own command";
+  EXPECT_THAT(GetFlags(Unreliable), Contains("-DMAIN"))
+      << "Included from main file, own command is heuristic";
+  EXPECT_THAT(GetFlags(OK), Not(Contains("-DMAIN")))
+      << "Included from main file, but own command is used";
+  EXPECT_THAT(GetFlags(NotIncluded), Not(Contains("-DMAIN")))
+      << "Not included from main file";
+
+  // Open another file - it won't overwrite the associations with Main.
+  std::string SomeIncludes = R"cpp(
+    #include "no_cmd.h"
+    #include "not_included.h"
+  )cpp";
+  S.update(Main2, getInputs(Main2, SomeIncludes), WantDiagnostics::Yes);
+  EXPECT_TRUE(S.blockUntilIdle(timeoutSeconds(10)));
+  EXPECT_THAT(GetFlags(NoCmd),
+              AllOf(Contains("-DMAIN"), Not(Contains("-DMAIN2"))))
+      << "mainfile association is stable";
+  EXPECT_THAT(GetFlags(NotIncluded),
+              AllOf(Contains("-DMAIN2"), Not(Contains("-DMAIN"))))
+      << "new headers are associated with new mainfile";
+
+  // Remove includes from main - this marks the associations as invalid but
+  // doesn't actually remove them until another preamble claims them.
+  S.update(Main, getInputs(Main, ""), WantDiagnostics::Yes);
+  EXPECT_TRUE(S.blockUntilIdle(timeoutSeconds(10)));
+  EXPECT_THAT(GetFlags(NoCmd),
+              AllOf(Contains("-DMAIN"), Not(Contains("-DMAIN2"))))
+      << "mainfile association not updated yet!";
+
+  // Open yet another file - this time it claims the associations.
+  S.update(Main3, getInputs(Main3, SomeIncludes), WantDiagnostics::Yes);
+  EXPECT_TRUE(S.blockUntilIdle(timeoutSeconds(10)));
+  EXPECT_THAT(GetFlags(NoCmd), Contains("-DMAIN3"))
+      << "association invalidated and then claimed by main3";
+  EXPECT_THAT(GetFlags(Unreliable), Contains("-DMAIN"))
+      << "association invalidated but not reclaimed";
+  EXPECT_THAT(GetFlags(NotIncluded), Contains("-DMAIN2"))
+      << "association still valid";
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang

clang/include/clang/Tooling/CompilationDatabase.h

public:
   getCompileCommands(StringRef FilePath) const override;
 
 private:
   /// This is built up to contain a single entry vector to be returned from
   /// getCompileCommands after adding the positional argument.
   std::vector<CompileCommand> CompileCommands;
 };
 
+/// Transforms a compile command so that it applies the same configuration to
+/// a different file. Most args are left intact, but tweaks may be needed
+/// to certain flags (-x, -std etc).
+tooling::CompileCommand transferCompileCommand(tooling::CompileCommand,
+                                               StringRef Filename);
+
 /// Returns a wrapped CompilationDatabase that defers to the provided one,
 /// but getCompileCommands() will infer commands for unknown files.
 /// The return value of getAllFiles() or getAllCompileCommands() is unchanged.
 /// See InterpolatingCompilationDatabase.cpp for details on heuristics.
 std::unique_ptr<CompilationDatabase>
     inferMissingCompileCommands(std::unique_ptr<CompilationDatabase>);
 
 /// Returns a wrapped CompilationDatabase that will add -target and -mode flags

clang/lib/Tooling/InterpolatingCompilationDatabase.cpp

if (Type == types::TY_INVALID && Std != LangStandard::lang_unspecified)
       Type = toType(LangStandard::getLangStandardForKind(Std).getLanguage());
     Type = foldType(*Type);
     // The contract is to store None instead of TY_INVALID.
     if (Type == types::TY_INVALID)
       Type = llvm::None;
   }
 
   // Produce a CompileCommand for \p filename, based on this one.
-  CompileCommand transferTo(StringRef Filename) const {
-    CompileCommand Result = Cmd;
+  // (This consumes the TransferableCommand just to avoid copying Cmd).
+  CompileCommand transferTo(StringRef Filename) && {
+    CompileCommand Result = std::move(Cmd);
+    Result.Heuristic = "inferred from " + Result.Filename;
     Result.Filename = std::string(Filename);
     bool TypeCertain;
     auto TargetType = guessType(Filename, &TypeCertain);
     // If the filename doesn't determine the language (.h), transfer with -x.
     if ((!TargetType || !TypeCertain) && Type) {
       // Use *Type, or its header variant if the file is a header.
       // Treat no/invalid extension as header (e.g. C++ standard library).
       TargetType =
CompileCommand transferTo(StringRef Filename) && {
     // --std flag may only be transferred if the language is the same.
     // We may consider "translating" these, e.g. c++11 -> c11.
     if (Std != LangStandard::lang_unspecified && foldType(TargetType) == Type) {
       Result.CommandLine.emplace_back((
           llvm::Twine(ClangCLMode ? "/std:" : "-std=") +
           LangStandard::getLangStandardForKind(Std).getName()).str());
     }
     Result.CommandLine.push_back(std::string(Filename));
-    Result.Heuristic = "inferred from " + Cmd.Filename;
     return Result;
   }
 
 private:
   // Determine whether the given command line is intended for the CL driver.
   static bool checkIsCLMode(ArrayRef<std::string> CmdLine) {
     // First look for --driver-mode.
     for (StringRef S : llvm::reverse(CmdLine)) {
getCompileCommands(StringRef Filename) const override {
     bool TypeCertain;
     auto Lang = guessType(Filename, &TypeCertain);
     if (!TypeCertain)
       Lang = types::TY_INVALID;
     auto ProxyCommands =
         Inner->getCompileCommands(Index.chooseProxy(Filename, foldType(Lang)));
     if (ProxyCommands.empty())
       return {};
-    return {TransferableCommand(ProxyCommands[0]).transferTo(Filename)};
+    return {transferCompileCommand(std::move(ProxyCommands.front()), Filename)};
   }
 
   std::vector<std::string> getAllFiles() const override {
     return Inner->getAllFiles();
   }
 
   std::vector<CompileCommand> getAllCompileCommands() const override {
     return Inner->getAllCompileCommands();
   }
 
 private:
   std::unique_ptr<CompilationDatabase> Inner;
   FileIndex Index;
 };
 
 } // namespace
 
 std::unique_ptr<CompilationDatabase>
 inferMissingCompileCommands(std::unique_ptr<CompilationDatabase> Inner) {
   return std::make_unique<InterpolatingCompilationDatabase>(std::move(Inner));
 }
 
+tooling::CompileCommand transferCompileCommand(CompileCommand Cmd,
+                                               StringRef Filename) {
+  return TransferableCommand(std::move(Cmd)).transferTo(Filename);
+}
+
 } // namespace tooling
 } // namespace clang

clang/unittests/Tooling/CompilationDatabaseTest.cpp

TEST_F(InterpolateTest, DriverModes) {
   add("foo.cpp", "clang-cl", "--driver-mode=gcc");
   add("bar.cpp", "clang", "--driver-mode=cl");
 
   // --driver-mode overrides should be respected.
   EXPECT_EQ(getCommand("foo.h"), "clang-cl -D foo.cpp --driver-mode=gcc -x c++-header");
   EXPECT_EQ(getCommand("bar.h"), "clang -D bar.cpp --driver-mode=cl /TP");
 }
 
+TEST(TransferCompileCommandTest, Smoke) {
+  CompileCommand Cmd;
+  Cmd.Filename = "foo.cc";
+  Cmd.CommandLine = {"clang", "-Wall", "foo.cc"};
+  Cmd.Directory = "dir";
+  CompileCommand Transferred = transferCompileCommand(std::move(Cmd), "foo.h");
+  EXPECT_EQ(Transferred.Filename, "foo.h");
+  EXPECT_THAT(Transferred.CommandLine,
+              ElementsAre("clang", "-Wall", "-x", "c++-header", "foo.h"));
+  EXPECT_EQ(Transferred.Directory, "dir");
+}
+
 TEST(CompileCommandTest, EqualityOperator) {
   CompileCommand CCRef("/foo/bar", "hello.c", {"a", "b"}, "hello.o");
   CompileCommand CCTest = CCRef;
 
   EXPECT_TRUE(CCRef == CCTest);
   EXPECT_FALSE(CCRef != CCTest);
 
   CCTest = CCRef;