1226586Sdim//===--- ModuleManager.cpp - Module Manager ---------------------*- C++ -*-===// 2226586Sdim// 3226586Sdim// The LLVM Compiler Infrastructure 4226586Sdim// 5226586Sdim// This file is distributed under the University of Illinois Open Source 6226586Sdim// License. See LICENSE.TXT for details. 7226586Sdim// 8226586Sdim//===----------------------------------------------------------------------===// 9226586Sdim// 10226586Sdim// This file defines the ModuleManager class, which manages a set of loaded 11226586Sdim// modules for the ASTReader. 12226586Sdim// 13226586Sdim//===----------------------------------------------------------------------===// 14252723Sdim#include "clang/Lex/ModuleMap.h" 15263509Sdim#include "clang/Serialization/GlobalModuleIndex.h" 16226586Sdim#include "clang/Serialization/ModuleManager.h" 17226586Sdim#include "llvm/Support/MemoryBuffer.h" 18263509Sdim#include "llvm/Support/Path.h" 19226586Sdim#include "llvm/Support/raw_ostream.h" 20226586Sdim#include "llvm/Support/system_error.h" 21226586Sdim 22226586Sdim#ifndef NDEBUG 23226586Sdim#include "llvm/Support/GraphWriter.h" 24226586Sdim#endif 25226586Sdim 26226586Sdimusing namespace clang; 27226586Sdimusing namespace serialization; 28226586Sdim 29235633SdimModuleFile *ModuleManager::lookup(StringRef Name) { 30252723Sdim const FileEntry *Entry = FileMgr.getFile(Name, /*openFile=*/false, 31252723Sdim /*cacheFailure=*/false); 32252723Sdim if (Entry) 33252723Sdim return lookup(Entry); 34252723Sdim 35252723Sdim return 0; 36226586Sdim} 37226586Sdim 38252723SdimModuleFile *ModuleManager::lookup(const FileEntry *File) { 39252723Sdim llvm::DenseMap<const FileEntry *, ModuleFile *>::iterator Known 40252723Sdim = Modules.find(File); 41252723Sdim if (Known == Modules.end()) 42252723Sdim return 0; 43252723Sdim 44252723Sdim return Known->second; 45252723Sdim} 46252723Sdim 47226586Sdimllvm::MemoryBuffer *ModuleManager::lookupBuffer(StringRef Name) { 48252723Sdim const FileEntry *Entry = FileMgr.getFile(Name, /*openFile=*/false, 49252723Sdim /*cacheFailure=*/false); 50226586Sdim return InMemoryBuffers[Entry]; 51226586Sdim} 52226586Sdim 53252723SdimModuleManager::AddModuleResult 54252723SdimModuleManager::addModule(StringRef FileName, ModuleKind Type, 55252723Sdim SourceLocation ImportLoc, ModuleFile *ImportedBy, 56252723Sdim unsigned Generation, 57252723Sdim off_t ExpectedSize, time_t ExpectedModTime, 58252723Sdim ModuleFile *&Module, 59235633Sdim std::string &ErrorStr) { 60252723Sdim Module = 0; 61252723Sdim 62252723Sdim // Look for the file entry. This only fails if the expected size or 63252723Sdim // modification time differ. 64252723Sdim const FileEntry *Entry; 65263509Sdim if (lookupModuleFile(FileName, ExpectedSize, ExpectedModTime, Entry)) { 66263509Sdim ErrorStr = "module file out of date"; 67252723Sdim return OutOfDate; 68263509Sdim } 69252723Sdim 70226586Sdim if (!Entry && FileName != "-") { 71263509Sdim ErrorStr = "module file not found"; 72252723Sdim return Missing; 73226586Sdim } 74252723Sdim 75252723Sdim // Check whether we already loaded this module, before 76235633Sdim ModuleFile *&ModuleEntry = Modules[Entry]; 77226586Sdim bool NewModule = false; 78226586Sdim if (!ModuleEntry) { 79226586Sdim // Allocate a new module. 80235633Sdim ModuleFile *New = new ModuleFile(Type, Generation); 81252723Sdim New->Index = Chain.size(); 82226586Sdim New->FileName = FileName.str(); 83245431Sdim New->File = Entry; 84252723Sdim New->ImportLoc = ImportLoc; 85226586Sdim Chain.push_back(New); 86226586Sdim NewModule = true; 87226586Sdim ModuleEntry = New; 88252723Sdim 89226586Sdim // Load the contents of the module 90226586Sdim if (llvm::MemoryBuffer *Buffer = lookupBuffer(FileName)) { 91226586Sdim // The buffer was already provided for us. 92226586Sdim assert(Buffer && "Passed null buffer"); 93226586Sdim New->Buffer.reset(Buffer); 94226586Sdim } else { 95226586Sdim // Open the AST file. 96226586Sdim llvm::error_code ec; 97226586Sdim if (FileName == "-") { 98226586Sdim ec = llvm::MemoryBuffer::getSTDIN(New->Buffer); 99226586Sdim if (ec) 100226586Sdim ErrorStr = ec.message(); 101226586Sdim } else 102226586Sdim New->Buffer.reset(FileMgr.getBufferForFile(FileName, &ErrorStr)); 103226586Sdim 104226586Sdim if (!New->Buffer) 105252723Sdim return Missing; 106226586Sdim } 107226586Sdim 108226586Sdim // Initialize the stream 109226586Sdim New->StreamFile.init((const unsigned char *)New->Buffer->getBufferStart(), 110252723Sdim (const unsigned char *)New->Buffer->getBufferEnd()); 111252723Sdim } 112226586Sdim 113226586Sdim if (ImportedBy) { 114226586Sdim ModuleEntry->ImportedBy.insert(ImportedBy); 115226586Sdim ImportedBy->Imports.insert(ModuleEntry); 116226586Sdim } else { 117252723Sdim if (!ModuleEntry->DirectlyImported) 118252723Sdim ModuleEntry->ImportLoc = ImportLoc; 119252723Sdim 120226586Sdim ModuleEntry->DirectlyImported = true; 121226586Sdim } 122252723Sdim 123252723Sdim Module = ModuleEntry; 124252723Sdim return NewModule? NewlyLoaded : AlreadyLoaded; 125226586Sdim} 126226586Sdim 127245431Sdimnamespace { 128245431Sdim /// \brief Predicate that checks whether a module file occurs within 129245431Sdim /// the given set. 130245431Sdim class IsInModuleFileSet : public std::unary_function<ModuleFile *, bool> { 131245431Sdim llvm::SmallPtrSet<ModuleFile *, 4> &Removed; 132245431Sdim 133245431Sdim public: 134245431Sdim IsInModuleFileSet(llvm::SmallPtrSet<ModuleFile *, 4> &Removed) 135245431Sdim : Removed(Removed) { } 136245431Sdim 137245431Sdim bool operator()(ModuleFile *MF) const { 138245431Sdim return Removed.count(MF); 139245431Sdim } 140245431Sdim }; 141245431Sdim} 142245431Sdim 143252723Sdimvoid ModuleManager::removeModules(ModuleIterator first, ModuleIterator last, 144252723Sdim ModuleMap *modMap) { 145245431Sdim if (first == last) 146245431Sdim return; 147245431Sdim 148245431Sdim // Collect the set of module file pointers that we'll be removing. 149245431Sdim llvm::SmallPtrSet<ModuleFile *, 4> victimSet(first, last); 150245431Sdim 151245431Sdim // Remove any references to the now-destroyed modules. 152245431Sdim IsInModuleFileSet checkInSet(victimSet); 153245431Sdim for (unsigned i = 0, n = Chain.size(); i != n; ++i) { 154245431Sdim Chain[i]->ImportedBy.remove_if(checkInSet); 155245431Sdim } 156245431Sdim 157245431Sdim // Delete the modules and erase them from the various structures. 158245431Sdim for (ModuleIterator victim = first; victim != last; ++victim) { 159245431Sdim Modules.erase((*victim)->File); 160252723Sdim 161252723Sdim FileMgr.invalidateCache((*victim)->File); 162252723Sdim if (modMap) { 163252723Sdim StringRef ModuleName = llvm::sys::path::stem((*victim)->FileName); 164252723Sdim if (Module *mod = modMap->findModule(ModuleName)) { 165252723Sdim mod->setASTFile(0); 166252723Sdim } 167252723Sdim } 168245431Sdim delete *victim; 169245431Sdim } 170245431Sdim 171245431Sdim // Remove the modules from the chain. 172245431Sdim Chain.erase(first, last); 173245431Sdim} 174245431Sdim 175226586Sdimvoid ModuleManager::addInMemoryBuffer(StringRef FileName, 176226586Sdim llvm::MemoryBuffer *Buffer) { 177226586Sdim 178226586Sdim const FileEntry *Entry = FileMgr.getVirtualFile(FileName, 179226586Sdim Buffer->getBufferSize(), 0); 180226586Sdim InMemoryBuffers[Entry] = Buffer; 181226586Sdim} 182226586Sdim 183252723SdimModuleManager::VisitState *ModuleManager::allocateVisitState() { 184252723Sdim // Fast path: if we have a cached state, use it. 185252723Sdim if (FirstVisitState) { 186252723Sdim VisitState *Result = FirstVisitState; 187252723Sdim FirstVisitState = FirstVisitState->NextState; 188252723Sdim Result->NextState = 0; 189252723Sdim return Result; 190252723Sdim } 191226586Sdim 192252723Sdim // Allocate and return a new state. 193252723Sdim return new VisitState(size()); 194252723Sdim} 195252723Sdim 196252723Sdimvoid ModuleManager::returnVisitState(VisitState *State) { 197252723Sdim assert(State->NextState == 0 && "Visited state is in list?"); 198252723Sdim State->NextState = FirstVisitState; 199252723Sdim FirstVisitState = State; 200252723Sdim} 201252723Sdim 202252723Sdimvoid ModuleManager::setGlobalIndex(GlobalModuleIndex *Index) { 203252723Sdim GlobalIndex = Index; 204252723Sdim if (!GlobalIndex) { 205252723Sdim ModulesInCommonWithGlobalIndex.clear(); 206252723Sdim return; 207252723Sdim } 208252723Sdim 209252723Sdim // Notify the global module index about all of the modules we've already 210252723Sdim // loaded. 211252723Sdim for (unsigned I = 0, N = Chain.size(); I != N; ++I) { 212252723Sdim if (!GlobalIndex->loadedModuleFile(Chain[I])) { 213252723Sdim ModulesInCommonWithGlobalIndex.push_back(Chain[I]); 214252723Sdim } 215252723Sdim } 216252723Sdim} 217252723Sdim 218252723Sdimvoid ModuleManager::moduleFileAccepted(ModuleFile *MF) { 219252723Sdim if (!GlobalIndex || GlobalIndex->loadedModuleFile(MF)) 220252723Sdim return; 221252723Sdim 222252723Sdim ModulesInCommonWithGlobalIndex.push_back(MF); 223252723Sdim} 224252723Sdim 225252723SdimModuleManager::ModuleManager(FileManager &FileMgr) 226252723Sdim : FileMgr(FileMgr), GlobalIndex(), FirstVisitState(0) { } 227252723Sdim 228226586SdimModuleManager::~ModuleManager() { 229226586Sdim for (unsigned i = 0, e = Chain.size(); i != e; ++i) 230226586Sdim delete Chain[e - i - 1]; 231252723Sdim delete FirstVisitState; 232226586Sdim} 233226586Sdim 234252723Sdimvoid 235252723SdimModuleManager::visit(bool (*Visitor)(ModuleFile &M, void *UserData), 236252723Sdim void *UserData, 237252723Sdim llvm::SmallPtrSet<ModuleFile *, 4> *ModuleFilesHit) { 238252723Sdim // If the visitation order vector is the wrong size, recompute the order. 239252723Sdim if (VisitOrder.size() != Chain.size()) { 240252723Sdim unsigned N = size(); 241252723Sdim VisitOrder.clear(); 242252723Sdim VisitOrder.reserve(N); 243252723Sdim 244252723Sdim // Record the number of incoming edges for each module. When we 245252723Sdim // encounter a module with no incoming edges, push it into the queue 246252723Sdim // to seed the queue. 247252723Sdim SmallVector<ModuleFile *, 4> Queue; 248252723Sdim Queue.reserve(N); 249252723Sdim llvm::SmallVector<unsigned, 4> UnusedIncomingEdges; 250252723Sdim UnusedIncomingEdges.reserve(size()); 251252723Sdim for (ModuleIterator M = begin(), MEnd = end(); M != MEnd; ++M) { 252252723Sdim if (unsigned Size = (*M)->ImportedBy.size()) 253252723Sdim UnusedIncomingEdges.push_back(Size); 254252723Sdim else { 255252723Sdim UnusedIncomingEdges.push_back(0); 256252723Sdim Queue.push_back(*M); 257252723Sdim } 258252723Sdim } 259252723Sdim 260252723Sdim // Traverse the graph, making sure to visit a module before visiting any 261252723Sdim // of its dependencies. 262252723Sdim unsigned QueueStart = 0; 263252723Sdim while (QueueStart < Queue.size()) { 264252723Sdim ModuleFile *CurrentModule = Queue[QueueStart++]; 265252723Sdim VisitOrder.push_back(CurrentModule); 266252723Sdim 267252723Sdim // For any module that this module depends on, push it on the 268252723Sdim // stack (if it hasn't already been marked as visited). 269252723Sdim for (llvm::SetVector<ModuleFile *>::iterator 270252723Sdim M = CurrentModule->Imports.begin(), 271252723Sdim MEnd = CurrentModule->Imports.end(); 272252723Sdim M != MEnd; ++M) { 273252723Sdim // Remove our current module as an impediment to visiting the 274252723Sdim // module we depend on. If we were the last unvisited module 275252723Sdim // that depends on this particular module, push it into the 276252723Sdim // queue to be visited. 277252723Sdim unsigned &NumUnusedEdges = UnusedIncomingEdges[(*M)->Index]; 278252723Sdim if (NumUnusedEdges && (--NumUnusedEdges == 0)) 279252723Sdim Queue.push_back(*M); 280252723Sdim } 281252723Sdim } 282252723Sdim 283252723Sdim assert(VisitOrder.size() == N && "Visitation order is wrong?"); 284252723Sdim 285252723Sdim delete FirstVisitState; 286252723Sdim FirstVisitState = 0; 287226586Sdim } 288252723Sdim 289252723Sdim VisitState *State = allocateVisitState(); 290252723Sdim unsigned VisitNumber = State->NextVisitNumber++; 291252723Sdim 292252723Sdim // If the caller has provided us with a hit-set that came from the global 293252723Sdim // module index, mark every module file in common with the global module 294252723Sdim // index that is *not* in that set as 'visited'. 295252723Sdim if (ModuleFilesHit && !ModulesInCommonWithGlobalIndex.empty()) { 296252723Sdim for (unsigned I = 0, N = ModulesInCommonWithGlobalIndex.size(); I != N; ++I) 297252723Sdim { 298252723Sdim ModuleFile *M = ModulesInCommonWithGlobalIndex[I]; 299252723Sdim if (!ModuleFilesHit->count(M)) 300252723Sdim State->VisitNumber[M->Index] = VisitNumber; 301252723Sdim } 302252723Sdim } 303252723Sdim 304252723Sdim for (unsigned I = 0, N = VisitOrder.size(); I != N; ++I) { 305252723Sdim ModuleFile *CurrentModule = VisitOrder[I]; 306252723Sdim // Should we skip this module file? 307252723Sdim if (State->VisitNumber[CurrentModule->Index] == VisitNumber) 308226586Sdim continue; 309252723Sdim 310252723Sdim // Visit the module. 311252723Sdim assert(State->VisitNumber[CurrentModule->Index] == VisitNumber - 1); 312252723Sdim State->VisitNumber[CurrentModule->Index] = VisitNumber; 313252723Sdim if (!Visitor(*CurrentModule, UserData)) 314252723Sdim continue; 315252723Sdim 316252723Sdim // The visitor has requested that cut off visitation of any 317252723Sdim // module that the current module depends on. To indicate this 318252723Sdim // behavior, we mark all of the reachable modules as having been visited. 319252723Sdim ModuleFile *NextModule = CurrentModule; 320252723Sdim do { 321252723Sdim // For any module that this module depends on, push it on the 322252723Sdim // stack (if it hasn't already been marked as visited). 323252723Sdim for (llvm::SetVector<ModuleFile *>::iterator 324226586Sdim M = NextModule->Imports.begin(), 325226586Sdim MEnd = NextModule->Imports.end(); 326252723Sdim M != MEnd; ++M) { 327252723Sdim if (State->VisitNumber[(*M)->Index] != VisitNumber) { 328252723Sdim State->Stack.push_back(*M); 329252723Sdim State->VisitNumber[(*M)->Index] = VisitNumber; 330226586Sdim } 331226586Sdim } 332252723Sdim 333252723Sdim if (State->Stack.empty()) 334252723Sdim break; 335252723Sdim 336252723Sdim // Pop the next module off the stack. 337263509Sdim NextModule = State->Stack.pop_back_val(); 338252723Sdim } while (true); 339226586Sdim } 340252723Sdim 341252723Sdim returnVisitState(State); 342226586Sdim} 343226586Sdim 344226586Sdim/// \brief Perform a depth-first visit of the current module. 345235633Sdimstatic bool visitDepthFirst(ModuleFile &M, 346235633Sdim bool (*Visitor)(ModuleFile &M, bool Preorder, 347226586Sdim void *UserData), 348226586Sdim void *UserData, 349252723Sdim SmallVectorImpl<bool> &Visited) { 350226586Sdim // Preorder visitation 351226586Sdim if (Visitor(M, /*Preorder=*/true, UserData)) 352226586Sdim return true; 353226586Sdim 354226586Sdim // Visit children 355235633Sdim for (llvm::SetVector<ModuleFile *>::iterator IM = M.Imports.begin(), 356252723Sdim IMEnd = M.Imports.end(); 357226586Sdim IM != IMEnd; ++IM) { 358252723Sdim if (Visited[(*IM)->Index]) 359226586Sdim continue; 360252723Sdim Visited[(*IM)->Index] = true; 361252723Sdim 362226586Sdim if (visitDepthFirst(**IM, Visitor, UserData, Visited)) 363226586Sdim return true; 364226586Sdim } 365226586Sdim 366226586Sdim // Postorder visitation 367226586Sdim return Visitor(M, /*Preorder=*/false, UserData); 368226586Sdim} 369226586Sdim 370235633Sdimvoid ModuleManager::visitDepthFirst(bool (*Visitor)(ModuleFile &M, bool Preorder, 371226586Sdim void *UserData), 372226586Sdim void *UserData) { 373252723Sdim SmallVector<bool, 16> Visited(size(), false); 374226586Sdim for (unsigned I = 0, N = Chain.size(); I != N; ++I) { 375252723Sdim if (Visited[Chain[I]->Index]) 376226586Sdim continue; 377252723Sdim Visited[Chain[I]->Index] = true; 378252723Sdim 379226586Sdim if (::visitDepthFirst(*Chain[I], Visitor, UserData, Visited)) 380226586Sdim return; 381226586Sdim } 382226586Sdim} 383226586Sdim 384252723Sdimbool ModuleManager::lookupModuleFile(StringRef FileName, 385252723Sdim off_t ExpectedSize, 386252723Sdim time_t ExpectedModTime, 387252723Sdim const FileEntry *&File) { 388252723Sdim File = FileMgr.getFile(FileName, /*openFile=*/false, /*cacheFailure=*/false); 389252723Sdim 390252723Sdim if (!File && FileName != "-") { 391252723Sdim return false; 392252723Sdim } 393252723Sdim 394252723Sdim if ((ExpectedSize && ExpectedSize != File->getSize()) || 395252723Sdim (ExpectedModTime && ExpectedModTime != File->getModificationTime())) { 396252723Sdim return true; 397252723Sdim } 398252723Sdim 399252723Sdim return false; 400252723Sdim} 401252723Sdim 402226586Sdim#ifndef NDEBUG 403226586Sdimnamespace llvm { 404226586Sdim template<> 405226586Sdim struct GraphTraits<ModuleManager> { 406235633Sdim typedef ModuleFile NodeType; 407235633Sdim typedef llvm::SetVector<ModuleFile *>::const_iterator ChildIteratorType; 408226586Sdim typedef ModuleManager::ModuleConstIterator nodes_iterator; 409226586Sdim 410226586Sdim static ChildIteratorType child_begin(NodeType *Node) { 411226586Sdim return Node->Imports.begin(); 412226586Sdim } 413226586Sdim 414226586Sdim static ChildIteratorType child_end(NodeType *Node) { 415226586Sdim return Node->Imports.end(); 416226586Sdim } 417226586Sdim 418226586Sdim static nodes_iterator nodes_begin(const ModuleManager &Manager) { 419226586Sdim return Manager.begin(); 420226586Sdim } 421226586Sdim 422226586Sdim static nodes_iterator nodes_end(const ModuleManager &Manager) { 423226586Sdim return Manager.end(); 424226586Sdim } 425226586Sdim }; 426226586Sdim 427226586Sdim template<> 428226586Sdim struct DOTGraphTraits<ModuleManager> : public DefaultDOTGraphTraits { 429226586Sdim explicit DOTGraphTraits(bool IsSimple = false) 430226586Sdim : DefaultDOTGraphTraits(IsSimple) { } 431226586Sdim 432226586Sdim static bool renderGraphFromBottomUp() { 433226586Sdim return true; 434226586Sdim } 435226586Sdim 436235633Sdim std::string getNodeLabel(ModuleFile *M, const ModuleManager&) { 437226586Sdim return llvm::sys::path::stem(M->FileName); 438226586Sdim } 439226586Sdim }; 440226586Sdim} 441226586Sdim 442226586Sdimvoid ModuleManager::viewGraph() { 443226586Sdim llvm::ViewGraph(*this, "Modules"); 444226586Sdim} 445226586Sdim#endif 446