From 53992adde3eda3ccf9da63bc7e45673f043de18f Mon Sep 17 00:00:00 2001 From: rdivacky Date: Thu, 27 May 2010 15:17:06 +0000 Subject: Update clang to r104832. --- lib/Basic/SourceManager.cpp | 131 +++++++++++++++++++++++++------------------- 1 file changed, 74 insertions(+), 57 deletions(-) (limited to 'lib/Basic/SourceManager.cpp') diff --git a/lib/Basic/SourceManager.cpp b/lib/Basic/SourceManager.cpp index 3ecab1d..e6d9785 100644 --- a/lib/Basic/SourceManager.cpp +++ b/lib/Basic/SourceManager.cpp @@ -1154,6 +1154,27 @@ SourceLocation SourceManager::getLocation(const FileEntry *SourceFile, return getLocForStartOfFile(FirstFID).getFileLocWithOffset(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. +static bool MoveUpIncludeHierarchy(std::pair &Loc, + const SourceManager &SM) { + SourceLocation UpperLoc; + const SrcMgr::SLocEntry &Entry = SM.getSLocEntry(Loc.first); + if (Entry.isInstantiation()) + UpperLoc = Entry.getInstantiation().getInstantiationLocStart(); + else + UpperLoc = Entry.getFile().getIncludeLoc(); + + if (UpperLoc.isInvalid()) + return true; // We reached the top. + + Loc = SM.getDecomposedLoc(UpperLoc); + return false; +} + + /// \brief Determines the order of 2 source locations in the translation unit. /// /// \returns true if LHS source location comes before RHS, false otherwise. @@ -1172,78 +1193,74 @@ bool SourceManager::isBeforeInTranslationUnit(SourceLocation LHS, // If we are comparing a source location with multiple locations in the same // file, we get a big win by caching the result. + if (IsBeforeInTUCache.isCacheValid(LOffs.first, ROffs.first)) + return IsBeforeInTUCache.getCachedResult(LOffs.second, ROffs.second); - if (LastLFIDForBeforeTUCheck == LOffs.first && - LastRFIDForBeforeTUCheck == ROffs.first) - return LastResForBeforeTUCheck; - - LastLFIDForBeforeTUCheck = LOffs.first; - LastRFIDForBeforeTUCheck = ROffs.first; + // 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". + // 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. // - // First we traverse the stack of the right location and check each level - // against the level of the left location, while collecting all levels in a - // "stack map". - - std::map ROffsMap; - ROffsMap[ROffs.first] = ROffs.second; - - while (1) { - SourceLocation UpperLoc; - const SrcMgr::SLocEntry &Entry = getSLocEntry(ROffs.first); - if (Entry.isInstantiation()) - UpperLoc = Entry.getInstantiation().getInstantiationLocStart(); - else - UpperLoc = Entry.getFile().getIncludeLoc(); - - if (UpperLoc.isInvalid()) - break; // We reached the top. - - ROffs = getDecomposedLoc(UpperLoc); - - if (LOffs.first == ROffs.first) - return LastResForBeforeTUCheck = LOffs.second < ROffs.second; - - ROffsMap[ROffs.first] = ROffs.second; - } - - // We didn't find a common ancestor. Now traverse the stack of the left - // location, checking against the stack map of the right location. - - while (1) { - SourceLocation UpperLoc; - const SrcMgr::SLocEntry &Entry = getSLocEntry(LOffs.first); - if (Entry.isInstantiation()) - UpperLoc = Entry.getInstantiation().getInstantiationLocStart(); - else - UpperLoc = Entry.getFile().getIncludeLoc(); - - if (UpperLoc.isInvalid()) - break; // We reached the top. - - LOffs = getDecomposedLoc(UpperLoc); + // 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. + 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); - std::map::iterator I = ROffsMap.find(LOffs.first); - if (I != ROffsMap.end()) - return LastResForBeforeTUCheck = LOffs.second < I->second; + // If we exited because we found a nearest common ancestor, compare the + // locations within the common file and cache them. + if (LOffs.first == ROffs.first) { + IsBeforeInTUCache.setCommonLoc(LOffs.first, LOffs.second, ROffs.second); + return IsBeforeInTUCache.getCachedResult(LOffs.second, ROffs.second); } // There is no common ancestor, most probably because one location is in the - // predefines buffer. - // + // predefines buffer or a PCH 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 preceeds the other. - bool LIsMB = !getSLocEntry(LOffs.first).getFile().getContentCache()->Entry; - bool RIsMB = !getSLocEntry(ROffs.first).getFile().getContentCache()->Entry; + + // 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 LastResForBeforeTUCheck = LIsMB; + return LIsMB; // Otherwise, just assume FileIDs were created in order. - return LastResForBeforeTUCheck = (LOffs.first < ROffs.first); + return LOffs.first < ROffs.first; } /// PrintStats - Print statistics to stderr. -- cgit v1.1