[clangd] reuse preambles from other files when possible

[qchateau]

Summary

Keep a store of the preambles of all opened filed, plus
a configurable number of previously used preambles (default 1).
When building the AST for a TU, if the preamble for this
TU is not yet built, look through the stored premables
to find the best compatible preamble and use this
preamble to speed-up the AST build.

[qchateau]

This is a revisit of D97417 which is a bit out of date and fell into oblivion.
I've been using a forked version of clangd including this change for months on my day-to-day work and it does significantly improve my experience.
Some numbers showing the kind of improvement you can expect from this change can be found in D97417, they are still relevant.

[qchateau]

Resolve conflicts, fix formatting, simplify patch

[qchateau]

Small correction

[nridge]

@qchateau How should I interpret the abandoning of this patch -- did you run into a problem with the approach, or just don't have the time / interest to pursue it further?

[qchateau]

@nridge after rebasing this change for several months, I find it less and less useful. It seems both clangd and the IDE I'm using are making significant improvements that make this changes less and less impactful.
I closed this revision as I feel that it now passed the threshold where the annoyance of maintaining it is greater than the return I'm getting from it

clang-tools-extra/clangd/ClangdServer.h

 //===--- ClangdServer.h - Main clangd server code ----------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
createConfiguredContextProvider(const config::Provider *Provider,
                                   ClangdServer::Callbacks *);
 
   struct Options {
     /// To process requests asynchronously, ClangdServer spawns worker threads.
     /// If this is zero, no threads are spawned. All work is done on the calling
     /// thread, and callbacks are invoked before "async" functions return.
     unsigned AsyncThreadsCount = getDefaultAsyncThreadsCount();
 
+    // Number of preambles of closed files to keep in the cache.
+    unsigned ClosedPreambleCacheSize = 1;
+
     /// AST caching policy. The default is to keep up to 3 ASTs in memory.
     ASTRetentionPolicy RetentionPolicy;
 
     /// Cached preambles are potentially large. If false, store them on disk.
     bool StorePreamblesInMemory = true;
 
     /// If true, ClangdServer builds a dynamic in-memory index for symbols in
     /// opened files and uses the index to augment code completion results.

clang-tools-extra/clangd/ClangdServer.cpp

 //===--- ClangdServer.cpp - Main clangd server code --------------*- 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
 //
 //===-------------------------------------------------------------------===//
 

 
 } // namespace
 
 ClangdServer::Options ClangdServer::optsForTest() {
   ClangdServer::Options Opts;
   Opts.UpdateDebounce = DebouncePolicy::fixed(/*zero*/ {});
   Opts.StorePreamblesInMemory = true;
   Opts.AsyncThreadsCount = 4; // Consistent!
+  Opts.ClosedPreambleCacheSize = 0;
   return Opts;
 }
 
 ClangdServer::Options::operator TUScheduler::Options() const {
   TUScheduler::Options Opts;
   Opts.AsyncThreadsCount = AsyncThreadsCount;
+  Opts.ClosedPreambleCacheSize = ClosedPreambleCacheSize;
   Opts.RetentionPolicy = RetentionPolicy;
   Opts.StorePreamblesInMemory = StorePreamblesInMemory;
   Opts.UpdateDebounce = UpdateDebounce;
   Opts.ContextProvider = ContextProvider;
   return Opts;
 }
 
 ClangdServer::ClangdServer(const GlobalCompilationDatabase &CDB,

clang-tools-extra/clangd/ParsedAST.cpp

 //===--- ParsedAST.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
 //
 //===----------------------------------------------------------------------===//
 
private:
 
   const std::vector<Inclusion> Includes;
   PPCallbacks *Delegate;
   const SourceManager &SM;
   Preprocessor &PP;
   std::vector<syntax::Token> MainFileTokens;
 };
 
