[clangd] Do not rebuild AST if inputs have not changed

[ilya-biryukov]

Summary

If the contents are the same, the update most likely comes from the
fact that compile commands were invalidated. In that case we want to
avoid rebuilds in case the compile commands are actually the same.

[ioeric]

clangd/TUScheduler.cpp

357

nit: (OldPreamble == NewPreamble)

Do you intend to compare the shared pointer instead of the values?

360

Why reset?

376

Do we choose to ignore this because it's rare? What are non-preamble #includes?

379

I think this can be a log.

test/clangd/extra-flags.test

26

Why this change?

[ilya-biryukov]

• Use log instead of vlog
• Add parens around &&

[ilya-biryukov]

clangd/TUScheduler.cpp

357

Yes, this is intentional. buildPreamble will either return the old one, if it can be reused, or build the new one.

360

We don't need the old preamble at this point, so we give it a chance to die (if there are no more references).
Note that there's an expensive operation that follows (building the AST), so removing the preamble before it seems like a win

376

Exactly, we don't have the code to track and check for all accessed files.
This should be rare, hopefully won't show up in practice.

test/clangd/extra-flags.test

26

The test expects two publishDiagnostics, but it won't get the second one since if the contents of the file are the same :-)
So I altered the contents a bit to make sure we get the second result too

[ioeric]

lg

clangd/TUScheduler.cpp

360

sg. and do we guard this with mutex because the same old preamble data can be accessed by other threads? might worth a comment.

[simark]

Thanks, that's simple and efficient. I'll update D49267 (to call reparseOpenFiles once again) once this is merged.

[ilya-biryukov]

• Move OldPreamble.reset() out of the lock, add a comment

[ilya-biryukov]

clangd/TUScheduler.cpp

360

Guarding with mutex is not actually required. Moved it out of the locked section and added a comment, thanks!

[ilya-biryukov]

In D49783#1175688, @simark wrote:

Thanks, that's simple and efficient. I'll update D49267 (to call reparseOpenFiles once again) once this is merged.

LG, thanks!

clangd/TUScheduler.cpp

