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