[clangd] Publish diagnostics with stale preambles

[kadircet]

Summary

This patch achieves this by building an AST and invoking main file
callbacks on each update, in addition to preamble updates.

It means we might have some extra AST builds now (e.g. if an update was
with a stale preamble and there were no reads on it, we would only build
an AST once we had the fresh preamble. Now we'll build 2, once with the
stale preamble and another with the fresh one, but we'll have one more
diagnostics cycle in between.).

This patch preserves forward progress of diagnostics by always using the
latest main file contents when emitting diagnostics after preamble
builds. It also guarantees eventual consistency:

• if an update doesn't invalidate preamble, we'll emit diagnostics with fresh preamble already.
• if an update invalidates preamble, we'll first emit diagnostics with stale contents, and then once the preamble build finishes it'll emit diagnostics (as preamble has changed) with newest version.

This has implications on parsing callbacks, as previously onMainAST
callback was called at most once, now it can be called up to 2 times.
All of the existing clients can already deal with callback firing
multiple times.

[sammccall]

Looks pretty good. I think we can build the main file & preamble in parallel. Otherwise nits.

clang-tools-extra/clangd/TUScheduler.cpp

946

We should probably kick off the preamble rebuild before doing this synchronous AST rebuild, so the two can run in parallel.

1134

This explanation focuses on the potential problems (why the other behavior is wrong) and on the AllowStalePreamble mode only. I think it would be more enlightening to talk both about problems and correctness, and about the old mode and the new mode.

Maybe:

The file may have been edited since we started building this preamble.

If diagnostics need a fresh preamble, we must use the old version that matches the preamble. We make forward progress as updatePreamble() receives increasing versions, and this is the only place we emit diagnostics.

If diagnostics can use a stale preamble, we use the current contents of the file instead.
This provides more up-to-date diagnostics, and avoids diagnostics going backwards (we may have already emitted staler-preamble diagnostics for the new version). We still have eventual consistency: at some point updatePreamble() will catch up to the current file.

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

1203

class comment?

// Callbacks that blocks the preamble thread after the first preamble is built.

1226

having a method on the PreambleCallbacks which calls update() on the scheduler seems pretty confusing - outside its responsibilities.

I'd suggest just moving this method and its associated state out of the class, and have onMainAST just invoke a callback. (I see the appeal of wrapping this in a class, I just don't think it should be *this* class)

1237

this nullopt stuff isn't used in the test, ADD_FAILURE and return something random instead?

1261

this should rather be *Unblock*Preamble, I think, as that's what triggering it does?

I'd suggest using this name rather than N inside the class too, would make it a bit less mysterious

1273

nit: Pair("1", "1") - tests should be explicit rather than DRY
maybe even Pair(/*Preamble=*/"1", /*Main=*/"1")

(and in the next two - the "eventual consistency" assert is probably fine as-is I think)

[kadircet]

• Notify preamble peer before building an AST, to concurrently build fresh preamble & AST.
• Refactoring for tests

clang-tools-extra/clangd/TUScheduler.cpp

 //
 // Some read requests might just need preamble. Since preambles can be read
 // concurrently, ASTWorker runs these requests on their own thread. These
 // requests will receive latest build preamble, which might possibly be stale.
 
 #include "TUScheduler.h"
 #include "CompileCommands.h"
 #include "Compiler.h"
+#include "Config.h"
 #include "Diagnostics.h"
 #include "GlobalCompilationDatabase.h"
 #include "ParsedAST.h"
 #include "Preamble.h"
 #include "index/CanonicalIncludes.h"
 #include "support/Cancellation.h"
 #include "support/Context.h"
 #include "support/Logger.h"
