Debian Codegraph @

llvm-project/clang-tools-extra/clangd/index/Background.cpp

raw
1 //===-- Background.cpp - Build an index in a background thread ------------===//
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 #include "index/Background.h"
10 #include "Compiler.h"
11 #include "Config.h"
12 #include "Headers.h"
13 #include "SourceCode.h"
14 #include "URI.h"
15 #include "index/BackgroundIndexLoader.h"
16 #include "index/FileIndex.h"
17 #include "index/Index.h"
18 #include "index/IndexAction.h"
19 #include "index/MemIndex.h"
20 #include "index/Ref.h"
21 #include "index/Relation.h"
22 #include "index/Serialization.h"
23 #include "index/Symbol.h"
24 #include "index/SymbolCollector.h"
25 #include "support/Context.h"
26 #include "support/Logger.h"
27 #include "support/Path.h"
28 #include "support/Threading.h"
29 #include "support/ThreadsafeFS.h"
30 #include "support/Trace.h"
31 #include "clang/Basic/SourceLocation.h"
32 #include "clang/Basic/SourceManager.h"
33 #include "clang/Frontend/FrontendAction.h"
34 #include "llvm/ADT/ArrayRef.h"
35 #include "llvm/ADT/DenseSet.h"
36 #include "llvm/ADT/STLExtras.h"
37 #include "llvm/ADT/StringMap.h"
38 #include "llvm/ADT/StringRef.h"
39 #include "llvm/Support/Error.h"
40 #include "llvm/Support/Path.h"
41 #include "llvm/Support/Threading.h"
42 #include "llvm/Support/xxhash.h"
43
44 #include <algorithm>
45 #include <atomic>
46 #include <chrono>
47 #include <condition_variable>
48 #include <cstddef>
49 #include <memory>
50 #include <mutex>
51 #include <numeric>
52 #include <optional>
53 #include <queue>
54 #include <random>
55 #include <string>
56 #include <thread>
57 #include <utility>
58 #include <vector>
59
60 namespace clang {
61 namespace clangd {
62 namespace {
63
64 // We cannot use vfs->makeAbsolute because Cmd.FileName is either absolute or
65 // relative to Cmd.Directory, which might not be the same as current working
66 // directory.
67 llvm::SmallString<128> getAbsolutePath(const tooling::CompileCommand &Cmd) {
68 llvm::SmallString<128> AbsolutePath;
69 if (llvm::sys::path::is_absolute(Cmd.Filename)) {
70 AbsolutePath = Cmd.Filename;
71 } else {
72 AbsolutePath = Cmd.Directory;
73 llvm::sys::path::append(AbsolutePath, Cmd.Filename);
74 llvm::sys::path::remove_dots(AbsolutePath, true);
75 }
76 return AbsolutePath;
77 }
78
79 bool shardIsStale(const LoadedShard &LS, llvm::vfs::FileSystem *FS) {
80 auto Buf = FS->getBufferForFile(LS.AbsolutePath);
81 if (!Buf) {
82 vlog("Background-index: Couldn't read {0} to validate stored index: {1}",
83 LS.AbsolutePath, Buf.getError().message());
84 // There is no point in indexing an unreadable file.
85 return false;
86 }
87 return digest(Buf->get()->getBuffer()) != LS.Digest;
88 }
89
90 } // namespace
91
92 BackgroundIndex::BackgroundIndex(
93 const ThreadsafeFS &TFS, const GlobalCompilationDatabase &CDB,
94 BackgroundIndexStorage::Factory IndexStorageFactory, Options Opts)
95 : SwapIndex(std::make_unique<MemIndex>()), TFS(TFS), CDB(CDB),
96 IndexingPriority(Opts.IndexingPriority),
97 ContextProvider(std::move(Opts.ContextProvider)),
98 IndexedSymbols(IndexContents::All),
99 Rebuilder(this, &IndexedSymbols, Opts.ThreadPoolSize),
100 IndexStorageFactory(std::move(IndexStorageFactory)),
101 Queue(std::move(Opts.OnProgress)),
102 CommandsChanged(
103 CDB.watch([&](const std::vector<std::string> &ChangedFiles) {
104 enqueue(ChangedFiles);
105 })) {
106 assert(Opts.ThreadPoolSize > 0 && "Thread pool size can't be zero.");
107 assert(this->IndexStorageFactory && "Storage factory can not be null!");
108 for (unsigned I = 0; I < Opts.ThreadPoolSize; ++I) {
109 ThreadPool.runAsync("background-worker-" + llvm::Twine(I + 1),
110 [this, Ctx(Context::current().clone())]() mutable {
111 WithContext BGContext(std::move(Ctx));
112 Queue.work([&] { Rebuilder.idle(); });
113 });
114 }
115 }
116
117 BackgroundIndex::~BackgroundIndex() {
118 stop();
119 ThreadPool.wait();
120 }
121
122 BackgroundQueue::Task BackgroundIndex::changedFilesTask(
123 const std::vector<std::string> &ChangedFiles) {
124 BackgroundQueue::Task T([this, ChangedFiles] {
125 trace::Span Tracer("BackgroundIndexEnqueue");
126
127 std::optional<WithContext> WithProvidedContext;
128 if (ContextProvider)
129 WithProvidedContext.emplace(ContextProvider(/*Path=*/""));
130
131 // We're doing this asynchronously, because we'll read shards here too.
132 log("Enqueueing {0} commands for indexing", ChangedFiles.size());
133 SPAN_ATTACH(Tracer, "files", int64_t(ChangedFiles.size()));
134
135 auto NeedsReIndexing = loadProject(std::move(ChangedFiles));
136 // Run indexing for files that need to be updated.
137 std::shuffle(NeedsReIndexing.begin(), NeedsReIndexing.end(),
138 std::mt19937(std::random_device{}()));
139 std::vector<BackgroundQueue::Task> Tasks;
140 Tasks.reserve(NeedsReIndexing.size());
141 for (const auto &File : NeedsReIndexing)
142 Tasks.push_back(indexFileTask(std::move(File)));
143 Queue.append(std::move(Tasks));
144 });
145
146 T.QueuePri = LoadShards;
147 T.ThreadPri = llvm::ThreadPriority::Default;
148 return T;
149 }
150
151 static llvm::StringRef filenameWithoutExtension(llvm::StringRef Path) {
152 Path = llvm::sys::path::filename(Path);
153 return Path.drop_back(llvm::sys::path::extension(Path).size());
154 }
155
156 BackgroundQueue::Task BackgroundIndex::indexFileTask(std::string Path) {
157 std::string Tag = filenameWithoutExtension(Path).str();
158 uint64_t Key = llvm::xxHash64(Path);
159 BackgroundQueue::Task T([this, Path(std::move(Path))] {
160 std::optional<WithContext> WithProvidedContext;
161 if (ContextProvider)
162 WithProvidedContext.emplace(ContextProvider(Path));
163 auto Cmd = CDB.getCompileCommand(Path);
164 if (!Cmd)
165 return;
166 if (auto Error = index(std::move(*Cmd)))
167 elog("Indexing {0} failed: {1}", Path, std::move(Error));
168 });
169 T.QueuePri = IndexFile;
170 T.ThreadPri = IndexingPriority;
171 T.Tag = std::move(Tag);
172 T.Key = Key;
173 return T;
174 }
175
176 void BackgroundIndex::boostRelated(llvm::StringRef Path) {
177 if (isHeaderFile(Path))
178 Queue.boost(filenameWithoutExtension(Path), IndexBoostedFile);
179 }
180
181 /// Given index results from a TU, only update symbols coming from files that
182 /// are different or missing from than \p ShardVersionsSnapshot. Also stores new
183 /// index information on IndexStorage.
184 void BackgroundIndex::update(
185 llvm::StringRef MainFile, IndexFileIn Index,
186 const llvm::StringMap<ShardVersion> &ShardVersionsSnapshot,
187 bool HadErrors) {
188 // Keys are URIs.
189 llvm::StringMap<std::pair<Path, FileDigest>> FilesToUpdate;
190 // Note that sources do not contain any information regarding missing headers,
191 // since we don't even know what absolute path they should fall in.
192 for (const auto &IndexIt : *Index.Sources) {
193 const auto &IGN = IndexIt.getValue();
194 auto AbsPath = URI::resolve(IGN.URI, MainFile);
195 if (!AbsPath) {
196 elog("Failed to resolve URI: {0}", AbsPath.takeError());
197 continue;
198 }
199 const auto DigestIt = ShardVersionsSnapshot.find(*AbsPath);
200 // File has different contents, or indexing was successful this time.
201 if (DigestIt == ShardVersionsSnapshot.end() ||
202 DigestIt->getValue().Digest != IGN.Digest ||
203 (DigestIt->getValue().HadErrors && !HadErrors))
204 FilesToUpdate[IGN.URI] = {std::move(*AbsPath), IGN.Digest};
205 }
206
207 // Shard slabs into files.
208 FileShardedIndex ShardedIndex(std::move(Index));
209
210 // Build and store new slabs for each updated file.
211 for (const auto &FileIt : FilesToUpdate) {
212 auto Uri = FileIt.first();
213 auto IF = ShardedIndex.getShard(Uri);
214 assert(IF && "no shard for file in Index.Sources?");
215 PathRef Path = FileIt.getValue().first;
216
217 // Only store command line hash for main files of the TU, since our
218 // current model keeps only one version of a header file.
219 if (Path != MainFile)
220 IF->Cmd.reset();
221
222 // We need to store shards before updating the index, since the latter
223 // consumes slabs.
224 // FIXME: Also skip serializing the shard if it is already up-to-date.
225 if (auto Error = IndexStorageFactory(Path)->storeShard(Path, *IF))
226 elog("Failed to write background-index shard for file {0}: {1}", Path,
227 std::move(Error));
228
229 {
230 std::lock_guard<std::mutex> Lock(ShardVersionsMu);
231 const auto &Hash = FileIt.getValue().second;
232 auto DigestIt = ShardVersions.try_emplace(Path);
233 ShardVersion &SV = DigestIt.first->second;
234 // Skip if file is already up to date, unless previous index was broken
235 // and this one is not.
236 if (!DigestIt.second && SV.Digest == Hash && SV.HadErrors && !HadErrors)
237 continue;
238 SV.Digest = Hash;
239 SV.HadErrors = HadErrors;
240
241 // This can override a newer version that is added in another thread, if
242 // this thread sees the older version but finishes later. This should be
243 // rare in practice.
244 IndexedSymbols.update(
245 Uri, std::make_unique<SymbolSlab>(std::move(*IF->Symbols)),
246 std::make_unique<RefSlab>(std::move(*IF->Refs)),
247 std::make_unique<RelationSlab>(std::move(*IF->Relations)),
248 Path == MainFile);
249 }
250 }
251 }
252
253 llvm::Error BackgroundIndex::index(tooling::CompileCommand Cmd) {
254 trace::Span Tracer("BackgroundIndex");
255 SPAN_ATTACH(Tracer, "file", Cmd.Filename);
256 auto AbsolutePath = getAbsolutePath(Cmd);
257
258 auto FS = TFS.view(Cmd.Directory);
259 auto Buf = FS->getBufferForFile(AbsolutePath);
260 if (!Buf)
261 return llvm::errorCodeToError(Buf.getError());
262 auto Hash = digest(Buf->get()->getBuffer());
263
264 // Take a snapshot of the versions to avoid locking for each file in the TU.
265 llvm::StringMap<ShardVersion> ShardVersionsSnapshot;
266 {
267 std::lock_guard<std::mutex> Lock(ShardVersionsMu);
268 ShardVersionsSnapshot = ShardVersions;
269 }
270
271 vlog("Indexing {0} (digest:={1})", Cmd.Filename, llvm::toHex(Hash));
272 ParseInputs Inputs;
273 Inputs.TFS = &TFS;
274 Inputs.CompileCommand = std::move(Cmd);
275 IgnoreDiagnostics IgnoreDiags;
276 auto CI = buildCompilerInvocation(Inputs, IgnoreDiags);
277 if (!CI)
278 return error("Couldn't build compiler invocation");
279
280 auto Clang =
281 prepareCompilerInstance(std::move(CI), /*Preamble=*/nullptr,
282 std::move(*Buf), std::move(FS), IgnoreDiags);
283 if (!Clang)
284 return error("Couldn't build compiler instance");
285
286 SymbolCollector::Options IndexOpts;
287 // Creates a filter to not collect index results from files with unchanged
288 // digests.
289 IndexOpts.FileFilter = [&ShardVersionsSnapshot](const SourceManager &SM,
290 FileID FID) {
291 const auto *F = SM.getFileEntryForID(FID);
292 if (!F)
293 return false; // Skip invalid files.
294 auto AbsPath = getCanonicalPath(F, SM);
295 if (!AbsPath)
296 return false; // Skip files without absolute path.
297 auto Digest = digestFile(SM, FID);
298 if (!Digest)
299 return false;
300 auto D = ShardVersionsSnapshot.find(*AbsPath);
301 if (D != ShardVersionsSnapshot.end() && D->second.Digest == Digest &&
302 !D->second.HadErrors)
303 return false; // Skip files that haven't changed, without errors.
304 return true;
305 };
306 IndexOpts.CollectMainFileRefs = true;
307
308 IndexFileIn Index;
309 auto Action = createStaticIndexingAction(
310 IndexOpts, [&](SymbolSlab S) { Index.Symbols = std::move(S); },
311 [&](RefSlab R) { Index.Refs = std::move(R); },
312 [&](RelationSlab R) { Index.Relations = std::move(R); },
313 [&](IncludeGraph IG) { Index.Sources = std::move(IG); });
314
315 // We're going to run clang here, and it could potentially crash.
316 // We could use CrashRecoveryContext to try to make indexing crashes nonfatal,
317 // but the leaky "recovery" is pretty scary too in a long-running process.
318 // If crashes are a real problem, maybe we should fork a child process.
319
320 const FrontendInputFile &Input = Clang->getFrontendOpts().Inputs.front();
321 if (!Action->BeginSourceFile(*Clang, Input))
322 return error("BeginSourceFile() failed");
323 if (llvm::Error Err = Action->Execute())
324 return Err;
325
326 Action->EndSourceFile();
327
328 Index.Cmd = Inputs.CompileCommand;
329 assert(Index.Symbols && Index.Refs && Index.Sources &&
330 "Symbols, Refs and Sources must be set.");
331
332 log("Indexed {0} ({1} symbols, {2} refs, {3} files)",
333 Inputs.CompileCommand.Filename, Index.Symbols->size(),
334 Index.Refs->numRefs(), Index.Sources->size());
335 SPAN_ATTACH(Tracer, "symbols", int(Index.Symbols->size()));
336 SPAN_ATTACH(Tracer, "refs", int(Index.Refs->numRefs()));
337 SPAN_ATTACH(Tracer, "sources", int(Index.Sources->size()));
338
339 bool HadErrors = Clang->hasDiagnostics() &&
340 Clang->getDiagnostics().hasUncompilableErrorOccurred();
341 if (HadErrors) {
342 log("Failed to compile {0}, index may be incomplete", AbsolutePath);
343 for (auto &It : *Index.Sources)
344 It.second.Flags |= IncludeGraphNode::SourceFlag::HadErrors;
345 }
346 update(AbsolutePath, std::move(Index), ShardVersionsSnapshot, HadErrors);
347
348 Rebuilder.indexedTU();
349 return llvm::Error::success();
350 }
351
352 // Restores shards for \p MainFiles from index storage. Then checks staleness of
353 // those shards and returns a list of TUs that needs to be indexed to update
354 // staleness.
355 std::vector<std::string>
356 BackgroundIndex::loadProject(std::vector<std::string> MainFiles) {
357 // Drop files where background indexing is disabled in config.
358 if (ContextProvider)
359 llvm::erase_if(MainFiles, [&](const std::string &TU) {
360 // Load the config for each TU, as indexing may be selectively enabled.
361 WithContext WithProvidedContext(ContextProvider(TU));
362 return Config::current().Index.Background ==
363 Config::BackgroundPolicy::Skip;
364 });
365 Rebuilder.startLoading();
366 // Load shards for all of the mainfiles.
367 const std::vector<LoadedShard> Result =
368 loadIndexShards(MainFiles, IndexStorageFactory, CDB);
369 size_t LoadedShards = 0;
370 {
371 // Update in-memory state.
372 std::lock_guard<std::mutex> Lock(ShardVersionsMu);
373 for (auto &LS : Result) {
374 if (!LS.Shard)
375 continue;
376 auto SS =
377 LS.Shard->Symbols
378 ? std::make_unique<SymbolSlab>(std::move(*LS.Shard->Symbols))
379 : nullptr;
380 auto RS = LS.Shard->Refs
381 ? std::make_unique<RefSlab>(std::move(*LS.Shard->Refs))
382 : nullptr;
383 auto RelS =
384 LS.Shard->Relations
385 ? std::make_unique<RelationSlab>(std::move(*LS.Shard->Relations))
386 : nullptr;
387 ShardVersion &SV = ShardVersions[LS.AbsolutePath];
388 SV.Digest = LS.Digest;
389 SV.HadErrors = LS.HadErrors;
390 ++LoadedShards;
391
392 IndexedSymbols.update(URI::create(LS.AbsolutePath).toString(),
393 std::move(SS), std::move(RS), std::move(RelS),
394 LS.CountReferences);
395 }
396 }
397 Rebuilder.loadedShard(LoadedShards);
398 Rebuilder.doneLoading();
399
400 auto FS = TFS.view(/*CWD=*/std::nullopt);
401 llvm::DenseSet<PathRef> TUsToIndex;
402 // We'll accept data from stale shards, but ensure the files get reindexed
403 // soon.
404 for (auto &LS : Result) {
405 if (!shardIsStale(LS, FS.get()))
406 continue;
407 PathRef TUForFile = LS.DependentTU;
408 assert(!TUForFile.empty() && "File without a TU!");
409
410 // FIXME: Currently, we simply schedule indexing on a TU whenever any of
411 // its dependencies needs re-indexing. We might do it smarter by figuring
412 // out a minimal set of TUs that will cover all the stale dependencies.
413 // FIXME: Try looking at other TUs if no compile commands are available
414 // for this TU, i.e TU was deleted after we performed indexing.
415 TUsToIndex.insert(TUForFile);
416 }
417
418 return {TUsToIndex.begin(), TUsToIndex.end()};
419 }
420
421 void BackgroundIndex::profile(MemoryTree &MT) const {
422 IndexedSymbols.profile(MT.child("slabs"));
423 // We don't want to mix memory used by index and symbols, so call base class.
424 MT.child("index").addUsage(SwapIndex::estimateMemoryUsage());
425 }
426 } // namespace clangd
427 } // namespace clang