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