[clangd] use a compatible preamble for the first AST built

[qchateau]

Summary

Keep a store of the preambles of all opened filed, plus up to
5 previously used preambles. 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.

---

This patch is starting to look like something acceptable, so
I'm sending it for review. At this point I'd like to get some
feedback on this before going further.

[sammccall]

@kadircet who was doing (or planning!) some measurements around this idea. Maybe it's possible to use this patch for them?

My guess about risks:

• currently, preamble patching covers relatively few extra headers in practice. Here we're likely to end up with larger divergences which might lead to really terrible AST build times (e.g. what if we're missing 30% of a 500MB preamble...)
• maybe extra resource consumption from the +5 cached preambles (e.g. in preamble-in-ram case), but I guess this number can just be tuned

[qchateau]

The hardcoded 5 premables can indeed be changed, I did not want to waste time on coding a configuration logic at such an early stage.

Well indeed do some extra work if we elect a compatible but almost useless preamble. We'll basically do the work twice (but at least we do it concurrently \o/). I can look into adding a heuristic layer to detect almost useless preambles and reject them. Though I'm not sure how I could do this as a single header can contain 99% of the preamble through include chains

Anyway that's the current state of this patch: it's already pretty cool (it does speed things up noticeably) but there are probably tons of flaws or potential improvements and I'd like to receive comments from another POV

[kadircet]

In D97417#2588101, @qchateau wrote:

Well indeed do some extra work if we elect a compatible but almost useless preamble. We'll basically do the work twice (but at least we do it concurrently \o/).

I am afraid this can happen more than twice, e.g. for signature help, the client will issue a request after each keystroke, clangd will see the request try to serve it by patching the AST, while building it we'll receive more requests, and each of those will be served with a huge patching penalty. (as we don't cancel preamble tasks, maybe we should but even then, we'll keep building responses for out-dated requests).

I can look into adding a heuristic layer to detect almost useless preambles and reject them. Though I'm not sure how I could do this as a single header can contain 99% of the preamble through include chains

That's actually an interesting trade-off we can make. getBestPreamble can choose the preamble that has most similar line coverage (this was something i was testing internally already) but in addition to that as you mentioned we can have a threshold and say that we won't consider a preamble as a match, if it requires patching more than X lines(or bytes) of code (note that this heuristic would require doing some IO to calculate number of new lines/bytes, until first preamble is built). Though we would need to ensure that we can still utilize the preamble cache even after that mechanism, and find the sweet spot for X.

Anyway that's the current state of this patch: it's already pretty cool (it does speed things up noticeably) but there are probably tons of flaws or potential improvements and I'd like to receive comments from another POV

