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