+llvm::Expected<MainFileMacros>
+scanMainFileMacros(llvm::StringRef Contents,
+                   const tooling::CompileCommand &Cmd) {
+  class EmptyFS : public ThreadsafeFS {
+  private:
+    llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> viewImpl() const override {
+      return new llvm::vfs::InMemoryFileSystem;
+    }
+  };
+  EmptyFS FS;
+  // Build and run Preprocessor over the preamble.
+  ParseInputs PI;
+  PI.Contents = Contents.str();
+  PI.TFS = &FS;
+  PI.CompileCommand = Cmd;
+  IgnoringDiagConsumer IgnoreDiags;
+  auto CI = buildCompilerInvocation(PI, IgnoreDiags);
+  if (!CI)
+    return error("failed to create compiler invocation");
+  CI->getDiagnosticOpts().IgnoreWarnings = true;
+  auto ContentsBuffer = llvm::MemoryBuffer::getMemBuffer(Contents);
+  // This means we're scanning (though not preprocessing) the preamble section
+  // twice. However, it's important to precisely follow the preamble bounds used
+  // elsewhere.
+  auto Bounds = ComputePreambleBounds(*CI->getLangOpts(), *ContentsBuffer, 0);
+  auto PreambleContents =
+      llvm::MemoryBuffer::getMemBufferCopy(Contents.substr(0, Bounds.Size));
+  auto Clang = prepareCompilerInstance(
+      std::move(CI), nullptr, std::move(PreambleContents),
+      // Provide an empty FS to prevent preprocessor from performing IO. This
+      // also implies missing resolved paths for includes.
+      FS.view(llvm::None), IgnoreDiags);
+  if (Clang->getFrontendOpts().Inputs.empty())
+    return error("compiler instance had no inputs");
+  // We are only interested in main file includes.
+  Clang->getPreprocessorOpts().SingleFileParseMode = true;
+  PreprocessOnlyAction Action;
+  if (!Action.BeginSourceFile(*Clang, Clang->getFrontendOpts().Inputs[0]))
+    return error("failed BeginSourceFile");
+
+  MainFileMacros Macros;
+  Clang->getPreprocessor().addPPCallbacks(
+      std::make_unique<CollectMainFileMacros>(Clang->getSourceManager(),
+                                              Macros));
+
+  if (llvm::Error Err = Action.Execute())
+    return std::move(Err);
+  Action.EndSourceFile();
+
+  return Macros;
+}
+
 } // namespace
 
 llvm::Optional<ParsedAST>
 ParsedAST::build(llvm::StringRef Filename, const ParseInputs &Inputs,
                  std::unique_ptr<clang::CompilerInvocation> CI,
                  llvm::ArrayRef<Diag> CompilerInvocationDiags,
                  std::shared_ptr<const PreambleData> Preamble) {
   trace::Span Tracer("BuildAST");
ParsedAST::build(llvm::StringRef Filename, const ParseInputs &Inputs,
   // Important: collectIncludeStructure is registered *after* ReplayPreamble!
   // Otherwise we would collect the replayed includes again...
   // (We can't *just* use the replayed includes, they don't have Resolved path).
   Clang->getPreprocessor().addPPCallbacks(
       Includes.collect(Clang->getSourceManager()));
   // Copy over the macros in the preamble region of the main file, and combine
   // with non-preamble macros below.
   MainFileMacros Macros;
-  if (Preamble)
+  if (Preamble && Preamble->CompileCommand.Filename == Filename) {
     Macros = Preamble->Macros;
+  } else if (Preamble) {
+    auto EM = scanMainFileMacros(Inputs.Contents, Inputs.CompileCommand);
+    if (!EM) {
+      elog("Failed to scan macros of {0}: {1}", Filename, EM.takeError());
+    } else {
+      Macros = std::move(*EM);
+    }
+  }
   Clang->getPreprocessor().addPPCallbacks(
       std::make_unique<CollectMainFileMacros>(Clang->getSourceManager(),
                                               Macros));
 
   std::vector<PragmaMark> Marks;
   // FIXME: We need to patch the marks for stale preambles.
   if (Preamble)
     Marks = Preamble->Marks;

clang-tools-extra/clangd/TUScheduler.h

 //===--- TUScheduler.h -------------------------------------------*-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
 //
 //===----------------------------------------------------------------------===//
 

 public:
   struct Options {
     /// Number of concurrent actions.
     /// Governs per-file worker threads and threads spawned for other tasks.
     /// (This does not prevent threads being spawned, but rather blocks them).
     /// If 0, executes actions synchronously on the calling thread.
     unsigned AsyncThreadsCount = getDefaultAsyncThreadsCount();
 
+    // Number of preambles of closed files to keep in the cache.
+    unsigned ClosedPreambleCacheSize = 1;
+
     /// Cache (large) preamble data in RAM rather than temporary files on disk.
     bool StorePreamblesInMemory = false;
 
     /// Time to wait after an update to see if another one comes along.
     /// This tries to ensure we rebuild once the user stops typing.
     DebouncePolicy UpdateDebounce;
 
     /// Determines when to keep idle ASTs in memory for future use.
private:
   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;
+  /// Store all known preambles
+  class PreambleStore;
 
   // 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;
+  std::unique_ptr<PreambleStore> Preambles;
   // None when running tasks synchronously and non-None when running tasks
   // asynchronously.
   llvm::Optional<AsyncTaskRunner> PreambleTasks;
   llvm::Optional<AsyncTaskRunner> WorkerThreads;
   // Used to create contexts for operations that are not bound to a particular
   // file (e.g. index queries).
   std::string LastActiveFile;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clang-tools-extra/clangd/TUScheduler.cpp

 //===--- TUScheduler.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
 //
 //===----------------------------------------------------------------------===//
 // TUScheduler manages a worker per active file. This ASTWorker processes
std::string get(PathRef Header) const {
     return HeaderToMain.lookup(Header).MainFile.str();
   }
 
   size_t getUsedBytes() const {
     return UsedBytes.load(std::memory_order_acquire);
   }
 };
 
+class TUScheduler::PreambleStore {
+public:
+  struct Entry {
+    std::shared_ptr<const PreambleData> Preamble;
+    size_t Score;
+    Path FileName;
+
+    bool operator>(const Entry &Other) const { return Score > Other.Score; }
+  };
+
+  explicit PreambleStore(size_t ClosedPreamblesToKeep): ClosedPreamblesToKeep(ClosedPreamblesToKeep) {}
+
+  auto getAll() {
+    std::unique_lock<std::mutex> Lock(Mut);
+    return Store;
+  }
+
+  void push(PathRef FileName, std::shared_ptr<const PreambleData> Preamble) {
+    std::unique_lock<std::mutex> Lock(Mut);
+    auto It = llvm::find_if(
+        Store, [&](const auto &Item) { return Item.FileName == FileName; });
+    if (It == Store.end()) {
+      Store.push_back(Entry{std::move(Preamble), 0, FileName.str()});
+      popWorstPreambles();
+    }
+    else {
+      It->Preamble = std::move(Preamble);
+    }
+    vlog("Store contains {0} preambles", Store.size());
+  }
+
+  void hit(PathRef FileName) {
+    std::unique_lock<std::mutex> Lock(Mut);
+    auto It = llvm::find_if(
+        Store, [&](const auto &Item) { return Item.FileName == FileName; });
+    if (It == Store.end()) {
+      return;
+    }
+    It->Score++;
+  }
+
+private:
+  void popWorstPreambles() {
+    auto Begin = llvm::partition(
+        Store, [](const auto &Item) { return Item.Preamble.use_count() > 1; });
+    if (static_cast<size_t>(std::distance(Begin, Store.end())) <=
+        ClosedPreamblesToKeep) {
+      return;
+    }
+    auto Nth = Begin + ClosedPreamblesToKeep;
+    std::nth_element(Begin, Nth, Store.end(), std::greater<Entry>());
+    Store.erase(Nth, Store.end());
+  }
+
+  std::mutex Mut;
+  std::vector<Entry> Store;
+  size_t ClosedPreamblesToKeep;
+};
+
 namespace {
 
 bool isReliable(const tooling::CompileCommand &Cmd) {
   return Cmd.Heuristic.empty();
 }
 
 /// Threadsafe manager for updating a TUStatus and emitting it after each
 /// update.

 /// 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,
             TUScheduler::HeaderIncluderCache &HeaderIncluders,
-            Semaphore &Barrier, bool RunSync, const TUScheduler::Options &Opts,
+            TUScheduler::PreambleStore &Preambles, 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,
          TUScheduler::HeaderIncluderCache &HeaderIncluders,
-         AsyncTaskRunner *Tasks, Semaphore &Barrier,
-         const TUScheduler::Options &Opts, ParsingCallbacks &Callbacks);
+         TUScheduler::PreambleStore &Preambles, AsyncTaskRunner *Tasks,
+         Semaphore &Barrier, 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;
 
   std::shared_ptr<const PreambleData> getPossiblyStalePreamble(
       std::shared_ptr<const ASTSignals> *ASTSignals = nullptr) const;
+  std::shared_ptr<const PreambleData> getBestPreamble(
+      std::shared_ptr<const ASTSignals> *ASTSignals = nullptr) const;
 
   /// Used to inform ASTWorker about a new preamble build by PreambleThread.
   /// Diagnostics are only published through this callback. This ensures they
   /// are always for newer versions of the file, as the callback gets called in
   /// the same order as update requests.
   void updatePreamble(std::unique_ptr<CompilerInvocation> CI, ParseInputs PI,
                       std::shared_ptr<const PreambleData> Preamble,
                       std::vector<Diag> CIDiags, WantDiagnostics WantDiags);
private:
   /// Determines the next action to perform.
   /// All actions that should never run are discarded.
   /// Returns a deadline for the next action. If it's expired, run now.
   /// scheduleLocked() is called again at the deadline, or if requests arrive.
   Deadline scheduleLocked();
   /// Should the first task in the queue be skipped instead of run?
   bool shouldSkipHeadLocked() const;
 
+  /// Get all preambles that may be used to accelerate the AST build
+  std::vector<TUScheduler::PreambleStore::Entry> getCompatiblePreambles() const;
+
   struct Request {
     llvm::unique_function<void()> Action;
     std::string Name;
     steady_clock::time_point AddTime;
     Context Ctx;
     llvm::Optional<Context> QueueCtx;
     llvm::Optional<UpdateType> Update;
     TUScheduler::ASTActionInvalidation InvalidationPolicy;
     Canceler Invalidate;
   };
 
   /// Handles retention of ASTs.
   TUScheduler::ASTCache &IdleASTs;
   TUScheduler::HeaderIncluderCache &HeaderIncluders;
+  TUScheduler::PreambleStore &Preambles;
   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;

 private:
   std::shared_ptr<ASTWorker> Worker;
 };
 
 ASTWorkerHandle
 ASTWorker::create(PathRef FileName, const GlobalCompilationDatabase &CDB,
                   TUScheduler::ASTCache &IdleASTs,
                   TUScheduler::HeaderIncluderCache &HeaderIncluders,
-                  AsyncTaskRunner *Tasks, Semaphore &Barrier,
-                  const TUScheduler::Options &Opts,
+                  TUScheduler::PreambleStore &Preambles, AsyncTaskRunner *Tasks,
+                  Semaphore &Barrier, const TUScheduler::Options &Opts,
                   ParsingCallbacks &Callbacks) {
-  std::shared_ptr<ASTWorker> Worker(
-      new ASTWorker(FileName, CDB, IdleASTs, HeaderIncluders, Barrier,
-                    /*RunSync=*/!Tasks, Opts, Callbacks));
+  std::shared_ptr<ASTWorker> Worker(new ASTWorker(
+      FileName, CDB, IdleASTs, HeaderIncluders, Preambles, Barrier,
   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,
                      TUScheduler::HeaderIncluderCache &HeaderIncluders,
-                     Semaphore &Barrier, bool RunSync,
-                     const TUScheduler::Options &Opts,
+                     TUScheduler::PreambleStore &Preambles, Semaphore &Barrier,
+                     bool RunSync, const TUScheduler::Options &Opts,
                      ParsingCallbacks &Callbacks)
-    : IdleASTs(LRUCache), HeaderIncluders(HeaderIncluders), RunSync(RunSync),
+    : IdleASTs(LRUCache), HeaderIncluders(HeaderIncluders),
+      Preambles(Preambles), 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, 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.
if (!Invocation) {
       // Make sure anyone waiting for the preamble gets notified it could not be
       // built.
       PreambleCV.notify_all();
       return;
     }
 
     PreamblePeer.update(std::move(Invocation), std::move(Inputs),
                         std::move(CompilerInvocationDiags), WantDiags);
+
     std::unique_lock<std::mutex> Lock(Mutex);
     PreambleCV.wait(Lock, [this] {
       // Block until we reiceve a preamble request, unless a preamble already
       // exists, as patching an empty preamble would imply rebuilding it from
       // scratch.
+      // It is also acceptable to unblock is we have compatible preambles
+      // that may be used to accelerate the AST build.
       // We block here instead of the consumer to prevent any deadlocks. Since
       // LatestPreamble is only populated by ASTWorker thread.
-      return LatestPreamble || !PreambleRequests.empty() || Done;
+      return LatestPreamble || !PreambleRequests.empty() ||
+             !getCompatiblePreambles().empty() || Done;
     });
     return;
   };
   startTask(TaskName, std::move(Task), UpdateType{WantDiags, ContentChanged},
             TUScheduler::NoInvalidation);
 }
 
 void ASTWorker::runWithAST(
auto Task = [=, Action = std::move(Action)]() mutable {
     if (!AST) {
       StoreDiags CompilerInvocationDiagConsumer;
       std::unique_ptr<CompilerInvocation> Invocation =
           buildCompilerInvocation(FileInputs, CompilerInvocationDiagConsumer);
       // Try rebuilding the AST.
       vlog("ASTWorker rebuilding evicted AST to run {0}: {1} version {2}", Name,
            FileName, FileInputs.Version);
       // FIXME: We might need to build a patched ast once preamble thread starts
-      // running async. Currently getPossiblyStalePreamble below will always
+      // running async. Currently getBestPreamble below will always
       // return a compatible preamble as ASTWorker::update blocks.
       llvm::Optional<ParsedAST> NewAST;
       if (Invocation) {
         NewAST = ParsedAST::build(FileName, FileInputs, std::move(Invocation),
                                   CompilerInvocationDiagConsumer.take(),
-                                  getPossiblyStalePreamble());
+                                  getBestPreamble());
         ++ASTBuildCount;
       }
       AST = NewAST ? std::make_unique<ParsedAST>(std::move(*NewAST)) : nullptr;
     }
     // Make sure we put the AST back into the LRU cache.
     auto _ = llvm::make_scope_exit(
         [&AST, this]() { IdleASTs.put(this, std::move(*AST)); });
     // Run the user-provided action.
if (!LatestPreamble || Preamble != *LatestPreamble) {
       std::lock_guard<std::mutex> Lock(Mutex);
       // LatestPreamble might be the last reference to old preamble, do not
       // trigger destructor while holding the lock.
       if (LatestPreamble)
         std::swap(*LatestPreamble, Preamble);
       else
         LatestPreamble = std::move(Preamble);
     }
+    Preambles.push(FileName, *LatestPreamble);
     // Notify anyone waiting for a preamble.
     PreambleCV.notify_all();
     // Give up our ownership to old preamble before starting expensive AST
     // build.
     Preamble.reset();
     // We only need to build the AST if diagnostics were requested.
     if (WantDiags == WantDiagnostics::No)
       return;

 std::shared_ptr<const PreambleData> ASTWorker::getPossiblyStalePreamble(
     std::shared_ptr<const ASTSignals> *ASTSignals) const {
   std::lock_guard<std::mutex> Lock(Mutex);
   if (ASTSignals)
     *ASTSignals = LatestASTSignals;
   return LatestPreamble ? *LatestPreamble : nullptr;
 }
 
+std::vector<TUScheduler::PreambleStore::Entry>
+ASTWorker::getCompatiblePreambles() const {
+  auto AllPreamblesEntries = Preambles.getAll();
+  auto End = llvm::remove_if(AllPreamblesEntries, [&](const auto &Item) {
+    auto TransferedCmd = tooling::transferCompileCommand(
+        Item.Preamble->CompileCommand, FileName);
+    return TransferedCmd != FileInputs.CompileCommand;
+  });
+  AllPreamblesEntries.erase(End, AllPreamblesEntries.end());
+  return AllPreamblesEntries;
+}
+
+std::shared_ptr<const PreambleData> ASTWorker::getBestPreamble(
+    std::shared_ptr<const ASTSignals> *ASTSignals) const {
+  if (auto Preamble = getPossiblyStalePreamble(ASTSignals)) {
+    vlog("Best premable is the real one");
+    return Preamble;
+  }
+
+  auto CompatiblePreambles = getCompatiblePreambles();
+  vlog("Looking for the best of {0} preambles ...", CompatiblePreambles.size());
+  if (CompatiblePreambles.empty()) {
+    vlog("No compatible preamble");
+    return nullptr;
+  }
+
+  auto Best = CompatiblePreambles.begin();
+  auto BestPatch =
+      PreamblePatch::createFullPatch(FileName, FileInputs, *Best->Preamble);
+
+  for (auto It = Best + 1; It != CompatiblePreambles.end(); ++It) {
+    auto Patch =
+        PreamblePatch::createFullPatch(FileName, FileInputs, *It->Preamble);
+    if (Patch.preambleIncludes().size() > BestPatch.preambleIncludes().size()) {
+      BestPatch = std::move(Patch);
+      Best = It;
+    }
+  }
+
+  vlog("Using preamble from: {0}", Best->FileName);
+  Preambles.hit(Best->FileName);
+  return Best->Preamble;
+}
+
 void ASTWorker::waitForFirstPreamble() const {
   std::unique_lock<std::mutex> Lock(Mutex);
   PreambleCV.wait(Lock, [this] { return LatestPreamble.hasValue() || Done; });
 }
 
 tooling::CompileCommand ASTWorker::getCurrentCompileCommand() const {
   std::unique_lock<std::mutex> Lock(Mutex);
   return FileInputs.CompileCommand;
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)),
-      HeaderIncluders(std::make_unique<HeaderIncluderCache>()) {
+      HeaderIncluders(std::make_unique<HeaderIncluderCache>()),
+      Preambles(std::make_unique<PreambleStore>(Opts.ClosedPreambleCacheSize)) {
   // 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, *HeaderIncluders,
+        ASTWorker::create(File, CDB, *IdleASTs, *HeaderIncluders, *Preambles,
                           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;
void TUScheduler::runWithPreamble(llvm::StringRef Name, PathRef File,
   }
   LastActiveFile = File.str();
 
   if (!PreambleTasks) {
     trace::Span Tracer(Name);
     SPAN_ATTACH(Tracer, "file", File);
     std::shared_ptr<const ASTSignals> Signals;
     std::shared_ptr<const PreambleData> Preamble =
-        It->second->Worker->getPossiblyStalePreamble(&Signals);
+        It->second->Worker->getBestPreamble(&Signals);
     WithContext WithProvidedContext(Opts.ContextProvider(File));
     Action(InputsAndPreamble{It->second->Contents,
                              It->second->Worker->getCurrentCompileCommand(),
                              Preamble.get(), Signals.get()});
     return;
   }
 
   std::shared_ptr<const ASTWorker> Worker = It->second->Worker.lock();
auto Task = [Worker, Consistency, Name = Name.str(), File = File.str(),
     std::shared_ptr<const PreambleData> Preamble;
     if (Consistency == PreambleConsistency::Stale) {
       // Wait until the preamble is built for the first time, if preamble
       // is required. This avoids extra work of processing the preamble
       // headers in parallel multiple times.
       Worker->waitForFirstPreamble();
     }
     std::shared_ptr<const ASTSignals> Signals;
-    Preamble = Worker->getPossiblyStalePreamble(&Signals);
+    Preamble = Worker->getBestPreamble(&Signals);
 
     std::lock_guard<Semaphore> BarrierLock(Barrier);
     WithContext Guard(std::move(Ctx));
     trace::Span Tracer(Name);
     SPAN_ATTACH(Tracer, "file", File);
     WithContext WithProvidedContext(Opts.ContextProvider(File));
     Action(InputsAndPreamble{Contents, Command, Preamble.get(), Signals.get()});
   };

clang-tools-extra/clangd/tool/ClangdMain.cpp

 //===--- ClangdMain.cpp - clangd server loop ------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 

 opt<unsigned> WorkerThreadsCount{
     "j",
     cat(Misc),
     desc("Number of async workers used by clangd. Background index also "
          "uses this many workers."),
     init(getDefaultAsyncThreadsCount()),
 };
 
+opt<unsigned> ClosedPreambleCacheSize{
+    "closed-preamble-cache-size",
+    cat(Misc),
+    desc("Number of preambles of closed files to keep in the cache."),
+    init(1),
+};
+
 opt<Path> IndexFile{
     "index-file",
     cat(Misc),
     desc(
         "Index file to build the static index. The file must have been created "
         "by a compatible clangd-indexer\n"
         "WARNING: This option is experimental only, and will be removed "
         "eventually. Don't rely on it"),
if (StaticIdx) {
     IdxStack.emplace_back(std::move(StaticIdx));
     IdxStack.emplace_back(
         std::make_unique<MergedIndex>(PAI.get(), IdxStack.back().get()));
     Opts.StaticIndex = IdxStack.back().get();
   } else {
     Opts.StaticIndex = PAI.get();
   }
   Opts.AsyncThreadsCount = WorkerThreadsCount;
+  Opts.ClosedPreambleCacheSize = ClosedPreambleCacheSize;
   Opts.FoldingRanges = FoldingRanges;
   Opts.InlayHints = InlayHints;
   Opts.MemoryCleanup = getMemoryCleanupFunction();
 
   Opts.CodeComplete.IncludeIneligibleResults = IncludeIneligibleResults;
   Opts.CodeComplete.Limit = LimitResults;
   if (CompletionStyle.getNumOccurrences())
     Opts.CodeComplete.BundleOverloads = CompletionStyle != Detailed;