#ifndef NDEBUG
   assert(Requests.empty() && "unprocessed requests when destroying ASTWorker");
 #endif
 }
 
 void ASTWorker::update(
     ParseInputs Inputs, WantDiagnostics WantDiags,
     llvm::unique_function<void(std::vector<Diag>)> OnUpdated) {
   auto Task = [=](decltype(OnUpdated) OnUpdated) mutable {
+    // Will be used to check if we can avoid rebuilding the AST.
+    bool InputsAreTheSame =
+        std::tie(FileInputs.CompileCommand, FileInputs.Contents) ==
+        std::tie(Inputs.CompileCommand, Inputs.Contents);
+
     tooling::CompileCommand OldCommand = std::move(FileInputs.CompileCommand);
     FileInputs = Inputs;
     // Remove the old AST if it's still in cache.
     IdleASTs.take(this);
 
     log("Updating file {0} with command [{1}] {2}", FileName,
         Inputs.CompileCommand.Directory,
         llvm::join(Inputs.CompileCommand.CommandLine, " "));
     // Rebuild the preamble and the AST.
     std::unique_ptr<CompilerInvocation> Invocation =
         buildCompilerInvocation(Inputs);
     if (!Invocation) {
       elog("Could not build CompilerInvocation for file {0}", FileName);
       // Make sure anyone waiting for the preamble gets notified it could not
       // be built.
       PreambleWasBuilt.notify();
       return;
     }
 
-    std::shared_ptr<const PreambleData> NewPreamble = buildPreamble(
-        FileName, *Invocation, getPossiblyStalePreamble(), OldCommand, Inputs,
+    std::shared_ptr<const PreambleData> OldPreamble =
+        getPossiblyStalePreamble();
+    std::shared_ptr<const PreambleData> NewPreamble =
+        buildPreamble(FileName, *Invocation, OldPreamble, OldCommand, Inputs,
                       PCHs, StorePreambleInMemory, PreambleCallback);
+
+    bool CanReuseAST = InputsAreTheSame && (OldPreamble == NewPreamble);
     {
       std::lock_guard<std::mutex> Lock(Mutex);
       if (NewPreamble)
         LastBuiltPreamble = NewPreamble;
     }
+    // Before doing the expensive AST reparse, we want to release our reference
+    // to the old preamble, so it can be freed if there are no other references
+    // to it.
+    OldPreamble.reset();
     PreambleWasBuilt.notify();
 
+    if (CanReuseAST) {
+      // Take a shortcut and don't build the AST, neither the inputs nor the
+      // preamble have changed.
+      // Note that we do not report the diagnostics, since they should not have
+      // changed either. All the clients should handle the lack of OnUpdated()
+      // call anyway, to handle empty result from buildAST.
+      // FIXME(ibiryukov): the AST could actually change if non-preamble
+      // includes changed, but we choose to ignore it.
+      // FIXME(ibiryukov): should we refresh the cache in IdleASTs for the
+      // current file at this point?
+      log("Skipping rebuild of the AST for {0}, inputs are the same.",
+          FileName);
+      return;
+    }
     // Build the AST for diagnostics.
     llvm::Optional<ParsedAST> AST =
         buildAST(FileName, std::move(Invocation), Inputs, NewPreamble, PCHs);
     // We want to report the diagnostics even if this update was cancelled.
     // It seems more useful than making the clients wait indefinitely if they
     // spam us with updates.
     if (WantDiags != WantDiagnostics::No && AST)
       OnUpdated(AST->getDiagnostics());

test/clangd/extra-flags.test

 # CHECK-NEXT:          }
 # CHECK-NEXT:        },
 # CHECK-NEXT:        "severity": 2
 # CHECK-NEXT:      }
 # CHECK-NEXT:    ],
 # CHECK-NEXT:    "uri": "file://{{.*}}/foo.c"
 # CHECK-NEXT:  }
 ---
-{"jsonrpc":"2.0","method":"textDocument/didChange","params":{"textDocument":{"uri":"test:///foo.c","version":2},"contentChanges":[{"text":"int main() { int i; return i; }"}]}}
+{"jsonrpc":"2.0","method":"textDocument/didChange","params":{"textDocument":{"uri":"test:///foo.c","version":2},"contentChanges":[{"text":"int main() { int i; return i+1; }"}]}}
 #      CHECK:  "method": "textDocument/publishDiagnostics",
 # CHECK-NEXT:  "params": {
 # CHECK-NEXT:    "diagnostics": [
 # CHECK-NEXT:      {
 # CHECK-NEXT:        "message": "variable 'i' is uninitialized when used here",
 # CHECK-NEXT:        "range": {
 # CHECK-NEXT:          "end": {
 # CHECK-NEXT:            "character": 28,

unittests/clangd/TUSchedulerTests.cpp

 void ignoreUpdate(llvm::Optional<std::vector<Diag>>) {}
 void ignoreError(llvm::Error Err) {
   handleAllErrors(std::move(Err), [](const llvm::ErrorInfoBase &) {});
 }
 
 class TUSchedulerTests : public ::testing::Test {
 protected:
   ParseInputs getInputs(PathRef File, std::string Contents) {
-    return ParseInputs{*CDB.getCompileCommand(File), buildTestFS(Files),
-                       std::move(Contents)};
+    return ParseInputs{*CDB.getCompileCommand(File),
+                       buildTestFS(Files, Timestamps), std::move(Contents)};
   }
 
   llvm::StringMap<std::string> Files;
-
-private:
+  llvm::StringMap<time_t> Timestamps;
   MockCompilationDatabase CDB;
 };
 
 TEST_F(TUSchedulerTests, MissingFiles) {
   TUScheduler S(getDefaultAsyncThreadsCount(),
                 /*StorePreamblesInMemory=*/true,
                 /*PreambleParsedCallback=*/nullptr,
                 /*UpdateDebounce=*/std::chrono::steady_clock::duration::zero(),
TUScheduler S(
       /*AsyncThreadsCount=*/1, /*StorePreambleInMemory=*/true,
       PreambleParsedCallback(),
       /*UpdateDebounce=*/std::chrono::steady_clock::duration::zero(), Policy);
 
   llvm::StringLiteral SourceContents = R"cpp(
     int* a;
     double* b = a;
   )cpp";
+  llvm::StringLiteral OtherSourceContents = R"cpp(
+    int* a;
+    double* b = a + 0;
+  )cpp";
 
   auto Foo = testPath("foo.cpp");
   auto Bar = testPath("bar.cpp");
   auto Baz = testPath("baz.cpp");
 
   // Build one file in advance. We will not access it later, so it will be the
   // one that the cache will evict.
   S.update(Foo, getInputs(Foo, SourceContents), WantDiagnostics::Yes,
S.update(Baz, getInputs(Baz, SourceContents), WantDiagnostics::Yes,
            [&BuiltASTCounter](std::vector<Diag> Diags) { ++BuiltASTCounter; });
   ASSERT_TRUE(S.blockUntilIdle(timeoutSeconds(1)));
   ASSERT_EQ(BuiltASTCounter.load(), 3);
 
   // Check only the last two ASTs are retained.
   ASSERT_THAT(S.getFilesWithCachedAST(), UnorderedElementsAre(Bar, Baz));
 
   // Access the old file again.
-  S.update(Foo, getInputs(Foo, SourceContents), WantDiagnostics::Yes,
+  S.update(Foo, getInputs(Foo, OtherSourceContents), WantDiagnostics::Yes,
            [&BuiltASTCounter](std::vector<Diag> Diags) { ++BuiltASTCounter; });
   ASSERT_TRUE(S.blockUntilIdle(timeoutSeconds(1)));
   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)));
TEST_F(TUSchedulerTests, RunWaitsForPreamble) {
   }
   ASSERT_TRUE(S.blockUntilIdle(timeoutSeconds(10)));
   // Check all actions got the same non-null preamble.
   std::lock_guard<std::mutex> Lock(PreamblesMut);
   ASSERT_NE(Preambles[0], nullptr);
   ASSERT_THAT(Preambles, Each(Preambles[0]));
 }
 
+TEST_F(TUSchedulerTests, NoopOnEmptyChanges) {
+  TUScheduler S(
+      /*AsyncThreadsCount=*/getDefaultAsyncThreadsCount(),
+      /*StorePreambleInMemory=*/true, PreambleParsedCallback(),
+      /*UpdateDebounce=*/std::chrono::steady_clock::duration::zero(),
+      ASTRetentionPolicy());
+
+  auto Source = testPath("foo.cpp");
+  auto Header = testPath("foo.h");
+
+  Files[Header] = "int a;";
+  Timestamps[Header] = time_t(0);
+
+  auto SourceContents = R"cpp(
+      #include "foo.h"
+      int b = a;
+    )cpp";
+
+  // Return value indicates if the updated callback was received.
+  auto DoUpdate = [&](ParseInputs Inputs) -> bool {
+    std::atomic<bool> Updated(false);
+    Updated = false;
+    S.update(Source, std::move(Inputs), WantDiagnostics::Yes,
+             [&Updated](std::vector<Diag>) { Updated = true; });
+    bool UpdateFinished = S.blockUntilIdle(timeoutSeconds(1));
+    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(getInputs(Source, SourceContents)));
+  ASSERT_FALSE(DoUpdate(getInputs(Source, SourceContents)));
+
+  // Update to a header should cause a rebuild, though.
+  Files[Header] = time_t(1);
+  ASSERT_TRUE(DoUpdate(getInputs(Source, SourceContents)));
+  ASSERT_FALSE(DoUpdate(getInputs(Source, SourceContents)));
+
+  // Update to the contents should cause a rebuild.
+  auto OtherSourceContents = R"cpp(
+      #include "foo.h"
+      int c = d;
+    )cpp";
+  ASSERT_TRUE(DoUpdate(getInputs(Source, OtherSourceContents)));
+  ASSERT_FALSE(DoUpdate(getInputs(Source, OtherSourceContents)));
+
+  // Update to the compile commands should also cause a rebuild.
+  CDB.ExtraClangFlags.push_back("-DSOMETHING");
+  ASSERT_TRUE(DoUpdate(getInputs(Source, OtherSourceContents)));
+  ASSERT_FALSE(DoUpdate(getInputs(Source, OtherSourceContents)));
+}
+
 } // namespace clangd
 } // namespace clang

