1//===--- Background.h - Build an index in a background thread ----*- 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
9#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_BACKGROUND_H
10#define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_BACKGROUND_H
11
12#include "GlobalCompilationDatabase.h"
13#include "SourceCode.h"
14#include "index/BackgroundRebuild.h"
15#include "index/FileIndex.h"
16#include "index/Index.h"
17#include "index/Serialization.h"
18#include "support/Context.h"
19#include "support/MemoryTree.h"
20#include "support/Path.h"
21#include "support/Threading.h"
22#include "support/ThreadsafeFS.h"
23#include "clang/Tooling/CompilationDatabase.h"
24#include "llvm/ADT/StringMap.h"
25#include "llvm/Support/Threading.h"
26#include <atomic>
27#include <condition_variable>
28#include <deque>
29#include <mutex>
30#include <optional>
31#include <queue>
32#include <string>
33#include <thread>
34#include <vector>
35
36namespace clang {
37namespace clangd {
38
39// Handles storage and retrieval of index shards. Both store and load
40// operations can be called from multiple-threads concurrently.
41class BackgroundIndexStorage {
42public:
43 virtual ~BackgroundIndexStorage() = default;
44
45 // Shards of the index are stored and retrieved independently, keyed by shard
46 // identifier - in practice this is a source file name
47 virtual llvm::Error storeShard(llvm::StringRef ShardIdentifier,
48 IndexFileOut Shard) const = 0;
49
50 // Tries to load shard with given identifier, returns nullptr if shard
51 // couldn't be loaded.
52 virtual std::unique_ptr<IndexFileIn>
53 loadShard(llvm::StringRef ShardIdentifier) const = 0;
54
55 // The factory provides storage for each File.
56 // It keeps ownership of the storage instances, and should manage caching
57 // itself. Factory must be threadsafe and never returns nullptr.
58 using Factory = llvm::unique_function<BackgroundIndexStorage *(PathRef)>;
59
60 // Creates an Index Storage that saves shards into disk. Index storage uses
61 // CDBDirectory + ".cache/clangd/index/" as the folder to save shards.
62 // CDBDirectory is the first directory containing a CDB in parent directories
63 // of a file, or user cache directory if none was found, e.g. stdlib headers.
64 static Factory createDiskBackedStorageFactory(
65 std::function<std::optional<ProjectInfo>(PathRef)> GetProjectInfo);
66};
67
68// A priority queue of tasks which can be run on (external) worker threads.
69class BackgroundQueue {
70public:
71 /// A work item on the thread pool's queue.
72 struct Task {
73 explicit Task(std::function<void()> Run) : Run(std::move(Run)) {}
74
75 std::function<void()> Run;
76 llvm::ThreadPriority ThreadPri = llvm::ThreadPriority::Low;
77 unsigned QueuePri = 0; // Higher-priority tasks will run first.
78 std::string Tag; // Allows priority to be boosted later.
79 uint64_t Key = 0; // If the key matches a previous task, drop this one.
80 // (in practice this means we never reindex a file).
81
82 bool operator<(const Task &O) const { return QueuePri < O.QueuePri; }
83 };
84
85 // Describes the number of tasks processed by the queue.
86 struct Stats {
87 unsigned Enqueued = 0; // Total number of tasks ever enqueued.
88 unsigned Active = 0; // Tasks being currently processed by a worker.
89 unsigned Completed = 0; // Tasks that have been finished.
90 unsigned LastIdle = 0; // Number of completed tasks when last empty.
91 };
92
93 BackgroundQueue(std::function<void(Stats)> OnProgress = nullptr)
94 : OnProgress(OnProgress) {}
95
96 // Add tasks to the queue.
97 void push(Task);
98 void append(std::vector<Task>);
99 // Boost priority of current and new tasks with matching Tag, if they are
100 // lower priority.
101 // Reducing the boost of a tag affects future tasks but not current ones.
102 void boost(llvm::StringRef Tag, unsigned NewPriority);
103
104 // Process items on the queue until the queue is stopped.
105 // If the queue becomes empty, OnIdle will be called (on one worker).
106 void work(std::function<void()> OnIdle = nullptr);
107
108 // Stop processing new tasks, allowing all work() calls to return soon.
109 void stop();
110
111 // Disables thread priority lowering to ensure progress on loaded systems.
112 // Only affects tasks that run after the call.
113 static void preventThreadStarvationInTests();
114 [[nodiscard]] bool
115 blockUntilIdleForTest(std::optional<double> TimeoutSeconds);
116
117private:
118 void notifyProgress() const; // Requires lock Mu
119 bool adjust(Task &T);
120
121 std::mutex Mu;
122 Stats Stat;
123 std::condition_variable CV;
124 bool ShouldStop = false;
125 std::vector<Task> Queue; // max-heap
126 llvm::StringMap<unsigned> Boosts;
127 std::function<void(Stats)> OnProgress;
128 llvm::DenseSet<uint64_t> SeenKeys;
129};
130
131// Builds an in-memory index by by running the static indexer action over
132// all commands in a compilation database. Indexing happens in the background.
133// FIXME: it should watch for changes to files on disk.
134class BackgroundIndex : public SwapIndex {
135public:
136 struct Options {
137 // Arbitrary value to ensure some concurrency in tests.
138 // In production an explicit value is specified.
139 size_t ThreadPoolSize = 4;
140 // Thread priority when indexing files.
141 llvm::ThreadPriority IndexingPriority = llvm::ThreadPriority::Low;
142 // Callback that provides notifications as indexing makes progress.
143 std::function<void(BackgroundQueue::Stats)> OnProgress = nullptr;
144 // Function called to obtain the Context to use while indexing the specified
145 // file. Called with the empty string for other tasks.
146 // (When called, the context from BackgroundIndex construction is active).
147 std::function<Context(PathRef)> ContextProvider = nullptr;
148 // Whether the index needs to support the containedRefs() operation.
149 // May use extra memory.
150 bool SupportContainedRefs = true;
151 };
152
153 /// Creates a new background index and starts its threads.
154 /// The current Context will be propagated to each worker thread.
155 BackgroundIndex(const ThreadsafeFS &, const GlobalCompilationDatabase &CDB,
156 BackgroundIndexStorage::Factory IndexStorageFactory,
157 Options Opts);
158 ~BackgroundIndex(); // Blocks while the current task finishes.
159
160 // Enqueue translation units for indexing.
161 // The indexing happens in a background thread, so the symbols will be
162 // available sometime later.
163 void enqueue(const std::vector<std::string> &ChangedFiles) {
164 Queue.push(changedFilesTask(ChangedFiles));
165 }
166
167 /// Boosts priority of indexing related to Path.
168 /// Typically used to index TUs when headers are opened.
169 void boostRelated(llvm::StringRef Path);
170
171 // Cause background threads to stop after ther current task, any remaining
172 // tasks will be discarded.
173 void stop() {
174 Rebuilder.shutdown();
175 Queue.stop();
176 }
177
178 // Wait until the queue is empty, to allow deterministic testing.
179 [[nodiscard]] bool
180 blockUntilIdleForTest(std::optional<double> TimeoutSeconds = 10) {
181 return Queue.blockUntilIdleForTest(TimeoutSeconds);
182 }
183
184 void profile(MemoryTree &MT) const;
185
186private:
187 /// Represents the state of a single file when indexing was performed.
188 struct ShardVersion {
189 FileDigest Digest{._M_elems: {0}};
190 bool HadErrors = false;
191 };
192
193 /// Given index results from a TU, only update symbols coming from files with
194 /// different digests than \p ShardVersionsSnapshot. Also stores new index
195 /// information on IndexStorage.
196 void update(llvm::StringRef MainFile, IndexFileIn Index,
197 const llvm::StringMap<ShardVersion> &ShardVersionsSnapshot,
198 bool HadErrors);
199
200 // configuration
201 const ThreadsafeFS &TFS;
202 const GlobalCompilationDatabase &CDB;
203 llvm::ThreadPriority IndexingPriority;
204 std::function<Context(PathRef)> ContextProvider;
205
206 llvm::Error index(tooling::CompileCommand);
207
208 FileSymbols IndexedSymbols;
209 BackgroundIndexRebuilder Rebuilder;
210 llvm::StringMap<ShardVersion> ShardVersions; // Key is absolute file path.
211 std::mutex ShardVersionsMu;
212
213 BackgroundIndexStorage::Factory IndexStorageFactory;
214 // Tries to load shards for the MainFiles and their dependencies.
215 std::vector<std::string> loadProject(std::vector<std::string> MainFiles);
216
217 BackgroundQueue::Task
218 changedFilesTask(const std::vector<std::string> &ChangedFiles);
219 BackgroundQueue::Task indexFileTask(std::string Path);
220
221 // from lowest to highest priority
222 enum QueuePriority {
223 IndexFile,
224 IndexBoostedFile,
225 LoadShards,
226 };
227 BackgroundQueue Queue;
228 AsyncTaskRunner ThreadPool;
229 GlobalCompilationDatabase::CommandChanged::Subscription CommandsChanged;
230};
231
232} // namespace clangd
233} // namespace clang
234
235#endif
236

source code of clang-tools-extra/clangd/index/Background.h