xref: /minix3/external/bsd/llvm/dist/clang/lib/Serialization/ModuleManager.cpp (revision 0a6a1f1d05b60e214de2f05a7310ddd1f0e590e7)
1 //===--- ModuleManager.cpp - Module Manager ---------------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 //  This file defines the ModuleManager class, which manages a set of loaded
11 //  modules for the ASTReader.
12 //
13 //===----------------------------------------------------------------------===//
14 #include "clang/Lex/HeaderSearch.h"
15 #include "clang/Lex/ModuleMap.h"
16 #include "clang/Serialization/GlobalModuleIndex.h"
17 #include "clang/Serialization/ModuleManager.h"
18 #include "llvm/Support/MemoryBuffer.h"
19 #include "llvm/Support/Path.h"
20 #include "llvm/Support/raw_ostream.h"
21 #include <system_error>
22 
23 #ifndef NDEBUG
24 #include "llvm/Support/GraphWriter.h"
25 #endif
26 
27 using namespace clang;
28 using namespace serialization;
29 
lookup(StringRef Name)30 ModuleFile *ModuleManager::lookup(StringRef Name) {
31   const FileEntry *Entry = FileMgr.getFile(Name, /*openFile=*/false,
32                                            /*cacheFailure=*/false);
33   if (Entry)
34     return lookup(Entry);
35 
36   return nullptr;
37 }
38 
lookup(const FileEntry * File)39 ModuleFile *ModuleManager::lookup(const FileEntry *File) {
40   llvm::DenseMap<const FileEntry *, ModuleFile *>::iterator Known
41     = Modules.find(File);
42   if (Known == Modules.end())
43     return nullptr;
44 
45   return Known->second;
46 }
47 
48 std::unique_ptr<llvm::MemoryBuffer>
lookupBuffer(StringRef Name)49 ModuleManager::lookupBuffer(StringRef Name) {
50   const FileEntry *Entry = FileMgr.getFile(Name, /*openFile=*/false,
51                                            /*cacheFailure=*/false);
52   return std::move(InMemoryBuffers[Entry]);
53 }
54 
55 ModuleManager::AddModuleResult
addModule(StringRef FileName,ModuleKind Type,SourceLocation ImportLoc,ModuleFile * ImportedBy,unsigned Generation,off_t ExpectedSize,time_t ExpectedModTime,ASTFileSignature ExpectedSignature,std::function<ASTFileSignature (llvm::BitstreamReader &)> ReadSignature,ModuleFile * & Module,std::string & ErrorStr)56 ModuleManager::addModule(StringRef FileName, ModuleKind Type,
57                          SourceLocation ImportLoc, ModuleFile *ImportedBy,
58                          unsigned Generation,
59                          off_t ExpectedSize, time_t ExpectedModTime,
60                          ASTFileSignature ExpectedSignature,
61                          std::function<ASTFileSignature(llvm::BitstreamReader &)>
62                              ReadSignature,
63                          ModuleFile *&Module,
64                          std::string &ErrorStr) {
65   Module = nullptr;
66 
67   // Look for the file entry. This only fails if the expected size or
68   // modification time differ.
69   const FileEntry *Entry;
70   if (Type == MK_ExplicitModule) {
71     // If we're not expecting to pull this file out of the module cache, it
72     // might have a different mtime due to being moved across filesystems in
73     // a distributed build. The size must still match, though. (As must the
74     // contents, but we can't check that.)
75     ExpectedModTime = 0;
76   }
77   if (lookupModuleFile(FileName, ExpectedSize, ExpectedModTime, Entry)) {
78     ErrorStr = "module file out of date";
79     return OutOfDate;
80   }
81 
82   if (!Entry && FileName != "-") {
83     ErrorStr = "module file not found";
84     return Missing;
85   }
86 
87   // Check whether we already loaded this module, before
88   ModuleFile *&ModuleEntry = Modules[Entry];
89   bool NewModule = false;
90   if (!ModuleEntry) {
91     // Allocate a new module.
92     ModuleFile *New = new ModuleFile(Type, Generation);
93     New->Index = Chain.size();
94     New->FileName = FileName.str();
95     New->File = Entry;
96     New->ImportLoc = ImportLoc;
97     Chain.push_back(New);
98     NewModule = true;
99     ModuleEntry = New;
100 
101     New->InputFilesValidationTimestamp = 0;
102     if (New->Kind == MK_ImplicitModule) {
103       std::string TimestampFilename = New->getTimestampFilename();
104       vfs::Status Status;
105       // A cached stat value would be fine as well.
106       if (!FileMgr.getNoncachedStatValue(TimestampFilename, Status))
107         New->InputFilesValidationTimestamp =
108             Status.getLastModificationTime().toEpochTime();
109     }
110 
111     // Load the contents of the module
112     if (std::unique_ptr<llvm::MemoryBuffer> Buffer = lookupBuffer(FileName)) {
113       // The buffer was already provided for us.
114       New->Buffer = std::move(Buffer);
115     } else {
116       // Open the AST file.
117       llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Buf(
118           (std::error_code()));
119       if (FileName == "-") {
120         Buf = llvm::MemoryBuffer::getSTDIN();
121       } else {
122         // Leave the FileEntry open so if it gets read again by another
123         // ModuleManager it must be the same underlying file.
124         // FIXME: Because FileManager::getFile() doesn't guarantee that it will
125         // give us an open file, this may not be 100% reliable.
126         Buf = FileMgr.getBufferForFile(New->File,
127                                        /*IsVolatile=*/false,
128                                        /*ShouldClose=*/false);
129       }
130 
131       if (!Buf) {
132         ErrorStr = Buf.getError().message();
133         return Missing;
134       }
135 
136       New->Buffer = std::move(*Buf);
137     }
138 
139     // Initialize the stream
140     New->StreamFile.init((const unsigned char *)New->Buffer->getBufferStart(),
141                          (const unsigned char *)New->Buffer->getBufferEnd());
142   }
143 
144   if (ExpectedSignature) {
145     if (NewModule)
146       ModuleEntry->Signature = ReadSignature(ModuleEntry->StreamFile);
147     else
148       assert(ModuleEntry->Signature == ReadSignature(ModuleEntry->StreamFile));
149 
150     if (ModuleEntry->Signature != ExpectedSignature) {
151       ErrorStr = ModuleEntry->Signature ? "signature mismatch"
152                                         : "could not read module signature";
153 
154       if (NewModule) {
155         // Remove the module file immediately, since removeModules might try to
156         // invalidate the file cache for Entry, and that is not safe if this
157         // module is *itself* up to date, but has an out-of-date importer.
158         Modules.erase(Entry);
159         Chain.pop_back();
160         delete ModuleEntry;
161       }
162       return OutOfDate;
163     }
164   }
165 
166   if (ImportedBy) {
167     ModuleEntry->ImportedBy.insert(ImportedBy);
168     ImportedBy->Imports.insert(ModuleEntry);
169   } else {
170     if (!ModuleEntry->DirectlyImported)
171       ModuleEntry->ImportLoc = ImportLoc;
172 
173     ModuleEntry->DirectlyImported = true;
174   }
175 
176   Module = ModuleEntry;
177   return NewModule? NewlyLoaded : AlreadyLoaded;
178 }
179 
removeModules(ModuleIterator first,ModuleIterator last,llvm::SmallPtrSetImpl<ModuleFile * > & LoadedSuccessfully,ModuleMap * modMap)180 void ModuleManager::removeModules(
181     ModuleIterator first, ModuleIterator last,
182     llvm::SmallPtrSetImpl<ModuleFile *> &LoadedSuccessfully,
183     ModuleMap *modMap) {
184   if (first == last)
185     return;
186 
187   // Collect the set of module file pointers that we'll be removing.
188   llvm::SmallPtrSet<ModuleFile *, 4> victimSet(first, last);
189 
190   // Remove any references to the now-destroyed modules.
191   for (unsigned i = 0, n = Chain.size(); i != n; ++i) {
192     Chain[i]->ImportedBy.remove_if([&](ModuleFile *MF) {
193       return victimSet.count(MF);
194     });
195   }
196 
197   // Delete the modules and erase them from the various structures.
198   for (ModuleIterator victim = first; victim != last; ++victim) {
199     Modules.erase((*victim)->File);
200 
201     if (modMap) {
202       StringRef ModuleName = (*victim)->ModuleName;
203       if (Module *mod = modMap->findModule(ModuleName)) {
204         mod->setASTFile(nullptr);
205       }
206     }
207 
208     // Files that didn't make it through ReadASTCore successfully will be
209     // rebuilt (or there was an error). Invalidate them so that we can load the
210     // new files that will be renamed over the old ones.
211     if (LoadedSuccessfully.count(*victim) == 0)
212       FileMgr.invalidateCache((*victim)->File);
213 
214     delete *victim;
215   }
216 
217   // Remove the modules from the chain.
218   Chain.erase(first, last);
219 }
220 
221 void
addInMemoryBuffer(StringRef FileName,std::unique_ptr<llvm::MemoryBuffer> Buffer)222 ModuleManager::addInMemoryBuffer(StringRef FileName,
223                                  std::unique_ptr<llvm::MemoryBuffer> Buffer) {
224 
225   const FileEntry *Entry =
226       FileMgr.getVirtualFile(FileName, Buffer->getBufferSize(), 0);
227   InMemoryBuffers[Entry] = std::move(Buffer);
228 }
229 
allocateVisitState()230 ModuleManager::VisitState *ModuleManager::allocateVisitState() {
231   // Fast path: if we have a cached state, use it.
232   if (FirstVisitState) {
233     VisitState *Result = FirstVisitState;
234     FirstVisitState = FirstVisitState->NextState;
235     Result->NextState = nullptr;
236     return Result;
237   }
238 
239   // Allocate and return a new state.
240   return new VisitState(size());
241 }
242 
returnVisitState(VisitState * State)243 void ModuleManager::returnVisitState(VisitState *State) {
244   assert(State->NextState == nullptr && "Visited state is in list?");
245   State->NextState = FirstVisitState;
246   FirstVisitState = State;
247 }
248 
setGlobalIndex(GlobalModuleIndex * Index)249 void ModuleManager::setGlobalIndex(GlobalModuleIndex *Index) {
250   GlobalIndex = Index;
251   if (!GlobalIndex) {
252     ModulesInCommonWithGlobalIndex.clear();
253     return;
254   }
255 
256   // Notify the global module index about all of the modules we've already
257   // loaded.
258   for (unsigned I = 0, N = Chain.size(); I != N; ++I) {
259     if (!GlobalIndex->loadedModuleFile(Chain[I])) {
260       ModulesInCommonWithGlobalIndex.push_back(Chain[I]);
261     }
262   }
263 }
264 
moduleFileAccepted(ModuleFile * MF)265 void ModuleManager::moduleFileAccepted(ModuleFile *MF) {
266   if (!GlobalIndex || GlobalIndex->loadedModuleFile(MF))
267     return;
268 
269   ModulesInCommonWithGlobalIndex.push_back(MF);
270 }
271 
ModuleManager(FileManager & FileMgr)272 ModuleManager::ModuleManager(FileManager &FileMgr)
273   : FileMgr(FileMgr), GlobalIndex(), FirstVisitState(nullptr) {}
274 
~ModuleManager()275 ModuleManager::~ModuleManager() {
276   for (unsigned i = 0, e = Chain.size(); i != e; ++i)
277     delete Chain[e - i - 1];
278   delete FirstVisitState;
279 }
280 
281 void
visit(bool (* Visitor)(ModuleFile & M,void * UserData),void * UserData,llvm::SmallPtrSetImpl<ModuleFile * > * ModuleFilesHit)282 ModuleManager::visit(bool (*Visitor)(ModuleFile &M, void *UserData),
283                      void *UserData,
284                      llvm::SmallPtrSetImpl<ModuleFile *> *ModuleFilesHit) {
285   // If the visitation order vector is the wrong size, recompute the order.
286   if (VisitOrder.size() != Chain.size()) {
287     unsigned N = size();
288     VisitOrder.clear();
289     VisitOrder.reserve(N);
290 
291     // Record the number of incoming edges for each module. When we
292     // encounter a module with no incoming edges, push it into the queue
293     // to seed the queue.
294     SmallVector<ModuleFile *, 4> Queue;
295     Queue.reserve(N);
296     llvm::SmallVector<unsigned, 4> UnusedIncomingEdges;
297     UnusedIncomingEdges.reserve(size());
298     for (ModuleIterator M = begin(), MEnd = end(); M != MEnd; ++M) {
299       if (unsigned Size = (*M)->ImportedBy.size())
300         UnusedIncomingEdges.push_back(Size);
301       else {
302         UnusedIncomingEdges.push_back(0);
303         Queue.push_back(*M);
304       }
305     }
306 
307     // Traverse the graph, making sure to visit a module before visiting any
308     // of its dependencies.
309     unsigned QueueStart = 0;
310     while (QueueStart < Queue.size()) {
311       ModuleFile *CurrentModule = Queue[QueueStart++];
312       VisitOrder.push_back(CurrentModule);
313 
314       // For any module that this module depends on, push it on the
315       // stack (if it hasn't already been marked as visited).
316       for (llvm::SetVector<ModuleFile *>::iterator
317              M = CurrentModule->Imports.begin(),
318              MEnd = CurrentModule->Imports.end();
319            M != MEnd; ++M) {
320         // Remove our current module as an impediment to visiting the
321         // module we depend on. If we were the last unvisited module
322         // that depends on this particular module, push it into the
323         // queue to be visited.
324         unsigned &NumUnusedEdges = UnusedIncomingEdges[(*M)->Index];
325         if (NumUnusedEdges && (--NumUnusedEdges == 0))
326           Queue.push_back(*M);
327       }
328     }
329 
330     assert(VisitOrder.size() == N && "Visitation order is wrong?");
331 
332     delete FirstVisitState;
333     FirstVisitState = nullptr;
334   }
335 
336   VisitState *State = allocateVisitState();
337   unsigned VisitNumber = State->NextVisitNumber++;
338 
339   // If the caller has provided us with a hit-set that came from the global
340   // module index, mark every module file in common with the global module
341   // index that is *not* in that set as 'visited'.
342   if (ModuleFilesHit && !ModulesInCommonWithGlobalIndex.empty()) {
343     for (unsigned I = 0, N = ModulesInCommonWithGlobalIndex.size(); I != N; ++I)
344     {
345       ModuleFile *M = ModulesInCommonWithGlobalIndex[I];
346       if (!ModuleFilesHit->count(M))
347         State->VisitNumber[M->Index] = VisitNumber;
348     }
349   }
350 
351   for (unsigned I = 0, N = VisitOrder.size(); I != N; ++I) {
352     ModuleFile *CurrentModule = VisitOrder[I];
353     // Should we skip this module file?
354     if (State->VisitNumber[CurrentModule->Index] == VisitNumber)
355       continue;
356 
357     // Visit the module.
358     assert(State->VisitNumber[CurrentModule->Index] == VisitNumber - 1);
359     State->VisitNumber[CurrentModule->Index] = VisitNumber;
360     if (!Visitor(*CurrentModule, UserData))
361       continue;
362 
363     // The visitor has requested that cut off visitation of any
364     // module that the current module depends on. To indicate this
365     // behavior, we mark all of the reachable modules as having been visited.
366     ModuleFile *NextModule = CurrentModule;
367     do {
368       // For any module that this module depends on, push it on the
369       // stack (if it hasn't already been marked as visited).
370       for (llvm::SetVector<ModuleFile *>::iterator
371              M = NextModule->Imports.begin(),
372              MEnd = NextModule->Imports.end();
373            M != MEnd; ++M) {
374         if (State->VisitNumber[(*M)->Index] != VisitNumber) {
375           State->Stack.push_back(*M);
376           State->VisitNumber[(*M)->Index] = VisitNumber;
377         }
378       }
379 
380       if (State->Stack.empty())
381         break;
382 
383       // Pop the next module off the stack.
384       NextModule = State->Stack.pop_back_val();
385     } while (true);
386   }
387 
388   returnVisitState(State);
389 }
390 
391 /// \brief Perform a depth-first visit of the current module.
visitDepthFirst(ModuleFile & M,bool (* Visitor)(ModuleFile & M,bool Preorder,void * UserData),void * UserData,SmallVectorImpl<bool> & Visited)392 static bool visitDepthFirst(ModuleFile &M,
393                             bool (*Visitor)(ModuleFile &M, bool Preorder,
394                                             void *UserData),
395                             void *UserData,
396                             SmallVectorImpl<bool> &Visited) {
397   // Preorder visitation
398   if (Visitor(M, /*Preorder=*/true, UserData))
399     return true;
400 
401   // Visit children
402   for (llvm::SetVector<ModuleFile *>::iterator IM = M.Imports.begin(),
403                                             IMEnd = M.Imports.end();
404        IM != IMEnd; ++IM) {
405     if (Visited[(*IM)->Index])
406       continue;
407     Visited[(*IM)->Index] = true;
408 
409     if (visitDepthFirst(**IM, Visitor, UserData, Visited))
410       return true;
411   }
412 
413   // Postorder visitation
414   return Visitor(M, /*Preorder=*/false, UserData);
415 }
416 
visitDepthFirst(bool (* Visitor)(ModuleFile & M,bool Preorder,void * UserData),void * UserData)417 void ModuleManager::visitDepthFirst(bool (*Visitor)(ModuleFile &M, bool Preorder,
418                                                     void *UserData),
419                                     void *UserData) {
420   SmallVector<bool, 16> Visited(size(), false);
421   for (unsigned I = 0, N = Chain.size(); I != N; ++I) {
422     if (Visited[Chain[I]->Index])
423       continue;
424     Visited[Chain[I]->Index] = true;
425 
426     if (::visitDepthFirst(*Chain[I], Visitor, UserData, Visited))
427       return;
428   }
429 }
430 
lookupModuleFile(StringRef FileName,off_t ExpectedSize,time_t ExpectedModTime,const FileEntry * & File)431 bool ModuleManager::lookupModuleFile(StringRef FileName,
432                                      off_t ExpectedSize,
433                                      time_t ExpectedModTime,
434                                      const FileEntry *&File) {
435   // Open the file immediately to ensure there is no race between stat'ing and
436   // opening the file.
437   File = FileMgr.getFile(FileName, /*openFile=*/true, /*cacheFailure=*/false);
438 
439   if (!File && FileName != "-") {
440     return false;
441   }
442 
443   if ((ExpectedSize && ExpectedSize != File->getSize()) ||
444       (ExpectedModTime && ExpectedModTime != File->getModificationTime()))
445     // Do not destroy File, as it may be referenced. If we need to rebuild it,
446     // it will be destroyed by removeModules.
447     return true;
448 
449   return false;
450 }
451 
452 #ifndef NDEBUG
453 namespace llvm {
454   template<>
455   struct GraphTraits<ModuleManager> {
456     typedef ModuleFile NodeType;
457     typedef llvm::SetVector<ModuleFile *>::const_iterator ChildIteratorType;
458     typedef ModuleManager::ModuleConstIterator nodes_iterator;
459 
child_beginllvm::GraphTraits460     static ChildIteratorType child_begin(NodeType *Node) {
461       return Node->Imports.begin();
462     }
463 
child_endllvm::GraphTraits464     static ChildIteratorType child_end(NodeType *Node) {
465       return Node->Imports.end();
466     }
467 
nodes_beginllvm::GraphTraits468     static nodes_iterator nodes_begin(const ModuleManager &Manager) {
469       return Manager.begin();
470     }
471 
nodes_endllvm::GraphTraits472     static nodes_iterator nodes_end(const ModuleManager &Manager) {
473       return Manager.end();
474     }
475   };
476 
477   template<>
478   struct DOTGraphTraits<ModuleManager> : public DefaultDOTGraphTraits {
DOTGraphTraitsllvm::DOTGraphTraits479     explicit DOTGraphTraits(bool IsSimple = false)
480       : DefaultDOTGraphTraits(IsSimple) { }
481 
renderGraphFromBottomUpllvm::DOTGraphTraits482     static bool renderGraphFromBottomUp() {
483       return true;
484     }
485 
getNodeLabelllvm::DOTGraphTraits486     std::string getNodeLabel(ModuleFile *M, const ModuleManager&) {
487       return M->ModuleName;
488     }
489   };
490 }
491 
viewGraph()492 void ModuleManager::viewGraph() {
493   llvm::ViewGraph(*this, "Modules");
494 }
495 #endif
496