yes it indeed looks great! could you give a bit more information on average preamble build latency in the files you are testing this with, and how all of this works when you open files from different parts of the codebase? (I'll also try to do some analysis for this one myself, especially for the heuristic I mentioned)

[qchateau]

• [clangd] make more compile commands compatible
• [clangd] ignore incompatible preamble
  
  I improved command line compatibility detection (faster & matches more files) and I had to blacklist some preambles. Namely, when the file we're building the AST for appears in the include tree of a preamble, we can't use it, otherwise symbols are missing from the AST. I feel like I understand why, but I have no idea how to fix it ...

[qchateau]

I am much more afraid of providing bad results than I am afraid of degrading performance. I mean, eventually the "real" preamble is built, and the results are just as correct as before, but it may yield incorrect results until we invalidate the AST.
That is especially the case as I'm not very experienced in compiler design and I don't have a deep understanding of what happens behind the curtains when using a PCH.
There are probably cases where we degrade perf, but overall my experience with this patch is overwhelmingly positive, especially for "long coding sessions".

I am afraid this can happen more than twice

I'm not sure I follow, I see these different situations (in TUScheduler):

• runWithPreamble
  • PreambleConsistency::Stale -> will wait for a "real" preamble, no change in behavior
  • PreambleConsistency::StaleOrAbsent
    • a preamble is available, we'll use it, no change in behavior
    • the preamble is not yet built, we'll use a compatible preamble instead -> this means instant partial completion !
• runWithAST
  • a preamble is available, we'll use it, no change in behavior
  • the preamble is not yet built, we'll use a compatible preamble to start building the AST straight away -> here there is a risk of double work, if the compatible preamble is useless, we'll start building the AST *while* we're also building the preamble

But I don't see how we can do worse than building the AST and the preamble at the same time ?

could you give a bit more information on average preamble build latency in the files you are testing this with

Extracts from VSCode logs, between the file being opened and the semantic token request completion.
Also worth noting that we have partial completion with 0 delay (with the compatible preamble)

Without the patch:

I[22:40:57.317] ASTWorker building file /home/quentin/dev/llvm-project/clang-tools-extra/clangd/ParsedAST.h version 1 with command inferred from /home/quentin/dev/llvm-project/clang-tools-extra/clangd/ParsedAST.cpp
I[22:41:07.893] --> reply:textDocument/semanticTokens/full(1) 9921 ms

I[22:41:16.526] ASTWorker building file /home/quentin/dev/llvm-project/clang-tools-extra/clangd/ParsedAST.cpp version 1 with command
I[22:41:38.401] --> reply:textDocument/semanticTokens/full(12) 21877 ms

I[22:41:53.861] ASTWorker building file /home/quentin/dev/llvm-project/clang-tools-extra/clangd/IncludeFixer.h version 1 with command inferred from /home/quentin/dev/llvm-project/clang-tools-extra/clangd/IncludeFixer.cpp
I[22:42:06.006] --> reply:textDocument/semanticTokens/full(23) 12144 ms

I[22:42:08.619] ASTWorker building file /home/quentin/dev/llvm-project/clang-tools-extra/clangd/IncludeFixer.cpp version 1 with command
I[22:42:21.920] --> reply:textDocument/semanticTokens/full(28) 13278 ms

With the patch

I[22:36:32.828] ASTWorker building file /home/quentin/dev/llvm-project/clang-tools-extra/clangd/ParsedAST.h version 1 with command inferred from /home/quentin/dev/llvm-project/clang-tools-extra/clangd/ParsedAST.cpp
I[22:36:43.211] --> reply:textDocument/semanticTokens/full(3) 9675 ms

I[22:36:52.331] ASTWorker building file /home/quentin/dev/llvm-project/clang-tools-extra/clangd/ParsedAST.cpp version 1 with command
I[22:36:58.206] --> reply:textDocument/semanticTokens/full(9) 5881 ms

I[22:37:13.474] ASTWorker building file /home/quentin/dev/llvm-project/clang-tools-extra/clangd/IncludeFixer.h version 1 with command inferred from /home/quentin/dev/llvm-project/clang-tools-extra/clangd/IncludeFixer.cpp
I[22:37:15.840] --> reply:textDocument/semanticTokens/full(15) 2351 ms

I[22:37:23.939] ASTWorker building file /home/quentin/dev/llvm-project/clang-tools-extra/clangd/IncludeFixer.cpp version 1 with command
I[22:37:25.030] --> reply:textDocument/semanticTokens/full(20) 1089 ms

[qchateau]

rebase on main, fix formatting

[qchateau]

fix bad arc diff

[qchateau]

Have you guys been giving some thoughts to that patch ? I've been using it in my daily work since I submitted the patch, and I'd not go back

[qchateau]

• Rebase
• Add cli argument to set the cache size
• Reduce default cache size to 1 (to allow fast open/close/reopen)

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(
       collectIncludeStructureCallback(Clang->getSourceManager(), &Includes));
   // 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));
 
   // Copy over the includes from the preamble, then combine with the
   // non-preamble includes below.
   CanonicalIncludes CanonIncludes;
   if (Preamble)

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

 #include <vector>
 
 namespace clang {
 namespace clangd {
 using std::chrono::steady_clock;
 
 namespace {
 class ASTWorker;
+
+bool compileCommandsAreSimilar(const tooling::CompileCommand &LHS,
+                               const tooling::CompileCommand &RHS) {
+  auto LIt = LHS.CommandLine.begin();
+  auto RIt = RHS.CommandLine.begin();
+
+  auto SkipSpecificArg = [](auto It, auto End, const std::string &Filename) {
+    while (It != End) {
+      if (*It == "-o" || *It == "-x") {
+        // Erase -o and its argument
+        // Erase -x and its argument: it would prevent using header file
+        // preamble for a source file
+        It = std::min(It + 2, End);
+      } else if (*It == "-c" || It->find("-W") == 0 || *It == "-pedantic") {
+        // We don't care about those flags
+        It++;
+      } else if (It->find(Filename) != std::string::npos) {
+        // The file we're compiling appears in this argument, drop it to make it
+        // generic
+        It++;
+      } else {
+        break;
+      }
+    }
+    return It;
+  };
+
+  // Iterate the command line, skipping arguments that are specific to the
+  // file being compiled and that would not influence the premable
+  // compatiblity. Stop when one iterate reach the or when an argument differs
+  auto LEnd = LHS.CommandLine.end();
+  auto REnd = RHS.CommandLine.end();
+  while (true) {
+    LIt = SkipSpecificArg(LIt, LEnd, LHS.Filename);
+    RIt = SkipSpecificArg(RIt, REnd, RHS.Filename);
+
+    if (LIt == LEnd || RIt == REnd) {
+      break;
+    }
+
+    if (*LIt != *RIt) {
+      break;
+    }
+
+    LIt++;
+    RIt++;
+  }
+
+  // If both iterator get to the end at the same time, the CL are compatible
+  bool Compatible = LIt == LEnd && RIt == REnd;
+  if (Compatible) {
+    vlog("{0} and {1} are compatible", LHS.Filename, RHS.Filename);
+  }
+  return Compatible;
+}
+
 } // namespace
 
 static clang::clangd::Key<std::string> kFileBeingProcessed;
 
 llvm::Optional<llvm::StringRef> TUScheduler::getFileBeingProcessedInContext() {
   if (auto *File = Context::current().get(kFileBeingProcessed))
     return llvm::StringRef(*File);
   return None;
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) {
+    return !compileCommandsAreSimilar(FileInputs.CompileCommand,
+                                      Item.Preamble->CompileCommand) ||
+           // Using the preamble of a file that include the file we're
+           // processing will only yield partial results Unless we can tackle
+           // this issue, just ignore this preamble
+           Item.Preamble->Includes.includeDepth(Item.FileName).count(FileName);
+  });
+  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::create(FileName, FileInputs, *Best->Preamble);
+
+  for (auto It = Best + 1; It != CompatiblePreambles.end(); ++It) {
+    auto Patch = PreamblePatch::create(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(),
                Contents = It->second->Contents,
                Command = Worker->getCurrentCompileCommand(),
                Ctx = Context::current().derive(kFileBeingProcessed,
                                                std::string(File)),
                Action = std::move(Action), this]() mutable {
     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;