CbC/CbC_llvm: clang-tools-extra/clangd/TUScheduler.cpp comparison

comparison clang-tools-extra/clangd/TUScheduler.cpp @ 221:79ff65ed7e25

LLVM12 Original

author	Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date	Tue, 15 Jun 2021 19:15:29 +0900
parents	0572611fdcc8
children	5f17cb93ff66

comparison

equal deleted inserted replaced

-:42394fc6a535
+:79ff65ed7e25
 #include "Preamble.h"
 #include "index/CanonicalIncludes.h"
 #include "support/Cancellation.h"
 #include "support/Context.h"
 #include "support/Logger.h"
+#include "support/MemoryTree.h"
 #include "support/Path.h"
 #include "support/Threading.h"
 #include "support/Trace.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Allocator.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 <algorithm>
+#include <atomic>
 #include <chrono>
+#include <condition_variable>
 #include <functional>
 #include <memory>
 #include <mutex>
 #include <queue>
 #include <string>
 /// Items sorted in LRU order, i.e. first item is the most recently accessed
 /// one.
 std::vector<KVPair> LRU; /* GUARDED_BY(Mut) */
 };
+/// A map from header files to an opened "proxy" file that includes them.
+/// If you open the header, the compile command from the proxy file is used.
+///
+/// This inclusion information could also naturally live in the index, but there
+/// are advantages to using open files instead:
+///  - it's easier to achieve a *stable* choice of proxy, which is important
+///    to avoid invalidating the preamble
+///  - context-sensitive flags for libraries with multiple configurations
+///    (e.g. C++ stdlib sensitivity to -std version)
+///  - predictable behavior, e.g. guarantees that go-to-def landing on a header
+///    will have a suitable command available
+///  - fewer scaling problems to solve (project include graphs are big!)
+///
+/// Implementation details:
+/// - We only record this for mainfiles where the command was trustworthy
+///   (i.e. not inferred). This avoids a bad inference "infecting" other files.
+/// - Once we've picked a proxy file for a header, we stick with it until the
+///   proxy file is invalidated *and* a new candidate proxy file is built.
+///   Switching proxies is expensive, as the compile flags will (probably)
+///   change and therefore we'll end up rebuilding the header's preamble.
+/// - We don't capture the actual compile command, but just the filename we
+///   should query to get it. This avoids getting out of sync with the CDB.
+///
+/// All methods are threadsafe. In practice, update() comes from preamble
+/// threads, remove()s mostly from the main thread, and get() from ASTWorker.
+/// Writes are rare and reads are cheap, so we don't expect much contention.
+class TUScheduler::HeaderIncluderCache {
+// We should be be a little careful how we store the include graph of open
+// files, as each can have a large number of transitive headers.
+// This representation is O(unique transitive source files).
+llvm::BumpPtrAllocator Arena;
+struct Association {
+llvm::StringRef MainFile;
+// Circular-linked-list of associations with the same mainFile.
+// Null indicates that the mainfile was removed.
+Association *Next;
+};
+llvm::StringMap<Association, llvm::BumpPtrAllocator &> HeaderToMain;
+llvm::StringMap<Association *, llvm::BumpPtrAllocator &> MainToFirst;
+std::atomic<size_t> UsedBytes; // Updated after writes.
+mutable std::mutex Mu;
+void invalidate(Association *First) {
+Association *Current = First;
+do {
+Association *Next = Current->Next;
+Current->Next = nullptr;
+Current = Next;
+} while (Current != First);
+}
+// Create the circular list and return the head of it.
+Association *associate(llvm::StringRef MainFile,
+llvm::ArrayRef<std::string> Headers) {
+Association *First = nullptr, *Prev = nullptr;
+for (const std::string &Header : Headers) {
+auto &Assoc = HeaderToMain[Header];
+if (Assoc.Next)
+continue; // Already has a valid association.
+Assoc.MainFile = MainFile;
+Assoc.Next = Prev;
+Prev = &Assoc;
+if (!First)
+First = &Assoc;
+}
+if (First)
+First->Next = Prev;
+return First;
+}
+void updateMemoryUsage() {
+auto StringMapHeap = [](const auto &Map) {
+// StringMap stores the hashtable on the heap.
+// It contains pointers to the entries, and a hashcode for each.
+return Map.getNumBuckets() * (sizeof(void *) + sizeof(unsigned));
+};
+size_t Usage = Arena.getTotalMemory() + StringMapHeap(MainToFirst) +
+StringMapHeap(HeaderToMain) + sizeof(*this);
+UsedBytes.store(Usage, std::memory_order_release);
+}
+public:
+HeaderIncluderCache() : HeaderToMain(Arena), MainToFirst(Arena) {
+updateMemoryUsage();
+}
+// Associate each header with MainFile (unless already associated).
+// Headers not in the list will have their associations removed.
+void update(PathRef MainFile, llvm::ArrayRef<std::string> Headers) {
+std::lock_guard<std::mutex> Lock(Mu);
+auto It = MainToFirst.try_emplace(MainFile, nullptr);
+Association *&First = It.first->second;
+if (First)
+invalidate(First);
+First = associate(It.first->first(), Headers);
+updateMemoryUsage();
+}
+// Mark MainFile as gone.
+// This will *not* disassociate headers with MainFile immediately, but they
+// will be eligible for association with other files that get update()d.
+void remove(PathRef MainFile) {
+std::lock_guard<std::mutex> Lock(Mu);
+Association *&First = MainToFirst[MainFile];
+if (First)
+invalidate(First);
+}
+/// Get the mainfile associated with Header, or the empty string if none.
+std::string get(PathRef Header) const {
+std::lock_guard<std::mutex> Lock(Mu);
+return HeaderToMain.lookup(Header).MainFile.str();
+}
+size_t getUsedBytes() const {
+return UsedBytes.load(std::memory_order_acquire);
+}
+};
 namespace {
+bool isReliable(const tooling::CompileCommand &Cmd) {
+return Cmd.Heuristic.empty();
+}
 /// Threadsafe manager for updating a TUStatus and emitting it after each
 /// update.
 class SynchronizedTUStatus {
 public:
 SynchronizedTUStatus(PathRef FileName, ParsingCallbacks &Callbacks)
 /// instead.
 class PreambleThread {
 public:
 PreambleThread(llvm::StringRef FileName, ParsingCallbacks &Callbacks,
 bool StorePreambleInMemory, bool RunSync,
-SynchronizedTUStatus &Status, ASTWorker &AW)
+SynchronizedTUStatus &Status,
+TUScheduler::HeaderIncluderCache &HeaderIncluders,
+ASTWorker &AW)
 : FileName(FileName), Callbacks(Callbacks),
 StoreInMemory(StorePreambleInMemory), RunSync(RunSync), Status(Status),
-ASTPeer(AW) {}
+ASTPeer(AW), HeaderIncluders(HeaderIncluders) {}
 /// 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(std::unique_ptr<CompilerInvocation> CI, ParseInputs PI,
 Status.PreambleActivity = PreambleAction::Idle;
 });
 return;
 }
 {
-std::lock_guard<std::mutex> Lock(Mutex);
+std::unique_lock<std::mutex> Lock(Mutex);
-// If shutdown is issued, don't bother building.
+// If NextReq was requested with WantDiagnostics::Yes we cannot just drop
-if (Done)
+// that on the floor. Block until we start building it. This won't
-return;
+// dead-lock as we are blocking the caller thread, while builds continue
+// on preamble thread.
+ReqCV.wait(Lock, [this] {
+return !NextReq || NextReq->WantDiags != WantDiagnostics::Yes;
+});
 NextReq = std::move(Req);
 }
 // Let the worker thread know there's a request, notify_one is safe as there
 // should be a single worker thread waiting on it.
 ReqCV.notify_all();
 NextReq.reset();
 }
 {
 WithContext Guard(std::move(CurrentReq->Ctx));
+// Note that we don't make use of the ContextProvider here.
+// Preamble tasks are always scheduled by ASTWorker tasks, and we
+// reuse the context/config that was created at that level.
 // Build the preamble and let the waiters know about it.
 build(std::move(*CurrentReq));
 }
 bool IsEmpty = false;
 {
 const bool StoreInMemory;
 const bool RunSync;
 SynchronizedTUStatus &Status;
 ASTWorker &ASTPeer;
+TUScheduler::HeaderIncluderCache &HeaderIncluders;
 };
 class ASTWorkerHandle;
 /// Owns one instance of the AST, schedules updates and reads of it.
 /// signals the worker to exit its run loop and gives up shared ownership of the
 /// worker.
 class ASTWorker {
 friend class ASTWorkerHandle;
 ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB,
-TUScheduler::ASTCache &LRUCache, Semaphore &Barrier, bool RunSync,
+TUScheduler::ASTCache &LRUCache,
-DebouncePolicy UpdateDebounce, bool StorePreamblesInMemory,
+TUScheduler::HeaderIncluderCache &HeaderIncluders,
+Semaphore &Barrier, bool RunSync, const TUScheduler::Options &Opts,
 ParsingCallbacks &Callbacks);
 public:
 /// Create a new ASTWorker and return a handle to it.
 /// The processing thread is spawned using \p Tasks. However, when \p Tasks
 /// is null, all requests will be processed on the calling thread
 /// synchronously instead. \p Barrier is acquired when processing each
 /// request, it is used to limit the number of actively running threads.
 static ASTWorkerHandle
 create(PathRef FileName, const GlobalCompilationDatabase &CDB,
-TUScheduler::ASTCache &IdleASTs, AsyncTaskRunner *Tasks,
+TUScheduler::ASTCache &IdleASTs,
-Semaphore &Barrier, DebouncePolicy UpdateDebounce,
+TUScheduler::HeaderIncluderCache &HeaderIncluders,
-bool StorePreamblesInMemory, ParsingCallbacks &Callbacks);
+AsyncTaskRunner *Tasks, Semaphore &Barrier,
+const TUScheduler::Options &Opts, ParsingCallbacks &Callbacks);
 ~ASTWorker();
