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