llvm-project

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 "Config.h"
53
#include "Diagnostics.h"
54
#include "GlobalCompilationDatabase.h"
55
#include "ParsedAST.h"
56
#include "Preamble.h"
57
#include "clang-include-cleaner/Record.h"
58
#include "support/Cancellation.h"
59
#include "support/Context.h"
60
#include "support/Logger.h"
61
#include "support/MemoryTree.h"
62
#include "support/Path.h"
63
#include "support/ThreadCrashReporter.h"
64
#include "support/Threading.h"
65
#include "support/Trace.h"
66
#include "clang/Basic/Stack.h"
67
#include "clang/Frontend/CompilerInvocation.h"
68
#include "clang/Tooling/CompilationDatabase.h"
69
#include "llvm/ADT/FunctionExtras.h"
70
#include "llvm/ADT/STLExtras.h"
71
#include "llvm/ADT/ScopeExit.h"
72
#include "llvm/ADT/SmallVector.h"
73
#include "llvm/ADT/StringExtras.h"
74
#include "llvm/ADT/StringRef.h"
75
#include "llvm/Support/Allocator.h"
76
#include "llvm/Support/Errc.h"
77
#include "llvm/Support/ErrorHandling.h"
78
#include "llvm/Support/FormatVariadic.h"
79
#include "llvm/Support/Path.h"
80
#include "llvm/Support/Threading.h"
81
#include "llvm/Support/raw_ostream.h"
82
#include <algorithm>
83
#include <atomic>
84
#include <chrono>
85
#include <condition_variable>
86
#include <functional>
87
#include <memory>
88
#include <mutex>
89
#include <optional>
90
#include <queue>
91
#include <string>
92
#include <thread>
93
#include <type_traits>
94
#include <utility>
95
#include <vector>
96

