[clangd] Add tests that no-op changes are cheap

[sammccall]

Summary

We want to be sure they don't cause AST rebuilds or evict items from the cache.
D77847 is going to start sending spurious no-op changes (in case the preamble
was invalidated), this is cheap enough but we shouldn't regress that in future.

[sammccall]

format

[kadircet]

thanks for doing this LGTM!

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

501

nit:

std::make_tuple(arg.first(), arg.second.UsedBytes != 0, arg.second.PreambleBuilds, arg.second.ASTBuilds) == std::tie(Name, UsesMemory, PreambleBuilds, ASTBuilds);

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

762

nit: maybe we drop these noop updates except the first one.

[sammccall]

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

501

Switched to tie for the trivial fields, but I don't like separating out the unnamed (first()) or nonobvious (UsedBytes!=0) things from what they're compared to.

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

762

I think that allows an implementation that always compares the compile command to the first-ever (i.e. changes to the compile command don't "stick")
This is the primary test that verifies that no-op changes are recognized, so I think we should keep testing that (it's pretty cheap)

clang-tools-extra/clangd/ClangdServer.h

void semanticRanges(PathRef File, const std::vector<Position> &Pos,
                       Callback<std::vector<SelectionRange>> CB);
 
   /// Get all document links in a file.
   void documentLinks(PathRef File, Callback<std::vector<DocumentLink>> CB);
 
   void semanticHighlights(PathRef File,
                           Callback<std::vector<HighlightingToken>>);
 
-  /// Returns estimated memory usage for each of the currently open files.
-  /// The order of results is unspecified.
+  /// Returns estimated memory usage and other statistics for each of the
+  /// currently open files.
   /// Overall memory usage of clangd may be significantly more than reported
   /// here, as this metric does not account (at least) for:
   ///   - memory occupied by static and dynamic index,
   ///   - memory required for in-flight requests,
   /// FIXME: those metrics might be useful too, we should add them.
-  std::vector<std::pair<Path, std::size_t>> getUsedBytesPerFile() const;
+  llvm::StringMap<TUScheduler::FileStats> fileStats() const;
 
   // Blocks the main thread until the server is idle. Only for use in tests.
   // Returns false if the timeout expires.
   LLVM_NODISCARD bool
   blockUntilIdleForTest(llvm::Optional<double> TimeoutSeconds = 10);
 
 private:
   /// FIXME: This stats several files to find a .clang-format file. I/O can be

clang-tools-extra/clangd/ClangdServer.cpp

auto Action =
         if (!InpAST)
           return CB(InpAST.takeError());
         CB(clangd::getSemanticHighlightings(InpAST->AST));
       };
   WorkScheduler.runWithAST("SemanticHighlights", File, std::move(Action),
                            TUScheduler::InvalidateOnUpdate);
 }
 
