[clangd] Run PreambleThread in async mode behind a flag

[kadircet]

Summary

Depends on D80198.

This patch implies ASTs might be built with stale preambles without
blocking for a fresh one. It also drops any guarantees on every preamble
version being built. In case of multiple preamble build requests, in
addition to being debounced.

Any preamble requested with a WantDiags::Yes will always be built, this
is ensured by blocking enqueueing of any subsequent reqest.

AST worker will still block for initial preamble to reduce duplicate
work.

[kadircet]

clang-tools-extra/clangd/TUScheduler.cpp

248

This is mostly to make sure tests do not regress, I am not sure if we have any real world uses of it though.

I would love to just drop this and change tests instead. WDYT?

[kadircet]

• Rebase and update comments on block until idle.

[sammccall]

Sorry about the delay on this, I said I'd prioritize it... had a slightly odd day.

Haven't reviewed the unit test yet (mostly a reminder to myself).
Generally looks good...

clang-tools-extra/clangd/ClangdServer.h

156

Group with StorePreamblesInMemory.

This comment doesn't make much sense either - PreamblePeer describe's the thread's relation to the main ASTWorker thread, but readers here won't know what it is. What about:
Reuse even stale preambles, and rebuild them in the background.
This improves latency at the cost of accuracy.

clang-tools-extra/clangd/TUScheduler.cpp

244

First sentence makes sense, code makes sense, I can't parse the second sentence at all.
Just "block until it's built"?

Any maybe something about why we won't deadlock, but tests are enough I guess.

292

add comment // will never build one, or so

543–550

we're passing around enough loose booleans we should consider having TUScheduler hold its Options struct, and pass it here by refrerence...

654

"ready, as patching..."

721

hmm, we're notifying the ASTPeer, and then setting builtfirst which is being waited on... by astpeer.
This suggests to me the AST thread should own the notification, not the preamble thread.
And in fact it already has a notification for the first preamble being built! why can't we use that one?

1131

I think this would be clearer as a loop... and maybe more correct.

1143

um... isn't that allowed?
If new traffic means the queue doesn't go idle, I think we're supposed to return false, rather than crash.

clang-tools-extra/clangd/TUScheduler.h

195

nit: break before second sentence?

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

421

I'd drop "builds" at least from the flag name, possibly througout

423

This isn't very descriptive. I'd use some variation of the comment suggested for the ClangdServer::Options

[sammccall]

clang-tools-extra/clangd/TUScheduler.cpp

1135

I'd consider pulling out an IsIdle lambda (checking for all 3 conditions) and using it both here and at the bottom.

PreambleRequests will never be (solely) full here, and Requests will always be empty at the bottom, but it's harmless and I think easier to read.

1139

Maybe explicitly: "This might create new PreambleRequests for the ASTWorker."

1143

OK, I somehowe forgot that ASTWorker isn't threadsafe so we only have the current thread and the worker thread to worry about.

Suggest a slightly expanded message like: No new normal tasks can be scheduled concurrently with blockUntilIdle(): ASTWorker isn't threadsafe

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

101

Consider inlining this class until we have a second user.
It's not clear that adapting between lambda and an interface clarifies the test enough to justify the indirection.

101

capturePreamble isn't the right name for this function, unlike captureDiags it doesn't actually send the preamble anywhere.

453

As you've pointed out, Yes isn't used in production. So if the behaviour of Auto has changed we should test that rather than stop using it.

My understanding of the change:

1. we've asserted that every update yields diagnostics
2. this was true because we were calling runWithAST, this forced an AST build at each snapshot, and we'd publish the diagnostics
3. now we only publish diagnostics once the version has been through the preamble thread and back
4. these requests get coalesced in the preamble thread if the AST worker is pushing them faster than the preamble worker is servicing them
5. so we no longer publish diagnostics for every version even if we have a suitable AST

Is this right?
If so, I'd assert that TotalUpdates is at least FilesCount and at most FilesCount * UpdatesPerFile, and also that the latest UpdateI for diags (for any file) is equal to UpdatesPerFile - 1.
And maybe add a brief explanation (we drop diagnostics for some snapshots as they get coalesced in the preamble worker).

1000

This seems like a dubious use of atomic (lack of synchronization between accesses) - there's actually only one thread here, right?

It would be much clearer IMO to just test the passed-in Version directly.

1021

nit: spell out "blocking" explicitly

1021

if you expose preambleVersion() from ParsedAST, you could assert on it directly. I think this would be much clearer than the stuff with PreambleBuildCount.

(I don't see any reason not to expose preamble itself, but this probably isn't a good enough reason to do it)

[kadircet]

clang-tools-extra/clangd/TUScheduler.cpp

721

umm, it is a little bit more complicated.

