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