-std::vector<std::pair<Path, std::size_t>>
-ClangdServer::getUsedBytesPerFile() const {
-  return WorkScheduler.getUsedBytesPerFile();
+llvm::StringMap<TUScheduler::FileStats> ClangdServer::fileStats() const {
+  return WorkScheduler.fileStats();
 }
 
 LLVM_NODISCARD bool
 ClangdServer::blockUntilIdleForTest(llvm::Optional<double> TimeoutSeconds) {
   return WorkScheduler.blockUntilIdle(timeoutSeconds(TimeoutSeconds)) &&
          (!BackgroundIdx ||
           BackgroundIdx->blockUntilIdleForTest(TimeoutSeconds));
 }
 
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/TUScheduler.h

struct Options {
     /// Determines when to keep idle ASTs in memory for future use.
     ASTRetentionPolicy RetentionPolicy;
   };
 
   TUScheduler(const GlobalCompilationDatabase &CDB, const Options &Opts,
               std::unique_ptr<ParsingCallbacks> ASTCallbacks = nullptr);
   ~TUScheduler();
 
-  /// Returns estimated memory usage for each of the currently open files.
-  /// The order of results is unspecified.
-  std::vector<std::pair<Path, std::size_t>> getUsedBytesPerFile() const;
+  struct FileStats {
+    std::size_t UsedBytes = 0;
+    unsigned PreambleBuilds = 0;
+    unsigned ASTBuilds = 0;
+  };
+  /// Returns resources used for each of the currently open files.
+  /// Results are inherently racy as they measure activity of other threads.
+  llvm::StringMap<FileStats> fileStats() const;
 
   /// Returns a list of files with ASTs currently stored in memory. This method
   /// is not very reliable and is only used for test. E.g., the results will not
   /// contain files that currently run something over their AST.
   std::vector<Path> getFilesWithCachedAST() const;
 
   /// Schedule an update for \p File.
   /// The compile command in \p Inputs is ignored; worker queries CDB to get

clang-tools-extra/clangd/TUScheduler.cpp

public:
   tooling::CompileCommand getCurrentCompileCommand() const;
 
   /// Wait for the first build of preamble to finish. Preamble itself can be
   /// accessed via getPossiblyStalePreamble(). Note that this function will
   /// return after an unsuccessful build of the preamble too, i.e. result of
   /// getPossiblyStalePreamble() can be null even after this function returns.
   void waitForFirstPreamble() const;
 
-  std::size_t getUsedBytes() const;
+  TUScheduler::FileStats stats() const;
   bool isASTCached() const;
 
 private:
   /// Publishes diagnostics for \p Inputs. It will build an AST or reuse the
   /// cached one if applicable. Assumes LatestPreamble is compatible for \p
   /// Inputs.
   void generateDiagnostics(std::unique_ptr<CompilerInvocation> Invocation,
                            ParseInputs Inputs, std::vector<Diag> CIDiags);
private:
   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
   // any results to the user.
   bool CanPublishResults = true; /* GUARDED_BY(PublishMu) */
+  std::atomic<unsigned> ASTBuildCount = {0};
+  std::atomic<unsigned> PreambleBuildCount = {0};
 
   SynchronizedTUStatus Status;
   PreambleThread PreamblePeer;
 };
 
 /// A smart-pointer-like class that points to an active ASTWorker.
 /// In destructor, signals to the underlying ASTWorker that no new requests will
 /// be sent and the processing loop may exit (after running all pending