unittests/clangd/TestFS.h

 #include "llvm/Support/Path.h"
 
 namespace clang {
 namespace clangd {
 
 // Builds a VFS that provides access to the provided files, plus temporary
 // directories.
 llvm::IntrusiveRefCntPtr<vfs::FileSystem>
-buildTestFS(llvm::StringMap<std::string> const &Files);
+buildTestFS(llvm::StringMap<std::string> const &Files,
+            llvm::StringMap<time_t> const &Timestamps = {});
 
 // A VFS provider that returns TestFSes containing a provided set of files.
 class MockFSProvider : public FileSystemProvider {
 public:
   IntrusiveRefCntPtr<vfs::FileSystem> getFileSystem() override {
     return buildTestFS(Files);
   }
 

unittests/clangd/TestFS.cpp

 #include "llvm/Support/Path.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace clangd {
 using namespace llvm;
 
 IntrusiveRefCntPtr<vfs::FileSystem>
-buildTestFS(StringMap<std::string> const &Files) {
+buildTestFS(llvm::StringMap<std::string> const &Files,
+            llvm::StringMap<time_t> const &Timestamps) {
   IntrusiveRefCntPtr<vfs::InMemoryFileSystem> MemFS(
       new vfs::InMemoryFileSystem);
   for (auto &FileAndContents : Files) {
-    MemFS->addFile(FileAndContents.first(), time_t(),
-                   MemoryBuffer::getMemBufferCopy(FileAndContents.second,
-                                                  FileAndContents.first()));
+    StringRef File = FileAndContents.first();
+    MemFS->addFile(
+        File, Timestamps.lookup(File),
+        MemoryBuffer::getMemBufferCopy(FileAndContents.second, File));
   }
   return MemFS;
 }
 
 MockCompilationDatabase::MockCompilationDatabase(bool UseRelPaths)
     : ExtraClangFlags({"-ffreestanding"}), UseRelPaths(UseRelPaths) {
   // -ffreestanding avoids implicit stdc-predef.h.
 }