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