clang-tools  10.0.0svn
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 // For each file, managed by TUScheduler, we create a single ASTWorker that
9 // manages an AST for that file. All operations that modify or read the AST are
10 // run on a separate dedicated thread asynchronously in FIFO order.
11 //
12 // We start processing each update immediately after we receive it. If two or
13 // more updates come subsequently without reads in-between, we attempt to drop
14 // an older one to not waste time building the ASTs we don't need.
15 //
16 // The processing thread of the ASTWorker is also responsible for building the
17 // preamble. However, unlike AST, the same preamble can be read concurrently, so
18 // we run each of async preamble reads on its own thread.
19 //
20 // To limit the concurrent load that clangd produces we maintain a semaphore
21 // that keeps more than a fixed number of threads from running concurrently.
22 //
23 // Rationale for cancelling updates.
24 // LSP clients can send updates to clangd on each keystroke. Some files take
25 // significant time to parse (e.g. a few seconds) and clangd can get starved by
26 // the updates to those files. Therefore we try to process only the last update,
27 // if possible.
28 // Our current strategy to do that is the following:
29 // - For each update we immediately schedule rebuild of the AST.
30 // - Rebuild of the AST checks if it was cancelled before doing any actual work.
31 // If it was, it does not do an actual rebuild, only reports llvm::None to the
32 // callback
33 // - When adding an update, we cancel the last update in the queue if it didn't
34 // have any reads.
35 // There is probably a optimal ways to do that. One approach we might take is
36 // the following:
37 // - For each update we remember the pending inputs, but delay rebuild of the
38 // AST for some timeout.
39 // - If subsequent updates come before rebuild was started, we replace the
40 // pending inputs and reset the timer.
41 // - If any reads of the AST are scheduled, we start building the AST
42 // immediately.
43 
44 #include "TUScheduler.h"
45 #include "Cancellation.h"
46 #include "Compiler.h"
47 #include "Diagnostics.h"
49 #include "Logger.h"
50 #include "ParsedAST.h"
51 #include "Preamble.h"
52 #include "Trace.h"
54 #include "clang/Frontend/CompilerInvocation.h"
55 #include "clang/Tooling/CompilationDatabase.h"
56 #include "llvm/ADT/Optional.h"
57 #include "llvm/ADT/ScopeExit.h"
58 #include "llvm/Support/Errc.h"
59 #include "llvm/Support/Path.h"
60 #include "llvm/Support/Threading.h"
61 #include <algorithm>
62 #include <memory>
63 #include <queue>
64 #include <thread>
65 
66 namespace clang {
67 namespace clangd {
68 using std::chrono::steady_clock;
69 
70 namespace {
71 class ASTWorker;
72 } // namespace
73 
75 
76 llvm::Optional<llvm::StringRef> TUScheduler::getFileBeingProcessedInContext() {
77  if (auto *File = Context::current().get(kFileBeingProcessed))
78  return llvm::StringRef(*File);
79  return None;
80 }
81 
82 /// An LRU cache of idle ASTs.
83 /// Because we want to limit the overall number of these we retain, the cache
84 /// owns ASTs (and may evict them) while their workers are idle.
85 /// Workers borrow ASTs when active, and return them when done.
87 public:
88  using Key = const ASTWorker *;
89 
90  ASTCache(unsigned MaxRetainedASTs) : MaxRetainedASTs(MaxRetainedASTs) {}
91 
92  /// Returns result of getUsedBytes() for the AST cached by \p K.
93  /// If no AST is cached, 0 is returned.
94  std::size_t getUsedBytes(Key K) {
95  std::lock_guard<std::mutex> Lock(Mut);
96  auto It = findByKey(K);
97  if (It == LRU.end() || !It->second)
98  return 0;
99  return It->second->getUsedBytes();
100  }
101 
102  /// Store the value in the pool, possibly removing the last used AST.
103  /// The value should not be in the pool when this function is called.
104  void put(Key K, std::unique_ptr<ParsedAST> V) {
105  std::unique_lock<std::mutex> Lock(Mut);
106  assert(findByKey(K) == LRU.end());
107 
108  LRU.insert(LRU.begin(), {K, std::move(V)});
109  if (LRU.size() <= MaxRetainedASTs)
110  return;
111  // We're past the limit, remove the last element.
112  std::unique_ptr<ParsedAST> ForCleanup = std::move(LRU.back().second);
113  LRU.pop_back();
114  // Run the expensive destructor outside the lock.
115  Lock.unlock();
116  ForCleanup.reset();
117  }
118 
119  /// Returns the cached value for \p K, or llvm::None if the value is not in
120  /// the cache anymore. If nullptr was cached for \p K, this function will
121  /// return a null unique_ptr wrapped into an optional.
122  llvm::Optional<std::unique_ptr<ParsedAST>> take(Key K) {
123  std::unique_lock<std::mutex> Lock(Mut);
124  auto Existing = findByKey(K);
125  if (Existing == LRU.end())
126  return None;
127  std::unique_ptr<ParsedAST> V = std::move(Existing->second);
128  LRU.erase(Existing);
129  // GCC 4.8 fails to compile `return V;`, as it tries to call the copy
130  // constructor of unique_ptr, so we call the move ctor explicitly to avoid
131  // this miscompile.
132  return llvm::Optional<std::unique_ptr<ParsedAST>>(std::move(V));
133  }
134 
135 private:
136  using KVPair = std::pair<Key, std::unique_ptr<ParsedAST>>;
137 
138  std::vector<KVPair>::iterator findByKey(Key K) {
139  return llvm::find_if(LRU, [K](const KVPair &P) { return P.first == K; });
140  }
141 
142  std::mutex Mut;
143  unsigned MaxRetainedASTs;
144  /// Items sorted in LRU order, i.e. first item is the most recently accessed
145  /// one.
146  std::vector<KVPair> LRU; /* GUARDED_BY(Mut) */
147 };
148 
149 namespace {
150 class ASTWorkerHandle;
151 
152 /// Owns one instance of the AST, schedules updates and reads of it.
153 /// Also responsible for building and providing access to the preamble.
154 /// Each ASTWorker processes the async requests sent to it on a separate
155 /// dedicated thread.
156 /// The ASTWorker that manages the AST is shared by both the processing thread
157 /// and the TUScheduler. The TUScheduler should discard an ASTWorker when
158 /// remove() is called, but its thread may be busy and we don't want to block.
159 /// So the workers are accessed via an ASTWorkerHandle. Destroying the handle
160 /// signals the worker to exit its run loop and gives up shared ownership of the
161 /// worker.
162 class ASTWorker {
163  friend class ASTWorkerHandle;
164  ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB,
165  TUScheduler::ASTCache &LRUCache, Semaphore &Barrier, bool RunSync,
166  steady_clock::duration UpdateDebounce, bool StorePreamblesInMemory,
167  ParsingCallbacks &Callbacks);
168 
169 public:
170  /// Create a new ASTWorker and return a handle to it.
171  /// The processing thread is spawned using \p Tasks. However, when \p Tasks
172  /// is null, all requests will be processed on the calling thread
173  /// synchronously instead. \p Barrier is acquired when processing each
174  /// request, it is used to limit the number of actively running threads.
175  static ASTWorkerHandle
176  create(PathRef FileName, const GlobalCompilationDatabase &CDB,
177  TUScheduler::ASTCache &IdleASTs, AsyncTaskRunner *Tasks,
178  Semaphore &Barrier, steady_clock::duration UpdateDebounce,
179  bool StorePreamblesInMemory, ParsingCallbacks &Callbacks);
180  ~ASTWorker();
181 
182  void update(ParseInputs Inputs, WantDiagnostics);
183  void
184  runWithAST(llvm::StringRef Name,
185  llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action);
186  bool blockUntilIdle(Deadline Timeout) const;
187 
188  std::shared_ptr<const PreambleData> getPossiblyStalePreamble() const;
189 
190  /// Obtain a preamble reflecting all updates so far. Threadsafe.
191  /// It may be delivered immediately, or later on the worker thread.
192  void getCurrentPreamble(
193  llvm::unique_function<void(std::shared_ptr<const PreambleData>)>);
194  /// Returns compile command from the current file inputs.
195  tooling::CompileCommand getCurrentCompileCommand() const;
196 
197  /// Wait for the first build of preamble to finish. Preamble itself can be
198  /// accessed via getPossiblyStalePreamble(). Note that this function will
199  /// return after an unsuccessful build of the preamble too, i.e. result of
200  /// getPossiblyStalePreamble() can be null even after this function returns.
201  void waitForFirstPreamble() const;
202 
203  std::size_t getUsedBytes() const;
204  bool isASTCached() const;
205 
206 private:
207  // Must be called exactly once on processing thread. Will return after
208  // stop() is called on a separate thread and all pending requests are
209  // processed.
210  void run();
211  /// Signal that run() should finish processing pending requests and exit.
212  void stop();
213  /// Adds a new task to the end of the request queue.
214  void startTask(llvm::StringRef Name, llvm::unique_function<void()> Task,
215  llvm::Optional<WantDiagnostics> UpdateType);
216  /// Updates the TUStatus and emits it. Only called in the worker thread.
217  void emitTUStatus(TUAction FAction,
218  const TUStatus::BuildDetails *Detail = nullptr);
219 
220  /// Determines the next action to perform.
221  /// All actions that should never run are discarded.
222  /// Returns a deadline for the next action. If it's expired, run now.
223  /// scheduleLocked() is called again at the deadline, or if requests arrive.
224  Deadline scheduleLocked();
225  /// Should the first task in the queue be skipped instead of run?
226  bool shouldSkipHeadLocked() const;
227  /// This is private because `FileInputs.FS` is not thread-safe and thus not
228  /// safe to share. Callers should make sure not to expose `FS` via a public
229  /// interface.
230  std::shared_ptr<const ParseInputs> getCurrentFileInputs() const;
231 
232  struct Request {
233  llvm::unique_function<void()> Action;
234  std::string Name;
235  steady_clock::time_point AddTime;
236  Context Ctx;
237  llvm::Optional<WantDiagnostics> UpdateType;
238  };
239 
240  /// Handles retention of ASTs.
241  TUScheduler::ASTCache &IdleASTs;
242  const bool RunSync;
243  /// Time to wait after an update to see whether another update obsoletes it.
244  const steady_clock::duration UpdateDebounce;
245  /// File that ASTWorker is responsible for.
246  const Path FileName;
247  const GlobalCompilationDatabase &CDB;
248  /// Whether to keep the built preambles in memory or on disk.
249  const bool StorePreambleInMemory;
250  /// Callback invoked when preamble or main file AST is built.
251  ParsingCallbacks &Callbacks;
252  /// Only accessed by the worker thread.
253  TUStatus Status;
254 
255  Semaphore &Barrier;
256  /// Whether the 'onMainAST' callback ran for the current FileInputs.
257  bool RanASTCallback = false;
258  /// Guards members used by both TUScheduler and the worker thread.
259  mutable std::mutex Mutex;
260  /// File inputs, currently being used by the worker.
261  /// Inputs are written and read by the worker thread, compile command can also
262  /// be consumed by clients of ASTWorker.
263  std::shared_ptr<const ParseInputs> FileInputs; /* GUARDED_BY(Mutex) */
264  std::shared_ptr<const PreambleData> LastBuiltPreamble; /* GUARDED_BY(Mutex) */
265  /// Becomes ready when the first preamble build finishes.
266  Notification PreambleWasBuilt;
267  /// Set to true to signal run() to finish processing.
268  bool Done; /* GUARDED_BY(Mutex) */
269  std::deque<Request> Requests; /* GUARDED_BY(Mutex) */
270  mutable std::condition_variable RequestsCV;
271  /// Guards the callback that publishes results of AST-related computations
272  /// (diagnostics, highlightings) and file statuses.
273  std::mutex PublishMu;
274  // Used to prevent remove document + add document races that lead to
275  // out-of-order callbacks for publishing results of onMainAST callback.
276  //
277  // The lifetime of the old/new ASTWorkers will overlap, but their handles
278  // don't. When the old handle is destroyed, the old worker will stop reporting
279  // any results to the user.
280  bool CanPublishResults = true; /* GUARDED_BY(PublishMu) */
281 };
282 
283 /// A smart-pointer-like class that points to an active ASTWorker.
284 /// In destructor, signals to the underlying ASTWorker that no new requests will
285 /// be sent and the processing loop may exit (after running all pending
286 /// requests).
287 class ASTWorkerHandle {
288  friend class ASTWorker;
289  ASTWorkerHandle(std::shared_ptr<ASTWorker> Worker)
290  : Worker(std::move(Worker)) {
291  assert(this->Worker);
292  }
293 
294 public:
295  ASTWorkerHandle(const ASTWorkerHandle &) = delete;
296  ASTWorkerHandle &operator=(const ASTWorkerHandle &) = delete;
297  ASTWorkerHandle(ASTWorkerHandle &&) = default;
298  ASTWorkerHandle &operator=(ASTWorkerHandle &&) = default;
299 
300  ~ASTWorkerHandle() {
301  if (Worker)
302  Worker->stop();
303  }
304 
305  ASTWorker &operator*() {
306  assert(Worker && "Handle was moved from");
307  return *Worker;
308  }
309 
310  ASTWorker *operator->() {
311  assert(Worker && "Handle was moved from");
312  return Worker.get();
313  }
314 
315  /// Returns an owning reference to the underlying ASTWorker that can outlive
316  /// the ASTWorkerHandle. However, no new requests to an active ASTWorker can
317  /// be schedule via the returned reference, i.e. only reads of the preamble
318  /// are possible.
319  std::shared_ptr<const ASTWorker> lock() { return Worker; }
320 
321 private:
322  std::shared_ptr<ASTWorker> Worker;
323 };
324 
325 ASTWorkerHandle
326 ASTWorker::create(PathRef FileName, const GlobalCompilationDatabase &CDB,
327  TUScheduler::ASTCache &IdleASTs, AsyncTaskRunner *Tasks,
328  Semaphore &Barrier, steady_clock::duration UpdateDebounce,
329  bool StorePreamblesInMemory, ParsingCallbacks &Callbacks) {
330  std::shared_ptr<ASTWorker> Worker(
331  new ASTWorker(FileName, CDB, IdleASTs, Barrier, /*RunSync=*/!Tasks,
332  UpdateDebounce, StorePreamblesInMemory, Callbacks));
333  if (Tasks)
334  Tasks->runAsync("worker:" + llvm::sys::path::filename(FileName),
335  [Worker]() { Worker->run(); });
336 
337  return ASTWorkerHandle(std::move(Worker));
338 }
339 
340 ASTWorker::ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB,
341  TUScheduler::ASTCache &LRUCache, Semaphore &Barrier,
342  bool RunSync, steady_clock::duration UpdateDebounce,
343  bool StorePreamblesInMemory, ParsingCallbacks &Callbacks)
344  : IdleASTs(LRUCache), RunSync(RunSync), UpdateDebounce(UpdateDebounce),
345  FileName(FileName), CDB(CDB),
346  StorePreambleInMemory(StorePreamblesInMemory),
347  Callbacks(Callbacks), Status{TUAction(TUAction::Idle, ""),
348  TUStatus::BuildDetails()},
349  Barrier(Barrier), Done(false) {
350  auto Inputs = std::make_shared<ParseInputs>();
351  // Set a fallback command because compile command can be accessed before
352  // `Inputs` is initialized. Other fields are only used after initialization
353  // from client inputs.
354  Inputs->CompileCommand = CDB.getFallbackCommand(FileName);
355  FileInputs = std::move(Inputs);
356 }
357 
358 ASTWorker::~ASTWorker() {
359  // Make sure we remove the cached AST, if any.
360  IdleASTs.take(this);
361 #ifndef NDEBUG
362  std::lock_guard<std::mutex> Lock(Mutex);
363  assert(Done && "handle was not destroyed");
364  assert(Requests.empty() && "unprocessed requests when destroying ASTWorker");
365 #endif
366 }
367 
368 void ASTWorker::update(ParseInputs Inputs, WantDiagnostics WantDiags) {
369  llvm::StringRef TaskName = "Update";
370  auto Task = [=]() mutable {
371  auto RunPublish = [&](llvm::function_ref<void()> Publish) {
372  // Ensure we only publish results from the worker if the file was not
373  // removed, making sure there are not race conditions.
374  std::lock_guard<std::mutex> Lock(PublishMu);
375  if (CanPublishResults)
376  Publish();
377  };
378 
379  // Get the actual command as `Inputs` does not have a command.
380  // FIXME: some build systems like Bazel will take time to preparing
381  // environment to build the file, it would be nice if we could emit a
382  // "PreparingBuild" status to inform users, it is non-trivial given the
383  // current implementation.
384  if (auto Cmd = CDB.getCompileCommand(FileName))
385  Inputs.CompileCommand = *Cmd;
386  else
387  // FIXME: consider using old command if it's not a fallback one.
388  Inputs.CompileCommand = CDB.getFallbackCommand(FileName);
389  auto PrevInputs = getCurrentFileInputs();
390  // Will be used to check if we can avoid rebuilding the AST.
391  bool InputsAreTheSame =
392  std::tie(PrevInputs->CompileCommand, PrevInputs->Contents) ==
393  std::tie(Inputs.CompileCommand, Inputs.Contents);
394 
395  tooling::CompileCommand OldCommand = PrevInputs->CompileCommand;
396  bool RanCallbackForPrevInputs = RanASTCallback;
397  {
398  std::lock_guard<std::mutex> Lock(Mutex);
399  FileInputs = std::make_shared<ParseInputs>(Inputs);
400  }
401  RanASTCallback = false;
402  emitTUStatus({TUAction::BuildingPreamble, TaskName});
403  log("Updating file {0} with command {1}\n[{2}]\n{3}", FileName,
404  Inputs.CompileCommand.Heuristic,
405  Inputs.CompileCommand.Directory,
406  llvm::join(Inputs.CompileCommand.CommandLine, " "));
407  // Rebuild the preamble and the AST.
408  StoreDiags CompilerInvocationDiagConsumer;
409  std::unique_ptr<CompilerInvocation> Invocation =
410  buildCompilerInvocation(Inputs, CompilerInvocationDiagConsumer);
411  std::vector<Diag> CompilerInvocationDiags =
412  CompilerInvocationDiagConsumer.take();
413  if (!Invocation) {
414  elog("Could not build CompilerInvocation for file {0}", FileName);
415  // Remove the old AST if it's still in cache.
416  IdleASTs.take(this);
417  TUStatus::BuildDetails Details;
418  Details.BuildFailed = true;
419  emitTUStatus({TUAction::BuildingPreamble, TaskName}, &Details);
420  // Report the diagnostics we collected when parsing the command line.
421  Callbacks.onFailedAST(FileName, std::move(CompilerInvocationDiags),
422  RunPublish);
423  // Make sure anyone waiting for the preamble gets notified it could not
424  // be built.
425  PreambleWasBuilt.notify();
426  return;
427  }
428 
429  std::shared_ptr<const PreambleData> OldPreamble =
430  getPossiblyStalePreamble();
431  std::shared_ptr<const PreambleData> NewPreamble = buildPreamble(
432  FileName, *Invocation, OldPreamble, OldCommand, Inputs,
433  StorePreambleInMemory,
434  [this](ASTContext &Ctx, std::shared_ptr<clang::Preprocessor> PP,
435  const CanonicalIncludes &CanonIncludes) {
436  Callbacks.onPreambleAST(FileName, Ctx, std::move(PP), CanonIncludes);
437  });
438 
439  bool CanReuseAST = InputsAreTheSame && (OldPreamble == NewPreamble);
440  {
441  std::lock_guard<std::mutex> Lock(Mutex);
442  LastBuiltPreamble = NewPreamble;
443  }
444  // Before doing the expensive AST reparse, we want to release our reference
445  // to the old preamble, so it can be freed if there are no other references
446  // to it.
447  OldPreamble.reset();
448  PreambleWasBuilt.notify();
449  emitTUStatus({TUAction::BuildingFile, TaskName});
450  if (!CanReuseAST) {
451  IdleASTs.take(this); // Remove the old AST if it's still in cache.
452  } else {
453  // We don't need to rebuild the AST, check if we need to run the callback.
454  if (RanCallbackForPrevInputs) {
455  RanASTCallback = true;
456  // Take a shortcut and don't report the diagnostics, since they should
457  // not changed. All the clients should handle the lack of OnUpdated()
458  // call anyway to handle empty result from buildAST.
459  // FIXME(ibiryukov): the AST could actually change if non-preamble
460  // includes changed, but we choose to ignore it.
461  // FIXME(ibiryukov): should we refresh the cache in IdleASTs for the
462  // current file at this point?
463  log("Skipping rebuild of the AST for {0}, inputs are the same.",
464  FileName);
465  TUStatus::BuildDetails Details;
466  Details.ReuseAST = true;
467  emitTUStatus({TUAction::BuildingFile, TaskName}, &Details);
468  return;
469  }
470  }
471 
472  // We only need to build the AST if diagnostics were requested.
473  if (WantDiags == WantDiagnostics::No)
474  return;
475 
476  {
477  std::lock_guard<std::mutex> Lock(PublishMu);
478  // No need to rebuild the AST if we won't send the diagnotics. However,
479  // note that we don't prevent preamble rebuilds.
480  if (!CanPublishResults)
481  return;
482  }
483 
484  // Get the AST for diagnostics.
485  llvm::Optional<std::unique_ptr<ParsedAST>> AST = IdleASTs.take(this);
486  if (!AST) {
487  llvm::Optional<ParsedAST> NewAST =
488  buildAST(FileName, std::move(Invocation), CompilerInvocationDiags,
489  Inputs, NewPreamble);
490  AST = NewAST ? std::make_unique<ParsedAST>(std::move(*NewAST)) : nullptr;
491  if (!(*AST)) { // buildAST fails.
492  TUStatus::BuildDetails Details;
493  Details.BuildFailed = true;
494  emitTUStatus({TUAction::BuildingFile, TaskName}, &Details);
495  }
496  } else {
497  // We are reusing the AST.
498  TUStatus::BuildDetails Details;
499  Details.ReuseAST = true;
500  emitTUStatus({TUAction::BuildingFile, TaskName}, &Details);
501  }
502 
503  // We want to report the diagnostics even if this update was cancelled.
504  // It seems more useful than making the clients wait indefinitely if they
505  // spam us with updates.
506  // Note *AST can still be null if buildAST fails.
507  if (*AST) {
508  trace::Span Span("Running main AST callback");
509 
510  Callbacks.onMainAST(FileName, **AST, RunPublish);
511  RanASTCallback = true;
512  } else {
513  // Failed to build the AST, at least report diagnostics from the command
514  // line if there were any.
515  // FIXME: we might have got more errors while trying to build the AST,
516  // surface them too.
517  Callbacks.onFailedAST(FileName, CompilerInvocationDiags, RunPublish);
518  }
519  // Stash the AST in the cache for further use.
520  IdleASTs.put(this, std::move(*AST));
521  };
522  startTask(TaskName, std::move(Task), WantDiags);
523 }
524 
525 void ASTWorker::runWithAST(
526  llvm::StringRef Name,
527  llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action) {
528  auto Task = [=, Action = std::move(Action)]() mutable {
529  if (isCancelled())
530  return Action(llvm::make_error<CancelledError>());
531  llvm::Optional<std::unique_ptr<ParsedAST>> AST = IdleASTs.take(this);
532  auto CurrentInputs = getCurrentFileInputs();
533  if (!AST) {
534  StoreDiags CompilerInvocationDiagConsumer;
535  std::unique_ptr<CompilerInvocation> Invocation = buildCompilerInvocation(
536  *CurrentInputs, CompilerInvocationDiagConsumer);
537  // Try rebuilding the AST.
538  llvm::Optional<ParsedAST> NewAST =
539  Invocation
540  ? buildAST(FileName,
541  std::make_unique<CompilerInvocation>(*Invocation),
542  CompilerInvocationDiagConsumer.take(), *CurrentInputs,
543  getPossiblyStalePreamble())
544  : None;
545  AST = NewAST ? std::make_unique<ParsedAST>(std::move(*NewAST)) : nullptr;
546  }
547  // Make sure we put the AST back into the LRU cache.
548  auto _ = llvm::make_scope_exit(
549  [&AST, this]() { IdleASTs.put(this, std::move(*AST)); });
550  // Run the user-provided action.
551  if (!*AST)
552  return Action(llvm::make_error<llvm::StringError>(
553  "invalid AST", llvm::errc::invalid_argument));
554  Action(InputsAndAST{*CurrentInputs, **AST});
555  };
556  startTask(Name, std::move(Task), /*UpdateType=*/None);
557 }
558 
559 std::shared_ptr<const PreambleData>
560 ASTWorker::getPossiblyStalePreamble() const {
561  std::lock_guard<std::mutex> Lock(Mutex);
562  return LastBuiltPreamble;
563 }
564 
565 void ASTWorker::getCurrentPreamble(
566  llvm::unique_function<void(std::shared_ptr<const PreambleData>)> Callback) {
567  // We could just call startTask() to throw the read on the queue, knowing
568  // it will run after any updates. But we know this task is cheap, so to
569  // improve latency we cheat: insert it on the queue after the last update.
570  std::unique_lock<std::mutex> Lock(Mutex);
571  auto LastUpdate =
572  std::find_if(Requests.rbegin(), Requests.rend(),
573  [](const Request &R) { return R.UpdateType.hasValue(); });
574  // If there were no writes in the queue, the preamble is ready now.
575  if (LastUpdate == Requests.rend()) {
576  Lock.unlock();
577  return Callback(getPossiblyStalePreamble());
578  }
579  assert(!RunSync && "Running synchronously, but queue is non-empty!");
580  Requests.insert(LastUpdate.base(),
581  Request{[Callback = std::move(Callback), this]() mutable {
582  Callback(getPossiblyStalePreamble());
583  },
584  "GetPreamble", steady_clock::now(),
586  /*UpdateType=*/None});
587  Lock.unlock();
588  RequestsCV.notify_all();
589 }
590 
591 void ASTWorker::waitForFirstPreamble() const { PreambleWasBuilt.wait(); }
592 
593 std::shared_ptr<const ParseInputs> ASTWorker::getCurrentFileInputs() const {
594  std::unique_lock<std::mutex> Lock(Mutex);
595  return FileInputs;
596 }
597 
598 tooling::CompileCommand ASTWorker::getCurrentCompileCommand() const {
599  std::unique_lock<std::mutex> Lock(Mutex);
600  return FileInputs->CompileCommand;
601 }
602 
603 std::size_t ASTWorker::getUsedBytes() const {
604  // Note that we don't report the size of ASTs currently used for processing
605  // the in-flight requests. We used this information for debugging purposes
606  // only, so this should be fine.
607  std::size_t Result = IdleASTs.getUsedBytes(this);
608  if (auto Preamble = getPossiblyStalePreamble())
609  Result += Preamble->Preamble.getSize();
610  return Result;
611 }
612 
613 bool ASTWorker::isASTCached() const { return IdleASTs.getUsedBytes(this) != 0; }
614 
615 void ASTWorker::stop() {
616  {
617  std::lock_guard<std::mutex> Lock(PublishMu);
618  CanPublishResults = false;
619  }
620  {
621  std::lock_guard<std::mutex> Lock(Mutex);
622  assert(!Done && "stop() called twice");
623  Done = true;
624  }
625  RequestsCV.notify_all();
626 }
627 
628 void ASTWorker::startTask(llvm::StringRef Name,
629  llvm::unique_function<void()> Task,
630  llvm::Optional<WantDiagnostics> UpdateType) {
631  if (RunSync) {
632  assert(!Done && "running a task after stop()");
633  trace::Span Tracer(Name + ":" + llvm::sys::path::filename(FileName));
634  Task();
635  return;
636  }
637 
638  {
639  std::lock_guard<std::mutex> Lock(Mutex);
640  assert(!Done && "running a task after stop()");
641  Requests.push_back(
642  {std::move(Task), Name, steady_clock::now(),
643  Context::current().derive(kFileBeingProcessed, FileName), UpdateType});
644  }
645  RequestsCV.notify_all();
646 }
647 
648 void ASTWorker::emitTUStatus(TUAction Action,
649  const TUStatus::BuildDetails *Details) {
650  Status.Action = std::move(Action);
651  if (Details)
652  Status.Details = *Details;
653  std::lock_guard<std::mutex> Lock(PublishMu);
654  // Do not emit TU statuses when the ASTWorker is shutting down.
655  if (CanPublishResults) {
656  Callbacks.onFileUpdated(FileName, Status);
657  }
658 }
659 
660 void ASTWorker::run() {
661  while (true) {
662  Request Req;
663  {
664  std::unique_lock<std::mutex> Lock(Mutex);
665  for (auto Wait = scheduleLocked(); !Wait.expired();
666  Wait = scheduleLocked()) {
667  if (Done) {
668  if (Requests.empty())
669  return;
670  else // Even though Done is set, finish pending requests.
671  break; // However, skip delays to shutdown fast.
672  }
673 
674  // Tracing: we have a next request, attribute this sleep to it.
675  llvm::Optional<WithContext> Ctx;
676  llvm::Optional<trace::Span> Tracer;
677  if (!Requests.empty()) {
678  Ctx.emplace(Requests.front().Ctx.clone());
679  Tracer.emplace("Debounce");
680  SPAN_ATTACH(*Tracer, "next_request", Requests.front().Name);
681  if (!(Wait == Deadline::infinity())) {
682  emitTUStatus({TUAction::Queued, Req.Name});
683  SPAN_ATTACH(*Tracer, "sleep_ms",
684  std::chrono::duration_cast<std::chrono::milliseconds>(
685  Wait.time() - steady_clock::now())
686  .count());
687  }
688  }
689 
690  wait(Lock, RequestsCV, Wait);
691  }
692  Req = std::move(Requests.front());
693  // Leave it on the queue for now, so waiters don't see an empty queue.
694  } // unlock Mutex
695 
696  {
697  std::unique_lock<Semaphore> Lock(Barrier, std::try_to_lock);
698  if (!Lock.owns_lock()) {
699  emitTUStatus({TUAction::Queued, Req.Name});
700  Lock.lock();
701  }
702  WithContext Guard(std::move(Req.Ctx));
703  trace::Span Tracer(Req.Name);
704  emitTUStatus({TUAction::RunningAction, Req.Name});
705  Req.Action();
706  }
707 
708  bool IsEmpty = false;
709  {
710  std::lock_guard<std::mutex> Lock(Mutex);
711  Requests.pop_front();
712  IsEmpty = Requests.empty();
713  }
714  if (IsEmpty)
715  emitTUStatus({TUAction::Idle, /*Name*/ ""});
716  RequestsCV.notify_all();
717  }
718 }
719 
720 Deadline ASTWorker::scheduleLocked() {
721  if (Requests.empty())
722  return Deadline::infinity(); // Wait for new requests.
723  // Handle cancelled requests first so the rest of the scheduler doesn't.
724  for (auto I = Requests.begin(), E = Requests.end(); I != E; ++I) {
725  if (!isCancelled(I->Ctx)) {
726  // Cancellations after the first read don't affect current scheduling.
727  if (I->UpdateType == None)
728  break;
729  continue;
730  }
731  // Cancelled reads are moved to the front of the queue and run immediately.
732  if (I->UpdateType == None) {
733  Request R = std::move(*I);
734  Requests.erase(I);
735  Requests.push_front(std::move(R));
736  return Deadline::zero();
737  }
738  // Cancelled updates are downgraded to auto-diagnostics, and may be elided.
739  if (I->UpdateType == WantDiagnostics::Yes)
740  I->UpdateType = WantDiagnostics::Auto;
741  }
742 
743  while (shouldSkipHeadLocked())
744  Requests.pop_front();
745  assert(!Requests.empty() && "skipped the whole queue");
746  // Some updates aren't dead yet, but never end up being used.
747  // e.g. the first keystroke is live until obsoleted by the second.
748  // We debounce "maybe-unused" writes, sleeping 500ms in case they become dead.
749  // But don't delay reads (including updates where diagnostics are needed).
750  for (const auto &R : Requests)
751  if (R.UpdateType == None || R.UpdateType == WantDiagnostics::Yes)
752  return Deadline::zero();
753  // Front request needs to be debounced, so determine when we're ready.
754  Deadline D(Requests.front().AddTime + UpdateDebounce);
755  return D;
756 }
757 
758 // Returns true if Requests.front() is a dead update that can be skipped.
759 bool ASTWorker::shouldSkipHeadLocked() const {
760  assert(!Requests.empty());
761  auto Next = Requests.begin();
762  auto UpdateType = Next->UpdateType;
763  if (!UpdateType) // Only skip updates.
764  return false;
765  ++Next;
766  // An update is live if its AST might still be read.
767  // That is, if it's not immediately followed by another update.
768  if (Next == Requests.end() || !Next->UpdateType)
769  return false;
770  // The other way an update can be live is if its diagnostics might be used.
771  switch (*UpdateType) {
773  return false; // Always used.
774  case WantDiagnostics::No:
775  return true; // Always dead.
777  // Used unless followed by an update that generates diagnostics.
778  for (; Next != Requests.end(); ++Next)
779  if (Next->UpdateType == WantDiagnostics::Yes ||
780  Next->UpdateType == WantDiagnostics::Auto)
781  return true; // Prefer later diagnostics.
782  return false;
783  }
784  llvm_unreachable("Unknown WantDiagnostics");
785 }
786 
787 bool ASTWorker::blockUntilIdle(Deadline Timeout) const {
788  std::unique_lock<std::mutex> Lock(Mutex);
789  return wait(Lock, RequestsCV, Timeout, [&] { return Requests.empty(); });
790 }
791 
792 // Render a TUAction to a user-facing string representation.
793 // TUAction represents clangd-internal states, we don't intend to expose them
794 // to users (say C++ programmers) directly to avoid confusion, we use terms that
795 // are familiar by C++ programmers.
796 std::string renderTUAction(const TUAction &Action) {
797  std::string Result;
798  llvm::raw_string_ostream OS(Result);
799  switch (Action.S) {
800  case TUAction::Queued:
801  OS << "file is queued";
802  break;
804  OS << "running " << Action.Name;
805  break;
807  OS << "parsing includes";
808  break;
810  OS << "parsing main file";
811  break;
812  case TUAction::Idle:
813  OS << "idle";
814  break;
815  }
816  return OS.str();
817 }
818 
819 } // namespace
820 
822  unsigned HardwareConcurrency = llvm::heavyweight_hardware_concurrency();
823  // heavyweight_hardware_concurrency may fall back to hardware_concurrency.
824  // C++ standard says that hardware_concurrency() may return 0; fallback to 1
825  // worker thread in that case.
826  if (HardwareConcurrency == 0)
827  return 1;
828  return HardwareConcurrency;
829 }
830 
832  FileStatus FStatus;
833  FStatus.uri = URIForFile::canonicalize(File, /*TUPath=*/File);
834  FStatus.state = renderTUAction(Action);
835  return FStatus;
836 }
837 
839  /// Latest inputs, passed to TUScheduler::update().
840  std::string Contents;
841  ASTWorkerHandle Worker;
842 };
843 
845  unsigned AsyncThreadsCount,
846  bool StorePreamblesInMemory,
847  std::unique_ptr<ParsingCallbacks> Callbacks,
848  std::chrono::steady_clock::duration UpdateDebounce,
849  ASTRetentionPolicy RetentionPolicy)
850  : CDB(CDB), StorePreamblesInMemory(StorePreamblesInMemory),
851  Callbacks(Callbacks ? move(Callbacks)
852  : std::make_unique<ParsingCallbacks>()),
853  Barrier(AsyncThreadsCount),
854  IdleASTs(std::make_unique<ASTCache>(RetentionPolicy.MaxRetainedASTs)),
855  UpdateDebounce(UpdateDebounce) {
856  if (0 < AsyncThreadsCount) {
857  PreambleTasks.emplace();
858  WorkerThreads.emplace();
859  }
860 }
861 
863  // Notify all workers that they need to stop.
864  Files.clear();
865 
866  // Wait for all in-flight tasks to finish.
867  if (PreambleTasks)
868  PreambleTasks->wait();
869  if (WorkerThreads)
870  WorkerThreads->wait();
871 }
872 
874  for (auto &File : Files)
875  if (!File.getValue()->Worker->blockUntilIdle(D))
876  return false;
877  if (PreambleTasks)
878  if (!PreambleTasks->wait(D))
879  return false;
880  return true;
881 }
882 
884  WantDiagnostics WantDiags) {
885  std::unique_ptr<FileData> &FD = Files[File];
886  bool NewFile = FD == nullptr;
887  if (!FD) {
888  // Create a new worker to process the AST-related tasks.
889  ASTWorkerHandle Worker = ASTWorker::create(
890  File, CDB, *IdleASTs,
891  WorkerThreads ? WorkerThreads.getPointer() : nullptr, Barrier,
892  UpdateDebounce, StorePreamblesInMemory, *Callbacks);
893  FD = std::unique_ptr<FileData>(
894  new FileData{Inputs.Contents, std::move(Worker)});
895  } else {
896  FD->Contents = Inputs.Contents;
897  }
898  FD->Worker->update(std::move(Inputs), WantDiags);
899  return NewFile;
900 }
901 
903  bool Removed = Files.erase(File);
904  if (!Removed)
905  elog("Trying to remove file from TUScheduler that is not tracked: {0}",
906  File);
907 }
908 
909 llvm::StringRef TUScheduler::getContents(PathRef File) const {
910  auto It = Files.find(File);
911  if (It == Files.end()) {
912  elog("getContents() for untracked file: {0}", File);
913  return "";
914  }
915  return It->second->Contents;
916 }
917 
918 void TUScheduler::run(llvm::StringRef Name,
919  llvm::unique_function<void()> Action) {
920  if (!PreambleTasks)
921  return Action();
922  PreambleTasks->runAsync(Name, std::move(Action));
923 }
924 
926  llvm::StringRef Name, PathRef File,
927  llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action) {
928  auto It = Files.find(File);
929  if (It == Files.end()) {
930  Action(llvm::make_error<LSPError>(
931  "trying to get AST for non-added document", ErrorCode::InvalidParams));
932  return;
933  }
934 
935  It->second->Worker->runWithAST(Name, std::move(Action));
936 }
937 
938 void TUScheduler::runWithPreamble(llvm::StringRef Name, PathRef File,
939  PreambleConsistency Consistency,
941  auto It = Files.find(File);
942  if (It == Files.end()) {
943  Action(llvm::make_error<LSPError>(
944  "trying to get preamble for non-added document",
946  return;
947  }
948 
949  if (!PreambleTasks) {
950  trace::Span Tracer(Name);
951  SPAN_ATTACH(Tracer, "file", File);
952  std::shared_ptr<const PreambleData> Preamble =
953  It->second->Worker->getPossiblyStalePreamble();
954  Action(InputsAndPreamble{It->second->Contents,
955  It->second->Worker->getCurrentCompileCommand(),
956  Preamble.get()});
957  return;
958  }
959 
960  // Future is populated if the task needs a specific preamble.
961  std::future<std::shared_ptr<const PreambleData>> ConsistentPreamble;
962  if (Consistency == Consistent) {
963  std::promise<std::shared_ptr<const PreambleData>> Promise;
964  ConsistentPreamble = Promise.get_future();
965  It->second->Worker->getCurrentPreamble(
966  [Promise = std::move(Promise)](
967  std::shared_ptr<const PreambleData> Preamble) mutable {
968  Promise.set_value(std::move(Preamble));
969  });
970  }
971 
972  std::shared_ptr<const ASTWorker> Worker = It->second->Worker.lock();
973  auto Task = [Worker, Consistency, Name = Name.str(), File = File.str(),
974  Contents = It->second->Contents,
975  Command = Worker->getCurrentCompileCommand(),
976  Ctx = Context::current().derive(kFileBeingProcessed, File),
977  ConsistentPreamble = std::move(ConsistentPreamble),
978  Action = std::move(Action), this]() mutable {
979  std::shared_ptr<const PreambleData> Preamble;
980  if (ConsistentPreamble.valid()) {
981  Preamble = ConsistentPreamble.get();
982  } else {
983  if (Consistency != PreambleConsistency::StaleOrAbsent) {
984  // Wait until the preamble is built for the first time, if preamble is
985  // required. This avoids extra work of processing the preamble headers
986  // in parallel multiple times.
987  Worker->waitForFirstPreamble();
988  }
989  Preamble = Worker->getPossiblyStalePreamble();
990  }
991 
992  std::lock_guard<Semaphore> BarrierLock(Barrier);
993  WithContext Guard(std::move(Ctx));
994  trace::Span Tracer(Name);
995  SPAN_ATTACH(Tracer, "file", File);
996  Action(InputsAndPreamble{Contents, Command, Preamble.get()});
997  };
998 
999  PreambleTasks->runAsync("task:" + llvm::sys::path::filename(File),
1000  std::move(Task));
1001 }
1002 
1003 std::vector<std::pair<Path, std::size_t>>
1005  std::vector<std::pair<Path, std::size_t>> Result;
1006  Result.reserve(Files.size());
1007  for (auto &&PathAndFile : Files)
1008  Result.push_back(
1009  {PathAndFile.first(), PathAndFile.second->Worker->getUsedBytes()});
1010  return Result;
1011 }
1012 
1013 std::vector<Path> TUScheduler::getFilesWithCachedAST() const {
1014  std::vector<Path> Result;
1015  for (auto &&PathAndFile : Files) {
1016  if (!PathAndFile.second->Worker->isASTCached())
1017  continue;
1018  Result.push_back(PathAndFile.first());
1019  }
1020  return Result;
1021 }
1022 
1023 } // namespace clangd
1024 } // namespace clang
PreambleConsistency
Controls whether preamble reads wait for the preamble to be up-to-date.
Definition: TUScheduler.h:198
const tooling::CompileCommand & Command
WantDiagnostics
Determines whether diagnostics should be generated for a file snapshot.
Definition: TUScheduler.h:47
llvm::StringRef Contents
Diagnostics must be generated for this snapshot.
llvm::Optional< ParsedAST > buildAST(PathRef FileName, std::unique_ptr< CompilerInvocation > Invocation, llvm::ArrayRef< Diag > CompilerInvocationDiags, const ParseInputs &Inputs, std::shared_ptr< const PreambleData > Preamble)
Build an AST from provided user inputs.
Definition: ParsedAST.cpp:528
FileStatus render(PathRef File) const
Serialize this to an LSP file status item.
static llvm::Optional< llvm::StringRef > getFileBeingProcessedInContext()
Definition: TUScheduler.cpp:76
bool blockUntilIdle(Deadline D) const
Wait until there are no scheduled or running tasks.
void remove(PathRef File)
Remove File from the list of tracked files and schedule removal of its resources. ...
TUScheduler(const GlobalCompilationDatabase &CDB, unsigned AsyncThreadsCount, bool StorePreamblesInMemory, std::unique_ptr< ParsingCallbacks > ASTCallbacks, std::chrono::steady_clock::duration UpdateDebounce, ASTRetentionPolicy RetentionPolicy)
std::string state
The human-readable string presents the current state of the file, can be shown in the UI (e...
Definition: Protocol.h:1199
llvm::StringRef PathRef
A typedef to represent a ref to file path.
Definition: Path.h:23
Values in a Context are indexed by typed keys.
Definition: Context.h:40
llvm::unique_function< void(llvm::Expected< T >)> Callback
A Callback<T> is a void function that accepts Expected<T>.
Definition: Function.h:28
Documents should not be synced at all.
Limits the number of threads that can acquire the lock at the same time.
Definition: Threading.h:41
URIForFile uri
The text document&#39;s URI.
Definition: Protocol.h:1196
bool update(PathRef File, ParseInputs Inputs, WantDiagnostics WD)
Schedule an update for File.
void elog(const char *Fmt, Ts &&... Vals)
Definition: Logger.h:56
Configuration of the AST retention policy.
Definition: TUScheduler.h:57
bool isCancelled(const Context &Ctx)
True if the current context is within a cancelable task which was cancelled.
std::shared_ptr< const PreambleData > buildPreamble(PathRef FileName, CompilerInvocation &CI, std::shared_ptr< const PreambleData > OldPreamble, const tooling::CompileCommand &OldCompileCommand, const ParseInputs &Inputs, bool StoreInMemory, PreambleParsedCallback PreambleCallback)
Build a preamble for the new inputs unless an old one can be reused.
Definition: Preamble.cpp:120
Provides compilation arguments used for parsing C and C++ files.
Context Ctx
Context clone() const
Clone this context object.
Definition: Context.cpp:20
llvm::Optional< WantDiagnostics > UpdateType
static Deadline infinity()
Definition: Threading.h:63
llvm::unique_function< void()> Action
void log(const char *Fmt, Ts &&... Vals)
Definition: Logger.h:62
void put(Key K, std::unique_ptr< ParsedAST > V)
Store the value in the pool, possibly removing the last used AST.
std::string Path
A typedef to represent a file path.
Definition: Path.h:20
static const Context & current()
Returns the context for the current thread, creating it if needed.
Definition: Context.cpp:27
static URIForFile canonicalize(llvm::StringRef AbsPath, llvm::StringRef TUPath)
Canonicalizes AbsPath via URI.
Definition: Protocol.cpp:32
std::vector< std::pair< Path, std::size_t > > getUsedBytesPerFile() const
Returns estimated memory usage for each of the currently open files.
void runWithPreamble(llvm::StringRef Name, PathRef File, PreambleConsistency Consistency, Callback< InputsAndPreamble > Action)
Schedule an async read of the preamble.
const Decl * D
Definition: XRefs.cpp:847
std::vector< Path > getFilesWithCachedAST() const
Returns a list of files with ASTs currently stored in memory.
PathRef FileName
void wait(std::unique_lock< std::mutex > &Lock, std::condition_variable &CV, Deadline D)
Wait once on CV for the specified duration.
Definition: Threading.cpp:107
std::unique_ptr< CompilerInvocation > buildCompilerInvocation(const ParseInputs &Inputs, clang::DiagnosticConsumer &D)
Builds compiler invocation that could be used to build AST or preamble.
Definition: Compiler.cpp:44
Runs tasks on separate (detached) threads and wait for all tasks to finish.
Definition: Threading.h:105
std::string Name
unsigned getDefaultAsyncThreadsCount()
Returns a number of a default async threads to use for TUScheduler.
WithContext replaces Context::current() with a provided scope.
Definition: Context.h:189
std::string Contents
Latest inputs, passed to TUScheduler::update().
Information required to run clang, e.g. to parse AST or do code completion.
Definition: Compiler.h:44
ASTCache(unsigned MaxRetainedASTs)
Definition: TUScheduler.cpp:90
const PreambleData * Preamble
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
static Deadline zero()
Definition: Threading.h:62
Context derive(const Key< Type > &Key, typename std::decay< Type >::type Value) const &
Derives a child context It is safe to move or destroy a parent context after calling derive()...
Definition: Context.h:121
llvm::Optional< std::unique_ptr< ParsedAST > > take(Key K)
Returns the cached value for K, or llvm::None if the value is not in the cache anymore.
steady_clock::time_point AddTime
static clang::clangd::Key< std::string > kFileBeingProcessed
Definition: TUScheduler.cpp:74
void runWithAST(llvm::StringRef Name, PathRef File, Callback< InputsAndAST > Action)
Schedule an async read of the AST.
A point in time we can wait for.
Definition: Threading.h:58
Clangd extension: indicates the current state of the file in clangd, sent from server via the textDoc...
Definition: Protocol.h:1194
static std::string join(ArrayRef< SpecialMemberFunctionsCheck::SpecialMemberFunctionKind > SMFS, llvm::StringRef AndOr)
An LRU cache of idle ASTs.
Definition: TUScheduler.cpp:86
llvm::StringRef getContents(PathRef File) const
Returns the current contents of the buffer for File, per last update().
Records an event whose duration is the lifetime of the Span object.
Definition: Trace.h:81
#define SPAN_ATTACH(S, Name, Expr)
Attach a key-value pair to a Span event.
Definition: Trace.h:97
Diagnostics must not be generated for this snapshot.
The preamble is generated from the current version of the file.
Definition: TUScheduler.h:203
std::size_t getUsedBytes(Key K)
Returns result of getUsedBytes() for the AST cached by K.
Definition: TUScheduler.cpp:94
void run(llvm::StringRef Name, llvm::unique_function< void()> Action)
Schedule an async task with no dependencies.