SourceManager.cpp revision 194711
1//===--- SourceManager.cpp - Track and cache source files -----------------===// 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 implements the SourceManager interface. 11// 12//===----------------------------------------------------------------------===// 13 14#include "clang/Basic/SourceManager.h" 15#include "clang/Basic/SourceManagerInternals.h" 16#include "clang/Basic/FileManager.h" 17#include "llvm/Support/Compiler.h" 18#include "llvm/Support/MemoryBuffer.h" 19#include "llvm/System/Path.h" 20#include "llvm/Support/Streams.h" 21#include <algorithm> 22#include <iostream> 23using namespace clang; 24using namespace SrcMgr; 25using llvm::MemoryBuffer; 26 27//===----------------------------------------------------------------------===// 28// SourceManager Helper Classes 29//===----------------------------------------------------------------------===// 30 31ContentCache::~ContentCache() { 32 delete Buffer; 33} 34 35/// getSizeBytesMapped - Returns the number of bytes actually mapped for 36/// this ContentCache. This can be 0 if the MemBuffer was not actually 37/// instantiated. 38unsigned ContentCache::getSizeBytesMapped() const { 39 return Buffer ? Buffer->getBufferSize() : 0; 40} 41 42/// getSize - Returns the size of the content encapsulated by this ContentCache. 43/// This can be the size of the source file or the size of an arbitrary 44/// scratch buffer. If the ContentCache encapsulates a source file, that 45/// file is not lazily brought in from disk to satisfy this query. 46unsigned ContentCache::getSize() const { 47 return Entry ? Entry->getSize() : Buffer->getBufferSize(); 48} 49 50const llvm::MemoryBuffer *ContentCache::getBuffer() const { 51 // Lazily create the Buffer for ContentCaches that wrap files. 52 if (!Buffer && Entry) { 53 // FIXME: Should we support a way to not have to do this check over 54 // and over if we cannot open the file? 55 Buffer = MemoryBuffer::getFile(Entry->getName(), 0, Entry->getSize()); 56 } 57 return Buffer; 58} 59 60unsigned LineTableInfo::getLineTableFilenameID(const char *Ptr, unsigned Len) { 61 // Look up the filename in the string table, returning the pre-existing value 62 // if it exists. 63 llvm::StringMapEntry<unsigned> &Entry = 64 FilenameIDs.GetOrCreateValue(Ptr, Ptr+Len, ~0U); 65 if (Entry.getValue() != ~0U) 66 return Entry.getValue(); 67 68 // Otherwise, assign this the next available ID. 69 Entry.setValue(FilenamesByID.size()); 70 FilenamesByID.push_back(&Entry); 71 return FilenamesByID.size()-1; 72} 73 74/// AddLineNote - Add a line note to the line table that indicates that there 75/// is a #line at the specified FID/Offset location which changes the presumed 76/// location to LineNo/FilenameID. 77void LineTableInfo::AddLineNote(unsigned FID, unsigned Offset, 78 unsigned LineNo, int FilenameID) { 79 std::vector<LineEntry> &Entries = LineEntries[FID]; 80 81 assert((Entries.empty() || Entries.back().FileOffset < Offset) && 82 "Adding line entries out of order!"); 83 84 SrcMgr::CharacteristicKind Kind = SrcMgr::C_User; 85 unsigned IncludeOffset = 0; 86 87 if (!Entries.empty()) { 88 // If this is a '#line 4' after '#line 42 "foo.h"', make sure to remember 89 // that we are still in "foo.h". 90 if (FilenameID == -1) 91 FilenameID = Entries.back().FilenameID; 92 93 // If we are after a line marker that switched us to system header mode, or 94 // that set #include information, preserve it. 95 Kind = Entries.back().FileKind; 96 IncludeOffset = Entries.back().IncludeOffset; 97 } 98 99 Entries.push_back(LineEntry::get(Offset, LineNo, FilenameID, Kind, 100 IncludeOffset)); 101} 102 103/// AddLineNote This is the same as the previous version of AddLineNote, but is 104/// used for GNU line markers. If EntryExit is 0, then this doesn't change the 105/// presumed #include stack. If it is 1, this is a file entry, if it is 2 then 106/// this is a file exit. FileKind specifies whether this is a system header or 107/// extern C system header. 108void LineTableInfo::AddLineNote(unsigned FID, unsigned Offset, 109 unsigned LineNo, int FilenameID, 110 unsigned EntryExit, 111 SrcMgr::CharacteristicKind FileKind) { 112 assert(FilenameID != -1 && "Unspecified filename should use other accessor"); 113 114 std::vector<LineEntry> &Entries = LineEntries[FID]; 115 116 assert((Entries.empty() || Entries.back().FileOffset < Offset) && 117 "Adding line entries out of order!"); 118 119 unsigned IncludeOffset = 0; 120 if (EntryExit == 0) { // No #include stack change. 121 IncludeOffset = Entries.empty() ? 0 : Entries.back().IncludeOffset; 122 } else if (EntryExit == 1) { 123 IncludeOffset = Offset-1; 124 } else if (EntryExit == 2) { 125 assert(!Entries.empty() && Entries.back().IncludeOffset && 126 "PPDirectives should have caught case when popping empty include stack"); 127 128 // Get the include loc of the last entries' include loc as our include loc. 129 IncludeOffset = 0; 130 if (const LineEntry *PrevEntry = 131 FindNearestLineEntry(FID, Entries.back().IncludeOffset)) 132 IncludeOffset = PrevEntry->IncludeOffset; 133 } 134 135 Entries.push_back(LineEntry::get(Offset, LineNo, FilenameID, FileKind, 136 IncludeOffset)); 137} 138 139 140/// FindNearestLineEntry - Find the line entry nearest to FID that is before 141/// it. If there is no line entry before Offset in FID, return null. 142const LineEntry *LineTableInfo::FindNearestLineEntry(unsigned FID, 143 unsigned Offset) { 144 const std::vector<LineEntry> &Entries = LineEntries[FID]; 145 assert(!Entries.empty() && "No #line entries for this FID after all!"); 146 147 // It is very common for the query to be after the last #line, check this 148 // first. 149 if (Entries.back().FileOffset <= Offset) 150 return &Entries.back(); 151 152 // Do a binary search to find the maximal element that is still before Offset. 153 std::vector<LineEntry>::const_iterator I = 154 std::upper_bound(Entries.begin(), Entries.end(), Offset); 155 if (I == Entries.begin()) return 0; 156 return &*--I; 157} 158 159/// \brief Add a new line entry that has already been encoded into 160/// the internal representation of the line table. 161void LineTableInfo::AddEntry(unsigned FID, 162 const std::vector<LineEntry> &Entries) { 163 LineEntries[FID] = Entries; 164} 165 166/// getLineTableFilenameID - Return the uniqued ID for the specified filename. 167/// 168unsigned SourceManager::getLineTableFilenameID(const char *Ptr, unsigned Len) { 169 if (LineTable == 0) 170 LineTable = new LineTableInfo(); 171 return LineTable->getLineTableFilenameID(Ptr, Len); 172} 173 174 175/// AddLineNote - Add a line note to the line table for the FileID and offset 176/// specified by Loc. If FilenameID is -1, it is considered to be 177/// unspecified. 178void SourceManager::AddLineNote(SourceLocation Loc, unsigned LineNo, 179 int FilenameID) { 180 std::pair<FileID, unsigned> LocInfo = getDecomposedInstantiationLoc(Loc); 181 182 const SrcMgr::FileInfo &FileInfo = getSLocEntry(LocInfo.first).getFile(); 183 184 // Remember that this file has #line directives now if it doesn't already. 185 const_cast<SrcMgr::FileInfo&>(FileInfo).setHasLineDirectives(); 186 187 if (LineTable == 0) 188 LineTable = new LineTableInfo(); 189 LineTable->AddLineNote(LocInfo.first.ID, LocInfo.second, LineNo, FilenameID); 190} 191 192/// AddLineNote - Add a GNU line marker to the line table. 193void SourceManager::AddLineNote(SourceLocation Loc, unsigned LineNo, 194 int FilenameID, bool IsFileEntry, 195 bool IsFileExit, bool IsSystemHeader, 196 bool IsExternCHeader) { 197 // If there is no filename and no flags, this is treated just like a #line, 198 // which does not change the flags of the previous line marker. 199 if (FilenameID == -1) { 200 assert(!IsFileEntry && !IsFileExit && !IsSystemHeader && !IsExternCHeader && 201 "Can't set flags without setting the filename!"); 202 return AddLineNote(Loc, LineNo, FilenameID); 203 } 204 205 std::pair<FileID, unsigned> LocInfo = getDecomposedInstantiationLoc(Loc); 206 const SrcMgr::FileInfo &FileInfo = getSLocEntry(LocInfo.first).getFile(); 207 208 // Remember that this file has #line directives now if it doesn't already. 209 const_cast<SrcMgr::FileInfo&>(FileInfo).setHasLineDirectives(); 210 211 if (LineTable == 0) 212 LineTable = new LineTableInfo(); 213 214 SrcMgr::CharacteristicKind FileKind; 215 if (IsExternCHeader) 216 FileKind = SrcMgr::C_ExternCSystem; 217 else if (IsSystemHeader) 218 FileKind = SrcMgr::C_System; 219 else 220 FileKind = SrcMgr::C_User; 221 222 unsigned EntryExit = 0; 223 if (IsFileEntry) 224 EntryExit = 1; 225 else if (IsFileExit) 226 EntryExit = 2; 227 228 LineTable->AddLineNote(LocInfo.first.ID, LocInfo.second, LineNo, FilenameID, 229 EntryExit, FileKind); 230} 231 232LineTableInfo &SourceManager::getLineTable() { 233 if (LineTable == 0) 234 LineTable = new LineTableInfo(); 235 return *LineTable; 236} 237 238//===----------------------------------------------------------------------===// 239// Private 'Create' methods. 240//===----------------------------------------------------------------------===// 241 242SourceManager::~SourceManager() { 243 delete LineTable; 244 245 // Delete FileEntry objects corresponding to content caches. Since the actual 246 // content cache objects are bump pointer allocated, we just have to run the 247 // dtors, but we call the deallocate method for completeness. 248 for (unsigned i = 0, e = MemBufferInfos.size(); i != e; ++i) { 249 MemBufferInfos[i]->~ContentCache(); 250 ContentCacheAlloc.Deallocate(MemBufferInfos[i]); 251 } 252 for (llvm::DenseMap<const FileEntry*, SrcMgr::ContentCache*>::iterator 253 I = FileInfos.begin(), E = FileInfos.end(); I != E; ++I) { 254 I->second->~ContentCache(); 255 ContentCacheAlloc.Deallocate(I->second); 256 } 257} 258 259void SourceManager::clearIDTables() { 260 MainFileID = FileID(); 261 SLocEntryTable.clear(); 262 LastLineNoFileIDQuery = FileID(); 263 LastLineNoContentCache = 0; 264 LastFileIDLookup = FileID(); 265 266 if (LineTable) 267 LineTable->clear(); 268 269 // Use up FileID #0 as an invalid instantiation. 270 NextOffset = 0; 271 createInstantiationLoc(SourceLocation(),SourceLocation(),SourceLocation(), 1); 272} 273 274/// getOrCreateContentCache - Create or return a cached ContentCache for the 275/// specified file. 276const ContentCache * 277SourceManager::getOrCreateContentCache(const FileEntry *FileEnt) { 278 assert(FileEnt && "Didn't specify a file entry to use?"); 279 280 // Do we already have information about this file? 281 ContentCache *&Entry = FileInfos[FileEnt]; 282 if (Entry) return Entry; 283 284 // Nope, create a new Cache entry. Make sure it is at least 8-byte aligned 285 // so that FileInfo can use the low 3 bits of the pointer for its own 286 // nefarious purposes. 287 unsigned EntryAlign = llvm::AlignOf<ContentCache>::Alignment; 288 EntryAlign = std::max(8U, EntryAlign); 289 Entry = ContentCacheAlloc.Allocate<ContentCache>(1, EntryAlign); 290 new (Entry) ContentCache(FileEnt); 291 return Entry; 292} 293 294 295/// createMemBufferContentCache - Create a new ContentCache for the specified 296/// memory buffer. This does no caching. 297const ContentCache* 298SourceManager::createMemBufferContentCache(const MemoryBuffer *Buffer) { 299 // Add a new ContentCache to the MemBufferInfos list and return it. Make sure 300 // it is at least 8-byte aligned so that FileInfo can use the low 3 bits of 301 // the pointer for its own nefarious purposes. 302 unsigned EntryAlign = llvm::AlignOf<ContentCache>::Alignment; 303 EntryAlign = std::max(8U, EntryAlign); 304 ContentCache *Entry = ContentCacheAlloc.Allocate<ContentCache>(1, EntryAlign); 305 new (Entry) ContentCache(); 306 MemBufferInfos.push_back(Entry); 307 Entry->setBuffer(Buffer); 308 return Entry; 309} 310 311void SourceManager::PreallocateSLocEntries(ExternalSLocEntrySource *Source, 312 unsigned NumSLocEntries, 313 unsigned NextOffset) { 314 ExternalSLocEntries = Source; 315 this->NextOffset = NextOffset; 316 SLocEntryLoaded.resize(NumSLocEntries + 1); 317 SLocEntryLoaded[0] = true; 318 SLocEntryTable.resize(SLocEntryTable.size() + NumSLocEntries); 319} 320 321void SourceManager::ClearPreallocatedSLocEntries() { 322 unsigned I = 0; 323 for (unsigned N = SLocEntryLoaded.size(); I != N; ++I) 324 if (!SLocEntryLoaded[I]) 325 break; 326 327 // We've already loaded all preallocated source location entries. 328 if (I == SLocEntryLoaded.size()) 329 return; 330 331 // Remove everything from location I onward. 332 SLocEntryTable.resize(I); 333 SLocEntryLoaded.clear(); 334 ExternalSLocEntries = 0; 335} 336 337 338//===----------------------------------------------------------------------===// 339// Methods to create new FileID's and instantiations. 340//===----------------------------------------------------------------------===// 341 342/// createFileID - Create a new fileID for the specified ContentCache and 343/// include position. This works regardless of whether the ContentCache 344/// corresponds to a file or some other input source. 345FileID SourceManager::createFileID(const ContentCache *File, 346 SourceLocation IncludePos, 347 SrcMgr::CharacteristicKind FileCharacter, 348 unsigned PreallocatedID, 349 unsigned Offset) { 350 if (PreallocatedID) { 351 // If we're filling in a preallocated ID, just load in the file 352 // entry and return. 353 assert(PreallocatedID < SLocEntryLoaded.size() && 354 "Preallocate ID out-of-range"); 355 assert(!SLocEntryLoaded[PreallocatedID] && 356 "Source location entry already loaded"); 357 assert(Offset && "Preallocate source location cannot have zero offset"); 358 SLocEntryTable[PreallocatedID] 359 = SLocEntry::get(Offset, FileInfo::get(IncludePos, File, FileCharacter)); 360 SLocEntryLoaded[PreallocatedID] = true; 361 FileID FID = FileID::get(PreallocatedID); 362 if (File->FirstFID.isInvalid()) 363 File->FirstFID = FID; 364 return LastFileIDLookup = FID; 365 } 366 367 SLocEntryTable.push_back(SLocEntry::get(NextOffset, 368 FileInfo::get(IncludePos, File, 369 FileCharacter))); 370 unsigned FileSize = File->getSize(); 371 assert(NextOffset+FileSize+1 > NextOffset && "Ran out of source locations!"); 372 NextOffset += FileSize+1; 373 374 // Set LastFileIDLookup to the newly created file. The next getFileID call is 375 // almost guaranteed to be from that file. 376 FileID FID = FileID::get(SLocEntryTable.size()-1); 377 if (File->FirstFID.isInvalid()) 378 File->FirstFID = FID; 379 return LastFileIDLookup = FID; 380} 381 382/// createInstantiationLoc - Return a new SourceLocation that encodes the fact 383/// that a token from SpellingLoc should actually be referenced from 384/// InstantiationLoc. 385SourceLocation SourceManager::createInstantiationLoc(SourceLocation SpellingLoc, 386 SourceLocation ILocStart, 387 SourceLocation ILocEnd, 388 unsigned TokLength, 389 unsigned PreallocatedID, 390 unsigned Offset) { 391 InstantiationInfo II = InstantiationInfo::get(ILocStart,ILocEnd, SpellingLoc); 392 if (PreallocatedID) { 393 // If we're filling in a preallocated ID, just load in the 394 // instantiation entry and return. 395 assert(PreallocatedID < SLocEntryLoaded.size() && 396 "Preallocate ID out-of-range"); 397 assert(!SLocEntryLoaded[PreallocatedID] && 398 "Source location entry already loaded"); 399 assert(Offset && "Preallocate source location cannot have zero offset"); 400 SLocEntryTable[PreallocatedID] = SLocEntry::get(Offset, II); 401 SLocEntryLoaded[PreallocatedID] = true; 402 return SourceLocation::getMacroLoc(Offset); 403 } 404 SLocEntryTable.push_back(SLocEntry::get(NextOffset, II)); 405 assert(NextOffset+TokLength+1 > NextOffset && "Ran out of source locations!"); 406 NextOffset += TokLength+1; 407 return SourceLocation::getMacroLoc(NextOffset-(TokLength+1)); 408} 409 410/// getBufferData - Return a pointer to the start and end of the source buffer 411/// data for the specified FileID. 412std::pair<const char*, const char*> 413SourceManager::getBufferData(FileID FID) const { 414 const llvm::MemoryBuffer *Buf = getBuffer(FID); 415 return std::make_pair(Buf->getBufferStart(), Buf->getBufferEnd()); 416} 417 418 419//===----------------------------------------------------------------------===// 420// SourceLocation manipulation methods. 421//===----------------------------------------------------------------------===// 422 423/// getFileIDSlow - Return the FileID for a SourceLocation. This is a very hot 424/// method that is used for all SourceManager queries that start with a 425/// SourceLocation object. It is responsible for finding the entry in 426/// SLocEntryTable which contains the specified location. 427/// 428FileID SourceManager::getFileIDSlow(unsigned SLocOffset) const { 429 assert(SLocOffset && "Invalid FileID"); 430 431 // After the first and second level caches, I see two common sorts of 432 // behavior: 1) a lot of searched FileID's are "near" the cached file location 433 // or are "near" the cached instantiation location. 2) others are just 434 // completely random and may be a very long way away. 435 // 436 // To handle this, we do a linear search for up to 8 steps to catch #1 quickly 437 // then we fall back to a less cache efficient, but more scalable, binary 438 // search to find the location. 439 440 // See if this is near the file point - worst case we start scanning from the 441 // most newly created FileID. 442 std::vector<SrcMgr::SLocEntry>::const_iterator I; 443 444 if (SLocEntryTable[LastFileIDLookup.ID].getOffset() < SLocOffset) { 445 // Neither loc prunes our search. 446 I = SLocEntryTable.end(); 447 } else { 448 // Perhaps it is near the file point. 449 I = SLocEntryTable.begin()+LastFileIDLookup.ID; 450 } 451 452 // Find the FileID that contains this. "I" is an iterator that points to a 453 // FileID whose offset is known to be larger than SLocOffset. 454 unsigned NumProbes = 0; 455 while (1) { 456 --I; 457 if (ExternalSLocEntries) 458 getSLocEntry(FileID::get(I - SLocEntryTable.begin())); 459 if (I->getOffset() <= SLocOffset) { 460#if 0 461 printf("lin %d -> %d [%s] %d %d\n", SLocOffset, 462 I-SLocEntryTable.begin(), 463 I->isInstantiation() ? "inst" : "file", 464 LastFileIDLookup.ID, int(SLocEntryTable.end()-I)); 465#endif 466 FileID Res = FileID::get(I-SLocEntryTable.begin()); 467 468 // If this isn't an instantiation, remember it. We have good locality 469 // across FileID lookups. 470 if (!I->isInstantiation()) 471 LastFileIDLookup = Res; 472 NumLinearScans += NumProbes+1; 473 return Res; 474 } 475 if (++NumProbes == 8) 476 break; 477 } 478 479 // Convert "I" back into an index. We know that it is an entry whose index is 480 // larger than the offset we are looking for. 481 unsigned GreaterIndex = I-SLocEntryTable.begin(); 482 // LessIndex - This is the lower bound of the range that we're searching. 483 // We know that the offset corresponding to the FileID is is less than 484 // SLocOffset. 485 unsigned LessIndex = 0; 486 NumProbes = 0; 487 while (1) { 488 unsigned MiddleIndex = (GreaterIndex-LessIndex)/2+LessIndex; 489 unsigned MidOffset = getSLocEntry(FileID::get(MiddleIndex)).getOffset(); 490 491 ++NumProbes; 492 493 // If the offset of the midpoint is too large, chop the high side of the 494 // range to the midpoint. 495 if (MidOffset > SLocOffset) { 496 GreaterIndex = MiddleIndex; 497 continue; 498 } 499 500 // If the middle index contains the value, succeed and return. 501 if (isOffsetInFileID(FileID::get(MiddleIndex), SLocOffset)) { 502#if 0 503 printf("bin %d -> %d [%s] %d %d\n", SLocOffset, 504 I-SLocEntryTable.begin(), 505 I->isInstantiation() ? "inst" : "file", 506 LastFileIDLookup.ID, int(SLocEntryTable.end()-I)); 507#endif 508 FileID Res = FileID::get(MiddleIndex); 509 510 // If this isn't an instantiation, remember it. We have good locality 511 // across FileID lookups. 512 if (!I->isInstantiation()) 513 LastFileIDLookup = Res; 514 NumBinaryProbes += NumProbes; 515 return Res; 516 } 517 518 // Otherwise, move the low-side up to the middle index. 519 LessIndex = MiddleIndex; 520 } 521} 522 523SourceLocation SourceManager:: 524getInstantiationLocSlowCase(SourceLocation Loc) const { 525 do { 526 std::pair<FileID, unsigned> LocInfo = getDecomposedLoc(Loc); 527 Loc = getSLocEntry(LocInfo.first).getInstantiation() 528 .getInstantiationLocStart(); 529 Loc = Loc.getFileLocWithOffset(LocInfo.second); 530 } while (!Loc.isFileID()); 531 532 return Loc; 533} 534 535SourceLocation SourceManager::getSpellingLocSlowCase(SourceLocation Loc) const { 536 do { 537 std::pair<FileID, unsigned> LocInfo = getDecomposedLoc(Loc); 538 Loc = getSLocEntry(LocInfo.first).getInstantiation().getSpellingLoc(); 539 Loc = Loc.getFileLocWithOffset(LocInfo.second); 540 } while (!Loc.isFileID()); 541 return Loc; 542} 543 544 545std::pair<FileID, unsigned> 546SourceManager::getDecomposedInstantiationLocSlowCase(const SrcMgr::SLocEntry *E, 547 unsigned Offset) const { 548 // If this is an instantiation record, walk through all the instantiation 549 // points. 550 FileID FID; 551 SourceLocation Loc; 552 do { 553 Loc = E->getInstantiation().getInstantiationLocStart(); 554 555 FID = getFileID(Loc); 556 E = &getSLocEntry(FID); 557 Offset += Loc.getOffset()-E->getOffset(); 558 } while (!Loc.isFileID()); 559 560 return std::make_pair(FID, Offset); 561} 562 563std::pair<FileID, unsigned> 564SourceManager::getDecomposedSpellingLocSlowCase(const SrcMgr::SLocEntry *E, 565 unsigned Offset) const { 566 // If this is an instantiation record, walk through all the instantiation 567 // points. 568 FileID FID; 569 SourceLocation Loc; 570 do { 571 Loc = E->getInstantiation().getSpellingLoc(); 572 573 FID = getFileID(Loc); 574 E = &getSLocEntry(FID); 575 Offset += Loc.getOffset()-E->getOffset(); 576 } while (!Loc.isFileID()); 577 578 return std::make_pair(FID, Offset); 579} 580 581/// getImmediateSpellingLoc - Given a SourceLocation object, return the 582/// spelling location referenced by the ID. This is the first level down 583/// towards the place where the characters that make up the lexed token can be 584/// found. This should not generally be used by clients. 585SourceLocation SourceManager::getImmediateSpellingLoc(SourceLocation Loc) const{ 586 if (Loc.isFileID()) return Loc; 587 std::pair<FileID, unsigned> LocInfo = getDecomposedLoc(Loc); 588 Loc = getSLocEntry(LocInfo.first).getInstantiation().getSpellingLoc(); 589 return Loc.getFileLocWithOffset(LocInfo.second); 590} 591 592 593/// getImmediateInstantiationRange - Loc is required to be an instantiation 594/// location. Return the start/end of the instantiation information. 595std::pair<SourceLocation,SourceLocation> 596SourceManager::getImmediateInstantiationRange(SourceLocation Loc) const { 597 assert(Loc.isMacroID() && "Not an instantiation loc!"); 598 const InstantiationInfo &II = getSLocEntry(getFileID(Loc)).getInstantiation(); 599 return II.getInstantiationLocRange(); 600} 601 602/// getInstantiationRange - Given a SourceLocation object, return the 603/// range of tokens covered by the instantiation in the ultimate file. 604std::pair<SourceLocation,SourceLocation> 605SourceManager::getInstantiationRange(SourceLocation Loc) const { 606 if (Loc.isFileID()) return std::make_pair(Loc, Loc); 607 608 std::pair<SourceLocation,SourceLocation> Res = 609 getImmediateInstantiationRange(Loc); 610 611 // Fully resolve the start and end locations to their ultimate instantiation 612 // points. 613 while (!Res.first.isFileID()) 614 Res.first = getImmediateInstantiationRange(Res.first).first; 615 while (!Res.second.isFileID()) 616 Res.second = getImmediateInstantiationRange(Res.second).second; 617 return Res; 618} 619 620 621 622//===----------------------------------------------------------------------===// 623// Queries about the code at a SourceLocation. 624//===----------------------------------------------------------------------===// 625 626/// getCharacterData - Return a pointer to the start of the specified location 627/// in the appropriate MemoryBuffer. 628const char *SourceManager::getCharacterData(SourceLocation SL) const { 629 // Note that this is a hot function in the getSpelling() path, which is 630 // heavily used by -E mode. 631 std::pair<FileID, unsigned> LocInfo = getDecomposedSpellingLoc(SL); 632 633 // Note that calling 'getBuffer()' may lazily page in a source file. 634 return getSLocEntry(LocInfo.first).getFile().getContentCache() 635 ->getBuffer()->getBufferStart() + LocInfo.second; 636} 637 638 639/// getColumnNumber - Return the column # for the specified file position. 640/// this is significantly cheaper to compute than the line number. 641unsigned SourceManager::getColumnNumber(FileID FID, unsigned FilePos) const { 642 const char *Buf = getBuffer(FID)->getBufferStart(); 643 644 unsigned LineStart = FilePos; 645 while (LineStart && Buf[LineStart-1] != '\n' && Buf[LineStart-1] != '\r') 646 --LineStart; 647 return FilePos-LineStart+1; 648} 649 650unsigned SourceManager::getSpellingColumnNumber(SourceLocation Loc) const { 651 if (Loc.isInvalid()) return 0; 652 std::pair<FileID, unsigned> LocInfo = getDecomposedSpellingLoc(Loc); 653 return getColumnNumber(LocInfo.first, LocInfo.second); 654} 655 656unsigned SourceManager::getInstantiationColumnNumber(SourceLocation Loc) const { 657 if (Loc.isInvalid()) return 0; 658 std::pair<FileID, unsigned> LocInfo = getDecomposedInstantiationLoc(Loc); 659 return getColumnNumber(LocInfo.first, LocInfo.second); 660} 661 662 663 664static void ComputeLineNumbers(ContentCache* FI, 665 llvm::BumpPtrAllocator &Alloc) DISABLE_INLINE; 666static void ComputeLineNumbers(ContentCache* FI, llvm::BumpPtrAllocator &Alloc){ 667 // Note that calling 'getBuffer()' may lazily page in the file. 668 const MemoryBuffer *Buffer = FI->getBuffer(); 669 670 // Find the file offsets of all of the *physical* source lines. This does 671 // not look at trigraphs, escaped newlines, or anything else tricky. 672 std::vector<unsigned> LineOffsets; 673 674 // Line #1 starts at char 0. 675 LineOffsets.push_back(0); 676 677 const unsigned char *Buf = (const unsigned char *)Buffer->getBufferStart(); 678 const unsigned char *End = (const unsigned char *)Buffer->getBufferEnd(); 679 unsigned Offs = 0; 680 while (1) { 681 // Skip over the contents of the line. 682 // TODO: Vectorize this? This is very performance sensitive for programs 683 // with lots of diagnostics and in -E mode. 684 const unsigned char *NextBuf = (const unsigned char *)Buf; 685 while (*NextBuf != '\n' && *NextBuf != '\r' && *NextBuf != '\0') 686 ++NextBuf; 687 Offs += NextBuf-Buf; 688 Buf = NextBuf; 689 690 if (Buf[0] == '\n' || Buf[0] == '\r') { 691 // If this is \n\r or \r\n, skip both characters. 692 if ((Buf[1] == '\n' || Buf[1] == '\r') && Buf[0] != Buf[1]) 693 ++Offs, ++Buf; 694 ++Offs, ++Buf; 695 LineOffsets.push_back(Offs); 696 } else { 697 // Otherwise, this is a null. If end of file, exit. 698 if (Buf == End) break; 699 // Otherwise, skip the null. 700 ++Offs, ++Buf; 701 } 702 } 703 704 // Copy the offsets into the FileInfo structure. 705 FI->NumLines = LineOffsets.size(); 706 FI->SourceLineCache = Alloc.Allocate<unsigned>(LineOffsets.size()); 707 std::copy(LineOffsets.begin(), LineOffsets.end(), FI->SourceLineCache); 708} 709 710/// getLineNumber - Given a SourceLocation, return the spelling line number 711/// for the position indicated. This requires building and caching a table of 712/// line offsets for the MemoryBuffer, so this is not cheap: use only when 713/// about to emit a diagnostic. 714unsigned SourceManager::getLineNumber(FileID FID, unsigned FilePos) const { 715 ContentCache *Content; 716 if (LastLineNoFileIDQuery == FID) 717 Content = LastLineNoContentCache; 718 else 719 Content = const_cast<ContentCache*>(getSLocEntry(FID) 720 .getFile().getContentCache()); 721 722 // If this is the first use of line information for this buffer, compute the 723 /// SourceLineCache for it on demand. 724 if (Content->SourceLineCache == 0) 725 ComputeLineNumbers(Content, ContentCacheAlloc); 726 727 // Okay, we know we have a line number table. Do a binary search to find the 728 // line number that this character position lands on. 729 unsigned *SourceLineCache = Content->SourceLineCache; 730 unsigned *SourceLineCacheStart = SourceLineCache; 731 unsigned *SourceLineCacheEnd = SourceLineCache + Content->NumLines; 732 733 unsigned QueriedFilePos = FilePos+1; 734 735 // FIXME: I would like to be convinced that this code is worth being as 736 // complicated as it is, binary search isn't that slow. 737 // 738 // If it is worth being optimized, then in my opinion it could be more 739 // performant, simpler, and more obviously correct by just "galloping" outward 740 // from the queried file position. In fact, this could be incorporated into a 741 // generic algorithm such as lower_bound_with_hint. 742 // 743 // If someone gives me a test case where this matters, and I will do it! - DWD 744 745 // If the previous query was to the same file, we know both the file pos from 746 // that query and the line number returned. This allows us to narrow the 747 // search space from the entire file to something near the match. 748 if (LastLineNoFileIDQuery == FID) { 749 if (QueriedFilePos >= LastLineNoFilePos) { 750 // FIXME: Potential overflow? 751 SourceLineCache = SourceLineCache+LastLineNoResult-1; 752 753 // The query is likely to be nearby the previous one. Here we check to 754 // see if it is within 5, 10 or 20 lines. It can be far away in cases 755 // where big comment blocks and vertical whitespace eat up lines but 756 // contribute no tokens. 757 if (SourceLineCache+5 < SourceLineCacheEnd) { 758 if (SourceLineCache[5] > QueriedFilePos) 759 SourceLineCacheEnd = SourceLineCache+5; 760 else if (SourceLineCache+10 < SourceLineCacheEnd) { 761 if (SourceLineCache[10] > QueriedFilePos) 762 SourceLineCacheEnd = SourceLineCache+10; 763 else if (SourceLineCache+20 < SourceLineCacheEnd) { 764 if (SourceLineCache[20] > QueriedFilePos) 765 SourceLineCacheEnd = SourceLineCache+20; 766 } 767 } 768 } 769 } else { 770 if (LastLineNoResult < Content->NumLines) 771 SourceLineCacheEnd = SourceLineCache+LastLineNoResult+1; 772 } 773 } 774 775 // If the spread is large, do a "radix" test as our initial guess, based on 776 // the assumption that lines average to approximately the same length. 777 // NOTE: This is currently disabled, as it does not appear to be profitable in 778 // initial measurements. 779 if (0 && SourceLineCacheEnd-SourceLineCache > 20) { 780 unsigned FileLen = Content->SourceLineCache[Content->NumLines-1]; 781 782 // Take a stab at guessing where it is. 783 unsigned ApproxPos = Content->NumLines*QueriedFilePos / FileLen; 784 785 // Check for -10 and +10 lines. 786 unsigned LowerBound = std::max(int(ApproxPos-10), 0); 787 unsigned UpperBound = std::min(ApproxPos+10, FileLen); 788 789 // If the computed lower bound is less than the query location, move it in. 790 if (SourceLineCache < SourceLineCacheStart+LowerBound && 791 SourceLineCacheStart[LowerBound] < QueriedFilePos) 792 SourceLineCache = SourceLineCacheStart+LowerBound; 793 794 // If the computed upper bound is greater than the query location, move it. 795 if (SourceLineCacheEnd > SourceLineCacheStart+UpperBound && 796 SourceLineCacheStart[UpperBound] >= QueriedFilePos) 797 SourceLineCacheEnd = SourceLineCacheStart+UpperBound; 798 } 799 800 unsigned *Pos 801 = std::lower_bound(SourceLineCache, SourceLineCacheEnd, QueriedFilePos); 802 unsigned LineNo = Pos-SourceLineCacheStart; 803 804 LastLineNoFileIDQuery = FID; 805 LastLineNoContentCache = Content; 806 LastLineNoFilePos = QueriedFilePos; 807 LastLineNoResult = LineNo; 808 return LineNo; 809} 810 811unsigned SourceManager::getInstantiationLineNumber(SourceLocation Loc) const { 812 if (Loc.isInvalid()) return 0; 813 std::pair<FileID, unsigned> LocInfo = getDecomposedInstantiationLoc(Loc); 814 return getLineNumber(LocInfo.first, LocInfo.second); 815} 816unsigned SourceManager::getSpellingLineNumber(SourceLocation Loc) const { 817 if (Loc.isInvalid()) return 0; 818 std::pair<FileID, unsigned> LocInfo = getDecomposedSpellingLoc(Loc); 819 return getLineNumber(LocInfo.first, LocInfo.second); 820} 821 822/// getFileCharacteristic - return the file characteristic of the specified 823/// source location, indicating whether this is a normal file, a system 824/// header, or an "implicit extern C" system header. 825/// 826/// This state can be modified with flags on GNU linemarker directives like: 827/// # 4 "foo.h" 3 828/// which changes all source locations in the current file after that to be 829/// considered to be from a system header. 830SrcMgr::CharacteristicKind 831SourceManager::getFileCharacteristic(SourceLocation Loc) const { 832 assert(!Loc.isInvalid() && "Can't get file characteristic of invalid loc!"); 833 std::pair<FileID, unsigned> LocInfo = getDecomposedInstantiationLoc(Loc); 834 const SrcMgr::FileInfo &FI = getSLocEntry(LocInfo.first).getFile(); 835 836 // If there are no #line directives in this file, just return the whole-file 837 // state. 838 if (!FI.hasLineDirectives()) 839 return FI.getFileCharacteristic(); 840 841 assert(LineTable && "Can't have linetable entries without a LineTable!"); 842 // See if there is a #line directive before the location. 843 const LineEntry *Entry = 844 LineTable->FindNearestLineEntry(LocInfo.first.ID, LocInfo.second); 845 846 // If this is before the first line marker, use the file characteristic. 847 if (!Entry) 848 return FI.getFileCharacteristic(); 849 850 return Entry->FileKind; 851} 852 853/// Return the filename or buffer identifier of the buffer the location is in. 854/// Note that this name does not respect #line directives. Use getPresumedLoc 855/// for normal clients. 856const char *SourceManager::getBufferName(SourceLocation Loc) const { 857 if (Loc.isInvalid()) return "<invalid loc>"; 858 859 return getBuffer(getFileID(Loc))->getBufferIdentifier(); 860} 861 862 863/// getPresumedLoc - This method returns the "presumed" location of a 864/// SourceLocation specifies. A "presumed location" can be modified by #line 865/// or GNU line marker directives. This provides a view on the data that a 866/// user should see in diagnostics, for example. 867/// 868/// Note that a presumed location is always given as the instantiation point 869/// of an instantiation location, not at the spelling location. 870PresumedLoc SourceManager::getPresumedLoc(SourceLocation Loc) const { 871 if (Loc.isInvalid()) return PresumedLoc(); 872 873 // Presumed locations are always for instantiation points. 874 std::pair<FileID, unsigned> LocInfo = getDecomposedInstantiationLoc(Loc); 875 876 const SrcMgr::FileInfo &FI = getSLocEntry(LocInfo.first).getFile(); 877 const SrcMgr::ContentCache *C = FI.getContentCache(); 878 879 // To get the source name, first consult the FileEntry (if one exists) 880 // before the MemBuffer as this will avoid unnecessarily paging in the 881 // MemBuffer. 882 const char *Filename = 883 C->Entry ? C->Entry->getName() : C->getBuffer()->getBufferIdentifier(); 884 unsigned LineNo = getLineNumber(LocInfo.first, LocInfo.second); 885 unsigned ColNo = getColumnNumber(LocInfo.first, LocInfo.second); 886 SourceLocation IncludeLoc = FI.getIncludeLoc(); 887 888 // If we have #line directives in this file, update and overwrite the physical 889 // location info if appropriate. 890 if (FI.hasLineDirectives()) { 891 assert(LineTable && "Can't have linetable entries without a LineTable!"); 892 // See if there is a #line directive before this. If so, get it. 893 if (const LineEntry *Entry = 894 LineTable->FindNearestLineEntry(LocInfo.first.ID, LocInfo.second)) { 895 // If the LineEntry indicates a filename, use it. 896 if (Entry->FilenameID != -1) 897 Filename = LineTable->getFilename(Entry->FilenameID); 898 899 // Use the line number specified by the LineEntry. This line number may 900 // be multiple lines down from the line entry. Add the difference in 901 // physical line numbers from the query point and the line marker to the 902 // total. 903 unsigned MarkerLineNo = getLineNumber(LocInfo.first, Entry->FileOffset); 904 LineNo = Entry->LineNo + (LineNo-MarkerLineNo-1); 905 906 // Note that column numbers are not molested by line markers. 907 908 // Handle virtual #include manipulation. 909 if (Entry->IncludeOffset) { 910 IncludeLoc = getLocForStartOfFile(LocInfo.first); 911 IncludeLoc = IncludeLoc.getFileLocWithOffset(Entry->IncludeOffset); 912 } 913 } 914 } 915 916 return PresumedLoc(Filename, LineNo, ColNo, IncludeLoc); 917} 918 919//===----------------------------------------------------------------------===// 920// Other miscellaneous methods. 921//===----------------------------------------------------------------------===// 922 923/// \brief Get the source location for the given file:line:col triplet. 924/// 925/// If the source file is included multiple times, the source location will 926/// be based upon the first inclusion. 927SourceLocation SourceManager::getLocation(const FileEntry *SourceFile, 928 unsigned Line, unsigned Col) const { 929 assert(SourceFile && "Null source file!"); 930 assert(Line && Col && "Line and column should start from 1!"); 931 932 fileinfo_iterator FI = FileInfos.find(SourceFile); 933 if (FI == FileInfos.end()) 934 return SourceLocation(); 935 ContentCache *Content = FI->second; 936 937 // If this is the first use of line information for this buffer, compute the 938 /// SourceLineCache for it on demand. 939 if (Content->SourceLineCache == 0) 940 ComputeLineNumbers(Content, ContentCacheAlloc); 941 942 if (Line > Content->NumLines) 943 return SourceLocation(); 944 945 unsigned FilePos = Content->SourceLineCache[Line - 1]; 946 const char *Buf = Content->getBuffer()->getBufferStart(); 947 unsigned BufLength = Content->getBuffer()->getBufferEnd() - Buf; 948 unsigned i = 0; 949 950 // Check that the given column is valid. 951 while (i < BufLength-1 && i < Col-1 && Buf[i] != '\n' && Buf[i] != '\r') 952 ++i; 953 if (i < Col-1) 954 return SourceLocation(); 955 956 return getLocForStartOfFile(Content->FirstFID). 957 getFileLocWithOffset(FilePos + Col - 1); 958} 959 960 961/// PrintStats - Print statistics to stderr. 962/// 963void SourceManager::PrintStats() const { 964 llvm::cerr << "\n*** Source Manager Stats:\n"; 965 llvm::cerr << FileInfos.size() << " files mapped, " << MemBufferInfos.size() 966 << " mem buffers mapped.\n"; 967 llvm::cerr << SLocEntryTable.size() << " SLocEntry's allocated, " 968 << NextOffset << "B of Sloc address space used.\n"; 969 970 unsigned NumLineNumsComputed = 0; 971 unsigned NumFileBytesMapped = 0; 972 for (fileinfo_iterator I = fileinfo_begin(), E = fileinfo_end(); I != E; ++I){ 973 NumLineNumsComputed += I->second->SourceLineCache != 0; 974 NumFileBytesMapped += I->second->getSizeBytesMapped(); 975 } 976 977 llvm::cerr << NumFileBytesMapped << " bytes of files mapped, " 978 << NumLineNumsComputed << " files with line #'s computed.\n"; 979 llvm::cerr << "FileID scans: " << NumLinearScans << " linear, " 980 << NumBinaryProbes << " binary.\n"; 981} 982 983ExternalSLocEntrySource::~ExternalSLocEntrySource() { } 984