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