The above call only inserts the "update request" onto ASTPeer's queue and doesn't update the preamble inside ASTPeer. This enables ASTPeer to access LatestPreamble without holding the lock, as it is the only writer. We can change that, update the LatestPreamble while queueing the request.

1131

as discussed offline, loop version isn't more clear keeping the straight version.

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

453

Is this right?

yes. in addition to those, previously Auto promised a diagnostics release if it was followed by a read(that's how this test used to work). we no longer guarantee that for the reasons you've mentioned.

What about keeping WantDiagnostics::Yes at all? I believe it should be a separate patch none the less, but I would be happy with silently converting Yes to Auto. I would expect this to only break editors not using Auto at all and always forcing diags or not requesting them at all.

[kadircet]

• Address comments

[sammccall]

clang-tools-extra/clangd/TUScheduler.cpp

654

This isn't the natural place to block, rather where the preamble would be consumed.
But that's too late, we'd be running on the worker thread with the PreambleTask scheduled and so we'd deadlock.
This needs a comment :-)

721

As discussed, the relationship between the two is complicated.
At least we should move the second into ASTPeer to reduce the surface area between the two.

As a followup, we can "explode" the existing notification into CV + Mutex + bool.
The bool can naturally become the "present" bit on LatestPreamble if it turns into an Optional<shared_ptr<>> - we must document none vs null!
The Mutex already exists.

Then we don't need the second notification: we just wait on !preambletasks.empty() || LatestPreamble.hasValue()

[kadircet]

• Move notification from PreambleThread to ASTWorker

[kadircet]

• Add comment explaining why we block on ASTWorker::update rather than consumers of a preamble

[wolfgangp]

Hi!

Shortly after this patch went in, we started to see intermittent failures with the unittest TUSchedulerTests.ManyUpdates. The build server (Windows) we're running it on is quite powerful and our own hand-run tests only take about 400 ms, so we don't really understand what could be happening. Any help would be appreciated.

Here is an excerpt from the log:

Note: Google Test filter = TUSchedulerTests.ManyUpdates

[==========] Running 1 test from 1 test case.

[----------] Global test environment set-up.

[----------] 1 test from TUSchedulerTests

[ RUN ] TUSchedulerTests.ManyUpdates

C:\j\w\...\clang-tools-extra\clangd\unittests\TUSchedulerTests.cpp(508): error: Value of: S.blockUntilIdle(timeoutSeconds(10))

Actual: false

Expected: true

[ FAILED ] TUSchedulerTests.ManyUpdates (10576 ms)

[----------] 1 test from TUSchedulerTests (10576 ms total)

clang-tools-extra/clangd/ClangdServer.h

struct Options {
     /// thread, and callbacks are invoked before "async" functions return.
     unsigned AsyncThreadsCount = getDefaultAsyncThreadsCount();
 
     /// 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;
+    /// Reuse even stale preambles, and rebuild them in the background.
+    /// This improves latency at the cost of accuracy.
+    bool AsyncPreambleBuilds = false;
 
     /// If true, ClangdServer builds a dynamic in-memory index for symbols in
     /// opened files and uses the index to augment code completion results.
     bool BuildDynamicSymbolIndex = false;
     /// Use a heavier and faster in-memory index implementation.
     bool HeavyweightDynamicSymbolIndex = true;
     /// If true, ClangdServer automatically indexes files in the current project
     /// on background threads. The index is stored in the project root.
struct Options {
 
     /// Clangd will execute compiler drivers matching one of these globs to
     /// fetch system include path.
     std::vector<std::string> QueryDriverGlobs;
 
     /// Enable notification-based semantic highlighting.
     bool TheiaSemanticHighlighting = false;
 
     /// Returns true if the tweak should be enabled.
     std::function<bool(const Tweak &)> TweakFilter = [](const Tweak &T) {
       return !T.hidden(); // only enable non-hidden tweaks.
     };
 
