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