diff --git a/clang-tools-extra/clangd/index/Background.h b/clang-tools-extra/clangd/index/Background.h --- a/clang-tools-extra/clangd/index/Background.h +++ b/clang-tools-extra/clangd/index/Background.h @@ -76,6 +76,8 @@ llvm::ThreadPriority ThreadPri = llvm::ThreadPriority::Background; unsigned QueuePri = 0; // Higher-priority tasks will run first. std::string Tag; // Allows priority to be boosted later. + uint64_t Key = 0; // If the key matches a previous task, drop this one. + // (in practice this means we never reindex a file). bool operator<(const Task &O) const { return QueuePri < O.QueuePri; } }; @@ -114,6 +116,7 @@ private: void notifyProgress() const; // Requires lock Mu + bool adjust(Task &T); std::mutex Mu; Stats Stat; @@ -122,6 +125,7 @@ std::vector Queue; // max-heap llvm::StringMap Boosts; std::function OnProgress; + llvm::DenseSet SeenKeys; }; // Builds an in-memory index by by running the static indexer action over diff --git a/clang-tools-extra/clangd/index/Background.cpp b/clang-tools-extra/clangd/index/Background.cpp --- a/clang-tools-extra/clangd/index/Background.cpp +++ b/clang-tools-extra/clangd/index/Background.cpp @@ -43,6 +43,7 @@ #include "llvm/Support/Error.h" #include "llvm/Support/Path.h" #include "llvm/Support/Threading.h" +#include "llvm/Support/xxhash.h" #include #include @@ -139,8 +140,8 @@ std::mt19937(std::random_device{}())); std::vector Tasks; Tasks.reserve(NeedsReIndexing.size()); - for (auto &Cmd : NeedsReIndexing) - Tasks.push_back(indexFileTask(std::move(Cmd))); + for (const auto &File : NeedsReIndexing) + Tasks.push_back(indexFileTask(std::move(File))); Queue.append(std::move(Tasks)); }); @@ -156,6 +157,7 @@ BackgroundQueue::Task BackgroundIndex::indexFileTask(std::string Path) { std::string Tag = filenameWithoutExtension(Path).str(); + uint64_t Key = llvm::xxHash64(Path); BackgroundQueue::Task T([this, Path(std::move(Path))] { llvm::Optional WithProvidedContext; if (ContextProvider) @@ -168,6 +170,7 @@ }); T.QueuePri = IndexFile; T.Tag = std::move(Tag); + T.Key = Key; return T; } diff --git a/clang-tools-extra/clangd/index/BackgroundQueue.cpp b/clang-tools-extra/clangd/index/BackgroundQueue.cpp --- a/clang-tools-extra/clangd/index/BackgroundQueue.cpp +++ b/clang-tools-extra/clangd/index/BackgroundQueue.cpp @@ -72,10 +72,24 @@ CV.notify_all(); } +// Tweaks the priority of a newly-enqueued task, or returns false to cancel it. +bool BackgroundQueue::adjust(Task &T) { + // It is tempting to drop duplicates of queued tasks, and merely deprioritize + // duplicates of completed tasks (i.e. reindexing on CDB changes). But: + // - the background indexer doesn't support reindexing well, e.g. staleness + // is checked at *enqueue* time only, and doesn't account for compile flags + // - reindexing on compile flags is often a poor use of CPU in practice + if (T.Key && !SeenKeys.insert(T.Key).second) + return false; + T.QueuePri = std::max(T.QueuePri, Boosts.lookup(T.Tag)); + return true; +} + void BackgroundQueue::push(Task T) { { std::lock_guard Lock(Mu); - T.QueuePri = std::max(T.QueuePri, Boosts.lookup(T.Tag)); + if (!adjust(T)) + return; Queue.push_back(std::move(T)); std::push_heap(Queue.begin(), Queue.end()); ++Stat.Enqueued; @@ -87,11 +101,13 @@ void BackgroundQueue::append(std::vector Tasks) { { std::lock_guard Lock(Mu); - for (Task &T : Tasks) - T.QueuePri = std::max(T.QueuePri, Boosts.lookup(T.Tag)); - std::move(Tasks.begin(), Tasks.end(), std::back_inserter(Queue)); + for (Task &T : Tasks) { + if (!adjust(T)) + continue; + Queue.push_back(std::move(T)); + ++Stat.Enqueued; + } std::make_heap(Queue.begin(), Queue.end()); - Stat.Enqueued += Tasks.size(); notifyProgress(); } CV.notify_all(); diff --git a/clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp b/clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp --- a/clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp +++ b/clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp @@ -9,6 +9,7 @@ #include "index/BackgroundRebuild.h" #include "clang/Tooling/ArgumentsAdjusters.h" #include "clang/Tooling/CompilationDatabase.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/Support/ScopedPrinter.h" #include "llvm/Support/Threading.h" #include "gmock/gmock.h" @@ -666,25 +667,45 @@ // Make sure we only store the Cmd for main file. EXPECT_FALSE(MSS.loadShard(testPath("A.h"))->Cmd); - { - tooling::CompileCommand CmdStored = *MSS.loadShard(testPath("A.cc"))->Cmd; - EXPECT_EQ(CmdStored.CommandLine, Cmd.CommandLine); - EXPECT_EQ(CmdStored.Directory, Cmd.Directory); - } + tooling::CompileCommand CmdStored = *MSS.loadShard(testPath("A.cc"))->Cmd; + EXPECT_EQ(CmdStored.CommandLine, Cmd.CommandLine); + EXPECT_EQ(CmdStored.Directory, Cmd.Directory); +} - // FIXME: Changing compile commands should be enough to invalidate the cache. - FS.Files[testPath("A.cc")] = " "; - Cmd.CommandLine = {"clang++", "../A.cc", "-Dfoo", "-fsyntax-only"}; - CDB.setCompileCommand(testPath("build/../A.cc"), Cmd); +TEST_F(BackgroundIndexTest, Reindex) { + MockFS FS; + llvm::StringMap Storage; + size_t CacheHits = 0; + MemoryShardStorage MSS(Storage, CacheHits); + OverlayCDB CDB(/*Base=*/nullptr); + BackgroundIndex Idx(FS, CDB, [&](llvm::StringRef) { return &MSS; }, + /*Opts=*/{}); + + // Index a file. + FS.Files[testPath("A.cc")] = "int theOldFunction();"; + tooling::CompileCommand Cmd; + Cmd.Filename = "../A.cc"; + Cmd.Directory = testPath("build"); + Cmd.CommandLine = {"clang++", "../A.cc", "-fsyntax-only"}; + CDB.setCompileCommand(testPath("A.cc"), Cmd); ASSERT_TRUE(Idx.blockUntilIdleForTest()); - EXPECT_FALSE(MSS.loadShard(testPath("A.h"))->Cmd); + // Verify the result is indexed and stored. + EXPECT_EQ(1u, runFuzzyFind(Idx, "theOldFunction").size()); + EXPECT_EQ(0u, runFuzzyFind(Idx, "theNewFunction").size()); + std::string OldShard = Storage.lookup(testPath("A.cc")); + EXPECT_NE("", OldShard); - { - tooling::CompileCommand CmdStored = *MSS.loadShard(testPath("A.cc"))->Cmd; - EXPECT_EQ(CmdStored.CommandLine, Cmd.CommandLine); - EXPECT_EQ(CmdStored.Directory, Cmd.Directory); - } + // Change the content and command, and notify to reindex it. + Cmd.CommandLine.push_back("-DFOO"); + FS.Files[testPath("A.cc")] = "int theNewFunction();"; + CDB.setCompileCommand(testPath("A.cc"), Cmd); + ASSERT_TRUE(Idx.blockUntilIdleForTest()); + + // Currently, we will never index the same main file again. + EXPECT_EQ(1u, runFuzzyFind(Idx, "theOldFunction").size()); + EXPECT_EQ(0u, runFuzzyFind(Idx, "theNewFunction").size()); + EXPECT_EQ(OldShard, Storage.lookup(testPath("A.cc"))); } class BackgroundIndexRebuilderTest : public testing::Test { @@ -829,6 +850,31 @@ } } +TEST(BackgroundQueueTest, Duplicates) { + std::string Sequence; + BackgroundQueue::Task A([&] { Sequence.push_back('A'); }); + A.QueuePri = 100; + A.Key = 1; + BackgroundQueue::Task B([&] { Sequence.push_back('B'); }); + // B has no key, and is not subject to duplicate detection. + B.QueuePri = 50; + + BackgroundQueue Q; + Q.append({A, B, A, B}); // One A is dropped, the other is high priority. + Q.work(/*OnIdle=*/[&] { + // The first time we go idle, we enqueue the same task again. + if (!llvm::is_contained(Sequence, ' ')) { + Sequence.push_back(' '); + Q.append({A, B, A, B}); // Both As are dropped. + } else { + Q.stop(); + } + }); + + // This could reasonably be "ABB BBA", if we had good *re*indexing support. + EXPECT_EQ("ABB BB", Sequence); +} + TEST(BackgroundQueueTest, Progress) { using testing::AnyOf; BackgroundQueue::Stats S;