     explicit operator TUScheduler::Options() const;
   };
   // Sensible default options for use in tests.
   // Features like indexing must be enabled if desired.

clang-tools-extra/clangd/ClangdServer.cpp

 } // namespace
 
 ClangdServer::Options ClangdServer::optsForTest() {
   ClangdServer::Options Opts;
   Opts.UpdateDebounce = DebouncePolicy::fixed(/*zero*/ {});
   Opts.StorePreamblesInMemory = true;
   Opts.AsyncThreadsCount = 4; // Consistent!
   Opts.TheiaSemanticHighlighting = true;
+  Opts.AsyncPreambleBuilds = true;
   return Opts;
 }
 
 ClangdServer::Options::operator TUScheduler::Options() const {
   TUScheduler::Options Opts;
   Opts.AsyncThreadsCount = AsyncThreadsCount;
   Opts.RetentionPolicy = RetentionPolicy;
   Opts.StorePreamblesInMemory = StorePreamblesInMemory;
   Opts.UpdateDebounce = UpdateDebounce;
+  Opts.AsyncPreambleBuilds = AsyncPreambleBuilds;
   return Opts;
 }
 
 ClangdServer::ClangdServer(const GlobalCompilationDatabase &CDB,
                            const FileSystemProvider &FSProvider,
                            const Options &Opts, Callbacks *Callbacks)
     : FSProvider(FSProvider),
       DynamicIdx(Opts.BuildDynamicSymbolIndex

clang-tools-extra/clangd/ParsedAST.h

 #include "index/CanonicalIncludes.h"
 #include "support/Path.h"
 #include "clang/Frontend/FrontendAction.h"
 #include "clang/Frontend/PrecompiledPreamble.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "clang/Tooling/Syntax/Tokens.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/None.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringRef.h"
 #include <memory>
 #include <string>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 class SymbolIndex;
 
public:
   const MainFileMacros &getMacros() const;
   /// Tokens recorded while parsing the main file.
   /// (!) does not have tokens from the preamble.
   const syntax::TokenBuffer &getTokens() const { return Tokens; }
 
   /// Returns the version of the ParseInputs this AST was built from.
   llvm::StringRef version() const { return Version; }
 
+  /// Returns the version of the ParseInputs used to build Preamble part of this
+  /// AST. Might be None if no Preamble is used.
+  llvm::Optional<llvm::StringRef> preambleVersion() const;
+
 private:
   ParsedAST(llvm::StringRef Version,
             std::shared_ptr<const PreambleData> Preamble,
             std::unique_ptr<CompilerInstance> Clang,
             std::unique_ptr<FrontendAction> Action, syntax::TokenBuffer Tokens,
             MainFileMacros Macros, std::vector<Decl *> LocalTopLevelDecls,
             std::vector<Diag> Diags, IncludeStructure Includes,
             CanonicalIncludes CanonIncludes);

clang-tools-extra/clangd/ParsedAST.cpp

: Version(Version), Preamble(std::move(Preamble)), Clang(std::move(Clang)),
       Action(std::move(Action)), Tokens(std::move(Tokens)),
       Macros(std::move(Macros)), Diags(std::move(Diags)),
       LocalTopLevelDecls(std::move(LocalTopLevelDecls)),
       Includes(std::move(Includes)), CanonIncludes(std::move(CanonIncludes)) {
   assert(this->Clang);
   assert(this->Action);
 }
 
+llvm::Optional<llvm::StringRef> ParsedAST::preambleVersion() const {
+  if (!Preamble)
+    return llvm::None;
+  return llvm::StringRef(Preamble->Version);
+}
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/TUScheduler.h

struct Options {
     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.
     ASTRetentionPolicy RetentionPolicy;
+
+    /// Whether to run PreamblePeer asynchronously.
+    /// No-op if AsyncThreadsCount is 0.
+    bool AsyncPreambleBuilds = false;
   };
 
   TUScheduler(const GlobalCompilationDatabase &CDB, const Options &Opts,
               std::unique_ptr<ParsingCallbacks> ASTCallbacks = nullptr);
   ~TUScheduler();
 
   struct FileStats {
     std::size_t UsedBytes = 0;
public:
   // 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.
   static llvm::Optional<llvm::StringRef> getFileBeingProcessedInContext();
 
 private:
   const GlobalCompilationDatabase &CDB;
-  const bool StorePreamblesInMemory;
+  const Options Opts;
   std::unique_ptr<ParsingCallbacks> Callbacks; // not nullptr
   Semaphore Barrier;
   llvm::StringMap<std::unique_ptr<FileData>> Files;
   std::unique_ptr<ASTCache> IdleASTs;
   // None when running tasks synchronously and non-None when running tasks
   // asynchronously.
   llvm::Optional<AsyncTaskRunner> PreambleTasks;
   llvm::Optional<AsyncTaskRunner> WorkerThreads;
-  DebouncePolicy UpdateDebounce;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif

clang-tools-extra/clangd/TUScheduler.cpp

void update(std::unique_ptr<CompilerInvocation> CI, ParseInputs PI,
     if (RunSync) {
       build(std::move(Req));
       Status.update([](TUStatus &Status) {
         Status.PreambleActivity = PreambleAction::Idle;
       });
       return;
     }
     {
-      std::lock_guard<std::mutex> Lock(Mutex);
-      // If shutdown is issued, don't bother building.
-      if (Done)
-        return;
+      std::unique_lock<std::mutex> Lock(Mutex);
+      // If NextReq was requested with WantDiagnostics::Yes we cannot just drop
+      // that on the floor. Block until we start building it. This won't
+      // dead-lock as we are blocking the caller thread, while builds continue
+      // on preamble thread.
+      ReqCV.wait(Lock, [this] {
+        return !NextReq || NextReq->WantDiags != WantDiagnostics::Yes;
+      });
       NextReq = std::move(Req);
     }
     // Let the worker thread know there's a request, notify_one is safe as there
     // should be a single worker thread waiting on it.
     ReqCV.notify_all();
   }
 
   void run() {
while (true) {
         // and client thread(clangdserver).
         Status.update([](TUStatus &Status) {
           Status.PreambleActivity = PreambleAction::Idle;
         });
       }
       ReqCV.notify_all();
     }
     dlog("Preamble worker for {0} stopped", FileName);
   }
 
   /// Signals the run loop to exit.
   void stop() {
     dlog("Preamble worker for {0} received stop", FileName);
     {
       std::lock_guard<std::mutex> Lock(Mutex);
       Done = true;
       NextReq.reset();

 /// 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,
-            DebouncePolicy UpdateDebounce, bool StorePreamblesInMemory,
-            ParsingCallbacks &Callbacks);
+            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, DebouncePolicy UpdateDebounce,
-         bool StorePreamblesInMemory, ParsingCallbacks &Callbacks);
+  static ASTWorkerHandle create(PathRef FileName,
+                                const GlobalCompilationDatabase &CDB,
+                                TUScheduler::ASTCache &IdleASTs,
+                                AsyncTaskRunner *Tasks, Semaphore &Barrier,
+                                const TUScheduler::Options &Opts,
+                                ParsingCallbacks &Callbacks);
   ~ASTWorker();
 
   void update(ParseInputs Inputs, WantDiagnostics);
   void
   runWithAST(llvm::StringRef Name,
              llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action,
              TUScheduler::ASTActionInvalidation);
   bool blockUntilIdle(Deadline Timeout) const;
private:
   llvm::SmallVector<DebouncePolicy::clock::duration, 8>
       RebuildTimes; /* GUARDED_BY(Mutex) */
   /// Set to true to signal run() to finish processing.
   bool Done;                              /* GUARDED_BY(Mutex) */
   std::deque<Request> Requests;           /* GUARDED_BY(Mutex) */
   std::queue<Request> PreambleRequests;   /* GUARDED_BY(Mutex) */
   llvm::Optional<Request> CurrentRequest; /* GUARDED_BY(Mutex) */
   mutable std::condition_variable RequestsCV;
+  Notification ReceivedPreamble;
   /// Guards the callback that publishes results of AST-related computations
   /// (diagnostics, highlightings) and file statuses.
   std::mutex PublishMu;
   // Used to prevent remove document + add document races that lead to
   // out-of-order callbacks for publishing results of onMainAST callback.
   //
   // The lifetime of the old/new ASTWorkers will overlap, but their handles
   // don't. When the old handle is destroyed, the old worker will stop reporting
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, DebouncePolicy UpdateDebounce,
-                  bool StorePreamblesInMemory, ParsingCallbacks &Callbacks) {
-  std::shared_ptr<ASTWorker> Worker(
-      new ASTWorker(FileName, CDB, IdleASTs, Barrier, /*RunSync=*/!Tasks,
-                    UpdateDebounce, StorePreamblesInMemory, Callbacks));
+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));
   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, DebouncePolicy UpdateDebounce,