97
namespace clang {
98
namespace clangd {
99
using std::chrono::steady_clock;
100

101
namespace {
102
// Tracks latency (in seconds) of FS operations done during a preamble build.
103
// build_type allows to split by expected VFS cache state (cold on first
104
// preamble, somewhat warm after that when building first preamble for new file,
105
// likely ~everything cached on preamble rebuild.
106
constexpr trace::Metric
107
    PreambleBuildFilesystemLatency("preamble_fs_latency",
108
                                   trace::Metric::Distribution, "build_type");
109
// Tracks latency of FS operations done during a preamble build as a ratio of
110
// preamble build time. build_type is same as above.
111
constexpr trace::Metric PreambleBuildFilesystemLatencyRatio(
112
    "preamble_fs_latency_ratio", trace::Metric::Distribution, "build_type");
113

114
constexpr trace::Metric PreambleBuildSize("preamble_build_size",
115
                                          trace::Metric::Distribution);
116
constexpr trace::Metric PreambleSerializedSize("preamble_serialized_size",
117
                                               trace::Metric::Distribution);
118

119
void reportPreambleBuild(const PreambleBuildStats &Stats,
120
                         bool IsFirstPreamble) {
121
  auto RecordWithLabel = [&Stats](llvm::StringRef Label) {
122
    PreambleBuildFilesystemLatency.record(Stats.FileSystemTime, Label);
123
    if (Stats.TotalBuildTime > 0) // Avoid division by zero.
124
      PreambleBuildFilesystemLatencyRatio.record(
125
          Stats.FileSystemTime / Stats.TotalBuildTime, Label);
126
  };
127

128
  static llvm::once_flag OnceFlag;
129
  llvm::call_once(OnceFlag, [&] { RecordWithLabel("first_build"); });
130
  RecordWithLabel(IsFirstPreamble ? "first_build_for_file" : "rebuild");
131

132
  PreambleBuildSize.record(Stats.BuildSize);
133
  PreambleSerializedSize.record(Stats.SerializedSize);
134
}
135

136
class ASTWorker;
137
} // namespace
138

139
static clang::clangd::Key<std::string> FileBeingProcessed;
140

141
std::optional<llvm::StringRef> TUScheduler::getFileBeingProcessedInContext() {
142
  if (auto *File = Context::current().get(FileBeingProcessed))
143
    return llvm::StringRef(*File);
144
  return std::nullopt;
145
}
146

147
/// An LRU cache of idle ASTs.
148
/// Because we want to limit the overall number of these we retain, the cache
149
/// owns ASTs (and may evict them) while their workers are idle.
150
/// Workers borrow ASTs when active, and return them when done.
151
class TUScheduler::ASTCache {
152
public:
153
  using Key = const ASTWorker *;
154

155
  ASTCache(unsigned MaxRetainedASTs) : MaxRetainedASTs(MaxRetainedASTs) {}
156

157
  /// Returns result of getUsedBytes() for the AST cached by \p K.
158
  /// If no AST is cached, 0 is returned.
159
  std::size_t getUsedBytes(Key K) {
160
    std::lock_guard<std::mutex> Lock(Mut);
161
    auto It = findByKey(K);
162
    if (It == LRU.end() || !It->second)
163
      return 0;
164
    return It->second->getUsedBytes();
165
  }
166

167
  /// Store the value in the pool, possibly removing the last used AST.
168
  /// The value should not be in the pool when this function is called.
169
  void put(Key K, std::unique_ptr<ParsedAST> V) {
170
    std::unique_lock<std::mutex> Lock(Mut);
171
    assert(findByKey(K) == LRU.end());
172

173
    LRU.insert(LRU.begin(), {K, std::move(V)});
174
    if (LRU.size() <= MaxRetainedASTs)
175
      return;
176
    // We're past the limit, remove the last element.
177
    std::unique_ptr<ParsedAST> ForCleanup = std::move(LRU.back().second);
178
    LRU.pop_back();
179
    // Run the expensive destructor outside the lock.
180
    Lock.unlock();
181
    ForCleanup.reset();
182
  }
183

184
  /// Returns the cached value for \p K, or std::nullopt if the value is not in
185
  /// the cache anymore. If nullptr was cached for \p K, this function will
186
  /// return a null unique_ptr wrapped into an optional.
187
  /// If \p AccessMetric is set records whether there was a hit or miss.
188
  std::optional<std::unique_ptr<ParsedAST>>
189
  take(Key K, const trace::Metric *AccessMetric = nullptr) {
190
    // Record metric after unlocking the mutex.
191
    std::unique_lock<std::mutex> Lock(Mut);
192
    auto Existing = findByKey(K);
193
    if (Existing == LRU.end()) {
194
      if (AccessMetric)
195
        AccessMetric->record(1, "miss");
196
      return std::nullopt;
197
    }
198
    if (AccessMetric)
199
      AccessMetric->record(1, "hit");
200
    std::unique_ptr<ParsedAST> V = std::move(Existing->second);
201
    LRU.erase(Existing);
202
    // GCC 4.8 fails to compile `return V;`, as it tries to call the copy
203
    // constructor of unique_ptr, so we call the move ctor explicitly to avoid
204
    // this miscompile.
205
    return std::optional<std::unique_ptr<ParsedAST>>(std::move(V));
206
  }
207

208
private:
209
  using KVPair = std::pair<Key, std::unique_ptr<ParsedAST>>;
210

211
  std::vector<KVPair>::iterator findByKey(Key K) {
212
    return llvm::find_if(LRU, [K](const KVPair &P) { return P.first == K; });
213
  }
214

215
  std::mutex Mut;
216
  unsigned MaxRetainedASTs;
217
  /// Items sorted in LRU order, i.e. first item is the most recently accessed
218
  /// one.
219
  std::vector<KVPair> LRU; /* GUARDED_BY(Mut) */
220
};
221

222
/// A map from header files to an opened "proxy" file that includes them.
223
/// If you open the header, the compile command from the proxy file is used.
224
///
225
/// This inclusion information could also naturally live in the index, but there
226
/// are advantages to using open files instead:
227
///  - it's easier to achieve a *stable* choice of proxy, which is important
228
///    to avoid invalidating the preamble
229
///  - context-sensitive flags for libraries with multiple configurations
230
///    (e.g. C++ stdlib sensitivity to -std version)
231
///  - predictable behavior, e.g. guarantees that go-to-def landing on a header
232
///    will have a suitable command available
233
///  - fewer scaling problems to solve (project include graphs are big!)
234
///
235
/// Implementation details:
236
/// - We only record this for mainfiles where the command was trustworthy
237
///   (i.e. not inferred). This avoids a bad inference "infecting" other files.
238
/// - Once we've picked a proxy file for a header, we stick with it until the
239
///   proxy file is invalidated *and* a new candidate proxy file is built.
240
///   Switching proxies is expensive, as the compile flags will (probably)
241
///   change and therefore we'll end up rebuilding the header's preamble.
242
/// - We don't capture the actual compile command, but just the filename we
243
///   should query to get it. This avoids getting out of sync with the CDB.
244
///
245
/// All methods are threadsafe. In practice, update() comes from preamble
246
/// threads, remove()s mostly from the main thread, and get() from ASTWorker.
247
/// Writes are rare and reads are cheap, so we don't expect much contention.
248
class TUScheduler::HeaderIncluderCache {
249
  // We should be a little careful how we store the include graph of open
250
  // files, as each can have a large number of transitive headers.
251
  // This representation is O(unique transitive source files).
252
  llvm::BumpPtrAllocator Arena;
253
  struct Association {
254
    llvm::StringRef MainFile;
255
    // Circular-linked-list of associations with the same mainFile.
256
    // Null indicates that the mainfile was removed.
257
    Association *Next;
258
  };
259
  llvm::StringMap<Association, llvm::BumpPtrAllocator &> HeaderToMain;
260
  llvm::StringMap<Association *, llvm::BumpPtrAllocator &> MainToFirst;
261
  std::atomic<size_t> UsedBytes; // Updated after writes.
262
  mutable std::mutex Mu;
263

264
  void invalidate(Association *First) {
265
    Association *Current = First;
266
    do {
267
      Association *Next = Current->Next;
268
      Current->Next = nullptr;
269
      Current = Next;
270
    } while (Current != First);
271
  }
272

273
  // Create the circular list and return the head of it.
274
  Association *associate(llvm::StringRef MainFile,
275
                         llvm::ArrayRef<std::string> Headers) {
276
    Association *First = nullptr, *Prev = nullptr;
277
    for (const std::string &Header : Headers) {
278
      auto &Assoc = HeaderToMain[Header];
279
      if (Assoc.Next)
280
        continue; // Already has a valid association.
281

282
      Assoc.MainFile = MainFile;
283
      Assoc.Next = Prev;
284
      Prev = &Assoc;
285
      if (!First)
286
        First = &Assoc;
287
    }
288
    if (First)
289
      First->Next = Prev;
290
    return First;
291
  }
292

293
  void updateMemoryUsage() {
294
    auto StringMapHeap = [](const auto &Map) {
295
      // StringMap stores the hashtable on the heap.
296
      // It contains pointers to the entries, and a hashcode for each.
297
      return Map.getNumBuckets() * (sizeof(void *) + sizeof(unsigned));
298
    };
299
    size_t Usage = Arena.getTotalMemory() + StringMapHeap(MainToFirst) +
300
                   StringMapHeap(HeaderToMain) + sizeof(*this);
301
    UsedBytes.store(Usage, std::memory_order_release);
302
  }
303

304
public:
305
  HeaderIncluderCache() : HeaderToMain(Arena), MainToFirst(Arena) {
306
    updateMemoryUsage();
307
  }
308

309
  // Associate each header with MainFile (unless already associated).
310
  // Headers not in the list will have their associations removed.
311
  void update(PathRef MainFile, llvm::ArrayRef<std::string> Headers) {
312
    std::lock_guard<std::mutex> Lock(Mu);
313
    auto It = MainToFirst.try_emplace(MainFile, nullptr);
314
    Association *&First = It.first->second;
315
    if (First)
316
      invalidate(First);
317
    First = associate(It.first->first(), Headers);
318
    updateMemoryUsage();
319
  }
320

321
  // Mark MainFile as gone.
322
  // This will *not* disassociate headers with MainFile immediately, but they
323
  // will be eligible for association with other files that get update()d.
324
  void remove(PathRef MainFile) {
325
    std::lock_guard<std::mutex> Lock(Mu);
326
    Association *&First = MainToFirst[MainFile];
327
    if (First) {
328
      invalidate(First);
329
      First = nullptr;
330
    }
331
    // MainToFirst entry should stay alive, as Associations might be pointing at
332
    // its key.
333
  }
334

335
  /// Get the mainfile associated with Header, or the empty string if none.
336
  std::string get(PathRef Header) const {
337
    std::lock_guard<std::mutex> Lock(Mu);
338
    return HeaderToMain.lookup(Header).MainFile.str();
339
  }
340

341
  size_t getUsedBytes() const {
342
    return UsedBytes.load(std::memory_order_acquire);
343
  }
344
};
345

346
namespace {
347

348
bool isReliable(const tooling::CompileCommand &Cmd) {
349
  return Cmd.Heuristic.empty();
350
}
351

352
/// Threadsafe manager for updating a TUStatus and emitting it after each
353
/// update.
354
class SynchronizedTUStatus {
355
public:
356
  SynchronizedTUStatus(PathRef FileName, ParsingCallbacks &Callbacks)
357
      : FileName(FileName), Callbacks(Callbacks) {}
358

359
  void update(llvm::function_ref<void(TUStatus &)> Mutator) {
360
    std::lock_guard<std::mutex> Lock(StatusMu);
361
    Mutator(Status);
362
    emitStatusLocked();
363
  }
364

365
  /// Prevents emitting of further updates.
366
  void stop() {
367
    std::lock_guard<std::mutex> Lock(StatusMu);
368
    CanPublish = false;
369
  }
370

371
private:
372
  void emitStatusLocked() {
373
    if (CanPublish)
374
      Callbacks.onFileUpdated(FileName, Status);
375
  }
376

377
  const Path FileName;
378

379
  std::mutex StatusMu;
380
  TUStatus Status;
381
  bool CanPublish = true;
382
  ParsingCallbacks &Callbacks;
383
};
384

385
// An attempt to acquire resources for a task using PreambleThrottler.
386
// Initially it is unsatisfied, it (hopefully) becomes satisfied later but may
387
// be destroyed before then. Destruction releases all resources.
388
class PreambleThrottlerRequest {
389
public:
390
  // The condition variable is signalled when the request is satisfied.
391
  PreambleThrottlerRequest(llvm::StringRef Filename,
392
                           PreambleThrottler *Throttler,
393
                           std::condition_variable &CV)
394
      : Throttler(Throttler),
395
        Satisfied(Throttler == nullptr) {
396
    // If there is no throttler, this dummy request is always satisfied.
397
    if (!Throttler)
398
      return;
399
    ID = Throttler->acquire(Filename, [&] {
400
      Satisfied.store(true, std::memory_order_release);
401
      CV.notify_all();
402
    });
403
  }
404

405
  bool satisfied() const { return Satisfied.load(std::memory_order_acquire); }
406

407
  // When the request is destroyed:
408
  //  - if resources are not yet obtained, stop trying to get them.
409
  //  - if resources were obtained, release them.
410
  ~PreambleThrottlerRequest() {
411
    if (Throttler)
412
      Throttler->release(ID);
413
  }
414

415
private:
416
  PreambleThrottler::RequestID ID;
417
  PreambleThrottler *Throttler;
418
  std::atomic<bool> Satisfied = {false};
419
};
420

421
/// Responsible for building preambles. Whenever the thread is idle and the
422
/// preamble is outdated, it starts to build a fresh preamble from the latest
423
/// inputs. If RunSync is true, preambles are built synchronously in update()
424
/// instead.
425
class PreambleThread {
426
public:
427
  PreambleThread(llvm::StringRef FileName, ParsingCallbacks &Callbacks,
428
                 bool StorePreambleInMemory, bool RunSync,
429
                 PreambleThrottler *Throttler, SynchronizedTUStatus &Status,
430
                 TUScheduler::HeaderIncluderCache &HeaderIncluders,
431
                 ASTWorker &AW)
432
      : FileName(FileName), Callbacks(Callbacks),
433
        StoreInMemory(StorePreambleInMemory), RunSync(RunSync),
434
        Throttler(Throttler), Status(Status), ASTPeer(AW),
435
        HeaderIncluders(HeaderIncluders) {}
436

437
  /// It isn't guaranteed that each requested version will be built. If there
438
  /// are multiple update requests while building a preamble, only the last one
439
  /// will be built.
440
  void update(std::unique_ptr<CompilerInvocation> CI, ParseInputs PI,
441
              std::vector<Diag> CIDiags, WantDiagnostics WantDiags) {
442
    Request Req = {std::move(CI), std::move(PI), std::move(CIDiags), WantDiags,
443
                   Context::current().clone()};
444
    if (RunSync) {
445
      build(std::move(Req));
446
      Status.update([](TUStatus &Status) {
447
        Status.PreambleActivity = PreambleAction::Idle;
448
      });
449
      return;
450
    }
451
    {
452
      std::unique_lock<std::mutex> Lock(Mutex);
453
      // If NextReq was requested with WantDiagnostics::Yes we cannot just drop
454
      // that on the floor. Block until we start building it. This won't
455
      // dead-lock as we are blocking the caller thread, while builds continue
456
      // on preamble thread.
457
      ReqCV.wait(Lock, [this] {
458
        return !NextReq || NextReq->WantDiags != WantDiagnostics::Yes;
459
      });
460
      NextReq = std::move(Req);
461
    }
462
    // Let the worker thread know there's a request, notify_one is safe as there
463
    // should be a single worker thread waiting on it.
464
    ReqCV.notify_all();
465
  }
466

467
  void run() {
468
    // We mark the current as the stack bottom so that clang running on this
469
    // thread can notice the stack usage and prevent stack overflow with best
470
    // efforts. Same applies to other calls thoughout clangd.
471
    clang::noteBottomOfStack();
472
    while (true) {
473
      std::optional<PreambleThrottlerRequest> Throttle;
474
      {
475
        std::unique_lock<std::mutex> Lock(Mutex);
476
        assert(!CurrentReq && "Already processing a request?");
477
        // Wait until stop is called or there is a request.
478
        ReqCV.wait(Lock, [&] { return NextReq || Done; });
479
        if (Done)
480
          break;
481

482
        {
483
          Throttle.emplace(FileName, Throttler, ReqCV);
484
          std::optional<trace::Span> Tracer;
485
          // If acquire succeeded synchronously, avoid status jitter.
486
          if (!Throttle->satisfied()) {
487
            Tracer.emplace("PreambleThrottle");
488
            Status.update([&](TUStatus &Status) {
489
              Status.PreambleActivity = PreambleAction::Queued;
490
            });
491
          }
492
          ReqCV.wait(Lock, [&] { return Throttle->satisfied() || Done; });
493
        }
494
        if (Done)
495
          break;
496
        // While waiting for the throttler, the request may have been updated!
497
        // That's fine though, there's still guaranteed to be some request.
498

499
        CurrentReq = std::move(*NextReq);
500
        NextReq.reset();
501
      }
502

503
      {
504
        WithContext Guard(std::move(CurrentReq->Ctx));
505
        // Note that we don't make use of the ContextProvider here.
506
        // Preamble tasks are always scheduled by ASTWorker tasks, and we
507
        // reuse the context/config that was created at that level.
508

509
        // Build the preamble and let the waiters know about it.
510
        build(std::move(*CurrentReq));
511
      }
512
      // Releasing the throttle before destroying the request assists testing.
513
      Throttle.reset();
514
      bool IsEmpty = false;
515
      {
516
        std::lock_guard<std::mutex> Lock(Mutex);
517
        CurrentReq.reset();
518
        IsEmpty = !NextReq;
519
      }
520
      if (IsEmpty) {
521
        // We don't perform this above, before waiting for a request to make
522
        // tests more deterministic. As there can be a race between this thread
523
        // and client thread(clangdserver).
524
        Status.update([](TUStatus &Status) {
525
          Status.PreambleActivity = PreambleAction::Idle;
526
        });
527
      }
528
      ReqCV.notify_all();
529
    }
530
    dlog("Preamble worker for {0} stopped", FileName);
531
  }
532

533
  /// Signals the run loop to exit.
534
  void stop() {
535
    dlog("Preamble worker for {0} received stop", FileName);
536
    {
537
      std::lock_guard<std::mutex> Lock(Mutex);
538
      Done = true;
539
      NextReq.reset();
540
    }
541
    // Let the worker thread know that it should stop.
542
    ReqCV.notify_all();
543
  }
544

545
  bool blockUntilIdle(Deadline Timeout) const {
546
    std::unique_lock<std::mutex> Lock(Mutex);
547
    return wait(Lock, ReqCV, Timeout, [&] { return !NextReq && !CurrentReq; });
548
  }
549

550
private:
551
  /// Holds inputs required for building a preamble. CI is guaranteed to be
552
  /// non-null.
553
  struct Request {
554
    std::unique_ptr<CompilerInvocation> CI;
555
    ParseInputs Inputs;
556
    std::vector<Diag> CIDiags;
557
    WantDiagnostics WantDiags;
558
    Context Ctx;
559
  };
560

561
  bool isDone() {
562
    std::lock_guard<std::mutex> Lock(Mutex);
563
    return Done;
564
  }
565

566
  /// Builds a preamble for \p Req, might reuse LatestBuild if possible.
567
  /// Notifies ASTWorker after build finishes.
568
  void build(Request Req);
569

570
  mutable std::mutex Mutex;
571
  bool Done = false;                  /* GUARDED_BY(Mutex) */
572
  std::optional<Request> NextReq;     /* GUARDED_BY(Mutex) */
573
  std::optional<Request> CurrentReq;  /* GUARDED_BY(Mutex) */
574
  // Signaled whenever a thread populates NextReq or worker thread builds a
575
  // Preamble.
576
  mutable std::condition_variable ReqCV; /* GUARDED_BY(Mutex) */
577
  // Accessed only by preamble thread.
578
  std::shared_ptr<const PreambleData> LatestBuild;
579

580
  const Path FileName;
581
  ParsingCallbacks &Callbacks;
582
  const bool StoreInMemory;
583
  const bool RunSync;
584
  PreambleThrottler *Throttler;
585

586
  SynchronizedTUStatus &Status;
587
  ASTWorker &ASTPeer;
588
  TUScheduler::HeaderIncluderCache &HeaderIncluders;
589
};
590

591
class ASTWorkerHandle;
592

593
/// Owns one instance of the AST, schedules updates and reads of it.
594
/// Also responsible for building and providing access to the preamble.
595
/// Each ASTWorker processes the async requests sent to it on a separate
596
/// dedicated thread.
597
/// The ASTWorker that manages the AST is shared by both the processing thread
598
/// and the TUScheduler. The TUScheduler should discard an ASTWorker when
599
/// remove() is called, but its thread may be busy and we don't want to block.
600
/// So the workers are accessed via an ASTWorkerHandle. Destroying the handle
601
/// signals the worker to exit its run loop and gives up shared ownership of the
602
/// worker.
603
class ASTWorker {
604
  friend class ASTWorkerHandle;
605
  ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB,
606
            TUScheduler::ASTCache &LRUCache,
607
            TUScheduler::HeaderIncluderCache &HeaderIncluders,
608
            Semaphore &Barrier, bool RunSync, const TUScheduler::Options &Opts,
609
            ParsingCallbacks &Callbacks);
610

611
public:
612
  /// Create a new ASTWorker and return a handle to it.
613
  /// The processing thread is spawned using \p Tasks. However, when \p Tasks
614
  /// is null, all requests will be processed on the calling thread
615
  /// synchronously instead. \p Barrier is acquired when processing each
616
  /// request, it is used to limit the number of actively running threads.
617
  static ASTWorkerHandle
618
  create(PathRef FileName, const GlobalCompilationDatabase &CDB,
619
         TUScheduler::ASTCache &IdleASTs,
620
         TUScheduler::HeaderIncluderCache &HeaderIncluders,
621
         AsyncTaskRunner *Tasks, Semaphore &Barrier,
622
         const TUScheduler::Options &Opts, ParsingCallbacks &Callbacks);
623
  ~ASTWorker();
624

625
  void update(ParseInputs Inputs, WantDiagnostics, bool ContentChanged);
626
  void
627
  runWithAST(llvm::StringRef Name,
628
             llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action,
629
             TUScheduler::ASTActionInvalidation);
630
  bool blockUntilIdle(Deadline Timeout) const;
631

632
  std::shared_ptr<const PreambleData> getPossiblyStalePreamble(
633
      std::shared_ptr<const ASTSignals> *ASTSignals = nullptr) const;
634

635
  /// Used to inform ASTWorker about a new preamble build by PreambleThread.
636
  /// Diagnostics are only published through this callback. This ensures they
637
  /// are always for newer versions of the file, as the callback gets called in
638
  /// the same order as update requests.
639
  void updatePreamble(std::unique_ptr<CompilerInvocation> CI, ParseInputs PI,
640
                      std::shared_ptr<const PreambleData> Preamble,
641
                      std::vector<Diag> CIDiags, WantDiagnostics WantDiags);
642

643
  /// Returns compile command from the current file inputs.
644
  tooling::CompileCommand getCurrentCompileCommand() const;
645

646
  /// Wait for the first build of preamble to finish. Preamble itself can be
647
  /// accessed via getPossiblyStalePreamble(). Note that this function will
648
  /// return after an unsuccessful build of the preamble too, i.e. result of
649
  /// getPossiblyStalePreamble() can be null even after this function returns.
650
  void waitForFirstPreamble() const;
651

652
  TUScheduler::FileStats stats() const;
653
  bool isASTCached() const;
654

655
private:
656
  // Details of an update request that are relevant to scheduling.
657
  struct UpdateType {
658
    // Do we want diagnostics from this version?
659
    // If Yes, we must always build this version.
660
    // If No, we only need to build this version if it's read.
661
    // If Auto, we build if it's read or if the debounce expires.
662
    WantDiagnostics Diagnostics;
663
    // Did the main-file content of the document change?
664
    // If so, we're allowed to cancel certain invalidated preceding reads.
665
    bool ContentChanged;
666
  };
667

668
  /// Publishes diagnostics for \p Inputs. It will build an AST or reuse the
669
  /// cached one if applicable. Assumes LatestPreamble is compatible for \p
670
  /// Inputs.
671
  void generateDiagnostics(std::unique_ptr<CompilerInvocation> Invocation,
672
                           ParseInputs Inputs, std::vector<Diag> CIDiags);
673

674
  void updateASTSignals(ParsedAST &AST);
675

676
  // Must be called exactly once on processing thread. Will return after
677
  // stop() is called on a separate thread and all pending requests are
678
  // processed.
679
  void run();
680
  /// Signal that run() should finish processing pending requests and exit.
681
  void stop();
682

683
  /// Adds a new task to the end of the request queue.
684
  void startTask(llvm::StringRef Name, llvm::unique_function<void()> Task,
685
                 std::optional<UpdateType> Update,
686
                 TUScheduler::ASTActionInvalidation);
687
  /// Runs a task synchronously.
688
  void runTask(llvm::StringRef Name, llvm::function_ref<void()> Task);
689

690
  /// Determines the next action to perform.
691
  /// All actions that should never run are discarded.
692
  /// Returns a deadline for the next action. If it's expired, run now.
693
  /// scheduleLocked() is called again at the deadline, or if requests arrive.
694
  Deadline scheduleLocked();
695
  /// Should the first task in the queue be skipped instead of run?
696
  bool shouldSkipHeadLocked() const;
697

698
  struct Request {
699
    llvm::unique_function<void()> Action;
700
    std::string Name;
701
    steady_clock::time_point AddTime;
702
    Context Ctx;
703
    std::optional<Context> QueueCtx;
704
    std::optional<UpdateType> Update;
705
    TUScheduler::ASTActionInvalidation InvalidationPolicy;
706
    Canceler Invalidate;
707
  };
708

709
  /// Handles retention of ASTs.
710
  TUScheduler::ASTCache &IdleASTs;
711
  TUScheduler::HeaderIncluderCache &HeaderIncluders;
712
  const bool RunSync;
713
  /// Time to wait after an update to see whether another update obsoletes it.
714
  const DebouncePolicy UpdateDebounce;
715
  /// File that ASTWorker is responsible for.
716
  const Path FileName;
717
  /// Callback to create processing contexts for tasks.
718
  const std::function<Context(llvm::StringRef)> ContextProvider;
719
  const GlobalCompilationDatabase &CDB;
720
  /// Callback invoked when preamble or main file AST is built.
721
  ParsingCallbacks &Callbacks;
722

723
  Semaphore &Barrier;
724
  /// Whether the 'onMainAST' callback ran for the current FileInputs.
725
  bool RanASTCallback = false;
726
  /// Guards members used by both TUScheduler and the worker thread.
727
  mutable std::mutex Mutex;
728
  /// File inputs, currently being used by the worker.
729
  /// Writes and reads from unknown threads are locked. Reads from the worker
730
  /// thread are not locked, as it's the only writer.
731
  ParseInputs FileInputs; /* GUARDED_BY(Mutex) */
732
  /// Times of recent AST rebuilds, used for UpdateDebounce computation.
733
  llvm::SmallVector<DebouncePolicy::clock::duration>
734
      RebuildTimes; /* GUARDED_BY(Mutex) */
735
  /// Set to true to signal run() to finish processing.
736
  bool Done;                              /* GUARDED_BY(Mutex) */
737
  std::deque<Request> Requests;           /* GUARDED_BY(Mutex) */
738
  std::optional<Request> CurrentRequest;  /* GUARDED_BY(Mutex) */
739
  /// Signalled whenever a new request has been scheduled or processing of a
740
  /// request has completed.
741
  mutable std::condition_variable RequestsCV;
742
  std::shared_ptr<const ASTSignals> LatestASTSignals; /* GUARDED_BY(Mutex) */
743
  /// Latest build preamble for current TU.
744
  /// std::nullopt means no builds yet, null means there was an error while
745
  /// building. Only written by ASTWorker's thread.
746
  std::optional<std::shared_ptr<const PreambleData>> LatestPreamble;
747
  std::deque<Request> PreambleRequests; /* GUARDED_BY(Mutex) */
748
  /// Signaled whenever LatestPreamble changes state or there's a new
749
  /// PreambleRequest.
750
  mutable std::condition_variable PreambleCV;
751
  /// Guards the callback that publishes results of AST-related computations
752
  /// (diagnostics) and file statuses.
753
  std::mutex PublishMu;
754
  // Used to prevent remove document + add document races that lead to
755
  // out-of-order callbacks for publishing results of onMainAST callback.
756
  //
757
  // The lifetime of the old/new ASTWorkers will overlap, but their handles
758
  // don't. When the old handle is destroyed, the old worker will stop reporting
759
  // any results to the user.
760
  bool CanPublishResults = true; /* GUARDED_BY(PublishMu) */
761
  std::atomic<unsigned> ASTBuildCount = {0};
762
  std::atomic<unsigned> PreambleBuildCount = {0};
763

764
  SynchronizedTUStatus Status;
765
  PreambleThread PreamblePeer;
766
};
767

768
/// A smart-pointer-like class that points to an active ASTWorker.
769
/// In destructor, signals to the underlying ASTWorker that no new requests will
770
/// be sent and the processing loop may exit (after running all pending
771
/// requests).
772
class ASTWorkerHandle {
773
  friend class ASTWorker;
774
  ASTWorkerHandle(std::shared_ptr<ASTWorker> Worker)
775
      : Worker(std::move(Worker)) {
776
    assert(this->Worker);
777
  }
778

779
public:
780
  ASTWorkerHandle(const ASTWorkerHandle &) = delete;
781
  ASTWorkerHandle &operator=(const ASTWorkerHandle &) = delete;
782
  ASTWorkerHandle(ASTWorkerHandle &&) = default;
783
  ASTWorkerHandle &operator=(ASTWorkerHandle &&) = default;
784

785
  ~ASTWorkerHandle() {
786
    if (Worker)
787
      Worker->stop();
788
  }
789

790
  ASTWorker &operator*() {
791
    assert(Worker && "Handle was moved from");
792
    return *Worker;
793
  }
794

795
  ASTWorker *operator->() {
796
    assert(Worker && "Handle was moved from");
797
    return Worker.get();
798
  }
799

800
  /// Returns an owning reference to the underlying ASTWorker that can outlive
801
  /// the ASTWorkerHandle. However, no new requests to an active ASTWorker can
802
  /// be schedule via the returned reference, i.e. only reads of the preamble
803
  /// are possible.
804
  std::shared_ptr<const ASTWorker> lock() { return Worker; }
805

806
private:
807
  std::shared_ptr<ASTWorker> Worker;
808
};
809

810
ASTWorkerHandle
811
ASTWorker::create(PathRef FileName, const GlobalCompilationDatabase &CDB,
812
                  TUScheduler::ASTCache &IdleASTs,
813
                  TUScheduler::HeaderIncluderCache &HeaderIncluders,
814
                  AsyncTaskRunner *Tasks, Semaphore &Barrier,
815
                  const TUScheduler::Options &Opts,
816
                  ParsingCallbacks &Callbacks) {
817
  std::shared_ptr<ASTWorker> Worker(
818
      new ASTWorker(FileName, CDB, IdleASTs, HeaderIncluders, Barrier,
819
                    /*RunSync=*/!Tasks, Opts, Callbacks));
820
  if (Tasks) {
821
    Tasks->runAsync("ASTWorker:" + llvm::sys::path::filename(FileName),
822
                    [Worker]() { Worker->run(); });
823
    Tasks->runAsync("PreambleWorker:" + llvm::sys::path::filename(FileName),
824
                    [Worker]() { Worker->PreamblePeer.run(); });
825
  }
826

827
  return ASTWorkerHandle(std::move(Worker));
828
}
829

830
ASTWorker::ASTWorker(PathRef FileName, const GlobalCompilationDatabase &CDB,
831
                     TUScheduler::ASTCache &LRUCache,
832
                     TUScheduler::HeaderIncluderCache &HeaderIncluders,
833
                     Semaphore &Barrier, bool RunSync,
834
                     const TUScheduler::Options &Opts,
835
                     ParsingCallbacks &Callbacks)
836
    : IdleASTs(LRUCache), HeaderIncluders(HeaderIncluders), RunSync(RunSync),
837
      UpdateDebounce(Opts.UpdateDebounce), FileName(FileName),
838
      ContextProvider(Opts.ContextProvider), CDB(CDB), Callbacks(Callbacks),
839
      Barrier(Barrier), Done(false), Status(FileName, Callbacks),
840
      PreamblePeer(FileName, Callbacks, Opts.StorePreamblesInMemory, RunSync,
841
                   Opts.PreambleThrottler, Status, HeaderIncluders, *this) {
842
  // Set a fallback command because compile command can be accessed before
843
  // `Inputs` is initialized. Other fields are only used after initialization
844
  // from client inputs.
845
  FileInputs.CompileCommand = CDB.getFallbackCommand(FileName);
846
}
847

848
ASTWorker::~ASTWorker() {
849
  // Make sure we remove the cached AST, if any.
850
  IdleASTs.take(this);
851
#ifndef NDEBUG
852
  std::lock_guard<std::mutex> Lock(Mutex);
853
  assert(Done && "handle was not destroyed");
854
  assert(Requests.empty() && !CurrentRequest &&
855
         "unprocessed requests when destroying ASTWorker");
856
#endif
857
}
858

859
void ASTWorker::update(ParseInputs Inputs, WantDiagnostics WantDiags,
860
                       bool ContentChanged) {
861
  llvm::StringLiteral TaskName = "Update";
862
  auto Task = [=]() mutable {
863
    // Get the actual command as `Inputs` does not have a command.
864
    // FIXME: some build systems like Bazel will take time to preparing
865
    // environment to build the file, it would be nice if we could emit a
866
    // "PreparingBuild" status to inform users, it is non-trivial given the
867
    // current implementation.
868
    auto Cmd = CDB.getCompileCommand(FileName);
869
    // If we don't have a reliable command for this file, it may be a header.
870
    // Try to find a file that includes it, to borrow its command.
871
    if (!Cmd || !isReliable(*Cmd)) {
872
      std::string ProxyFile = HeaderIncluders.get(FileName);
873
      if (!ProxyFile.empty()) {
874
        auto ProxyCmd = CDB.getCompileCommand(ProxyFile);
875
        if (!ProxyCmd || !isReliable(*ProxyCmd)) {
876
          // This command is supposed to be reliable! It's probably gone.
877
          HeaderIncluders.remove(ProxyFile);
878
        } else {
879
          // We have a reliable command for an including file, use it.
880
          Cmd = tooling::transferCompileCommand(std::move(*ProxyCmd), FileName);
881
        }
882
      }
883
    }
884
    if (Cmd)
885
      Inputs.CompileCommand = std::move(*Cmd);
886
    else
887
      Inputs.CompileCommand = CDB.getFallbackCommand(FileName);
888

889
    bool InputsAreTheSame =
890
        std::tie(FileInputs.CompileCommand, FileInputs.Contents) ==
891
        std::tie(Inputs.CompileCommand, Inputs.Contents);
892
    // Cached AST is invalidated.
893
    if (!InputsAreTheSame) {
894
      IdleASTs.take(this);
895
      RanASTCallback = false;
896
    }
897

898
    // Update current inputs so that subsequent reads can see them.
899
    {
900
      std::lock_guard<std::mutex> Lock(Mutex);
901
      FileInputs = Inputs;
902
    }
903

904
    log("ASTWorker building file {0} version {1} with command {2}\n[{3}]\n{4}",
905
        FileName, Inputs.Version, Inputs.CompileCommand.Heuristic,
906
        Inputs.CompileCommand.Directory,
907
        printArgv(Inputs.CompileCommand.CommandLine));
908

909
    StoreDiags CompilerInvocationDiagConsumer;
910
    std::vector<std::string> CC1Args;
911
    std::unique_ptr<CompilerInvocation> Invocation = buildCompilerInvocation(
912
        Inputs, CompilerInvocationDiagConsumer, &CC1Args);
913
    // Log cc1 args even (especially!) if creating invocation failed.
914
    if (!CC1Args.empty())
915
      vlog("Driver produced command: cc1 {0}", printArgv(CC1Args));
916
    std::vector<Diag> CompilerInvocationDiags =
917
        CompilerInvocationDiagConsumer.take();
918
    if (!Invocation) {
919
      elog("Could not build CompilerInvocation for file {0}", FileName);
920
      // Remove the old AST if it's still in cache.
921
      IdleASTs.take(this);
922
      RanASTCallback = false;
923
      // Report the diagnostics we collected when parsing the command line.
924
      Callbacks.onFailedAST(FileName, Inputs.Version,
925
                            std::move(CompilerInvocationDiags),
926
                            [&](llvm::function_ref<void()> Publish) {
927
                              // Ensure we only publish results from the worker
928
                              // if the file was not removed, making sure there
929
                              // are not race conditions.
930
                              std::lock_guard<std::mutex> Lock(PublishMu);
931
                              if (CanPublishResults)
932
                                Publish();
933
                            });
934
      // Note that this might throw away a stale preamble that might still be
935
      // useful, but this is how we communicate a build error.
936
      LatestPreamble.emplace();
937
      // Make sure anyone waiting for the preamble gets notified it could not be
938
      // built.
939
      PreambleCV.notify_all();
940
      return;
941
    }
942

943
    // Inform preamble peer, before attempting to build diagnostics so that they
944
    // can be built concurrently.
945
    PreamblePeer.update(std::make_unique<CompilerInvocation>(*Invocation),
946
                        Inputs, CompilerInvocationDiags, WantDiags);
947

948
    // Emit diagnostics from (possibly) stale preamble while waiting for a
949
    // rebuild. Newly built preamble cannot emit diagnostics before this call
950
    // finishes (ast callbacks are called from astpeer thread), hence we
951
    // guarantee eventual consistency.
952
    if (LatestPreamble && WantDiags != WantDiagnostics::No)
953
      generateDiagnostics(std::move(Invocation), std::move(Inputs),
954
                          std::move(CompilerInvocationDiags));
955

956
    std::unique_lock<std::mutex> Lock(Mutex);
957
    PreambleCV.wait(Lock, [this] {
958
      // Block until we reiceve a preamble request, unless a preamble already
959
      // exists, as patching an empty preamble would imply rebuilding it from
960
      // scratch.
961
      // We block here instead of the consumer to prevent any deadlocks. Since
962
      // LatestPreamble is only populated by ASTWorker thread.
963
      return LatestPreamble || !PreambleRequests.empty() || Done;
964
    });
965
  };
966
  startTask(TaskName, std::move(Task), UpdateType{WantDiags, ContentChanged},
967
            TUScheduler::NoInvalidation);
968
}
969

970
void ASTWorker::runWithAST(
971
    llvm::StringRef Name,
972
    llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action,
973
    TUScheduler::ASTActionInvalidation Invalidation) {
974
  // Tracks ast cache accesses for read operations.
975
  static constexpr trace::Metric ASTAccessForRead(
976
      "ast_access_read", trace::Metric::Counter, "result");
977
  auto Task = [=, Action = std::move(Action)]() mutable {
978
    if (auto Reason = isCancelled())
979
      return Action(llvm::make_error<CancelledError>(Reason));
980
    std::optional<std::unique_ptr<ParsedAST>> AST =
981
        IdleASTs.take(this, &ASTAccessForRead);
982
    if (!AST) {
983
      StoreDiags CompilerInvocationDiagConsumer;
984
      std::unique_ptr<CompilerInvocation> Invocation =
985
          buildCompilerInvocation(FileInputs, CompilerInvocationDiagConsumer);
986
      // Try rebuilding the AST.
987
      vlog("ASTWorker rebuilding evicted AST to run {0}: {1} version {2}", Name,
988
           FileName, FileInputs.Version);
989
      // FIXME: We might need to build a patched ast once preamble thread starts
990
      // running async. Currently getPossiblyStalePreamble below will always
991
      // return a compatible preamble as ASTWorker::update blocks.
992
      std::optional<ParsedAST> NewAST;
993
      if (Invocation) {
994
        NewAST = ParsedAST::build(FileName, FileInputs, std::move(Invocation),
995
                                  CompilerInvocationDiagConsumer.take(),
996
                                  getPossiblyStalePreamble());
997
        ++ASTBuildCount;
998
      }
999
      AST = NewAST ? std::make_unique<ParsedAST>(std::move(*NewAST)) : nullptr;
1000
    }
1001
    // Make sure we put the AST back into the LRU cache.
1002
    auto _ = llvm::make_scope_exit(
1003
        [&AST, this]() { IdleASTs.put(this, std::move(*AST)); });
1004
    // Run the user-provided action.
1005
    if (!*AST)
1006
      return Action(error(llvm::errc::invalid_argument, "invalid AST"));
1007
    vlog("ASTWorker running {0} on version {2} of {1}", Name, FileName,
1008
         FileInputs.Version);
1009
    Action(InputsAndAST{FileInputs, **AST});
1010
  };
1011
  startTask(Name, std::move(Task), /*Update=*/std::nullopt, Invalidation);
1012
}
1013

1014
/// To be called from ThreadCrashReporter's signal handler.
1015
static void crashDumpCompileCommand(llvm::raw_ostream &OS,
1016
                                    const tooling::CompileCommand &Command) {
1017
  OS << "  Filename: " << Command.Filename << "\n";
1018
  OS << "  Directory: " << Command.Directory << "\n";
1019
  OS << "  Command Line:";
1020
  for (auto &Arg : Command.CommandLine) {
1021
    OS << " " << Arg;
1022
  }
1023
  OS << "\n";
1024
}
1025

1026
/// To be called from ThreadCrashReporter's signal handler.
1027
static void crashDumpFileContents(llvm::raw_ostream &OS,
1028
                                  const std::string &Contents) {
1029
  // Avoid flooding the terminal with source code by default, but allow clients
1030
  // to opt in. Use an env var to preserve backwards compatibility of the
1031
  // command line interface, while allowing it to be set outside the clangd
1032
  // launch site for more flexibility.
1033
  if (getenv("CLANGD_CRASH_DUMP_SOURCE")) {
1034
    OS << "  Contents:\n";
1035
    OS << Contents << "\n";
1036
  }
1037
}
1038

1039
/// To be called from ThreadCrashReporter's signal handler.
1040
static void crashDumpParseInputs(llvm::raw_ostream &OS,
1041
                                 const ParseInputs &FileInputs) {
1042
  auto &Command = FileInputs.CompileCommand;
1043
  crashDumpCompileCommand(OS, Command);
1044
  OS << "  Version: " << FileInputs.Version << "\n";
1045
  crashDumpFileContents(OS, FileInputs.Contents);
1046
}
1047

1048
void PreambleThread::build(Request Req) {
1049
  assert(Req.CI && "Got preamble request with null compiler invocation");
1050
  const ParseInputs &Inputs = Req.Inputs;
1051
  bool ReusedPreamble = false;
1052

1053
  Status.update([&](TUStatus &Status) {
1054
    Status.PreambleActivity = PreambleAction::Building;
1055
  });
1056
  auto _ = llvm::make_scope_exit([this, &Req, &ReusedPreamble] {
1057
    ASTPeer.updatePreamble(std::move(Req.CI), std::move(Req.Inputs),
1058
                           LatestBuild, std::move(Req.CIDiags),
1059
                           std::move(Req.WantDiags));
1060
    if (!ReusedPreamble)
1061
      Callbacks.onPreamblePublished(FileName);
1062
  });
1063

1064
  if (!LatestBuild || Inputs.ForceRebuild) {
1065
    vlog("Building first preamble for {0} version {1}", FileName,
1066
         Inputs.Version);
1067
  } else if (isPreambleCompatible(*LatestBuild, Inputs, FileName, *Req.CI)) {
1068
    vlog("Reusing preamble version {0} for version {1} of {2}",
1069
         LatestBuild->Version, Inputs.Version, FileName);
1070
    ReusedPreamble = true;
1071
    return;
1072
  } else {
1073
    vlog("Rebuilding invalidated preamble for {0} version {1} (previous was "
1074
         "version {2})",
1075
         FileName, Inputs.Version, LatestBuild->Version);
1076
  }
1077

1078
  ThreadCrashReporter ScopedReporter([&Inputs]() {
1079
    llvm::errs() << "Signalled while building preamble\n";
1080
    crashDumpParseInputs(llvm::errs(), Inputs);
1081
  });
1082

1083
  PreambleBuildStats Stats;
1084
  bool IsFirstPreamble = !LatestBuild;
1085
  LatestBuild = clang::clangd::buildPreamble(
1086
      FileName, *Req.CI, Inputs, StoreInMemory,
1087
      [&](CapturedASTCtx ASTCtx,
1088
          std::shared_ptr<const include_cleaner::PragmaIncludes> PI) {
1089
        Callbacks.onPreambleAST(FileName, Inputs.Version, std::move(ASTCtx),
1090
                                std::move(PI));
1091
      },
1092
      &Stats);
1093
  if (!LatestBuild)
1094
    return;
1095
  reportPreambleBuild(Stats, IsFirstPreamble);
1096
  if (isReliable(LatestBuild->CompileCommand))
1097
    HeaderIncluders.update(FileName, LatestBuild->Includes.allHeaders());
1098
}
1099

1100
void ASTWorker::updatePreamble(std::unique_ptr<CompilerInvocation> CI,
1101
                               ParseInputs PI,
1102
                               std::shared_ptr<const PreambleData> Preamble,
1103
                               std::vector<Diag> CIDiags,
1104
                               WantDiagnostics WantDiags) {
1105
  llvm::StringLiteral TaskName = "Build AST";
1106
  // Store preamble and build diagnostics with new preamble if requested.
1107
  auto Task = [this, Preamble = std::move(Preamble), CI = std::move(CI),
1108
               CIDiags = std::move(CIDiags),
1109
               WantDiags = std::move(WantDiags)]() mutable {
1110
    // Update the preamble inside ASTWorker queue to ensure atomicity. As a task
1111
    // running inside ASTWorker assumes internals won't change until it
1112
    // finishes.
1113
    if (!LatestPreamble || Preamble != *LatestPreamble) {
1114
      ++PreambleBuildCount;
1115
      // Cached AST is no longer valid.
1116
      IdleASTs.take(this);
1117
      RanASTCallback = false;
1118
      std::lock_guard<std::mutex> Lock(Mutex);
1119
      // LatestPreamble might be the last reference to old preamble, do not
1120
      // trigger destructor while holding the lock.
1121
      if (LatestPreamble)
1122
        std::swap(*LatestPreamble, Preamble);
1123
      else
1124
        LatestPreamble = std::move(Preamble);
1125
    }
1126
    // Notify anyone waiting for a preamble.
1127
    PreambleCV.notify_all();
1128
    // Give up our ownership to old preamble before starting expensive AST
1129
    // build.
1130
    Preamble.reset();
1131
    // We only need to build the AST if diagnostics were requested.
1132
    if (WantDiags == WantDiagnostics::No)
1133
      return;
1134
    // Since the file may have been edited since we started building this
1135
    // preamble, we use the current contents of the file instead. This provides
1136
    // more up-to-date diagnostics, and avoids diagnostics going backwards (we
1137
    // may have already emitted staler-preamble diagnostics for the new
1138
    // version).
1139
    // We still have eventual consistency: at some point updatePreamble() will
1140
    // catch up to the current file.
1141
    // Report diagnostics with the new preamble to ensure progress. Otherwise
1142
    // diagnostics might get stale indefinitely if user keeps invalidating the
1143
    // preamble.
1144
    generateDiagnostics(std::move(CI), FileInputs, std::move(CIDiags));
1145
  };
1146
  if (RunSync) {
1147
    runTask(TaskName, Task);
1148
    return;
1149
  }
1150
  {
1151
    std::lock_guard<std::mutex> Lock(Mutex);
1152
    PreambleRequests.push_back({std::move(Task), std::string(TaskName),
1153
                                steady_clock::now(), Context::current().clone(),
1154
                                std::nullopt, std::nullopt,
1155
                                TUScheduler::NoInvalidation, nullptr});
1156
  }
1157
  PreambleCV.notify_all();
1158
  RequestsCV.notify_all();
1159
}
1160

1161
void ASTWorker::updateASTSignals(ParsedAST &AST) {
1162
  auto Signals = std::make_shared<const ASTSignals>(ASTSignals::derive(AST));
1163
  // Existing readers of ASTSignals will have their copy preserved until the
1164
  // read is completed. The last reader deletes the old ASTSignals.
1165
  {
1166
    std::lock_guard<std::mutex> Lock(Mutex);
1167
    std::swap(LatestASTSignals, Signals);
1168
  }
1169
}
1170

1171
void ASTWorker::generateDiagnostics(
1172
    std::unique_ptr<CompilerInvocation> Invocation, ParseInputs Inputs,
1173
    std::vector<Diag> CIDiags) {
1174
  // Tracks ast cache accesses for publishing diags.
1175
  static constexpr trace::Metric ASTAccessForDiag(
1176
      "ast_access_diag", trace::Metric::Counter, "result");
1177
  assert(Invocation);
1178
  assert(LatestPreamble);
1179
  // No need to rebuild the AST if we won't send the diagnostics.
1180
  {
1181
    std::lock_guard<std::mutex> Lock(PublishMu);
1182
    if (!CanPublishResults)
1183
      return;
1184
  }
1185
  // Used to check whether we can update AST cache.
1186
  bool InputsAreLatest =
1187
      std::tie(FileInputs.CompileCommand, FileInputs.Contents) ==
1188
      std::tie(Inputs.CompileCommand, Inputs.Contents);
1189
  // Take a shortcut and don't report the diagnostics, since they should be the
1190
  // same. All the clients should handle the lack of OnUpdated() call anyway to
1191
  // handle empty result from buildAST.
1192
  // FIXME: the AST could actually change if non-preamble includes changed,
1193
  // but we choose to ignore it.
1194
  if (InputsAreLatest && RanASTCallback)
1195
    return;
1196

1197
  // Get the AST for diagnostics, either build it or use the cached one.
1198
  std::string TaskName = llvm::formatv("Build AST ({0})", Inputs.Version);
1199
  Status.update([&](TUStatus &Status) {
1200
    Status.ASTActivity.K = ASTAction::Building;
1201
    Status.ASTActivity.Name = std::move(TaskName);
1202
  });
1203
  // We might be able to reuse the last we've built for a read request.
1204
  // FIXME: It might be better to not reuse this AST. That way queued AST builds
1205
  // won't be required for diags.
1206
  std::optional<std::unique_ptr<ParsedAST>> AST =
1207
      IdleASTs.take(this, &ASTAccessForDiag);
1208
  if (!AST || !InputsAreLatest) {
1209
    auto RebuildStartTime = DebouncePolicy::clock::now();
1210
    std::optional<ParsedAST> NewAST = ParsedAST::build(
1211
        FileName, Inputs, std::move(Invocation), CIDiags, *LatestPreamble);
1212
    auto RebuildDuration = DebouncePolicy::clock::now() - RebuildStartTime;
1213
    ++ASTBuildCount;
1214
    // Try to record the AST-build time, to inform future update debouncing.
1215
    // This is best-effort only: if the lock is held, don't bother.
1216
    std::unique_lock<std::mutex> Lock(Mutex, std::try_to_lock);
1217
    if (Lock.owns_lock()) {
1218
      // Do not let RebuildTimes grow beyond its small-size (i.e.
1219
      // capacity).
1220
      if (RebuildTimes.size() == RebuildTimes.capacity())
1221
        RebuildTimes.erase(RebuildTimes.begin());
1222
      RebuildTimes.push_back(RebuildDuration);
1223
      Lock.unlock();
1224
    }
1225
    Status.update([&](TUStatus &Status) {
1226
      Status.Details.ReuseAST = false;
1227
      Status.Details.BuildFailed = !NewAST;
1228
    });
1229
    AST = NewAST ? std::make_unique<ParsedAST>(std::move(*NewAST)) : nullptr;
1230
  } else {
1231
    log("Skipping rebuild of the AST for {0}, inputs are the same.", FileName);
1232
    Status.update([](TUStatus &Status) {
1233
      Status.Details.ReuseAST = true;
1234
      Status.Details.BuildFailed = false;
1235
    });
1236
  }
1237

1238
  // Publish diagnostics.
1239
  auto RunPublish = [&](llvm::function_ref<void()> Publish) {
1240
    // Ensure we only publish results from the worker if the file was not
1241
    // removed, making sure there are not race conditions.
1242
    std::lock_guard<std::mutex> Lock(PublishMu);
1243
    if (CanPublishResults)
1244
      Publish();
1245
  };
1246
  if (*AST) {
1247
    trace::Span Span("Running main AST callback");
1248
    Callbacks.onMainAST(FileName, **AST, RunPublish);
1249
    updateASTSignals(**AST);
1250
  } else {
1251
    // Failed to build the AST, at least report diagnostics from the
1252
    // command line if there were any.
1253
    // FIXME: we might have got more errors while trying to build the
1254
    // AST, surface them too.
1255
    Callbacks.onFailedAST(FileName, Inputs.Version, CIDiags, RunPublish);
1256
  }
1257

1258
  // AST might've been built for an older version of the source, as ASTWorker
1259
  // queue raced ahead while we were waiting on the preamble. In that case the
1260
  // queue can't reuse the AST.
1261
  if (InputsAreLatest) {
1262
    RanASTCallback = *AST != nullptr;
1263
    IdleASTs.put(this, std::move(*AST));
1264
  }
1265
}
1266

1267
std::shared_ptr<const PreambleData> ASTWorker::getPossiblyStalePreamble(
1268
    std::shared_ptr<const ASTSignals> *ASTSignals) const {
1269
  std::lock_guard<std::mutex> Lock(Mutex);
1270
  if (ASTSignals)
1271
    *ASTSignals = LatestASTSignals;
1272
  return LatestPreamble ? *LatestPreamble : nullptr;
1273
}
1274

1275
void ASTWorker::waitForFirstPreamble() const {
1276
  std::unique_lock<std::mutex> Lock(Mutex);
1277
  PreambleCV.wait(Lock, [this] { return LatestPreamble || Done; });
1278
}
1279

1280
tooling::CompileCommand ASTWorker::getCurrentCompileCommand() const {
1281
  std::unique_lock<std::mutex> Lock(Mutex);
1282
  return FileInputs.CompileCommand;
1283
}
1284

1285
TUScheduler::FileStats ASTWorker::stats() const {
1286
  TUScheduler::FileStats Result;
1287
  Result.ASTBuilds = ASTBuildCount;
1288
  Result.PreambleBuilds = PreambleBuildCount;
1289
  // Note that we don't report the size of ASTs currently used for processing
1290
  // the in-flight requests. We used this information for debugging purposes
1291
  // only, so this should be fine.
1292
  Result.UsedBytesAST = IdleASTs.getUsedBytes(this);
1293
  if (auto Preamble = getPossiblyStalePreamble())
1294
    Result.UsedBytesPreamble = Preamble->Preamble.getSize();
1295
  return Result;
1296
}
1297

1298
bool ASTWorker::isASTCached() const { return IdleASTs.getUsedBytes(this) != 0; }
1299

1300
void ASTWorker::stop() {
1301
  {
1302
    std::lock_guard<std::mutex> Lock(PublishMu);
1303
    CanPublishResults = false;
1304
  }
1305
  {
1306
    std::lock_guard<std::mutex> Lock(Mutex);
1307
    assert(!Done && "stop() called twice");
1308
    Done = true;
1309
  }
1310
  PreamblePeer.stop();
1311
  // We are no longer going to build any preambles, let the waiters know that.
1312
  PreambleCV.notify_all();
1313
  Status.stop();
1314
  RequestsCV.notify_all();
1315
}
1316

1317
void ASTWorker::runTask(llvm::StringRef Name, llvm::function_ref<void()> Task) {
1318
  ThreadCrashReporter ScopedReporter([this, Name]() {
1319
    llvm::errs() << "Signalled during AST worker action: " << Name << "\n";
1320
    crashDumpParseInputs(llvm::errs(), FileInputs);
1321
  });
1322
  trace::Span Tracer(Name);
1323
  WithContext WithProvidedContext(ContextProvider(FileName));
1324
  Task();
1325
}
1326

1327
void ASTWorker::startTask(llvm::StringRef Name,
1328
                          llvm::unique_function<void()> Task,
1329
                          std::optional<UpdateType> Update,
1330
                          TUScheduler::ASTActionInvalidation Invalidation) {
1331
  if (RunSync) {
1332
    assert(!Done && "running a task after stop()");
1333
    runTask(Name, Task);
1334
    return;
1335
  }
1336

1337
  {
1338
    std::lock_guard<std::mutex> Lock(Mutex);
1339
    assert(!Done && "running a task after stop()");
1340
    // Cancel any requests invalidated by this request.
1341
    if (Update && Update->ContentChanged) {
1342
      for (auto &R : llvm::reverse(Requests)) {
1343
        if (R.InvalidationPolicy == TUScheduler::InvalidateOnUpdate)
1344
          R.Invalidate();
1345
        if (R.Update && R.Update->ContentChanged)
1346
          break; // Older requests were already invalidated by the older update.
1347
      }
1348
    }
1349

1350
    // Allow this request to be cancelled if invalidated.
1351
    Context Ctx = Context::current().derive(FileBeingProcessed, FileName);
1352
    Canceler Invalidate = nullptr;
1353
    if (Invalidation) {
1354
      WithContext WC(std::move(Ctx));
1355
      std::tie(Ctx, Invalidate) = cancelableTask(
1356
          /*Reason=*/static_cast<int>(ErrorCode::ContentModified));
1357
    }
1358
    // Trace the time the request spends in the queue, and the requests that
1359
    // it's going to wait for.
1360
    std::optional<Context> QueueCtx;
1361
    if (trace::enabled()) {
1362
      // Tracers that follow threads and need strict nesting will see a tiny
1363
      // instantaneous event "we're enqueueing", and sometime later it runs.
1364
      WithContext WC(Ctx.clone());
1365
      trace::Span Tracer("Queued:" + Name);
1366
      if (Tracer.Args) {
1367
        if (CurrentRequest)
1368
          SPAN_ATTACH(Tracer, "CurrentRequest", CurrentRequest->Name);
1369
        llvm::json::Array PreambleRequestsNames;
1370
        for (const auto &Req : PreambleRequests)
1371
          PreambleRequestsNames.push_back(Req.Name);
1372
        SPAN_ATTACH(Tracer, "PreambleRequestsNames",
1373
                    std::move(PreambleRequestsNames));
1374
        llvm::json::Array RequestsNames;
1375
        for (const auto &Req : Requests)
1376
          RequestsNames.push_back(Req.Name);
1377
        SPAN_ATTACH(Tracer, "RequestsNames", std::move(RequestsNames));
1378
      }
1379
      // For tracers that follow contexts, keep the trace span's context alive
1380
      // until we dequeue the request, so they see the full duration.
1381
      QueueCtx = Context::current().clone();
1382
    }
1383
    Requests.push_back({std::move(Task), std::string(Name), steady_clock::now(),
1384
                        std::move(Ctx), std::move(QueueCtx), Update,
1385
                        Invalidation, std::move(Invalidate)});
1386
  }
1387
  RequestsCV.notify_all();
1388
}
1389

1390
void ASTWorker::run() {
1391
  clang::noteBottomOfStack();
1392
  while (true) {
1393
    {
1394
      std::unique_lock<std::mutex> Lock(Mutex);
1395
      assert(!CurrentRequest && "A task is already running, multiple workers?");
1396
      for (auto Wait = scheduleLocked(); !Wait.expired();
1397
           Wait = scheduleLocked()) {
1398
        assert(PreambleRequests.empty() &&
1399
               "Preamble updates should be scheduled immediately");
1400
        if (Done) {
1401
          if (Requests.empty())
1402
            return;
1403
          // Even though Done is set, finish pending requests.
1404
          break; // However, skip delays to shutdown fast.
1405
        }
1406

1407
        // Tracing: we have a next request, attribute this sleep to it.
1408
        std::optional<WithContext> Ctx;
1409
        std::optional<trace::Span> Tracer;
1410
        if (!Requests.empty()) {
1411
          Ctx.emplace(Requests.front().Ctx.clone());
1412
          Tracer.emplace("Debounce");
1413
          SPAN_ATTACH(*Tracer, "next_request", Requests.front().Name);
1414
          if (!(Wait == Deadline::infinity())) {
1415
            Status.update([&](TUStatus &Status) {
1416
              Status.ASTActivity.K = ASTAction::Queued;
1417
              Status.ASTActivity.Name = Requests.front().Name;
1418
            });
1419
            SPAN_ATTACH(*Tracer, "sleep_ms",
1420
                        std::chrono::duration_cast<std::chrono::milliseconds>(
1421
                            Wait.time() - steady_clock::now())
1422
                            .count());
1423
          }
1424
        }
1425

1426
        wait(Lock, RequestsCV, Wait);
1427
      }
1428
      // Any request in ReceivedPreambles is at least as old as the
1429
      // Requests.front(), so prefer them first to preserve LSP order.
1430
      if (!PreambleRequests.empty()) {
1431
        CurrentRequest = std::move(PreambleRequests.front());
1432
        PreambleRequests.pop_front();
1433
      } else {
1434
        CurrentRequest = std::move(Requests.front());
1435
        Requests.pop_front();
1436
      }
1437
    } // unlock Mutex
1438

1439
    // Inform tracing that the request was dequeued.
1440
    CurrentRequest->QueueCtx.reset();
1441

1442
    // It is safe to perform reads to CurrentRequest without holding the lock as
1443
    // only writer is also this thread.
1444
    {
1445
      std::unique_lock<Semaphore> Lock(Barrier, std::try_to_lock);
1446
      if (!Lock.owns_lock()) {
1447
        Status.update([&](TUStatus &Status) {
1448
          Status.ASTActivity.K = ASTAction::Queued;
1449
          Status.ASTActivity.Name = CurrentRequest->Name;
1450
        });
1451
        Lock.lock();
1452
      }
1453
      WithContext Guard(std::move(CurrentRequest->Ctx));
1454
      Status.update([&](TUStatus &Status) {
1455
        Status.ASTActivity.K = ASTAction::RunningAction;
1456
        Status.ASTActivity.Name = CurrentRequest->Name;
1457
      });
1458
      runTask(CurrentRequest->Name, CurrentRequest->Action);
1459
    }
1460

1461
    bool IsEmpty = false;
1462
    {
1463
      std::lock_guard<std::mutex> Lock(Mutex);
1464
      CurrentRequest.reset();
1465
      IsEmpty = Requests.empty() && PreambleRequests.empty();
1466
    }
1467
    if (IsEmpty) {
1468
      Status.update([&](TUStatus &Status) {
1469
        Status.ASTActivity.K = ASTAction::Idle;
1470
        Status.ASTActivity.Name = "";
1471
      });
1472
    }
1473
    RequestsCV.notify_all();
1474
  }
1475
}
1476

1477
Deadline ASTWorker::scheduleLocked() {
1478
  // Process new preambles immediately.
1479
  if (!PreambleRequests.empty())
1480
    return Deadline::zero();
1481
  if (Requests.empty())
1482
    return Deadline::infinity(); // Wait for new requests.
1483
  // Handle cancelled requests first so the rest of the scheduler doesn't.
1484
  for (auto I = Requests.begin(), E = Requests.end(); I != E; ++I) {
1485
    if (!isCancelled(I->Ctx)) {
1486
      // Cancellations after the first read don't affect current scheduling.
1487
      if (I->Update == std::nullopt)
1488
        break;
1489
      continue;
1490
    }
1491
    // Cancelled reads are moved to the front of the queue and run immediately.
1492
    if (I->Update == std::nullopt) {
1493
      Request R = std::move(*I);
1494
      Requests.erase(I);
1495
      Requests.push_front(std::move(R));
1496
      return Deadline::zero();
1497
    }
1498
    // Cancelled updates are downgraded to auto-diagnostics, and may be elided.
1499
    if (I->Update->Diagnostics == WantDiagnostics::Yes)
1500
      I->Update->Diagnostics = WantDiagnostics::Auto;
1501
  }
1502

1503
  while (shouldSkipHeadLocked()) {
1504
    vlog("ASTWorker skipping {0} for {1}", Requests.front().Name, FileName);
1505
    Requests.pop_front();
1506
  }
1507
  assert(!Requests.empty() && "skipped the whole queue");
1508
  // Some updates aren't dead yet, but never end up being used.
1509
  // e.g. the first keystroke is live until obsoleted by the second.
1510
  // We debounce "maybe-unused" writes, sleeping in case they become dead.
1511
  // But don't delay reads (including updates where diagnostics are needed).
1512
  for (const auto &R : Requests)
1513
    if (R.Update == std::nullopt ||
1514
        R.Update->Diagnostics == WantDiagnostics::Yes)
1515
      return Deadline::zero();
1516
  // Front request needs to be debounced, so determine when we're ready.
1517
  Deadline D(Requests.front().AddTime + UpdateDebounce.compute(RebuildTimes));
1518
  return D;
1519
}
1520

1521
// Returns true if Requests.front() is a dead update that can be skipped.
1522
bool ASTWorker::shouldSkipHeadLocked() const {
1523
  assert(!Requests.empty());
1524
  auto Next = Requests.begin();
1525
  auto Update = Next->Update;
1526
  if (!Update) // Only skip updates.
1527
    return false;
1528
  ++Next;
1529
  // An update is live if its AST might still be read.
1530
  // That is, if it's not immediately followed by another update.
1531
  if (Next == Requests.end() || !Next->Update)
1532
    return false;
1533
  // The other way an update can be live is if its diagnostics might be used.
1534
  switch (Update->Diagnostics) {
1535
  case WantDiagnostics::Yes:
1536
    return false; // Always used.
1537
  case WantDiagnostics::No:
1538
    return true; // Always dead.
1539
  case WantDiagnostics::Auto:
1540
    // Used unless followed by an update that generates diagnostics.
1541
    for (; Next != Requests.end(); ++Next)
1542
      if (Next->Update && Next->Update->Diagnostics != WantDiagnostics::No)
1543
        return true; // Prefer later diagnostics.
1544
    return false;
1545
  }
1546
  llvm_unreachable("Unknown WantDiagnostics");
1547
}
1548

1549
bool ASTWorker::blockUntilIdle(Deadline Timeout) const {
1550
  auto WaitUntilASTWorkerIsIdle = [&] {
1551
    std::unique_lock<std::mutex> Lock(Mutex);
1552
    return wait(Lock, RequestsCV, Timeout, [&] {
1553
      return PreambleRequests.empty() && Requests.empty() && !CurrentRequest;
1554
    });
1555
  };
1556
  // Make sure ASTWorker has processed all requests, which might issue new
1557
  // updates to PreamblePeer.
1558
  if (!WaitUntilASTWorkerIsIdle())
1559
    return false;
1560
  // Now that ASTWorker processed all requests, ensure PreamblePeer has served
1561
  // all update requests. This might create new PreambleRequests for the
1562
  // ASTWorker.
1563
  if (!PreamblePeer.blockUntilIdle(Timeout))
1564
    return false;
1565
  assert(Requests.empty() &&
1566
         "No new normal tasks can be scheduled concurrently with "
1567
         "blockUntilIdle(): ASTWorker isn't threadsafe");
1568
  // Finally make sure ASTWorker has processed all of the preamble updates.
1569
  return WaitUntilASTWorkerIsIdle();
1570
}
1571

1572
// Render a TUAction to a user-facing string representation.
1573
// TUAction represents clangd-internal states, we don't intend to expose them
1574
// to users (say C++ programmers) directly to avoid confusion, we use terms that
1575
// are familiar by C++ programmers.
1576
std::string renderTUAction(const PreambleAction PA, const ASTAction &AA) {
1577
  llvm::SmallVector<std::string, 2> Result;
1578
  switch (PA) {
1579
  case PreambleAction::Building:
1580
    Result.push_back("parsing includes");
1581
    break;
1582
  case PreambleAction::Queued:
1583
    Result.push_back("includes are queued");
1584
    break;
1585
  case PreambleAction::Idle:
1586
    // We handle idle specially below.
1587
    break;
1588
  }
1589
  switch (AA.K) {
1590
  case ASTAction::Queued:
1591
    Result.push_back("file is queued");
1592
    break;
1593
  case ASTAction::RunningAction:
1594
    Result.push_back("running " + AA.Name);
1595
    break;
1596
  case ASTAction::Building:
1597
    Result.push_back("parsing main file");
1598
    break;
1599
  case ASTAction::Idle:
1600
    // We handle idle specially below.
1601
    break;
1602
  }
1603
  if (Result.empty())
1604
    return "idle";
1605
  return llvm::join(Result, ", ");
1606
}
1607

1608
} // namespace
1609

1610
unsigned getDefaultAsyncThreadsCount() {
1611
  return llvm::heavyweight_hardware_concurrency().compute_thread_count();
1612
}
1613

1614
FileStatus TUStatus::render(PathRef File) const {
1615
  FileStatus FStatus;
1616
  FStatus.uri = URIForFile::canonicalize(File, /*TUPath=*/File);
1617
  FStatus.state = renderTUAction(PreambleActivity, ASTActivity);
1618
  return FStatus;
1619
}
1620

1621
struct TUScheduler::FileData {
1622
  /// Latest inputs, passed to TUScheduler::update().
1623
  std::string Contents;
1624
  ASTWorkerHandle Worker;
1625
};
1626

1627
TUScheduler::TUScheduler(const GlobalCompilationDatabase &CDB,
1628
                         const Options &Opts,
1629
                         std::unique_ptr<ParsingCallbacks> Callbacks)
1630
    : CDB(CDB), Opts(Opts),
1631
      Callbacks(Callbacks ? std::move(Callbacks)
1632
                          : std::make_unique<ParsingCallbacks>()),
1633
      Barrier(Opts.AsyncThreadsCount), QuickRunBarrier(Opts.AsyncThreadsCount),
1634
      IdleASTs(
1635
          std::make_unique<ASTCache>(Opts.RetentionPolicy.MaxRetainedASTs)),
1636
      HeaderIncluders(std::make_unique<HeaderIncluderCache>()) {
1637
  // Avoid null checks everywhere.
1638
  if (!Opts.ContextProvider) {
1639
    this->Opts.ContextProvider = [](llvm::StringRef) {
1640
      return Context::current().clone();
1641
    };
1642
  }
1643
  if (0 < Opts.AsyncThreadsCount) {
1644
    PreambleTasks.emplace();
1645
    WorkerThreads.emplace();
1646
  }
1647
}
1648

1649
TUScheduler::~TUScheduler() {
1650
  // Notify all workers that they need to stop.
1651
  Files.clear();
1652

1653
  // Wait for all in-flight tasks to finish.
1654
  if (PreambleTasks)
1655
    PreambleTasks->wait();
1656
  if (WorkerThreads)
1657
    WorkerThreads->wait();
1658
}
1659

1660
bool TUScheduler::blockUntilIdle(Deadline D) const {
1661
  for (auto &File : Files)
1662
    if (!File.getValue()->Worker->blockUntilIdle(D))
1663
      return false;
1664
  if (PreambleTasks)
1665
    if (!PreambleTasks->wait(D))
1666
      return false;
1667
  return true;
1668
}
1669

1670
bool TUScheduler::update(PathRef File, ParseInputs Inputs,
1671
                         WantDiagnostics WantDiags) {
1672
  std::unique_ptr<FileData> &FD = Files[File];
1673
  bool NewFile = FD == nullptr;
1674
  bool ContentChanged = false;
1675
  if (!FD) {
1676
    // Create a new worker to process the AST-related tasks.
1677
    ASTWorkerHandle Worker = ASTWorker::create(
1678
        File, CDB, *IdleASTs, *HeaderIncluders,
1679
        WorkerThreads ? &*WorkerThreads : nullptr, Barrier, Opts, *Callbacks);
1680
    FD = std::unique_ptr<FileData>(
1681
        new FileData{Inputs.Contents, std::move(Worker)});
1682
    ContentChanged = true;
1683
  } else if (FD->Contents != Inputs.Contents) {
1684
    ContentChanged = true;
1685
    FD->Contents = Inputs.Contents;
1686
  }
1687
  FD->Worker->update(std::move(Inputs), WantDiags, ContentChanged);
1688
  // There might be synthetic update requests, don't change the LastActiveFile
1689
  // in such cases.
1690
  if (ContentChanged)
1691
    LastActiveFile = File.str();
1692
  return NewFile;
1693
}
1694

1695
void TUScheduler::remove(PathRef File) {
1696
  bool Removed = Files.erase(File);
1697
  if (!Removed)
1698
    elog("Trying to remove file from TUScheduler that is not tracked: {0}",
1699
         File);
1700
  // We don't call HeaderIncluders.remove(File) here.
1701
  // If we did, we'd avoid potentially stale header/mainfile associations.
1702
  // However, it would mean that closing a mainfile could invalidate the
1703
  // preamble of several open headers.
1704
}
1705

1706
void TUScheduler::run(llvm::StringRef Name, llvm::StringRef Path,
1707
                      llvm::unique_function<void()> Action) {
1708
  runWithSemaphore(Name, Path, std::move(Action), Barrier);
1709
}
1710

1711
void TUScheduler::runQuick(llvm::StringRef Name, llvm::StringRef Path,
1712
                           llvm::unique_function<void()> Action) {
1713
  // Use QuickRunBarrier to serialize quick tasks: we are ignoring
1714
  // the parallelism level set by the user, don't abuse it
1715
  runWithSemaphore(Name, Path, std::move(Action), QuickRunBarrier);
1716
}
1717

1718
void TUScheduler::runWithSemaphore(llvm::StringRef Name, llvm::StringRef Path,
1719
                                   llvm::unique_function<void()> Action,
1720
                                   Semaphore &Sem) {
1721
  if (Path.empty())
1722
    Path = LastActiveFile;
1723
  else
1724
    LastActiveFile = Path.str();
1725
  if (!PreambleTasks) {
1726
    WithContext WithProvidedContext(Opts.ContextProvider(Path));
1727
    return Action();
1728
  }
1729
  PreambleTasks->runAsync(Name, [this, &Sem, Ctx = Context::current().clone(),
1730
                                 Path(Path.str()),
1731
                                 Action = std::move(Action)]() mutable {
1732
    std::lock_guard<Semaphore> BarrierLock(Sem);
1733
    WithContext WC(std::move(Ctx));
1734
    WithContext WithProvidedContext(Opts.ContextProvider(Path));
1735
    Action();
1736
  });
1737
}
1738

1739
void TUScheduler::runWithAST(
1740
    llvm::StringRef Name, PathRef File,
1741
    llvm::unique_function<void(llvm::Expected<InputsAndAST>)> Action,
1742
    TUScheduler::ASTActionInvalidation Invalidation) {
1743
  auto It = Files.find(File);
1744
  if (It == Files.end()) {
1745
    Action(llvm::make_error<LSPError>(
1746
        "trying to get AST for non-added document", ErrorCode::InvalidParams));
1747
    return;
1748
  }
1749
  LastActiveFile = File.str();
1750

1751
  It->second->Worker->runWithAST(Name, std::move(Action), Invalidation);
1752
}
1753

1754
void TUScheduler::runWithPreamble(llvm::StringRef Name, PathRef File,
1755
                                  PreambleConsistency Consistency,
1756
                                  Callback<InputsAndPreamble> Action) {
1757
  auto It = Files.find(File);
1758
  if (It == Files.end()) {
1759
    Action(llvm::make_error<LSPError>(
1760
        "trying to get preamble for non-added document",
1761
        ErrorCode::InvalidParams));
1762
    return;
1763
  }
1764
  LastActiveFile = File.str();
1765

1766
  if (!PreambleTasks) {
1767
    trace::Span Tracer(Name);
1768
    SPAN_ATTACH(Tracer, "file", File);
1769
    std::shared_ptr<const ASTSignals> Signals;
1770
    std::shared_ptr<const PreambleData> Preamble =
1771
        It->second->Worker->getPossiblyStalePreamble(&Signals);
1772
    WithContext WithProvidedContext(Opts.ContextProvider(File));
1773
    Action(InputsAndPreamble{It->second->Contents,
1774
                             It->second->Worker->getCurrentCompileCommand(),
1775
                             Preamble.get(), Signals.get()});
1776
    return;
1777
  }
1778

1779
  std::shared_ptr<const ASTWorker> Worker = It->second->Worker.lock();
1780
  auto Task = [Worker, Consistency, Name = Name.str(), File = File.str(),
1781
               Contents = It->second->Contents,
1782
               Command = Worker->getCurrentCompileCommand(),
1783
               Ctx = Context::current().derive(FileBeingProcessed,
1784
                                               std::string(File)),
1785
               Action = std::move(Action), this]() mutable {
1786
    clang::noteBottomOfStack();
1787
    ThreadCrashReporter ScopedReporter([&Name, &Contents, &Command]() {
1788
      llvm::errs() << "Signalled during preamble action: " << Name << "\n";
1789
      crashDumpCompileCommand(llvm::errs(), Command);
1790
      crashDumpFileContents(llvm::errs(), Contents);
1791
    });
1792
    std::shared_ptr<const PreambleData> Preamble;
1793
    if (Consistency == PreambleConsistency::Stale) {
1794
      // Wait until the preamble is built for the first time, if preamble
1795
      // is required. This avoids extra work of processing the preamble
1796
      // headers in parallel multiple times.
1797
      Worker->waitForFirstPreamble();
1798
    }
1799
    std::shared_ptr<const ASTSignals> Signals;
1800
    Preamble = Worker->getPossiblyStalePreamble(&Signals);
1801

1802
    std::lock_guard<Semaphore> BarrierLock(Barrier);
1803
    WithContext Guard(std::move(Ctx));
1804
    trace::Span Tracer(Name);
1805
    SPAN_ATTACH(Tracer, "file", File);
1806
    WithContext WithProvidedContext(Opts.ContextProvider(File));
1807
    Action(InputsAndPreamble{Contents, Command, Preamble.get(), Signals.get()});
1808
  };
1809

1810
  PreambleTasks->runAsync("task:" + llvm::sys::path::filename(File),
1811
                          std::move(Task));
1812
}
1813

1814
llvm::StringMap<TUScheduler::FileStats> TUScheduler::fileStats() const {
1815
  llvm::StringMap<TUScheduler::FileStats> Result;
1816
  for (const auto &PathAndFile : Files)
1817
    Result.try_emplace(PathAndFile.first(),
1818
                       PathAndFile.second->Worker->stats());
1819
  return Result;
1820
}
1821

1822
std::vector<Path> TUScheduler::getFilesWithCachedAST() const {
1823
  std::vector<Path> Result;
1824
  for (auto &&PathAndFile : Files) {
1825
    if (!PathAndFile.second->Worker->isASTCached())
1826
      continue;
1827
    Result.push_back(std::string(PathAndFile.first()));
1828
  }
1829
  return Result;
1830
}
1831

1832
DebouncePolicy::clock::duration
1833
DebouncePolicy::compute(llvm::ArrayRef<clock::duration> History) const {
1834
  assert(Min <= Max && "Invalid policy");
1835
  if (History.empty())
1836
    return Max; // Arbitrary.
1837

1838
  // Base the result on the median rebuild.
1839
  // nth_element needs a mutable array, take the chance to bound the data size.
1840
  History = History.take_back(15);
1841
  llvm::SmallVector<clock::duration, 15> Recent(History.begin(), History.end());
1842
  auto *Median = Recent.begin() + Recent.size() / 2;
1843
  std::nth_element(Recent.begin(), Median, Recent.end());
1844

1845
  clock::duration Target =
1846
      std::chrono::duration_cast<clock::duration>(RebuildRatio * *Median);
1847
  if (Target > Max)
1848
    return Max;
1849
  if (Target < Min)
1850
    return Min;
1851
  return Target;
1852
}
1853

1854
DebouncePolicy DebouncePolicy::fixed(clock::duration T) {
1855
  DebouncePolicy P;
1856
  P.Min = P.Max = T;
1857
  return P;
1858
}
1859

1860
void TUScheduler::profile(MemoryTree &MT) const {
1861
  for (const auto &Elem : fileStats()) {
1862
    MT.detail(Elem.first())
1863
        .child("preamble")
1864
        .addUsage(Opts.StorePreamblesInMemory ? Elem.second.UsedBytesPreamble
1865
                                              : 0);
1866
    MT.detail(Elem.first()).child("ast").addUsage(Elem.second.UsedBytesAST);
1867
    MT.child("header_includer_cache").addUsage(HeaderIncluders->getUsedBytes());
1868
  }
1869
}
1870
} // namespace clangd
1871
} // namespace clang
1872