clang-tools  16.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 "CompileCommands.h"
51 #include "Compiler.h"
52 #include "Diagnostics.h"
54 #include "ParsedAST.h"
55 #include "Preamble.h"
57 #include "support/Cancellation.h"
58 #include "support/Context.h"
59 #include "support/Logger.h"
60 #include "support/MemoryTree.h"
61 #include "support/Path.h"
63 #include "support/Threading.h"
64 #include "support/Trace.h"
65 #include "clang/Frontend/CompilerInvocation.h"
66 #include "clang/Tooling/CompilationDatabase.h"
67 #include "llvm/ADT/FunctionExtras.h"
68 #include "llvm/ADT/None.h"
69 #include "llvm/ADT/Optional.h"
70 #include "llvm/ADT/STLExtras.h"
71 #include "llvm/ADT/ScopeExit.h"
72 #include "llvm/ADT/SmallVector.h"
73 #include "llvm/ADT/StringExtras.h"
74 #include "llvm/ADT/StringRef.h"
75 #include "llvm/Support/Allocator.h"
76 #include "llvm/Support/Errc.h"
77 #include "llvm/Support/ErrorHandling.h"
78 #include "llvm/Support/FormatVariadic.h"
79 #include "llvm/Support/Path.h"
80 #include "llvm/Support/Threading.h"
81 #include "llvm/Support/raw_ostream.h"
82 #include <algorithm>
83 #include <atomic>
84 #include <chrono>
85 #include <condition_variable>
86 #include <functional>
87 #include <memory>
88 #include <mutex>
89 #include <queue>
90 #include <string>
91 #include <thread>
92 #include <type_traits>
93 #include <utility>
94 #include <vector>
95 
96 namespace clang {
97 namespace clangd {
98 using std::chrono::steady_clock;
99 
100 namespace {
101 // Tracks latency (in seconds) of FS operations done during a preamble build.
102 // build_type allows to split by expected VFS cache state (cold on first
103 // preamble, somewhat warm after that when building first preamble for new file,
104 // likely ~everything cached on preamble rebuild.
105 constexpr trace::Metric
106  PreambleBuildFilesystemLatency("preamble_fs_latency",
107  trace::Metric::Distribution, "build_type");
108 // Tracks latency of FS operations done during a preamble build as a ratio of
109 // preamble build time. build_type is same as above.
110 constexpr trace::Metric PreambleBuildFilesystemLatencyRatio(
111  "preamble_fs_latency_ratio", trace::Metric::Distribution, "build_type");
112 
113 constexpr trace::Metric PreambleBuildSize("preamble_build_size",
115 constexpr trace::Metric PreambleSerializedSize("preamble_serialized_size",
117 
118 void reportPreambleBuild(const PreambleBuildStats &Stats,
119  bool IsFirstPreamble) {
120  auto RecordWithLabel = [&Stats](llvm::StringRef Label) {
121  PreambleBuildFilesystemLatency.record(Stats.FileSystemTime, Label);
122  if (Stats.TotalBuildTime > 0) // Avoid division by zero.
123  PreambleBuildFilesystemLatencyRatio.record(
124  Stats.FileSystemTime / Stats.TotalBuildTime, Label);
125  };
126 
127  static llvm::once_flag OnceFlag;
128  llvm::call_once(OnceFlag, [&] { RecordWithLabel("first_build"); });
129  RecordWithLabel(IsFirstPreamble ? "first_build_for_file" : "rebuild");
130 
131  PreambleBuildSize.record(Stats.BuildSize);
132  PreambleSerializedSize.record(Stats.SerializedSize);
133 }
134 
135 class ASTWorker;
136 } // namespace
137 
139 
140 llvm::Optional<llvm::StringRef> TUScheduler::getFileBeingProcessedInContext() {
141  if (auto *File = Context::current().get(FileBeingProcessed))
142  return llvm::StringRef(*File);
143  return None;
144 }
145 
146 /// An LRU cache of idle ASTs.
147 /// Because we want to limit the overall number of these we retain, the cache
148 /// owns ASTs (and may evict them) while their workers are idle.
149 /// Workers borrow ASTs when active, and return them when done.
151 public:
152  using Key = const ASTWorker *;
153 
154  ASTCache(unsigned MaxRetainedASTs) : MaxRetainedASTs(MaxRetainedASTs) {}
155 
156  /// Returns result of getUsedBytes() for the AST cached by \p K.
157  /// If no AST is cached, 0 is returned.
158  std::size_t getUsedBytes(Key K) {
159  std::lock_guard<std::mutex> Lock(Mut);
160  auto It = findByKey(K);
161  if (It == LRU.end() || !It->second)
162  return 0;
163  return It->second->getUsedBytes();
164  }
165 
166  /// Store the value in the pool, possibly removing the last used AST.
167  /// The value should not be in the pool when this function is called.
168  void put(Key K, std::unique_ptr<ParsedAST> V) {
169  std::unique_lock<std::mutex> Lock(Mut);
170  assert(findByKey(K) == LRU.end());
171 
172  LRU.insert(LRU.begin(), {K, std::move(V)});
173  if (LRU.size() <= MaxRetainedASTs)
174  return;
175  // We're past the limit, remove the last element.
176  std::unique_ptr<ParsedAST> ForCleanup = std::move(LRU.back().second);
177  LRU.pop_back();
178  // Run the expensive destructor outside the lock.
179  Lock.unlock();
180  ForCleanup.reset();
181  }
182 
183  /// Returns the cached value for \p K, or llvm::None if the value is not in
184  /// the cache anymore. If nullptr was cached for \p K, this function will
185  /// return a null unique_ptr wrapped into an optional.
186  /// If \p AccessMetric is set records whether there was a hit or miss.
187  llvm::Optional<std::unique_ptr<ParsedAST>>
188  take(Key K, const trace::Metric *AccessMetric = nullptr) {
189  // Record metric after unlocking the mutex.
190  std::unique_lock<std::mutex> Lock(Mut);
191  auto Existing = findByKey(K);
192  if (Existing == LRU.end()) {
193  if (AccessMetric)
194  AccessMetric->record(1, "miss");
195  return None;
196  }
197  if (AccessMetric)
198  AccessMetric->record(1, "hit");
199  std::unique_ptr<ParsedAST> V = std::move(Existing->second);
200  LRU.erase(Existing);
201  // GCC 4.8 fails to compile `return V;`, as it tries to call the copy
202  // constructor of unique_ptr, so we call the move ctor explicitly to avoid
203  // this miscompile.
204  return llvm::Optional<std::unique_ptr<ParsedAST>>(std::move(V));
205  }
206 
207 private:
208  using KVPair = std::pair<Key, std::unique_ptr<ParsedAST>>;
209 
210  std::vector<KVPair>::iterator findByKey(Key K) {
211  return llvm::find_if(LRU, [K](const KVPair &P) { return P.first == K; });
212  }
213 
214  std::mutex Mut;
215  unsigned MaxRetainedASTs;
216  /// Items sorted in LRU order, i.e. first item is the most recently accessed
217  /// one.
218  std::vector<KVPair> LRU; /* GUARDED_BY(Mut) */
219 };
220 
221 /// A map from header files to an opened "proxy" file that includes them.
222 /// If you open the header, the compile command from the proxy file is used.
223 ///
224 /// This inclusion information could also naturally live in the index, but there
225 /// are advantages to using open files instead:
226 /// - it's easier to achieve a *stable* choice of proxy, which is important
227 /// to avoid invalidating the preamble
228 /// - context-sensitive flags for libraries with multiple configurations
229 /// (e.g. C++ stdlib sensitivity to -std version)
230 /// - predictable behavior, e.g. guarantees that go-to-def landing on a header
231 /// will have a suitable command available
232 /// - fewer scaling problems to solve (project include graphs are big!)
233 ///
234 /// Implementation details:
235 /// - We only record this for mainfiles where the command was trustworthy
236 /// (i.e. not inferred). This avoids a bad inference "infecting" other files.
237 /// - Once we've picked a proxy file for a header, we stick with it until the
238 /// proxy file is invalidated *and* a new candidate proxy file is built.
239 /// Switching proxies is expensive, as the compile flags will (probably)
240 /// change and therefore we'll end up rebuilding the header's preamble.
241 /// - We don't capture the actual compile command, but just the filename we
242 /// should query to get it. This avoids getting out of sync with the CDB.
243 ///
244 /// All methods are threadsafe. In practice, update() comes from preamble
245 /// threads, remove()s mostly from the main thread, and get() from ASTWorker.
246 /// Writes are rare and reads are cheap, so we don't expect much contention.
248  // We should be be a little careful how we store the include graph of open
249  // files, as each can have a large number of transitive headers.
250  // This representation is O(unique transitive source files).
251  llvm::BumpPtrAllocator Arena;
252  struct Association {
253  llvm::StringRef MainFile;
254  // Circular-linked-list of associations with the same mainFile.
255  // Null indicates that the mainfile was removed.
256  Association *Next;
257  };
258  llvm::StringMap<Association, llvm::BumpPtrAllocator &> HeaderToMain;
259  llvm::StringMap<Association *, llvm::BumpPtrAllocator &> MainToFirst;
260  std::atomic<size_t> UsedBytes; // Updated after writes.
261  mutable std::mutex Mu;
262 
263  void invalidate(Association *First) {
264  Association *Current = First;
265  do {
266  Association *Next = Current->Next;
267  Current->Next = nullptr;
268  Current = Next;
269  } while (Current != First);
270  }
271 
272  // Create the circular list and return the head of it.
273  Association *associate(llvm::StringRef MainFile,
274  llvm::ArrayRef<std::string> Headers) {
275  Association *First = nullptr, *Prev = nullptr;
276  for (const std::string &Header : Headers) {
277  auto &Assoc = HeaderToMain[Header];
278  if (Assoc.Next)
279  continue; // Already has a valid association.
280 
281  Assoc.MainFile = MainFile;
282  Assoc.Next = Prev;
283  Prev = &Assoc;
284  if (!First)
285  First = &Assoc;
286  }
287  if (First)
288  First->Next = Prev;
289  return First;
290  }
291 
292  void updateMemoryUsage() {
293  auto StringMapHeap = [](const auto &Map) {
294  // StringMap stores the hashtable on the heap.
295  // It contains pointers to the entries, and a hashcode for each.
296  return Map.getNumBuckets() * (sizeof(void *) + sizeof(unsigned));
297  };
298  size_t Usage = Arena.getTotalMemory() + StringMapHeap(MainToFirst) +
299  StringMapHeap(HeaderToMain) + sizeof(*this);
300  UsedBytes.store(Usage, std::memory_order_release);
301  }
302 
303 public:
304  HeaderIncluderCache() : HeaderToMain(Arena), MainToFirst(Arena) {
305  updateMemoryUsage();
306  }
307 
308  // Associate each header with MainFile (unless already associated).
309  // Headers not in the list will have their associations removed.
310  void update(PathRef MainFile, llvm::ArrayRef<std::string> Headers) {
311  std::lock_guard<std::mutex> Lock(Mu);
312  auto It = MainToFirst.try_emplace(MainFile, nullptr);
313  Association *&First = It.first->second;
314  if (First)
315  invalidate(First);
316  First = associate(It.first->first(), Headers);
317  updateMemoryUsage();
318  }
319 
320  // Mark MainFile as gone.
321  // This will *not* disassociate headers with MainFile immediately, but they
322  // will be eligible for association with other files that get update()d.
324  std::lock_guard<std::mutex> Lock(Mu);
325  Association *&First = MainToFirst[MainFile];
326  if (First) {
327  invalidate(First);
328  First = nullptr;
329  }
330  // MainToFirst entry should stay alive, as Associations might be pointing at
331  // its key.
332  }
333 
334  /// Get the mainfile associated with Header, or the empty string if none.
335  std::string get(PathRef Header) const {
336  std::lock_guard<std::mutex> Lock(Mu);
337  return HeaderToMain.lookup(Header).MainFile.str();
338  }
339 
340  size_t getUsedBytes() const {
341  return UsedBytes.load(std::memory_order_acquire);
342  }
343 };
344 
345 namespace {
346 
347 bool isReliable(const tooling::CompileCommand &Cmd) {
348  return Cmd.Heuristic.empty();
349 }
350 
351 /// Threadsafe manager for updating a TUStatus and emitting it after each
352 /// update.
353 class SynchronizedTUStatus {
354 public:
355  SynchronizedTUStatus(PathRef FileName, ParsingCallbacks &Callbacks)
356  : FileName(FileName), Callbacks(Callbacks) {}
357 
358  void update(llvm::function_ref<void(TUStatus &)> Mutator) {
359  std::lock_guard<std::mutex> Lock(StatusMu);
360  Mutator(Status);
361  emitStatusLocked();
362  }
363 
364  /// Prevents emitting of further updates.
365  void stop() {
366  std::lock_guard<std::mutex> Lock(StatusMu);
367  CanPublish = false;
368  }
369 
370 private:
371  void emitStatusLocked() {
372  if (CanPublish)
373  Callbacks.onFileUpdated(FileName, Status);
374  }
375 
376  const Path FileName;
377 
378  std::mutex StatusMu;
379  TUStatus Status;
380  bool CanPublish = true;
381  ParsingCallbacks &Callbacks;
382 };
383 
384 // An attempt to acquire resources for a task using PreambleThrottler.
385 // Initially it is unsatisfied, it (hopefully) becomes satisfied later but may
386 // be destroyed before then. Destruction releases all resources.
387 class PreambleThrottlerRequest {
388 public:
389  // The condition variable is signalled when the request is satisfied.
390  PreambleThrottlerRequest(llvm::StringRef Filename,
391  PreambleThrottler *Throttler,
392  std::condition_variable &CV)
393  : Throttler(Throttler),
394  Satisfied(Throttler == nullptr) {
395  // If there is no throttler, this dummy request is always satisfied.
396  if (!Throttler)
397  return;
398  ID = Throttler->acquire(Filename, [&] {
399  Satisfied.store(true, std::memory_order_release);
400  CV.notify_all();
401  });
402  }
403 
404  bool satisfied() const { return Satisfied.load(std::memory_order_acquire); }
405 
406  // When the request is destroyed:
407  // - if resources are not yet obtained, stop trying to get them.
408  // - if resources were obtained, release them.
409  ~PreambleThrottlerRequest() {
410  if (Throttler)
411  Throttler->release(ID);
412  }
413 
414 private:
416  PreambleThrottler *Throttler;
417  std::atomic<bool> Satisfied = {false};
418 };
419 
420 /// Responsible for building preambles. Whenever the thread is idle and the
421 /// preamble is outdated, it starts to build a fresh preamble from the latest
422 /// inputs. If RunSync is true, preambles are built synchronously in update()
423 /// instead.
424 class PreambleThread {
425 public:
426  PreambleThread(llvm::StringRef FileName, ParsingCallbacks &Callbacks,
427  bool StorePreambleInMemory, bool RunSync,
428  PreambleThrottler *Throttler, SynchronizedTUStatus &Status,
429  TUScheduler::HeaderIncluderCache &HeaderIncluders,
430  ASTWorker &AW)
431  : FileName(FileName), Callbacks(Callbacks),
432  StoreInMemory(StorePreambleInMemory), RunSync(RunSync),
433  Throttler(Throttler), Status(Status), ASTPeer(AW),
434  HeaderIncluders(HeaderIncluders) {}
435 
436  /// It isn't guaranteed that each requested version will be built. If there
437  /// are multiple update requests while building a preamble, only the last one
438  /// will be built.
439  void update(std::unique_ptr<CompilerInvocation> CI, ParseInputs PI,
440  std::vector<Diag> CIDiags, WantDiagnostics WantDiags) {
441  Request Req = {std::move(CI), std::move(PI), std::move(CIDiags), WantDiags,
442  Context::current().clone()};
443  if (RunSync) {
444  build(std::move(Req));
445  Status.update([](TUStatus &Status) {
446  Status.PreambleActivity = PreambleAction::Idle;
447  });
448  return;
449  }
450  {
451  std::unique_lock<std::mutex> Lock(Mutex);
452  // If NextReq was requested with WantDiagnostics::Yes we cannot just drop
453  // that on the floor. Block until we start building it. This won't
454  // dead-lock as we are blocking the caller thread, while builds continue
455  // on preamble thread.
456  ReqCV.wait(Lock, [this] {
457  return !NextReq || NextReq->WantDiags != WantDiagnostics::Yes;
458  });
459  NextReq = std::move(Req);
460  }
461  // Let the worker thread know there's a request, notify_one is safe as there
462  // should be a single worker thread waiting on it.
463  ReqCV.notify_all();
464  }
465 
466  void run() {
467  while (true) {
468  llvm::Optional<PreambleThrottlerRequest> Throttle;
469  {
470  std::unique_lock<std::mutex> Lock(Mutex);
471  assert(!CurrentReq && "Already processing a request?");
472  // Wait until stop is called or there is a request.
473  ReqCV.wait(Lock, [&] { return NextReq || Done; });
474  if (Done)
475  break;
476 
477  {
478  Throttle.emplace(FileName, Throttler, ReqCV);
479  llvm::Optional<trace::Span> Tracer;
480  // If acquire succeeded synchronously, avoid status jitter.
481  if (!Throttle->satisfied()) {
482  Tracer.emplace("PreambleThrottle");
483  Status.update([&](TUStatus &Status) {
484  Status.PreambleActivity = PreambleAction::Queued;
485  });
486  }
487  ReqCV.wait(Lock, [&] { return Throttle->satisfied() || Done; });
488  }
489  if (Done)
490  break;
491  // While waiting for the throttler, the request may have been updated!
492  // That's fine though, there's still guaranteed to be some request.
493 
494  CurrentReq = std::move(*NextReq);
495  NextReq.reset();
496  }
497 
498  {
499  WithContext Guard(std::move(CurrentReq->Ctx));
500  // Note that we don't make use of the ContextProvider here.
501  // Preamble tasks are always scheduled by ASTWorker tasks, and we
502  // reuse the context/config that was created at that level.
503 
504  // Build the preamble and let the waiters know about it.
505  build(std::move(*CurrentReq));
506  }
507  // Releasing the throttle before destroying the request assists testing.
508  Throttle.reset();
509  bool IsEmpty = false;
510  {
511  std::lock_guard<std::mutex> Lock(Mutex);
512  CurrentReq.reset();
513  IsEmpty = !NextReq;
514  }
515  if (IsEmpty) {
516  // We don't perform this above, before waiting for a request to make
517  // tests more deterministic. As there can be a race between this thread
518  // and client thread(clangdserver).
519  Status.update([](TUStatus &Status) {
520  Status.PreambleActivity = PreambleAction::Idle;
521  });
522  }
523  ReqCV.notify_all();
524  }
525  dlog("Preamble worker for {0} stopped", FileName);
526  }
527 
528  /// Signals the run loop to exit.
529  void stop() {
530  dlog("Preamble worker for {0} received stop", FileName);
531  {
532  std::lock_guard<std::mutex> Lock(Mutex);
533  Done = true;
534  NextReq.reset();
535  }
536  // Let the worker thread know that it should stop.
537  ReqCV.notify_all();
538  }
539 
540  bool blockUntilIdle(Deadline Timeout) const {
541  std::unique_lock<std::mutex> Lock(Mutex);
542  return wait(Lock, ReqCV, Timeout, [&] { return !NextReq && !CurrentReq; });
543  }
544 
545 private:
546  /// Holds inputs required for building a preamble. CI is guaranteed to be
547  /// non-null.
548  struct Request {
549  std::unique_ptr<CompilerInvocation> CI;
550  ParseInputs Inputs;
551  std::vector<Diag> CIDiags;
553  Context Ctx;
554  };
555 
556  bool isDone() {
557  std::lock_guard<std::mutex> Lock(Mutex);
558  return Done;
559  }
560 
561  /// Builds a preamble for \p Req, might reuse LatestBuild if possible.
562  /// Notifies ASTWorker after build finishes.
563  void build(Request Req);
564 
565  mutable std::mutex Mutex;
566  bool Done = false; /* GUARDED_BY(Mutex) */
567  llvm::Optional<Request> NextReq; /* GUARDED_BY(Mutex) */
568  llvm::Optional<Request> CurrentReq; /* GUARDED_BY(Mutex) */
569  // Signaled whenever a thread populates NextReq or worker thread builds a
570  // Preamble.
571  mutable std::condition_variable ReqCV; /* GUARDED_BY(Mutex) */
572  // Accessed only by preamble thread.
573  std::shared_ptr<const PreambleData> LatestBuild;
574 
575  const Path FileName;
576  ParsingCallbacks &Callbacks;
577  const bool StoreInMemory;
578  const bool RunSync;
579  PreambleThrottler *Throttler;
580 
581  SynchronizedTUStatus &Status;
582  ASTWorker &ASTPeer;
583  TUScheduler::HeaderIncluderCache &HeaderIncluders;
584 };
585 
586 class ASTWorkerHandle;
587 
588 /// Owns one instance of the AST, schedules updates and reads of it.
589 /// Also responsible for building and providing access to the preamble.
590 /// Each ASTWorker processes the async requests sent to it on a separate
591 /// dedicated thread.
592 /// The ASTWorker that manages the AST is shared by both the processing thread
593 /// and the TUScheduler. The TUScheduler should discard an ASTWorker when
594 /// remove() is called, but its thread may be busy and we don't want to block.
595 /// So the workers are accessed via an ASTWorkerHandle. Destroying the handle
596 /// signals the worker to exit its run loop and gives up shared ownership of the
597 /// worker.
598 class ASTWorker {
599  friend class ASTWorkerHandle;
600  ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB,
601  TUScheduler::ASTCache &LRUCache,
602  TUScheduler::HeaderIncluderCache &HeaderIncluders,
603  Semaphore &Barrier, bool RunSync, const TUScheduler::Options &Opts,
604  ParsingCallbacks &Callbacks);
605 
606 public:
607  /// Create a new ASTWorker and return a handle to it.
608  /// The processing thread is spawned using \p Tasks. However, when \p Tasks
609  /// is null, all requests will be processed on the calling thread
610  /// synchronously instead. \p Barrier is acquired when processing each
611  /// request, it is used to limit the number of actively running threads.
612  static ASTWorkerHandle
613  create(PathRef FileName, const GlobalCompilationDatabase &CDB,
614  TUScheduler::ASTCache &IdleASTs,
615  TUScheduler::HeaderIncluderCache &HeaderIncluders,
616  AsyncTaskRunner *Tasks, Semaphore &Barrier,
617  const TUScheduler::Options &Opts, ParsingCallbacks &Callbacks);
618  ~ASTWorker();
619 
620  void update(ParseInputs Inputs, WantDiagnostics, bool ContentChanged);
621  void
622  runWithAST(llvm::StringRef Name,
623  llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action,
625  bool blockUntilIdle(Deadline Timeout) const;
626 
627  std::shared_ptr<const PreambleData> getPossiblyStalePreamble(
628  std::shared_ptr<const ASTSignals> *ASTSignals = nullptr) const;
629 
630  /// Used to inform ASTWorker about a new preamble build by PreambleThread.
631  /// Diagnostics are only published through this callback. This ensures they
632  /// are always for newer versions of the file, as the callback gets called in
633  /// the same order as update requests.
634  void updatePreamble(std::unique_ptr<CompilerInvocation> CI, ParseInputs PI,
635  std::shared_ptr<const PreambleData> Preamble,
636  std::vector<Diag> CIDiags, WantDiagnostics WantDiags);
637 
638  /// Obtain a preamble reflecting all updates so far. Threadsafe.
639  /// It may be delivered immediately, or later on the worker thread.
640  void getCurrentPreamble(
641  llvm::unique_function<void(std::shared_ptr<const PreambleData>)>);
642  /// Returns compile command from the current file inputs.
643  tooling::CompileCommand getCurrentCompileCommand() const;
644 
645  /// Wait for the first build of preamble to finish. Preamble itself can be
646  /// accessed via getPossiblyStalePreamble(). Note that this function will
647  /// return after an unsuccessful build of the preamble too, i.e. result of
648  /// getPossiblyStalePreamble() can be null even after this function returns.
649  void waitForFirstPreamble() const;
650 
651  TUScheduler::FileStats stats() const;
652  bool isASTCached() const;
653 
654 private:
655  // Details of an update request that are relevant to scheduling.
656  struct UpdateType {
657  // Do we want diagnostics from this version?
658  // If Yes, we must always build this version.
659  // If No, we only need to build this version if it's read.
660  // If Auto, we build if it's read or if the debounce expires.
662  // Did the main-file content of the document change?
663  // If so, we're allowed to cancel certain invalidated preceding reads.
665  };
666 
667  /// Publishes diagnostics for \p Inputs. It will build an AST or reuse the
668  /// cached one if applicable. Assumes LatestPreamble is compatible for \p
669  /// Inputs.
670  void generateDiagnostics(std::unique_ptr<CompilerInvocation> Invocation,
671  ParseInputs Inputs, std::vector<Diag> CIDiags);
672 
673  void updateASTSignals(ParsedAST &AST);
674 
675  // Must be called exactly once on processing thread. Will return after
676  // stop() is called on a separate thread and all pending requests are
677  // processed.
678  void run();
679  /// Signal that run() should finish processing pending requests and exit.
680  void stop();
681 
682  /// Adds a new task to the end of the request queue.
683  void startTask(llvm::StringRef Name, llvm::unique_function<void()> Task,
684  llvm::Optional<UpdateType> Update,
686  /// Runs a task synchronously.
687  void runTask(llvm::StringRef Name, llvm::function_ref<void()> Task);
688 
689  /// Determines the next action to perform.
690  /// All actions that should never run are discarded.
691  /// Returns a deadline for the next action. If it's expired, run now.
692  /// scheduleLocked() is called again at the deadline, or if requests arrive.
693  Deadline scheduleLocked();
694  /// Should the first task in the queue be skipped instead of run?
695  bool shouldSkipHeadLocked() const;
696 
697  struct Request {
698  llvm::unique_function<void()> Action;
699  std::string Name;
700  steady_clock::time_point AddTime;
701  Context Ctx;
702  llvm::Optional<Context> QueueCtx;
703  llvm::Optional<UpdateType> Update;
706  };
707 
708  /// Handles retention of ASTs.
709  TUScheduler::ASTCache &IdleASTs;
710  TUScheduler::HeaderIncluderCache &HeaderIncluders;
711  const bool RunSync;
712  /// Time to wait after an update to see whether another update obsoletes it.
713  const DebouncePolicy UpdateDebounce;
714  /// File that ASTWorker is responsible for.
715  const Path FileName;
716  /// Callback to create processing contexts for tasks.
717  const std::function<Context(llvm::StringRef)> ContextProvider;
718  const GlobalCompilationDatabase &CDB;
719  /// Callback invoked when preamble or main file AST is built.
720  ParsingCallbacks &Callbacks;
721 
722  Semaphore &Barrier;
723  /// Whether the 'onMainAST' callback ran for the current FileInputs.
724  bool RanASTCallback = false;
725  /// Guards members used by both TUScheduler and the worker thread.
726  mutable std::mutex Mutex;
727  /// File inputs, currently being used by the worker.
728  /// Writes and reads from unknown threads are locked. Reads from the worker
729  /// thread are not locked, as it's the only writer.
730  ParseInputs FileInputs; /* GUARDED_BY(Mutex) */
731  /// Times of recent AST rebuilds, used for UpdateDebounce computation.
732  llvm::SmallVector<DebouncePolicy::clock::duration>
733  RebuildTimes; /* GUARDED_BY(Mutex) */
734  /// Set to true to signal run() to finish processing.
735  bool Done; /* GUARDED_BY(Mutex) */
736  std::deque<Request> Requests; /* GUARDED_BY(Mutex) */
737  llvm::Optional<Request> CurrentRequest; /* GUARDED_BY(Mutex) */
738  /// Signalled whenever a new request has been scheduled or processing of a
739  /// request has completed.
740  mutable std::condition_variable RequestsCV;
741  std::shared_ptr<const ASTSignals> LatestASTSignals; /* GUARDED_BY(Mutex) */
742  /// Latest build preamble for current TU.
743  /// None means no builds yet, null means there was an error while building.
744  /// Only written by ASTWorker's thread.
745  llvm::Optional<std::shared_ptr<const PreambleData>> LatestPreamble;
746  std::deque<Request> PreambleRequests; /* GUARDED_BY(Mutex) */
747  /// Signaled whenever LatestPreamble changes state or there's a new
748  /// PreambleRequest.
749  mutable std::condition_variable PreambleCV;
750  /// Guards the callback that publishes results of AST-related computations
751  /// (diagnostics) and file statuses.
752  std::mutex PublishMu;
753  // Used to prevent remove document + add document races that lead to
754  // out-of-order callbacks for publishing results of onMainAST callback.
755  //
756  // The lifetime of the old/new ASTWorkers will overlap, but their handles
757  // don't. When the old handle is destroyed, the old worker will stop reporting
758  // any results to the user.
759  bool CanPublishResults = true; /* GUARDED_BY(PublishMu) */
760  std::atomic<unsigned> ASTBuildCount = {0};
761  std::atomic<unsigned> PreambleBuildCount = {0};
762 
763  SynchronizedTUStatus Status;
764  PreambleThread PreamblePeer;
765 };
766 
767 /// A smart-pointer-like class that points to an active ASTWorker.
768 /// In destructor, signals to the underlying ASTWorker that no new requests will
769 /// be sent and the processing loop may exit (after running all pending
770 /// requests).
771 class ASTWorkerHandle {
772  friend class ASTWorker;
773  ASTWorkerHandle(std::shared_ptr<ASTWorker> Worker)
774  : Worker(std::move(Worker)) {
775  assert(this->Worker);
776  }
777 
778 public:
779  ASTWorkerHandle(const ASTWorkerHandle &) = delete;
780  ASTWorkerHandle &operator=(const ASTWorkerHandle &) = delete;
781  ASTWorkerHandle(ASTWorkerHandle &&) = default;
782  ASTWorkerHandle &operator=(ASTWorkerHandle &&) = default;
783 
784  ~ASTWorkerHandle() {
785  if (Worker)
786  Worker->stop();
787  }
788 
789  ASTWorker &operator*() {
790  assert(Worker && "Handle was moved from");
791  return *Worker;
792  }
793 
794  ASTWorker *operator->() {
795  assert(Worker && "Handle was moved from");
796  return Worker.get();
797  }
798 
799  /// Returns an owning reference to the underlying ASTWorker that can outlive
800  /// the ASTWorkerHandle. However, no new requests to an active ASTWorker can
801  /// be schedule via the returned reference, i.e. only reads of the preamble
802  /// are possible.
803  std::shared_ptr<const ASTWorker> lock() { return Worker; }
804 
805 private:
806  std::shared_ptr<ASTWorker> Worker;
807 };
808 
809 ASTWorkerHandle
810 ASTWorker::create(PathRef FileName, const GlobalCompilationDatabase &CDB,
811  TUScheduler::ASTCache &IdleASTs,
812  TUScheduler::HeaderIncluderCache &HeaderIncluders,
813  AsyncTaskRunner *Tasks, Semaphore &Barrier,
814  const TUScheduler::Options &Opts,
815  ParsingCallbacks &Callbacks) {
816  std::shared_ptr<ASTWorker> Worker(
817  new ASTWorker(FileName, CDB, IdleASTs, HeaderIncluders, Barrier,
818  /*RunSync=*/!Tasks, Opts, Callbacks));
819  if (Tasks) {
820  Tasks->runAsync("ASTWorker:" + llvm::sys::path::filename(FileName),
821  [Worker]() { Worker->run(); });
822  Tasks->runAsync("PreambleWorker:" + llvm::sys::path::filename(FileName),
823  [Worker]() { Worker->PreamblePeer.run(); });
824  }
825 
826  return ASTWorkerHandle(std::move(Worker));
827 }
828 
829 ASTWorker::ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB,
830  TUScheduler::ASTCache &LRUCache,
831  TUScheduler::HeaderIncluderCache &HeaderIncluders,
832  Semaphore &Barrier, bool RunSync,
833  const TUScheduler::Options &Opts,
834  ParsingCallbacks &Callbacks)
835  : IdleASTs(LRUCache), HeaderIncluders(HeaderIncluders), RunSync(RunSync),
836  UpdateDebounce(Opts.UpdateDebounce), FileName(FileName),
837  ContextProvider(Opts.ContextProvider), CDB(CDB), Callbacks(Callbacks),
838  Barrier(Barrier), Done(false), Status(FileName, Callbacks),
839  PreamblePeer(FileName, Callbacks, Opts.StorePreamblesInMemory, RunSync,
840  Opts.PreambleThrottler, Status, HeaderIncluders, *this) {
841  // Set a fallback command because compile command can be accessed before
842  // `Inputs` is initialized. Other fields are only used after initialization
843  // from client inputs.
844  FileInputs.CompileCommand = CDB.getFallbackCommand(FileName);
845 }
846 
847 ASTWorker::~ASTWorker() {
848  // Make sure we remove the cached AST, if any.
849  IdleASTs.take(this);
850 #ifndef NDEBUG
851  std::lock_guard<std::mutex> Lock(Mutex);
852  assert(Done && "handle was not destroyed");
853  assert(Requests.empty() && !CurrentRequest &&
854  "unprocessed requests when destroying ASTWorker");
855 #endif
856 }
857 
858 void ASTWorker::update(ParseInputs Inputs, WantDiagnostics WantDiags,
859  bool ContentChanged) {
860  llvm::StringLiteral TaskName = "Update";
861  auto Task = [=]() mutable {
862  // Get the actual command as `Inputs` does not have a command.
863  // FIXME: some build systems like Bazel will take time to preparing
864  // environment to build the file, it would be nice if we could emit a
865  // "PreparingBuild" status to inform users, it is non-trivial given the
866  // current implementation.
867  auto Cmd = CDB.getCompileCommand(FileName);
868  // If we don't have a reliable command for this file, it may be a header.
869  // Try to find a file that includes it, to borrow its command.
870  if (!Cmd || !isReliable(*Cmd)) {
871  std::string ProxyFile = HeaderIncluders.get(FileName);
872  if (!ProxyFile.empty()) {
873  auto ProxyCmd = CDB.getCompileCommand(ProxyFile);
874  if (!ProxyCmd || !isReliable(*ProxyCmd)) {
875  // This command is supposed to be reliable! It's probably gone.
876  HeaderIncluders.remove(ProxyFile);
877  } else {
878  // We have a reliable command for an including file, use it.
879  Cmd = tooling::transferCompileCommand(std::move(*ProxyCmd), FileName);
880  }
881  }
882  }
883  if (Cmd)
884  Inputs.CompileCommand = std::move(*Cmd);
885  else
886  Inputs.CompileCommand = CDB.getFallbackCommand(FileName);
887 
888  bool InputsAreTheSame =
889  std::tie(FileInputs.CompileCommand, FileInputs.Contents) ==
890  std::tie(Inputs.CompileCommand, Inputs.Contents);
891  // Cached AST is invalidated.
892  if (!InputsAreTheSame) {
893  IdleASTs.take(this);
894  RanASTCallback = false;
895  }
896 
897  // Update current inputs so that subsequent reads can see them.
898  {
899  std::lock_guard<std::mutex> Lock(Mutex);
900  FileInputs = Inputs;
901  }
902 
903  log("ASTWorker building file {0} version {1} with command {2}\n[{3}]\n{4}",
904  FileName, Inputs.Version, Inputs.CompileCommand.Heuristic,
905  Inputs.CompileCommand.Directory,
906  printArgv(Inputs.CompileCommand.CommandLine));
907 
908  StoreDiags CompilerInvocationDiagConsumer;
909  std::vector<std::string> CC1Args;
910  std::unique_ptr<CompilerInvocation> Invocation = buildCompilerInvocation(
911  Inputs, CompilerInvocationDiagConsumer, &CC1Args);
912  // Log cc1 args even (especially!) if creating invocation failed.
913  if (!CC1Args.empty())
914  vlog("Driver produced command: cc1 {0}", printArgv(CC1Args));
915  std::vector<Diag> CompilerInvocationDiags =
916  CompilerInvocationDiagConsumer.take();
917  if (!Invocation) {
918  elog("Could not build CompilerInvocation for file {0}", FileName);
919  // Remove the old AST if it's still in cache.
920  IdleASTs.take(this);
921  RanASTCallback = false;
922  // Report the diagnostics we collected when parsing the command line.
923  Callbacks.onFailedAST(FileName, Inputs.Version,
924  std::move(CompilerInvocationDiags),
925  [&](llvm::function_ref<void()> Publish) {
926  // Ensure we only publish results from the worker
927  // if the file was not removed, making sure there
928  // are not race conditions.
929  std::lock_guard<std::mutex> Lock(PublishMu);
930  if (CanPublishResults)
931  Publish();
932  });
933  // Note that this might throw away a stale preamble that might still be
934  // useful, but this is how we communicate a build error.
935  LatestPreamble.emplace();
936  // Make sure anyone waiting for the preamble gets notified it could not be
937  // built.
938  PreambleCV.notify_all();
939  return;
940  }
941 
942  PreamblePeer.update(std::move(Invocation), std::move(Inputs),
943  std::move(CompilerInvocationDiags), WantDiags);
944  std::unique_lock<std::mutex> Lock(Mutex);
945  PreambleCV.wait(Lock, [this] {
946  // Block until we reiceve a preamble request, unless a preamble already
947  // exists, as patching an empty preamble would imply rebuilding it from
948  // scratch.
949  // We block here instead of the consumer to prevent any deadlocks. Since
950  // LatestPreamble is only populated by ASTWorker thread.
951  return LatestPreamble || !PreambleRequests.empty() || Done;
952  });
953  };
954  startTask(TaskName, std::move(Task), UpdateType{WantDiags, ContentChanged},
955  TUScheduler::NoInvalidation);
956 }
957 
958 void ASTWorker::runWithAST(
959  llvm::StringRef Name,
960  llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action,
961  TUScheduler::ASTActionInvalidation Invalidation) {
962  // Tracks ast cache accesses for read operations.
963  static constexpr trace::Metric ASTAccessForRead(
964  "ast_access_read", trace::Metric::Counter, "result");
965  auto Task = [=, Action = std::move(Action)]() mutable {
966  if (auto Reason = isCancelled())
967  return Action(llvm::make_error<CancelledError>(Reason));
968  llvm::Optional<std::unique_ptr<ParsedAST>> AST =
969  IdleASTs.take(this, &ASTAccessForRead);
970  if (!AST) {
971  StoreDiags CompilerInvocationDiagConsumer;
972  std::unique_ptr<CompilerInvocation> Invocation =
973  buildCompilerInvocation(FileInputs, CompilerInvocationDiagConsumer);
974  // Try rebuilding the AST.
975  vlog("ASTWorker rebuilding evicted AST to run {0}: {1} version {2}", Name,
976  FileName, FileInputs.Version);
977  // FIXME: We might need to build a patched ast once preamble thread starts
978  // running async. Currently getPossiblyStalePreamble below will always
979  // return a compatible preamble as ASTWorker::update blocks.
980  llvm::Optional<ParsedAST> NewAST;
981  if (Invocation) {
982  NewAST = ParsedAST::build(FileName, FileInputs, std::move(Invocation),
983  CompilerInvocationDiagConsumer.take(),
984  getPossiblyStalePreamble());
985  ++ASTBuildCount;
986  }
987  AST = NewAST ? std::make_unique<ParsedAST>(std::move(*NewAST)) : nullptr;
988  }
989  // Make sure we put the AST back into the LRU cache.
990  auto _ = llvm::make_scope_exit(
991  [&AST, this]() { IdleASTs.put(this, std::move(*AST)); });
992  // Run the user-provided action.
993  if (!*AST)
994  return Action(error(llvm::errc::invalid_argument, "invalid AST"));
995  vlog("ASTWorker running {0} on version {2} of {1}", Name, FileName,
996  FileInputs.Version);
997  Action(InputsAndAST{FileInputs, **AST});
998  };
999  startTask(Name, std::move(Task), /*Update=*/None, Invalidation);
1000 }
1001 
1002 /// To be called from ThreadCrashReporter's signal handler.
1003 static void crashDumpCompileCommand(llvm::raw_ostream &OS,
1004  const tooling::CompileCommand &Command) {
1005  OS << " Filename: " << Command.Filename << "\n";
1006  OS << " Directory: " << Command.Directory << "\n";
1007  OS << " Command Line:";
1008  for (auto &Arg : Command.CommandLine) {
1009  OS << " " << Arg;
1010  }
1011  OS << "\n";
1012 }
1013 
1014 /// To be called from ThreadCrashReporter's signal handler.
1015 static void crashDumpFileContents(llvm::raw_ostream &OS,
1016  const std::string &Contents) {
1017  // Avoid flooding the terminal with source code by default, but allow clients
1018  // to opt in. Use an env var to preserve backwards compatibility of the
1019  // command line interface, while allowing it to be set outside the clangd
1020  // launch site for more flexibility.
1021  if (getenv("CLANGD_CRASH_DUMP_SOURCE")) {
1022  OS << " Contents:\n";
1023  OS << Contents << "\n";
1024  }
1025 }
1026 
1027 /// To be called from ThreadCrashReporter's signal handler.
1028 static void crashDumpParseInputs(llvm::raw_ostream &OS,
1029  const ParseInputs &FileInputs) {
1030  auto &Command = FileInputs.CompileCommand;
1031  crashDumpCompileCommand(OS, Command);
1032  OS << " Version: " << FileInputs.Version << "\n";
1033  crashDumpFileContents(OS, FileInputs.Contents);
1034 }
1035 
1036 void PreambleThread::build(Request Req) {
1037  assert(Req.CI && "Got preamble request with null compiler invocation");
1038  const ParseInputs &Inputs = Req.Inputs;
1039  bool ReusedPreamble = false;
1040 
1041  Status.update([&](TUStatus &Status) {
1042  Status.PreambleActivity = PreambleAction::Building;
1043  });
1044  auto _ = llvm::make_scope_exit([this, &Req, &ReusedPreamble] {
1045  ASTPeer.updatePreamble(std::move(Req.CI), std::move(Req.Inputs),
1046  LatestBuild, std::move(Req.CIDiags),
1047  std::move(Req.WantDiags));
1048  if (!ReusedPreamble)
1049  Callbacks.onPreamblePublished(FileName);
1050  });
1051 
1052  if (!LatestBuild || Inputs.ForceRebuild) {
1053  vlog("Building first preamble for {0} version {1}", FileName,
1054  Inputs.Version);
1055  } else if (isPreambleCompatible(*LatestBuild, Inputs, FileName, *Req.CI)) {
1056  vlog("Reusing preamble version {0} for version {1} of {2}",
1057  LatestBuild->Version, Inputs.Version, FileName);
1058  ReusedPreamble = true;
1059  return;
1060  } else {
1061  vlog("Rebuilding invalidated preamble for {0} version {1} (previous was "
1062  "version {2})",
1063  FileName, Inputs.Version, LatestBuild->Version);
1064  }
1065 
1066  ThreadCrashReporter ScopedReporter([&Inputs]() {
1067  llvm::errs() << "Signalled while building preamble\n";
1068  crashDumpParseInputs(llvm::errs(), Inputs);
1069  });
1070 
1071  PreambleBuildStats Stats;
1072  bool IsFirstPreamble = !LatestBuild;
1073  LatestBuild = clang::clangd::buildPreamble(
1074  FileName, *Req.CI, Inputs, StoreInMemory,
1075  [&](ASTContext &Ctx, Preprocessor &PP,
1076  const CanonicalIncludes &CanonIncludes) {
1077  Callbacks.onPreambleAST(FileName, Inputs.Version, *Req.CI, Ctx, PP,
1078  CanonIncludes);
1079  },
1080  &Stats);
1081  if (!LatestBuild)
1082  return;
1083  reportPreambleBuild(Stats, IsFirstPreamble);
1084  if (isReliable(LatestBuild->CompileCommand))
1085  HeaderIncluders.update(FileName, LatestBuild->Includes.allHeaders());
1086 }
1087 
1088 void ASTWorker::updatePreamble(std::unique_ptr<CompilerInvocation> CI,
1089  ParseInputs PI,
1090  std::shared_ptr<const PreambleData> Preamble,
1091  std::vector<Diag> CIDiags,
1093  llvm::StringLiteral TaskName = "Build AST";
1094  // Store preamble and build diagnostics with new preamble if requested.
1095  auto Task = [this, Preamble = std::move(Preamble), CI = std::move(CI),
1096  PI = std::move(PI), CIDiags = std::move(CIDiags),
1097  WantDiags = std::move(WantDiags)]() mutable {
1098  // Update the preamble inside ASTWorker queue to ensure atomicity. As a task
1099  // running inside ASTWorker assumes internals won't change until it
1100  // finishes.
1101  if (!LatestPreamble || Preamble != *LatestPreamble) {
1102  ++PreambleBuildCount;
1103  // Cached AST is no longer valid.
1104  IdleASTs.take(this);
1105  RanASTCallback = false;
1106  std::lock_guard<std::mutex> Lock(Mutex);
1107  // LatestPreamble might be the last reference to old preamble, do not
1108  // trigger destructor while holding the lock.
1109  if (LatestPreamble)
1110  std::swap(*LatestPreamble, Preamble);
1111  else
1112  LatestPreamble = std::move(Preamble);
1113  }
1114  // Notify anyone waiting for a preamble.
1115  PreambleCV.notify_all();
1116  // Give up our ownership to old preamble before starting expensive AST
1117  // build.
1118  Preamble.reset();
1119  // We only need to build the AST if diagnostics were requested.
1120  if (WantDiags == WantDiagnostics::No)
1121  return;
1122  // Report diagnostics with the new preamble to ensure progress. Otherwise
1123  // diagnostics might get stale indefinitely if user keeps invalidating the
1124  // preamble.
1125  generateDiagnostics(std::move(CI), std::move(PI), std::move(CIDiags));
1126  };
1127  if (RunSync) {
1128  runTask(TaskName, Task);
1129  return;
1130  }
1131  {
1132  std::lock_guard<std::mutex> Lock(Mutex);
1133  PreambleRequests.push_back({std::move(Task), std::string(TaskName),
1134  steady_clock::now(), Context::current().clone(),
1135  llvm::None, llvm::None,
1136  TUScheduler::NoInvalidation, nullptr});
1137  }
1138  PreambleCV.notify_all();
1139  RequestsCV.notify_all();
1140 }
1141 
1142 void ASTWorker::updateASTSignals(ParsedAST &AST) {
1143  auto Signals = std::make_shared<const ASTSignals>(ASTSignals::derive(AST));
1144  // Existing readers of ASTSignals will have their copy preserved until the
1145  // read is completed. The last reader deletes the old ASTSignals.
1146  {
1147  std::lock_guard<std::mutex> Lock(Mutex);
1148  std::swap(LatestASTSignals, Signals);
1149  }
1150 }
1151 
1152 void ASTWorker::generateDiagnostics(
1153  std::unique_ptr<CompilerInvocation> Invocation, ParseInputs Inputs,
1154  std::vector<Diag> CIDiags) {
1155  // Tracks ast cache accesses for publishing diags.
1156  static constexpr trace::Metric ASTAccessForDiag(
1157  "ast_access_diag", trace::Metric::Counter, "result");
1158  assert(Invocation);
1159  assert(LatestPreamble);
1160  // No need to rebuild the AST if we won't send the diagnostics.
1161  {
1162  std::lock_guard<std::mutex> Lock(PublishMu);
1163  if (!CanPublishResults)
1164  return;
1165  }
1166  // Used to check whether we can update AST cache.
1167  bool InputsAreLatest =
1168  std::tie(FileInputs.CompileCommand, FileInputs.Contents) ==
1169  std::tie(Inputs.CompileCommand, Inputs.Contents);
1170  // Take a shortcut and don't report the diagnostics, since they should be the
1171  // same. All the clients should handle the lack of OnUpdated() call anyway to
1172  // handle empty result from buildAST.
1173  // FIXME: the AST could actually change if non-preamble includes changed,
1174  // but we choose to ignore it.
1175  if (InputsAreLatest && RanASTCallback)
1176  return;
1177 
1178  // Get the AST for diagnostics, either build it or use the cached one.
1179  std::string TaskName = llvm::formatv("Build AST ({0})", Inputs.Version);
1180  Status.update([&](TUStatus &Status) {
1181  Status.ASTActivity.K = ASTAction::Building;
1182  Status.ASTActivity.Name = std::move(TaskName);
1183  });
1184  // We might be able to reuse the last we've built for a read request.
1185  // FIXME: It might be better to not reuse this AST. That way queued AST builds
1186  // won't be required for diags.
1187  llvm::Optional<std::unique_ptr<ParsedAST>> AST =
1188  IdleASTs.take(this, &ASTAccessForDiag);
1189  if (!AST || !InputsAreLatest) {
1190  auto RebuildStartTime = DebouncePolicy::clock::now();
1191  llvm::Optional<ParsedAST> NewAST = ParsedAST::build(
1192  FileName, Inputs, std::move(Invocation), CIDiags, *LatestPreamble);
1193  auto RebuildDuration = DebouncePolicy::clock::now() - RebuildStartTime;
1194  ++ASTBuildCount;
1195  // Try to record the AST-build time, to inform future update debouncing.
1196  // This is best-effort only: if the lock is held, don't bother.
1197  std::unique_lock<std::mutex> Lock(Mutex, std::try_to_lock);
1198  if (Lock.owns_lock()) {
1199  // Do not let RebuildTimes grow beyond its small-size (i.e.
1200  // capacity).
1201  if (RebuildTimes.size() == RebuildTimes.capacity())
1202  RebuildTimes.erase(RebuildTimes.begin());
1203  RebuildTimes.push_back(RebuildDuration);
1204  Lock.unlock();
1205  }
1206  Status.update([&](TUStatus &Status) {
1207  Status.Details.ReuseAST = false;
1208  Status.Details.BuildFailed = !NewAST;
1209  });
1210  AST = NewAST ? std::make_unique<ParsedAST>(std::move(*NewAST)) : nullptr;
1211  } else {
1212  log("Skipping rebuild of the AST for {0}, inputs are the same.", FileName);
1213  Status.update([](TUStatus &Status) {
1214  Status.Details.ReuseAST = true;
1215  Status.Details.BuildFailed = false;
1216  });
1217  }
1218 
1219  // Publish diagnostics.
1220  auto RunPublish = [&](llvm::function_ref<void()> Publish) {
1221  // Ensure we only publish results from the worker if the file was not
1222  // removed, making sure there are not race conditions.
1223  std::lock_guard<std::mutex> Lock(PublishMu);
1224  if (CanPublishResults)
1225  Publish();
1226  };
1227  if (*AST) {
1228  trace::Span Span("Running main AST callback");
1229  Callbacks.onMainAST(FileName, **AST, RunPublish);
1230  updateASTSignals(**AST);
1231  } else {
1232  // Failed to build the AST, at least report diagnostics from the
1233  // command line if there were any.
1234  // FIXME: we might have got more errors while trying to build the
1235  // AST, surface them too.
1236  Callbacks.onFailedAST(FileName, Inputs.Version, CIDiags, RunPublish);
1237  }
1238 
1239  // AST might've been built for an older version of the source, as ASTWorker
1240  // queue raced ahead while we were waiting on the preamble. In that case the
1241  // queue can't reuse the AST.
1242  if (InputsAreLatest) {
1243  RanASTCallback = *AST != nullptr;
1244  IdleASTs.put(this, std::move(*AST));
1245  }
1246 }
1247 
1248 std::shared_ptr<const PreambleData> ASTWorker::getPossiblyStalePreamble(
1249  std::shared_ptr<const ASTSignals> *ASTSignals) const {
1250  std::lock_guard<std::mutex> Lock(Mutex);
1251  if (ASTSignals)
1252  *ASTSignals = LatestASTSignals;
1253  return LatestPreamble ? *LatestPreamble : nullptr;
1254 }
1255 
1256 void ASTWorker::waitForFirstPreamble() const {
1257  std::unique_lock<std::mutex> Lock(Mutex);
1258  PreambleCV.wait(Lock, [this] { return LatestPreamble || Done; });
1259 }
1260 
1261 tooling::CompileCommand ASTWorker::getCurrentCompileCommand() const {
1262  std::unique_lock<std::mutex> Lock(Mutex);
1263  return FileInputs.CompileCommand;
1264 }
1265 
1266 TUScheduler::FileStats ASTWorker::stats() const {
1267  TUScheduler::FileStats Result;
1268  Result.ASTBuilds = ASTBuildCount;
1269  Result.PreambleBuilds = PreambleBuildCount;
1270  // Note that we don't report the size of ASTs currently used for processing
1271  // the in-flight requests. We used this information for debugging purposes
1272  // only, so this should be fine.
1273  Result.UsedBytesAST = IdleASTs.getUsedBytes(this);
1274  if (auto Preamble = getPossiblyStalePreamble())
1275  Result.UsedBytesPreamble = Preamble->Preamble.getSize();
1276  return Result;
1277 }
1278 
1279 bool ASTWorker::isASTCached() const { return IdleASTs.getUsedBytes(this) != 0; }
1280 
1281 void ASTWorker::stop() {
1282  {
1283  std::lock_guard<std::mutex> Lock(PublishMu);
1284  CanPublishResults = false;
1285  }
1286  {
1287  std::lock_guard<std::mutex> Lock(Mutex);
1288  assert(!Done && "stop() called twice");
1289  Done = true;
1290  }
1291  PreamblePeer.stop();
1292  // We are no longer going to build any preambles, let the waiters know that.
1293  PreambleCV.notify_all();
1294  Status.stop();
1295  RequestsCV.notify_all();
1296 }
1297 
1298 void ASTWorker::runTask(llvm::StringRef Name, llvm::function_ref<void()> Task) {
1299  ThreadCrashReporter ScopedReporter([this, Name]() {
1300  llvm::errs() << "Signalled during AST worker action: " << Name << "\n";
1301  crashDumpParseInputs(llvm::errs(), FileInputs);
1302  });
1303  trace::Span Tracer(Name);
1304  WithContext WithProvidedContext(ContextProvider(FileName));
1305  Task();
1306 }
1307 
1308 void ASTWorker::startTask(llvm::StringRef Name,
1309  llvm::unique_function<void()> Task,
1310  llvm::Optional<UpdateType> Update,
1311  TUScheduler::ASTActionInvalidation Invalidation) {
1312  if (RunSync) {
1313  assert(!Done && "running a task after stop()");
1314  runTask(Name, Task);
1315  return;
1316  }
1317 
1318  {
1319  std::lock_guard<std::mutex> Lock(Mutex);
1320  assert(!Done && "running a task after stop()");
1321  // Cancel any requests invalidated by this request.
1322  if (Update && Update->ContentChanged) {
1323  for (auto &R : llvm::reverse(Requests)) {
1324  if (R.InvalidationPolicy == TUScheduler::InvalidateOnUpdate)
1325  R.Invalidate();
1326  if (R.Update && R.Update->ContentChanged)
1327  break; // Older requests were already invalidated by the older update.
1328  }
1329  }
1330 
1331  // Allow this request to be cancelled if invalidated.
1332  Context Ctx = Context::current().derive(FileBeingProcessed, FileName);
1333  Canceler Invalidate = nullptr;
1334  if (Invalidation) {
1335  WithContext WC(std::move(Ctx));
1336  std::tie(Ctx, Invalidate) = cancelableTask(
1337  /*Reason=*/static_cast<int>(ErrorCode::ContentModified));
1338  }
1339  // Trace the time the request spends in the queue, and the requests that
1340  // it's going to wait for.
1341  llvm::Optional<Context> QueueCtx;
1342  if (trace::enabled()) {
1343  // Tracers that follow threads and need strict nesting will see a tiny
1344  // instantaneous event "we're enqueueing", and sometime later it runs.
1345  WithContext WC(Ctx.clone());
1346  trace::Span Tracer("Queued:" + Name);
1347  if (Tracer.Args) {
1348  if (CurrentRequest)
1349  SPAN_ATTACH(Tracer, "CurrentRequest", CurrentRequest->Name);
1350  llvm::json::Array PreambleRequestsNames;
1351  for (const auto &Req : PreambleRequests)
1352  PreambleRequestsNames.push_back(Req.Name);
1353  SPAN_ATTACH(Tracer, "PreambleRequestsNames",
1354  std::move(PreambleRequestsNames));
1355  llvm::json::Array RequestsNames;
1356  for (const auto &Req : Requests)
1357  RequestsNames.push_back(Req.Name);
1358  SPAN_ATTACH(Tracer, "RequestsNames", std::move(RequestsNames));
1359  }
1360  // For tracers that follow contexts, keep the trace span's context alive
1361  // until we dequeue the request, so they see the full duration.
1362  QueueCtx = Context::current().clone();
1363  }
1364  Requests.push_back({std::move(Task), std::string(Name), steady_clock::now(),
1365  std::move(Ctx), std::move(QueueCtx), Update,
1366  Invalidation, std::move(Invalidate)});
1367  }
1368  RequestsCV.notify_all();
1369 }
1370 
1371 void ASTWorker::run() {
1372  while (true) {
1373  {
1374  std::unique_lock<std::mutex> Lock(Mutex);
1375  assert(!CurrentRequest && "A task is already running, multiple workers?");
1376  for (auto Wait = scheduleLocked(); !Wait.expired();
1377  Wait = scheduleLocked()) {
1378  assert(PreambleRequests.empty() &&
1379  "Preamble updates should be scheduled immediately");
1380  if (Done) {
1381  if (Requests.empty())
1382  return;
1383  // Even though Done is set, finish pending requests.
1384  break; // However, skip delays to shutdown fast.
1385  }
1386 
1387  // Tracing: we have a next request, attribute this sleep to it.
1388  llvm::Optional<WithContext> Ctx;
1389  llvm::Optional<trace::Span> Tracer;
1390  if (!Requests.empty()) {
1391  Ctx.emplace(Requests.front().Ctx.clone());
1392  Tracer.emplace("Debounce");
1393  SPAN_ATTACH(*Tracer, "next_request", Requests.front().Name);
1394  if (!(Wait == Deadline::infinity())) {
1395  Status.update([&](TUStatus &Status) {
1396  Status.ASTActivity.K = ASTAction::Queued;
1397  Status.ASTActivity.Name = Requests.front().Name;
1398  });
1399  SPAN_ATTACH(*Tracer, "sleep_ms",
1400  std::chrono::duration_cast<std::chrono::milliseconds>(
1401  Wait.time() - steady_clock::now())
1402  .count());
1403  }
1404  }
1405 
1406  wait(Lock, RequestsCV, Wait);
1407  }
1408  // Any request in ReceivedPreambles is at least as old as the
1409  // Requests.front(), so prefer them first to preserve LSP order.
1410  if (!PreambleRequests.empty()) {
1411  CurrentRequest = std::move(PreambleRequests.front());
1412  PreambleRequests.pop_front();
1413  } else {
1414  CurrentRequest = std::move(Requests.front());
1415  Requests.pop_front();
1416  }
1417  } // unlock Mutex
1418 
1419  // Inform tracing that the request was dequeued.
1420  CurrentRequest->QueueCtx.reset();
1421 
1422  // It is safe to perform reads to CurrentRequest without holding the lock as
1423  // only writer is also this thread.
1424  {
1425  std::unique_lock<Semaphore> Lock(Barrier, std::try_to_lock);
1426  if (!Lock.owns_lock()) {
1427  Status.update([&](TUStatus &Status) {
1428  Status.ASTActivity.K = ASTAction::Queued;
1429  Status.ASTActivity.Name = CurrentRequest->Name;
1430  });
1431  Lock.lock();
1432  }
1433  WithContext Guard(std::move(CurrentRequest->Ctx));
1434  Status.update([&](TUStatus &Status) {
1435  Status.ASTActivity.K = ASTAction::RunningAction;
1436  Status.ASTActivity.Name = CurrentRequest->Name;
1437  });
1438  runTask(CurrentRequest->Name, CurrentRequest->Action);
1439  }
1440 
1441  bool IsEmpty = false;
1442  {
1443  std::lock_guard<std::mutex> Lock(Mutex);
1444  CurrentRequest.reset();
1445  IsEmpty = Requests.empty() && PreambleRequests.empty();
1446  }
1447  if (IsEmpty) {
1448  Status.update([&](TUStatus &Status) {
1449  Status.ASTActivity.K = ASTAction::Idle;
1450  Status.ASTActivity.Name = "";
1451  });
1452  }
1453  RequestsCV.notify_all();
1454  }
1455 }
1456 
1457 Deadline ASTWorker::scheduleLocked() {
1458  // Process new preambles immediately.
1459  if (!PreambleRequests.empty())
1460  return Deadline::zero();
1461  if (Requests.empty())
1462  return Deadline::infinity(); // Wait for new requests.
1463  // Handle cancelled requests first so the rest of the scheduler doesn't.
1464  for (auto I = Requests.begin(), E = Requests.end(); I != E; ++I) {
1465  if (!isCancelled(I->Ctx)) {
1466  // Cancellations after the first read don't affect current scheduling.
1467  if (I->Update == None)
1468  break;
1469  continue;
1470  }
1471  // Cancelled reads are moved to the front of the queue and run immediately.
1472  if (I->Update == None) {
1473  Request R = std::move(*I);
1474  Requests.erase(I);
1475  Requests.push_front(std::move(R));
1476  return Deadline::zero();
1477  }
1478  // Cancelled updates are downgraded to auto-diagnostics, and may be elided.
1479  if (I->Update->Diagnostics == WantDiagnostics::Yes)
1480  I->Update->Diagnostics = WantDiagnostics::Auto;
1481  }
1482 
1483  while (shouldSkipHeadLocked()) {
1484  vlog("ASTWorker skipping {0} for {1}", Requests.front().Name, FileName);
1485  Requests.pop_front();
1486  }
1487  assert(!Requests.empty() && "skipped the whole queue");
1488  // Some updates aren't dead yet, but never end up being used.
1489  // e.g. the first keystroke is live until obsoleted by the second.
1490  // We debounce "maybe-unused" writes, sleeping in case they become dead.
1491  // But don't delay reads (including updates where diagnostics are needed).
1492  for (const auto &R : Requests)
1493  if (R.Update == None || R.Update->Diagnostics == WantDiagnostics::Yes)
1494  return Deadline::zero();
1495  // Front request needs to be debounced, so determine when we're ready.
1496  Deadline D(Requests.front().AddTime + UpdateDebounce.compute(RebuildTimes));
1497  return D;
1498 }
1499 
1500 // Returns true if Requests.front() is a dead update that can be skipped.
1501 bool ASTWorker::shouldSkipHeadLocked() const {
1502  assert(!Requests.empty());
1503  auto Next = Requests.begin();
1504  auto Update = Next->Update;
1505  if (!Update) // Only skip updates.
1506  return false;
1507  ++Next;
1508  // An update is live if its AST might still be read.
1509  // That is, if it's not immediately followed by another update.
1510  if (Next == Requests.end() || !Next->Update)
1511  return false;
1512  // The other way an update can be live is if its diagnostics might be used.
1513  switch (Update->Diagnostics) {
1514  case WantDiagnostics::Yes:
1515  return false; // Always used.
1516  case WantDiagnostics::No:
1517  return true; // Always dead.
1518  case WantDiagnostics::Auto:
1519  // Used unless followed by an update that generates diagnostics.
1520  for (; Next != Requests.end(); ++Next)
1521  if (Next->Update && Next->Update->Diagnostics != WantDiagnostics::No)
1522  return true; // Prefer later diagnostics.
1523  return false;
1524  }
1525  llvm_unreachable("Unknown WantDiagnostics");
1526 }
1527 
1528 bool ASTWorker::blockUntilIdle(Deadline Timeout) const {
1529  auto WaitUntilASTWorkerIsIdle = [&] {
1530  std::unique_lock<std::mutex> Lock(Mutex);
1531  return wait(Lock, RequestsCV, Timeout, [&] {
1532  return PreambleRequests.empty() && Requests.empty() && !CurrentRequest;
1533  });
1534  };
1535  // Make sure ASTWorker has processed all requests, which might issue new
1536  // updates to PreamblePeer.
1537  if (!WaitUntilASTWorkerIsIdle())
1538  return false;
1539  // Now that ASTWorker processed all requests, ensure PreamblePeer has served
1540  // all update requests. This might create new PreambleRequests for the
1541  // ASTWorker.
1542  if (!PreamblePeer.blockUntilIdle(Timeout))
1543  return false;
1544  assert(Requests.empty() &&
1545  "No new normal tasks can be scheduled concurrently with "
1546  "blockUntilIdle(): ASTWorker isn't threadsafe");
1547  // Finally make sure ASTWorker has processed all of the preamble updates.
1548  return WaitUntilASTWorkerIsIdle();
1549 }
1550 
1551 // Render a TUAction to a user-facing string representation.
1552 // TUAction represents clangd-internal states, we don't intend to expose them
1553 // to users (say C++ programmers) directly to avoid confusion, we use terms that
1554 // are familiar by C++ programmers.
1555 std::string renderTUAction(const PreambleAction PA, const ASTAction &AA) {
1556  llvm::SmallVector<std::string, 2> Result;
1557  switch (PA) {
1558  case PreambleAction::Building:
1559  Result.push_back("parsing includes");
1560  break;
1561  case PreambleAction::Queued:
1562  Result.push_back("includes are queued");
1563  break;
1564  case PreambleAction::Idle:
1565  // We handle idle specially below.
1566  break;
1567  }
1568  switch (AA.K) {
1569  case ASTAction::Queued:
1570  Result.push_back("file is queued");
1571  break;
1572  case ASTAction::RunningAction:
1573  Result.push_back("running " + AA.Name);
1574  break;
1575  case ASTAction::Building:
1576  Result.push_back("parsing main file");
1577  break;
1578  case ASTAction::Idle:
1579  // We handle idle specially below.
1580  break;
1581  }
1582  if (Result.empty())
1583  return "idle";
1584  return llvm::join(Result, ", ");
1585 }
1586 
1587 } // namespace
1588 
1590  return llvm::heavyweight_hardware_concurrency().compute_thread_count();
1591 }
1592 
1593 FileStatus TUStatus::render(PathRef File) const {
1594  FileStatus FStatus;
1595  FStatus.uri = URIForFile::canonicalize(File, /*TUPath=*/File);
1596  FStatus.state = renderTUAction(PreambleActivity, ASTActivity);
1597  return FStatus;
1598 }
1599 
1601  /// Latest inputs, passed to TUScheduler::update().
1602  std::string Contents;
1603  ASTWorkerHandle Worker;
1604 };
1605 
1606 TUScheduler::TUScheduler(const GlobalCompilationDatabase &CDB,
1607  const Options &Opts,
1608  std::unique_ptr<ParsingCallbacks> Callbacks)
1609  : CDB(CDB), Opts(Opts),
1610  Callbacks(Callbacks ? std::move(Callbacks)
1611  : std::make_unique<ParsingCallbacks>()),
1612  Barrier(Opts.AsyncThreadsCount), QuickRunBarrier(Opts.AsyncThreadsCount),
1613  IdleASTs(
1614  std::make_unique<ASTCache>(Opts.RetentionPolicy.MaxRetainedASTs)),
1615  HeaderIncluders(std::make_unique<HeaderIncluderCache>()) {
1616  // Avoid null checks everywhere.
1617  if (!Opts.ContextProvider) {
1618  this->Opts.ContextProvider = [](llvm::StringRef) {
1619  return Context::current().clone();
1620  };
1621  }
1622  if (0 < Opts.AsyncThreadsCount) {
1623  PreambleTasks.emplace();
1624  WorkerThreads.emplace();
1625  }
1626 }
1627 
1629  // Notify all workers that they need to stop.
1630  Files.clear();
1631 
1632  // Wait for all in-flight tasks to finish.
1633  if (PreambleTasks)
1634  PreambleTasks->wait();
1635  if (WorkerThreads)
1636  WorkerThreads->wait();
1637 }
1638 
1640  for (auto &File : Files)
1641  if (!File.getValue()->Worker->blockUntilIdle(D))
1642  return false;
1643  if (PreambleTasks)
1644  if (!PreambleTasks->wait(D))
1645  return false;
1646  return true;
1647 }
1648 
1651  std::unique_ptr<FileData> &FD = Files[File];
1652  bool NewFile = FD == nullptr;
1653  bool ContentChanged = false;
1654  if (!FD) {
1655  // Create a new worker to process the AST-related tasks.
1656  ASTWorkerHandle Worker =
1657  ASTWorker::create(File, CDB, *IdleASTs, *HeaderIncluders,
1658  WorkerThreads ? WorkerThreads.getPointer() : nullptr,
1659  Barrier, Opts, *Callbacks);
1660  FD = std::unique_ptr<FileData>(
1661  new FileData{Inputs.Contents, std::move(Worker)});
1662  ContentChanged = true;
1663  } else if (FD->Contents != Inputs.Contents) {
1664  ContentChanged = true;
1665  FD->Contents = Inputs.Contents;
1666  }
1667  FD->Worker->update(std::move(Inputs), WantDiags, ContentChanged);
1668  // There might be synthetic update requests, don't change the LastActiveFile
1669  // in such cases.
1670  if (ContentChanged)
1671  LastActiveFile = File.str();
1672  return NewFile;
1673 }
1674 
1676  bool Removed = Files.erase(File);
1677  if (!Removed)
1678  elog("Trying to remove file from TUScheduler that is not tracked: {0}",
1679  File);
1680  // We don't call HeaderIncluders.remove(File) here.
1681  // If we did, we'd avoid potentially stale header/mainfile associations.
1682  // However, it would mean that closing a mainfile could invalidate the
1683  // preamble of several open headers.
1684 }
1685 
1686 void TUScheduler::run(llvm::StringRef Name, llvm::StringRef Path,
1687  llvm::unique_function<void()> Action) {
1688  runWithSemaphore(Name, Path, std::move(Action), Barrier);
1689 }
1690 
1691 void TUScheduler::runQuick(llvm::StringRef Name, llvm::StringRef Path,
1692  llvm::unique_function<void()> Action) {
1693  // Use QuickRunBarrier to serialize quick tasks: we are ignoring
1694  // the parallelism level set by the user, don't abuse it
1695  runWithSemaphore(Name, Path, std::move(Action), QuickRunBarrier);
1696 }
1697 
1698 void TUScheduler::runWithSemaphore(llvm::StringRef Name, llvm::StringRef Path,
1699  llvm::unique_function<void()> Action,
1700  Semaphore &Sem) {
1701  if (Path.empty())
1702  Path = LastActiveFile;
1703  else
1704  LastActiveFile = Path.str();
1705  if (!PreambleTasks) {
1706  WithContext WithProvidedContext(Opts.ContextProvider(Path));
1707  return Action();
1708  }
1709  PreambleTasks->runAsync(Name, [this, &Sem, Ctx = Context::current().clone(),
1710  Path(Path.str()),
1711  Action = std::move(Action)]() mutable {
1712  std::lock_guard<Semaphore> BarrierLock(Sem);
1713  WithContext WC(std::move(Ctx));
1714  WithContext WithProvidedContext(Opts.ContextProvider(Path));
1715  Action();
1716  });
1717 }
1718 
1720  llvm::StringRef Name, PathRef File,
1721  llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action,
1722  TUScheduler::ASTActionInvalidation Invalidation) {
1723  auto It = Files.find(File);
1724  if (It == Files.end()) {
1725  Action(llvm::make_error<LSPError>(
1726  "trying to get AST for non-added document", ErrorCode::InvalidParams));
1727  return;
1728  }
1729  LastActiveFile = File.str();
1730 
1731  It->second->Worker->runWithAST(Name, std::move(Action), Invalidation);
1732 }
1733 
1734 void TUScheduler::runWithPreamble(llvm::StringRef Name, PathRef File,
1735  PreambleConsistency Consistency,
1737  auto It = Files.find(File);
1738  if (It == Files.end()) {
1739  Action(llvm::make_error<LSPError>(
1740  "trying to get preamble for non-added document",
1742  return;
1743  }
1744  LastActiveFile = File.str();
1745 
1746  if (!PreambleTasks) {
1748  SPAN_ATTACH(Tracer, "file", File);
1749  std::shared_ptr<const ASTSignals> Signals;
1750  std::shared_ptr<const PreambleData> Preamble =
1751  It->second->Worker->getPossiblyStalePreamble(&Signals);
1752  WithContext WithProvidedContext(Opts.ContextProvider(File));
1753  Action(InputsAndPreamble{It->second->Contents,
1754  It->second->Worker->getCurrentCompileCommand(),
1755  Preamble.get(), Signals.get()});
1756  return;
1757  }
1758 
1759  std::shared_ptr<const ASTWorker> Worker = It->second->Worker.lock();
1760  auto Task = [Worker, Consistency, Name = Name.str(), File = File.str(),
1761  Contents = It->second->Contents,
1762  Command = Worker->getCurrentCompileCommand(),
1764  std::string(File)),
1765  Action = std::move(Action), this]() mutable {
1766  ThreadCrashReporter ScopedReporter([&Name, &Contents, &Command]() {
1767  llvm::errs() << "Signalled during preamble action: " << Name << "\n";
1768  crashDumpCompileCommand(llvm::errs(), Command);
1769  crashDumpFileContents(llvm::errs(), Contents);
1770  });
1771  std::shared_ptr<const PreambleData> Preamble;
1772  if (Consistency == PreambleConsistency::Stale) {
1773  // Wait until the preamble is built for the first time, if preamble
1774  // is required. This avoids extra work of processing the preamble
1775  // headers in parallel multiple times.
1776  Worker->waitForFirstPreamble();
1777  }
1778  std::shared_ptr<const ASTSignals> Signals;
1779  Preamble = Worker->getPossiblyStalePreamble(&Signals);
1780 
1781  std::lock_guard<Semaphore> BarrierLock(Barrier);
1782  WithContext Guard(std::move(Ctx));
1784  SPAN_ATTACH(Tracer, "file", File);
1785  WithContext WithProvidedContext(Opts.ContextProvider(File));
1786  Action(InputsAndPreamble{Contents, Command, Preamble.get(), Signals.get()});
1787  };
1788 
1789  PreambleTasks->runAsync("task:" + llvm::sys::path::filename(File),
1790  std::move(Task));
1791 }
1792 
1793 llvm::StringMap<TUScheduler::FileStats> TUScheduler::fileStats() const {
1794  llvm::StringMap<TUScheduler::FileStats> Result;
1795  for (const auto &PathAndFile : Files)
1796  Result.try_emplace(PathAndFile.first(),
1797  PathAndFile.second->Worker->stats());
1798  return Result;
1799 }
1800 
1801 std::vector<Path> TUScheduler::getFilesWithCachedAST() const {
1802  std::vector<Path> Result;
1803  for (auto &&PathAndFile : Files) {
1804  if (!PathAndFile.second->Worker->isASTCached())
1805  continue;
1806  Result.push_back(std::string(PathAndFile.first()));
1807  }
1808  return Result;
1809 }
1810 
1811 DebouncePolicy::clock::duration
1812 DebouncePolicy::compute(llvm::ArrayRef<clock::duration> History) const {
1813  assert(Min <= Max && "Invalid policy");
1814  if (History.empty())
1815  return Max; // Arbitrary.
1816 
1817  // Base the result on the median rebuild.
1818  // nth_element needs a mutable array, take the chance to bound the data size.
1819  History = History.take_back(15);
1820  llvm::SmallVector<clock::duration, 15> Recent(History.begin(), History.end());
1821  auto *Median = Recent.begin() + Recent.size() / 2;
1822  std::nth_element(Recent.begin(), Median, Recent.end());
1823 
1824  clock::duration Target =
1825  std::chrono::duration_cast<clock::duration>(RebuildRatio * *Median);
1826  if (Target > Max)
1827  return Max;
1828  if (Target < Min)
1829  return Min;
1830  return Target;
1831 }
1832 
1834  DebouncePolicy P;
1835  P.Min = P.Max = T;
1836  return P;
1837 }
1838 
1840  for (const auto &Elem : fileStats()) {
1841  MT.detail(Elem.first())
1842  .child("preamble")
1843  .addUsage(Opts.StorePreamblesInMemory ? Elem.second.UsedBytesPreamble
1844  : 0);
1845  MT.detail(Elem.first()).child("ast").addUsage(Elem.second.UsedBytesAST);
1846  MT.child("header_includer_cache").addUsage(HeaderIncluders->getUsedBytes());
1847  }
1848 }
1849 } // namespace clangd
1850 } // namespace clang
dlog
#define dlog(...)
Definition: Logger.h:101
clang::clangd::buildPreamble
std::shared_ptr< const PreambleData > buildPreamble(PathRef FileName, CompilerInvocation CI, const ParseInputs &Inputs, bool StoreInMemory, PreambleParsedCallback PreambleCallback, PreambleBuildStats *Stats)
Build a preamble for the new inputs unless an old one can be reused.
Definition: Preamble.cpp:466
WantDiags
WantDiagnostics WantDiags
Definition: TUScheduler.cpp:552
clang::clangd::MemoryTree::child
MemoryTree & child(llvm::StringLiteral Name)
No copy of the Name.
Definition: MemoryTree.h:39
clang::clangd::isPreambleCompatible
bool isPreambleCompatible(const PreambleData &Preamble, const ParseInputs &Inputs, PathRef FileName, const CompilerInvocation &CI)
Returns true if Preamble is reusable for Inputs.
Definition: Preamble.cpp:577
clang::clangd::cancelableTask
std::pair< Context, Canceler > cancelableTask(int Reason)
Defines a new task whose cancellation may be requested.
Definition: Cancellation.cpp:24
Label
std::string Label
Definition: InlayHintTests.cpp:46
E
const Expr * E
Definition: AvoidBindCheck.cpp:88
clang::clangd::TUScheduler::runWithPreamble
void runWithPreamble(llvm::StringRef Name, PathRef File, PreambleConsistency Consistency, Callback< InputsAndPreamble > Action)
Schedule an async read of the preamble.
Definition: TUScheduler.cpp:1734
clang::clangd::getDefaultAsyncThreadsCount
unsigned getDefaultAsyncThreadsCount()
Returns a number of a default async threads to use for TUScheduler.
Definition: TUScheduler.cpp:1589
CIDiags
std::vector< Diag > CIDiags
Definition: TUScheduler.cpp:551
clang::clangd::printArgv
std::string printArgv(llvm::ArrayRef< llvm::StringRef > Args)
Definition: CompileCommands.cpp:633
clang::clangd::Path
std::string Path
A typedef to represent a file path.
Definition: Path.h:26
Update
llvm::Optional< UpdateType > Update
Definition: TUScheduler.cpp:703
clang::clangd::TUScheduler::~TUScheduler
~TUScheduler()
Definition: TUScheduler.cpp:1628
Usage
const char Usage[]
Definition: ClangReorderFields.cpp:50
Tracer
std::unique_ptr< trace::EventTracer > Tracer
Definition: TraceTests.cpp:161
Path.h
clang::clangd::Context::current
static const Context & current()
Returns the context for the current thread, creating it if needed.
Definition: Context.cpp:27
clang::clangd::WantDiagnostics::Yes
@ Yes
clang::clangd::TUScheduler::blockUntilIdle
bool blockUntilIdle(Deadline D) const
Wait until there are no scheduled or running tasks.
Definition: TUScheduler.cpp:1639
clang::clangd::Context::clone
Context clone() const
Clone this context object.
Definition: Context.cpp:20
Diagnostics
WantDiagnostics Diagnostics
Definition: TUScheduler.cpp:661
ContentChanged
bool ContentChanged
Definition: TUScheduler.cpp:664
clang::clangd::detail::error
llvm::Error error(std::error_code, std::string &&)
Definition: Logger.cpp:80
CI
std::unique_ptr< CompilerInvocation > CI
Definition: TUScheduler.cpp:549
Filename
std::string Filename
Filename as a string.
Definition: IncludeOrderCheck.cpp:40
QueueCtx
llvm::Optional< Context > QueueCtx
Definition: TUScheduler.cpp:702
clang::clangd::PreambleAction
PreambleAction
Definition: TUScheduler.h:118
Preamble.h
clang::clangd::PreambleBuildStats::TotalBuildTime
double TotalBuildTime
Total wall time it took to build preamble, in seconds.
Definition: Preamble.h:83
Ctx
Context Ctx
Definition: TUScheduler.cpp:553
clang::clangd::TUScheduler::run
void run(llvm::StringRef Name, llvm::StringRef Path, llvm::unique_function< void()> Action)
Schedule an async task with no dependencies.
Definition: TUScheduler.cpp:1686
Trace.h
AST
llvm::Optional< ParsedAST > AST
Definition: SymbolCollectorTests.cpp:135
clang::clangd::PreambleAction::Queued
@ Queued
clang::clangd::TUScheduler::getFilesWithCachedAST
std::vector< Path > getFilesWithCachedAST() const
Returns a list of files with ASTs currently stored in memory.
Definition: TUScheduler.cpp:1801
clang::tidy::cppcoreguidelines::join
static std::string join(ArrayRef< SpecialMemberFunctionsCheck::SpecialMemberFunctionKind > SMFS, llvm::StringRef AndOr)
Definition: SpecialMemberFunctionsCheck.cpp:78
clang::clangd::TUScheduler::update
bool update(PathRef File, ParseInputs Inputs, WantDiagnostics WD)
Schedule an update for File.
Definition: TUScheduler.cpp:1649
clang::clangd::GlobalCompilationDatabase
Provides compilation arguments used for parsing C and C++ files.
Definition: GlobalCompilationDatabase.h:34
Action
llvm::unique_function< void()> Action
Definition: TUScheduler.cpp:698
clang::clangd::PreambleThrottler::RequestID
unsigned RequestID
Definition: TUScheduler.h:101
clang::clangd::TUScheduler::Options::ContextProvider
std::function< Context(PathRef)> ContextProvider
Used to create a context that wraps each single operation.
Definition: TUScheduler.h:238
Target
std::string Target
Definition: QueryDriverDatabase.cpp:64
clang::clangd::Semaphore
Limits the number of threads that can acquire the lock at the same time.
Definition: Threading.h:28
Preamble
const PreambleData & Preamble
Definition: CodeComplete.cpp:1212
Cancellation.h
clang::clangd::PreambleBuildStats::SerializedSize
size_t SerializedSize
The serialized size of the preamble.
Definition: Preamble.h:93
clang::clangd::Deadline
A point in time we can wait for.
Definition: Threading.h:45
clang::clangd::WantDiagnostics
WantDiagnostics
Determines whether diagnostics should be generated for a file snapshot.
Definition: TUScheduler.h:52
clang::clangd::canonicalize
static llvm::SmallString< 128 > canonicalize(llvm::StringRef Path)
Definition: FileDistance.cpp:48
clang::clangd::MemoryTree::detail
MemoryTree & detail(llvm::StringRef Name)
Makes a copy of the Name in detailed mode, returns current node otherwise.
Definition: MemoryTree.h:51
Inputs
ParseInputs Inputs
Definition: TUScheduler.cpp:550
clang::clangd::isCancelled
int isCancelled(const Context &Ctx)
If the current context is within a cancelled task, returns the reason.
Definition: Cancellation.cpp:35
clang::clangd::TUScheduler::HeaderIncluderCache::HeaderIncluderCache
HeaderIncluderCache()
Definition: TUScheduler.cpp:304
clang::clangd::MemoryTree::addUsage
void addUsage(size_t Increment)
Increases size of current node by Increment.
Definition: MemoryTree.h:56
clang::clangd::wait
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:120
clang::clangd::Context::derive
Context derive(const Key< Type > &Key, std::decay_t< Type > Value) const &
Derives a child context It is safe to move or destroy a parent context after calling derive().
Definition: Context.h:119
clang::clangd::ParseInputs
Information required to run clang, e.g. to parse AST or do code completion.
Definition: Compiler.h:46
CanonicalIncludes.h
ns1::ns2::D
@ D
Definition: CategoricalFeature.h:3
clang::clangd::InputsAndPreamble::Contents
llvm::StringRef Contents
Definition: TUScheduler.h:43
clang::clangd::FileStatus::state
std::string state
The human-readable string presents the current state of the file, can be shown in the UI (e....
Definition: Protocol.h:1648
clang::clangd::ErrorCode::InvalidParams
@ InvalidParams
clang::clangd::ParsingCallbacks
Definition: TUScheduler.h:157
clang::clangd::TUScheduler::HeaderIncluderCache::remove
void remove(PathRef MainFile)
Definition: TUScheduler.cpp:323
clang::clangd::MemoryTree
A tree that can be used to represent memory usage of nested components while preserving the hierarchy...
Definition: MemoryTree.h:30
GlobalCompilationDatabase.h
clang::clangd::PreambleAction::Idle
@ Idle
clang::clangd::ThreadCrashReporter
Allows setting per-thread abort/kill signal callbacks, to print additional information about the cras...
Definition: ThreadCrashReporter.h:19
clang::clangd::PreambleBuildStats::FileSystemTime
double FileSystemTime
Time spent in filesystem operations during the build, in seconds.
Definition: Preamble.h:85
clang::clangd::TUScheduler::ASTCache::ASTCache
ASTCache(unsigned MaxRetainedASTs)
Definition: TUScheduler.cpp:154
CompileCommands.h
clang::clangd::trace::enabled
bool enabled()
Returns true if there is an active tracer.
Definition: Trace.cpp:283
Logger.h
Threading.h
clang::clangd::FileStatus::uri
URIForFile uri
The text document's URI.
Definition: Protocol.h:1645
Name
std::string Name
Definition: TUScheduler.cpp:699
clang::clangd::TUScheduler::HeaderIncluderCache::get
std::string get(PathRef Header) const
Get the mainfile associated with Header, or the empty string if none.
Definition: TUScheduler.cpp:335
SPAN_ATTACH
#define SPAN_ATTACH(S, Name, Expr)
Attach a key-value pair to a Span event.
Definition: Trace.h:164
clang::clangd::TUScheduler::FileData::Contents
std::string Contents
Latest inputs, passed to TUScheduler::update().
Definition: TUScheduler.cpp:1602
clang::clangd::vlog
void vlog(const char *Fmt, Ts &&... Vals)
Definition: Logger.h:72
clang::clangd::trace::Metric::Distribution
@ Distribution
A distribution of values with a meaningful mean and count.
Definition: Trace.h:52
Diagnostics.h
clang::clangd::TUScheduler::remove
void remove(PathRef File)
Remove File from the list of tracked files and schedule removal of its resources.
Definition: TUScheduler.cpp:1675
clang::clangd::Key
Values in a Context are indexed by typed keys.
Definition: Context.h:40
FileName
StringRef FileName
Definition: KernelNameRestrictionCheck.cpp:46
clang::clangd::TUScheduler::fileStats
llvm::StringMap< FileStats > fileStats() const
Returns resources used for each of the currently open files.
Definition: TUScheduler.cpp:1793
clang::clangd::TUScheduler::ASTCache::getUsedBytes
std::size_t getUsedBytes(Key K)
Returns result of getUsedBytes() for the AST cached by K.
Definition: TUScheduler.cpp:158
clang::clangd::WithContext
WithContext replaces Context::current() with a provided scope.
Definition: Context.h:185
clang::clangd::DebouncePolicy::Min
clock::duration Min
The minimum time that we always debounce for.
Definition: TUScheduler.h:77
clang::tidy::bugprone::PP
static Preprocessor * PP
Definition: BadSignalToKillThreadCheck.cpp:29
clang::clangd::buildCompilerInvocation
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:86
Counter
trace::Metric Counter
Definition: TraceTests.cpp:149
clang::clangd::TUScheduler::ASTCache
An LRU cache of idle ASTs.
Definition: TUScheduler.cpp:150
clang::clangd::FileBeingProcessed
static clang::clangd::Key< std::string > FileBeingProcessed
Definition: TUScheduler.cpp:138
Compiler.h
clang::clangd::TUScheduler::runQuick
void runQuick(llvm::StringRef Name, llvm::StringRef Path, llvm::unique_function< void()> Action)
Similar to run, except the task is expected to be quick.
Definition: TUScheduler.cpp:1691
AddTime
steady_clock::time_point AddTime
Definition: TUScheduler.cpp:700
ID
static char ID
Definition: Logger.cpp:74
clang::clangd::TUScheduler::profile
void profile(MemoryTree &MT) const
Definition: TUScheduler.cpp:1839
clang::clangd::PathRef
llvm::StringRef PathRef
A typedef to represent a ref to file path.
Definition: Path.h:29
clang::clangd::TUScheduler::ASTActionInvalidation
ASTActionInvalidation
Defines how a runWithAST action is implicitly cancelled by other actions.
Definition: TUScheduler.h:287
clang::clangd::trace::Metric
Represents measurements of clangd events, e.g.
Definition: Trace.h:38
clang::clangd::InputsAndPreamble
Definition: TUScheduler.h:42
InvalidationPolicy
TUScheduler::ASTActionInvalidation InvalidationPolicy
Definition: TUScheduler.cpp:704
clang::clangd::TUScheduler::HeaderIncluderCache
A map from header files to an opened "proxy" file that includes them.
Definition: TUScheduler.cpp:247
clang::clangd::TUScheduler::Options
Definition: TUScheduler.h:215
clang::clangd::AsyncTaskRunner::runAsync
void runAsync(const llvm::Twine &Name, llvm::unique_function< void()> Action)
Definition: Threading.cpp:80
clang::clangd::TUScheduler::runWithAST
void runWithAST(llvm::StringRef Name, PathRef File, Callback< InputsAndAST > Action, ASTActionInvalidation=NoInvalidation)
Schedule an async read of the AST.
Definition: TUScheduler.cpp:1719
ThreadCrashReporter.h
clang::clangd::TUScheduler::ASTCache::put
void put(Key K, std::unique_ptr< ParsedAST > V)
Store the value in the pool, possibly removing the last used AST.
Definition: TUScheduler.cpp:168
clang::clangd::DebouncePolicy
Clangd may wait after an update to see if another one comes along.
Definition: TUScheduler.h:73
MemoryTree.h
if
if(CLANG_PLUGIN_SUPPORT) export_executable_symbols_for_plugins(clang-tidy) endif() install(PROGRAMS clang-tidy-diff.py DESTINATION "$
Definition: clang-tidy/tool/CMakeLists.txt:59
clang::clangd::Canceler
std::function< void()> Canceler
A canceller requests cancellation of a task, when called.
Definition: Cancellation.h:70
clang
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Definition: ApplyReplacements.h:27
OS
llvm::raw_string_ostream OS
Definition: TraceTests.cpp:160
Arena
llvm::BumpPtrAllocator Arena
Definition: Serialization.cpp:213
TUScheduler.h
clang::clangd::FileStatus
Clangd extension: indicates the current state of the file in clangd, sent from server via the textDoc...
Definition: Protocol.h:1643
clang::clangd::DebouncePolicy::RebuildRatio
float RebuildRatio
Target debounce, as a fraction of file rebuild time.
Definition: TUScheduler.h:82
clang::clangd::DebouncePolicy::Max
clock::duration Max
The maximum time we may debounce for.
Definition: TUScheduler.h:79
clang::clangd::TUScheduler::PreambleConsistency
PreambleConsistency
Controls whether preamble reads wait for the preamble to be up-to-date.
Definition: TUScheduler.h:310
clang::clangd::TUScheduler::FileData
Definition: TUScheduler.cpp:1600
clang::clangd::PreambleBuildStats::BuildSize
size_t BuildSize
Estimate of the memory used while building the preamble.
Definition: Preamble.h:90
clang::clangd::TUScheduler::HeaderIncluderCache::update
void update(PathRef MainFile, llvm::ArrayRef< std::string > Headers)
Definition: TUScheduler.cpp:310
clang::clangd::DebouncePolicy::fixed
static DebouncePolicy fixed(clock::duration)
A policy that always returns the same duration, useful for tests.
Definition: TUScheduler.cpp:1833
clang::clangd::Callback
llvm::unique_function< void(llvm::Expected< T >)> Callback
A Callback<T> is a void function that accepts Expected<T>.
Definition: Function.h:28
MainFile
std::string MainFile
Definition: HeadersTests.cpp:134
Invalidate
Canceler Invalidate
Definition: TUScheduler.cpp:705
clang::clangd::TUScheduler::FileData::Worker
ASTWorkerHandle Worker
Definition: TUScheduler.cpp:1603
clang::clangd::TUScheduler::ASTCache::take
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.
Definition: TUScheduler.cpp:188
clang::clangd::elog
void elog(const char *Fmt, Ts &&... Vals)
Definition: Logger.h:61
clang::clangd::detail::log
void log(Logger::Level L, const char *Fmt, Ts &&... Vals)
Definition: Logger.h:47
clang::clangd::DebouncePolicy::compute
clock::duration compute(llvm::ArrayRef< clock::duration > History) const
Compute the time to debounce based on this policy and recent build times.
Definition: TUScheduler.cpp:1812
K
Kind K
Definition: Rename.cpp:436
clang::clangd::TUScheduler::ASTCache::Key
const ASTWorker * Key
Definition: TUScheduler.cpp:152
clang::clangd::TUScheduler::HeaderIncluderCache::getUsedBytes
size_t getUsedBytes() const
Definition: TUScheduler.cpp:340
Context.h
clang::clangd::TUScheduler::getFileBeingProcessedInContext
static llvm::Optional< llvm::StringRef > getFileBeingProcessedInContext()
Definition: TUScheduler.cpp:140
ParsedAST.h
clang::clangd::trace::Span
Records an event whose duration is the lifetime of the Span object.
Definition: Trace.h:143