-void update(ParseInputs Inputs, WantDiagnostics);
+void update(ParseInputs Inputs, WantDiagnostics, bool ContentChanged);
 void
 runWithAST(llvm::StringRef Name,
 llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action,
 TUScheduler::ASTActionInvalidation);
 bool blockUntilIdle(Deadline Timeout) const;
-std::shared_ptr<const PreambleData> getPossiblyStalePreamble() const;
+std::shared_ptr<const PreambleData> getPossiblyStalePreamble(
+std::shared_ptr<const ASTSignals> *ASTSignals = nullptr) const;
 /// Used to inform ASTWorker about a new preamble build by PreambleThread.
 /// Diagnostics are only published through this callback. This ensures they
 /// are always for newer versions of the file, as the callback gets called in
 /// the same order as update requests.
 TUScheduler::FileStats stats() const;
 bool isASTCached() const;
 private:
+// Details of an update request that are relevant to scheduling.
+struct UpdateType {
+// Do we want diagnostics from this version?
+// If Yes, we must always build this version.
+// If No, we only need to build this version if it's read.
+// If Auto, we build if it's read or if the debounce expires.
+WantDiagnostics Diagnostics;
+// Did the main-file content of the document change?
+// If so, we're allowed to cancel certain invalidated preceding reads.
+bool ContentChanged;
+};
 /// 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);
+void updateASTSignals(ParsedAST &AST);
 // Must be called exactly once on processing thread. Will return after
 // stop() is called on a separate thread and all pending requests are
 // processed.
 void run();
 /// Signal that run() should finish processing pending requests and exit.
 void stop();
 /// Adds a new task to the end of the request queue.
 void startTask(llvm::StringRef Name, llvm::unique_function<void()> Task,
-llvm::Optional<WantDiagnostics> UpdateType,
+llvm::Optional<UpdateType> Update,
 TUScheduler::ASTActionInvalidation);
 /// Determines the next action to perform.
 /// All actions that should never run are discarded.
 /// Returns a deadline for the next action. If it's expired, run now.
 struct Request {
 llvm::unique_function<void()> Action;
 std::string Name;
 steady_clock::time_point AddTime;
 Context Ctx;
-llvm::Optional<WantDiagnostics> UpdateType;
+llvm::Optional<Context> QueueCtx;
+llvm::Optional<UpdateType> Update;
 TUScheduler::ASTActionInvalidation InvalidationPolicy;
 Canceler Invalidate;
 };
 /// Handles retention of ASTs.
 TUScheduler::ASTCache &IdleASTs;
+TUScheduler::HeaderIncluderCache &HeaderIncluders;
 const bool RunSync;
 /// Time to wait after an update to see whether another update obsoletes it.
 const DebouncePolicy UpdateDebounce;
 /// File that ASTWorker is responsible for.
 const Path FileName;
+/// Callback to create processing contexts for tasks.
+const std::function<Context(llvm::StringRef)> ContextProvider;
 const GlobalCompilationDatabase &CDB;
 /// Callback invoked when preamble or main file AST is built.
 ParsingCallbacks &Callbacks;
-/// Latest build preamble for current TU.
-std::shared_ptr<const PreambleData> LatestPreamble;
-Notification BuiltFirstPreamble;
 Semaphore &Barrier;
 /// Whether the 'onMainAST' callback ran for the current FileInputs.
 bool RanASTCallback = false;
 /// Guards members used by both TUScheduler and the worker thread.
 /// File inputs, currently being used by the worker.
 /// Writes and reads from unknown threads are locked. Reads from the worker
 /// thread are not locked, as it's the only writer.
 ParseInputs FileInputs; /* GUARDED_BY(Mutex) */
 /// Times of recent AST rebuilds, used for UpdateDebounce computation.
-llvm::SmallVector<DebouncePolicy::clock::duration, 8>
+llvm::SmallVector<DebouncePolicy::clock::duration>
 RebuildTimes; /* GUARDED_BY(Mutex) */
 /// Set to true to signal run() to finish processing.
 bool Done;                              /* GUARDED_BY(Mutex) */
 std::deque<Request> Requests;           /* GUARDED_BY(Mutex) */
-std::queue<Request> PreambleRequests;   /* GUARDED_BY(Mutex) */
 llvm::Optional<Request> CurrentRequest; /* GUARDED_BY(Mutex) */
+/// Signalled whenever a new request has been scheduled or processing of a
+/// request has completed.
 mutable std::condition_variable RequestsCV;
+std::shared_ptr<const ASTSignals> LatestASTSignals; /* GUARDED_BY(Mutex) */
+/// Latest build preamble for current TU.
+/// None means no builds yet, null means there was an error while building.
+/// Only written by ASTWorker's thread.
+llvm::Optional<std::shared_ptr<const PreambleData>> LatestPreamble;
+std::deque<Request> PreambleRequests; /* GUARDED_BY(Mutex) */
+/// Signaled whenever LatestPreamble changes state or there's a new
+/// PreambleRequest.
+mutable std::condition_variable PreambleCV;
 /// Guards the callback that publishes results of AST-related computations
-/// (diagnostics, highlightings) and file statuses.
+/// (diagnostics) and file statuses.
 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
 std::shared_ptr<ASTWorker> Worker;
 };
 ASTWorkerHandle
 ASTWorker::create(PathRef FileName, const GlobalCompilationDatabase &CDB,
-TUScheduler::ASTCache &IdleASTs, AsyncTaskRunner *Tasks,
+TUScheduler::ASTCache &IdleASTs,
-Semaphore &Barrier, DebouncePolicy UpdateDebounce,
+TUScheduler::HeaderIncluderCache &HeaderIncluders,
-bool StorePreamblesInMemory, ParsingCallbacks &Callbacks) {
+AsyncTaskRunner *Tasks, Semaphore &Barrier,
+const TUScheduler::Options &Opts,
+ParsingCallbacks &Callbacks) {
 std::shared_ptr<ASTWorker> Worker(
-new ASTWorker(FileName, CDB, IdleASTs, Barrier, /*RunSync=*/!Tasks,
+new ASTWorker(FileName, CDB, IdleASTs, HeaderIncluders, Barrier,
-UpdateDebounce, StorePreamblesInMemory, Callbacks));
+/*RunSync=*/!Tasks, Opts, Callbacks));
 if (Tasks) {
 Tasks->runAsync("ASTWorker:" + llvm::sys::path::filename(FileName),
 [Worker]() { Worker->run(); });
 Tasks->runAsync("PreambleWorker:" + llvm::sys::path::filename(FileName),
 [Worker]() { Worker->PreamblePeer.run(); });
 return ASTWorkerHandle(std::move(Worker));
 }
 ASTWorker::ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB,
-TUScheduler::ASTCache &LRUCache, Semaphore &Barrier,
+TUScheduler::ASTCache &LRUCache,
-bool RunSync, DebouncePolicy UpdateDebounce,
+TUScheduler::HeaderIncluderCache &HeaderIncluders,
-bool StorePreamblesInMemory, ParsingCallbacks &Callbacks)
+Semaphore &Barrier, bool RunSync,
-: IdleASTs(LRUCache), RunSync(RunSync), UpdateDebounce(UpdateDebounce),
+const TUScheduler::Options &Opts,
-FileName(FileName), CDB(CDB), Callbacks(Callbacks), Barrier(Barrier),
+ParsingCallbacks &Callbacks)
-Done(false), Status(FileName, Callbacks),
+: IdleASTs(LRUCache), HeaderIncluders(HeaderIncluders), RunSync(RunSync),
-PreamblePeer(FileName, Callbacks, StorePreamblesInMemory,
+UpdateDebounce(Opts.UpdateDebounce), FileName(FileName),
-// FIXME: Run PreamblePeer asynchronously once ast patching
+ContextProvider(Opts.ContextProvider), CDB(CDB), Callbacks(Callbacks),
-// is available.
+Barrier(Barrier), Done(false), Status(FileName, Callbacks),
-/*RunSync=*/true, Status, *this) {
+PreamblePeer(FileName, Callbacks, Opts.StorePreamblesInMemory, RunSync,
+Status, HeaderIncluders, *this) {
 // Set a fallback command because compile command can be accessed before
 // `Inputs` is initialized. Other fields are only used after initialization
 // from client inputs.
 FileInputs.CompileCommand = CDB.getFallbackCommand(FileName);
 }
 assert(Requests.empty() && !CurrentRequest &&
 "unprocessed requests when destroying ASTWorker");
 #endif
 }
-void ASTWorker::update(ParseInputs Inputs, WantDiagnostics WantDiags) {
+void ASTWorker::update(ParseInputs Inputs, WantDiagnostics WantDiags,
+bool ContentChanged) {
 std::string TaskName = llvm::formatv("Update ({0})", Inputs.Version);
 auto Task = [=]() mutable {
 // 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
 // "PreparingBuild" status to inform users, it is non-trivial given the
 // current implementation.
-if (auto Cmd = CDB.getCompileCommand(FileName))
+auto Cmd = CDB.getCompileCommand(FileName);
-Inputs.CompileCommand = *Cmd;
+// If we don't have a reliable command for this file, it may be a header.
+// Try to find a file that includes it, to borrow its command.
+if (!Cmd || !isReliable(*Cmd)) {
+std::string ProxyFile = HeaderIncluders.get(FileName);
+if (!ProxyFile.empty()) {
+auto ProxyCmd = CDB.getCompileCommand(ProxyFile);
+if (!ProxyCmd || !isReliable(*ProxyCmd)) {
+// This command is supposed to be reliable! It's probably gone.
+HeaderIncluders.remove(ProxyFile);
+} else {
+// We have a reliable command for an including file, use it.
+Cmd = tooling::transferCompileCommand(std::move(*ProxyCmd), FileName);
+}
+}
+}
+if (Cmd)
+Inputs.CompileCommand = std::move(*Cmd);
 else
-// FIXME: consider using old command if it's not a fallback one.
 Inputs.CompileCommand = CDB.getFallbackCommand(FileName);
 bool InputsAreTheSame =
 std::tie(FileInputs.CompileCommand, FileInputs.Contents) ==
 std::tie(Inputs.CompileCommand, Inputs.Contents);
 }
 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, " "));
+printArgv(Inputs.CompileCommand.CommandLine));
 StoreDiags CompilerInvocationDiagConsumer;
 std::vector<std::string> CC1Args;
 std::unique_ptr<CompilerInvocation> Invocation = buildCompilerInvocation(
 Inputs, CompilerInvocationDiagConsumer, &CC1Args);
 // Log cc1 args even (especially!) if creating invocation failed.
 if (!CC1Args.empty())
-vlog("Driver produced command: cc1 {0}", llvm::join(CC1Args, " "));
+vlog("Driver produced command: cc1 {0}", printArgv(CC1Args));
 std::vector<Diag> CompilerInvocationDiags =
 CompilerInvocationDiagConsumer.take();
 if (!Invocation) {
 elog("Could not build CompilerInvocation for file {0}", FileName);
 // Remove the old AST if it's still in cache.
 // are not race conditions.
 std::lock_guard<std::mutex> Lock(PublishMu);
 if (CanPublishResults)
 Publish();
 });
+// Note that this might throw away a stale preamble that might still be
+// useful, but this is how we communicate a build error.
+LatestPreamble.emplace();
 // Make sure anyone waiting for the preamble gets notified it could not be
 // built.
-BuiltFirstPreamble.notify();
+PreambleCV.notify_all();
 return;
 }
 PreamblePeer.update(std::move(Invocation), std::move(Inputs),
 std::move(CompilerInvocationDiags), WantDiags);
+std::unique_lock<std::mutex> Lock(Mutex);
+PreambleCV.wait(Lock, [this] {
+// Block until we reiceve a preamble request, unless a preamble already
+// exists, as patching an empty preamble would imply rebuilding it from
+// scratch.
+// We block here instead of the consumer to prevent any deadlocks. Since
+// LatestPreamble is only populated by ASTWorker thread.
+return LatestPreamble || !PreambleRequests.empty() || Done;
+});
 return;
 };
-startTask(TaskName, std::move(Task), WantDiags, TUScheduler::NoInvalidation);
+startTask(TaskName, std::move(Task), UpdateType{WantDiags, ContentChanged},
+TUScheduler::NoInvalidation);
 }
 void ASTWorker::runWithAST(
 llvm::StringRef Name,
 llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action,
 // 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>(
+return Action(error(llvm::errc::invalid_argument, "invalid AST"));
-"invalid AST", llvm::errc::invalid_argument));
 vlog("ASTWorker running {0} on version {2} of {1}", Name, FileName,
 FileInputs.Version);
 Action(InputsAndAST{FileInputs, **AST});
 };
-startTask(Name, std::move(Task), /*UpdateType=*/None, Invalidation);
+startTask(Name, std::move(Task), /*Update=*/None, Invalidation);
 }
 void PreambleThread::build(Request Req) {
 assert(Req.CI && "Got preamble request with null compiler invocation");
 const ParseInputs &Inputs = Req.Inputs;
 });
 auto _ = llvm::make_scope_exit([this, &Req] {
 ASTPeer.updatePreamble(std::move(Req.CI), std::move(Req.Inputs),
 LatestBuild, std::move(Req.CIDiags),
 std::move(Req.WantDiags));
+Callbacks.onPreamblePublished(FileName);
 });
 if (!LatestBuild || Inputs.ForceRebuild) {
 vlog("Building first preamble for {0} version {1}", FileName,
 Inputs.Version);
 std::shared_ptr<clang::Preprocessor> PP,
 const CanonicalIncludes &CanonIncludes) {
 Callbacks.onPreambleAST(FileName, Version, Ctx, std::move(PP),
 CanonIncludes);
 });
+if (LatestBuild && isReliable(LatestBuild->CompileCommand))
+HeaderIncluders.update(FileName, LatestBuild->Includes.allHeaders());
 }
 void ASTWorker::updatePreamble(std::unique_ptr<CompilerInvocation> CI,
 ParseInputs PI,
 std::shared_ptr<const PreambleData> Preamble,
 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) {
+if (!LatestPreamble || 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);
+if (LatestPreamble)
-}
+std::swap(*LatestPreamble, Preamble);
+else
+LatestPreamble = std::move(Preamble);
+}
+// Notify anyone waiting for a preamble.
+PreambleCV.notify_all();
 // Give up our ownership to old preamble before starting expensive AST
 // build.
 Preamble.reset();
-BuiltFirstPreamble.notify();
 // 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
 Task();
 return;
 }
 {
 std::lock_guard<std::mutex> Lock(Mutex);
-PreambleRequests.push({std::move(Task), std::move(TaskName),
+PreambleRequests.push_back({std::move(Task), std::move(TaskName),
 steady_clock::now(), Context::current().clone(),
-llvm::None, TUScheduler::NoInvalidation, nullptr});
+llvm::None, llvm::None,
-}
+TUScheduler::NoInvalidation, nullptr});
+}
+PreambleCV.notify_all();
 RequestsCV.notify_all();
+}
+void ASTWorker::updateASTSignals(ParsedAST &AST) {
+auto Signals = std::make_shared<const ASTSignals>(ASTSignals::derive(AST));
+// Existing readers of ASTSignals will have their copy preserved until the
+// read is completed. The last reader deletes the old ASTSignals.
+{
+std::lock_guard<std::mutex> Lock(Mutex);
+std::swap(LatestASTSignals, Signals);
+}
 }
 void ASTWorker::generateDiagnostics(
 std::unique_ptr<CompilerInvocation> Invocation, ParseInputs Inputs,
 std::vector<Diag> CIDiags) {
 // Tracks ast cache accesses for publishing diags.
 static constexpr trace::Metric ASTAccessForDiag(
 "ast_access_diag", trace::Metric::Counter, "result");
 assert(Invocation);
+assert(LatestPreamble);
 // No need to rebuild the AST if we won't send the diagnostics.
 {
 std::lock_guard<std::mutex> Lock(PublishMu);
 if (!CanPublishResults)
 return;
 llvm::Optional<std::unique_ptr<ParsedAST>> AST =
 IdleASTs.take(this, &ASTAccessForDiag);
 if (!AST || !InputsAreLatest) {
 auto RebuildStartTime = DebouncePolicy::clock::now();
 llvm::Optional<ParsedAST> NewAST = ParsedAST::build(
-FileName, Inputs, std::move(Invocation), CIDiags, LatestPreamble);
+FileName, Inputs, std::move(Invocation), CIDiags, *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);
 Publish();
 };
 if (*AST) {
 trace::Span Span("Running main AST callback");
 Callbacks.onMainAST(FileName, **AST, RunPublish);
+updateASTSignals(**AST);
 } 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.
 RanASTCallback = *AST != nullptr;
 IdleASTs.put(this, std::move(*AST));
 }
 }
-std::shared_ptr<const PreambleData>
+std::shared_ptr<const PreambleData> ASTWorker::getPossiblyStalePreamble(
-ASTWorker::getPossiblyStalePreamble() const {
+std::shared_ptr<const ASTSignals> *ASTSignals) const {
 std::lock_guard<std::mutex> Lock(Mutex);
-return LatestPreamble;
+if (ASTSignals)
-}
+*ASTSignals = LatestASTSignals;
+return LatestPreamble ? *LatestPreamble : nullptr;
-void ASTWorker::waitForFirstPreamble() const { BuiltFirstPreamble.wait(); }
+}
+void ASTWorker::waitForFirstPreamble() const {
+std::unique_lock<std::mutex> Lock(Mutex);
+PreambleCV.wait(Lock, [this] { return LatestPreamble.hasValue() || Done; });
+}
 tooling::CompileCommand ASTWorker::getCurrentCompileCommand() const {
 std::unique_lock<std::mutex> Lock(Mutex);
 return FileInputs.CompileCommand;
 }
 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.
-Result.UsedBytes = IdleASTs.getUsedBytes(this);
+Result.UsedBytesAST = IdleASTs.getUsedBytes(this);
 if (auto Preamble = getPossiblyStalePreamble())
-Result.UsedBytes += Preamble->Preamble.getSize();
+Result.UsedBytesPreamble = Preamble->Preamble.getSize();
 return Result;
 }
 bool ASTWorker::isASTCached() const { return IdleASTs.getUsedBytes(this) != 0; }
 {
 std::lock_guard<std::mutex> Lock(Mutex);
 assert(!Done && "stop() called twice");
 Done = true;
 }
+PreamblePeer.stop();
 // We are no longer going to build any preambles, let the waiters know that.
-BuiltFirstPreamble.notify();
+PreambleCV.notify_all();
-PreamblePeer.stop();
 Status.stop();
 RequestsCV.notify_all();
 }
 void ASTWorker::startTask(llvm::StringRef Name,
 llvm::unique_function<void()> Task,
-llvm::Optional<WantDiagnostics> UpdateType,
+llvm::Optional<UpdateType> Update,
 TUScheduler::ASTActionInvalidation Invalidation) {
 if (RunSync) {
 assert(!Done && "running a task after stop()");
 trace::Span Tracer(Name + ":" + llvm::sys::path::filename(FileName));
+WithContext WithProvidedContext(ContextProvider(FileName));
 Task();
 return;
 }
 {
 std::lock_guard<std::mutex> Lock(Mutex);
 assert(!Done && "running a task after stop()");
 // Cancel any requests invalidated by this request.
-if (UpdateType) {
+if (Update && Update->ContentChanged) {
 for (auto &R : llvm::reverse(Requests)) {
 if (R.InvalidationPolicy == TUScheduler::InvalidateOnUpdate)
 R.Invalidate();
-if (R.UpdateType)
+if (R.Update && R.Update->ContentChanged)
 break; // Older requests were already invalidated by the older update.
 }
 }
 // Allow this request to be cancelled if invalidated.
 if (Invalidation) {
 WithContext WC(std::move(Ctx));
 std::tie(Ctx, Invalidate) = cancelableTask(
 /*Reason=*/static_cast<int>(ErrorCode::ContentModified));
 }
+// Trace the time the request spends in the queue, and the requests that
+// it's going to wait for.
+llvm::Optional<Context> QueueCtx;
+if (trace::enabled()) {
+// Tracers that follow threads and need strict nesting will see a tiny
+// instantaneous event "we're enqueueing", and sometime later it runs.
+WithContext WC(Ctx.clone());
+trace::Span Tracer("Queued:" + Name);
+if (Tracer.Args) {
+if (CurrentRequest)
+SPAN_ATTACH(Tracer, "CurrentRequest", CurrentRequest->Name);
+llvm::json::Array PreambleRequestsNames;
+for (const auto &Req : PreambleRequests)
+PreambleRequestsNames.push_back(Req.Name);
+SPAN_ATTACH(Tracer, "PreambleRequestsNames",
+std::move(PreambleRequestsNames));
+llvm::json::Array RequestsNames;
+for (const auto &Req : Requests)
+RequestsNames.push_back(Req.Name);
+SPAN_ATTACH(Tracer, "RequestsNames", std::move(RequestsNames));
+}
+// For tracers that follow contexts, keep the trace span's context alive
+// until we dequeue the request, so they see the full duration.
+QueueCtx = Context::current().clone();
+}
 Requests.push_back({std::move(Task), std::string(Name), steady_clock::now(),
-std::move(Ctx), UpdateType, Invalidation,
+std::move(Ctx), std::move(QueueCtx), Update,
-std::move(Invalidate)});
+Invalidation, std::move(Invalidate)});
 }
 RequestsCV.notify_all();
 }
 void ASTWorker::run() {
 }
 // Any request in ReceivedPreambles is at least as old as the
 // Requests.front(), so prefer them first to preserve LSP order.
 if (!PreambleRequests.empty()) {
 CurrentRequest = std::move(PreambleRequests.front());
-PreambleRequests.pop();
+PreambleRequests.pop_front();
 } else {
 CurrentRequest = std::move(Requests.front());
 Requests.pop_front();
 }
 } // unlock Mutex
+// Inform tracing that the request was dequeued.
+CurrentRequest->QueueCtx.reset();
 // It is safe to perform reads to CurrentRequest without holding the lock as
 // only writer is also this thread.
 {
 std::unique_lock<Semaphore> Lock(Barrier, std::try_to_lock);
 trace::Span Tracer(CurrentRequest->Name);
 Status.update([&](TUStatus &Status) {
 Status.ASTActivity.K = ASTAction::RunningAction;
 Status.ASTActivity.Name = CurrentRequest->Name;
 });
+WithContext WithProvidedContext(ContextProvider(FileName));
 CurrentRequest->Action();
 }
 bool IsEmpty = false;
 {
 return Deadline::infinity(); // Wait for new requests.
 // Handle cancelled requests first so the rest of the scheduler doesn't.
 for (auto I = Requests.begin(), E = Requests.end(); I != E; ++I) {
 if (!isCancelled(I->Ctx)) {
 // Cancellations after the first read don't affect current scheduling.
-if (I->UpdateType == None)
+if (I->Update == None)
 break;
 continue;
 }
 // Cancelled reads are moved to the front of the queue and run immediately.
-if (I->UpdateType == None) {
+if (I->Update == None) {
 Request R = std::move(*I);
 Requests.erase(I);
 Requests.push_front(std::move(R));
 return Deadline::zero();
 }
 // Cancelled updates are downgraded to auto-diagnostics, and may be elided.
-if (I->UpdateType == WantDiagnostics::Yes)
+if (I->Update->Diagnostics == WantDiagnostics::Yes)
-I->UpdateType = WantDiagnostics::Auto;
+I->Update->Diagnostics = WantDiagnostics::Auto;
 }
 while (shouldSkipHeadLocked()) {
 vlog("ASTWorker skipping {0} for {1}", Requests.front().Name, FileName);
 Requests.pop_front();
 // 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 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)
+if (R.Update == None || R.Update->Diagnostics == WantDiagnostics::Yes)
 return Deadline::zero();
 // Front request needs to be debounced, so determine when we're ready.
 Deadline D(Requests.front().AddTime + UpdateDebounce.compute(RebuildTimes));
 return D;
 }
 // Returns true if Requests.front() is a dead update that can be skipped.
 bool ASTWorker::shouldSkipHeadLocked() const {
 assert(!Requests.empty());
 auto Next = Requests.begin();
-auto UpdateType = Next->UpdateType;
+auto Update = Next->Update;
-if (!UpdateType) // Only skip updates.
+if (!Update) // Only skip updates.
 return false;
 ++Next;
 // An update is live if its AST might still be read.
 // That is, if it's not immediately followed by another update.
-if (Next == Requests.end() || !Next->UpdateType)
+if (Next == Requests.end() || !Next->Update)
 return false;
 // The other way an update can be live is if its diagnostics might be used.
-switch (*UpdateType) {
+switch (Update->Diagnostics) {
 case WantDiagnostics::Yes:
 return false; // Always used.
 case WantDiagnostics::No:
 return true; // Always dead.
 case WantDiagnostics::Auto:
 // Used unless followed by an update that generates diagnostics.
 for (; Next != Requests.end(); ++Next)
-if (Next->UpdateType == WantDiagnostics::Yes ||
+if (Next->Update && Next->Update->Diagnostics != WantDiagnostics::No)
-Next->UpdateType == WantDiagnostics::Auto)
 return true; // Prefer later diagnostics.
 return false;
 }
 llvm_unreachable("Unknown WantDiagnostics");
 }
 bool ASTWorker::blockUntilIdle(Deadline Timeout) const {
-std::unique_lock<std::mutex> Lock(Mutex);
+auto WaitUntilASTWorkerIsIdle = [&] {
-return wait(Lock, RequestsCV, Timeout, [&] {
+std::unique_lock<std::mutex> Lock(Mutex);
-return PreambleRequests.empty() && Requests.empty() && !CurrentRequest;
+return wait(Lock, RequestsCV, Timeout, [&] {
-});
+return PreambleRequests.empty() && Requests.empty() && !CurrentRequest;
+});
+};
+// Make sure ASTWorker has processed all requests, which might issue new
+// updates to PreamblePeer.
+WaitUntilASTWorkerIsIdle();
+// Now that ASTWorker processed all requests, ensure PreamblePeer has served
+// all update requests. This might create new PreambleRequests for the
+// ASTWorker.
+PreamblePeer.blockUntilIdle(Timeout);
+assert(Requests.empty() &&
+"No new normal tasks can be scheduled concurrently with "
+"blockUntilIdle(): ASTWorker isn't threadsafe");
+// Finally make sure ASTWorker has processed all of the preamble updates.
+return WaitUntilASTWorkerIsIdle();
 }
 // Render a TUAction to a user-facing string representation.
 // TUAction represents clangd-internal states, we don't intend to expose them
 // to users (say C++ programmers) directly to avoid confusion, we use terms that
 // We handle idle specially below.
 break;
 }
 if (Result.empty())
 return "idle";
-return llvm::join(Result, ",");
+return llvm::join(Result, ", ");
 }
 } // namespace
 unsigned getDefaultAsyncThreadsCount() {
 };
 TUScheduler::TUScheduler(const GlobalCompilationDatabase &CDB,
 const Options &Opts,
 std::unique_ptr<ParsingCallbacks> Callbacks)
-: CDB(CDB), StorePreamblesInMemory(Opts.StorePreamblesInMemory),
+: CDB(CDB), Opts(Opts),
 Callbacks(Callbacks ? move(Callbacks)
 : std::make_unique<ParsingCallbacks>()),
-Barrier(Opts.AsyncThreadsCount),
+Barrier(Opts.AsyncThreadsCount), QuickRunBarrier(Opts.AsyncThreadsCount),
 IdleASTs(
 std::make_unique<ASTCache>(Opts.RetentionPolicy.MaxRetainedASTs)),
-UpdateDebounce(Opts.UpdateDebounce) {
+HeaderIncluders(std::make_unique<HeaderIncluderCache>()) {
+// Avoid null checks everywhere.
+if (!Opts.ContextProvider) {
+this->Opts.ContextProvider = [](llvm::StringRef) {
+return Context::current().clone();
+};
+}
 if (0 < Opts.AsyncThreadsCount) {
 PreambleTasks.emplace();
 WorkerThreads.emplace();
 }
 }
 bool TUScheduler::update(PathRef File, ParseInputs Inputs,
 WantDiagnostics WantDiags) {
 std::unique_ptr<FileData> &FD = Files[File];
 bool NewFile = FD == nullptr;
+bool ContentChanged = false;
 if (!FD) {
 // Create a new worker to process the AST-related tasks.
-ASTWorkerHandle Worker = ASTWorker::create(
+ASTWorkerHandle Worker =
-File, CDB, *IdleASTs,
+ASTWorker::create(File, CDB, *IdleASTs, *HeaderIncluders,
-WorkerThreads ? WorkerThreads.getPointer() : nullptr, Barrier,
+WorkerThreads ? WorkerThreads.getPointer() : nullptr,
-UpdateDebounce, StorePreamblesInMemory, *Callbacks);
+Barrier, Opts, *Callbacks);
 FD = std::unique_ptr<FileData>(
 new FileData{Inputs.Contents, std::move(Worker)});
-} else {
+ContentChanged = true;
+} else if (FD->Contents != Inputs.Contents) {
+ContentChanged = true;
 FD->Contents = Inputs.Contents;
 }
-FD->Worker->update(std::move(Inputs), WantDiags);
+FD->Worker->update(std::move(Inputs), WantDiags, ContentChanged);
+// There might be synthetic update requests, don't change the LastActiveFile
+// in such cases.
+if (ContentChanged)
+LastActiveFile = File.str();
 return NewFile;
 }
 void TUScheduler::remove(PathRef File) {
 bool Removed = Files.erase(File);
 if (!Removed)
 elog("Trying to remove file from TUScheduler that is not tracked: {0}",
 File);
-}
+// We don't call HeaderIncluders.remove(File) here.
+// If we did, we'd avoid potentially stale header/mainfile associations.
-llvm::StringMap<std::string> TUScheduler::getAllFileContents() const {
+// However, it would mean that closing a mainfile could invalidate the
-llvm::StringMap<std::string> Results;
+// preamble of several open headers.
-for (auto &It : Files)
+}
-Results.try_emplace(It.getKey(), It.getValue()->Contents);
-return Results;
+void TUScheduler::run(llvm::StringRef Name, llvm::StringRef Path,
-}
-void TUScheduler::run(llvm::StringRef Name,
 llvm::unique_function<void()> Action) {
-if (!PreambleTasks)
+runWithSemaphore(Name, Path, std::move(Action), Barrier);
+}
+void TUScheduler::runQuick(llvm::StringRef Name, llvm::StringRef Path,
+llvm::unique_function<void()> Action) {
+// Use QuickRunBarrier to serialize quick tasks: we are ignoring
+// the parallelism level set by the user, don't abuse it
+runWithSemaphore(Name, Path, std::move(Action), QuickRunBarrier);
+}
+void TUScheduler::runWithSemaphore(llvm::StringRef Name, llvm::StringRef Path,
+llvm::unique_function<void()> Action,
+Semaphore &Sem) {
+if (Path.empty())
+Path = LastActiveFile;
+else
+LastActiveFile = Path.str();
+if (!PreambleTasks) {
+WithContext WithProvidedContext(Opts.ContextProvider(Path));
 return Action();
-PreambleTasks->runAsync(Name, [this, Ctx = Context::current().clone(),
+}
+PreambleTasks->runAsync(Name, [this, &Sem, Ctx = Context::current().clone(),
+Path(Path.str()),
 Action = std::move(Action)]() mutable {
-std::lock_guard<Semaphore> BarrierLock(Barrier);
+std::lock_guard<Semaphore> BarrierLock(Sem);
 WithContext WC(std::move(Ctx));
+WithContext WithProvidedContext(Opts.ContextProvider(Path));
 Action();
 });
 }
 void TUScheduler::runWithAST(
 if (It == Files.end()) {
 Action(llvm::make_error<LSPError>(
 "trying to get AST for non-added document", ErrorCode::InvalidParams));
 return;
 }
+LastActiveFile = File.str();
 It->second->Worker->runWithAST(Name, std::move(Action), Invalidation);
 }
 void TUScheduler::runWithPreamble(llvm::StringRef Name, PathRef File,
 Action(llvm::make_error<LSPError>(
 "trying to get preamble for non-added document",
 ErrorCode::InvalidParams));
 return;
 }
+LastActiveFile = File.str();
 if (!PreambleTasks) {
 trace::Span Tracer(Name);
 SPAN_ATTACH(Tracer, "file", File);
+std::shared_ptr<const ASTSignals> Signals;
 std::shared_ptr<const PreambleData> Preamble =
-It->second->Worker->getPossiblyStalePreamble();
+It->second->Worker->getPossiblyStalePreamble(&Signals);
+WithContext WithProvidedContext(Opts.ContextProvider(File));
 Action(InputsAndPreamble{It->second->Contents,
 It->second->Worker->getCurrentCompileCommand(),
-Preamble.get()});
+Preamble.get(), Signals.get()});
 return;
 }
 std::shared_ptr<const ASTWorker> Worker = It->second->Worker.lock();
-auto Task =
+auto Task = [Worker, Consistency, Name = Name.str(), File = File.str(),
-[Worker, Consistency, Name = Name.str(), File = File.str(),
+Contents = It->second->Contents,
-Contents = It->second->Contents,
+Command = Worker->getCurrentCompileCommand(),
-Command = Worker->getCurrentCompileCommand(),
+Ctx = Context::current().derive(kFileBeingProcessed,
-Ctx = Context::current().derive(kFileBeingProcessed, std::string(File)),
+std::string(File)),
 Action = std::move(Action), this]() mutable {
 std::shared_ptr<const PreambleData> Preamble;
 if (Consistency == PreambleConsistency::Stale) {
 // Wait until the preamble is built for the first time, if preamble
 // is required. This avoids extra work of processing the preamble
 // headers in parallel multiple times.
 Worker->waitForFirstPreamble();
 }
-Preamble = Worker->getPossiblyStalePreamble();
+std::shared_ptr<const ASTSignals> Signals;
+Preamble = Worker->getPossiblyStalePreamble(&Signals);
-std::lock_guard<Semaphore> BarrierLock(Barrier);
-WithContext Guard(std::move(Ctx));
+std::lock_guard<Semaphore> BarrierLock(Barrier);
-trace::Span Tracer(Name);
+WithContext Guard(std::move(Ctx));
-SPAN_ATTACH(Tracer, "file", File);
+trace::Span Tracer(Name);
-Action(InputsAndPreamble{Contents, Command, Preamble.get()});
+SPAN_ATTACH(Tracer, "file", File);
-};
+WithContext WithProvidedContext(Opts.ContextProvider(File));
+Action(InputsAndPreamble{Contents, Command, Preamble.get(), Signals.get()});
+};
 PreambleTasks->runAsync("task:" + llvm::sys::path::filename(File),
 std::move(Task));
 }
 DebouncePolicy P;
 P.Min = P.Max = T;
 return P;
 }
+void TUScheduler::profile(MemoryTree &MT) const {
+for (const auto &Elem : fileStats()) {
+MT.detail(Elem.first())
+.child("preamble")
+.addUsage(Opts.StorePreamblesInMemory ? Elem.second.UsedBytesPreamble
+: 0);
+MT.detail(Elem.first()).child("ast").addUsage(Elem.second.UsedBytesAST);
+MT.child("header_includer_cache").addUsage(HeaderIncluders->getUsedBytes());
+}
+}
 } // namespace clangd
 } // namespace clang

Mercurial > hg > CbC > CbC_llvm

comparison clang-tools-extra/clangd/TUScheduler.cpp @ 221:79ff65ed7e25