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