if (!Invocation) {
       // useful, but this is how we communicate a build error.
       LatestPreamble.emplace();
       // 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);
+    // Inform preamble peer, before attempting to build diagnostics so that they
+    // can be built concurrently.
+    PreamblePeer.update(std::make_unique<CompilerInvocation>(*Invocation),
+                        Inputs, CompilerInvocationDiags, WantDiags);
+
+    // Emit diagnostics from (possibly) stale preamble while waiting for a
+    // rebuild. Newly built preamble cannot emit diagnostics before this call
+    // finishes (ast callbacks are called from astpeer thread), hence we
+    // gurantee eventual consistency.
+    if (LatestPreamble && Config::current().Diagnostics.AllowStalePreamble)
+      generateDiagnostics(std::move(Invocation), std::move(Inputs),
+                          std::move(CompilerInvocationDiags));
+
     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.
       // We block here instead of the consumer to prevent any deadlocks. Since
       // LatestPreamble is only populated by ASTWorker thread.
       return LatestPreamble || !PreambleRequests.empty() || Done;
auto Task = [this, Preamble = std::move(Preamble), CI = std::move(CI),
     // 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;
+    // The file may have been edited since we started building this preamble.
+    // If diagnostics need a fresh preamble, we must use the old version that
+    // matches the preamble. We make forward progress as updatePreamble()
+    // receives increasing versions, and this is the only place we emit
+    // diagnostics.
+    // If diagnostics can use a stale preamble, we use the current contents of
+    // the file instead. This provides more up-to-date diagnostics, and avoids
+    // diagnostics going backwards (we may have already emitted staler-preamble
+    // diagnostics for the new version). We still have eventual consistency: at
+    // some point updatePreamble() will catch up to the current file.
+    if (Config::current().Diagnostics.AllowStalePreamble)
+      PI = FileInputs;
     // 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) {
     runTask(TaskName, Task);
     return;

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

 //===-- TUSchedulerTests.cpp ------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "Annotations.h"
 #include "ClangdServer.h"
+#include "Compiler.h"
+#include "Config.h"
 #include "Diagnostics.h"
 #include "GlobalCompilationDatabase.h"
 #include "Matchers.h"
 #include "ParsedAST.h"
 #include "Preamble.h"
 #include "TUScheduler.h"
 #include "TestFS.h"
 #include "TestIndex.h"
 #include "support/Cancellation.h"
 #include "support/Context.h"
 #include "support/Path.h"
 #include "support/TestTracer.h"
 #include "support/Threading.h"
-#include "support/ThreadsafeFS.h"
 #include "clang/Basic/DiagnosticDriver.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/FunctionExtras.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 <condition_variable>
 #include <cstdint>
+#include <functional>
 #include <memory>
+#include <mutex>
 #include <optional>
 #include <string>
 #include <utility>
+#include <vector>
 
 namespace clang {
 namespace clangd {
 namespace {
 
+using ::testing::_;
 using ::testing::AllOf;
 using ::testing::AnyOf;
 using ::testing::Contains;
 using ::testing::Each;
 using ::testing::ElementsAre;
 using ::testing::Eq;
 using ::testing::Field;
 using ::testing::IsEmpty;
TEST_F(TUSchedulerTests, OnlyPublishWhenPreambleIsBuilt) {
   S.blockUntilIdle(timeoutSeconds(10));
   EXPECT_EQ(PreamblePublishCount, 1);
   // New contents, should publish.
   S.update(File, getInputs(File, "#define FOO"), WantDiagnostics::Auto);
   S.blockUntilIdle(timeoutSeconds(10));
   EXPECT_EQ(PreamblePublishCount, 2);
 }
 
+TEST_F(TUSchedulerTests, PublishWithStalePreamble) {
+  // Callbacks that blocks the preamble thread after the first preamble is
+  // built and stores preamble/main-file versions for diagnostics released.
+  class BlockPreambleThread : public ParsingCallbacks {
+  public:
+    using DiagsCB = std::function<void(ParsedAST &)>;
+    BlockPreambleThread(Notification &UnblockPreamble, DiagsCB CB)
+        : UnblockPreamble(UnblockPreamble), CB(std::move(CB)) {}
+
+    void onPreambleAST(PathRef Path, llvm::StringRef Version,
+                       const CompilerInvocation &, ASTContext &Ctx,
+                       Preprocessor &, const CanonicalIncludes &) override {
+      if (BuildBefore)
+        ASSERT_TRUE(UnblockPreamble.wait(timeoutSeconds(5)))
+            << "Expected notification";
+      BuildBefore = true;
+    }
+
+    void onMainAST(PathRef File, ParsedAST &AST, PublishFn Publish) override {
+      CB(AST);
+    }
+
+    void onFailedAST(PathRef File, llvm::StringRef Version,
+                     std::vector<Diag> Diags, PublishFn Publish) override {
+      ADD_FAILURE() << "Received failed ast for: " << File << " with version "
+                    << Version << '\n';
+    }
+
+  private:
+    bool BuildBefore = false;
+    Notification &UnblockPreamble;
+    std::function<void(ParsedAST &)> CB;
+  };
+
+  // Helpers for issuing blocking update requests on a TUScheduler, whose
+  // onMainAST callback would call onDiagnostics.
+  class DiagCollector {
+  public:
+    void onDiagnostics(ParsedAST &AST) {
+      std::scoped_lock<std::mutex> Lock(DiagMu);
+      DiagVersions.emplace_back(
+          std::make_pair(AST.preambleVersion()->str(), AST.version().str()));
+      DiagsReceived.notify_all();
+    }
+
+    std::pair<std::string, std::string>
+    waitForNewDiags(TUScheduler &S, PathRef File, ParseInputs PI) {
+      std::unique_lock<std::mutex> Lock(DiagMu);
+      // Perform the update under the lock to make sure it isn't handled until
+      // we're waiting for it.
+      S.update(File, std::move(PI), WantDiagnostics::Auto);
+      size_t OldSize = DiagVersions.size();
+      bool ReceivedDiags = DiagsReceived.wait_for(
+          Lock, std::chrono::seconds(5),
+          [this, OldSize] { return OldSize + 1 == DiagVersions.size(); });
+      if (!ReceivedDiags) {
+        ADD_FAILURE() << "Timed out waiting for diags";
+        return {"invalid", "version"};
+      }
+      return DiagVersions.back();
+    }
+
+    std::vector<std::pair<std::string, std::string>> diagVersions() {
+      std::scoped_lock<std::mutex> Lock(DiagMu);
+      return DiagVersions;
+    }
+
+  private:
+    std::condition_variable DiagsReceived;
+    std::mutex DiagMu;
+    std::vector<std::pair</*PreambleVersion*/ std::string,
+                          /*MainFileVersion*/ std::string>>
+        DiagVersions;
+  };
+
+  Config Cfg;
+  Cfg.Diagnostics.AllowStalePreamble = true;
+  WithContextValue WithCfg(Config::Key, std::move(Cfg));
+
+  DiagCollector Collector;
+  Notification UnblockPreamble;
+  auto DiagCallbacks = std::make_unique<BlockPreambleThread>(
+      UnblockPreamble,
+      [&Collector](ParsedAST &AST) { Collector.onDiagnostics(AST); });
+  TUScheduler S(CDB, optsForTest(), std::move(DiagCallbacks));
+  Path File = testPath("foo.cpp");
+  auto BlockForDiags = [&](ParseInputs PI) {
+    return Collector.waitForNewDiags(S, File, std::move(PI));
+  };
+
+  // Build first preamble.
+  auto PI = getInputs(File, "");
+  PI.Version = PI.Contents = "1";
+  ASSERT_THAT(BlockForDiags(PI), testing::Pair("1", "1"));
+
+  // Now preamble thread is blocked, so rest of the requests sees only the
+  // stale preamble.
+  PI.Version = "2";
+  PI.Contents = "#define BAR\n" + PI.Version;
+  ASSERT_THAT(BlockForDiags(PI), testing::Pair("1", "2"));
+
+  PI.Version = "3";
+  PI.Contents = "#define FOO\n" + PI.Version;
+  ASSERT_THAT(BlockForDiags(PI), testing::Pair("1", "3"));
+
+  UnblockPreamble.notify();
+  S.blockUntilIdle(timeoutSeconds(5));
+
+  // Make sure that we have eventual consistency.
+  EXPECT_THAT(Collector.diagVersions().back(), Pair(PI.Version, PI.Version));
+}
+
 // If a header file is missing from the CDB (or inferred using heuristics), and
 // it's included by another open file, then we parse it using that files flags.
 TEST_F(TUSchedulerTests, IncluderCache) {
   static std::string Main = testPath("main.cpp"), Main2 = testPath("main2.cpp"),
                      Main3 = testPath("main3.cpp"),
                      NoCmd = testPath("no_cmd.h"),
                      Unreliable = testPath("unreliable.h"),
                      OK = testPath("ok.h"),