if (!AST) {
       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
       // return a compatible preamble as ASTWorker::update blocks.
-      llvm::Optional<ParsedAST> NewAST =
-          Invocation ? buildAST(FileName, std::move(Invocation),
-                                CompilerInvocationDiagConsumer.take(),
-                                FileInputs, getPossiblyStalePreamble())
-                     : None;
+      llvm::Optional<ParsedAST> NewAST;
+      if (Invocation) {
+        NewAST = buildAST(FileName, std::move(Invocation),
+                          CompilerInvocationDiagConsumer.take(), FileInputs,
+                          getPossiblyStalePreamble());
+        ++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 (!*AST)
       return Action(llvm::make_error<llvm::StringError>(
void ASTWorker::updatePreamble(std::unique_ptr<CompilerInvocation> CI,
   // Store preamble and build diagnostics with new preamble if requested.
   auto Task = [this, Preamble = std::move(Preamble), CI = std::move(CI),
                PI = std::move(PI), CIDiags = std::move(CIDiags),
                WantDiags = std::move(WantDiags)]() mutable {
     // Update the preamble inside ASTWorker queue to ensure atomicity. As a task
     // running inside ASTWorker assumes internals won't change until it
     // finishes.
     if (Preamble != LatestPreamble) {
+      ++PreambleBuildCount;
       // Cached AST is no longer valid.
       IdleASTs.take(this);
       RanASTCallback = false;
       std::lock_guard<std::mutex> Lock(Mutex);
       // LatestPreamble might be the last reference to old preamble, do not
       // trigger destructor while holding the lock.
       std::swap(LatestPreamble, Preamble);
     }
void ASTWorker::generateDiagnostics(
   // FIXME: It might be better to not reuse this AST. That way queued AST builds
   // won't be required for diags.
   llvm::Optional<std::unique_ptr<ParsedAST>> AST = IdleASTs.take(this);
   if (!AST || !InputsAreLatest) {
     auto RebuildStartTime = DebouncePolicy::clock::now();
     llvm::Optional<ParsedAST> NewAST = buildAST(
         FileName, std::move(Invocation), CIDiags, Inputs, LatestPreamble);
     auto RebuildDuration = DebouncePolicy::clock::now() - RebuildStartTime;
+    ++ASTBuildCount;
     // Try to record the AST-build time, to inform future update debouncing.
     // This is best-effort only: if the lock is held, don't bother.
     std::unique_lock<std::mutex> Lock(Mutex, std::try_to_lock);
     if (Lock.owns_lock()) {
       // Do not let RebuildTimes grow beyond its small-size (i.e.
       // capacity).
       if (RebuildTimes.size() == RebuildTimes.capacity())
         RebuildTimes.erase(RebuildTimes.begin());

 
 void ASTWorker::waitForFirstPreamble() const { BuiltFirstPreamble.wait(); }
 
 tooling::CompileCommand ASTWorker::getCurrentCompileCommand() const {
   std::unique_lock<std::mutex> Lock(Mutex);
   return FileInputs.CompileCommand;
 }
 
-std::size_t ASTWorker::getUsedBytes() const {
+TUScheduler::FileStats ASTWorker::stats() const {
+  TUScheduler::FileStats Result;
+  Result.ASTBuilds = ASTBuildCount;
+  Result.PreambleBuilds = PreambleBuildCount;
   // Note that we don't report the size of ASTs currently used for processing
   // the in-flight requests. We used this information for debugging purposes
   // only, so this should be fine.
-  std::size_t Result = IdleASTs.getUsedBytes(this);
+  Result.UsedBytes = IdleASTs.getUsedBytes(this);
   if (auto Preamble = getPossiblyStalePreamble())
-    Result += Preamble->Preamble.getSize();
+    Result.UsedBytes += Preamble->Preamble.getSize();
   return Result;
 }
 
 bool ASTWorker::isASTCached() const { return IdleASTs.getUsedBytes(this) != 0; }
 
 void ASTWorker::stop() {
   {
     std::lock_guard<std::mutex> Lock(PublishMu);
auto Task =
         SPAN_ATTACH(Tracer, "file", File);
         Action(InputsAndPreamble{Contents, Command, Preamble.get()});
       };
 
   PreambleTasks->runAsync("task:" + llvm::sys::path::filename(File),
                           std::move(Task));
 }
 
-std::vector<std::pair<Path, std::size_t>>
-TUScheduler::getUsedBytesPerFile() const {
-  std::vector<std::pair<Path, std::size_t>> Result;
-  Result.reserve(Files.size());
-  for (auto &&PathAndFile : Files)
-    Result.push_back({std::string(PathAndFile.first()),
-                      PathAndFile.second->Worker->getUsedBytes()});
+llvm::StringMap<TUScheduler::FileStats> TUScheduler::fileStats() const {
+  llvm::StringMap<TUScheduler::FileStats> Result;
+  for (const auto &PathAndFile : Files)
+    Result.try_emplace(PathAndFile.first(),
+                       PathAndFile.second->Worker->stats());
   return Result;
 }
 
 std::vector<Path> TUScheduler::getFilesWithCachedAST() const {
   std::vector<Path> Result;
   for (auto &&PathAndFile : Files) {
     if (!PathAndFile.second->Worker->isASTCached())
       continue;

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

 #include <thread>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 
 namespace {
 
+using ::testing::AllOf;
 using ::testing::ElementsAre;
 using ::testing::Field;
 using ::testing::Gt;
 using ::testing::IsEmpty;
 using ::testing::Pair;
 using ::testing::UnorderedElementsAre;
 
 MATCHER_P2(DeclAt, File, Range, "") {
)cpp");
   EXPECT_THAT(DiagConsumer.filesWithDiags(),
               UnorderedElementsAre(Pair(FooCpp, false), Pair(BarCpp, false)));
 
   Locations = runLocateSymbolAt(Server, FooCpp, FooSource.point());
   EXPECT_TRUE(bool(Locations));
   EXPECT_THAT(*Locations, ElementsAre(DeclAt(FooCpp, FooSource.range("two"))));
 }
 
-TEST_F(ClangdVFSTest, MemoryUsage) {
+MATCHER_P4(Stats, Name, UsesMemory, PreambleBuilds, ASTBuilds, "") {
+  return arg.first() == Name && (arg.second.UsedBytes != 0) == UsesMemory &&
+         std::tie(arg.second.PreambleBuilds, ASTBuilds) ==
+             std::tie(PreambleBuilds, ASTBuilds);
+}
+
+TEST_F(ClangdVFSTest, FileStats) {
   MockFSProvider FS;
   ErrorCheckingCallbacks DiagConsumer;
   MockCompilationDatabase CDB;
   ClangdServer Server(CDB, FS, ClangdServer::optsForTest(), &DiagConsumer);
 
   Path FooCpp = testPath("foo.cpp");
   const auto SourceContents = R"cpp(
 struct Something {
   int method();
 };
 )cpp";
   Path BarCpp = testPath("bar.cpp");
 
   FS.Files[FooCpp] = "";
   FS.Files[BarCpp] = "";
 
-  EXPECT_THAT(Server.getUsedBytesPerFile(), IsEmpty());
+  EXPECT_THAT(Server.fileStats(), IsEmpty());
 
   Server.addDocument(FooCpp, SourceContents);
   Server.addDocument(BarCpp, SourceContents);
   ASSERT_TRUE(Server.blockUntilIdleForTest());
 
-  EXPECT_THAT(Server.getUsedBytesPerFile(),
-              UnorderedElementsAre(Pair(FooCpp, Gt(0u)), Pair(BarCpp, Gt(0u))));
+  EXPECT_THAT(Server.fileStats(),
+              UnorderedElementsAre(Stats(FooCpp, true, 1, 1),
+                                   Stats(BarCpp, true, 1, 1)));
 
   Server.removeDocument(FooCpp);
   ASSERT_TRUE(Server.blockUntilIdleForTest());
-  EXPECT_THAT(Server.getUsedBytesPerFile(), ElementsAre(Pair(BarCpp, Gt(0u))));
+  EXPECT_THAT(Server.fileStats(), ElementsAre(Stats(BarCpp, true, 1, 1)));
 
   Server.removeDocument(BarCpp);
   ASSERT_TRUE(Server.blockUntilIdleForTest());
-  EXPECT_THAT(Server.getUsedBytesPerFile(), IsEmpty());
+  EXPECT_THAT(Server.fileStats(), IsEmpty());
 }
 
 TEST_F(ClangdVFSTest, InvalidCompileCommand) {
   MockFSProvider FS;
   ErrorCheckingCallbacks DiagConsumer;
   MockCompilationDatabase CDB;
 
   ClangdServer Server(CDB, FS, ClangdServer::optsForTest(), &DiagConsumer);

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

TEST_F(TUSchedulerTests, EvictedAST) {
   ASSERT_EQ(BuiltASTCounter.load(), 4);
 
   // Check the AST for foo.cpp is retained now and one of the others got
   // evicted.
   EXPECT_THAT(S.getFilesWithCachedAST(),
               UnorderedElementsAre(Foo, AnyOf(Bar, Baz)));
 }
 
+// We send "empty" changes to TUScheduler when we think some external event
+// *might* have invalidated current state (e.g. a header was edited).
+// Verify that this doesn't evict our cache entries.
+TEST_F(TUSchedulerTests, NoopChangesDontThrashCache) {
+  auto Opts = optsForTest();
+  Opts.RetentionPolicy.MaxRetainedASTs = 1;
+  TUScheduler S(CDB, Opts);
+
+  auto Foo = testPath("foo.cpp");
+  auto FooInputs = getInputs(Foo, "int x=1;");
+  auto Bar = testPath("bar.cpp");
+  auto BarInputs = getInputs(Bar, "int x=2;");
+
+  // After opening Foo then Bar, AST cache contains Bar.
+  S.update(Foo, FooInputs, WantDiagnostics::Auto);
+  ASSERT_TRUE(S.blockUntilIdle(timeoutSeconds(10)));
+  S.update(Bar, BarInputs, WantDiagnostics::Auto);
+  ASSERT_TRUE(S.blockUntilIdle(timeoutSeconds(10)));
+  ASSERT_THAT(S.getFilesWithCachedAST(), ElementsAre(Bar));
+
+  // Any number of no-op updates to Foo don't dislodge Bar from the cache.
+  S.update(Foo, FooInputs, WantDiagnostics::Auto);
+  S.update(Foo, FooInputs, WantDiagnostics::Auto);
+  S.update(Foo, FooInputs, WantDiagnostics::Auto);
+  ASSERT_TRUE(S.blockUntilIdle(timeoutSeconds(10)));
+  ASSERT_THAT(S.getFilesWithCachedAST(), ElementsAre(Bar));
+  // In fact each file has been built only once.
+  ASSERT_EQ(S.fileStats().lookup(Foo).ASTBuilds, 1u);
+  ASSERT_EQ(S.fileStats().lookup(Bar).ASTBuilds, 1u);
+}
+
 TEST_F(TUSchedulerTests, EmptyPreamble) {
   TUScheduler S(CDB, optsForTest());
 
   auto Foo = testPath("foo.cpp");
   auto Header = testPath("foo.h");
 
   Files[Header] = "void foo()";
   Timestamps[Header] = time_t(0);
TEST_F(TUSchedulerTests, NoopOnEmptyChanges) {
   TUScheduler S(CDB, optsForTest(), captureDiags());
 
   auto Source = testPath("foo.cpp");
   auto Header = testPath("foo.h");
 
   Files[Header] = "int a;";
   Timestamps[Header] = time_t(0);
 
-  auto SourceContents = R"cpp(
+  std::string SourceContents = R"cpp(
       #include "foo.h"
       int b = a;
     )cpp";
 
   // Return value indicates if the updated callback was received.
   auto DoUpdate = [&](std::string Contents) -> bool {
     std::atomic<bool> Updated(false);
     Updated = false;
     updateWithDiags(S, Source, Contents, WantDiagnostics::Yes,
                     [&Updated](std::vector<Diag>) { Updated = true; });
     bool UpdateFinished = S.blockUntilIdle(timeoutSeconds(10));
     if (!UpdateFinished)
       ADD_FAILURE() << "Updated has not finished in one second. Threading bug?";
     return Updated;
   };
 
   // Test that subsequent updates with the same inputs do not cause rebuilds.
   ASSERT_TRUE(DoUpdate(SourceContents));
+  ASSERT_EQ(S.fileStats().lookup(Source).ASTBuilds, 1u);
+  ASSERT_EQ(S.fileStats().lookup(Source).PreambleBuilds, 1u);
   ASSERT_FALSE(DoUpdate(SourceContents));
+  ASSERT_EQ(S.fileStats().lookup(Source).ASTBuilds, 1u);
+  ASSERT_EQ(S.fileStats().lookup(Source).PreambleBuilds, 1u);
 
   // Update to a header should cause a rebuild, though.
   Timestamps[Header] = time_t(1);
   ASSERT_TRUE(DoUpdate(SourceContents));
   ASSERT_FALSE(DoUpdate(SourceContents));
+  ASSERT_EQ(S.fileStats().lookup(Source).ASTBuilds, 2u);
+  ASSERT_EQ(S.fileStats().lookup(Source).PreambleBuilds, 2u);
 
   // Update to the contents should cause a rebuild.
-  auto OtherSourceContents = R"cpp(
-      #include "foo.h"
-      int c = d;
-    )cpp";
-  ASSERT_TRUE(DoUpdate(OtherSourceContents));
-  ASSERT_FALSE(DoUpdate(OtherSourceContents));
+  SourceContents += "\nint c = b;";
+  ASSERT_TRUE(DoUpdate(SourceContents));
+  ASSERT_FALSE(DoUpdate(SourceContents));
+  ASSERT_EQ(S.fileStats().lookup(Source).ASTBuilds, 3u);
+  ASSERT_EQ(S.fileStats().lookup(Source).PreambleBuilds, 2u);
 
   // Update to the compile commands should also cause a rebuild.
   CDB.ExtraClangFlags.push_back("-DSOMETHING");
-  ASSERT_TRUE(DoUpdate(OtherSourceContents));
-  ASSERT_FALSE(DoUpdate(OtherSourceContents));
+  ASSERT_TRUE(DoUpdate(SourceContents));
+  ASSERT_FALSE(DoUpdate(SourceContents));
+  ASSERT_EQ(S.fileStats().lookup(Source).ASTBuilds, 4u);
+  ASSERT_EQ(S.fileStats().lookup(Source).PreambleBuilds, 3u);
 }
 
 TEST_F(TUSchedulerTests, ForceRebuild) {
   TUScheduler S(CDB, optsForTest(), captureDiags());
 
   auto Source = testPath("foo.cpp");
   auto Header = testPath("foo.h");