[SourceManager] isPointWithin: avoid using isBeforeInTranslationUnit, compare buffer offsets directly for lexical correctness

[arphaman]

Summary

The current implementation of isPointWithin uses isBeforeInTranslationUnit to check if a location is within a range.
The problem is that isPointWithin is used to perform is lexical range check, i.e. we want to determine if a location in a particular source file is within a source range in the same source file.
The use of isBeforeInTranslationUnit is not correct for this use-case, as one source file can be included multiple times. Given a source range and a location that's lexically contained within that source range (e.g. file.h:1:2->1:10 and file:h:1:5), isBeforeInTranslationUnit will fail to correctly determine if a source range from the first occurrence of the source file contains a location from the second occurrence of the same source file, as the start and end of the range are both included before the location.
This patch reimplements isPointWithin to ensure that buffer offsets are compared directly for lexical correctness.

This patch is a pre-requisuite to fix a bug in clang-rename where we are unable to rename a structure in a PCH that has a header that's included multiple times (follow-up patch will be posted to update clang-rename to use isPointWithin).

rdar://42746284

[jkorous]

Hi Alex, nice work!

I am just wondering if it would be beneficial to assert Loc and End are in the same file. It might help to catch bugs.

I also stumbled upon this function but not sure it makes things significantly cleaner here:
https://clang.llvm.org/doxygen/SourceLocation_8h_source.html#l00175

LGTM otherwise.

[ioeric]

lib/Basic/SourceManager.cpp

2035

Why do we disallow locations from macro expansions?

2049

nit: the pattern seems repetitive. Maybe pull out a helper/lambda like: isBeforeInSameFile(L1, L2)?

[arphaman]

In D50740#1202248, @jkorous wrote:

Hi Alex, nice work!

I am just wondering if it would be beneficial to assert Loc and End are in the same file. It might help to catch bugs.

I don't see the value in that unless I'm misunderstanding something. We already check if Loc and End are in the same file, and return false if they're not.

I also stumbled upon this function but not sure it makes things significantly cleaner here:
https://clang.llvm.org/doxygen/SourceLocation_8h_source.html#l00175

LGTM otherwise.

[arphaman]

lib/Basic/SourceManager.cpp

2035

I changed the patch to allow them by working with spelling locs.

[arphaman]

• Use lambda
• Work with spelling locs

[rsmith]

In D50740#1203126, @arphaman wrote:

In D50740#1202248, @jkorous wrote:

Hi Alex, nice work!

I am just wondering if it would be beneficial to assert Loc and End are in the same file. It might help to catch bugs.

I don't see the value in that unless I'm misunderstanding something. We already check if Loc and End are in the same file, and return false if they're not.

I think we should assert that Start and End are in the same file. If not, the query doesn't make any sense; the range is malformed. And maybe we should also assert that Start is before End in that file.

include/clang/Basic/SourceManager.h

1585–1586

Please rename this function to make it clearer what it's doing. The old implementation is the obvious one for a function with this name. Maybe isSpellingLocInFileRange or similar?

lib/Basic/SourceManager.cpp

2038–2050

Does this do the right thing if both points are within (eg) macro expansion ranges in the same file? Eg, given:

// A
#define FOO BAR
// B
FOO
// C

is the macro-expanded BAR token between B and C? Is it between A and B?

I would guess that the intended semantics here are:

• Start and End are expected to be file locations in the same inclusion of the same file, with Start occuring no later than End.
• Loc is an arbitrary location.
• Function returns true if the spelling location of Loc is in the same source file as Start and End, and occurs between them; false otherwise.

Is that right? If so, please write that down somewhere; the current function comment is too vague. (And if not, please write down what the intended rule is.)

[arphaman]

Hmm, after more analysis I realized that this is not the right solution for the rename problem. It would be correct to map one file:line:column location to a set of SourceLocations, and to use the old isPointWithin on a set of such locations. I opened https://reviews.llvm.org/D50926 instead. Sorry for the trouble!

include/clang/Basic/SourceManager.h

bool isBeforeInSLocAddrSpace(SourceLocation LHS, unsigned RHS) const {
     bool LHSLoaded = LHSOffset >= CurrentLoadedOffset;
     bool RHSLoaded = RHS >= CurrentLoadedOffset;
     if (LHSLoaded == RHSLoaded)
       return LHSOffset < RHS;
 
     return LHSLoaded;
   }
 
