diff --git a/clang-tools-extra/clangd/Preamble.h b/clang-tools-extra/clangd/Preamble.h --- a/clang-tools-extra/clangd/Preamble.h +++ b/clang-tools-extra/clangd/Preamble.h @@ -27,7 +27,9 @@ #include "Diagnostics.h" #include "FS.h" #include "Headers.h" +#include "Path.h" #include "index/CanonicalIncludes.h" +#include "clang/Frontend/CompilerInvocation.h" #include "clang/Frontend/PrecompiledPreamble.h" #include "clang/Tooling/CompilationDatabase.h" @@ -72,17 +74,19 @@ const CanonicalIncludes &)>; /// Build a preamble for the new inputs unless an old one can be reused. -/// If \p OldPreamble can be reused, it is returned unchanged. -/// If \p OldPreamble is null, always builds the preamble. /// If \p PreambleCallback is set, it will be run on top of the AST while -/// building the preamble. Note that if the old preamble was reused, no AST is -/// built and, therefore, the callback will not be executed. +/// building the preamble. std::shared_ptr buildPreamble(PathRef FileName, CompilerInvocation CI, - std::shared_ptr OldPreamble, const ParseInputs &Inputs, bool StoreInMemory, PreambleParsedCallback PreambleCallback); +/// Returns true if \p Preamble is reusable for \p Inputs. Note that it will +/// return true when some missing headers are now available. +/// FIXME: Should return more information about the delta between \p Preamble +/// and \p Inputs, e.g. new headers. +bool isPreambleUsable(const PreambleData &Preamble, const ParseInputs &Inputs, + PathRef FileName, const CompilerInvocation &CI); } // namespace clangd } // namespace clang diff --git a/clang-tools-extra/clangd/Preamble.cpp b/clang-tools-extra/clangd/Preamble.cpp --- a/clang-tools-extra/clangd/Preamble.cpp +++ b/clang-tools-extra/clangd/Preamble.cpp @@ -90,7 +90,6 @@ std::shared_ptr buildPreamble(PathRef FileName, CompilerInvocation CI, - std::shared_ptr OldPreamble, const ParseInputs &Inputs, bool StoreInMemory, PreambleParsedCallback PreambleCallback) { // Note that we don't need to copy the input contents, preamble can live @@ -100,23 +99,6 @@ auto Bounds = ComputePreambleBounds(*CI.getLangOpts(), ContentsBuffer.get(), 0); - if (OldPreamble && - compileCommandsAreEqual(Inputs.CompileCommand, - OldPreamble->CompileCommand) && - OldPreamble->Preamble.CanReuse(CI, ContentsBuffer.get(), Bounds, - Inputs.FS.get())) { - vlog("Reusing preamble version {0} for version {1} of {2}", - OldPreamble->Version, Inputs.Version, FileName); - return OldPreamble; - } - if (OldPreamble) - vlog("Rebuilding invalidated preamble for {0} version {1} " - "(previous was version {2})", - FileName, Inputs.Version, OldPreamble->Version); - else - vlog("Building first preamble for {0} verson {1}", FileName, - Inputs.Version); - trace::Span Tracer("BuildPreamble"); SPAN_ATTACH(Tracer, "File", FileName); StoreDiags PreambleDiagnostics; @@ -168,5 +150,16 @@ } } +bool isPreambleUsable(const PreambleData &Preamble, const ParseInputs &Inputs, + PathRef FileName, const CompilerInvocation &CI) { + auto ContentsBuffer = + llvm::MemoryBuffer::getMemBuffer(Inputs.Contents, FileName); + auto Bounds = + ComputePreambleBounds(*CI.getLangOpts(), ContentsBuffer.get(), 0); + return compileCommandsAreEqual(Inputs.CompileCommand, + Preamble.CompileCommand) && + Preamble.Preamble.CanReuse(CI, ContentsBuffer.get(), Bounds, + Inputs.FS.get()); +} } // namespace clangd } // namespace clang diff --git a/clang-tools-extra/clangd/TUScheduler.cpp b/clang-tools-extra/clangd/TUScheduler.cpp --- a/clang-tools-extra/clangd/TUScheduler.cpp +++ b/clang-tools-extra/clangd/TUScheduler.cpp @@ -5,41 +5,55 @@ // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// -// For each file, managed by TUScheduler, we create a single ASTWorker that -// manages an AST for that file. All operations that modify or read the AST are -// run on a separate dedicated thread asynchronously in FIFO order. +// TUScheduler stores a worker per active file. This worker is called ASTWorker +// and manages updates(modifications to file contents) and reads(actions +// performed on preamble/AST) to the file. // -// We start processing each update immediately after we receive it. If two or -// more updates come subsequently without reads in-between, we attempt to drop -// an older one to not waste time building the ASTs we don't need. +// Each ASTWorker owns a dedicated thread to process updates and reads to the +// relevant file. Any request gets queued in FIFO order to be processed by that +// thread. // -// The processing thread of the ASTWorker is also responsible for building the -// preamble. However, unlike AST, the same preamble can be read concurrently, so -// we run each of async preamble reads on its own thread. +// An update request changes latest inputs to ensure any subsequent read sees +// the version of the file they were requested. In addition to that it might +// result in publishing diagnostics. // -// To limit the concurrent load that clangd produces we maintain a semaphore -// that keeps more than a fixed number of threads from running concurrently. +// An update is considered dead if no read was issued for that version and +// diagnostics weren't requested by client or could be generated for a later +// version of the file. ASTWorker eliminates such requests as they are +// redundant. // -// Rationale for cancelling updates. -// LSP clients can send updates to clangd on each keystroke. Some files take -// significant time to parse (e.g. a few seconds) and clangd can get starved by -// the updates to those files. Therefore we try to process only the last update, -// if possible. -// Our current strategy to do that is the following: -// - For each update we immediately schedule rebuild of the AST. -// - Rebuild of the AST checks if it was cancelled before doing any actual work. -// If it was, it does not do an actual rebuild, only reports llvm::None to the -// callback -// - When adding an update, we cancel the last update in the queue if it didn't -// have any reads. -// There is probably a optimal ways to do that. One approach we might take is -// the following: -// - For each update we remember the pending inputs, but delay rebuild of the -// AST for some timeout. -// - If subsequent updates come before rebuild was started, we replace the -// pending inputs and reset the timer. -// - If any reads of the AST are scheduled, we start building the AST -// immediately. +// ASTWorker processes the file in two parts, a preamble and a mainfile +// section. A preamble can be reused between multiple versions of the file if it +// isn't invalidated by a modification to a header, compile commands or +// modification to relevant part of the current file. Such a preamble is called +// usable. +// In the presence of stale(non-usable) preambles, ASTWorker won't publish +// diagnostics for update requests. Read requests will be served with ASTs build +// with stale preambles, unless the read is picky and requires a usable +// preamble. In such cases it will block until new preamble is built. +// +// ASTWorker owns a PreambleThread for building preambles. If the preamble gets +// invalidated by an update request, a new build will be requested on +// PreambleThread. PreambleThread serves those requests by building preambles on +// a dedicated thread. Since PreambleThread only receives requests for newer +// versions of the file, in case of multiple requests it will only build the +// last one and skip requests in between. Unless client force requested +// diagnostics(WantDiagnostics::Yes). +// +// Whenever PreambleThread finishes a build, ASTWorker will enqueue a task to +// build a new AST using that preamble, called golden AST to publish +// diagnostics. This task will be executed before any other task waiting in +// ASTWorker queue, this is to ensure progress of diagnostics even when +// ASTWorker queue is full. +// These golden ASTs also ensures diagnostics are always for newer versions of +// the file. As diagnostics are only published for update requests after a +// golden AST, and until the preamble is invalidated. Diagnostics won't be +// published for any update request arriving after invalidation until a new +// golden AST is released. +// +// 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 "Cancellation.h" @@ -56,6 +70,8 @@ #include "index/CanonicalIncludes.h" #include "clang/Frontend/CompilerInvocation.h" #include "clang/Tooling/CompilationDatabase.h" +#include "llvm/ADT/FunctionExtras.h" +#include "llvm/ADT/None.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/ScopeExit.h" @@ -64,14 +80,20 @@ #include "llvm/ADT/StringRef.h" #include "llvm/Support/Errc.h" #include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/FormatVariadic.h" #include "llvm/Support/Path.h" #include "llvm/Support/Threading.h" #include +#include +#include #include #include #include #include #include +#include +#include +#include namespace clang { namespace clangd { @@ -190,44 +212,37 @@ ParsingCallbacks &Callbacks; }; -/// Responsible for building and providing access to the preamble of a TU. -/// Whenever the thread is idle and the preamble is outdated, it starts to build -/// a fresh preamble from the latest inputs. If RunSync is true, preambles are -/// built synchronously in update() instead. +/// Responsible for building preambles. Whenever the thread is idle and the +/// preamble is outdated, it starts to build a fresh preamble from the latest +/// inputs. If RunSync is true, preambles are built synchronously in update() +/// instead. class PreambleThread { public: PreambleThread(llvm::StringRef FileName, ParsingCallbacks &Callbacks, bool StorePreambleInMemory, bool RunSync, - SynchronizedTUStatus &Status) + SynchronizedTUStatus &Status, ASTWorker &AW) : FileName(FileName), Callbacks(Callbacks), - StoreInMemory(StorePreambleInMemory), RunSync(RunSync), Status(Status) { - } - - size_t getUsedBytes() const { - auto Preamble = latest(); - return Preamble ? Preamble->Preamble.getSize() : 0; - } + StoreInMemory(StorePreambleInMemory), RunSync(RunSync), Status(Status), + AW(AW) {} /// It isn't guaranteed that each requested version will be built. If there /// are multiple update requests while building a preamble, only the last one /// will be built. - void update(CompilerInvocation *CI, ParseInputs PI) { - // If compiler invocation was broken, just fail out early. - if (!CI) { - // Make sure anyone waiting for the preamble gets notified it could not be - // built. - BuiltFirst.notify(); - return; - } + void update(const CompilerInvocation &CI, ParseInputs PI, + std::vector CIDiags, WantDiagnostics WantDiags) { // Make possibly expensive copy while not holding the lock. - Request Req = {std::make_unique(*CI), std::move(PI)}; + Request Req = {std::make_unique(CI), std::move(PI), + std::move(CIDiags), std::move(WantDiags), + Context::current().clone()}; if (RunSync) { build(std::move(Req)); return; } { std::lock_guard Lock(Mutex); - assert(!Done && "Build request to PreambleWorker after stop"); + // If shutdown is issued, don't bother building. + if (Done) + return; NextReq = std::move(Req); } // Let the worker thread know there's a request, notify_one is safe as there @@ -235,19 +250,8 @@ ReqCV.notify_all(); } - /// Blocks until at least a single request has been processed. Note that it - /// will unblock even after an unsuccessful build. - void waitForFirst() const { BuiltFirst.wait(); } - - /// Returns the latest built preamble, might be null if no preamble has been - /// built or latest attempt resulted in a failure. - std::shared_ptr latest() const { - std::lock_guard Lock(Mutex); - return LatestBuild; - } - void run() { - dlog("Starting preamble worker for {0}", FileName); + dlog("PreambleThread: Starting worker for {0}", FileName); while (true) { { std::unique_lock Lock(Mutex); @@ -259,6 +263,8 @@ CurrentReq = std::move(*NextReq); NextReq.reset(); } + + WithContext Guard(std::move(CurrentReq->Ctx)); // Build the preamble and let the waiters know about it. build(std::move(*CurrentReq)); bool IsEmpty = false; @@ -275,20 +281,18 @@ Status.PreambleActivity = PreambleAction::Idle; }); } - BuiltFirst.notify(); ReqCV.notify_all(); } - // We are no longer going to build any preambles, let the waiters know that. - BuiltFirst.notify(); - dlog("Preamble worker for {0} finished", FileName); + dlog("PreambleThread: Finished for {0}", FileName); } /// Signals the run loop to exit. void stop() { - dlog("Stopping preamble worker for {0}", FileName); + dlog("PreambleThread: Stopping for {0}", FileName); { std::lock_guard Lock(Mutex); Done = true; + NextReq.reset(); } // Let the worker thread know that it should stop. ReqCV.notify_all(); @@ -305,6 +309,9 @@ struct Request { std::unique_ptr CI; ParseInputs Inputs; + std::vector CIDiags; + WantDiagnostics WantDiags; + Context Ctx; }; bool isDone() { @@ -312,35 +319,9 @@ return Done; } - /// Builds a preamble for Req and caches it. Might re-use the latest built - /// preamble if it is valid for Req. Also signals waiters about the build. - /// FIXME: We shouldn't cache failed preambles, if we've got a successful - /// build before. - void build(Request Req) { - assert(Req.CI && "Got preamble request with null compiler invocation"); - const ParseInputs &Inputs = Req.Inputs; - std::shared_ptr OldPreamble = - Inputs.ForceRebuild ? nullptr : latest(); - - Status.update([&](TUStatus &Status) { - Status.PreambleActivity = PreambleAction::Building; - }); - - auto Preamble = clang::clangd::buildPreamble( - FileName, std::move(*Req.CI), OldPreamble, Inputs, StoreInMemory, - [this, Version(Inputs.Version)]( - ASTContext &Ctx, std::shared_ptr PP, - const CanonicalIncludes &CanonIncludes) { - Callbacks.onPreambleAST(FileName, Version, Ctx, std::move(PP), - CanonIncludes); - }); - { - std::lock_guard Lock(Mutex); - // LatestBuild might be the last reference to old preamble, do not trigger - // destructor while holding the lock. - std::swap(LatestBuild, Preamble); - } - } + /// Builds a preamble for \p Req will reuse LatestBuild if possible. Notifies + /// ASTWorker. + void build(Request Req); mutable std::mutex Mutex; bool Done = false; /* GUARDED_BY(Mutex) */ @@ -351,13 +332,13 @@ mutable std::condition_variable ReqCV; /* GUARDED_BY(Mutex) */ std::shared_ptr LatestBuild; /* GUARDED_BY(Mutex) */ - Notification BuiltFirst; const Path FileName; ParsingCallbacks &Callbacks; const bool StoreInMemory; const bool RunSync; SynchronizedTUStatus &Status; + ASTWorker &AW; }; class ASTWorkerHandle; @@ -417,7 +398,24 @@ std::size_t getUsedBytes() const; bool isASTCached() const; + /// Used to inform ASTWorker about a new preamble build by PreambleThread. + void preambleReady(std::unique_ptr CI, ParseInputs PI, + std::shared_ptr Preamble, + std::vector CIDiags, WantDiagnostics WantDiags); + private: + /// Publishes diagnostics for \p Inputs. It will build an AST or reuse the + /// cached one if applicable. Assumes LatestPreamble is usable by \p Inputs. + void publishDiagnostics(std::unique_ptr Invocation, + ParseInputs Inputs, std::vector CIDiags); + + /// Returns the latest built preamble, might be null if no preamble has been + /// built or latest attempt resulted in a failure. + std::shared_ptr latestPreamble() const { + std::lock_guard Lock(Mutex); + return LatestPreamble; + } + // Must be called exactly once on processing thread. Will return after // stop() is called on a separate thread and all pending requests are // processed. @@ -461,6 +459,9 @@ const GlobalCompilationDatabase &CDB; /// Callback invoked when preamble or main file AST is built. ParsingCallbacks &Callbacks; + /// Latest build preamble for current TU. + std::shared_ptr LatestPreamble; + Notification BuiltFirstPreamble; Semaphore &Barrier; /// Whether the 'onMainAST' callback ran for the current FileInputs. @@ -477,6 +478,7 @@ /// Set to true to signal run() to finish processing. bool Done; /* GUARDED_BY(Mutex) */ std::deque Requests; /* GUARDED_BY(Mutex) */ + std::queue ReceivedPreambles; /* GUARDED_BY(Mutex) */ llvm::Optional CurrentRequest; /* GUARDED_BY(Mutex) */ mutable std::condition_variable RequestsCV; /// Guards the callback that publishes results of AST-related computations @@ -536,6 +538,45 @@ std::shared_ptr Worker; }; +void PreambleThread::build(Request Req) { + assert(Req.CI && "Got preamble request with null compiler invocation"); + const ParseInputs &Inputs = Req.Inputs; + + Status.update([&](TUStatus &Status) { + Status.PreambleActivity = PreambleAction::Building; + }); + if (LatestBuild) { + if (!Inputs.ForceRebuild && + isPreambleUsable(*LatestBuild, Inputs, FileName, *Req.CI)) { + vlog( + "PreambleThread: Reusing preamble version {0} for version {1} of {2}", + LatestBuild->Version, Inputs.Version, FileName); + // We still notify the ASTWorker to make sure diagnostics are updated to + // the latest version of the file without requiring user update. + AW.preambleReady(std::move(Req.CI), std::move(Req.Inputs), LatestBuild, + std::move(Req.CIDiags), std::move(Req.WantDiags)); + return; + } + vlog("PreambleThread: Rebuilding invalidated preamble for {0} version {1} " + "(previous was version {2})", + FileName, Inputs.Version, LatestBuild->Version); + } else { + vlog("PreambleThread: Building first preamble for {0} version {1}", + FileName, Inputs.Version); + } + + LatestBuild = clang::clangd::buildPreamble( + FileName, *Req.CI, Inputs, StoreInMemory, + [this, Version(Inputs.Version)](ASTContext &Ctx, + std::shared_ptr PP, + const CanonicalIncludes &CanonIncludes) { + Callbacks.onPreambleAST(FileName, Version, Ctx, std::move(PP), + CanonIncludes); + }); + AW.preambleReady(std::move(Req.CI), std::move(Req.Inputs), LatestBuild, + std::move(Req.CIDiags), std::move(Req.WantDiags)); +} + ASTWorkerHandle ASTWorker::create(PathRef FileName, const GlobalCompilationDatabase &CDB, TUScheduler::ASTCache &IdleASTs, AsyncTaskRunner *Tasks, @@ -561,7 +602,7 @@ : IdleASTs(LRUCache), RunSync(RunSync), UpdateDebounce(UpdateDebounce), FileName(FileName), CDB(CDB), Callbacks(Callbacks), Barrier(Barrier), Done(false), Status(FileName, Callbacks), - PW(FileName, Callbacks, StorePreamblesInMemory, RunSync, Status) { + PW(FileName, Callbacks, StorePreamblesInMemory, RunSync, Status, *this) { auto Inputs = std::make_shared(); // Set a fallback command because compile command can be accessed before // `Inputs` is initialized. Other fields are only used after initialization @@ -581,17 +622,140 @@ #endif } +void ASTWorker::preambleReady(std::unique_ptr CI, + ParseInputs PI, + std::shared_ptr Preamble, + std::vector CIDiags, + WantDiagnostics WantDiags) { + std::string TaskName = llvm::formatv("Preamble Update ({0})", PI.Version); + // 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. + { + std::lock_guard Lock(Mutex); + // LatestPreamble might be the last reference to old preamble, do not + // trigger destructor while holding the lock. + std::swap(LatestPreamble, Preamble); + } + // Give up our ownership to old preamble before starting expensive + Preamble.reset(); + BuiltFirstPreamble.notify(); + // Cached AST is no longer valid. + IdleASTs.take(this); + // We only need to build the AST if diagnostics were requested. + if (WantDiags == WantDiagnostics::No) + return; + // Report diagnostics with the new preamble to ensure progress. Otherwise + // diagnostics might get stale indefinitely if user keeps invalidating the + // preamble. + publishDiagnostics(std::move(CI), std::move(PI), std::move(CIDiags)); + }; + if (RunSync) { + Task(); + return; + } + { + std::lock_guard Lock(Mutex); + ReceivedPreambles.push({std::move(Task), std::move(TaskName), + steady_clock::now(), Context::current().clone(), + llvm::None, TUScheduler::NoInvalidation, nullptr}); + } + RequestsCV.notify_all(); +} + +void ASTWorker::publishDiagnostics( + std::unique_ptr Invocation, ParseInputs Inputs, + std::vector CIDiags) { + assert(Invocation); + assert(LatestPreamble); + assert(isPreambleUsable(*LatestPreamble, Inputs, FileName, *Invocation)); + + auto RunPublish = [&](llvm::function_ref Publish) { + // Ensure we only publish results from the worker if the file was not + // removed, making sure there are not race conditions. + std::lock_guard Lock(PublishMu); + if (CanPublishResults) + Publish(); + }; + + { + std::lock_guard Lock(PublishMu); + // No need to rebuild the AST if we won't send the diagnostics. + if (!CanPublishResults) + return; + } + + // Used to check whether we can update AST cache and callback status. + bool InputsAreTheSame = + std::tie(FileInputs->CompileCommand, FileInputs->Contents) == + std::tie(Inputs.CompileCommand, Inputs.Contents); + + std::string TaskName = llvm::formatv("Build AST ({0})", Inputs.Version); + Status.update([&](TUStatus &Status) { + Status.ASTActivity.K = ASTAction::Building; + Status.ASTActivity.Name = std::move(TaskName); + }); + llvm::Optional RebuildDuration; + // Get the AST for diagnostics. + llvm::Optional> AST = IdleASTs.take(this); + if (!AST) { + auto RebuildStartTime = DebouncePolicy::clock::now(); + llvm::Optional NewAST = clang::clangd::buildAST( + FileName, std::move(Invocation), CIDiags, Inputs, LatestPreamble); + RebuildDuration = DebouncePolicy::clock::now() - RebuildStartTime; + Status.update([&](TUStatus &Status) { + Status.Details.ReuseAST = false; + Status.Details.BuildFailed = !NewAST.hasValue(); + }); + AST = NewAST ? std::make_unique(std::move(*NewAST)) : nullptr; + } else { + assert(InputsAreTheSame && "forgot to invalidate cached ast?"); + // We are reusing the AST. + Status.update([](TUStatus &Status) { + Status.Details.ReuseAST = true; + Status.Details.BuildFailed = false; + }); + } + // Note *AST can still be null if buildAST fails. + if (*AST) { + { + // 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 Lock(Mutex, std::try_to_lock); + if (RebuildDuration && Lock.owns_lock()) { + // Do not let RebuildTimes grow beyond its small-size (i.e. + // capacity). + if (RebuildTimes.size() == RebuildTimes.capacity()) + RebuildTimes.erase(RebuildTimes.begin()); + RebuildTimes.push_back(*RebuildDuration); + } + } + trace::Span Span("Running main AST callback"); + Callbacks.onMainAST(FileName, **AST, RunPublish); + // Update RanASTCallback only if we are publishing for the same inputs. + if (InputsAreTheSame) + RanASTCallback = true; + } else { + // Failed to build the AST, at least report diagnostics from the + // command line if there were any. + // FIXME: we might have got more errors while trying to build the + // AST, surface them too. + Callbacks.onFailedAST(FileName, Inputs.Version, CIDiags, RunPublish); + } + // Stash the AST in the cache for further use if it is compatible with current + // ASTWorker inputs. + if (InputsAreTheSame) + IdleASTs.put(this, std::move(*AST)); +} + void ASTWorker::update(ParseInputs Inputs, WantDiagnostics WantDiags) { std::string TaskName = llvm::formatv("Update ({0})", Inputs.Version); auto Task = [=]() mutable { - auto RunPublish = [&](llvm::function_ref Publish) { - // Ensure we only publish results from the worker if the file was not - // removed, making sure there are not race conditions. - std::lock_guard Lock(PublishMu); - if (CanPublishResults) - Publish(); - }; - // Get the actual command as `Inputs` does not have a command. // FIXME: some build systems like Bazel will take time to preparing // environment to build the file, it would be nice if we could emit a @@ -602,35 +766,33 @@ else // FIXME: consider using old command if it's not a fallback one. Inputs.CompileCommand = CDB.getFallbackCommand(FileName); - auto PrevInputs = getCurrentFileInputs(); // Will be used to check if we can avoid rebuilding the AST. bool InputsAreTheSame = - std::tie(PrevInputs->CompileCommand, PrevInputs->Contents) == + std::tie(FileInputs->CompileCommand, FileInputs->Contents) == std::tie(Inputs.CompileCommand, Inputs.Contents); - bool RanCallbackForPrevInputs = RanASTCallback; + if (!InputsAreTheSame) { + // Old AST is invalidated. + IdleASTs.take(this); + RanCallbackForPrevInputs = false; + } + + // Update current inputs so that subsequent reads can see them. { std::lock_guard Lock(Mutex); FileInputs = std::make_shared(Inputs); } RanASTCallback = false; + log("ASTWorker building file {0} version {1} with command {2}\n[{3}]\n{4}", FileName, Inputs.Version, Inputs.CompileCommand.Heuristic, Inputs.CompileCommand.Directory, llvm::join(Inputs.CompileCommand.CommandLine, " ")); - // Rebuild the preamble and the AST. + StoreDiags CompilerInvocationDiagConsumer; std::vector CC1Args; std::unique_ptr Invocation = buildCompilerInvocation( Inputs, CompilerInvocationDiagConsumer, &CC1Args); - // This is true for now, as we always block until new preamble is build. - // Once we start to block preambles out-of-order we need to make sure - // OldPreamble refers to the preamble that was used to build last AST. - auto OldPreamble = PW.latest(); - PW.update(Invocation.get(), Inputs); - // FIXME make use of the stale preambles instead. - PW.blockUntilIdle(Deadline::infinity()); - auto NewPreamble = PW.latest(); // Log cc1 args even (especially!) if creating invocation failed. if (!CC1Args.empty()) vlog("Driver produced command: cc1 {0}", llvm::join(CC1Args, " ")); @@ -642,107 +804,74 @@ IdleASTs.take(this); // Report the diagnostics we collected when parsing the command line. Callbacks.onFailedAST(FileName, Inputs.Version, - std::move(CompilerInvocationDiags), RunPublish); + std::move(CompilerInvocationDiags), + [&](llvm::function_ref Publish) { + // Ensure we only publish results from the worker + // if the file was not removed, making sure there + // are not race conditions. + std::lock_guard Lock(PublishMu); + if (CanPublishResults) + Publish(); + }); + // Make sure anyone waiting for the preamble gets notified it could not be + // built. + BuiltFirstPreamble.notify(); return; } - bool CanReuseAST = InputsAreTheSame && (OldPreamble == 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(); - Status.update([&](TUStatus &Status) { - Status.ASTActivity.K = ASTAction::Building; - Status.ASTActivity.Name = std::move(TaskName); - }); - if (!CanReuseAST) { - IdleASTs.take(this); // Remove the old AST if it's still in cache. - } else { - // We don't need to rebuild the AST, check if we need to run the callback. - if (RanCallbackForPrevInputs) { - RanASTCallback = true; - // Take a shortcut and don't report the diagnostics, since they should - // not changed. 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); - - Status.update([](TUStatus &Status) { - Status.Details.ReuseAST = true; - Status.Details.BuildFailed = false; - }); - return; - } - } - - // We only need to build the AST if diagnostics were requested. - if (WantDiags == WantDiagnostics::No) + // Even when inputs are the same, preamble might've changed due to edits on + // headers. Check whether preamble is stale. + bool PreambleFresh = + !Inputs.ForceRebuild && LatestPreamble && + isPreambleUsable(*LatestPreamble, Inputs, FileName, *Invocation); + // Do not build AST with stale preambles, as diagnostics might contain false + // positives and symbol information might be misleading. + if (!PreambleFresh) { + // Since preamble has changed, cached ast is no longer valid. + IdleASTs.take(this); + PW.update(*Invocation, Inputs, std::move(CompilerInvocationDiags), + WantDiags); + // FIXME: We block here to ensure any subsequent reads gets a fresh + // preamble. Instead of blocking here, we should build patched-up ASTs on + // reads or block only for picky reads. + PW.blockUntilIdle(Deadline::infinity()); return; - - { - std::lock_guard Lock(PublishMu); - // No need to rebuild the AST if we won't send the diagnostics. However, - // note that we don't prevent preamble rebuilds. - if (!CanPublishResults) - return; } + vlog("ASTWorker: Reusing preamble version {0} for version {1} of {2}", + LatestPreamble->Version, Inputs.Version, FileName); + + // Take a shortcut and don't report the diagnostics, since they should be + // the same. All the clients should handle the lack of OnUpdated() call + // anyway to handle empty result from buildAST. + // FIXME: the AST could actually change if non-preamble includes changed, + // but we choose to ignore it. + // FIXME: should we refresh the cache in IdleASTs for the current file at + // this point? + if (RanCallbackForPrevInputs) { + assert(InputsAreTheSame); + RanASTCallback = true; + log("ASTWorker: Skipping rebuild of the AST for {0}, inputs are the " + "same.", + FileName); - // Get the AST for diagnostics. - llvm::Optional> AST = IdleASTs.take(this); - auto RebuildStartTime = DebouncePolicy::clock::now(); - if (!AST) { - llvm::Optional NewAST = - buildAST(FileName, std::move(Invocation), CompilerInvocationDiags, - Inputs, NewPreamble); - // buildAST fails. - Status.update([&](TUStatus &Status) { - Status.Details.ReuseAST = false; - Status.Details.BuildFailed = !NewAST.hasValue(); - }); - AST = NewAST ? std::make_unique(std::move(*NewAST)) : nullptr; - } else { - // We are reusing the AST. Status.update([](TUStatus &Status) { Status.Details.ReuseAST = true; Status.Details.BuildFailed = false; }); + return; } - // 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. - // Note *AST can still be null if buildAST fails. - if (*AST) { - { - // 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. - auto RebuildDuration = DebouncePolicy::clock::now() - RebuildStartTime; - std::unique_lock 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()); - RebuildTimes.push_back(RebuildDuration); - } - } - trace::Span Span("Running main AST callback"); + // We only need to build the AST if diagnostics were requested. + if (WantDiags == WantDiagnostics::No) + return; - Callbacks.onMainAST(FileName, **AST, RunPublish); - RanASTCallback = true; - } else { - // Failed to build the AST, at least report diagnostics from the command - // line if there were any. - // FIXME: we might have got more errors while trying to build the AST, - // surface them too. - Callbacks.onFailedAST(FileName, Inputs.Version, CompilerInvocationDiags, - RunPublish); - } - // Stash the AST in the cache for further use. - IdleASTs.put(this, std::move(*AST)); + // Either there's an update to mainfile or callbacks were not invoked last + // time we built the AST. So invoke the callbacks while building the ast if + // needed. Note that this update might've been cancelled/invalidated by a + // subsequent update. Still report the diagnostics. It seems more useful + // than making the clients wait indefinitely if they spam us with updates. + publishDiagnostics(std::move(Invocation), std::move(Inputs), + std::move(CompilerInvocationDiags)); }; startTask(TaskName, std::move(Task), WantDiags, TUScheduler::NoInvalidation); } @@ -761,14 +890,14 @@ std::unique_ptr Invocation = buildCompilerInvocation( *CurrentInputs, CompilerInvocationDiagConsumer); // Try rebuilding the AST. - vlog("ASTWorker rebuilding evicted AST to run {0}: {1} version {2}", Name, - FileName, CurrentInputs->Version); + vlog("ASTWorker: Rebuilding evicted AST to run {0}: {1} version {2}", + Name, FileName, CurrentInputs->Version); llvm::Optional NewAST = Invocation - ? buildAST(FileName, - std::make_unique(*Invocation), - CompilerInvocationDiagConsumer.take(), *CurrentInputs, - getPossiblyStalePreamble()) + ? clang::clangd::buildAST( + FileName, std::make_unique(*Invocation), + CompilerInvocationDiagConsumer.take(), *CurrentInputs, + getPossiblyStalePreamble()) : None; AST = NewAST ? std::make_unique(std::move(*NewAST)) : nullptr; } @@ -779,7 +908,7 @@ if (!*AST) return Action(llvm::make_error( "invalid AST", llvm::errc::invalid_argument)); - vlog("ASTWorker running {0} on version {2} of {1}", Name, FileName, + vlog("ASTWorker: Running {0} on version {2} of {1}", Name, FileName, CurrentInputs->Version); Action(InputsAndAST{*CurrentInputs, **AST}); }; @@ -788,7 +917,8 @@ std::shared_ptr ASTWorker::getPossiblyStalePreamble() const { - return PW.latest(); + std::lock_guard Lock(Mutex); + return LatestPreamble; } void ASTWorker::getCurrentPreamble( @@ -821,7 +951,7 @@ RequestsCV.notify_all(); } -void ASTWorker::waitForFirstPreamble() const { PW.waitForFirst(); } +void ASTWorker::waitForFirstPreamble() const { BuiltFirstPreamble.wait(); } std::shared_ptr ASTWorker::getCurrentFileInputs() const { std::unique_lock Lock(Mutex); @@ -855,6 +985,9 @@ assert(!Done && "stop() called twice"); Done = true; } + // We are no longer going to build any preambles, let the waiters know that. + BuiltFirstPreamble.notify(); + PW.stop(); Status.stop(); RequestsCV.notify_all(); } @@ -898,13 +1031,14 @@ } void ASTWorker::run() { - auto _ = llvm::make_scope_exit([this] { PW.stop(); }); while (true) { { std::unique_lock Lock(Mutex); assert(!CurrentRequest && "A task is already running, multiple workers?"); for (auto Wait = scheduleLocked(); !Wait.expired(); Wait = scheduleLocked()) { + assert(ReceivedPreambles.empty() && + "Preamble updates should be scheduled immediately"); if (Done) { if (Requests.empty()) return; @@ -933,8 +1067,15 @@ wait(Lock, RequestsCV, Wait); } - CurrentRequest = std::move(Requests.front()); - Requests.pop_front(); + // Any request in ReceivedPreambles is at least as old as the + // Requests.front(), so prefer them first to preserve LSP order. + if (!ReceivedPreambles.empty()) { + CurrentRequest = std::move(ReceivedPreambles.front()); + ReceivedPreambles.pop(); + } else { + CurrentRequest = std::move(Requests.front()); + Requests.pop_front(); + } } // unlock Mutex // It is safe to perform reads to CurrentRequest without holding the lock as @@ -961,7 +1102,7 @@ { std::lock_guard Lock(Mutex); CurrentRequest.reset(); - IsEmpty = Requests.empty(); + IsEmpty = Requests.empty() && ReceivedPreambles.empty(); } if (IsEmpty) { Status.update([&](TUStatus &Status) { @@ -974,6 +1115,9 @@ } Deadline ASTWorker::scheduleLocked() { + // Process new preambles immediately. + if (!ReceivedPreambles.empty()) + return Deadline::zero(); if (Requests.empty()) return Deadline::infinity(); // Wait for new requests. // Handle cancelled requests first so the rest of the scheduler doesn't. @@ -997,7 +1141,7 @@ } while (shouldSkipHeadLocked()) { - vlog("ASTWorker skipping {0} for {1}", Requests.front().Name, FileName); + vlog("ASTWorker: Skipping {0} for {1}", Requests.front().Name, FileName); Requests.pop_front(); } assert(!Requests.empty() && "skipped the whole queue"); @@ -1044,8 +1188,9 @@ bool ASTWorker::blockUntilIdle(Deadline Timeout) const { std::unique_lock Lock(Mutex); - return wait(Lock, RequestsCV, Timeout, - [&] { return Requests.empty() && !CurrentRequest; }); + return wait(Lock, RequestsCV, Timeout, [&] { + return ReceivedPreambles.empty() && Requests.empty() && !CurrentRequest; + }); } // Render a TUAction to a user-facing string representation. @@ -1220,6 +1365,9 @@ // Future is populated if the task needs a specific preamble. std::future> ConsistentPreamble; + // FIXME: Currently this only holds because ASTWorker blocks after issuing a + // preamble build. Get rid of consistent reads or make them build on the + // calling thread instead. if (Consistency == Consistent) { std::promise> Promise; ConsistentPreamble = Promise.get_future(); diff --git a/clang-tools-extra/clangd/unittests/FileIndexTests.cpp b/clang-tools-extra/clangd/unittests/FileIndexTests.cpp --- a/clang-tools-extra/clangd/unittests/FileIndexTests.cpp +++ b/clang-tools-extra/clangd/unittests/FileIndexTests.cpp @@ -286,7 +286,7 @@ FileIndex Index; bool IndexUpdated = false; - buildPreamble(FooCpp, *CI, /*OldPreamble=*/nullptr, PI, + buildPreamble(FooCpp, *CI, PI, /*StoreInMemory=*/true, [&](ASTContext &Ctx, std::shared_ptr PP, const CanonicalIncludes &CanonIncludes) { @@ -424,7 +424,7 @@ } TEST(FileIndexTest, MergeMainFileSymbols) { - const char* CommonHeader = "void foo();"; + const char *CommonHeader = "void foo();"; TestTU Header = TestTU::withCode(CommonHeader); TestTU Cpp = TestTU::withCode("void foo() {}"); Cpp.Filename = "foo.cpp"; diff --git a/clang-tools-extra/clangd/unittests/TUSchedulerTests.cpp b/clang-tools-extra/clangd/unittests/TUSchedulerTests.cpp --- a/clang-tools-extra/clangd/unittests/TUSchedulerTests.cpp +++ b/clang-tools-extra/clangd/unittests/TUSchedulerTests.cpp @@ -283,6 +283,7 @@ S.runWithPreamble("StaleRead", Path, TUScheduler::Stale, [&](Expected Pre) { ASSERT_TRUE(bool(Pre)); + ASSERT_TRUE(Pre->Preamble); EXPECT_EQ(Pre->Preamble->Version, "A"); EXPECT_THAT(includes(Pre->Preamble), ElementsAre("")); @@ -292,11 +293,13 @@ S.runWithPreamble("ConsistentRead", Path, TUScheduler::Consistent, [&](Expected Pre) { ASSERT_TRUE(bool(Pre)); + ASSERT_TRUE(Pre->Preamble); EXPECT_EQ(Pre->Preamble->Version, "B"); EXPECT_THAT(includes(Pre->Preamble), ElementsAre("")); ++CallbackCount; }); + S.blockUntilIdle(timeoutSeconds(10)); } EXPECT_EQ(2, CallbackCount); } @@ -853,15 +856,19 @@ TUState(PreambleAction::Idle, ASTAction::RunningAction), // We build the preamble TUState(PreambleAction::Building, ASTAction::RunningAction), - // Preamble worker goes idle + // We built the preamble, and issued ast built on ASTWorker + // thread. Preambleworker goes idle afterwards. TUState(PreambleAction::Idle, ASTAction::RunningAction), - // We start building the ast + // Start task for building the ast, as a result of building + // preamble, on astworker thread. + TUState(PreambleAction::Idle, ASTAction::RunningAction), + // AST build starts. TUState(PreambleAction::Idle, ASTAction::Building), - // Built finished succesffully + // AST built finished successfully TUState(PreambleAction::Idle, ASTAction::Building), - // Rnning go to def + // Running go to def TUState(PreambleAction::Idle, ASTAction::RunningAction), - // both workers go idle + // ASTWorker goes idle. TUState(PreambleAction::Idle, ASTAction::Idle))); } diff --git a/clang-tools-extra/clangd/unittests/TestTU.cpp b/clang-tools-extra/clangd/unittests/TestTU.cpp --- a/clang-tools-extra/clangd/unittests/TestTU.cpp +++ b/clang-tools-extra/clangd/unittests/TestTU.cpp @@ -66,8 +66,7 @@ auto CI = buildCompilerInvocation(Inputs, Diags); assert(CI && "Failed to build compilation invocation."); auto Preamble = - buildPreamble(FullFilename, *CI, - /*OldPreamble=*/nullptr, Inputs, + buildPreamble(FullFilename, *CI, Inputs, /*StoreInMemory=*/true, /*PreambleCallback=*/nullptr); auto AST = buildAST(FullFilename, std::move(CI), Diags.take(), Inputs, Preamble);