xref: /llvm-project/clang/lib/Serialization/ModuleManager.cpp (revision b55d0226b7139648941466d6e6dc08a05e3902e7)
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/ModuleMap.h"
15 #include "clang/Serialization/GlobalModuleIndex.h"
16 #include "clang/Serialization/ModuleManager.h"
17 #include "llvm/Support/MemoryBuffer.h"
18 #include "llvm/Support/Path.h"
19 #include "llvm/Support/raw_ostream.h"
20 #include "llvm/Support/system_error.h"
21 
22 #ifndef NDEBUG
23 #include "llvm/Support/GraphWriter.h"
24 #endif
25 
26 using namespace clang;
27 using namespace serialization;
28 
29 ModuleFile *ModuleManager::lookup(StringRef Name) {
30   const FileEntry *Entry = FileMgr.getFile(Name, /*openFile=*/false,
31                                            /*cacheFailure=*/false);
32   if (Entry)
33     return lookup(Entry);
34 
35   return 0;
36 }
37 
38 ModuleFile *ModuleManager::lookup(const FileEntry *File) {
39   llvm::DenseMap<const FileEntry *, ModuleFile *>::iterator Known
40     = Modules.find(File);
41   if (Known == Modules.end())
42     return 0;
43 
44   return Known->second;
45 }
46 
47 llvm::MemoryBuffer *ModuleManager::lookupBuffer(StringRef Name) {
48   const FileEntry *Entry = FileMgr.getFile(Name, /*openFile=*/false,
49                                            /*cacheFailure=*/false);
50   return InMemoryBuffers[Entry];
51 }
52 
53 ModuleManager::AddModuleResult
54 ModuleManager::addModule(StringRef FileName, ModuleKind Type,
55                          SourceLocation ImportLoc, ModuleFile *ImportedBy,
56                          unsigned Generation,
57                          off_t ExpectedSize, time_t ExpectedModTime,
58                          ModuleFile *&Module,
59                          std::string &ErrorStr) {
60   Module = 0;
61 
62   // Look for the file entry. This only fails if the expected size or
63   // modification time differ.
64   const FileEntry *Entry;
65   if (lookupModuleFile(FileName, ExpectedSize, ExpectedModTime, Entry)) {
66     ErrorStr = "module file out of date";
67     return OutOfDate;
68   }
69 
70   if (!Entry && FileName != "-") {
71     ErrorStr = "module file not found";
72     return Missing;
73   }
74 
75   // Check whether we already loaded this module, before
76   ModuleFile *&ModuleEntry = Modules[Entry];
77   bool NewModule = false;
78   if (!ModuleEntry) {
79     // Allocate a new module.
80     ModuleFile *New = new ModuleFile(Type, Generation);
81     New->Index = Chain.size();
82     New->FileName = FileName.str();
83     New->File = Entry;
84     New->ImportLoc = ImportLoc;
85     Chain.push_back(New);
86     NewModule = true;
87     ModuleEntry = New;
88 
89     New->InputFilesValidationTimestamp = 0;
90     if (New->Kind == MK_Module) {
91       std::string TimestampFilename = New->getTimestampFilename();
92       vfs::Status Status;
93       // A cached stat value would be fine as well.
94       if (!FileMgr.getNoncachedStatValue(TimestampFilename, Status))
95         New->InputFilesValidationTimestamp =
96             Status.getLastModificationTime().toEpochTime();
97     }
98 
99     // Load the contents of the module
100     if (llvm::MemoryBuffer *Buffer = lookupBuffer(FileName)) {
101       // The buffer was already provided for us.
102       assert(Buffer && "Passed null buffer");
103       New->Buffer.reset(Buffer);
104     } else {
105       // Open the AST file.
106       llvm::error_code ec;
107       if (FileName == "-") {
108         ec = llvm::MemoryBuffer::getSTDIN(New->Buffer);
109         if (ec)
110           ErrorStr = ec.message();
111       } else
112         New->Buffer.reset(FileMgr.getBufferForFile(FileName, &ErrorStr));
113 
114       if (!New->Buffer)
115         return Missing;
116     }
117 
118     // Initialize the stream
119     New->StreamFile.init((const unsigned char *)New->Buffer->getBufferStart(),
120                          (const unsigned char *)New->Buffer->getBufferEnd());
121   }
122 
123   if (ImportedBy) {
124     ModuleEntry->ImportedBy.insert(ImportedBy);
125     ImportedBy->Imports.insert(ModuleEntry);
126   } else {
127     if (!ModuleEntry->DirectlyImported)
128       ModuleEntry->ImportLoc = ImportLoc;
129 
130     ModuleEntry->DirectlyImported = true;
131   }
132 
133   Module = ModuleEntry;
134   return NewModule? NewlyLoaded : AlreadyLoaded;
135 }
136 
137 void ModuleManager::removeModules(ModuleIterator first, ModuleIterator last,
138                                   ModuleMap *modMap) {
139   if (first == last)
140     return;
141 
142   // Collect the set of module file pointers that we'll be removing.
143   llvm::SmallPtrSet<ModuleFile *, 4> victimSet(first, last);
144 
145   // Remove any references to the now-destroyed modules.
146   for (unsigned i = 0, n = Chain.size(); i != n; ++i) {
147     Chain[i]->ImportedBy.remove_if([&](ModuleFile *MF) {
148       return victimSet.count(MF);
149     });
150   }
151 
152   // Delete the modules and erase them from the various structures.
153   for (ModuleIterator victim = first; victim != last; ++victim) {
154     Modules.erase((*victim)->File);
155 
156     FileMgr.invalidateCache((*victim)->File);
157     if (modMap) {
158       StringRef ModuleName = llvm::sys::path::stem((*victim)->FileName);
159       if (Module *mod = modMap->findModule(ModuleName)) {
160         mod->setASTFile(0);
161       }
162     }
163     delete *victim;
164   }
165 
166   // Remove the modules from the chain.
167   Chain.erase(first, last);
168 }
169 
170 void ModuleManager::addInMemoryBuffer(StringRef FileName,
171                                       llvm::MemoryBuffer *Buffer) {
172 
173   const FileEntry *Entry = FileMgr.getVirtualFile(FileName,
174                                                   Buffer->getBufferSize(), 0);
175   InMemoryBuffers[Entry] = Buffer;
176 }
177 
178 ModuleManager::VisitState *ModuleManager::allocateVisitState() {
179   // Fast path: if we have a cached state, use it.
180   if (FirstVisitState) {
181     VisitState *Result = FirstVisitState;
182     FirstVisitState = FirstVisitState->NextState;
183     Result->NextState = 0;
184     return Result;
185   }
186 
187   // Allocate and return a new state.
188   return new VisitState(size());
189 }
190 
191 void ModuleManager::returnVisitState(VisitState *State) {
192   assert(State->NextState == 0 && "Visited state is in list?");
193   State->NextState = FirstVisitState;
194   FirstVisitState = State;
195 }
196 
197 void ModuleManager::setGlobalIndex(GlobalModuleIndex *Index) {
198   GlobalIndex = Index;
199   if (!GlobalIndex) {
200     ModulesInCommonWithGlobalIndex.clear();
201     return;
202   }
203 
204   // Notify the global module index about all of the modules we've already
205   // loaded.
206   for (unsigned I = 0, N = Chain.size(); I != N; ++I) {
207     if (!GlobalIndex->loadedModuleFile(Chain[I])) {
208       ModulesInCommonWithGlobalIndex.push_back(Chain[I]);
209     }
210   }
211 }
212 
213 void ModuleManager::moduleFileAccepted(ModuleFile *MF) {
214   if (!GlobalIndex || GlobalIndex->loadedModuleFile(MF))
215     return;
216 
217   ModulesInCommonWithGlobalIndex.push_back(MF);
218 }
219 
220 ModuleManager::ModuleManager(FileManager &FileMgr)
221   : FileMgr(FileMgr), GlobalIndex(), FirstVisitState(0) { }
222 
223 ModuleManager::~ModuleManager() {
224   for (unsigned i = 0, e = Chain.size(); i != e; ++i)
225     delete Chain[e - i - 1];
226   delete FirstVisitState;
227 }
228 
229 void
230 ModuleManager::visit(bool (*Visitor)(ModuleFile &M, void *UserData),
231                      void *UserData,
232                      llvm::SmallPtrSet<ModuleFile *, 4> *ModuleFilesHit) {
233   // If the visitation order vector is the wrong size, recompute the order.
234   if (VisitOrder.size() != Chain.size()) {
235     unsigned N = size();
236     VisitOrder.clear();
237     VisitOrder.reserve(N);
238 
239     // Record the number of incoming edges for each module. When we
240     // encounter a module with no incoming edges, push it into the queue
241     // to seed the queue.
242     SmallVector<ModuleFile *, 4> Queue;
243     Queue.reserve(N);
244     llvm::SmallVector<unsigned, 4> UnusedIncomingEdges;
245     UnusedIncomingEdges.reserve(size());
246     for (ModuleIterator M = begin(), MEnd = end(); M != MEnd; ++M) {
247       if (unsigned Size = (*M)->ImportedBy.size())
248         UnusedIncomingEdges.push_back(Size);
249       else {
250         UnusedIncomingEdges.push_back(0);
251         Queue.push_back(*M);
252       }
253     }
254 
255     // Traverse the graph, making sure to visit a module before visiting any
256     // of its dependencies.
257     unsigned QueueStart = 0;
258     while (QueueStart < Queue.size()) {
259       ModuleFile *CurrentModule = Queue[QueueStart++];
260       VisitOrder.push_back(CurrentModule);
261 
262       // For any module that this module depends on, push it on the
263       // stack (if it hasn't already been marked as visited).
264       for (llvm::SetVector<ModuleFile *>::iterator
265              M = CurrentModule->Imports.begin(),
266              MEnd = CurrentModule->Imports.end();
267            M != MEnd; ++M) {
268         // Remove our current module as an impediment to visiting the
269         // module we depend on. If we were the last unvisited module
270         // that depends on this particular module, push it into the
271         // queue to be visited.
272         unsigned &NumUnusedEdges = UnusedIncomingEdges[(*M)->Index];
273         if (NumUnusedEdges && (--NumUnusedEdges == 0))
274           Queue.push_back(*M);
275       }
276     }
277 
278     assert(VisitOrder.size() == N && "Visitation order is wrong?");
279 
280     delete FirstVisitState;
281     FirstVisitState = 0;
282   }
283 
284   VisitState *State = allocateVisitState();
285   unsigned VisitNumber = State->NextVisitNumber++;
286 
287   // If the caller has provided us with a hit-set that came from the global
288   // module index, mark every module file in common with the global module
289   // index that is *not* in that set as 'visited'.
290   if (ModuleFilesHit && !ModulesInCommonWithGlobalIndex.empty()) {
291     for (unsigned I = 0, N = ModulesInCommonWithGlobalIndex.size(); I != N; ++I)
292     {
293       ModuleFile *M = ModulesInCommonWithGlobalIndex[I];
294       if (!ModuleFilesHit->count(M))
295         State->VisitNumber[M->Index] = VisitNumber;
296     }
297   }
298 
299   for (unsigned I = 0, N = VisitOrder.size(); I != N; ++I) {
300     ModuleFile *CurrentModule = VisitOrder[I];
301     // Should we skip this module file?
302     if (State->VisitNumber[CurrentModule->Index] == VisitNumber)
303       continue;
304 
305     // Visit the module.
306     assert(State->VisitNumber[CurrentModule->Index] == VisitNumber - 1);
307     State->VisitNumber[CurrentModule->Index] = VisitNumber;
308     if (!Visitor(*CurrentModule, UserData))
309       continue;
310 
311     // The visitor has requested that cut off visitation of any
312     // module that the current module depends on. To indicate this
313     // behavior, we mark all of the reachable modules as having been visited.
314     ModuleFile *NextModule = CurrentModule;
315     do {
316       // For any module that this module depends on, push it on the
317       // stack (if it hasn't already been marked as visited).
318       for (llvm::SetVector<ModuleFile *>::iterator
319              M = NextModule->Imports.begin(),
320              MEnd = NextModule->Imports.end();
321            M != MEnd; ++M) {
322         if (State->VisitNumber[(*M)->Index] != VisitNumber) {
323           State->Stack.push_back(*M);
324           State->VisitNumber[(*M)->Index] = VisitNumber;
325         }
326       }
327 
328       if (State->Stack.empty())
329         break;
330 
331       // Pop the next module off the stack.
332       NextModule = State->Stack.pop_back_val();
333     } while (true);
334   }
335 
336   returnVisitState(State);
337 }
338 
339 /// \brief Perform a depth-first visit of the current module.
340 static bool visitDepthFirst(ModuleFile &M,
341                             bool (*Visitor)(ModuleFile &M, bool Preorder,
342                                             void *UserData),
343                             void *UserData,
344                             SmallVectorImpl<bool> &Visited) {
345   // Preorder visitation
346   if (Visitor(M, /*Preorder=*/true, UserData))
347     return true;
348 
349   // Visit children
350   for (llvm::SetVector<ModuleFile *>::iterator IM = M.Imports.begin(),
351                                             IMEnd = M.Imports.end();
352        IM != IMEnd; ++IM) {
353     if (Visited[(*IM)->Index])
354       continue;
355     Visited[(*IM)->Index] = true;
356 
357     if (visitDepthFirst(**IM, Visitor, UserData, Visited))
358       return true;
359   }
360 
361   // Postorder visitation
362   return Visitor(M, /*Preorder=*/false, UserData);
363 }
364 
365 void ModuleManager::visitDepthFirst(bool (*Visitor)(ModuleFile &M, bool Preorder,
366                                                     void *UserData),
367                                     void *UserData) {
368   SmallVector<bool, 16> Visited(size(), false);
369   for (unsigned I = 0, N = Chain.size(); I != N; ++I) {
370     if (Visited[Chain[I]->Index])
371       continue;
372     Visited[Chain[I]->Index] = true;
373 
374     if (::visitDepthFirst(*Chain[I], Visitor, UserData, Visited))
375       return;
376   }
377 }
378 
379 bool ModuleManager::lookupModuleFile(StringRef FileName,
380                                      off_t ExpectedSize,
381                                      time_t ExpectedModTime,
382                                      const FileEntry *&File) {
383   File = FileMgr.getFile(FileName, /*openFile=*/false, /*cacheFailure=*/false);
384 
385   if (!File && FileName != "-") {
386     return false;
387   }
388 
389   if ((ExpectedSize && ExpectedSize != File->getSize()) ||
390       (ExpectedModTime && ExpectedModTime != File->getModificationTime())) {
391     return true;
392   }
393 
394   return false;
395 }
396 
397 #ifndef NDEBUG
398 namespace llvm {
399   template<>
400   struct GraphTraits<ModuleManager> {
401     typedef ModuleFile NodeType;
402     typedef llvm::SetVector<ModuleFile *>::const_iterator ChildIteratorType;
403     typedef ModuleManager::ModuleConstIterator nodes_iterator;
404 
405     static ChildIteratorType child_begin(NodeType *Node) {
406       return Node->Imports.begin();
407     }
408 
409     static ChildIteratorType child_end(NodeType *Node) {
410       return Node->Imports.end();
411     }
412 
413     static nodes_iterator nodes_begin(const ModuleManager &Manager) {
414       return Manager.begin();
415     }
416 
417     static nodes_iterator nodes_end(const ModuleManager &Manager) {
418       return Manager.end();
419     }
420   };
421 
422   template<>
423   struct DOTGraphTraits<ModuleManager> : public DefaultDOTGraphTraits {
424     explicit DOTGraphTraits(bool IsSimple = false)
425       : DefaultDOTGraphTraits(IsSimple) { }
426 
427     static bool renderGraphFromBottomUp() {
428       return true;
429     }
430 
431     std::string getNodeLabel(ModuleFile *M, const ModuleManager&) {
432       return llvm::sys::path::stem(M->FileName);
433     }
434   };
435 }
436 
437 void ModuleManager::viewGraph() {
438   llvm::ViewGraph(*this, "Modules");
439 }
440 #endif
441