1//===- ModuleManager.cpp - Module Manager ---------------------------------===//
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// This file defines the ModuleManager class, which manages a set of loaded
10// modules for the ASTReader.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/Serialization/ModuleManager.h"
15#include "clang/Basic/FileManager.h"
16#include "clang/Basic/LLVM.h"
17#include "clang/Lex/HeaderSearch.h"
18#include "clang/Lex/ModuleMap.h"
19#include "clang/Serialization/GlobalModuleIndex.h"
20#include "clang/Serialization/InMemoryModuleCache.h"
21#include "clang/Serialization/ModuleCache.h"
22#include "clang/Serialization/ModuleFile.h"
23#include "clang/Serialization/PCHContainerOperations.h"
24#include "llvm/ADT/STLExtras.h"
25#include "llvm/ADT/SetVector.h"
26#include "llvm/ADT/SmallPtrSet.h"
27#include "llvm/ADT/SmallVector.h"
28#include "llvm/ADT/StringRef.h"
29#include "llvm/ADT/iterator.h"
30#include "llvm/Support/DOTGraphTraits.h"
31#include "llvm/Support/Error.h"
32#include "llvm/Support/ErrorOr.h"
33#include "llvm/Support/GraphWriter.h"
34#include "llvm/Support/MemoryBuffer.h"
35#include "llvm/Support/VirtualFileSystem.h"
36#include <cassert>
37#include <memory>
38#include <string>
39#include <system_error>
40
41using namespace clang;
42using namespace serialization;
43
44std::optional<ModuleFileKey>
45ModuleManager::makeKey(const ModuleFileName &Name) const {
46 if (unsigned SuffixLen = Name.getImplicitModuleSuffixLength()) {
47 StringRef ModuleCachePath = StringRef(Name).drop_back(N: SuffixLen);
48 StringRef ImplicitModuleSuffix = StringRef(Name).take_back(N: SuffixLen);
49 if (auto *ModuleCacheDir = ModCache.getDirectoryPtr(Path: ModuleCachePath))
50 return ModuleFileKey(ModuleCacheDir, ImplicitModuleSuffix);
51 } else if (Name.isInMemory()) {
52 off_t Size;
53 time_t ModTime;
54 if (auto *Buf =
55 ModCache.getInMemoryModuleCache().lookupPCM(Filename: Name, Size, ModTime))
56 return ModuleFileKey(Buf);
57 } else {
58 if (auto ModuleFile = FileMgr.getOptionalFileRef(Filename: Name, /*OpenFile=*/true,
59 /*CacheFailure=*/false,
60 /*IsText=*/false))
61 return ModuleFileKey(*ModuleFile);
62 }
63
64 return std::nullopt;
65}
66
67ModuleFile *ModuleManager::lookupByModuleName(StringRef Name) const {
68 if (const Module *Mod = HeaderSearchInfo.getModuleMap().findModule(Name))
69 if (const ModuleFileName *FileName = Mod->getASTFileName())
70 return lookupByFileName(FileName: *FileName);
71
72 return nullptr;
73}
74
75ModuleFile *ModuleManager::lookupByFileName(ModuleFileName Name) const {
76 std::optional<ModuleFileKey> Key = makeKey(Name);
77 return Key ? lookup(Key: *Key) : nullptr;
78}
79
80ModuleFile *ModuleManager::lookup(ModuleFileKey Key) const {
81 return Modules.lookup(Val: Key);
82}
83
84bool ModuleManager::isModuleFileOutOfDate(off_t Size, time_t ModTime,
85 off_t ExpectedSize,
86 time_t ExpectedModTime,
87 AddModuleResult &Result) {
88 bool OutOfDate = false;
89 if (ExpectedSize && ExpectedSize != Size) {
90 Result.Changes.push_back(Elt: {.Kind: Change::Size, .Old: ExpectedSize, .New: Size});
91 OutOfDate = true;
92 }
93
94 if (ExpectedModTime && ExpectedModTime != ModTime) {
95 Result.Changes.push_back(Elt: {.Kind: Change::ModTime, .Old: ExpectedModTime, .New: ModTime});
96 OutOfDate = true;
97 }
98
99 return OutOfDate;
100}
101
102bool ModuleManager::checkSignature(ASTFileSignature Signature,
103 ASTFileSignature ExpectedSignature,
104 AddModuleResult &Result) {
105 if (!ExpectedSignature || Signature == ExpectedSignature)
106 return false;
107 Result.SignatureError =
108 Signature ? "signature mismatch" : "could not read module signature";
109 return true;
110}
111
112static void updateModuleImports(ModuleFile &MF, ModuleFile *ImportedBy,
113 SourceLocation ImportLoc) {
114 if (ImportedBy) {
115 MF.ImportedBy.insert(X: ImportedBy);
116 ImportedBy->Imports.insert(X: &MF);
117 } else {
118 if (!MF.DirectlyImported)
119 MF.ImportLoc = ImportLoc;
120
121 MF.DirectlyImported = true;
122 }
123}
124
125AddModuleResult ModuleManager::addModule(
126 ModuleFileName FileName, ModuleKind Type, SourceLocation ImportLoc,
127 ModuleFile *ImportedBy, unsigned Generation, off_t ExpectedSize,
128 time_t ExpectedModTime, ASTFileSignature ExpectedSignature,
129 ASTFileSignatureReader ReadSignature) {
130 AddModuleResult Result;
131
132 uint64_t InputFilesValidationTimestamp = 0;
133 if (Type == MK_ImplicitModule)
134 InputFilesValidationTimestamp = ModCache.getModuleTimestamp(ModuleFilename: FileName);
135
136 bool IgnoreModTime = Type == MK_ExplicitModule || Type == MK_PrebuiltModule;
137 if (ImportedBy)
138 IgnoreModTime &= ImportedBy->Kind == MK_ExplicitModule ||
139 ImportedBy->Kind == MK_PrebuiltModule;
140 if (IgnoreModTime) {
141 // If neither this file nor the importer are in the module cache, this file
142 // might have a different mtime due to being moved across filesystems in
143 // a distributed build. The size must still match, though. (As must the
144 // contents, but we can't check that.)
145 ExpectedModTime = 0;
146 }
147
148 std::optional<ModuleFileKey> FileKey = makeKey(Name: FileName);
149 if (!FileKey) {
150 Result.K = AddModuleResult::Missing;
151 return Result;
152 }
153
154 // Check whether we already loaded this module before.
155 // Note: `isModuleFileOutOfDate` and `checkSignature` are mutually exclusive
156 // in practice. If a signature is stored, it means size/mtime values have been
157 // zeroed out. If size/mtime are non-NULL, the signature is empty.
158 if (ModuleFile *ModuleEntry = lookup(Key: *FileKey)) {
159 if (isModuleFileOutOfDate(Size: ModuleEntry->Size, ModTime: ModuleEntry->ModTime,
160 ExpectedSize, ExpectedModTime, Result)) {
161 Result.setOutOfDate(ModuleEntry->InputFilesValidationStatus);
162 return Result;
163 }
164
165 // Check the stored signature.
166 if (checkSignature(Signature: ModuleEntry->Signature, ExpectedSignature, Result)) {
167 Result.setOutOfDate(ModuleEntry->InputFilesValidationStatus);
168 return Result;
169 }
170
171 Result.Module = ModuleEntry;
172 updateModuleImports(MF&: *ModuleEntry, ImportedBy, ImportLoc);
173 Result.K = AddModuleResult::AlreadyLoaded;
174 return Result;
175 }
176
177 // Load the contents of the module
178 off_t Size = ExpectedSize;
179 time_t ModTime = ExpectedModTime;
180 llvm::MemoryBuffer *ModuleBuffer = nullptr;
181 std::unique_ptr<llvm::MemoryBuffer> NewFileBuffer = nullptr;
182 if (llvm::MemoryBuffer *Buffer =
183 getModuleCache().getInMemoryModuleCache().lookupPCM(Filename: FileName, Size,
184 ModTime)) {
185 ModuleBuffer = Buffer;
186 } else if (getModuleCache().getInMemoryModuleCache().shouldBuildPCM(
187 Filename: FileName)) {
188 // Report that the module is out of date, since we tried (and failed) to
189 // import it earlier. No ModuleFile exists yet, so derive the validation
190 // status from the module kind being loaded.
191 Result.setOutOfDate(Type == MK_ExplicitModule || Type == MK_PrebuiltModule
192 ? InputFilesValidation::Disabled
193 : InputFilesValidation::NotStarted);
194 return Result;
195 } else {
196 auto Buf = [&]() -> Expected<std::unique_ptr<llvm::MemoryBuffer>> {
197 assert(!FileName.isInMemory() && "In-memory module not found");
198
199 // Implicit modules live in the module cache.
200 if (FileName.getImplicitModuleSuffixLength())
201 return ModCache.read(FileName, Size, ModTime);
202
203 // Explicit modules are treated as any other compiler input file, load
204 // them via FileManager.
205 Expected<FileEntryRef> Entry =
206 FileName == StringRef("-")
207 ? FileMgr.getSTDIN()
208 : FileMgr.getFileRef(Filename: FileName, /*OpenFile=*/true,
209 /*CacheFailure=*/false,
210 /*IsText=*/false);
211 if (!Entry)
212 return Entry.takeError();
213
214 Size = Entry->getSize();
215 ModTime = Entry->getModificationTime();
216
217 // RequiresNullTerminator is false because module files don't need it, and
218 // this allows the file to still be mmapped.
219 return llvm::errorOrToExpected(
220 EO: FileMgr.getBufferForFile(Entry: *Entry, /*IsVolatile=*/isVolatile: false,
221 /*RequiresNullTerminator=*/false,
222 /*MaybeLimit=*/std::nullopt,
223 /*IsText=*/false));
224 }();
225
226 if (!Buf) {
227 Result.BufferError = llvm::toString(E: Buf.takeError());
228 Result.K = AddModuleResult::Missing;
229 return Result;
230 }
231
232 NewFileBuffer = std::move(*Buf);
233 ModuleBuffer = NewFileBuffer.get();
234 }
235
236 // Allocate bookkeeping for a module file not yet loaded into this reader.
237 auto NewModule = std::make_unique<ModuleFile>(args&: Type, args&: *FileKey, args&: Generation);
238 NewModule->Index = Chain.size();
239 NewModule->FileName = FileName;
240 NewModule->ImportLoc = ImportLoc;
241 NewModule->InputFilesValidationTimestamp = InputFilesValidationTimestamp;
242 NewModule->Size = Size;
243 NewModule->ModTime = ModTime;
244 NewModule->Buffer = ModuleBuffer;
245 // Initialize the stream.
246 NewModule->Data = PCHContainerRdr.ExtractPCH(Buffer: *NewModule->Buffer);
247
248 // Check file properties.
249 if (isModuleFileOutOfDate(Size, ModTime, ExpectedSize, ExpectedModTime,
250 Result)) {
251 Result.setOutOfDate(NewModule->InputFilesValidationStatus);
252 return Result;
253 }
254
255 // Read the signature eagerly now so that we can check it. Avoid calling
256 // ReadSignature unless there's something to check though.
257 if (ExpectedSignature && checkSignature(Signature: ReadSignature(NewModule->Data),
258 ExpectedSignature, Result)) {
259 Result.setOutOfDate(NewModule->InputFilesValidationStatus);
260 return Result;
261 }
262
263 if (NewFileBuffer)
264 getModuleCache().getInMemoryModuleCache().addPCM(
265 Filename: FileName, Buffer: std::move(NewFileBuffer), Size, ModTime);
266
267 // We're keeping this module. Store it in the map.
268 Result.Module = Modules[*FileKey] = NewModule.get();
269
270 updateModuleImports(MF&: *NewModule, ImportedBy, ImportLoc);
271
272 if (!NewModule->isModule())
273 PCHChain.push_back(Elt: NewModule.get());
274 if (!ImportedBy)
275 Roots.push_back(Elt: NewModule.get());
276
277 Chain.push_back(Elt: std::move(NewModule));
278 Result.K = AddModuleResult::NewlyLoaded;
279 return Result;
280}
281
282void ModuleManager::removeModules(ModuleIterator First) {
283 auto Last = end();
284 if (First == Last)
285 return;
286
287 // Explicitly clear VisitOrder since we might not notice it is stale.
288 VisitOrder.clear();
289
290 // Collect the set of module file pointers that we'll be removing.
291 llvm::SmallPtrSet<ModuleFile *, 4> victimSet(
292 (llvm::pointer_iterator<ModuleIterator>(First)),
293 (llvm::pointer_iterator<ModuleIterator>(Last)));
294
295 auto IsVictim = [&](ModuleFile *MF) {
296 return victimSet.count(Ptr: MF);
297 };
298 // Remove any references to the now-destroyed modules.
299 for (auto I = begin(); I != First; ++I) {
300 I->Imports.remove_if(P: IsVictim);
301 I->ImportedBy.remove_if(P: IsVictim);
302 }
303 llvm::erase_if(C&: Roots, P: IsVictim);
304
305 // Remove the modules from the PCH chain.
306 for (auto I = First; I != Last; ++I) {
307 if (!I->isModule()) {
308 PCHChain.erase(CS: llvm::find(Range&: PCHChain, Val: &*I), CE: PCHChain.end());
309 break;
310 }
311 }
312
313 // Delete the modules.
314 for (ModuleIterator victim = First; victim != Last; ++victim)
315 Modules.erase(Val: victim->FileKey);
316
317 Chain.erase(CS: Chain.begin() + (First - begin()), CE: Chain.end());
318}
319
320std::unique_ptr<ModuleManager::VisitState> ModuleManager::allocateVisitState() {
321 // Fast path: if we have a cached state, use it.
322 if (FirstVisitState) {
323 auto Result = std::move(FirstVisitState);
324 FirstVisitState = std::move(Result->NextState);
325 return Result;
326 }
327
328 // Allocate and return a new state.
329 return std::make_unique<VisitState>(args: size());
330}
331
332void ModuleManager::returnVisitState(std::unique_ptr<VisitState> State) {
333 assert(State->NextState == nullptr && "Visited state is in list?");
334 State->NextState = std::move(FirstVisitState);
335 FirstVisitState = std::move(State);
336}
337
338void ModuleManager::setGlobalIndex(GlobalModuleIndex *Index) {
339 GlobalIndex = Index;
340 if (!GlobalIndex) {
341 ModulesInCommonWithGlobalIndex.clear();
342 return;
343 }
344
345 // Notify the global module index about all of the modules we've already
346 // loaded.
347 for (ModuleFile &M : *this)
348 if (!GlobalIndex->loadedModuleFile(File: &M))
349 ModulesInCommonWithGlobalIndex.push_back(Elt: &M);
350}
351
352void ModuleManager::moduleFileAccepted(ModuleFile *MF) {
353 if (!GlobalIndex || GlobalIndex->loadedModuleFile(File: MF))
354 return;
355
356 ModulesInCommonWithGlobalIndex.push_back(Elt: MF);
357}
358
359ModuleManager::ModuleManager(FileManager &FileMgr, ModuleCache &ModCache,
360 const PCHContainerReader &PCHContainerRdr,
361 const HeaderSearch &HeaderSearchInfo)
362 : FileMgr(FileMgr), ModCache(ModCache), PCHContainerRdr(PCHContainerRdr),
363 HeaderSearchInfo(HeaderSearchInfo) {}
364
365void ModuleManager::visit(llvm::function_ref<bool(ModuleFile &M)> Visitor,
366 llvm::SmallPtrSetImpl<ModuleFile *> *ModuleFilesHit) {
367 // If the visitation order vector is the wrong size, recompute the order.
368 if (VisitOrder.size() != Chain.size()) {
369 unsigned N = size();
370 VisitOrder.clear();
371 VisitOrder.reserve(N);
372
373 // Record the number of incoming edges for each module. When we
374 // encounter a module with no incoming edges, push it into the queue
375 // to seed the queue.
376 SmallVector<ModuleFile *, 4> Queue;
377 Queue.reserve(N);
378 llvm::SmallVector<unsigned, 4> UnusedIncomingEdges;
379 UnusedIncomingEdges.resize(N: size());
380 for (ModuleFile &M : llvm::reverse(C&: *this)) {
381 unsigned Size = M.ImportedBy.size();
382 UnusedIncomingEdges[M.Index] = Size;
383 if (!Size)
384 Queue.push_back(Elt: &M);
385 }
386
387 // Traverse the graph, making sure to visit a module before visiting any
388 // of its dependencies.
389 while (!Queue.empty()) {
390 ModuleFile *CurrentModule = Queue.pop_back_val();
391 VisitOrder.push_back(Elt: CurrentModule);
392
393 // For any module that this module depends on, push it on the
394 // stack (if it hasn't already been marked as visited).
395 for (ModuleFile *M : llvm::reverse(C&: CurrentModule->Imports)) {
396 // Remove our current module as an impediment to visiting the
397 // module we depend on. If we were the last unvisited module
398 // that depends on this particular module, push it into the
399 // queue to be visited.
400 unsigned &NumUnusedEdges = UnusedIncomingEdges[M->Index];
401 if (NumUnusedEdges && (--NumUnusedEdges == 0))
402 Queue.push_back(Elt: M);
403 }
404 }
405
406 assert(VisitOrder.size() == N && "Visitation order is wrong?");
407
408 FirstVisitState = nullptr;
409 }
410
411 auto State = allocateVisitState();
412 unsigned VisitNumber = State->NextVisitNumber++;
413
414 // If the caller has provided us with a hit-set that came from the global
415 // module index, mark every module file in common with the global module
416 // index that is *not* in that set as 'visited'.
417 if (ModuleFilesHit && !ModulesInCommonWithGlobalIndex.empty()) {
418 for (unsigned I = 0, N = ModulesInCommonWithGlobalIndex.size(); I != N; ++I)
419 {
420 ModuleFile *M = ModulesInCommonWithGlobalIndex[I];
421 if (!ModuleFilesHit->count(Ptr: M))
422 State->VisitNumber[M->Index] = VisitNumber;
423 }
424 }
425
426 for (unsigned I = 0, N = VisitOrder.size(); I != N; ++I) {
427 ModuleFile *CurrentModule = VisitOrder[I];
428 // Should we skip this module file?
429 if (State->VisitNumber[CurrentModule->Index] == VisitNumber)
430 continue;
431
432 // Visit the module.
433 assert(State->VisitNumber[CurrentModule->Index] == VisitNumber - 1);
434 State->VisitNumber[CurrentModule->Index] = VisitNumber;
435 if (!Visitor(*CurrentModule))
436 continue;
437
438 // The visitor has requested that cut off visitation of any
439 // module that the current module depends on. To indicate this
440 // behavior, we mark all of the reachable modules as having been visited.
441 ModuleFile *NextModule = CurrentModule;
442 do {
443 // For any module that this module depends on, push it on the
444 // stack (if it hasn't already been marked as visited).
445 for (llvm::SetVector<ModuleFile *>::iterator
446 M = NextModule->Imports.begin(),
447 MEnd = NextModule->Imports.end();
448 M != MEnd; ++M) {
449 if (State->VisitNumber[(*M)->Index] != VisitNumber) {
450 State->Stack.push_back(Elt: *M);
451 State->VisitNumber[(*M)->Index] = VisitNumber;
452 }
453 }
454
455 if (State->Stack.empty())
456 break;
457
458 // Pop the next module off the stack.
459 NextModule = State->Stack.pop_back_val();
460 } while (true);
461 }
462
463 returnVisitState(State: std::move(State));
464}
465
466#ifndef NDEBUG
467namespace llvm {
468
469 template<>
470 struct GraphTraits<ModuleManager> {
471 using NodeRef = ModuleFile *;
472 using ChildIteratorType = llvm::SetVector<ModuleFile *>::const_iterator;
473 using nodes_iterator = pointer_iterator<ModuleManager::ModuleConstIterator>;
474
475 static ChildIteratorType child_begin(NodeRef Node) {
476 return Node->Imports.begin();
477 }
478
479 static ChildIteratorType child_end(NodeRef Node) {
480 return Node->Imports.end();
481 }
482
483 static nodes_iterator nodes_begin(const ModuleManager &Manager) {
484 return nodes_iterator(Manager.begin());
485 }
486
487 static nodes_iterator nodes_end(const ModuleManager &Manager) {
488 return nodes_iterator(Manager.end());
489 }
490 };
491
492 template<>
493 struct DOTGraphTraits<ModuleManager> : public DefaultDOTGraphTraits {
494 explicit DOTGraphTraits(bool IsSimple = false)
495 : DefaultDOTGraphTraits(IsSimple) {}
496
497 static bool renderGraphFromBottomUp() { return true; }
498
499 std::string getNodeLabel(ModuleFile *M, const ModuleManager&) {
500 return M->ModuleName;
501 }
502 };
503
504} // namespace llvm
505
506void ModuleManager::viewGraph() {
507 llvm::ViewGraph(*this, "Modules");
508}
509#endif
510