-  /// Return true if the Point is within Start and End.
+  /// Returns true if the point is within the start and end range.
+  ///
+  /// This check does a lexical check if the given point is located within a
+  /// range in one particular source file (regardless of whether the point is
+  /// located in the same inclusion span as the range).
   bool isPointWithin(SourceLocation Location, SourceLocation Start,
-                     SourceLocation End) const {
-    return Location == Start || Location == End ||
-           (isBeforeInTranslationUnit(Start, Location) &&
-            isBeforeInTranslationUnit(Location, End));
-  }
+                     SourceLocation End) const;
 
   // Iterators over FileInfos.
   using fileinfo_iterator =
       llvm::DenseMap<const FileEntry*, SrcMgr::ContentCache*>::const_iterator;
 
   fileinfo_iterator fileinfo_begin() const { return FileInfos.begin(); }
   fileinfo_iterator fileinfo_end() const { return FileInfos.end(); }
   bool hasFileInfo(const FileEntry *File) const {

lib/Basic/SourceManager.cpp

InBeforeInTUCacheEntry &SourceManager::getInBeforeInTUCache(FileID LFID,
   InBeforeInTUCache::iterator I = IBTUCache.find(Key);
   if (I != IBTUCache.end())
     return I->second;
 
   // Fall back to the overflow value.
   return IBTUCacheOverflow;
 }
 
+bool SourceManager::isPointWithin(SourceLocation Loc, SourceLocation Start,
+                                  SourceLocation End) const {
+  assert(Start.isValid() && End.isValid() && Loc.isValid() &&
+         "Passed invalid source location!");
+
+  std::pair<FileID, unsigned> PointLoc = getDecomposedLoc(getSpellingLoc(Loc));
+
+  auto isOrderedInSameFile =
+      [&](SourceLocation RangeLoc,
+          llvm::function_ref<bool(unsigned, unsigned)> Comparator) {
+        std::pair<FileID, unsigned> DecomposedRangeLoc =
+            getDecomposedLoc(getSpellingLoc(RangeLoc));
+        // Ensure that we check for FileEntry equivalency to account for
+        // multiple inclusions.
+        if (PointLoc.first != DecomposedRangeLoc.first &&
+            getFileEntryForID(PointLoc.first) !=
+                getFileEntryForID(DecomposedRangeLoc.first))
+          return false;
+        return Comparator(PointLoc.second, DecomposedRangeLoc.second);
+      };
+
+  // The point must be in the same file as the starting and end location.
+  // The point's offset must be >= than the starting location's offset and
+  // <= than the ending location's offset.
+  return isOrderedInSameFile(Start,
+                             [](unsigned PointOffset, unsigned StartLocOffset) {
+                               return PointOffset >= StartLocOffset;
+                             }) &&
+         isOrderedInSameFile(End,
+                             [](unsigned PointOffset, unsigned EndLocOffset) {
+                               return PointOffset <= EndLocOffset;
+                             });
+}
+
 /// Determines the order of 2 source locations in the translation unit.
 ///
 /// \returns true if LHS source location comes before RHS, false otherwise.
 bool SourceManager::isBeforeInTranslationUnit(SourceLocation LHS,
                                               SourceLocation RHS) const {
   assert(LHS.isValid() && RHS.isValid() && "Passed invalid source location!");
   if (LHS == RHS)
     return false;

unittests/Basic/SourceManagerTest.cpp

TEST_F(SourceManagerTest, isBeforeInTranslationUnitWithMacroInInclude) {
   // MACRO_IN_INCLUDE definition of the included file.
   EXPECT_TRUE(SourceMgr.isBeforeInTranslationUnit(Macros[3].Loc, Macros[4].Loc));
 
   // The INC2 expansion in #include M(INC2) comes before the second
   // MACRO_IN_INCLUDE definition of the included file.
   EXPECT_TRUE(SourceMgr.isBeforeInTranslationUnit(Macros[10].Loc, Macros[11].Loc));
 }
 
+TEST_F(SourceManagerTest, isPointWithin) {
+  const char *header = "int x;";
+
+  const char *main = "#include </test-header.h>\n"
+                     "#include </test-header.h>\n";
+
+  std::unique_ptr<llvm::MemoryBuffer> HeaderBuf =
+      llvm::MemoryBuffer::getMemBuffer(header);
+  std::unique_ptr<llvm::MemoryBuffer> MainBuf =
+      llvm::MemoryBuffer::getMemBuffer(main);
+  SourceMgr.setMainFileID(SourceMgr.createFileID(std::move(MainBuf)));
+
+  const FileEntry *headerFile =
+      FileMgr.getVirtualFile("/test-header.h", HeaderBuf->getBufferSize(), 0);
+  SourceMgr.overrideFileContents(headerFile, std::move(HeaderBuf));
+
+  TrivialModuleLoader ModLoader;
+  MemoryBufferCache PCMCache;
+  HeaderSearch HeaderInfo(std::make_shared<HeaderSearchOptions>(), SourceMgr,
+                          Diags, LangOpts, &*Target);
+  Preprocessor PP(std::make_shared<PreprocessorOptions>(), Diags, LangOpts,
+                  SourceMgr, PCMCache, HeaderInfo, ModLoader,
+                  /*IILookup =*/nullptr,
+                  /*OwnsHeaderSearch =*/false);
+  PP.Initialize(*Target);
+
+  PP.EnterMainSourceFile();
+
+  std::vector<Token> Tokens;
+  while (1) {
+    Token tok;
+    PP.Lex(tok);
+    if (tok.is(tok::eof))
+      break;
+    Tokens.push_back(tok);
+  }
+
+  // Make sure we got the tokens that we expected.
+  ASSERT_EQ(6U, Tokens.size());
+
+  // Make sure the FileIDs are different.
+  SourceLocation L1 = Tokens[0].getLocation();
+  SourceLocation L2 = Tokens[3].getLocation();
+  ASSERT_NE(L1, L2);
+
+  // The location of the 'int' in the first inclusion is lexically within the
+  // range of the 'int' in the second inclusion.
+  ASSERT_TRUE(SourceMgr.isPointWithin(L1, L2, L2));
+  // The location of the 'int' in the second inclusion is lexically within the
+  // range of the 'int' in the first inclusion.
+  ASSERT_TRUE(SourceMgr.isPointWithin(L2, L1, L1));
+  // The location of the 'x' in the second inclusion is lexically within the
+  // range of the 'int' in the first inclusion and ';' in the second inclusion.
+  ASSERT_TRUE(SourceMgr.isPointWithin(Tokens[4].getLocation(), L1,
+                                      Tokens[5].getLocation()));
+  // The location of the 'int' in the second inclusion is lexically outside of
+  // the 'x' in the first inclusion and ';' in the second inclusion.
+  ASSERT_FALSE(SourceMgr.isPointWithin(Tokens[3].getLocation(),
+                                       Tokens[1].getLocation(),
+                                       Tokens[5].getLocation()));
+}
+
+TEST_F(SourceManagerTest, isPointWithinMacroSpelling) {
+  const char *main = "#define MYMACRO int x;\n"
+                     "MYMACRO\n"
+                     "MYMACRO\n";
+
+  std::unique_ptr<llvm::MemoryBuffer> MainBuf =
+      llvm::MemoryBuffer::getMemBuffer(main);
+  SourceMgr.setMainFileID(SourceMgr.createFileID(std::move(MainBuf)));
+
+  TrivialModuleLoader ModLoader;
+  MemoryBufferCache PCMCache;
+  HeaderSearch HeaderInfo(std::make_shared<HeaderSearchOptions>(), SourceMgr,
+                          Diags, LangOpts, &*Target);
+  Preprocessor PP(std::make_shared<PreprocessorOptions>(), Diags, LangOpts,
+                  SourceMgr, PCMCache, HeaderInfo, ModLoader,
+                  /*IILookup =*/nullptr,
+                  /*OwnsHeaderSearch =*/false);
+  PP.Initialize(*Target);
+
+  PP.EnterMainSourceFile();
+
+  std::vector<Token> Tokens;
+  while (1) {
+    Token tok;
+    PP.Lex(tok);
+    if (tok.is(tok::eof))
+      break;
+    Tokens.push_back(tok);
+  }
+
+  // Make sure we got the tokens that we expected.
+  ASSERT_EQ(6U, Tokens.size());
+
+  // Make sure the FileIDs are different.
+  SourceLocation L1 = Tokens[0].getLocation();
+  SourceLocation L2 = Tokens[3].getLocation();
+  ASSERT_NE(L1, L2);
+
+  // The location of the 'int' in the first expansion is lexically within the
+  // range of the 'int' in the second expansion.
+  ASSERT_TRUE(SourceMgr.isPointWithin(L1, L2, L2));
+  // The location of the 'int' in the second expansion is lexically within the
+  // range of the 'int' in the first expansion.
+  ASSERT_TRUE(SourceMgr.isPointWithin(L2, L1, L1));
+  // The location of the 'x' in the second expansion is lexically within the
+  // range of the 'int' in the first expansion and ';' in the second expansion.
+  ASSERT_TRUE(SourceMgr.isPointWithin(Tokens[4].getLocation(), L1,
+                                      Tokens[5].getLocation()));
+  // The location of the 'int' in the second expansion is lexically outside of
+  // the 'x' in the first expansion and ';' in the second expansion.
+  ASSERT_FALSE(SourceMgr.isPointWithin(Tokens[3].getLocation(),
+                                       Tokens[1].getLocation(),
+                                       Tokens[5].getLocation()));
+}
+
 #endif
 
 } // anonymous namespace