-                     bool StorePreamblesInMemory, ParsingCallbacks &Callbacks)
-    : IdleASTs(LRUCache), RunSync(RunSync), UpdateDebounce(UpdateDebounce),
+                     bool RunSync, const TUScheduler::Options &Opts,
+                     ParsingCallbacks &Callbacks)
+    : IdleASTs(LRUCache), RunSync(RunSync), UpdateDebounce(Opts.UpdateDebounce),
       FileName(FileName), CDB(CDB), Callbacks(Callbacks), Barrier(Barrier),
       Done(false), Status(FileName, Callbacks),
-      PreamblePeer(FileName, Callbacks, StorePreamblesInMemory,
-                   // FIXME: Run PreamblePeer asynchronously once ast patching
-                   // is available.
-                   /*RunSync=*/true, Status, *this) {
+      PreamblePeer(FileName, Callbacks, Opts.StorePreamblesInMemory,
+                   RunSync || !Opts.AsyncPreambleBuilds, Status, *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.
if (!Invocation) {
       // Make sure anyone waiting for the preamble gets notified it could not be
       // built.
       BuiltFirstPreamble.notify();
       return;
     }
 
     PreamblePeer.update(std::move(Invocation), std::move(Inputs),
                         std::move(CompilerInvocationDiags), WantDiags);
+    // Block until first preamble is ready, as patching an empty preamble would
+    // imply rebuilding it from scratch.
+    // This isn't the natural place to block, rather where the preamble would be
+    // consumed. But that's too late, we'd be running on the worker thread with
+    // the PreambleTask scheduled and so we'd deadlock.
+    ReceivedPreamble.wait();
     return;
   };
   startTask(TaskName, std::move(Task), WantDiags, TUScheduler::NoInvalidation);
 }
 
 void ASTWorker::runWithAST(
     llvm::StringRef Name,
     llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action,
void PreambleThread::build(Request Req) {
 
   Status.update([&](TUStatus &Status) {
     Status.PreambleActivity = PreambleAction::Building;
   });
   auto _ = llvm::make_scope_exit([this, &Req] {
     ASTPeer.updatePreamble(std::move(Req.CI), std::move(Req.Inputs),
                            LatestBuild, std::move(Req.CIDiags),
                            std::move(Req.WantDiags));
   });
 
   if (!LatestBuild || Inputs.ForceRebuild) {
     vlog("Building first preamble for {0} version {1}", FileName,
          Inputs.Version);
   } else if (isPreambleCompatible(*LatestBuild, Inputs, FileName, *Req.CI)) {
     vlog("Reusing preamble version {0} for version {1} of {2}",
          LatestBuild->Version, Inputs.Version, FileName);
     return;
if (WantDiags == WantDiagnostics::No)
       return;
     // Report diagnostics with the new preamble to ensure progress. Otherwise
     // diagnostics might get stale indefinitely if user keeps invalidating the
     // preamble.
     generateDiagnostics(std::move(CI), std::move(PI), std::move(CIDiags));
   };
   if (RunSync) {
     Task();
+    ReceivedPreamble.notify();
     return;
   }
   {
     std::lock_guard<std::mutex> Lock(Mutex);
     PreambleRequests.push({std::move(Task), std::move(TaskName),
                            steady_clock::now(), Context::current().clone(),
                            llvm::None, TUScheduler::NoInvalidation, nullptr});
   }
+  ReceivedPreamble.notify();
   RequestsCV.notify_all();
 }
 
 void ASTWorker::generateDiagnostics(
     std::unique_ptr<CompilerInvocation> Invocation, ParseInputs Inputs,
     std::vector<Diag> CIDiags) {
   // Tracks ast cache accesses for publishing diags.
   static constexpr trace::Metric ASTAccessForDiag(
void ASTWorker::stop() {
     CanPublishResults = false;
   }
   {
     std::lock_guard<std::mutex> Lock(Mutex);
     assert(!Done && "stop() called twice");
     Done = true;
   }
   // We are no longer going to build any preambles, let the waiters know that.
+  ReceivedPreamble.notify();
   BuiltFirstPreamble.notify();
   PreamblePeer.stop();
   Status.stop();
   RequestsCV.notify_all();
 }
 
 void ASTWorker::startTask(llvm::StringRef Name,
                           llvm::unique_function<void()> Task,
for (; Next != Requests.end(); ++Next)
       if (Next->UpdateType == WantDiagnostics::Yes ||
           Next->UpdateType == WantDiagnostics::Auto)
         return true; // Prefer later diagnostics.
     return false;
   }
   llvm_unreachable("Unknown WantDiagnostics");
 }
 
 bool ASTWorker::blockUntilIdle(Deadline Timeout) const {
+  auto WaitUntilASTWorkerIsIdle = [&] {
     std::unique_lock<std::mutex> Lock(Mutex);
     return wait(Lock, RequestsCV, Timeout, [&] {
       return PreambleRequests.empty() && Requests.empty() && !CurrentRequest;
     });
+  };
+  // Make sure ASTWorker has processed all requests, which might issue new
+  // updates to PreamblePeer.
+  WaitUntilASTWorkerIsIdle();
+  // Now that ASTWorker processed all requests, ensure PreamblePeer has served
+  // all update requests. This might create new PreambleRequests for the
+  // ASTWorker.
+  PreamblePeer.blockUntilIdle(Timeout);
+  assert(Requests.empty() &&
+         "No new normal tasks can be scheduled concurrently with "
+         "blockUntilIdle(): ASTWorker isn't threadsafe");
+  // Finally make sure ASTWorker has processed all of the preamble updates.
+  return WaitUntilASTWorkerIsIdle();
 }
 
 // Render a TUAction to a user-facing string representation.
 // TUAction represents clangd-internal states, we don't intend to expose them
 // to users (say C++ programmers) directly to avoid confusion, we use terms that
 // are familiar by C++ programmers.
 std::string renderTUAction(const PreambleAction PA, const ASTAction &AA) {
   llvm::SmallVector<std::string, 2> Result;
struct TUScheduler::FileData {
   /// Latest inputs, passed to TUScheduler::update().
   std::string Contents;
   ASTWorkerHandle Worker;
 };
 
 TUScheduler::TUScheduler(const GlobalCompilationDatabase &CDB,
                          const Options &Opts,
                          std::unique_ptr<ParsingCallbacks> Callbacks)
-    : CDB(CDB), StorePreamblesInMemory(Opts.StorePreamblesInMemory),
+    : CDB(CDB), Opts(Opts),
       Callbacks(Callbacks ? move(Callbacks)
                           : std::make_unique<ParsingCallbacks>()),
       Barrier(Opts.AsyncThreadsCount),
       IdleASTs(
-          std::make_unique<ASTCache>(Opts.RetentionPolicy.MaxRetainedASTs)),
-      UpdateDebounce(Opts.UpdateDebounce) {
+          std::make_unique<ASTCache>(Opts.RetentionPolicy.MaxRetainedASTs)) {
   if (0 < Opts.AsyncThreadsCount) {
     PreambleTasks.emplace();
     WorkerThreads.emplace();
   }
 }
 
 TUScheduler::~TUScheduler() {
   // Notify all workers that they need to stop.

 }
 
 bool TUScheduler::update(PathRef File, ParseInputs Inputs,
                          WantDiagnostics WantDiags) {
   std::unique_ptr<FileData> &FD = Files[File];
   bool NewFile = FD == nullptr;
   if (!FD) {
     // Create a new worker to process the AST-related tasks.
-    ASTWorkerHandle Worker = ASTWorker::create(
-        File, CDB, *IdleASTs,
-        WorkerThreads ? WorkerThreads.getPointer() : nullptr, Barrier,
-        UpdateDebounce, StorePreamblesInMemory, *Callbacks);
+    ASTWorkerHandle Worker =
+        ASTWorker::create(File, CDB, *IdleASTs,
+                          WorkerThreads ? WorkerThreads.getPointer() : nullptr,
+                          Barrier, Opts, *Callbacks);
     FD = std::unique_ptr<FileData>(
         new FileData{Inputs.Contents, std::move(Worker)});
   } else {
     FD->Contents = Inputs.Contents;
   }
   FD->Worker->update(std::move(Inputs), WantDiags);
   return NewFile;
 }

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

 
 opt<bool> PrettyPrint{
     "pretty",
     cat(Protocol),
     desc("Pretty-print JSON output"),
     init(false),
 };
 
+opt<bool> AsyncPreamble{
+    "async-preamble",
+    cat(Misc),
+    desc("Reuse even stale preambles, and rebuild them in the background. This "
+         "improves latency at the cost of accuracy."),
+    init(ClangdServer::Options().AsyncPreambleBuilds),
+    Hidden,
+};
+
 /// Supports a test URI scheme with relaxed constraints for lit tests.
 /// The path in a test URI will be combined with a platform-specific fake
 /// directory to form an absolute path. For example, test:///a.cpp is resolved
 /// C:\clangd-test\a.cpp on Windows and /clangd-test/a.cpp on Unix.
 class TestScheme : public URIScheme {
 public:
   llvm::Expected<std::string>
   getAbsolutePath(llvm::StringRef /*Authority*/, llvm::StringRef Body,

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

 )cpp";
 
   auto FooCpp = testPath("foo.cpp");
 
   FS.Files[testPath("foo.h")] = "int a;";
   FS.Files[FooCpp] = SourceContents;
 
   Server.addDocument(FooCpp, SourceContents);
-  auto DumpParse1 = dumpASTWithoutMemoryLocs(Server, FooCpp);
   ASSERT_TRUE(Server.blockUntilIdleForTest()) << "Waiting for diagnostics";
+  auto DumpParse1 = dumpASTWithoutMemoryLocs(Server, FooCpp);
   EXPECT_FALSE(DiagConsumer.hadErrorInLastDiags());
 
   Server.addDocument(FooCpp, "");
-  auto DumpParseEmpty = dumpASTWithoutMemoryLocs(Server, FooCpp);
   ASSERT_TRUE(Server.blockUntilIdleForTest()) << "Waiting for diagnostics";
+  auto DumpParseEmpty = dumpASTWithoutMemoryLocs(Server, FooCpp);
   EXPECT_FALSE(DiagConsumer.hadErrorInLastDiags());
 
   Server.addDocument(FooCpp, SourceContents);
-  auto DumpParse2 = dumpASTWithoutMemoryLocs(Server, FooCpp);
   ASSERT_TRUE(Server.blockUntilIdleForTest()) << "Waiting for diagnostics";
+  auto DumpParse2 = dumpASTWithoutMemoryLocs(Server, FooCpp);
   EXPECT_FALSE(DiagConsumer.hadErrorInLastDiags());
 
   EXPECT_EQ(DumpParse1, DumpParse2);
   EXPECT_NE(DumpParse1, DumpParseEmpty);
 }
 
 TEST_F(ClangdVFSTest, ReparseOnHeaderChange) {
   MockFSProvider FS;
   ErrorCheckingCallbacks DiagConsumer;
   MockCompilationDatabase CDB;
   ClangdServer Server(CDB, FS, ClangdServer::optsForTest(), &DiagConsumer);
 
   const auto SourceContents = R"cpp(
 #include "foo.h"
 int b = a;
 )cpp";
 
   auto FooCpp = testPath("foo.cpp");
   auto FooH = testPath("foo.h");
 
   FS.Files[FooH] = "int a;";
   FS.Files[FooCpp] = SourceContents;
 
   Server.addDocument(FooCpp, SourceContents);
-  auto DumpParse1 = dumpASTWithoutMemoryLocs(Server, FooCpp);
   ASSERT_TRUE(Server.blockUntilIdleForTest()) << "Waiting for diagnostics";
+  auto DumpParse1 = dumpASTWithoutMemoryLocs(Server, FooCpp);
   EXPECT_FALSE(DiagConsumer.hadErrorInLastDiags());
 
   FS.Files[FooH] = "";
   Server.addDocument(FooCpp, SourceContents);
-  auto DumpParseDifferent = dumpASTWithoutMemoryLocs(Server, FooCpp);
   ASSERT_TRUE(Server.blockUntilIdleForTest()) << "Waiting for diagnostics";
+  auto DumpParseDifferent = dumpASTWithoutMemoryLocs(Server, FooCpp);
   EXPECT_TRUE(DiagConsumer.hadErrorInLastDiags());
 
   FS.Files[FooH] = "int a;";
   Server.addDocument(FooCpp, SourceContents);
-  auto DumpParse2 = dumpASTWithoutMemoryLocs(Server, FooCpp);
   ASSERT_TRUE(Server.blockUntilIdleForTest()) << "Waiting for diagnostics";
+  auto DumpParse2 = dumpASTWithoutMemoryLocs(Server, FooCpp);
   EXPECT_FALSE(DiagConsumer.hadErrorInLastDiags());
 
   EXPECT_EQ(DumpParse1, DumpParse2);
   EXPECT_NE(DumpParse1, DumpParseDifferent);
 }
 
 TEST_F(ClangdVFSTest, PropagatesContexts) {
   static Key<int> Secret;

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

 #include "TestFS.h"
 #include "support/Cancellation.h"
 #include "support/Context.h"
 #include "support/Path.h"
 #include "support/TestTracer.h"
 #include "support/Threading.h"
 #include "clang/Basic/DiagnosticDriver.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/FunctionExtras.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringRef.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <algorithm>
 #include <atomic>
 #include <chrono>
 #include <cstdint>
+#include <memory>
+#include <string>
 #include <utility>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 using ::testing::AnyOf;
 using ::testing::Each;
void updateWithCallback(TUScheduler &S, PathRef File, ParseInputs Inputs,
     S.update(File, Inputs, WD);
   }
 
   static Key<llvm::unique_function<void(PathRef File, std::vector<Diag>)>>
       DiagsCallbackKey;
 
   /// A diagnostics callback that should be passed to TUScheduler when it's used
   /// in updateWithDiags.
   static std::unique_ptr<ParsingCallbacks> captureDiags() {
     class CaptureDiags : public ParsingCallbacks {
     public:
       void onMainAST(PathRef File, ParsedAST &AST, PublishFn Publish) override {
         reportDiagnostics(File, AST.getDiagnostics(), Publish);
       }
 
       void onFailedAST(PathRef File, llvm::StringRef Version,
                        std::vector<Diag> Diags, PublishFn Publish) override {

 TEST_F(TUSchedulerTests, ManyUpdates) {
   const int FilesCount = 3;
   const int UpdatesPerFile = 10;
 
   std::mutex Mut;
   int TotalASTReads = 0;
   int TotalPreambleReads = 0;
   int TotalUpdates = 0;
+  llvm::StringMap<int> LatestDiagVersion;
 
   // Run TUScheduler and collect some stats.
   {
     auto Opts = optsForTest();
     Opts.UpdateDebounce = DebouncePolicy::fixed(std::chrono::milliseconds(50));
     TUScheduler S(CDB, Opts, captureDiags());
 
     std::vector<std::string> Files;
// Run TUScheduler and collect some stats.
     for (int FileI = 0; FileI < FilesCount; ++FileI) {
       for (int UpdateI = 0; UpdateI < UpdatesPerFile; ++UpdateI) {
         auto Contents = AllContents[(FileI + UpdateI) % AllContentsSize];
 
         auto File = Files[FileI];
         auto Inputs = getInputs(File, Contents.str());
         {
           WithContextValue WithNonce(NonceKey, ++Nonce);
-          Inputs.Version = std::to_string(Nonce);
+          Inputs.Version = std::to_string(UpdateI);
           updateWithDiags(
               S, File, Inputs, WantDiagnostics::Auto,
-              [File, Nonce, &Mut, &TotalUpdates](std::vector<Diag>) {
+              [File, Nonce, Version(Inputs.Version), &Mut, &TotalUpdates,
+               &LatestDiagVersion](std::vector<Diag>) {
                 EXPECT_THAT(Context::current().get(NonceKey), Pointee(Nonce));
 
                 std::lock_guard<std::mutex> Lock(Mut);
                 ++TotalUpdates;
                 EXPECT_EQ(File, *TUScheduler::getFileBeingProcessedInContext());
+                // Make sure Diags are for a newer version.
+                auto It = LatestDiagVersion.try_emplace(File, -1);
+                const int PrevVersion = It.first->second;
+                int CurVersion;
+                ASSERT_TRUE(llvm::to_integer(Version, CurVersion, 10));
+                EXPECT_LT(PrevVersion, CurVersion);
+                It.first->getValue() = CurVersion;
               });
         }
         {
           WithContextValue WithNonce(NonceKey, ++Nonce);
           S.runWithAST(
               "CheckAST", File,
               [File, Inputs, Nonce, &Mut,
                &TotalASTReads](Expected<InputsAndAST> AST) {
for (int FileI = 0; FileI < FilesCount; ++FileI) {
               });
         }
       }
     }
     ASSERT_TRUE(S.blockUntilIdle(timeoutSeconds(10)));
   } // TUScheduler destructor waits for all operations to finish.
 
   std::lock_guard<std::mutex> Lock(Mut);
-  EXPECT_EQ(TotalUpdates, FilesCount * UpdatesPerFile);
+  // Updates might get coalesced in preamble thread and result in dropping
+  // diagnostics for intermediate snapshots.
+  EXPECT_GE(TotalUpdates, FilesCount);
+  EXPECT_LE(TotalUpdates, FilesCount * UpdatesPerFile);
+  // We should receive diags for last update.
+  for (const auto &Entry : LatestDiagVersion)
+    EXPECT_EQ(Entry.second, UpdatesPerFile - 1);
   EXPECT_EQ(TotalASTReads, FilesCount * UpdatesPerFile);
   EXPECT_EQ(TotalPreambleReads, FilesCount * UpdatesPerFile);
 }
 
 TEST_F(TUSchedulerTests, EvictedAST) {
   std::atomic<int> BuiltASTCounter(0);
   auto Opts = optsForTest();
   Opts.AsyncThreadsCount = 1;
TEST(DebouncePolicy, Compute) {
   EXPECT_NEAR(15, Compute(History), 0.01) << "median = 10, ratio = 1.5";
   Policy.RebuildRatio = 3;
   EXPECT_NEAR(25, Compute(History), 0.01) << "constrained by max";
   Policy.RebuildRatio = 0;
   EXPECT_NEAR(3, Compute(History), 0.01) << "constrained by min";
   EXPECT_NEAR(25, Compute({}), 0.01) << "no history -> max";
 }
 
+TEST_F(TUSchedulerTests, AsyncPreambleThread) {
+  // Blocks preamble thread while building preamble with \p BlockVersion until
+  // \p N is notified.
+  class BlockPreambleThread : public ParsingCallbacks {
+  public:
+    BlockPreambleThread(llvm::StringRef BlockVersion, Notification &N)
+        : BlockVersion(BlockVersion), N(N) {}
+    void onPreambleAST(PathRef Path, llvm::StringRef Version, ASTContext &Ctx,
+                       std::shared_ptr<clang::Preprocessor> PP,
+                       const CanonicalIncludes &) override {
+      if (Version == BlockVersion)
+        N.wait();
+    }
+
+  private:
+    llvm::StringRef BlockVersion;
+    Notification &N;
+  };
+
+  static constexpr llvm::StringLiteral InputsV0 = "v0";
+  static constexpr llvm::StringLiteral InputsV1 = "v1";
+  Notification Ready;
+  TUScheduler S(CDB, optsForTest(),
+                std::make_unique<BlockPreambleThread>(InputsV1, Ready));
+
+  Path File = testPath("foo.cpp");
+  auto PI = getInputs(File, "");
+  PI.Version = InputsV0.str();
+  S.update(File, PI, WantDiagnostics::Auto);
+  S.blockUntilIdle(timeoutSeconds(10));
+
+  // Block preamble builds.
+  PI.Version = InputsV1.str();
+  // Issue second update which will block preamble thread.
+  S.update(File, PI, WantDiagnostics::Auto);
+
+  Notification RunASTAction;
+  // Issue an AST read, which shouldn't be blocked and see latest version of the
+  // file.
+  S.runWithAST("test", File, [&](Expected<InputsAndAST> AST) {
+    ASSERT_TRUE(bool(AST));
+    // Make sure preamble is built with stale inputs, but AST was built using
+    // new ones.
+    EXPECT_THAT(AST->AST.preambleVersion(), InputsV0);
+    EXPECT_THAT(AST->Inputs.Version, InputsV1.str());
+    RunASTAction.notify();
+  });
+  RunASTAction.wait();
+  Ready.notify();
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang