clang-tools  11.0.0git
TUScheduler.cpp
Go to the documentation of this file.
1 //===--- TUScheduler.cpp -----------------------------------------*-C++-*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 // TUScheduler manages a worker per active file. This ASTWorker processes
9 // updates (modifications to file contents) and reads (actions performed on
10 // preamble/AST) to the file.
11 //
12 // Each ASTWorker owns a dedicated thread to process updates and reads to the
13 // relevant file. Any request gets queued in FIFO order to be processed by that
14 // thread.
15 //
16 // An update request replaces current praser inputs to ensure any subsequent
17 // read sees the version of the file they were requested. It will also issue a
18 // build for new inputs.
19 //
20 // ASTWorker processes the file in two parts, a preamble and a main-file
21 // section. A preamble can be reused between multiple versions of the file until
22 // invalidated by a modification to a header, compile commands or modification
23 // to relevant part of the current file. Such a preamble is called compatible.
24 // An update is considered dead if no read was issued for that version and
25 // diagnostics weren't requested by client or could be generated for a later
26 // version of the file. ASTWorker eliminates such requests as they are
27 // redundant.
28 //
29 // In the presence of stale (non-compatible) preambles, ASTWorker won't publish
30 // diagnostics for update requests. Read requests will be served with ASTs build
31 // with stale preambles, unless the read is picky and requires a compatible
32 // preamble. In such cases it will block until new preamble is built.
33 //
34 // ASTWorker owns a PreambleThread for building preambles. If the preamble gets
35 // invalidated by an update request, a new build will be requested on
36 // PreambleThread. Since PreambleThread only receives requests for newer
37 // versions of the file, in case of multiple requests it will only build the
38 // last one and skip requests in between. Unless client force requested
39 // diagnostics(WantDiagnostics::Yes).
40 //
41 // When a new preamble is built, a "golden" AST is immediately built from that
42 // version of the file. This ensures diagnostics get updated even if the queue
43 // is full.
44 //
45 // Some read requests might just need preamble. Since preambles can be read
46 // concurrently, ASTWorker runs these requests on their own thread. These
47 // requests will receive latest build preamble, which might possibly be stale.
48 
49 #include "TUScheduler.h"
50 #include "Compiler.h"
51 #include "Diagnostics.h"
53 #include "ParsedAST.h"
54 #include "Preamble.h"
56 #include "support/Cancellation.h"
57 #include "support/Context.h"
58 #include "support/Logger.h"
59 #include "support/Path.h"
60 #include "support/Threading.h"
61 #include "support/Trace.h"
62 #include "clang/Frontend/CompilerInvocation.h"
63 #include "clang/Tooling/CompilationDatabase.h"
64 #include "llvm/ADT/FunctionExtras.h"
65 #include "llvm/ADT/None.h"
66 #include "llvm/ADT/Optional.h"
67 #include "llvm/ADT/STLExtras.h"
68 #include "llvm/ADT/ScopeExit.h"
69 #include "llvm/ADT/SmallVector.h"
70 #include "llvm/ADT/StringExtras.h"
71 #include "llvm/ADT/StringRef.h"
72 #include "llvm/Support/Errc.h"
73 #include "llvm/Support/ErrorHandling.h"
74 #include "llvm/Support/FormatVariadic.h"
75 #include "llvm/Support/Path.h"
76 #include "llvm/Support/Threading.h"
77 #include <algorithm>
78 #include <chrono>
79 #include <condition_variable>
80 #include <functional>
81 #include <memory>
82 #include <mutex>
83 #include <queue>
84 #include <string>
85 #include <thread>
86 #include <type_traits>
87 #include <utility>
88 #include <vector>
89 
90 namespace clang {
91 namespace clangd {
92 using std::chrono::steady_clock;
93 
94 namespace {
95 class ASTWorker;
96 } // namespace
97 
99 
100 llvm::Optional<llvm::StringRef> TUScheduler::getFileBeingProcessedInContext() {
101  if (auto *File = Context::current().get(kFileBeingProcessed))
102  return llvm::StringRef(*File);
103  return None;
104 }
105 
106 /// An LRU cache of idle ASTs.
107 /// Because we want to limit the overall number of these we retain, the cache
108 /// owns ASTs (and may evict them) while their workers are idle.
109 /// Workers borrow ASTs when active, and return them when done.
111 public:
112  using Key = const ASTWorker *;
113 
114  ASTCache(unsigned MaxRetainedASTs) : MaxRetainedASTs(MaxRetainedASTs) {}
115 
116  /// Returns result of getUsedBytes() for the AST cached by \p K.
117  /// If no AST is cached, 0 is returned.
118  std::size_t getUsedBytes(Key K) {
119  std::lock_guard<std::mutex> Lock(Mut);
120  auto It = findByKey(K);
121  if (It == LRU.end() || !It->second)
122  return 0;
123  return It->second->getUsedBytes();
124  }
125 
126  /// Store the value in the pool, possibly removing the last used AST.
127  /// The value should not be in the pool when this function is called.
128  void put(Key K, std::unique_ptr<ParsedAST> V) {
129  std::unique_lock<std::mutex> Lock(Mut);
130  assert(findByKey(K) == LRU.end());
131 
132  LRU.insert(LRU.begin(), {K, std::move(V)});
133  if (LRU.size() <= MaxRetainedASTs)
134  return;
135  // We're past the limit, remove the last element.
136  std::unique_ptr<ParsedAST> ForCleanup = std::move(LRU.back().second);
137  LRU.pop_back();
138  // Run the expensive destructor outside the lock.
139  Lock.unlock();
140  ForCleanup.reset();
141  }
142 
143  /// Returns the cached value for \p K, or llvm::None if the value is not in
144  /// the cache anymore. If nullptr was cached for \p K, this function will
145  /// return a null unique_ptr wrapped into an optional.
146  /// If \p AccessMetric is set records whether there was a hit or miss.
147  llvm::Optional<std::unique_ptr<ParsedAST>>
148  take(Key K, const trace::Metric *AccessMetric = nullptr) {
149  // Record metric after unlocking the mutex.
150  std::unique_lock<std::mutex> Lock(Mut);
151  auto Existing = findByKey(K);
152  if (Existing == LRU.end()) {
153  if (AccessMetric)
154  AccessMetric->record(1, "miss");
155  return None;
156  }
157  if (AccessMetric)
158  AccessMetric->record(1, "hit");
159  std::unique_ptr<ParsedAST> V = std::move(Existing->second);
160  LRU.erase(Existing);
161  // GCC 4.8 fails to compile `return V;`, as it tries to call the copy
162  // constructor of unique_ptr, so we call the move ctor explicitly to avoid
163  // this miscompile.
164  return llvm::Optional<std::unique_ptr<ParsedAST>>(std::move(V));
165  }
166 
167 private:
168  using KVPair = std::pair<Key, std::unique_ptr<ParsedAST>>;
169 
170  std::vector<KVPair>::iterator findByKey(Key K) {
171  return llvm::find_if(LRU, [K](const KVPair &P) { return P.first == K; });
172  }
173 
174  std::mutex Mut;
175  unsigned MaxRetainedASTs;
176  /// Items sorted in LRU order, i.e. first item is the most recently accessed
177  /// one.
178  std::vector<KVPair> LRU; /* GUARDED_BY(Mut) */
179 };
180 
181 namespace {
182 /// Threadsafe manager for updating a TUStatus and emitting it after each
183 /// update.
184 class SynchronizedTUStatus {
185 public:
186  SynchronizedTUStatus(PathRef FileName, ParsingCallbacks &Callbacks)
187  : FileName(FileName), Callbacks(Callbacks) {}
188 
189  void update(llvm::function_ref<void(TUStatus &)> Mutator) {
190  std::lock_guard<std::mutex> Lock(StatusMu);
191  Mutator(Status);
192  emitStatusLocked();
193  }
194 
195  /// Prevents emitting of further updates.
196  void stop() {
197  std::lock_guard<std::mutex> Lock(StatusMu);
198  CanPublish = false;
199  }
200 
201 private:
202  void emitStatusLocked() {
203  if (CanPublish)
204  Callbacks.onFileUpdated(FileName, Status);
205  }
206 
207  const Path FileName;
208 
209  std::mutex StatusMu;
210  TUStatus Status;
211  bool CanPublish = true;
212  ParsingCallbacks &Callbacks;
213 };
214 
215 /// Responsible for building preambles. Whenever the thread is idle and the
216 /// preamble is outdated, it starts to build a fresh preamble from the latest
217 /// inputs. If RunSync is true, preambles are built synchronously in update()
218 /// instead.
219 class PreambleThread {
220 public:
221  PreambleThread(llvm::StringRef FileName, ParsingCallbacks &Callbacks,
222  bool StorePreambleInMemory, bool RunSync,
223  SynchronizedTUStatus &Status, ASTWorker &AW)
224  : FileName(FileName), Callbacks(Callbacks),
225  StoreInMemory(StorePreambleInMemory), RunSync(RunSync), Status(Status),
226  ASTPeer(AW) {}
227 
228  /// It isn't guaranteed that each requested version will be built. If there
229  /// are multiple update requests while building a preamble, only the last one
230  /// will be built.
231  void update(std::unique_ptr<CompilerInvocation> CI, ParseInputs PI,
232  std::vector<Diag> CIDiags, WantDiagnostics WantDiags) {
233  Request Req = {std::move(CI), std::move(PI), std::move(CIDiags), WantDiags,
234  Context::current().clone()};
235  if (RunSync) {
236  build(std::move(Req));
237  Status.update([](TUStatus &Status) {
239  });
240  return;
241  }
242  {
243  std::unique_lock<std::mutex> Lock(Mutex);
244  // If NextReq was requested with WantDiagnostics::Yes we cannot just drop
245  // that on the floor. Block until we start building it. This won't
246  // dead-lock as we are blocking the caller thread, while builds continue
247  // on preamble thread.
248  ReqCV.wait(Lock, [this] {
249  return !NextReq || NextReq->WantDiags != WantDiagnostics::Yes;
250  });
251  NextReq = std::move(Req);
252  }
253  // Let the worker thread know there's a request, notify_one is safe as there
254  // should be a single worker thread waiting on it.
255  ReqCV.notify_all();
256  }
257 
258  void run() {
259  while (true) {
260  {
261  std::unique_lock<std::mutex> Lock(Mutex);
262  assert(!CurrentReq && "Already processing a request?");
263  // Wait until stop is called or there is a request.
264  ReqCV.wait(Lock, [this] { return NextReq || Done; });
265  if (Done)
266  break;
267  CurrentReq = std::move(*NextReq);
268  NextReq.reset();
269  }
270 
271  {
272  WithContext Guard(std::move(CurrentReq->Ctx));
273  // Note that we don't make use of the ContextProvider here.
274  // Preamble tasks are always scheduled by ASTWorker tasks, and we
275  // reuse the context/config that was created at that level.
276 
277  // Build the preamble and let the waiters know about it.
278  build(std::move(*CurrentReq));
279  }
280  bool IsEmpty = false;
281  {
282  std::lock_guard<std::mutex> Lock(Mutex);
283  CurrentReq.reset();
284  IsEmpty = !NextReq.hasValue();
285  }
286  if (IsEmpty) {
287  // We don't perform this above, before waiting for a request to make
288  // tests more deterministic. As there can be a race between this thread
289  // and client thread(clangdserver).
290  Status.update([](TUStatus &Status) {
292  });
293  }
294  ReqCV.notify_all();
295  }
296  dlog("Preamble worker for {0} stopped", FileName);
297  }
298 
299  /// Signals the run loop to exit.
300  void stop() {
301  dlog("Preamble worker for {0} received stop", FileName);
302  {
303  std::lock_guard<std::mutex> Lock(Mutex);
304  Done = true;
305  NextReq.reset();
306  }
307  // Let the worker thread know that it should stop.
308  ReqCV.notify_all();
309  }
310 
311  bool blockUntilIdle(Deadline Timeout) const {
312  std::unique_lock<std::mutex> Lock(Mutex);
313  return wait(Lock, ReqCV, Timeout, [&] { return !NextReq && !CurrentReq; });
314  }
315 
316 private:
317  /// Holds inputs required for building a preamble. CI is guaranteed to be
318  /// non-null.
319  struct Request {
320  std::unique_ptr<CompilerInvocation> CI;
321  ParseInputs Inputs;
322  std::vector<Diag> CIDiags;
324  Context Ctx;
325  };
326 
327  bool isDone() {
328  std::lock_guard<std::mutex> Lock(Mutex);
329  return Done;
330  }
331 
332  /// Builds a preamble for \p Req, might reuse LatestBuild if possible.
333  /// Notifies ASTWorker after build finishes.
334  void build(Request Req);
335 
336  mutable std::mutex Mutex;
337  bool Done = false; /* GUARDED_BY(Mutex) */
338  llvm::Optional<Request> NextReq; /* GUARDED_BY(Mutex) */
339  llvm::Optional<Request> CurrentReq; /* GUARDED_BY(Mutex) */
340  // Signaled whenever a thread populates NextReq or worker thread builds a
341  // Preamble.
342  mutable std::condition_variable ReqCV; /* GUARDED_BY(Mutex) */
343  // Accessed only by preamble thread.
344  std::shared_ptr<const PreambleData> LatestBuild;
345 
346  const Path FileName;
347  ParsingCallbacks &Callbacks;
348  const bool StoreInMemory;
349  const bool RunSync;
350 
351  SynchronizedTUStatus &Status;
352  ASTWorker &ASTPeer;
353 };
354 
355 class ASTWorkerHandle;
356 
357 /// Owns one instance of the AST, schedules updates and reads of it.
358 /// Also responsible for building and providing access to the preamble.
359 /// Each ASTWorker processes the async requests sent to it on a separate
360 /// dedicated thread.
361 /// The ASTWorker that manages the AST is shared by both the processing thread
362 /// and the TUScheduler. The TUScheduler should discard an ASTWorker when
363 /// remove() is called, but its thread may be busy and we don't want to block.
364 /// So the workers are accessed via an ASTWorkerHandle. Destroying the handle
365 /// signals the worker to exit its run loop and gives up shared ownership of the
366 /// worker.
367 class ASTWorker {
368  friend class ASTWorkerHandle;
369  ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB,
370  TUScheduler::ASTCache &LRUCache, Semaphore &Barrier, bool RunSync,
371  const TUScheduler::Options &Opts, ParsingCallbacks &Callbacks);
372 
373 public:
374  /// Create a new ASTWorker and return a handle to it.
375  /// The processing thread is spawned using \p Tasks. However, when \p Tasks
376  /// is null, all requests will be processed on the calling thread
377  /// synchronously instead. \p Barrier is acquired when processing each
378  /// request, it is used to limit the number of actively running threads.
379  static ASTWorkerHandle create(PathRef FileName,
380  const GlobalCompilationDatabase &CDB,
381  TUScheduler::ASTCache &IdleASTs,
382  AsyncTaskRunner *Tasks, Semaphore &Barrier,
383  const TUScheduler::Options &Opts,
384  ParsingCallbacks &Callbacks);
385  ~ASTWorker();
386 
387  void update(ParseInputs Inputs, WantDiagnostics);
388  void
389  runWithAST(llvm::StringRef Name,
390  llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action,
392  bool blockUntilIdle(Deadline Timeout) const;
393 
394  std::shared_ptr<const PreambleData> getPossiblyStalePreamble() const;
395 
396  /// Used to inform ASTWorker about a new preamble build by PreambleThread.
397  /// Diagnostics are only published through this callback. This ensures they
398  /// are always for newer versions of the file, as the callback gets called in
399  /// the same order as update requests.
400  void updatePreamble(std::unique_ptr<CompilerInvocation> CI, ParseInputs PI,
401  std::shared_ptr<const PreambleData> Preamble,
402  std::vector<Diag> CIDiags, WantDiagnostics WantDiags);
403 
404  /// Obtain a preamble reflecting all updates so far. Threadsafe.
405  /// It may be delivered immediately, or later on the worker thread.
406  void getCurrentPreamble(
407  llvm::unique_function<void(std::shared_ptr<const PreambleData>)>);
408  /// Returns compile command from the current file inputs.
409  tooling::CompileCommand getCurrentCompileCommand() const;
410 
411  /// Wait for the first build of preamble to finish. Preamble itself can be
412  /// accessed via getPossiblyStalePreamble(). Note that this function will
413  /// return after an unsuccessful build of the preamble too, i.e. result of
414  /// getPossiblyStalePreamble() can be null even after this function returns.
415  void waitForFirstPreamble() const;
416 
417  TUScheduler::FileStats stats() const;
418  bool isASTCached() const;
419 
420 private:
421  /// Publishes diagnostics for \p Inputs. It will build an AST or reuse the
422  /// cached one if applicable. Assumes LatestPreamble is compatible for \p
423  /// Inputs.
424  void generateDiagnostics(std::unique_ptr<CompilerInvocation> Invocation,
425  ParseInputs Inputs, std::vector<Diag> CIDiags);
426 
427  // Must be called exactly once on processing thread. Will return after
428  // stop() is called on a separate thread and all pending requests are
429  // processed.
430  void run();
431  /// Signal that run() should finish processing pending requests and exit.
432  void stop();
433  /// Adds a new task to the end of the request queue.
434  void startTask(llvm::StringRef Name, llvm::unique_function<void()> Task,
435  llvm::Optional<WantDiagnostics> UpdateType,
437 
438  /// Determines the next action to perform.
439  /// All actions that should never run are discarded.
440  /// Returns a deadline for the next action. If it's expired, run now.
441  /// scheduleLocked() is called again at the deadline, or if requests arrive.
442  Deadline scheduleLocked();
443  /// Should the first task in the queue be skipped instead of run?
444  bool shouldSkipHeadLocked() const;
445 
446  struct Request {
447  llvm::unique_function<void()> Action;
448  std::string Name;
449  steady_clock::time_point AddTime;
450  Context Ctx;
451  llvm::Optional<WantDiagnostics> UpdateType;
454  };
455 
456  /// Handles retention of ASTs.
457  TUScheduler::ASTCache &IdleASTs;
458  const bool RunSync;
459  /// Time to wait after an update to see whether another update obsoletes it.
460  const DebouncePolicy UpdateDebounce;
461  /// File that ASTWorker is responsible for.
462  const Path FileName;
463  /// Callback to create processing contexts for tasks.
464  const std::function<Context(llvm::StringRef)> ContextProvider;
465  const GlobalCompilationDatabase &CDB;
466  /// Callback invoked when preamble or main file AST is built.
467  ParsingCallbacks &Callbacks;
468 
469  Semaphore &Barrier;
470  /// Whether the 'onMainAST' callback ran for the current FileInputs.
471  bool RanASTCallback = false;
472  /// Guards members used by both TUScheduler and the worker thread.
473  mutable std::mutex Mutex;
474  /// File inputs, currently being used by the worker.
475  /// Writes and reads from unknown threads are locked. Reads from the worker
476  /// thread are not locked, as it's the only writer.
477  ParseInputs FileInputs; /* GUARDED_BY(Mutex) */
478  /// Times of recent AST rebuilds, used for UpdateDebounce computation.
479  llvm::SmallVector<DebouncePolicy::clock::duration, 8>
480  RebuildTimes; /* GUARDED_BY(Mutex) */
481  /// Set to true to signal run() to finish processing.
482  bool Done; /* GUARDED_BY(Mutex) */
483  std::deque<Request> Requests; /* GUARDED_BY(Mutex) */
484  llvm::Optional<Request> CurrentRequest; /* GUARDED_BY(Mutex) */
485  /// Signalled whenever a new request has been scheduled or processing of a
486  /// request has completed.
487  mutable std::condition_variable RequestsCV;
488  /// Latest build preamble for current TU.
489  /// None means no builds yet, null means there was an error while building.
490  /// Only written by ASTWorker's thread.
491  llvm::Optional<std::shared_ptr<const PreambleData>> LatestPreamble;
492  std::queue<Request> PreambleRequests; /* GUARDED_BY(Mutex) */
493  /// Signaled whenever LatestPreamble changes state or there's a new
494  /// PreambleRequest.
495  mutable std::condition_variable PreambleCV;
496  /// Guards the callback that publishes results of AST-related computations
497  /// (diagnostics, highlightings) and file statuses.
498  std::mutex PublishMu;
499  // Used to prevent remove document + add document races that lead to
500  // out-of-order callbacks for publishing results of onMainAST callback.
501  //
502  // The lifetime of the old/new ASTWorkers will overlap, but their handles
503  // don't. When the old handle is destroyed, the old worker will stop reporting
504  // any results to the user.
505  bool CanPublishResults = true; /* GUARDED_BY(PublishMu) */
506  std::atomic<unsigned> ASTBuildCount = {0};
507  std::atomic<unsigned> PreambleBuildCount = {0};
508 
509  SynchronizedTUStatus Status;
510  PreambleThread PreamblePeer;
511 };
512 
513 /// A smart-pointer-like class that points to an active ASTWorker.
514 /// In destructor, signals to the underlying ASTWorker that no new requests will
515 /// be sent and the processing loop may exit (after running all pending
516 /// requests).
517 class ASTWorkerHandle {
518  friend class ASTWorker;
519  ASTWorkerHandle(std::shared_ptr<ASTWorker> Worker)
520  : Worker(std::move(Worker)) {
521  assert(this->Worker);
522  }
523 
524 public:
525  ASTWorkerHandle(const ASTWorkerHandle &) = delete;
526  ASTWorkerHandle &operator=(const ASTWorkerHandle &) = delete;
527  ASTWorkerHandle(ASTWorkerHandle &&) = default;
528  ASTWorkerHandle &operator=(ASTWorkerHandle &&) = default;
529 
530  ~ASTWorkerHandle() {
531  if (Worker)
532  Worker->stop();
533  }
534 
535  ASTWorker &operator*() {
536  assert(Worker && "Handle was moved from");
537  return *Worker;
538  }
539 
540  ASTWorker *operator->() {
541  assert(Worker && "Handle was moved from");
542  return Worker.get();
543  }
544 
545  /// Returns an owning reference to the underlying ASTWorker that can outlive
546  /// the ASTWorkerHandle. However, no new requests to an active ASTWorker can
547  /// be schedule via the returned reference, i.e. only reads of the preamble
548  /// are possible.
549  std::shared_ptr<const ASTWorker> lock() { return Worker; }
550 
551 private:
552  std::shared_ptr<ASTWorker> Worker;
553 };
554 
555 ASTWorkerHandle ASTWorker::create(PathRef FileName,
556  const GlobalCompilationDatabase &CDB,
557  TUScheduler::ASTCache &IdleASTs,
558  AsyncTaskRunner *Tasks, Semaphore &Barrier,
559  const TUScheduler::Options &Opts,
560  ParsingCallbacks &Callbacks) {
561  std::shared_ptr<ASTWorker> Worker(new ASTWorker(
562  FileName, CDB, IdleASTs, Barrier, /*RunSync=*/!Tasks, Opts, Callbacks));
563  if (Tasks) {
564  Tasks->runAsync("ASTWorker:" + llvm::sys::path::filename(FileName),
565  [Worker]() { Worker->run(); });
566  Tasks->runAsync("PreambleWorker:" + llvm::sys::path::filename(FileName),
567  [Worker]() { Worker->PreamblePeer.run(); });
568  }
569 
570  return ASTWorkerHandle(std::move(Worker));
571 }
572 
573 ASTWorker::ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB,
574  TUScheduler::ASTCache &LRUCache, Semaphore &Barrier,
575  bool RunSync, const TUScheduler::Options &Opts,
576  ParsingCallbacks &Callbacks)
577  : IdleASTs(LRUCache), RunSync(RunSync), UpdateDebounce(Opts.UpdateDebounce),
578  FileName(FileName), ContextProvider(Opts.ContextProvider), CDB(CDB),
579  Callbacks(Callbacks), Barrier(Barrier), Done(false),
580  Status(FileName, Callbacks),
581  PreamblePeer(FileName, Callbacks, Opts.StorePreamblesInMemory,
582  RunSync || !Opts.AsyncPreambleBuilds, Status, *this) {
583  // Set a fallback command because compile command can be accessed before
584  // `Inputs` is initialized. Other fields are only used after initialization
585  // from client inputs.
586  FileInputs.CompileCommand = CDB.getFallbackCommand(FileName);
587 }
588 
589 ASTWorker::~ASTWorker() {
590  // Make sure we remove the cached AST, if any.
591  IdleASTs.take(this);
592 #ifndef NDEBUG
593  std::lock_guard<std::mutex> Lock(Mutex);
594  assert(Done && "handle was not destroyed");
595  assert(Requests.empty() && !CurrentRequest &&
596  "unprocessed requests when destroying ASTWorker");
597 #endif
598 }
599 
600 void ASTWorker::update(ParseInputs Inputs, WantDiagnostics WantDiags) {
601  std::string TaskName = llvm::formatv("Update ({0})", Inputs.Version);
602  auto Task = [=]() mutable {
603  // Get the actual command as `Inputs` does not have a command.
604  // FIXME: some build systems like Bazel will take time to preparing
605  // environment to build the file, it would be nice if we could emit a
606  // "PreparingBuild" status to inform users, it is non-trivial given the
607  // current implementation.
608  if (auto Cmd = CDB.getCompileCommand(FileName))
609  Inputs.CompileCommand = *Cmd;
610  else
611  // FIXME: consider using old command if it's not a fallback one.
612  Inputs.CompileCommand = CDB.getFallbackCommand(FileName);
613 
614  bool InputsAreTheSame =
615  std::tie(FileInputs.CompileCommand, FileInputs.Contents) ==
616  std::tie(Inputs.CompileCommand, Inputs.Contents);
617  // Cached AST is invalidated.
618  if (!InputsAreTheSame) {
619  IdleASTs.take(this);
620  RanASTCallback = false;
621  }
622 
623  // Update current inputs so that subsequent reads can see them.
624  {
625  std::lock_guard<std::mutex> Lock(Mutex);
626  FileInputs = Inputs;
627  }
628 
629  log("ASTWorker building file {0} version {1} with command {2}\n[{3}]\n{4}",
630  FileName, Inputs.Version, Inputs.CompileCommand.Heuristic,
631  Inputs.CompileCommand.Directory,
632  llvm::join(Inputs.CompileCommand.CommandLine, " "));
633 
634  StoreDiags CompilerInvocationDiagConsumer;
635  std::vector<std::string> CC1Args;
636  std::unique_ptr<CompilerInvocation> Invocation = buildCompilerInvocation(
637  Inputs, CompilerInvocationDiagConsumer, &CC1Args);
638  // Log cc1 args even (especially!) if creating invocation failed.
639  if (!CC1Args.empty())
640  vlog("Driver produced command: cc1 {0}", llvm::join(CC1Args, " "));
641  std::vector<Diag> CompilerInvocationDiags =
642  CompilerInvocationDiagConsumer.take();
643  if (!Invocation) {
644  elog("Could not build CompilerInvocation for file {0}", FileName);
645  // Remove the old AST if it's still in cache.
646  IdleASTs.take(this);
647  RanASTCallback = false;
648  // Report the diagnostics we collected when parsing the command line.
649  Callbacks.onFailedAST(FileName, Inputs.Version,
650  std::move(CompilerInvocationDiags),
651  [&](llvm::function_ref<void()> Publish) {
652  // Ensure we only publish results from the worker
653  // if the file was not removed, making sure there
654  // are not race conditions.
655  std::lock_guard<std::mutex> Lock(PublishMu);
656  if (CanPublishResults)
657  Publish();
658  });
659  // Note that this might throw away a stale preamble that might still be
660  // useful, but this is how we communicate a build error.
661  LatestPreamble.emplace();
662  // Make sure anyone waiting for the preamble gets notified it could not be
663  // built.
664  PreambleCV.notify_all();
665  return;
666  }
667 
668  PreamblePeer.update(std::move(Invocation), std::move(Inputs),
669  std::move(CompilerInvocationDiags), WantDiags);
670  std::unique_lock<std::mutex> Lock(Mutex);
671  PreambleCV.wait(Lock, [this] {
672  // Block until we reiceve a preamble request, unless a preamble already
673  // exists, as patching an empty preamble would imply rebuilding it from
674  // scratch.
675  // We block here instead of the consumer to prevent any deadlocks. Since
676  // LatestPreamble is only populated by ASTWorker thread.
677  return LatestPreamble || !PreambleRequests.empty() || Done;
678  });
679  return;
680  };
681  startTask(TaskName, std::move(Task), WantDiags, TUScheduler::NoInvalidation);
682 }
683 
684 void ASTWorker::runWithAST(
685  llvm::StringRef Name,
686  llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action,
687  TUScheduler::ASTActionInvalidation Invalidation) {
688  // Tracks ast cache accesses for read operations.
689  static constexpr trace::Metric ASTAccessForRead(
690  "ast_access_read", trace::Metric::Counter, "result");
691  auto Task = [=, Action = std::move(Action)]() mutable {
692  if (auto Reason = isCancelled())
693  return Action(llvm::make_error<CancelledError>(Reason));
694  llvm::Optional<std::unique_ptr<ParsedAST>> AST =
695  IdleASTs.take(this, &ASTAccessForRead);
696  if (!AST) {
697  StoreDiags CompilerInvocationDiagConsumer;
698  std::unique_ptr<CompilerInvocation> Invocation =
699  buildCompilerInvocation(FileInputs, CompilerInvocationDiagConsumer);
700  // Try rebuilding the AST.
701  vlog("ASTWorker rebuilding evicted AST to run {0}: {1} version {2}", Name,
702  FileName, FileInputs.Version);
703  // FIXME: We might need to build a patched ast once preamble thread starts
704  // running async. Currently getPossiblyStalePreamble below will always
705  // return a compatible preamble as ASTWorker::update blocks.
706  llvm::Optional<ParsedAST> NewAST;
707  if (Invocation) {
708  NewAST = ParsedAST::build(FileName, FileInputs, std::move(Invocation),
709  CompilerInvocationDiagConsumer.take(),
710  getPossiblyStalePreamble());
711  ++ASTBuildCount;
712  }
713  AST = NewAST ? std::make_unique<ParsedAST>(std::move(*NewAST)) : nullptr;
714  }
715  // Make sure we put the AST back into the LRU cache.
716  auto _ = llvm::make_scope_exit(
717  [&AST, this]() { IdleASTs.put(this, std::move(*AST)); });
718  // Run the user-provided action.
719  if (!*AST)
720  return Action(llvm::make_error<llvm::StringError>(
721  "invalid AST", llvm::errc::invalid_argument));
722  vlog("ASTWorker running {0} on version {2} of {1}", Name, FileName,
723  FileInputs.Version);
724  Action(InputsAndAST{FileInputs, **AST});
725  };
726  startTask(Name, std::move(Task), /*UpdateType=*/None, Invalidation);
727 }
728 
729 void PreambleThread::build(Request Req) {
730  assert(Req.CI && "Got preamble request with null compiler invocation");
731  const ParseInputs &Inputs = Req.Inputs;
732 
733  Status.update([&](TUStatus &Status) {
734  Status.PreambleActivity = PreambleAction::Building;
735  });
736  auto _ = llvm::make_scope_exit([this, &Req] {
737  ASTPeer.updatePreamble(std::move(Req.CI), std::move(Req.Inputs),
738  LatestBuild, std::move(Req.CIDiags),
739  std::move(Req.WantDiags));
740  });
741 
742  if (!LatestBuild || Inputs.ForceRebuild) {
743  vlog("Building first preamble for {0} version {1}", FileName,
744  Inputs.Version);
745  } else if (isPreambleCompatible(*LatestBuild, Inputs, FileName, *Req.CI)) {
746  vlog("Reusing preamble version {0} for version {1} of {2}",
747  LatestBuild->Version, Inputs.Version, FileName);
748  return;
749  } else {
750  vlog("Rebuilding invalidated preamble for {0} version {1} (previous was "
751  "version {2})",
752  FileName, Inputs.Version, LatestBuild->Version);
753  }
754 
755  LatestBuild = clang::clangd::buildPreamble(
756  FileName, *Req.CI, Inputs, StoreInMemory,
757  [this, Version(Inputs.Version)](ASTContext &Ctx,
758  std::shared_ptr<clang::Preprocessor> PP,
759  const CanonicalIncludes &CanonIncludes) {
760  Callbacks.onPreambleAST(FileName, Version, Ctx, std::move(PP),
761  CanonIncludes);
762  });
763 }
764 
765 void ASTWorker::updatePreamble(std::unique_ptr<CompilerInvocation> CI,
766  ParseInputs PI,
767  std::shared_ptr<const PreambleData> Preamble,
768  std::vector<Diag> CIDiags,
769  WantDiagnostics WantDiags) {
770  std::string TaskName = llvm::formatv("Build AST for ({0})", PI.Version);
771  // Store preamble and build diagnostics with new preamble if requested.
772  auto Task = [this, Preamble = std::move(Preamble), CI = std::move(CI),
773  PI = std::move(PI), CIDiags = std::move(CIDiags),
774  WantDiags = std::move(WantDiags)]() mutable {
775  // Update the preamble inside ASTWorker queue to ensure atomicity. As a task
776  // running inside ASTWorker assumes internals won't change until it
777  // finishes.
778  if (!LatestPreamble || Preamble != *LatestPreamble) {
779  ++PreambleBuildCount;
780  // Cached AST is no longer valid.
781  IdleASTs.take(this);
782  RanASTCallback = false;
783  std::lock_guard<std::mutex> Lock(Mutex);
784  // LatestPreamble might be the last reference to old preamble, do not
785  // trigger destructor while holding the lock.
786  if (LatestPreamble)
787  std::swap(*LatestPreamble, Preamble);
788  else
789  LatestPreamble = std::move(Preamble);
790  }
791  // Notify anyone waiting for a preamble.
792  PreambleCV.notify_all();
793  // Give up our ownership to old preamble before starting expensive AST
794  // build.
795  Preamble.reset();
796  // We only need to build the AST if diagnostics were requested.
797  if (WantDiags == WantDiagnostics::No)
798  return;
799  // Report diagnostics with the new preamble to ensure progress. Otherwise
800  // diagnostics might get stale indefinitely if user keeps invalidating the
801  // preamble.
802  generateDiagnostics(std::move(CI), std::move(PI), std::move(CIDiags));
803  };
804  if (RunSync) {
805  Task();
806  return;
807  }
808  {
809  std::lock_guard<std::mutex> Lock(Mutex);
810  PreambleRequests.push({std::move(Task), std::move(TaskName),
811  steady_clock::now(), Context::current().clone(),
813  }
814  PreambleCV.notify_all();
815  RequestsCV.notify_all();
816 }
817 
818 void ASTWorker::generateDiagnostics(
819  std::unique_ptr<CompilerInvocation> Invocation, ParseInputs Inputs,
820  std::vector<Diag> CIDiags) {
821  // Tracks ast cache accesses for publishing diags.
822  static constexpr trace::Metric ASTAccessForDiag(
823  "ast_access_diag", trace::Metric::Counter, "result");
824  assert(Invocation);
825  assert(LatestPreamble);
826  // No need to rebuild the AST if we won't send the diagnostics.
827  {
828  std::lock_guard<std::mutex> Lock(PublishMu);
829  if (!CanPublishResults)
830  return;
831  }
832  // Used to check whether we can update AST cache.
833  bool InputsAreLatest =
834  std::tie(FileInputs.CompileCommand, FileInputs.Contents) ==
835  std::tie(Inputs.CompileCommand, Inputs.Contents);
836  // Take a shortcut and don't report the diagnostics, since they should be the
837  // same. All the clients should handle the lack of OnUpdated() call anyway to
838  // handle empty result from buildAST.
839  // FIXME: the AST could actually change if non-preamble includes changed,
840  // but we choose to ignore it.
841  if (InputsAreLatest && RanASTCallback)
842  return;
843 
844  // Get the AST for diagnostics, either build it or use the cached one.
845  std::string TaskName = llvm::formatv("Build AST ({0})", Inputs.Version);
846  Status.update([&](TUStatus &Status) {
847  Status.ASTActivity.K = ASTAction::Building;
848  Status.ASTActivity.Name = std::move(TaskName);
849  });
850  // We might be able to reuse the last we've built for a read request.
851  // FIXME: It might be better to not reuse this AST. That way queued AST builds
852  // won't be required for diags.
853  llvm::Optional<std::unique_ptr<ParsedAST>> AST =
854  IdleASTs.take(this, &ASTAccessForDiag);
855  if (!AST || !InputsAreLatest) {
856  auto RebuildStartTime = DebouncePolicy::clock::now();
857  llvm::Optional<ParsedAST> NewAST = ParsedAST::build(
858  FileName, Inputs, std::move(Invocation), CIDiags, *LatestPreamble);
859  auto RebuildDuration = DebouncePolicy::clock::now() - RebuildStartTime;
860  ++ASTBuildCount;
861  // Try to record the AST-build time, to inform future update debouncing.
862  // This is best-effort only: if the lock is held, don't bother.
863  std::unique_lock<std::mutex> Lock(Mutex, std::try_to_lock);
864  if (Lock.owns_lock()) {
865  // Do not let RebuildTimes grow beyond its small-size (i.e.
866  // capacity).
867  if (RebuildTimes.size() == RebuildTimes.capacity())
868  RebuildTimes.erase(RebuildTimes.begin());
869  RebuildTimes.push_back(RebuildDuration);
870  Lock.unlock();
871  }
872  Status.update([&](TUStatus &Status) {
873  Status.Details.ReuseAST = false;
874  Status.Details.BuildFailed = !NewAST.hasValue();
875  });
876  AST = NewAST ? std::make_unique<ParsedAST>(std::move(*NewAST)) : nullptr;
877  } else {
878  log("Skipping rebuild of the AST for {0}, inputs are the same.", FileName);
879  Status.update([](TUStatus &Status) {
880  Status.Details.ReuseAST = true;
881  Status.Details.BuildFailed = false;
882  });
883  }
884 
885  // Publish diagnostics.
886  auto RunPublish = [&](llvm::function_ref<void()> Publish) {
887  // Ensure we only publish results from the worker if the file was not
888  // removed, making sure there are not race conditions.
889  std::lock_guard<std::mutex> Lock(PublishMu);
890  if (CanPublishResults)
891  Publish();
892  };
893  if (*AST) {
894  trace::Span Span("Running main AST callback");
895  Callbacks.onMainAST(FileName, **AST, RunPublish);
896  } else {
897  // Failed to build the AST, at least report diagnostics from the
898  // command line if there were any.
899  // FIXME: we might have got more errors while trying to build the
900  // AST, surface them too.
901  Callbacks.onFailedAST(FileName, Inputs.Version, CIDiags, RunPublish);
902  }
903 
904  // AST might've been built for an older version of the source, as ASTWorker
905  // queue raced ahead while we were waiting on the preamble. In that case the
906  // queue can't reuse the AST.
907  if (InputsAreLatest) {
908  RanASTCallback = *AST != nullptr;
909  IdleASTs.put(this, std::move(*AST));
910  }
911 }
912 
913 std::shared_ptr<const PreambleData>
914 ASTWorker::getPossiblyStalePreamble() const {
915  std::lock_guard<std::mutex> Lock(Mutex);
916  return LatestPreamble ? *LatestPreamble : nullptr;
917 }
918 
919 void ASTWorker::waitForFirstPreamble() const {
920  std::unique_lock<std::mutex> Lock(Mutex);
921  PreambleCV.wait(Lock, [this] { return LatestPreamble.hasValue() || Done; });
922 }
923 
924 tooling::CompileCommand ASTWorker::getCurrentCompileCommand() const {
925  std::unique_lock<std::mutex> Lock(Mutex);
926  return FileInputs.CompileCommand;
927 }
928 
929 TUScheduler::FileStats ASTWorker::stats() const {
930  TUScheduler::FileStats Result;
931  Result.ASTBuilds = ASTBuildCount;
932  Result.PreambleBuilds = PreambleBuildCount;
933  // Note that we don't report the size of ASTs currently used for processing
934  // the in-flight requests. We used this information for debugging purposes
935  // only, so this should be fine.
936  Result.UsedBytes = IdleASTs.getUsedBytes(this);
937  if (auto Preamble = getPossiblyStalePreamble())
938  Result.UsedBytes += Preamble->Preamble.getSize();
939  return Result;
940 }
941 
942 bool ASTWorker::isASTCached() const { return IdleASTs.getUsedBytes(this) != 0; }
943 
944 void ASTWorker::stop() {
945  {
946  std::lock_guard<std::mutex> Lock(PublishMu);
947  CanPublishResults = false;
948  }
949  {
950  std::lock_guard<std::mutex> Lock(Mutex);
951  assert(!Done && "stop() called twice");
952  Done = true;
953  }
954  PreamblePeer.stop();
955  // We are no longer going to build any preambles, let the waiters know that.
956  PreambleCV.notify_all();
957  Status.stop();
958  RequestsCV.notify_all();
959 }
960 
961 void ASTWorker::startTask(llvm::StringRef Name,
962  llvm::unique_function<void()> Task,
963  llvm::Optional<WantDiagnostics> UpdateType,
964  TUScheduler::ASTActionInvalidation Invalidation) {
965  if (RunSync) {
966  assert(!Done && "running a task after stop()");
967  trace::Span Tracer(Name + ":" + llvm::sys::path::filename(FileName));
968  Task();
969  return;
970  }
971 
972  {
973  std::lock_guard<std::mutex> Lock(Mutex);
974  assert(!Done && "running a task after stop()");
975  // Cancel any requests invalidated by this request.
976  if (UpdateType) {
977  for (auto &R : llvm::reverse(Requests)) {
978  if (R.InvalidationPolicy == TUScheduler::InvalidateOnUpdate)
979  R.Invalidate();
980  if (R.UpdateType)
981  break; // Older requests were already invalidated by the older update.
982  }
983  }
984 
985  // Allow this request to be cancelled if invalidated.
986  Context Ctx = Context::current().derive(kFileBeingProcessed, FileName);
987  Canceler Invalidate = nullptr;
988  if (Invalidation) {
989  WithContext WC(std::move(Ctx));
990  std::tie(Ctx, Invalidate) = cancelableTask(
991  /*Reason=*/static_cast<int>(ErrorCode::ContentModified));
992  }
993  Requests.push_back({std::move(Task), std::string(Name), steady_clock::now(),
994  std::move(Ctx), UpdateType, Invalidation,
995  std::move(Invalidate)});
996  }
997  RequestsCV.notify_all();
998 }
999 
1000 void ASTWorker::run() {
1001  while (true) {
1002  {
1003  std::unique_lock<std::mutex> Lock(Mutex);
1004  assert(!CurrentRequest && "A task is already running, multiple workers?");
1005  for (auto Wait = scheduleLocked(); !Wait.expired();
1006  Wait = scheduleLocked()) {
1007  assert(PreambleRequests.empty() &&
1008  "Preamble updates should be scheduled immediately");
1009  if (Done) {
1010  if (Requests.empty())
1011  return;
1012  else // Even though Done is set, finish pending requests.
1013  break; // However, skip delays to shutdown fast.
1014  }
1015 
1016  // Tracing: we have a next request, attribute this sleep to it.
1017  llvm::Optional<WithContext> Ctx;
1018  llvm::Optional<trace::Span> Tracer;
1019  if (!Requests.empty()) {
1020  Ctx.emplace(Requests.front().Ctx.clone());
1021  Tracer.emplace("Debounce");
1022  SPAN_ATTACH(*Tracer, "next_request", Requests.front().Name);
1023  if (!(Wait == Deadline::infinity())) {
1024  Status.update([&](TUStatus &Status) {
1025  Status.ASTActivity.K = ASTAction::Queued;
1026  Status.ASTActivity.Name = Requests.front().Name;
1027  });
1028  SPAN_ATTACH(*Tracer, "sleep_ms",
1029  std::chrono::duration_cast<std::chrono::milliseconds>(
1030  Wait.time() - steady_clock::now())
1031  .count());
1032  }
1033  }
1034 
1035  wait(Lock, RequestsCV, Wait);
1036  }
1037  // Any request in ReceivedPreambles is at least as old as the
1038  // Requests.front(), so prefer them first to preserve LSP order.
1039  if (!PreambleRequests.empty()) {
1040  CurrentRequest = std::move(PreambleRequests.front());
1041  PreambleRequests.pop();
1042  } else {
1043  CurrentRequest = std::move(Requests.front());
1044  Requests.pop_front();
1045  }
1046  } // unlock Mutex
1047 
1048  // It is safe to perform reads to CurrentRequest without holding the lock as
1049  // only writer is also this thread.
1050  {
1051  std::unique_lock<Semaphore> Lock(Barrier, std::try_to_lock);
1052  if (!Lock.owns_lock()) {
1053  Status.update([&](TUStatus &Status) {
1054  Status.ASTActivity.K = ASTAction::Queued;
1055  Status.ASTActivity.Name = CurrentRequest->Name;
1056  });
1057  Lock.lock();
1058  }
1059  WithContext Guard(std::move(CurrentRequest->Ctx));
1060  trace::Span Tracer(CurrentRequest->Name);
1061  Status.update([&](TUStatus &Status) {
1062  Status.ASTActivity.K = ASTAction::RunningAction;
1063  Status.ASTActivity.Name = CurrentRequest->Name;
1064  });
1065  llvm::Optional<WithContext> WithProvidedContext;
1066  if (ContextProvider)
1067  WithProvidedContext.emplace(ContextProvider(FileName));
1068  CurrentRequest->Action();
1069  }
1070 
1071  bool IsEmpty = false;
1072  {
1073  std::lock_guard<std::mutex> Lock(Mutex);
1074  CurrentRequest.reset();
1075  IsEmpty = Requests.empty() && PreambleRequests.empty();
1076  }
1077  if (IsEmpty) {
1078  Status.update([&](TUStatus &Status) {
1079  Status.ASTActivity.K = ASTAction::Idle;
1080  Status.ASTActivity.Name = "";
1081  });
1082  }
1083  RequestsCV.notify_all();
1084  }
1085 }
1086 
1087 Deadline ASTWorker::scheduleLocked() {
1088  // Process new preambles immediately.
1089  if (!PreambleRequests.empty())
1090  return Deadline::zero();
1091  if (Requests.empty())
1092  return Deadline::infinity(); // Wait for new requests.
1093  // Handle cancelled requests first so the rest of the scheduler doesn't.
1094  for (auto I = Requests.begin(), E = Requests.end(); I != E; ++I) {
1095  if (!isCancelled(I->Ctx)) {
1096  // Cancellations after the first read don't affect current scheduling.
1097  if (I->UpdateType == None)
1098  break;
1099  continue;
1100  }
1101  // Cancelled reads are moved to the front of the queue and run immediately.
1102  if (I->UpdateType == None) {
1103  Request R = std::move(*I);
1104  Requests.erase(I);
1105  Requests.push_front(std::move(R));
1106  return Deadline::zero();
1107  }
1108  // Cancelled updates are downgraded to auto-diagnostics, and may be elided.
1109  if (I->UpdateType == WantDiagnostics::Yes)
1110  I->UpdateType = WantDiagnostics::Auto;
1111  }
1112 
1113  while (shouldSkipHeadLocked()) {
1114  vlog("ASTWorker skipping {0} for {1}", Requests.front().Name, FileName);
1115  Requests.pop_front();
1116  }
1117  assert(!Requests.empty() && "skipped the whole queue");
1118  // Some updates aren't dead yet, but never end up being used.
1119  // e.g. the first keystroke is live until obsoleted by the second.
1120  // We debounce "maybe-unused" writes, sleeping in case they become dead.
1121  // But don't delay reads (including updates where diagnostics are needed).
1122  for (const auto &R : Requests)
1123  if (R.UpdateType == None || R.UpdateType == WantDiagnostics::Yes)
1124  return Deadline::zero();
1125  // Front request needs to be debounced, so determine when we're ready.
1126  Deadline D(Requests.front().AddTime + UpdateDebounce.compute(RebuildTimes));
1127  return D;
1128 }
1129 
1130 // Returns true if Requests.front() is a dead update that can be skipped.
1131 bool ASTWorker::shouldSkipHeadLocked() const {
1132  assert(!Requests.empty());
1133  auto Next = Requests.begin();
1134  auto UpdateType = Next->UpdateType;
1135  if (!UpdateType) // Only skip updates.
1136  return false;
1137  ++Next;
1138  // An update is live if its AST might still be read.
1139  // That is, if it's not immediately followed by another update.
1140  if (Next == Requests.end() || !Next->UpdateType)
1141  return false;
1142  // The other way an update can be live is if its diagnostics might be used.
1143  switch (*UpdateType) {
1144  case WantDiagnostics::Yes:
1145  return false; // Always used.
1146  case WantDiagnostics::No:
1147  return true; // Always dead.
1148  case WantDiagnostics::Auto:
1149  // Used unless followed by an update that generates diagnostics.
1150  for (; Next != Requests.end(); ++Next)
1151  if (Next->UpdateType == WantDiagnostics::Yes ||
1152  Next->UpdateType == WantDiagnostics::Auto)
1153  return true; // Prefer later diagnostics.
1154  return false;
1155  }
1156  llvm_unreachable("Unknown WantDiagnostics");
1157 }
1158 
1159 bool ASTWorker::blockUntilIdle(Deadline Timeout) const {
1160  auto WaitUntilASTWorkerIsIdle = [&] {
1161  std::unique_lock<std::mutex> Lock(Mutex);
1162  return wait(Lock, RequestsCV, Timeout, [&] {
1163  return PreambleRequests.empty() && Requests.empty() && !CurrentRequest;
1164  });
1165  };
1166  // Make sure ASTWorker has processed all requests, which might issue new
1167  // updates to PreamblePeer.
1168  WaitUntilASTWorkerIsIdle();
1169  // Now that ASTWorker processed all requests, ensure PreamblePeer has served
1170  // all update requests. This might create new PreambleRequests for the
1171  // ASTWorker.
1172  PreamblePeer.blockUntilIdle(Timeout);
1173  assert(Requests.empty() &&
1174  "No new normal tasks can be scheduled concurrently with "
1175  "blockUntilIdle(): ASTWorker isn't threadsafe");
1176  // Finally make sure ASTWorker has processed all of the preamble updates.
1177  return WaitUntilASTWorkerIsIdle();
1178 }
1179 
1180 // Render a TUAction to a user-facing string representation.
1181 // TUAction represents clangd-internal states, we don't intend to expose them
1182 // to users (say C++ programmers) directly to avoid confusion, we use terms that
1183 // are familiar by C++ programmers.
1184 std::string renderTUAction(const PreambleAction PA, const ASTAction &AA) {
1185  llvm::SmallVector<std::string, 2> Result;
1186  switch (PA) {
1188  Result.push_back("parsing includes");
1189  break;
1190  case PreambleAction::Idle:
1191  // We handle idle specially below.
1192  break;
1193  }
1194  switch (AA.K) {
1195  case ASTAction::Queued:
1196  Result.push_back("file is queued");
1197  break;
1199  Result.push_back("running " + AA.Name);
1200  break;
1201  case ASTAction::Building:
1202  Result.push_back("parsing main file");
1203  break;
1204  case ASTAction::Idle:
1205  // We handle idle specially below.
1206  break;
1207  }
1208  if (Result.empty())
1209  return "idle";
1210  return llvm::join(Result, ",");
1211 }
1212 
1213 } // namespace
1214 
1216  return llvm::heavyweight_hardware_concurrency().compute_thread_count();
1217 }
1218 
1220  FileStatus FStatus;
1221  FStatus.uri = URIForFile::canonicalize(File, /*TUPath=*/File);
1222  FStatus.state = renderTUAction(PreambleActivity, ASTActivity);
1223  return FStatus;
1224 }
1225 
1227  /// Latest inputs, passed to TUScheduler::update().
1228  std::string Contents;
1229  ASTWorkerHandle Worker;
1230 };
1231 
1233  const Options &Opts,
1234  std::unique_ptr<ParsingCallbacks> Callbacks)
1235  : CDB(CDB), Opts(Opts),
1236  Callbacks(Callbacks ? move(Callbacks)
1237  : std::make_unique<ParsingCallbacks>()),
1238  Barrier(Opts.AsyncThreadsCount),
1239  IdleASTs(
1240  std::make_unique<ASTCache>(Opts.RetentionPolicy.MaxRetainedASTs)) {
1241  if (0 < Opts.AsyncThreadsCount) {
1242  PreambleTasks.emplace();
1243  WorkerThreads.emplace();
1244  }
1245 }
1246 
1248  // Notify all workers that they need to stop.
1249  Files.clear();
1250 
1251  // Wait for all in-flight tasks to finish.
1252  if (PreambleTasks)
1253  PreambleTasks->wait();
1254  if (WorkerThreads)
1255  WorkerThreads->wait();
1256 }
1257 
1259  for (auto &File : Files)
1260  if (!File.getValue()->Worker->blockUntilIdle(D))
1261  return false;
1262  if (PreambleTasks)
1263  if (!PreambleTasks->wait(D))
1264  return false;
1265  return true;
1266 }
1267 
1270  std::unique_ptr<FileData> &FD = Files[File];
1271  bool NewFile = FD == nullptr;
1272  if (!FD) {
1273  // Create a new worker to process the AST-related tasks.
1274  ASTWorkerHandle Worker =
1275  ASTWorker::create(File, CDB, *IdleASTs,
1276  WorkerThreads ? WorkerThreads.getPointer() : nullptr,
1277  Barrier, Opts, *Callbacks);
1278  FD = std::unique_ptr<FileData>(
1279  new FileData{Inputs.Contents, std::move(Worker)});
1280  } else {
1281  FD->Contents = Inputs.Contents;
1282  }
1283  FD->Worker->update(std::move(Inputs), WantDiags);
1284  return NewFile;
1285 }
1286 
1288  bool Removed = Files.erase(File);
1289  if (!Removed)
1290  elog("Trying to remove file from TUScheduler that is not tracked: {0}",
1291  File);
1292 }
1293 
1294 llvm::StringMap<std::string> TUScheduler::getAllFileContents() const {
1295  llvm::StringMap<std::string> Results;
1296  for (auto &It : Files)
1297  Results.try_emplace(It.getKey(), It.getValue()->Contents);
1298  return Results;
1299 }
1300 
1301 void TUScheduler::run(llvm::StringRef Name, llvm::StringRef Path,
1302  llvm::unique_function<void()> Action) {
1303  if (!PreambleTasks)
1304  return Action();
1305  PreambleTasks->runAsync(Name, [this, Ctx = Context::current().clone(),
1306  Path(Path.str()),
1307  Action = std::move(Action)]() mutable {
1308  std::lock_guard<Semaphore> BarrierLock(Barrier);
1309  WithContext WC(std::move(Ctx));
1310  llvm::Optional<WithContext> WithProvidedContext;
1311  if (Opts.ContextProvider)
1312  WithProvidedContext.emplace(Opts.ContextProvider(Path));
1313  Action();
1314  });
1315 }
1316 
1318  llvm::StringRef Name, PathRef File,
1319  llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action,
1320  TUScheduler::ASTActionInvalidation Invalidation) {
1321  auto It = Files.find(File);
1322  if (It == Files.end()) {
1323  Action(llvm::make_error<LSPError>(
1324  "trying to get AST for non-added document", ErrorCode::InvalidParams));
1325  return;
1326  }
1327 
1328  It->second->Worker->runWithAST(Name, std::move(Action), Invalidation);
1329 }
1330 
1331 void TUScheduler::runWithPreamble(llvm::StringRef Name, PathRef File,
1332  PreambleConsistency Consistency,
1334  auto It = Files.find(File);
1335  if (It == Files.end()) {
1336  Action(llvm::make_error<LSPError>(
1337  "trying to get preamble for non-added document",
1339  return;
1340  }
1341 
1342  if (!PreambleTasks) {
1343  trace::Span Tracer(Name);
1344  SPAN_ATTACH(Tracer, "file", File);
1345  std::shared_ptr<const PreambleData> Preamble =
1346  It->second->Worker->getPossiblyStalePreamble();
1347  Action(InputsAndPreamble{It->second->Contents,
1348  It->second->Worker->getCurrentCompileCommand(),
1349  Preamble.get()});
1350  return;
1351  }
1352 
1353  std::shared_ptr<const ASTWorker> Worker = It->second->Worker.lock();
1354  auto Task =
1355  [Worker, Consistency, Name = Name.str(), File = File.str(),
1356  Contents = It->second->Contents,
1357  Command = Worker->getCurrentCompileCommand(),
1358  Ctx = Context::current().derive(kFileBeingProcessed, std::string(File)),
1359  Action = std::move(Action), this]() mutable {
1360  std::shared_ptr<const PreambleData> Preamble;
1361  if (Consistency == PreambleConsistency::Stale) {
1362  // Wait until the preamble is built for the first time, if preamble
1363  // is required. This avoids extra work of processing the preamble
1364  // headers in parallel multiple times.
1365  Worker->waitForFirstPreamble();
1366  }
1367  Preamble = Worker->getPossiblyStalePreamble();
1368 
1369  std::lock_guard<Semaphore> BarrierLock(Barrier);
1370  WithContext Guard(std::move(Ctx));
1371  trace::Span Tracer(Name);
1372  SPAN_ATTACH(Tracer, "file", File);
1373  llvm::Optional<WithContext> WithProvidedContext;
1374  if (Opts.ContextProvider)
1375  WithProvidedContext.emplace(Opts.ContextProvider(File));
1376  Action(InputsAndPreamble{Contents, Command, Preamble.get()});
1377  };
1378 
1379  PreambleTasks->runAsync("task:" + llvm::sys::path::filename(File),
1380  std::move(Task));
1381 }
1382 
1383 llvm::StringMap<TUScheduler::FileStats> TUScheduler::fileStats() const {
1384  llvm::StringMap<TUScheduler::FileStats> Result;
1385  for (const auto &PathAndFile : Files)
1386  Result.try_emplace(PathAndFile.first(),
1387  PathAndFile.second->Worker->stats());
1388  return Result;
1389 }
1390 
1391 std::vector<Path> TUScheduler::getFilesWithCachedAST() const {
1392  std::vector<Path> Result;
1393  for (auto &&PathAndFile : Files) {
1394  if (!PathAndFile.second->Worker->isASTCached())
1395  continue;
1396  Result.push_back(std::string(PathAndFile.first()));
1397  }
1398  return Result;
1399 }
1400 
1401 DebouncePolicy::clock::duration
1402 DebouncePolicy::compute(llvm::ArrayRef<clock::duration> History) const {
1403  assert(Min <= Max && "Invalid policy");
1404  if (History.empty())
1405  return Max; // Arbitrary.
1406 
1407  // Base the result on the median rebuild.
1408  // nth_element needs a mutable array, take the chance to bound the data size.
1409  History = History.take_back(15);
1410  llvm::SmallVector<clock::duration, 15> Recent(History.begin(), History.end());
1411  auto Median = Recent.begin() + Recent.size() / 2;
1412  std::nth_element(Recent.begin(), Median, Recent.end());
1413 
1414  clock::duration Target =
1415  std::chrono::duration_cast<clock::duration>(RebuildRatio * *Median);
1416  if (Target > Max)
1417  return Max;
1418  if (Target < Min)
1419  return Min;
1420  return Target;
1421 }
1422 
1424  DebouncePolicy P;
1425  P.Min = P.Max = T;
1426  return P;
1427 }
1428 
1429 } // namespace clangd
1430 } // namespace clang
PreambleConsistency
Controls whether preamble reads wait for the preamble to be up-to-date.
Definition: TUScheduler.h:269
WantDiagnostics
Determines whether diagnostics should be generated for a file snapshot.
Definition: TUScheduler.h:48
Diagnostics must be generated for this snapshot.
std::function< void()> Canceler
A canceller requests cancellation of a task, when called.
Definition: Cancellation.h:70
FileStatus render(PathRef File) const
Serialize this to an LSP file status item.
static llvm::Optional< llvm::StringRef > getFileBeingProcessedInContext()
bool blockUntilIdle(Deadline D) const
Wait until there are no scheduled or running tasks.
llvm::StringMap< FileStats > fileStats() const
Returns resources used for each of the currently open files.
void remove(PathRef File)
Remove File from the list of tracked files and schedule removal of its resources. ...
clock::duration Min
The minimum time that we always debounce for.
Definition: TUScheduler.h:73
ParseInputs Inputs
std::string state
The human-readable string presents the current state of the file, can be shown in the UI (e...
Definition: Protocol.h:1356
PreambleAction PreambleActivity
Definition: TUScheduler.h:118
llvm::StringRef PathRef
A typedef to represent a ref to file path.
Definition: Path.h:23
std::vector< CodeCompletionResult > Results
Values in a Context are indexed by typed keys.
Definition: Context.h:40
llvm::unique_function< void(llvm::Expected< T >)> Callback
A Callback<T> is a void function that accepts Expected<T>.
Definition: Function.h:28
TUScheduler::ASTActionInvalidation InvalidationPolicy
Documents should not be synced at all.
void run(llvm::StringRef Name, llvm::StringRef Path, llvm::unique_function< void()> Action)
Schedule an async task with no dependencies.
clock::duration Max
The maximum time we may debounce for.
Definition: TUScheduler.h:75
URIForFile uri
The text document&#39;s URI.
Definition: Protocol.h:1353
unsigned AsyncThreadsCount
Number of concurrent actions.
Definition: TUScheduler.h:183
void vlog(const char *Fmt, Ts &&... Vals)
Definition: Logger.h:67
bool update(PathRef File, ParseInputs Inputs, WantDiagnostics WD)
Schedule an update for File.
void elog(const char *Fmt, Ts &&... Vals)
Definition: Logger.h:56
virtual void onFileUpdated(PathRef File, const TUStatus &Status)
Called whenever the TU status is updated.
Definition: TUScheduler.h:167
TUScheduler(const GlobalCompilationDatabase &CDB, const Options &Opts, std::unique_ptr< ParsingCallbacks > ASTCallbacks=nullptr)
llvm::StringRef Contents
std::unique_ptr< CompilerInvocation > CI
static DebouncePolicy fixed(clock::duration)
A policy that always returns the same duration, useful for tests.
const PreambleData & Preamble
Provides compilation arguments used for parsing C and C++ files.
Represents measurements of clangd events, e.g.
Definition: Trace.h:38
std::shared_ptr< const PreambleData > buildPreamble(PathRef FileName, CompilerInvocation CI, const ParseInputs &Inputs, bool StoreInMemory, PreambleParsedCallback PreambleCallback)
Build a preamble for the new inputs unless an old one can be reused.
Definition: Preamble.cpp:321
void runWithAST(llvm::StringRef Name, PathRef File, Callback< InputsAndAST > Action, ASTActionInvalidation=NoInvalidation)
Schedule an async read of the AST.
Context Ctx
An aggregate number whose rate of change over time is meaningful.
Definition: Trace.h:46
std::pair< Context, Canceler > cancelableTask(int Reason)
Defines a new task whose cancellation may be requested.
Context clone() const
Clone this context object.
Definition: Context.cpp:20
clock::duration compute(llvm::ArrayRef< clock::duration > History) const
Compute the time to debounce based on this policy and recent build times.
llvm::Optional< WantDiagnostics > UpdateType
static Deadline infinity()
Definition: Threading.h:63
llvm::unique_function< void()> Action
void log(const char *Fmt, Ts &&... Vals)
Definition: Logger.h:62
llvm::Optional< std::unique_ptr< ParsedAST > > take(Key K, const trace::Metric *AccessMetric=nullptr)
Returns the cached value for K, or llvm::None if the value is not in the cache anymore.
ASTActionInvalidation
Defines how a runWithAST action is implicitly cancelled by other actions.
Definition: TUScheduler.h:246
void put(Key K, std::unique_ptr< ParsedAST > V)
Store the value in the pool, possibly removing the last used AST.
std::string Path
A typedef to represent a file path.
Definition: Path.h:20
static const Context & current()
Returns the context for the current thread, creating it if needed.
Definition: Context.cpp:27
#define dlog(...)
Definition: Logger.h:72
static URIForFile canonicalize(llvm::StringRef AbsPath, llvm::StringRef TUPath)
Canonicalizes AbsPath via URI.
Definition: Protocol.cpp:33
std::vector< Diag > CIDiags
void runWithPreamble(llvm::StringRef Name, PathRef File, PreambleConsistency Consistency, Callback< InputsAndPreamble > Action)
Schedule an async read of the preamble.
std::vector< Path > getFilesWithCachedAST() const
Returns a list of files with ASTs currently stored in memory.
PathRef FileName
void wait(std::unique_lock< std::mutex > &Lock, std::condition_variable &CV, Deadline D)
Wait once on CV for the specified duration.
Definition: Threading.cpp:110
std::string Name
unsigned getDefaultAsyncThreadsCount()
Returns a number of a default async threads to use for TUScheduler.
WithContext replaces Context::current() with a provided scope.
Definition: Context.h:189
std::string Contents
Latest inputs, passed to TUScheduler::update().
std::function< Context(PathRef)> ContextProvider
Used to create a context that wraps each single operation.
Definition: TUScheduler.h:202
Information required to run clang, e.g. to parse AST or do code completion.
Definition: Compiler.h:47
ASTCache(unsigned MaxRetainedASTs)
WantDiagnostics WantDiags
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
static Deadline zero()
Definition: Threading.h:62
Context derive(const Key< Type > &Key, typename std::decay< Type >::type Value) const &
Derives a child context It is safe to move or destroy a parent context after calling derive()...
Definition: Context.h:121
The request will run unless explicitly cancelled.
Definition: TUScheduler.h:248
std::unique_ptr< trace::EventTracer > Tracer
Definition: TraceTests.cpp:163
steady_clock::time_point AddTime
std::unique_ptr< CompilerInvocation > buildCompilerInvocation(const ParseInputs &Inputs, clang::DiagnosticConsumer &D, std::vector< std::string > *CC1Args)
Builds compiler invocation that could be used to build AST or preamble.
Definition: Compiler.cpp:45
static clang::clangd::Key< std::string > kFileBeingProcessed
Definition: TUScheduler.cpp:98
A point in time we can wait for.
Definition: Threading.h:58
const Expr * E
Clangd extension: indicates the current state of the file in clangd, sent from server via the textDoc...
Definition: Protocol.h:1351
static llvm::Optional< ParsedAST > build(llvm::StringRef Filename, const ParseInputs &Inputs, std::unique_ptr< clang::CompilerInvocation > CI, llvm::ArrayRef< Diag > CompilerInvocationDiags, std::shared_ptr< const PreambleData > Preamble)
Attempts to run Clang and store the parsed AST.
Definition: ParsedAST.cpp:246
static std::string join(ArrayRef< SpecialMemberFunctionsCheck::SpecialMemberFunctionKind > SMFS, llvm::StringRef AndOr)
The request will be implicitly cancelled by a subsequent update().
Definition: TUScheduler.h:253
An LRU cache of idle ASTs.
bool isPreambleCompatible(const PreambleData &Preamble, const ParseInputs &Inputs, PathRef FileName, const CompilerInvocation &CI)
Returns true if Preamble is reusable for Inputs.
Definition: Preamble.cpp:377
Records an event whose duration is the lifetime of the Span object.
Definition: Trace.h:135
Clangd may wait after an update to see if another one comes along.
Definition: TUScheduler.h:69
#define SPAN_ATTACH(S, Name, Expr)
Attach a key-value pair to a Span event.
Definition: Trace.h:154
Diagnostics must not be generated for this snapshot.
llvm::StringMap< std::string > getAllFileContents() const
Returns a snapshot of all file buffer contents, per last update().
std::size_t getUsedBytes(Key K)
Returns result of getUsedBytes() for the AST cached by K.
int isCancelled(const Context &Ctx)
If the current context is within a cancelled task, returns the reason.
Canceler Invalidate