diff options
Diffstat (limited to 'contrib/llvm/tools/clang/lib/Basic/SourceManager.cpp')
| -rw-r--r-- | contrib/llvm/tools/clang/lib/Basic/SourceManager.cpp | 797 |
1 files changed, 515 insertions, 282 deletions
diff --git a/contrib/llvm/tools/clang/lib/Basic/SourceManager.cpp b/contrib/llvm/tools/clang/lib/Basic/SourceManager.cpp index 45922c15527f..364663ee3265 100644 --- a/contrib/llvm/tools/clang/lib/Basic/SourceManager.cpp +++ b/contrib/llvm/tools/clang/lib/Basic/SourceManager.cpp @@ -17,10 +17,12 @@ #include "clang/Basic/FileManager.h" #include "llvm/ADT/StringSwitch.h" #include "llvm/ADT/Optional.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/MemoryBuffer.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Support/Path.h" +#include "llvm/Support/Capacity.h" #include <algorithm> #include <string> #include <cstring> @@ -39,9 +41,8 @@ ContentCache::~ContentCache() { delete Buffer.getPointer(); } -/// getSizeBytesMapped - Returns the number of bytes actually mapped for -/// this ContentCache. This can be 0 if the MemBuffer was not actually -/// instantiated. +/// getSizeBytesMapped - Returns the number of bytes actually mapped for this +/// ContentCache. This can be 0 if the MemBuffer was not actually expanded. unsigned ContentCache::getSizeBytesMapped() const { return Buffer.getPointer() ? Buffer.getPointer()->getBufferSize() : 0; } @@ -78,7 +79,7 @@ void ContentCache::replaceBuffer(const llvm::MemoryBuffer *B, Buffer.setInt(DoNotFree? DoNotFreeFlag : 0); } -const llvm::MemoryBuffer *ContentCache::getBuffer(Diagnostic &Diag, +const llvm::MemoryBuffer *ContentCache::getBuffer(DiagnosticsEngine &Diag, const SourceManager &SM, SourceLocation Loc, bool *Invalid) const { @@ -105,7 +106,7 @@ const llvm::MemoryBuffer *ContentCache::getBuffer(Diagnostic &Diag, // that we are in an inconsistent situation and error out as quickly as // possible. if (!Buffer.getPointer()) { - const llvm::StringRef FillStr("<<<MISSING SOURCE FILE>>>\n"); + const StringRef FillStr("<<<MISSING SOURCE FILE>>>\n"); Buffer.setPointer(MemoryBuffer::getNewMemBuffer(ContentsEntry->getSize(), "<invalid>")); char *Ptr = const_cast<char*>(Buffer.getPointer()->getBufferStart()); @@ -143,7 +144,7 @@ const llvm::MemoryBuffer *ContentCache::getBuffer(Diagnostic &Diag, // If the buffer is valid, check to see if it has a UTF Byte Order Mark // (BOM). We only support UTF-8 with and without a BOM right now. See // http://en.wikipedia.org/wiki/Byte_order_mark for more information. - llvm::StringRef BufStr = Buffer.getPointer()->getBuffer(); + StringRef BufStr = Buffer.getPointer()->getBuffer(); const char *InvalidBOM = llvm::StringSwitch<const char *>(BufStr) .StartsWith("\xFE\xFF", "UTF-16 (BE)") .StartsWith("\xFF\xFE", "UTF-16 (LE)") @@ -169,7 +170,7 @@ const llvm::MemoryBuffer *ContentCache::getBuffer(Diagnostic &Diag, return Buffer.getPointer(); } -unsigned LineTableInfo::getLineTableFilenameID(llvm::StringRef Name) { +unsigned LineTableInfo::getLineTableFilenameID(StringRef Name) { // Look up the filename in the string table, returning the pre-existing value // if it exists. llvm::StringMapEntry<unsigned> &Entry = @@ -186,7 +187,7 @@ unsigned LineTableInfo::getLineTableFilenameID(llvm::StringRef Name) { /// AddLineNote - Add a line note to the line table that indicates that there /// is a #line at the specified FID/Offset location which changes the presumed /// location to LineNo/FilenameID. -void LineTableInfo::AddLineNote(unsigned FID, unsigned Offset, +void LineTableInfo::AddLineNote(int FID, unsigned Offset, unsigned LineNo, int FilenameID) { std::vector<LineEntry> &Entries = LineEntries[FID]; @@ -217,7 +218,7 @@ void LineTableInfo::AddLineNote(unsigned FID, unsigned Offset, /// presumed #include stack. If it is 1, this is a file entry, if it is 2 then /// this is a file exit. FileKind specifies whether this is a system header or /// extern C system header. -void LineTableInfo::AddLineNote(unsigned FID, unsigned Offset, +void LineTableInfo::AddLineNote(int FID, unsigned Offset, unsigned LineNo, int FilenameID, unsigned EntryExit, SrcMgr::CharacteristicKind FileKind) { @@ -251,7 +252,7 @@ void LineTableInfo::AddLineNote(unsigned FID, unsigned Offset, /// FindNearestLineEntry - Find the line entry nearest to FID that is before /// it. If there is no line entry before Offset in FID, return null. -const LineEntry *LineTableInfo::FindNearestLineEntry(unsigned FID, +const LineEntry *LineTableInfo::FindNearestLineEntry(int FID, unsigned Offset) { const std::vector<LineEntry> &Entries = LineEntries[FID]; assert(!Entries.empty() && "No #line entries for this FID after all!"); @@ -270,14 +271,14 @@ const LineEntry *LineTableInfo::FindNearestLineEntry(unsigned FID, /// \brief Add a new line entry that has already been encoded into /// the internal representation of the line table. -void LineTableInfo::AddEntry(unsigned FID, +void LineTableInfo::AddEntry(int FID, const std::vector<LineEntry> &Entries) { LineEntries[FID] = Entries; } /// getLineTableFilenameID - Return the uniqued ID for the specified filename. /// -unsigned SourceManager::getLineTableFilenameID(llvm::StringRef Name) { +unsigned SourceManager::getLineTableFilenameID(StringRef Name) { if (LineTable == 0) LineTable = new LineTableInfo(); return LineTable->getLineTableFilenameID(Name); @@ -289,7 +290,7 @@ unsigned SourceManager::getLineTableFilenameID(llvm::StringRef Name) { /// unspecified. void SourceManager::AddLineNote(SourceLocation Loc, unsigned LineNo, int FilenameID) { - std::pair<FileID, unsigned> LocInfo = getDecomposedInstantiationLoc(Loc); + std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc); bool Invalid = false; const SLocEntry &Entry = getSLocEntry(LocInfo.first, &Invalid); @@ -319,7 +320,7 @@ void SourceManager::AddLineNote(SourceLocation Loc, unsigned LineNo, return AddLineNote(Loc, LineNo, FilenameID); } - std::pair<FileID, unsigned> LocInfo = getDecomposedInstantiationLoc(Loc); + std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc); bool Invalid = false; const SLocEntry &Entry = getSLocEntry(LocInfo.first, &Invalid); @@ -362,7 +363,7 @@ LineTableInfo &SourceManager::getLineTable() { // Private 'Create' methods. //===----------------------------------------------------------------------===// -SourceManager::SourceManager(Diagnostic &Diag, FileManager &FileMgr) +SourceManager::SourceManager(DiagnosticsEngine &Diag, FileManager &FileMgr) : Diag(Diag), FileMgr(FileMgr), OverridenFilesKeepOriginalName(true), ExternalSLocEntries(0), LineTable(0), NumLinearScans(0), NumBinaryProbes(0), FakeBufferForRecovery(0) { @@ -387,11 +388,18 @@ SourceManager::~SourceManager() { } delete FakeBufferForRecovery; + + for (llvm::DenseMap<FileID, MacroArgsMap *>::iterator + I = MacroArgsCacheMap.begin(),E = MacroArgsCacheMap.end(); I!=E; ++I) { + delete I->second; + } } void SourceManager::clearIDTables() { MainFileID = FileID(); - SLocEntryTable.clear(); + LocalSLocEntryTable.clear(); + LoadedSLocEntryTable.clear(); + SLocEntryLoaded.clear(); LastLineNoFileIDQuery = FileID(); LastLineNoContentCache = 0; LastFileIDLookup = FileID(); @@ -399,9 +407,10 @@ void SourceManager::clearIDTables() { if (LineTable) LineTable->clear(); - // Use up FileID #0 as an invalid instantiation. - NextOffset = 0; - createInstantiationLoc(SourceLocation(),SourceLocation(),SourceLocation(), 1); + // Use up FileID #0 as an invalid expansion. + NextLocalOffset = 0; + CurrentLoadedOffset = MaxLoadedOffset; + createExpansionLoc(SourceLocation(),SourceLocation(),SourceLocation(), 1); } /// getOrCreateContentCache - Create or return a cached ContentCache for the @@ -452,33 +461,16 @@ SourceManager::createMemBufferContentCache(const MemoryBuffer *Buffer) { return Entry; } -void SourceManager::PreallocateSLocEntries(ExternalSLocEntrySource *Source, - unsigned NumSLocEntries, - unsigned NextOffset) { - ExternalSLocEntries = Source; - this->NextOffset = NextOffset; - unsigned CurPrealloc = SLocEntryLoaded.size(); - // If we've ever preallocated, we must not count the dummy entry. - if (CurPrealloc) --CurPrealloc; - SLocEntryLoaded.resize(NumSLocEntries + 1); - SLocEntryLoaded[0] = true; - SLocEntryTable.resize(SLocEntryTable.size() + NumSLocEntries - CurPrealloc); -} - -void SourceManager::ClearPreallocatedSLocEntries() { - unsigned I = 0; - for (unsigned N = SLocEntryLoaded.size(); I != N; ++I) - if (!SLocEntryLoaded[I]) - break; - - // We've already loaded all preallocated source location entries. - if (I == SLocEntryLoaded.size()) - return; - - // Remove everything from location I onward. - SLocEntryTable.resize(I); - SLocEntryLoaded.clear(); - ExternalSLocEntries = 0; +std::pair<int, unsigned> +SourceManager::AllocateLoadedSLocEntries(unsigned NumSLocEntries, + unsigned TotalSize) { + assert(ExternalSLocEntries && "Don't have an external sloc source"); + LoadedSLocEntryTable.resize(LoadedSLocEntryTable.size() + NumSLocEntries); + SLocEntryLoaded.resize(LoadedSLocEntryTable.size()); + CurrentLoadedOffset -= TotalSize; + assert(CurrentLoadedOffset >= NextLocalOffset && "Out of source locations"); + int ID = LoadedSLocEntryTable.size(); + return std::make_pair(-ID - 1, CurrentLoadedOffset); } /// \brief As part of recovering from missing or changed content, produce a @@ -492,7 +484,7 @@ const llvm::MemoryBuffer *SourceManager::getFakeBufferForRecovery() const { } //===----------------------------------------------------------------------===// -// Methods to create new FileID's and instantiations. +// Methods to create new FileID's and macro expansions. //===----------------------------------------------------------------------===// /// createFileID - Create a new FileID for the specified ContentCache and @@ -501,77 +493,76 @@ const llvm::MemoryBuffer *SourceManager::getFakeBufferForRecovery() const { FileID SourceManager::createFileID(const ContentCache *File, SourceLocation IncludePos, SrcMgr::CharacteristicKind FileCharacter, - unsigned PreallocatedID, - unsigned Offset) { - if (PreallocatedID) { - // If we're filling in a preallocated ID, just load in the file - // entry and return. - assert(PreallocatedID < SLocEntryLoaded.size() && - "Preallocate ID out-of-range"); - assert(!SLocEntryLoaded[PreallocatedID] && - "Source location entry already loaded"); - assert(Offset && "Preallocate source location cannot have zero offset"); - SLocEntryTable[PreallocatedID] - = SLocEntry::get(Offset, FileInfo::get(IncludePos, File, FileCharacter)); - SLocEntryLoaded[PreallocatedID] = true; - FileID FID = FileID::get(PreallocatedID); - return FID; + int LoadedID, unsigned LoadedOffset) { + if (LoadedID < 0) { + assert(LoadedID != -1 && "Loading sentinel FileID"); + unsigned Index = unsigned(-LoadedID) - 2; + assert(Index < LoadedSLocEntryTable.size() && "FileID out of range"); + assert(!SLocEntryLoaded[Index] && "FileID already loaded"); + LoadedSLocEntryTable[Index] = SLocEntry::get(LoadedOffset, + FileInfo::get(IncludePos, File, FileCharacter)); + SLocEntryLoaded[Index] = true; + return FileID::get(LoadedID); } - - SLocEntryTable.push_back(SLocEntry::get(NextOffset, - FileInfo::get(IncludePos, File, - FileCharacter))); + LocalSLocEntryTable.push_back(SLocEntry::get(NextLocalOffset, + FileInfo::get(IncludePos, File, + FileCharacter))); unsigned FileSize = File->getSize(); - assert(NextOffset+FileSize+1 > NextOffset && "Ran out of source locations!"); - NextOffset += FileSize+1; + assert(NextLocalOffset + FileSize + 1 > NextLocalOffset && + NextLocalOffset + FileSize + 1 <= CurrentLoadedOffset && + "Ran out of source locations!"); + // We do a +1 here because we want a SourceLocation that means "the end of the + // file", e.g. for the "no newline at the end of the file" diagnostic. + NextLocalOffset += FileSize + 1; // Set LastFileIDLookup to the newly created file. The next getFileID call is // almost guaranteed to be from that file. - FileID FID = FileID::get(SLocEntryTable.size()-1); + FileID FID = FileID::get(LocalSLocEntryTable.size()-1); return LastFileIDLookup = FID; } SourceLocation -SourceManager::createMacroArgInstantiationLoc(SourceLocation SpellingLoc, - SourceLocation ILoc, - unsigned TokLength) { - InstantiationInfo II = - InstantiationInfo::createForMacroArg(SpellingLoc, ILoc); - return createInstantiationLocImpl(II, TokLength); -} - -SourceLocation SourceManager::createInstantiationLoc(SourceLocation SpellingLoc, - SourceLocation ILocStart, - SourceLocation ILocEnd, - unsigned TokLength, - unsigned PreallocatedID, - unsigned Offset) { - InstantiationInfo II = - InstantiationInfo::create(SpellingLoc, ILocStart, ILocEnd); - return createInstantiationLocImpl(II, TokLength, PreallocatedID, Offset); +SourceManager::createMacroArgExpansionLoc(SourceLocation SpellingLoc, + SourceLocation ExpansionLoc, + unsigned TokLength) { + ExpansionInfo Info = ExpansionInfo::createForMacroArg(SpellingLoc, + ExpansionLoc); + return createExpansionLocImpl(Info, TokLength); } SourceLocation -SourceManager::createInstantiationLocImpl(const InstantiationInfo &II, - unsigned TokLength, - unsigned PreallocatedID, - unsigned Offset) { - if (PreallocatedID) { - // If we're filling in a preallocated ID, just load in the - // instantiation entry and return. - assert(PreallocatedID < SLocEntryLoaded.size() && - "Preallocate ID out-of-range"); - assert(!SLocEntryLoaded[PreallocatedID] && - "Source location entry already loaded"); - assert(Offset && "Preallocate source location cannot have zero offset"); - SLocEntryTable[PreallocatedID] = SLocEntry::get(Offset, II); - SLocEntryLoaded[PreallocatedID] = true; - return SourceLocation::getMacroLoc(Offset); +SourceManager::createExpansionLoc(SourceLocation SpellingLoc, + SourceLocation ExpansionLocStart, + SourceLocation ExpansionLocEnd, + unsigned TokLength, + int LoadedID, + unsigned LoadedOffset) { + ExpansionInfo Info = ExpansionInfo::create(SpellingLoc, ExpansionLocStart, + ExpansionLocEnd); + return createExpansionLocImpl(Info, TokLength, LoadedID, LoadedOffset); +} + +SourceLocation +SourceManager::createExpansionLocImpl(const ExpansionInfo &Info, + unsigned TokLength, + int LoadedID, + unsigned LoadedOffset) { + if (LoadedID < 0) { + assert(LoadedID != -1 && "Loading sentinel FileID"); + unsigned Index = unsigned(-LoadedID) - 2; + assert(Index < LoadedSLocEntryTable.size() && "FileID out of range"); + assert(!SLocEntryLoaded[Index] && "FileID already loaded"); + LoadedSLocEntryTable[Index] = SLocEntry::get(LoadedOffset, Info); + SLocEntryLoaded[Index] = true; + return SourceLocation::getMacroLoc(LoadedOffset); } - SLocEntryTable.push_back(SLocEntry::get(NextOffset, II)); - assert(NextOffset+TokLength+1 > NextOffset && "Ran out of source locations!"); - NextOffset += TokLength+1; - return SourceLocation::getMacroLoc(NextOffset-(TokLength+1)); + LocalSLocEntryTable.push_back(SLocEntry::get(NextLocalOffset, Info)); + assert(NextLocalOffset + TokLength + 1 > NextLocalOffset && + NextLocalOffset + TokLength + 1 <= CurrentLoadedOffset && + "Ran out of source locations!"); + // See createFileID for that +1. + NextLocalOffset += TokLength + 1; + return SourceLocation::getMacroLoc(NextLocalOffset - (TokLength + 1)); } const llvm::MemoryBuffer * @@ -602,9 +593,9 @@ void SourceManager::overrideFileContents(const FileEntry *SourceFile, OverriddenFiles[SourceFile] = NewFile; } -llvm::StringRef SourceManager::getBufferData(FileID FID, bool *Invalid) const { +StringRef SourceManager::getBufferData(FileID FID, bool *Invalid) const { bool MyInvalid = false; - const SLocEntry &SLoc = getSLocEntry(FID.ID, &MyInvalid); + const SLocEntry &SLoc = getSLocEntry(FID, &MyInvalid); if (!SLoc.isFile() || MyInvalid) { if (Invalid) *Invalid = true; @@ -627,18 +618,32 @@ llvm::StringRef SourceManager::getBufferData(FileID FID, bool *Invalid) const { // SourceLocation manipulation methods. //===----------------------------------------------------------------------===// -/// getFileIDSlow - Return the FileID for a SourceLocation. This is a very hot -/// method that is used for all SourceManager queries that start with a -/// SourceLocation object. It is responsible for finding the entry in -/// SLocEntryTable which contains the specified location. +/// \brief Return the FileID for a SourceLocation. /// +/// This is the cache-miss path of getFileID. Not as hot as that function, but +/// still very important. It is responsible for finding the entry in the +/// SLocEntry tables that contains the specified location. FileID SourceManager::getFileIDSlow(unsigned SLocOffset) const { if (!SLocOffset) return FileID::get(0); + // Now it is time to search for the correct file. See where the SLocOffset + // sits in the global view and consult local or loaded buffers for it. + if (SLocOffset < NextLocalOffset) + return getFileIDLocal(SLocOffset); + return getFileIDLoaded(SLocOffset); +} + +/// \brief Return the FileID for a SourceLocation with a low offset. +/// +/// This function knows that the SourceLocation is in a local buffer, not a +/// loaded one. +FileID SourceManager::getFileIDLocal(unsigned SLocOffset) const { + assert(SLocOffset < NextLocalOffset && "Bad function choice"); + // After the first and second level caches, I see two common sorts of - // behavior: 1) a lot of searched FileID's are "near" the cached file location - // or are "near" the cached instantiation location. 2) others are just + // behavior: 1) a lot of searched FileID's are "near" the cached file + // location or are "near" the cached expansion location. 2) others are just // completely random and may be a very long way away. // // To handle this, we do a linear search for up to 8 steps to catch #1 quickly @@ -649,12 +654,13 @@ FileID SourceManager::getFileIDSlow(unsigned SLocOffset) const { // most newly created FileID. std::vector<SrcMgr::SLocEntry>::const_iterator I; - if (SLocEntryTable[LastFileIDLookup.ID].getOffset() < SLocOffset) { + if (LastFileIDLookup.ID < 0 || + LocalSLocEntryTable[LastFileIDLookup.ID].getOffset() < SLocOffset) { // Neither loc prunes our search. - I = SLocEntryTable.end(); + I = LocalSLocEntryTable.end(); } else { // Perhaps it is near the file point. - I = SLocEntryTable.begin()+LastFileIDLookup.ID; + I = LocalSLocEntryTable.begin()+LastFileIDLookup.ID; } // Find the FileID that contains this. "I" is an iterator that points to a @@ -662,25 +668,12 @@ FileID SourceManager::getFileIDSlow(unsigned SLocOffset) const { unsigned NumProbes = 0; while (1) { --I; - if (ExternalSLocEntries) { - bool Invalid = false; - getSLocEntry(FileID::get(I - SLocEntryTable.begin()), &Invalid); - if (Invalid) - return FileID::get(0); - } - if (I->getOffset() <= SLocOffset) { -#if 0 - printf("lin %d -> %d [%s] %d %d\n", SLocOffset, - I-SLocEntryTable.begin(), - I->isInstantiation() ? "inst" : "file", - LastFileIDLookup.ID, int(SLocEntryTable.end()-I)); -#endif - FileID Res = FileID::get(I-SLocEntryTable.begin()); - - // If this isn't an instantiation, remember it. We have good locality - // across FileID lookups. - if (!I->isInstantiation()) + FileID Res = FileID::get(int(I - LocalSLocEntryTable.begin())); + + // If this isn't an expansion, remember it. We have good locality across + // FileID lookups. + if (!I->isExpansion()) LastFileIDLookup = Res; NumLinearScans += NumProbes+1; return Res; @@ -691,7 +684,7 @@ FileID SourceManager::getFileIDSlow(unsigned SLocOffset) const { // Convert "I" back into an index. We know that it is an entry whose index is // larger than the offset we are looking for. - unsigned GreaterIndex = I-SLocEntryTable.begin(); + unsigned GreaterIndex = I - LocalSLocEntryTable.begin(); // LessIndex - This is the lower bound of the range that we're searching. // We know that the offset corresponding to the FileID is is less than // SLocOffset. @@ -700,8 +693,7 @@ FileID SourceManager::getFileIDSlow(unsigned SLocOffset) const { while (1) { bool Invalid = false; unsigned MiddleIndex = (GreaterIndex-LessIndex)/2+LessIndex; - unsigned MidOffset = getSLocEntry(FileID::get(MiddleIndex), &Invalid) - .getOffset(); + unsigned MidOffset = getLocalSLocEntry(MiddleIndex, &Invalid).getOffset(); if (Invalid) return FileID::get(0); @@ -715,18 +707,14 @@ FileID SourceManager::getFileIDSlow(unsigned SLocOffset) const { } // If the middle index contains the value, succeed and return. + // FIXME: This could be made faster by using a function that's aware of + // being in the local area. if (isOffsetInFileID(FileID::get(MiddleIndex), SLocOffset)) { -#if 0 - printf("bin %d -> %d [%s] %d %d\n", SLocOffset, - I-SLocEntryTable.begin(), - I->isInstantiation() ? "inst" : "file", - LastFileIDLookup.ID, int(SLocEntryTable.end()-I)); -#endif FileID Res = FileID::get(MiddleIndex); - // If this isn't an instantiation, remember it. We have good locality + // If this isn't a macro expansion, remember it. We have good locality // across FileID lookups. - if (!I->isInstantiation()) + if (!LocalSLocEntryTable[MiddleIndex].isExpansion()) LastFileIDLookup = Res; NumBinaryProbes += NumProbes; return Res; @@ -737,17 +725,82 @@ FileID SourceManager::getFileIDSlow(unsigned SLocOffset) const { } } +/// \brief Return the FileID for a SourceLocation with a high offset. +/// +/// This function knows that the SourceLocation is in a loaded buffer, not a +/// local one. +FileID SourceManager::getFileIDLoaded(unsigned SLocOffset) const { + assert(SLocOffset >= CurrentLoadedOffset && "Bad function choice"); + + // Sanity checking, otherwise a bug may lead to hanging in release build. + if (SLocOffset < CurrentLoadedOffset) + return FileID(); + + // Essentially the same as the local case, but the loaded array is sorted + // in the other direction. + + // First do a linear scan from the last lookup position, if possible. + unsigned I; + int LastID = LastFileIDLookup.ID; + if (LastID >= 0 || getLoadedSLocEntryByID(LastID).getOffset() < SLocOffset) + I = 0; + else + I = (-LastID - 2) + 1; + + unsigned NumProbes; + for (NumProbes = 0; NumProbes < 8; ++NumProbes, ++I) { + // Make sure the entry is loaded! + const SrcMgr::SLocEntry &E = getLoadedSLocEntry(I); + if (E.getOffset() <= SLocOffset) { + FileID Res = FileID::get(-int(I) - 2); + + if (!E.isExpansion()) + LastFileIDLookup = Res; + NumLinearScans += NumProbes + 1; + return Res; + } + } + + // Linear scan failed. Do the binary search. Note the reverse sorting of the + // table: GreaterIndex is the one where the offset is greater, which is + // actually a lower index! + unsigned GreaterIndex = I; + unsigned LessIndex = LoadedSLocEntryTable.size(); + NumProbes = 0; + while (1) { + ++NumProbes; + unsigned MiddleIndex = (LessIndex - GreaterIndex) / 2 + GreaterIndex; + const SrcMgr::SLocEntry &E = getLoadedSLocEntry(MiddleIndex); + + ++NumProbes; + + if (E.getOffset() > SLocOffset) { + GreaterIndex = MiddleIndex; + continue; + } + + if (isOffsetInFileID(FileID::get(-int(MiddleIndex) - 2), SLocOffset)) { + FileID Res = FileID::get(-int(MiddleIndex) - 2); + if (!E.isExpansion()) + LastFileIDLookup = Res; + NumBinaryProbes += NumProbes; + return Res; + } + + LessIndex = MiddleIndex; + } +} + SourceLocation SourceManager:: -getInstantiationLocSlowCase(SourceLocation Loc) const { +getExpansionLocSlowCase(SourceLocation Loc) const { do { // Note: If Loc indicates an offset into a token that came from a macro // expansion (e.g. the 5th character of the token) we do not want to add - // this offset when going to the instantiation location. The instatiation + // this offset when going to the expansion location. The expansion // location is the macro invocation, which the offset has nothing to do // with. This is unlike when we get the spelling loc, because the offset // directly correspond to the token whose spelling we're inspecting. - Loc = getSLocEntry(getFileID(Loc)).getInstantiation() - .getInstantiationLocStart(); + Loc = getSLocEntry(getFileID(Loc)).getExpansion().getExpansionLocStart(); } while (!Loc.isFileID()); return Loc; @@ -756,23 +809,32 @@ getInstantiationLocSlowCase(SourceLocation Loc) const { SourceLocation SourceManager::getSpellingLocSlowCase(SourceLocation Loc) const { do { std::pair<FileID, unsigned> LocInfo = getDecomposedLoc(Loc); - Loc = getSLocEntry(LocInfo.first).getInstantiation().getSpellingLoc(); - Loc = Loc.getFileLocWithOffset(LocInfo.second); + Loc = getSLocEntry(LocInfo.first).getExpansion().getSpellingLoc(); + Loc = Loc.getLocWithOffset(LocInfo.second); + } while (!Loc.isFileID()); + return Loc; +} + +SourceLocation SourceManager::getFileLocSlowCase(SourceLocation Loc) const { + do { + if (isMacroArgExpansion(Loc)) + Loc = getImmediateSpellingLoc(Loc); + else + Loc = getImmediateExpansionRange(Loc).first; } while (!Loc.isFileID()); return Loc; } std::pair<FileID, unsigned> -SourceManager::getDecomposedInstantiationLocSlowCase( +SourceManager::getDecomposedExpansionLocSlowCase( const SrcMgr::SLocEntry *E) const { - // If this is an instantiation record, walk through all the instantiation - // points. + // If this is an expansion record, walk through all the expansion points. FileID FID; SourceLocation Loc; unsigned Offset; do { - Loc = E->getInstantiation().getInstantiationLocStart(); + Loc = E->getExpansion().getExpansionLocStart(); FID = getFileID(Loc); E = &getSLocEntry(FID); @@ -785,16 +847,16 @@ SourceManager::getDecomposedInstantiationLocSlowCase( std::pair<FileID, unsigned> SourceManager::getDecomposedSpellingLocSlowCase(const SrcMgr::SLocEntry *E, unsigned Offset) const { - // If this is an instantiation record, walk through all the instantiation - // points. + // If this is an expansion record, walk through all the expansion points. FileID FID; SourceLocation Loc; do { - Loc = E->getInstantiation().getSpellingLoc(); + Loc = E->getExpansion().getSpellingLoc(); + Loc = Loc.getLocWithOffset(Offset); FID = getFileID(Loc); E = &getSLocEntry(FID); - Offset += Loc.getOffset()-E->getOffset(); + Offset = Loc.getOffset()-E->getOffset(); } while (!Loc.isFileID()); return std::make_pair(FID, Offset); @@ -807,45 +869,45 @@ SourceManager::getDecomposedSpellingLocSlowCase(const SrcMgr::SLocEntry *E, SourceLocation SourceManager::getImmediateSpellingLoc(SourceLocation Loc) const{ if (Loc.isFileID()) return Loc; std::pair<FileID, unsigned> LocInfo = getDecomposedLoc(Loc); - Loc = getSLocEntry(LocInfo.first).getInstantiation().getSpellingLoc(); - return Loc.getFileLocWithOffset(LocInfo.second); + Loc = getSLocEntry(LocInfo.first).getExpansion().getSpellingLoc(); + return Loc.getLocWithOffset(LocInfo.second); } -/// getImmediateInstantiationRange - Loc is required to be an instantiation -/// location. Return the start/end of the instantiation information. +/// getImmediateExpansionRange - Loc is required to be an expansion location. +/// Return the start/end of the expansion information. std::pair<SourceLocation,SourceLocation> -SourceManager::getImmediateInstantiationRange(SourceLocation Loc) const { - assert(Loc.isMacroID() && "Not an instantiation loc!"); - const InstantiationInfo &II = getSLocEntry(getFileID(Loc)).getInstantiation(); - return II.getInstantiationLocRange(); +SourceManager::getImmediateExpansionRange(SourceLocation Loc) const { + assert(Loc.isMacroID() && "Not a macro expansion loc!"); + const ExpansionInfo &Expansion = getSLocEntry(getFileID(Loc)).getExpansion(); + return Expansion.getExpansionLocRange(); } -/// getInstantiationRange - Given a SourceLocation object, return the -/// range of tokens covered by the instantiation in the ultimate file. +/// getExpansionRange - Given a SourceLocation object, return the range of +/// tokens covered by the expansion in the ultimate file. std::pair<SourceLocation,SourceLocation> -SourceManager::getInstantiationRange(SourceLocation Loc) const { +SourceManager::getExpansionRange(SourceLocation Loc) const { if (Loc.isFileID()) return std::make_pair(Loc, Loc); std::pair<SourceLocation,SourceLocation> Res = - getImmediateInstantiationRange(Loc); + getImmediateExpansionRange(Loc); - // Fully resolve the start and end locations to their ultimate instantiation + // Fully resolve the start and end locations to their ultimate expansion // points. while (!Res.first.isFileID()) - Res.first = getImmediateInstantiationRange(Res.first).first; + Res.first = getImmediateExpansionRange(Res.first).first; while (!Res.second.isFileID()) - Res.second = getImmediateInstantiationRange(Res.second).second; + Res.second = getImmediateExpansionRange(Res.second).second; return Res; } -bool SourceManager::isMacroArgInstantiation(SourceLocation Loc) const { +bool SourceManager::isMacroArgExpansion(SourceLocation Loc) const { if (!Loc.isMacroID()) return false; FileID FID = getFileID(Loc); const SrcMgr::SLocEntry *E = &getSLocEntry(FID); - const SrcMgr::InstantiationInfo &II = E->getInstantiation(); - return II.isMacroArgInstantiation(); + const SrcMgr::ExpansionInfo &Expansion = E->getExpansion(); + return Expansion.isMacroArgExpansion(); } @@ -913,10 +975,10 @@ unsigned SourceManager::getSpellingColumnNumber(SourceLocation Loc, return getColumnNumber(LocInfo.first, LocInfo.second, Invalid); } -unsigned SourceManager::getInstantiationColumnNumber(SourceLocation Loc, - bool *Invalid) const { +unsigned SourceManager::getExpansionColumnNumber(SourceLocation Loc, + bool *Invalid) const { if (isInvalid(Loc, Invalid)) return 0; - std::pair<FileID, unsigned> LocInfo = getDecomposedInstantiationLoc(Loc); + std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc); return getColumnNumber(LocInfo.first, LocInfo.second, Invalid); } @@ -927,10 +989,10 @@ unsigned SourceManager::getPresumedColumnNumber(SourceLocation Loc, } static LLVM_ATTRIBUTE_NOINLINE void -ComputeLineNumbers(Diagnostic &Diag, ContentCache *FI, +ComputeLineNumbers(DiagnosticsEngine &Diag, ContentCache *FI, llvm::BumpPtrAllocator &Alloc, const SourceManager &SM, bool &Invalid); -static void ComputeLineNumbers(Diagnostic &Diag, ContentCache *FI, +static void ComputeLineNumbers(DiagnosticsEngine &Diag, ContentCache *FI, llvm::BumpPtrAllocator &Alloc, const SourceManager &SM, bool &Invalid) { // Note that calling 'getBuffer()' may lazily page in the file. @@ -941,7 +1003,7 @@ static void ComputeLineNumbers(Diagnostic &Diag, ContentCache *FI, // Find the file offsets of all of the *physical* source lines. This does // not look at trigraphs, escaped newlines, or anything else tricky. - llvm::SmallVector<unsigned, 256> LineOffsets; + SmallVector<unsigned, 256> LineOffsets; // Line #1 starts at char 0. LineOffsets.push_back(0); @@ -1108,10 +1170,10 @@ unsigned SourceManager::getSpellingLineNumber(SourceLocation Loc, std::pair<FileID, unsigned> LocInfo = getDecomposedSpellingLoc(Loc); return getLineNumber(LocInfo.first, LocInfo.second); } -unsigned SourceManager::getInstantiationLineNumber(SourceLocation Loc, - bool *Invalid) const { +unsigned SourceManager::getExpansionLineNumber(SourceLocation Loc, + bool *Invalid) const { if (isInvalid(Loc, Invalid)) return 0; - std::pair<FileID, unsigned> LocInfo = getDecomposedInstantiationLoc(Loc); + std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc); return getLineNumber(LocInfo.first, LocInfo.second); } unsigned SourceManager::getPresumedLineNumber(SourceLocation Loc, @@ -1131,7 +1193,7 @@ unsigned SourceManager::getPresumedLineNumber(SourceLocation Loc, SrcMgr::CharacteristicKind SourceManager::getFileCharacteristic(SourceLocation Loc) const { assert(!Loc.isInvalid() && "Can't get file characteristic of invalid loc!"); - std::pair<FileID, unsigned> LocInfo = getDecomposedInstantiationLoc(Loc); + std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc); bool Invalid = false; const SLocEntry &SEntry = getSLocEntry(LocInfo.first, &Invalid); if (Invalid || !SEntry.isFile()) @@ -1172,13 +1234,13 @@ const char *SourceManager::getBufferName(SourceLocation Loc, /// or GNU line marker directives. This provides a view on the data that a /// user should see in diagnostics, for example. /// -/// Note that a presumed location is always given as the instantiation point -/// of an instantiation location, not at the spelling location. +/// Note that a presumed location is always given as the expansion point of an +/// expansion location, not at the spelling location. PresumedLoc SourceManager::getPresumedLoc(SourceLocation Loc) const { if (Loc.isInvalid()) return PresumedLoc(); - // Presumed locations are always for instantiation points. - std::pair<FileID, unsigned> LocInfo = getDecomposedInstantiationLoc(Loc); + // Presumed locations are always for expansion points. + std::pair<FileID, unsigned> LocInfo = getDecomposedExpansionLoc(Loc); bool Invalid = false; const SLocEntry &Entry = getSLocEntry(LocInfo.first, &Invalid); @@ -1229,7 +1291,7 @@ PresumedLoc SourceManager::getPresumedLoc(SourceLocation Loc) const { // Handle virtual #include manipulation. if (Entry->IncludeOffset) { IncludeLoc = getLocForStartOfFile(LocInfo.first); - IncludeLoc = IncludeLoc.getFileLocWithOffset(Entry->IncludeOffset); + IncludeLoc = IncludeLoc.getLocWithOffset(Entry->IncludeOffset); } } } @@ -1237,6 +1299,25 @@ PresumedLoc SourceManager::getPresumedLoc(SourceLocation Loc) const { return PresumedLoc(Filename, LineNo, ColNo, IncludeLoc); } +/// \brief The size of the SLocEnty that \arg FID represents. +unsigned SourceManager::getFileIDSize(FileID FID) const { + bool Invalid = false; + const SrcMgr::SLocEntry &Entry = getSLocEntry(FID, &Invalid); + if (Invalid) + return 0; + + int ID = FID.ID; + unsigned NextOffset; + if ((ID > 0 && unsigned(ID+1) == local_sloc_entry_size())) + NextOffset = getNextLocalOffset(); + else if (ID+1 == -1) + NextOffset = MaxLoadedOffset; + else + NextOffset = getSLocEntry(FileID::get(ID+1)).getOffset(); + + return NextOffset - Entry.getOffset() - 1; +} + //===----------------------------------------------------------------------===// // Other miscellaneous methods. //===----------------------------------------------------------------------===// @@ -1259,24 +1340,36 @@ static llvm::Optional<ino_t> getActualFileInode(const FileEntry *File) { /// \brief Get the source location for the given file:line:col triplet. /// /// If the source file is included multiple times, the source location will -/// be based upon the first inclusion. -SourceLocation SourceManager::getLocation(const FileEntry *SourceFile, - unsigned Line, unsigned Col) { +/// be based upon an arbitrary inclusion. +SourceLocation SourceManager::translateFileLineCol(const FileEntry *SourceFile, + unsigned Line, + unsigned Col) const { assert(SourceFile && "Null source file!"); assert(Line && Col && "Line and column should start from 1!"); + FileID FirstFID = translateFile(SourceFile); + return translateLineCol(FirstFID, Line, Col); +} + +/// \brief Get the FileID for the given file. +/// +/// If the source file is included multiple times, the FileID will be the +/// first inclusion. +FileID SourceManager::translateFile(const FileEntry *SourceFile) const { + assert(SourceFile && "Null source file!"); + // Find the first file ID that corresponds to the given file. FileID FirstFID; // First, check the main file ID, since it is common to look for a // location in the main file. llvm::Optional<ino_t> SourceFileInode; - llvm::Optional<llvm::StringRef> SourceFileName; + llvm::Optional<StringRef> SourceFileName; if (!MainFileID.isInvalid()) { bool Invalid = false; const SLocEntry &MainSLoc = getSLocEntry(MainFileID, &Invalid); if (Invalid) - return SourceLocation(); + return FileID(); if (MainSLoc.isFile()) { const ContentCache *MainContentCache @@ -1308,12 +1401,12 @@ SourceLocation SourceManager::getLocation(const FileEntry *SourceFile, if (FirstFID.isInvalid()) { // The location we're looking for isn't in the main file; look - // through all of the source locations. - for (unsigned I = 0, N = sloc_entry_size(); I != N; ++I) { + // through all of the local source locations. + for (unsigned I = 0, N = local_sloc_entry_size(); I != N; ++I) { bool Invalid = false; - const SLocEntry &SLoc = getSLocEntry(I, &Invalid); + const SLocEntry &SLoc = getLocalSLocEntry(I, &Invalid); if (Invalid) - return SourceLocation(); + return FileID(); if (SLoc.isFile() && SLoc.getFile().getContentCache() && @@ -1322,6 +1415,18 @@ SourceLocation SourceManager::getLocation(const FileEntry *SourceFile, break; } } + // If that still didn't help, try the modules. + if (FirstFID.isInvalid()) { + for (unsigned I = 0, N = loaded_sloc_entry_size(); I != N; ++I) { + const SLocEntry &SLoc = getLoadedSLocEntry(I); + if (SLoc.isFile() && + SLoc.getFile().getContentCache() && + SLoc.getFile().getContentCache()->OrigEntry == SourceFile) { + FirstFID = FileID::get(-int(I) - 2); + break; + } + } + } } // If we haven't found what we want yet, try again, but this time stat() @@ -1333,10 +1438,12 @@ SourceLocation SourceManager::getLocation(const FileEntry *SourceFile, (SourceFileInode || (SourceFileInode = getActualFileInode(SourceFile)))) { bool Invalid = false; - for (unsigned I = 0, N = sloc_entry_size(); I != N; ++I) { - const SLocEntry &SLoc = getSLocEntry(I, &Invalid); + for (unsigned I = 0, N = local_sloc_entry_size(); I != N; ++I) { + FileID IFileID; + IFileID.ID = I; + const SLocEntry &SLoc = getSLocEntry(IFileID, &Invalid); if (Invalid) - return SourceLocation(); + return FileID(); if (SLoc.isFile()) { const ContentCache *FileContentCache @@ -1355,20 +1462,38 @@ SourceLocation SourceManager::getLocation(const FileEntry *SourceFile, } } } - - if (FirstFID.isInvalid()) + + return FirstFID; +} + +/// \brief Get the source location in \arg FID for the given line:col. +/// Returns null location if \arg FID is not a file SLocEntry. +SourceLocation SourceManager::translateLineCol(FileID FID, + unsigned Line, + unsigned Col) const { + if (FID.isInvalid()) + return SourceLocation(); + + bool Invalid = false; + const SLocEntry &Entry = getSLocEntry(FID, &Invalid); + if (Invalid) + return SourceLocation(); + + if (!Entry.isFile()) return SourceLocation(); + SourceLocation FileLoc = SourceLocation::getFileLoc(Entry.getOffset()); + if (Line == 1 && Col == 1) - return getLocForStartOfFile(FirstFID); + return FileLoc; ContentCache *Content - = const_cast<ContentCache *>(getOrCreateContentCache(SourceFile)); + = const_cast<ContentCache *>(Entry.getFile().getContentCache()); if (!Content) return SourceLocation(); // If this is the first use of line information for this buffer, compute the - /// SourceLineCache for it on demand. + // SourceLineCache for it on demand. if (Content->SourceLineCache == 0) { bool MyInvalid = false; ComputeLineNumbers(Diag, Content, ContentCacheAlloc, *this, MyInvalid); @@ -1380,33 +1505,150 @@ SourceLocation SourceManager::getLocation(const FileEntry *SourceFile, unsigned Size = Content->getBuffer(Diag, *this)->getBufferSize(); if (Size > 0) --Size; - return getLocForStartOfFile(FirstFID).getFileLocWithOffset(Size); + return FileLoc.getLocWithOffset(Size); } unsigned FilePos = Content->SourceLineCache[Line - 1]; const char *Buf = Content->getBuffer(Diag, *this)->getBufferStart() + FilePos; unsigned BufLength = Content->getBuffer(Diag, *this)->getBufferEnd() - Buf; + if (BufLength == 0) + return FileLoc.getLocWithOffset(FilePos); + unsigned i = 0; // Check that the given column is valid. while (i < BufLength-1 && i < Col-1 && Buf[i] != '\n' && Buf[i] != '\r') ++i; if (i < Col-1) - return getLocForStartOfFile(FirstFID).getFileLocWithOffset(FilePos + i); + return FileLoc.getLocWithOffset(FilePos + i); - return getLocForStartOfFile(FirstFID).getFileLocWithOffset(FilePos + Col - 1); + return FileLoc.getLocWithOffset(FilePos + Col - 1); } -/// Given a decomposed source location, move it up the include/instantiation -/// stack to the parent source location. If this is possible, return the -/// decomposed version of the parent in Loc and return false. If Loc is the -/// top-level entry, return true and don't modify it. +/// \brief Compute a map of macro argument chunks to their expanded source +/// location. Chunks that are not part of a macro argument will map to an +/// invalid source location. e.g. if a file contains one macro argument at +/// offset 100 with length 10, this is how the map will be formed: +/// 0 -> SourceLocation() +/// 100 -> Expanded macro arg location +/// 110 -> SourceLocation() +void SourceManager::computeMacroArgsCache(MacroArgsMap *&CachePtr, + FileID FID) const { + assert(!FID.isInvalid()); + assert(!CachePtr); + + CachePtr = new MacroArgsMap(); + MacroArgsMap &MacroArgsCache = *CachePtr; + // Initially no macro argument chunk is present. + MacroArgsCache.insert(std::make_pair(0, SourceLocation())); + + int ID = FID.ID; + while (1) { + ++ID; + // Stop if there are no more FileIDs to check. + if (ID > 0) { + if (unsigned(ID) >= local_sloc_entry_size()) + return; + } else if (ID == -1) { + return; + } + + const SrcMgr::SLocEntry &Entry = getSLocEntryByID(ID); + if (Entry.isFile()) { + SourceLocation IncludeLoc = Entry.getFile().getIncludeLoc(); + if (IncludeLoc.isInvalid()) + continue; + if (!isInFileID(IncludeLoc, FID)) + return; // No more files/macros that may be "contained" in this file. + + // Skip the files/macros of the #include'd file, we only care about macros + // that lexed macro arguments from our file. + if (Entry.getFile().NumCreatedFIDs) + ID += Entry.getFile().NumCreatedFIDs - 1/*because of next ++ID*/; + continue; + } + + if (!Entry.getExpansion().isMacroArgExpansion()) + continue; + + SourceLocation SpellLoc = + getSpellingLoc(Entry.getExpansion().getSpellingLoc()); + unsigned BeginOffs; + if (!isInFileID(SpellLoc, FID, &BeginOffs)) + return; // No more files/macros that may be "contained" in this file. + unsigned EndOffs = BeginOffs + getFileIDSize(FileID::get(ID)); + + // Add a new chunk for this macro argument. A previous macro argument chunk + // may have been lexed again, so e.g. if the map is + // 0 -> SourceLocation() + // 100 -> Expanded loc #1 + // 110 -> SourceLocation() + // and we found a new macro FileID that lexed from offet 105 with length 3, + // the new map will be: + // 0 -> SourceLocation() + // 100 -> Expanded loc #1 + // 105 -> Expanded loc #2 + // 108 -> Expanded loc #1 + // 110 -> SourceLocation() + // + // Since re-lexed macro chunks will always be the same size or less of + // previous chunks, we only need to find where the ending of the new macro + // chunk is mapped to and update the map with new begin/end mappings. + + MacroArgsMap::iterator I = MacroArgsCache.upper_bound(EndOffs); + --I; + SourceLocation EndOffsMappedLoc = I->second; + MacroArgsCache[BeginOffs] = SourceLocation::getMacroLoc(Entry.getOffset()); + MacroArgsCache[EndOffs] = EndOffsMappedLoc; + } +} + +/// \brief If \arg Loc points inside a function macro argument, the returned +/// location will be the macro location in which the argument was expanded. +/// If a macro argument is used multiple times, the expanded location will +/// be at the first expansion of the argument. +/// e.g. +/// MY_MACRO(foo); +/// ^ +/// Passing a file location pointing at 'foo', will yield a macro location +/// where 'foo' was expanded into. +SourceLocation +SourceManager::getMacroArgExpandedLocation(SourceLocation Loc) const { + if (Loc.isInvalid() || !Loc.isFileID()) + return Loc; + + FileID FID; + unsigned Offset; + llvm::tie(FID, Offset) = getDecomposedLoc(Loc); + if (FID.isInvalid()) + return Loc; + + MacroArgsMap *&MacroArgsCache = MacroArgsCacheMap[FID]; + if (!MacroArgsCache) + computeMacroArgsCache(MacroArgsCache, FID); + + assert(!MacroArgsCache->empty()); + MacroArgsMap::iterator I = MacroArgsCache->upper_bound(Offset); + --I; + + unsigned MacroArgBeginOffs = I->first; + SourceLocation MacroArgExpandedLoc = I->second; + if (MacroArgExpandedLoc.isValid()) + return MacroArgExpandedLoc.getLocWithOffset(Offset - MacroArgBeginOffs); + + return Loc; +} + +/// Given a decomposed source location, move it up the include/expansion stack +/// to the parent source location. If this is possible, return the decomposed +/// version of the parent in Loc and return false. If Loc is the top-level +/// entry, return true and don't modify it. static bool MoveUpIncludeHierarchy(std::pair<FileID, unsigned> &Loc, const SourceManager &SM) { SourceLocation UpperLoc; const SrcMgr::SLocEntry &Entry = SM.getSLocEntry(Loc.first); - if (Entry.isInstantiation()) - UpperLoc = Entry.getInstantiation().getInstantiationLocStart(); + if (Entry.isExpansion()) + UpperLoc = Entry.getExpansion().getExpansionLocEnd(); else UpperLoc = Entry.getFile().getIncludeLoc(); @@ -1427,11 +1669,6 @@ bool SourceManager::isBeforeInTranslationUnit(SourceLocation LHS, if (LHS == RHS) return false; - // If both locations are macro instantiations, the order of their offsets - // reflect the order that the tokens, pointed to by these locations, were - // instantiated (during parsing each token that is instantiated by a macro, - // expands the SLocEntries). - std::pair<FileID, unsigned> LOffs = getDecomposedLoc(LHS); std::pair<FileID, unsigned> ROffs = getDecomposedLoc(RHS); @@ -1445,41 +1682,28 @@ bool SourceManager::isBeforeInTranslationUnit(SourceLocation LHS, return IsBeforeInTUCache.getCachedResult(LOffs.second, ROffs.second); // Okay, we missed in the cache, start updating the cache for this query. - IsBeforeInTUCache.setQueryFIDs(LOffs.first, ROffs.first); - - // "Traverse" the include/instantiation stacks of both locations and try to - // find a common "ancestor". FileIDs build a tree-like structure that - // reflects the #include hierarchy, and this algorithm needs to find the - // nearest common ancestor between the two locations. For example, if you - // have a.c that includes b.h and c.h, and are comparing a location in b.h to - // a location in c.h, we need to find that their nearest common ancestor is - // a.c, and compare the locations of the two #includes to find their relative - // ordering. - // - // SourceManager assigns FileIDs in order of parsing. This means that an - // includee always has a larger FileID than an includer. While you might - // think that we could just compare the FileID's here, that doesn't work to - // compare a point at the end of a.c with a point within c.h. Though c.h has - // a larger FileID, we have to compare the include point of c.h to the - // location in a.c. - // - // Despite not being able to directly compare FileID's, we can tell that a - // larger FileID is necessarily more deeply nested than a lower one and use - // this information to walk up the tree to the nearest common ancestor. + IsBeforeInTUCache.setQueryFIDs(LOffs.first, ROffs.first, + /*isLFIDBeforeRFID=*/LOffs.first.ID < ROffs.first.ID); + + // We need to find the common ancestor. The only way of doing this is to + // build the complete include chain for one and then walking up the chain + // of the other looking for a match. + // We use a map from FileID to Offset to store the chain. Easier than writing + // a custom set hash info that only depends on the first part of a pair. + typedef llvm::DenseMap<FileID, unsigned> LocSet; + LocSet LChain; do { - // If LOffs is larger than ROffs, then LOffs must be more deeply nested than - // ROffs, walk up the #include chain. - if (LOffs.first.ID > ROffs.first.ID) { - if (MoveUpIncludeHierarchy(LOffs, *this)) - break; // We reached the top. - - } else { - // Otherwise, ROffs is larger than LOffs, so ROffs must be more deeply - // nested than LOffs, walk up the #include chain. - if (MoveUpIncludeHierarchy(ROffs, *this)) - break; // We reached the top. - } - } while (LOffs.first != ROffs.first); + LChain.insert(LOffs); + // We catch the case where LOffs is in a file included by ROffs and + // quit early. The other way round unfortunately remains suboptimal. + } while (LOffs.first != ROffs.first && !MoveUpIncludeHierarchy(LOffs, *this)); + LocSet::iterator I; + while((I = LChain.find(ROffs.first)) == LChain.end()) { + if (MoveUpIncludeHierarchy(ROffs, *this)) + break; // Met at topmost file. + } + if (I != LChain.end()) + LOffs = *I; // If we exited because we found a nearest common ancestor, compare the // locations within the common file and cache them. @@ -1488,26 +1712,21 @@ bool SourceManager::isBeforeInTranslationUnit(SourceLocation LHS, return IsBeforeInTUCache.getCachedResult(LOffs.second, ROffs.second); } - // There is no common ancestor, most probably because one location is in the - // predefines buffer or an AST file. - // FIXME: We should rearrange the external interface so this simply never - // happens; it can't conceptually happen. Also see PR5662. - IsBeforeInTUCache.setQueryFIDs(FileID(), FileID()); // Don't try caching. - - // Zip both entries up to the top level record. - while (!MoveUpIncludeHierarchy(LOffs, *this)) /*empty*/; - while (!MoveUpIncludeHierarchy(ROffs, *this)) /*empty*/; - - // If exactly one location is a memory buffer, assume it precedes the other. - - // Strip off macro instantation locations, going up to the top-level File - // SLocEntry. - bool LIsMB = getFileEntryForID(LOffs.first) == 0; - bool RIsMB = getFileEntryForID(ROffs.first) == 0; - if (LIsMB != RIsMB) - return LIsMB; - - // Otherwise, just assume FileIDs were created in order. + // This can happen if a location is in a built-ins buffer. + // But see PR5662. + // Clear the lookup cache, it depends on a common location. + IsBeforeInTUCache.clear(); + bool LIsBuiltins = strcmp("<built-in>", + getBuffer(LOffs.first)->getBufferIdentifier()) == 0; + bool RIsBuiltins = strcmp("<built-in>", + getBuffer(ROffs.first)->getBufferIdentifier()) == 0; + // built-in is before non-built-in + if (LIsBuiltins != RIsBuiltins) + return LIsBuiltins; + assert(LIsBuiltins && RIsBuiltins && + "Non-built-in locations must be rooted in the main file"); + // Both are in built-in buffers, but from different files. We just claim that + // lower IDs come first. return LOffs.first < ROffs.first; } @@ -1517,20 +1736,26 @@ void SourceManager::PrintStats() const { llvm::errs() << "\n*** Source Manager Stats:\n"; llvm::errs() << FileInfos.size() << " files mapped, " << MemBufferInfos.size() << " mem buffers mapped.\n"; - llvm::errs() << SLocEntryTable.size() << " SLocEntry's allocated (" - << SLocEntryTable.capacity()*sizeof(SrcMgr::SLocEntry) + llvm::errs() << LocalSLocEntryTable.size() << " local SLocEntry's allocated (" + << llvm::capacity_in_bytes(LocalSLocEntryTable) << " bytes of capacity), " - << NextOffset << "B of Sloc address space used.\n"; - + << NextLocalOffset << "B of Sloc address space used.\n"; + llvm::errs() << LoadedSLocEntryTable.size() + << " loaded SLocEntries allocated, " + << MaxLoadedOffset - CurrentLoadedOffset + << "B of Sloc address space used.\n"; + unsigned NumLineNumsComputed = 0; unsigned NumFileBytesMapped = 0; for (fileinfo_iterator I = fileinfo_begin(), E = fileinfo_end(); I != E; ++I){ NumLineNumsComputed += I->second->SourceLineCache != 0; NumFileBytesMapped += I->second->getSizeBytesMapped(); } + unsigned NumMacroArgsComputed = MacroArgsCacheMap.size(); llvm::errs() << NumFileBytesMapped << " bytes of files mapped, " - << NumLineNumsComputed << " files with line #'s computed.\n"; + << NumLineNumsComputed << " files with line #'s computed, " + << NumMacroArgsComputed << " files with macro args computed.\n"; llvm::errs() << "FileID scans: " << NumLinearScans << " linear, " << NumBinaryProbes << " binary.\n"; } @@ -1557,3 +1782,11 @@ SourceManager::MemoryBufferSizes SourceManager::getMemoryBufferSizes() const { return MemoryBufferSizes(malloc_bytes, mmap_bytes); } +size_t SourceManager::getDataStructureSizes() const { + return llvm::capacity_in_bytes(MemBufferInfos) + + llvm::capacity_in_bytes(LocalSLocEntryTable) + + llvm::capacity_in_bytes(LoadedSLocEntryTable) + + llvm::capacity_in_bytes(SLocEntryLoaded) + + llvm::capacity_in_bytes(FileInfos) + + llvm::capacity_in_bytes(OverriddenFiles); +} |