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(Value: Stats.FileSystemTime, Label);
123	if (Stats.TotalBuildTime > 0) // Avoid division by zero.
124	PreambleBuildFilesystemLatencyRatio.record(
125	Value: Stats.FileSystemTime / Stats.TotalBuildTime, Label);
126	};
127
128	static llvm::once_flag OnceFlag;
129	llvm::call_once(flag&: OnceFlag, F: [&] { RecordWithLabel("first_build"); });
130	RecordWithLabel(IsFirstPreamble ? "first_build_for_file" : "rebuild");
131
132	PreambleBuildSize.record(Value: Stats.BuildSize);
133	PreambleSerializedSize.record(Value: 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(Key: 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(position: LRU.begin(), x: {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(Value: 1, Label: "miss");
196	return std::nullopt;
197	}
198	if (AccessMetric)
199	AccessMetric->record(Value: 1, Label: "hit");
200	std::unique_ptr<ParsedAST> V = std::move(Existing->second);
201	LRU.erase(position: 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(Range&: LRU, P: [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(i: Usage, m: 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(Key: MainFile, Args: nullptr);
314	Association *&First = It.first->second;
315	if (First)
316	invalidate(First);
317	First = associate(MainFile: 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(Key: Header).MainFile.str();
339	}
340
341	size_t getUsedBytes() const {
342	return UsedBytes.load(m: 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(File: 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(i: true, m: std::memory_order_release);
401	CV.notify_all();
402	});
403	}
404
405	bool satisfied() const { return Satisfied.load(m: 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 = {.CI: std::move(CI), .Inputs: std::move(PI), .CIDiags: std::move(CIDiags), .WantDiags: WantDiags,
443	.Ctx: Context::current().clone()};
444	if (RunSync) {
445	build(Req: std::move(Req));
446	Status.update(Mutator: [](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&: Lock, p: [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&: Lock, p: [&] { return NextReq || Done; });
479	if (Done)
480	break;
481
482	{
483	Throttle.emplace(args: FileName, args&: Throttler, args&: ReqCV);
484	std::optional<trace::Span> Tracer;
485	// If acquire succeeded synchronously, avoid status jitter.
486	if (!Throttle->satisfied()) {
487	Tracer.emplace(args: "PreambleThrottle");
488	Status.update(Mutator: [&](TUStatus &Status) {
489	Status.PreambleActivity = PreambleAction::Queued;
490	});
491	}
492	ReqCV.wait(lock&: Lock, p: [&] { 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(Req: 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(Mutator: [](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, CV&: ReqCV, D: Timeout, F: [&] { 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(Name: "ASTWorker:" + llvm::sys::path::filename(path: FileName),
822	Action: [Worker]() { Worker->run(); });
823	Tasks->runAsync(Name: "PreambleWorker:" + llvm::sys::path::filename(path: FileName),
824	Action: [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(File: FileName);
846	}
847
848	ASTWorker::~ASTWorker() {
849	// Make sure we remove the cached AST, if any.
850	IdleASTs.take(K: 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(File: 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: *Cmd)) {
872	std::string ProxyFile = HeaderIncluders.get(Header: FileName);
873	if (!ProxyFile.empty()) {
874	auto ProxyCmd = CDB.getCompileCommand(File: ProxyFile);
875	if (!ProxyCmd || !isReliable(Cmd: *ProxyCmd)) {
876	// This command is supposed to be reliable! It's probably gone.
877	HeaderIncluders.remove(MainFile: ProxyFile);
878	} else {
879	// We have a reliable command for an including file, use it.
880	Cmd = tooling::transferCompileCommand(std::move(*ProxyCmd), Filename: FileName);
881	}
882	}
883	}
884	if (Cmd)
885	Inputs.CompileCommand = std::move(*Cmd);
886	else
887	Inputs.CompileCommand = CDB.getFallbackCommand(File: FileName);
888
889	bool InputsAreTheSame =
890	std::tie(args&: FileInputs.CompileCommand, args&: FileInputs.Contents) ==
891	std::tie(args&: Inputs.CompileCommand, args&: Inputs.Contents);
892	// Cached AST is invalidated.
893	if (!InputsAreTheSame) {
894	IdleASTs.take(K: 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(Fmt: "ASTWorker building file {0} version {1} with command {2}\n[{3}]\n{4}",
905	Vals: FileName, Vals&: Inputs.Version, Vals&: Inputs.CompileCommand.Heuristic,
906	Vals&: Inputs.CompileCommand.Directory,
907	Vals: printArgv(Args: Inputs.CompileCommand.CommandLine));
908
909	StoreDiags CompilerInvocationDiagConsumer;
910	std::vector<std::string> CC1Args;
911	std::unique_ptr<CompilerInvocation> Invocation = buildCompilerInvocation(
912	Inputs, D&: CompilerInvocationDiagConsumer, CC1Args: &CC1Args);
913	// Log cc1 args even (especially!) if creating invocation failed.
914	if (!CC1Args.empty())
915	vlog(Fmt: "Driver produced command: cc1 {0}", Vals: printArgv(Args: CC1Args));
916	std::vector<Diag> CompilerInvocationDiags =
917	CompilerInvocationDiagConsumer.take();
918	if (!Invocation) {
919	elog(Fmt: "Could not build CompilerInvocation for file {0}", Vals: FileName);
920	// Remove the old AST if it's still in cache.
921	IdleASTs.take(K: this);
922	RanASTCallback = false;
923	// Report the diagnostics we collected when parsing the command line.
924	Callbacks.onFailedAST(Path: FileName, Version: Inputs.Version,
925	Diags: std::move(CompilerInvocationDiags),
926	Publish: [&](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(CI: std::make_unique<CompilerInvocation>(args&: *Invocation),
946	PI: Inputs, CIDiags: 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(Invocation: std::move(Invocation), Inputs: std::move(Inputs),
954	CIDiags: std::move(CompilerInvocationDiags));
955
956	std::unique_lock<std::mutex> Lock(Mutex);
957	PreambleCV.wait(lock&: Lock, p: [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(Name: TaskName, Task: std::move(Task), Update: UpdateType{.Diagnostics: WantDiags, .ContentChanged: 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>(Args&: Reason));
980	std::optional<std::unique_ptr<ParsedAST>> AST =
981	IdleASTs.take(K: this, AccessMetric: &ASTAccessForRead);
982	if (!AST) {
983	StoreDiags CompilerInvocationDiagConsumer;
984	std::unique_ptr<CompilerInvocation> Invocation =
985	buildCompilerInvocation(Inputs: FileInputs, D&: CompilerInvocationDiagConsumer);
986	// Try rebuilding the AST.
987	vlog(Fmt: "ASTWorker rebuilding evicted AST to run {0}: {1} version {2}", Vals&: Name,
988	Vals: FileName, Vals&: 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: FileName, Inputs: FileInputs, CI: std::move(Invocation),
995	CompilerInvocationDiags: CompilerInvocationDiagConsumer.take(),
996	Preamble: getPossiblyStalePreamble());
997	++ASTBuildCount;
998	}
999	AST = NewAST ? std::make_unique<ParsedAST>(args: std::move(*NewAST)) : nullptr;
1000	}
1001	// Make sure we put the AST back into the LRU cache.
1002	auto _ = llvm::make_scope_exit(
1003	F: [&AST, this]() { IdleASTs.put(K: this, V: std::move(*AST)); });
1004	// Run the user-provided action.
1005	if (!*AST)
1006	return Action(error(EC: llvm::errc::invalid_argument, Fmt: "invalid AST"));
1007	vlog(Fmt: "ASTWorker running {0} on version {2} of {1}", Vals&: Name, Vals: FileName,
1008	Vals&: FileInputs.Version);
1009	Action(InputsAndAST{.Inputs: FileInputs, .AST: **AST});
1010	};
1011	startTask(Name, Task: 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(name: "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, Contents: 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(Mutator: [&](TUStatus &Status) {
1054	Status.PreambleActivity = PreambleAction::Building;
1055	});
1056	auto _ = llvm::make_scope_exit(F: [this, &Req, &ReusedPreamble] {
1057	ASTPeer.updatePreamble(CI: std::move(Req.CI), PI: std::move(Req.Inputs),
1058	Preamble: LatestBuild, CIDiags: std::move(Req.CIDiags),
1059	WantDiags: std::move(Req.WantDiags));
1060	if (!ReusedPreamble)
1061	Callbacks.onPreamblePublished(File: FileName);
1062	});
1063
1064	if (!LatestBuild || Inputs.ForceRebuild) {
1065	vlog(Fmt: "Building first preamble for {0} version {1}", Vals: FileName,
1066	Vals: Inputs.Version);
1067	} else if (isPreambleCompatible(Preamble: *LatestBuild, Inputs, FileName, CI: *Req.CI)) {
1068	vlog(Fmt: "Reusing preamble version {0} for version {1} of {2}",
1069	Vals: LatestBuild->Version, Vals: Inputs.Version, Vals: FileName);
1070	ReusedPreamble = true;
1071	return;
1072	} else {
1073	vlog(Fmt: "Rebuilding invalidated preamble for {0} version {1} (previous was "
1074	"version {2})",
1075	Vals: FileName, Vals: Inputs.Version, Vals: LatestBuild->Version);
1076	}
1077
1078	ThreadCrashReporter ScopedReporter([&Inputs]() {
1079	llvm::errs() << "Signalled while building preamble\n";
1080	crashDumpParseInputs(OS&: llvm::errs(), FileInputs: Inputs);
1081	});
1082
1083	PreambleBuildStats Stats;
1084	bool IsFirstPreamble = !LatestBuild;
1085	LatestBuild = clang::clangd::buildPreamble(
1086	FileName, CI: *Req.CI, Inputs, StoreInMemory,
1087	PreambleCallback: [&](CapturedASTCtx ASTCtx,
1088	std::shared_ptr<const include_cleaner::PragmaIncludes> PI) {
1089	Callbacks.onPreambleAST(Path: FileName, Version: Inputs.Version, Ctx: std::move(ASTCtx),
1090	std::move(PI));
1091	},
1092	Stats: &Stats);
1093	if (!LatestBuild)
1094	return;
1095	reportPreambleBuild(Stats, IsFirstPreamble);
1096	if (isReliable(Cmd: LatestBuild->CompileCommand))
1097	HeaderIncluders.update(MainFile: FileName, Headers: 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(K: 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(a&: *LatestPreamble, b&: 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(Invocation: std::move(CI), Inputs: FileInputs, CIDiags: std::move(CIDiags));
1145	};
1146	if (RunSync) {
1147	runTask(Name: TaskName, Task);
1148	return;
1149	}
1150	{
1151	std::lock_guard<std::mutex> Lock(Mutex);
1152	PreambleRequests.push_back(x: {.Action: std::move(Task), .Name: std::string(TaskName),
1153	.AddTime: steady_clock::now(), .Ctx: Context::current().clone(),
1154	.QueueCtx: std::nullopt, .Update: std::nullopt,
1155	.InvalidationPolicy: TUScheduler::NoInvalidation, .Invalidate: 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>(args: 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(a&: LatestASTSignals, b&: 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(args&: FileInputs.CompileCommand, args&: FileInputs.Contents) ==
1188	std::tie(args&: Inputs.CompileCommand, args&: 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(Fmt: "Build AST ({0})", Vals&: Inputs.Version);
1199	Status.update(Mutator: [&](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(K: this, AccessMetric: &ASTAccessForDiag);
1208	if (!AST || !InputsAreLatest) {
1209	auto RebuildStartTime = DebouncePolicy::clock::now();
1210	std::optional<ParsedAST> NewAST = ParsedAST::build(
1211	Filename: FileName, Inputs, CI: std::move(Invocation), CompilerInvocationDiags: CIDiags, Preamble: *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(CI: RebuildTimes.begin());
1222	RebuildTimes.push_back(Elt: RebuildDuration);
1223	Lock.unlock();
1224	}
1225	Status.update(Mutator: [&](TUStatus &Status) {
1226	Status.Details.ReuseAST = false;
1227	Status.Details.BuildFailed = !NewAST;
1228	});
1229	AST = NewAST ? std::make_unique<ParsedAST>(args: std::move(*NewAST)) : nullptr;
1230	} else {
1231	log(Fmt: "Skipping rebuild of the AST for {0}, inputs are the same.", Vals: FileName);
1232	Status.update(Mutator: [](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(Path: FileName, AST&: **AST, Publish: RunPublish);
1249	updateASTSignals(AST&: **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(Path: FileName, Version: Inputs.Version, Diags: CIDiags, Publish: 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(K: this, V: 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&: Lock, p: [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(K: 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(K: 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(OS&: 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(C&: 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(Key: FileBeingProcessed, Value: FileName);
1352	Canceler Invalidate = nullptr;
1353	if (Invalidation) {
1354	WithContext WC(std::move(Ctx));
1355	std::tie(args&: Ctx, args&: 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(E: 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(E: 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(x: {.Action: std::move(Task), .Name: std::string(Name), .AddTime: steady_clock::now(),
1384	.Ctx: std::move(Ctx), .QueueCtx: std::move(QueueCtx), .Update: Update,
1385	.InvalidationPolicy: Invalidation, .Invalidate: 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(args: Requests.front().Ctx.clone());
1412	Tracer.emplace(args: "Debounce");
1413	SPAN_ATTACH(*Tracer, "next_request", Requests.front().Name);
1414	if (!(Wait == Deadline::infinity())) {
1415	Status.update(Mutator: [&](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, CV&: RequestsCV, D: 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(Mutator: [&](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(Mutator: [&](TUStatus &Status) {
1455	Status.ASTActivity.K = ASTAction::RunningAction;
1456	Status.ASTActivity.Name = CurrentRequest->Name;
1457	});
1458	runTask(Name: CurrentRequest->Name, Task: 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(Mutator: [&](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(Ctx: 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(position: I);
1495	Requests.push_front(x: 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(Fmt: "ASTWorker skipping {0} for {1}", Vals&: Requests.front().Name, Vals: 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(History: 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, CV&: RequestsCV, D: Timeout, F: [&] {
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(Elt: "parsing includes");
1581	break;
1582	case PreambleAction::Queued:
1583	Result.push_back(Elt: "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(Elt: "file is queued");
1592	break;
1593	case ASTAction::RunningAction:
1594	Result.push_back(Elt: "running " + AA.Name);
1595	break;
1596	case ASTAction::Building:
1597	Result.push_back(Elt: "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(R&: Result, Separator: ", ");
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(AbsPath: File, /*TUPath=*/File);
1617	FStatus.state = renderTUAction(PA: PreambleActivity, AA: 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>(args: 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(Timeout: 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	FileName: File, CDB, IdleASTs&: *IdleASTs, HeaderIncluders&: *HeaderIncluders,
1679	Tasks: WorkerThreads ? &*WorkerThreads : nullptr, Barrier, Opts, Callbacks&: *Callbacks);
1680	FD = std::unique_ptr<FileData>(
1681	new FileData{.Contents: Inputs.Contents, .Worker: 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(Inputs: 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(Key: File);
1697	if (!Removed)
1698	elog(Fmt: "Trying to remove file from TUScheduler that is not tracked: {0}",
1699	Vals&: 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, Action: std::move(Action), Sem&: 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, Action: std::move(Action), Sem&: 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, Action: [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(Key: File);
1744	if (It == Files.end()) {
1745	Action(llvm::make_error<LSPError>(
1746	Args: "trying to get AST for non-added document", Args: ErrorCode::InvalidParams));
1747	return;
1748	}
1749	LastActiveFile = File.str();
1750
1751	It->second->Worker->runWithAST(Name, Action: 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(Key: File);
1758	if (It == Files.end()) {
1759	Action(llvm::make_error<LSPError>(
1760	Args: "trying to get preamble for non-added document",
1761	Args: 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(ASTSignals: &Signals);
1772	WithContext WithProvidedContext(Opts.ContextProvider(File));
1773	Action(InputsAndPreamble{.Contents: It->second->Contents,
1774	.Command: It->second->Worker->getCurrentCompileCommand(),
1775	.Preamble: Preamble.get(), .Signals: 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(Key: FileBeingProcessed,
1784	Value: 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(OS&: llvm::errs(), Command);
1790	crashDumpFileContents(OS&: 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(ASTSignals: &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: Contents, .Command: Command, .Preamble: Preamble.get(), .Signals: Signals.get()});
1808	};
1809
1810	PreambleTasks->runAsync(Name: "task:" + llvm::sys::path::filename(path: File),
1811	Action: 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(Key: PathAndFile.first(),
1818	Args: 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(x: 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(N: 15);
1841	llvm::SmallVector<clock::duration, 15> Recent(History.begin(), History.end());
1842	auto *Median = Recent.begin() + Recent.size() / 2;
1843	std::nth_element(first: Recent.begin(), nth: Median, last: Recent.end());
1844
1845	clock::duration Target =
1846	std::chrono::duration_cast<clock::duration>(d: 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(Name: Elem.first())
1863	.child(Name: "preamble")
1864	.addUsage(Increment: Opts.StorePreamblesInMemory ? Elem.second.UsedBytesPreamble
1865	: 0);
1866	MT.detail(Name: Elem.first()).child(Name: "ast").addUsage(Increment: Elem.second.UsedBytesAST);
1867	MT.child(Name: "header_includer_cache").addUsage(Increment: HeaderIncluders->getUsedBytes());
1868	}
1869	}
1870	} // namespace clangd
1871	} // namespace clang
1872