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/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
  28 using namespace clang;
  29 using namespace serialization;
  30
  31 ModuleFile *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
  40 ModuleFile *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
  49 std::unique_ptr<llvm::MemoryBuffer>
  50 ModuleManager::lookupBuffer(StringRef Name) {
  51   const FileEntry *Entry = FileMgr.getFile(Name, /*openFile=*/false,
  52                                            /*cacheFailure=*/false);
  53   return std::move(InMemoryBuffers[Entry]);
  54 }
  55
  56 ModuleManager::AddModuleResult
  57 ModuleManager::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 (!ImportedBy)
  99       Roots.push_back(New);
 100     NewModule = true;
 101     ModuleEntry = New;
 102
 103     New->InputFilesValidationTimestamp = 0;
 104     if (New->Kind == MK_ImplicitModule) {
 105       std::string TimestampFilename = New->getTimestampFilename();
 106       vfs::Status Status;
 107       // A cached stat value would be fine as well.
 108       if (!FileMgr.getNoncachedStatValue(TimestampFilename, Status))
 109         New->InputFilesValidationTimestamp =
 110             Status.getLastModificationTime().toEpochTime();
 111     }
 112
 113     // Load the contents of the module
 114     if (std::unique_ptr<llvm::MemoryBuffer> Buffer = lookupBuffer(FileName)) {
 115       // The buffer was already provided for us.
 116       New->Buffer = std::move(Buffer);
 117     } else {
 118       // Open the AST file.
 119       llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Buf(
 120           (std::error_code()));
 121       if (FileName == "-") {
 122         Buf = llvm::MemoryBuffer::getSTDIN();
 123       } else {
 124         // Leave the FileEntry open so if it gets read again by another
 125         // ModuleManager it must be the same underlying file.
 126         // FIXME: Because FileManager::getFile() doesn't guarantee that it will
 127         // give us an open file, this may not be 100% reliable.
 128         Buf = FileMgr.getBufferForFile(New->File,
 129                                        /*IsVolatile=*/false,
 130                                        /*ShouldClose=*/false);
 131       }
 132
 133       if (!Buf) {
 134         ErrorStr = Buf.getError().message();
 135         return Missing;
 136       }
 137
 138       New->Buffer = std::move(*Buf);
 139     }
 140
 141     // Initialize the stream.
 142     PCHContainerRdr.ExtractPCH(New->Buffer->getMemBufferRef(), New->StreamFile);
 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                              const PCHContainerReader &PCHContainerRdr)
 294     : FileMgr(FileMgr), PCHContainerRdr(PCHContainerRdr), GlobalIndex(),
 295       FirstVisitState(nullptr) {}
 296
 297 ModuleManager::~ModuleManager() {
 298   for (unsigned i = 0, e = Chain.size(); i != e; ++i)
 299     delete Chain[e - i - 1];
 300   delete FirstVisitState;
 301 }
 302
 303 void
 304 ModuleManager::visit(bool (*Visitor)(ModuleFile &M, void *UserData),
 305                      void *UserData,
 306                      llvm::SmallPtrSetImpl<ModuleFile *> *ModuleFilesHit) {
 307   // If the visitation order vector is the wrong size, recompute the order.
 308   if (VisitOrder.size() != Chain.size()) {
 309     unsigned N = size();
 310     VisitOrder.clear();
 311     VisitOrder.reserve(N);
 312
 313     // Record the number of incoming edges for each module. When we
 314     // encounter a module with no incoming edges, push it into the queue
 315     // to seed the queue.
 316     SmallVector<ModuleFile *, 4> Queue;
 317     Queue.reserve(N);
 318     llvm::SmallVector<unsigned, 4> UnusedIncomingEdges;
 319     UnusedIncomingEdges.reserve(size());
 320     for (ModuleIterator M = begin(), MEnd = end(); M != MEnd; ++M) {
 321       if (unsigned Size = (*M)->ImportedBy.size())
 322         UnusedIncomingEdges.push_back(Size);
 323       else {
 324         UnusedIncomingEdges.push_back(0);
 325         Queue.push_back(*M);
 326       }
 327     }
 328
 329     // Traverse the graph, making sure to visit a module before visiting any
 330     // of its dependencies.
 331     unsigned QueueStart = 0;
 332     while (QueueStart < Queue.size()) {
 333       ModuleFile *CurrentModule = Queue[QueueStart++];
 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 (llvm::SetVector<ModuleFile *>::iterator
 339              M = CurrentModule->Imports.begin(),
 340              MEnd = CurrentModule->Imports.end();
 341            M != MEnd; ++M) {
 342         // Remove our current module as an impediment to visiting the
 343         // module we depend on. If we were the last unvisited module
 344         // that depends on this particular module, push it into the
 345         // queue to be visited.
 346         unsigned &NumUnusedEdges = UnusedIncomingEdges[(*M)->Index];
 347         if (NumUnusedEdges && (--NumUnusedEdges == 0))
 348           Queue.push_back(*M);
 349       }
 350     }
 351
 352     assert(VisitOrder.size() == N && "Visitation order is wrong?");
 353
 354     delete FirstVisitState;
 355     FirstVisitState = nullptr;
 356   }
 357
 358   VisitState *State = allocateVisitState();
 359   unsigned VisitNumber = State->NextVisitNumber++;
 360
 361   // If the caller has provided us with a hit-set that came from the global
 362   // module index, mark every module file in common with the global module
 363   // index that is *not* in that set as 'visited'.
 364   if (ModuleFilesHit && !ModulesInCommonWithGlobalIndex.empty()) {
 365     for (unsigned I = 0, N = ModulesInCommonWithGlobalIndex.size(); I != N; ++I)
 366     {
 367       ModuleFile *M = ModulesInCommonWithGlobalIndex[I];
 368       if (!ModuleFilesHit->count(M))
 369         State->VisitNumber[M->Index] = VisitNumber;
 370     }
 371   }
 372
 373   for (unsigned I = 0, N = VisitOrder.size(); I != N; ++I) {
 374     ModuleFile *CurrentModule = VisitOrder[I];
 375     // Should we skip this module file?
 376     if (State->VisitNumber[CurrentModule->Index] == VisitNumber)
 377       continue;
 378
 379     // Visit the module.
 380     assert(State->VisitNumber[CurrentModule->Index] == VisitNumber - 1);
 381     State->VisitNumber[CurrentModule->Index] = VisitNumber;
 382     if (!Visitor(*CurrentModule, UserData))
 383       continue;
 384
 385     // The visitor has requested that cut off visitation of any
 386     // module that the current module depends on. To indicate this
 387     // behavior, we mark all of the reachable modules as having been visited.
 388     ModuleFile *NextModule = CurrentModule;
 389     do {
 390       // For any module that this module depends on, push it on the
 391       // stack (if it hasn't already been marked as visited).
 392       for (llvm::SetVector<ModuleFile *>::iterator
 393              M = NextModule->Imports.begin(),
 394              MEnd = NextModule->Imports.end();
 395            M != MEnd; ++M) {
 396         if (State->VisitNumber[(*M)->Index] != VisitNumber) {
 397           State->Stack.push_back(*M);
 398           State->VisitNumber[(*M)->Index] = VisitNumber;
 399         }
 400       }
 401
 402       if (State->Stack.empty())
 403         break;
 404
 405       // Pop the next module off the stack.
 406       NextModule = State->Stack.pop_back_val();
 407     } while (true);
 408   }
 409
 410   returnVisitState(State);
 411 }
 412
 413 static void markVisitedDepthFirst(ModuleFile &M,
 414                                   SmallVectorImpl<bool> &Visited) {
 415   for (llvm::SetVector<ModuleFile *>::iterator IM = M.Imports.begin(),
 416                                                IMEnd = M.Imports.end();
 417        IM != IMEnd; ++IM) {
 418     if (Visited[(*IM)->Index])
 419       continue;
 420     Visited[(*IM)->Index] = true;
 421     if (!M.DirectlyImported)
 422       markVisitedDepthFirst(**IM, Visited);
 423   }
 424 }
 425
 426 /// \brief Perform a depth-first visit of the current module.
 427 static bool visitDepthFirst(
 428     ModuleFile &M,
 429     ModuleManager::DFSPreorderControl (*PreorderVisitor)(ModuleFile &M,
 430                                                          void *UserData),
 431     bool (*PostorderVisitor)(ModuleFile &M, void *UserData), void *UserData,
 432     SmallVectorImpl<bool> &Visited) {
 433   if (PreorderVisitor) {
 434     switch (PreorderVisitor(M, UserData)) {
 435     case ModuleManager::Abort:
 436       return true;
 437     case ModuleManager::SkipImports:
 438       markVisitedDepthFirst(M, Visited);
 439       return false;
 440     case ModuleManager::Continue:
 441       break;
 442     }
 443   }
 444
 445   // Visit children
 446   for (llvm::SetVector<ModuleFile *>::iterator IM = M.Imports.begin(),
 447                                             IMEnd = M.Imports.end();
 448        IM != IMEnd; ++IM) {
 449     if (Visited[(*IM)->Index])
 450       continue;
 451     Visited[(*IM)->Index] = true;
 452
 453     if (visitDepthFirst(**IM, PreorderVisitor, PostorderVisitor, UserData, Visited))
 454       return true;
 455   }
 456
 457   if (PostorderVisitor)
 458     return PostorderVisitor(M, UserData);
 459
 460   return false;
 461 }
 462
 463 void ModuleManager::visitDepthFirst(
 464     ModuleManager::DFSPreorderControl (*PreorderVisitor)(ModuleFile &M,
 465                                                          void *UserData),
 466     bool (*PostorderVisitor)(ModuleFile &M, void *UserData), void *UserData) {
 467   SmallVector<bool, 16> Visited(size(), false);
 468   for (unsigned I = 0, N = Roots.size(); I != N; ++I) {
 469     if (Visited[Roots[I]->Index])
 470       continue;
 471     Visited[Roots[I]->Index] = true;
 472
 473     if (::visitDepthFirst(*Roots[I], PreorderVisitor, PostorderVisitor, UserData, Visited))
 474       return;
 475   }
 476 }
 477
 478 bool ModuleManager::lookupModuleFile(StringRef FileName,
 479                                      off_t ExpectedSize,
 480                                      time_t ExpectedModTime,
 481                                      const FileEntry *&File) {
 482   // Open the file immediately to ensure there is no race between stat'ing and
 483   // opening the file.
 484   File = FileMgr.getFile(FileName, /*openFile=*/true, /*cacheFailure=*/false);
 485
 486   if (!File && FileName != "-") {
 487     return false;
 488   }
 489
 490   if ((ExpectedSize && ExpectedSize != File->getSize()) ||
 491       (ExpectedModTime && ExpectedModTime != File->getModificationTime()))
 492     // Do not destroy File, as it may be referenced. If we need to rebuild it,
 493     // it will be destroyed by removeModules.
 494     return true;
 495
 496   return false;
 497 }
 498
 499 #ifndef NDEBUG
 500 namespace llvm {
 501   template<>
 502   struct GraphTraits<ModuleManager> {
 503     typedef ModuleFile NodeType;
 504     typedef llvm::SetVector<ModuleFile *>::const_iterator ChildIteratorType;
 505     typedef ModuleManager::ModuleConstIterator nodes_iterator;
 506
 507     static ChildIteratorType child_begin(NodeType *Node) {
 508       return Node->Imports.begin();
 509     }
 510
 511     static ChildIteratorType child_end(NodeType *Node) {
 512       return Node->Imports.end();
 513     }
 514
 515     static nodes_iterator nodes_begin(const ModuleManager &Manager) {
 516       return Manager.begin();
 517     }
 518
 519     static nodes_iterator nodes_end(const ModuleManager &Manager) {
 520       return Manager.end();
 521     }
 522   };
 523
 524   template<>
 525   struct DOTGraphTraits<ModuleManager> : public DefaultDOTGraphTraits {
 526     explicit DOTGraphTraits(bool IsSimple = false)
 527       : DefaultDOTGraphTraits(IsSimple) { }
 528
 529     static bool renderGraphFromBottomUp() {
 530       return true;
 531     }
 532
 533     std::string getNodeLabel(ModuleFile *M, const ModuleManager&) {
 534       return M->ModuleName;
 535     }
 536   };
 537 }
 538
 539 void ModuleManager::viewGraph() {
 540   llvm::ViewGraph(*this, "Modules");
 541 }
 542 #endif