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