Index: clang-tools-extra/trunk/clangd/ClangdLSPServer.cpp =================================================================== --- clang-tools-extra/trunk/clangd/ClangdLSPServer.cpp +++ clang-tools-extra/trunk/clangd/ClangdLSPServer.cpp @@ -405,7 +405,7 @@ : Out(Out), CDB(std::move(CompileCommandsDir)), CCOpts(CCOpts), Server(CDB, /*DiagConsumer=*/*this, FSProvider, AsyncThreadsCount, StorePreamblesInMemory, BuildDynamicSymbolIndex, StaticIdx, - ResourceDir) {} + ResourceDir, /*UpdateDebounce=*/std::chrono::milliseconds(500)) {} bool ClangdLSPServer::run(std::istream &In, JSONStreamStyle InputStyle) { assert(!IsDone && "Run was called before"); Index: clang-tools-extra/trunk/clangd/ClangdServer.h =================================================================== --- clang-tools-extra/trunk/clangd/ClangdServer.h +++ clang-tools-extra/trunk/clangd/ClangdServer.h @@ -125,6 +125,8 @@ /// \p DiagConsumer. Note that a callback to \p DiagConsumer happens on a /// worker thread. Therefore, instances of \p DiagConsumer must properly /// synchronize access to shared state. + /// UpdateDebounce determines how long to wait after a new version of the file + /// before starting to compute diagnostics. /// /// \p StorePreamblesInMemory defines whether the Preambles generated by /// clangd are stored in-memory or on disk. @@ -135,13 +137,17 @@ /// /// If \p StaticIdx is set, ClangdServer uses the index for global code /// completion. + /// FIXME(sammccall): pull out an options struct. ClangdServer(GlobalCompilationDatabase &CDB, DiagnosticsConsumer &DiagConsumer, FileSystemProvider &FSProvider, unsigned AsyncThreadsCount, bool StorePreamblesInMemory, bool BuildDynamicSymbolIndex = false, SymbolIndex *StaticIdx = nullptr, - llvm::Optional ResourceDir = llvm::None); + llvm::Optional ResourceDir = llvm::None, + /* Tiny default debounce, so tests hit the debounce logic */ + std::chrono::steady_clock::duration UpdateDebounce = + std::chrono::milliseconds(20)); /// Set the root path of the workspace. void setRootPath(PathRef RootPath); Index: clang-tools-extra/trunk/clangd/ClangdServer.cpp =================================================================== --- clang-tools-extra/trunk/clangd/ClangdServer.cpp +++ clang-tools-extra/trunk/clangd/ClangdServer.cpp @@ -76,7 +76,8 @@ unsigned AsyncThreadsCount, bool StorePreamblesInMemory, bool BuildDynamicSymbolIndex, SymbolIndex *StaticIdx, - llvm::Optional ResourceDir) + llvm::Optional ResourceDir, + std::chrono::steady_clock::duration UpdateDebounce) : CompileArgs(CDB, ResourceDir ? ResourceDir->str() : getStandardResourceDir()), DiagConsumer(DiagConsumer), FSProvider(FSProvider), @@ -91,7 +92,8 @@ FileIdx ? [this](PathRef Path, ParsedAST *AST) { FileIdx->update(Path, AST); } - : ASTParsedCallback()) { + : ASTParsedCallback(), + UpdateDebounce) { if (FileIdx && StaticIdx) { MergedIndex = mergeIndex(FileIdx.get(), StaticIdx); Index = MergedIndex.get(); Index: clang-tools-extra/trunk/clangd/TUScheduler.h =================================================================== --- clang-tools-extra/trunk/clangd/TUScheduler.h +++ clang-tools-extra/trunk/clangd/TUScheduler.h @@ -17,6 +17,7 @@ namespace clang { namespace clangd { + /// Returns a number of a default async threads to use for TUScheduler. /// Returned value is always >= 1 (i.e. will not cause requests to be processed /// synchronously). @@ -46,10 +47,12 @@ /// and scheduling tasks. /// Callbacks are run on a threadpool and it's appropriate to do slow work in /// them. Each task has a name, used for tracing (should be UpperCamelCase). +/// FIXME(sammccall): pull out a scheduler options struct. class TUScheduler { public: TUScheduler(unsigned AsyncThreadsCount, bool StorePreamblesInMemory, - ASTParsedCallback ASTCallback); + ASTParsedCallback ASTCallback, + std::chrono::steady_clock::duration UpdateDebounce); ~TUScheduler(); /// Returns estimated memory usage for each of the currently open files. @@ -101,6 +104,7 @@ // asynchronously. llvm::Optional PreambleTasks; llvm::Optional WorkerThreads; + std::chrono::steady_clock::duration UpdateDebounce; }; } // namespace clangd } // namespace clang Index: clang-tools-extra/trunk/clangd/TUScheduler.cpp =================================================================== --- clang-tools-extra/trunk/clangd/TUScheduler.cpp +++ clang-tools-extra/trunk/clangd/TUScheduler.cpp @@ -54,6 +54,7 @@ namespace clang { namespace clangd { +using std::chrono::steady_clock; namespace { class ASTWorkerHandle; @@ -69,8 +70,8 @@ /// worker. class ASTWorker { friend class ASTWorkerHandle; - ASTWorker(llvm::StringRef File, Semaphore &Barrier, CppFile AST, - bool RunSync); + ASTWorker(llvm::StringRef File, Semaphore &Barrier, CppFile AST, bool RunSync, + steady_clock::duration UpdateDebounce); public: /// Create a new ASTWorker and return a handle to it. @@ -79,7 +80,8 @@ /// synchronously instead. \p Barrier is acquired when processing each /// request, it is be used to limit the number of actively running threads. static ASTWorkerHandle Create(llvm::StringRef File, AsyncTaskRunner *Tasks, - Semaphore &Barrier, CppFile AST); + Semaphore &Barrier, CppFile AST, + steady_clock::duration UpdateDebounce); ~ASTWorker(); void update(ParseInputs Inputs, WantDiagnostics, @@ -101,18 +103,27 @@ /// Adds a new task to the end of the request queue. void startTask(llvm::StringRef Name, UniqueFunction Task, llvm::Optional UpdateType); + /// Determines the next action to perform. + /// All actions that should never run are disarded. + /// Returns a deadline for the next action. If it's expired, run now. + /// scheduleLocked() is called again at the deadline, or if requests arrive. + Deadline scheduleLocked(); /// Should the first task in the queue be skipped instead of run? bool shouldSkipHeadLocked() const; struct Request { UniqueFunction Action; std::string Name; + steady_clock::time_point AddTime; Context Ctx; llvm::Optional UpdateType; }; - std::string File; + const std::string File; const bool RunSync; + // Time to wait after an update to see whether another update obsoletes it. + const steady_clock::duration UpdateDebounce; + Semaphore &Barrier; // AST and FileInputs are only accessed on the processing thread from run(). CppFile AST; @@ -172,9 +183,10 @@ }; ASTWorkerHandle ASTWorker::Create(llvm::StringRef File, AsyncTaskRunner *Tasks, - Semaphore &Barrier, CppFile AST) { - std::shared_ptr Worker( - new ASTWorker(File, Barrier, std::move(AST), /*RunSync=*/!Tasks)); + Semaphore &Barrier, CppFile AST, + steady_clock::duration UpdateDebounce) { + std::shared_ptr Worker(new ASTWorker( + File, Barrier, std::move(AST), /*RunSync=*/!Tasks, UpdateDebounce)); if (Tasks) Tasks->runAsync("worker:" + llvm::sys::path::filename(File), [Worker]() { Worker->run(); }); @@ -183,9 +195,9 @@ } ASTWorker::ASTWorker(llvm::StringRef File, Semaphore &Barrier, CppFile AST, - bool RunSync) - : File(File), RunSync(RunSync), Barrier(Barrier), AST(std::move(AST)), - Done(false) { + bool RunSync, steady_clock::duration UpdateDebounce) + : File(File), RunSync(RunSync), UpdateDebounce(UpdateDebounce), + Barrier(Barrier), AST(std::move(AST)), Done(false) { if (RunSync) return; } @@ -275,8 +287,8 @@ { std::lock_guard Lock(Mutex); assert(!Done && "running a task after stop()"); - Requests.push_back( - {std::move(Task), Name, Context::current().clone(), UpdateType}); + Requests.push_back({std::move(Task), Name, steady_clock::now(), + Context::current().clone(), UpdateType}); } RequestsCV.notify_all(); } @@ -286,17 +298,31 @@ Request Req; { std::unique_lock Lock(Mutex); - RequestsCV.wait(Lock, [&]() { return Done || !Requests.empty(); }); - if (Requests.empty()) { - assert(Done); - return; - } - // Even when Done is true, we finish processing all pending requests - // before exiting the processing loop. + for (auto Wait = scheduleLocked(); !Wait.expired(); + Wait = scheduleLocked()) { + if (Done) { + if (Requests.empty()) + return; + else // Even though Done is set, finish pending requests. + break; // However, skip delays to shutdown fast. + } + + // Tracing: we have a next request, attribute this sleep to it. + Optional Ctx; + Optional Tracer; + if (!Requests.empty()) { + Ctx.emplace(Requests.front().Ctx.clone()); + Tracer.emplace("Debounce"); + SPAN_ATTACH(*Tracer, "next_request", Requests.front().Name); + if (!(Wait == Deadline::infinity())) + SPAN_ATTACH(*Tracer, "sleep_ms", + std::chrono::duration_cast( + Wait.time() - steady_clock::now()) + .count()); + } - while (shouldSkipHeadLocked()) - Requests.pop_front(); - assert(!Requests.empty() && "skipped the whole queue"); + wait(Lock, RequestsCV, Wait); + } Req = std::move(Requests.front()); // Leave it on the queue for now, so waiters don't see an empty queue. } // unlock Mutex @@ -316,6 +342,24 @@ } } +Deadline ASTWorker::scheduleLocked() { + if (Requests.empty()) + return Deadline::infinity(); // Wait for new requests. + while (shouldSkipHeadLocked()) + Requests.pop_front(); + assert(!Requests.empty() && "skipped the whole queue"); + // Some updates aren't dead yet, but never end up being used. + // e.g. the first keystroke is live until obsoleted by the second. + // We debounce "maybe-unused" writes, sleeping 500ms in case they become dead. + // But don't delay reads (including updates where diagnostics are needed). + for (const auto &R : Requests) + if (R.UpdateType == None || R.UpdateType == WantDiagnostics::Yes) + return Deadline::zero(); + // Front request needs to be debounced, so determine when we're ready. + Deadline D(Requests.front().AddTime + UpdateDebounce); + return D; +} + // Returns true if Requests.front() is a dead update that can be skipped. bool ASTWorker::shouldSkipHeadLocked() const { assert(!Requests.empty()); @@ -370,10 +414,12 @@ TUScheduler::TUScheduler(unsigned AsyncThreadsCount, bool StorePreamblesInMemory, - ASTParsedCallback ASTCallback) + ASTParsedCallback ASTCallback, + steady_clock::duration UpdateDebounce) : StorePreamblesInMemory(StorePreamblesInMemory), PCHOps(std::make_shared()), - ASTCallback(std::move(ASTCallback)), Barrier(AsyncThreadsCount) { + ASTCallback(std::move(ASTCallback)), Barrier(AsyncThreadsCount), + UpdateDebounce(UpdateDebounce) { if (0 < AsyncThreadsCount) { PreambleTasks.emplace(); WorkerThreads.emplace(); @@ -409,7 +455,8 @@ // Create a new worker to process the AST-related tasks. ASTWorkerHandle Worker = ASTWorker::Create( File, WorkerThreads ? WorkerThreads.getPointer() : nullptr, Barrier, - CppFile(File, StorePreamblesInMemory, PCHOps, ASTCallback)); + CppFile(File, StorePreamblesInMemory, PCHOps, ASTCallback), + UpdateDebounce); FD = std::unique_ptr(new FileData{Inputs, std::move(Worker)}); } else { FD->Inputs = Inputs; Index: clang-tools-extra/trunk/clangd/Threading.h =================================================================== --- clang-tools-extra/trunk/clangd/Threading.h +++ clang-tools-extra/trunk/clangd/Threading.h @@ -50,18 +50,50 @@ std::size_t FreeSlots; }; -/// A point in time we may wait for, or None to wait forever. +/// A point in time we can wait for. +/// Can be zero (don't wait) or infinity (wait forever). /// (Not time_point::max(), because many std::chrono implementations overflow). -using Deadline = llvm::Optional; -/// Makes a deadline from a timeout in seconds. +class Deadline { +public: + Deadline(std::chrono::steady_clock::time_point Time) + : Type(Finite), Time(Time) {} + static Deadline zero() { return Deadline(Zero); } + static Deadline infinity() { return Deadline(Infinite); } + + std::chrono::steady_clock::time_point time() const { + assert(Type == Finite); + return Time; + } + bool expired() const { + return (Type == Zero) || + (Type == Finite && Time < std::chrono::steady_clock::now()); + } + bool operator==(const Deadline &Other) const { + return (Type == Other.Type) && (Type != Finite || Time == Other.Time); + } + +private: + enum Type { Zero, Infinite, Finite }; + + Deadline(enum Type Type) : Type(Type) {} + enum Type Type; + std::chrono::steady_clock::time_point Time; +}; + +/// Makes a deadline from a timeout in seconds. None means wait forever. Deadline timeoutSeconds(llvm::Optional Seconds); +/// Wait once on CV for the specified duration. +void wait(std::unique_lock &Lock, std::condition_variable &CV, + Deadline D); /// Waits on a condition variable until F() is true or D expires. template LLVM_NODISCARD bool wait(std::unique_lock &Lock, std::condition_variable &CV, Deadline D, Func F) { - if (D) - return CV.wait_until(Lock, *D, F); - CV.wait(Lock, F); + while (!F()) { + if (D.expired()) + return false; + wait(Lock, CV, D); + } return true; } @@ -73,7 +105,7 @@ /// Destructor waits for all pending tasks to finish. ~AsyncTaskRunner(); - void wait() const { (void) wait(llvm::None); } + void wait() const { (void)wait(Deadline::infinity()); } LLVM_NODISCARD bool wait(Deadline D) const; // The name is used for tracing and debugging (e.g. to name a spawned thread). void runAsync(llvm::Twine Name, UniqueFunction Action); Index: clang-tools-extra/trunk/clangd/Threading.cpp =================================================================== --- clang-tools-extra/trunk/clangd/Threading.cpp +++ clang-tools-extra/trunk/clangd/Threading.cpp @@ -76,10 +76,19 @@ Deadline timeoutSeconds(llvm::Optional Seconds) { using namespace std::chrono; if (!Seconds) - return llvm::None; + return Deadline::infinity(); return steady_clock::now() + duration_cast(duration(*Seconds)); } +void wait(std::unique_lock &Lock, std::condition_variable &CV, + Deadline D) { + if (D == Deadline::zero()) + return; + if (D == Deadline::infinity()) + return CV.wait(Lock); + CV.wait_until(Lock, D.time()); +} + } // namespace clangd } // namespace clang Index: clang-tools-extra/trunk/unittests/clangd/TUSchedulerTests.cpp =================================================================== --- clang-tools-extra/trunk/unittests/clangd/TUSchedulerTests.cpp +++ clang-tools-extra/trunk/unittests/clangd/TUSchedulerTests.cpp @@ -42,7 +42,8 @@ TEST_F(TUSchedulerTests, MissingFiles) { TUScheduler S(getDefaultAsyncThreadsCount(), /*StorePreamblesInMemory=*/true, - /*ASTParsedCallback=*/nullptr); + /*ASTParsedCallback=*/nullptr, + /*UpdateDebounce=*/std::chrono::steady_clock::duration::zero()); auto Added = testPath("added.cpp"); Files[Added] = ""; @@ -94,9 +95,11 @@ // To avoid a racy test, don't allow tasks to actualy run on the worker // thread until we've scheduled them all. Notification Ready; - TUScheduler S(getDefaultAsyncThreadsCount(), - /*StorePreamblesInMemory=*/true, - /*ASTParsedCallback=*/nullptr); + TUScheduler S( + getDefaultAsyncThreadsCount(), + /*StorePreamblesInMemory=*/true, + /*ASTParsedCallback=*/nullptr, + /*UpdateDebounce=*/std::chrono::steady_clock::duration::zero()); auto Path = testPath("foo.cpp"); S.update(Path, getInputs(Path, ""), WantDiagnostics::Yes, [&](std::vector) { Ready.wait(); }); @@ -118,6 +121,28 @@ EXPECT_EQ(2, CallbackCount); } +TEST_F(TUSchedulerTests, Debounce) { + std::atomic CallbackCount(0); + { + TUScheduler S(getDefaultAsyncThreadsCount(), + /*StorePreamblesInMemory=*/true, + /*ASTParsedCallback=*/nullptr, + /*UpdateDebounce=*/std::chrono::milliseconds(50)); + auto Path = testPath("foo.cpp"); + S.update(Path, getInputs(Path, "auto (debounced)"), WantDiagnostics::Auto, + [&](std::vector Diags) { + ADD_FAILURE() << "auto should have been debounced and canceled"; + }); + std::this_thread::sleep_for(std::chrono::milliseconds(10)); + S.update(Path, getInputs(Path, "auto (timed out)"), WantDiagnostics::Auto, + [&](std::vector Diags) { ++CallbackCount; }); + std::this_thread::sleep_for(std::chrono::milliseconds(60)); + S.update(Path, getInputs(Path, "auto (shut down)"), WantDiagnostics::Auto, + [&](std::vector Diags) { ++CallbackCount; }); + } + EXPECT_EQ(2, CallbackCount); +} + TEST_F(TUSchedulerTests, ManyUpdates) { const int FilesCount = 3; const int UpdatesPerFile = 10; @@ -131,7 +156,8 @@ { TUScheduler S(getDefaultAsyncThreadsCount(), /*StorePreamblesInMemory=*/true, - /*ASTParsedCallback=*/nullptr); + /*ASTParsedCallback=*/nullptr, + /*UpdateDebounce=*/std::chrono::milliseconds(50)); std::vector Files; for (int I = 0; I < FilesCount; ++I) {