contrib/llvm/tools/clang/lib/Serialization/ModuleManager.cpp

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