ModuleManager.cpp revision 263509
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 26using namespace clang; 27using namespace serialization; 28 29ModuleFile *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 38ModuleFile *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 47llvm::MemoryBuffer *ModuleManager::lookupBuffer(StringRef Name) { 48 const FileEntry *Entry = FileMgr.getFile(Name, /*openFile=*/false, 49 /*cacheFailure=*/false); 50 return InMemoryBuffers[Entry]; 51} 52 53ModuleManager::AddModuleResult 54ModuleManager::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 127namespace { 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 143void 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 175void 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 183ModuleManager::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 196void ModuleManager::returnVisitState(VisitState *State) { 197 assert(State->NextState == 0 && "Visited state is in list?"); 198 State->NextState = FirstVisitState; 199 FirstVisitState = State; 200} 201 202void 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 218void ModuleManager::moduleFileAccepted(ModuleFile *MF) { 219 if (!GlobalIndex || GlobalIndex->loadedModuleFile(MF)) 220 return; 221 222 ModulesInCommonWithGlobalIndex.push_back(MF); 223} 224 225ModuleManager::ModuleManager(FileManager &FileMgr) 226 : FileMgr(FileMgr), GlobalIndex(), FirstVisitState(0) { } 227 228ModuleManager::~ModuleManager() { 229 for (unsigned i = 0, e = Chain.size(); i != e; ++i) 230 delete Chain[e - i - 1]; 231 delete FirstVisitState; 232} 233 234void 235ModuleManager::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. 345static 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 370void 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 384bool 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 403namespace 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 442void ModuleManager::viewGraph() { 443 llvm::ViewGraph(*this, "Modules"); 444} 445#endif 446