Factor out a functionality from `isBeforeInTranslationUnit`

[xazax.hun]

Summary

Right now source locations from different translation units can not be compared.
This is a problem for an upcoming feature in the Static Analyzer, the cross translation unit support (https://reviews.llvm.org/D30691).

It would be great to be able to sort the source locations. To achieve this I factored out some code from isBeforeInTranslationUnit to be able to determine whether to source locations are from the same translation unit. Note that, in our use-case, these source locations are imported and from the same source manager.

[xazax.hun]

Note that, it is not easy to add a test case for this patch without the https://reviews.llvm.org/D30691 being accepted.

[joerg]

I don't think it is a good idea to make this function non-transitive.

[xazax.hun]

In D34506#787971, @joerg wrote:

I don't think it is a good idea to make this function non-transitive.

I think this is a good point. However, I am not entirely sure that it is transitive right now. Check the "Both are in built-in buffers, but from different files" case, which is similar to the separate TU case.
But I will look if I can come up with an alternative solution.

[akyrtzi]

Comparing SourceLocations from different translation units is not meaningful and my concern is that treating source locations like this can very easily lead to errors where by mistake the code is resolving a SourceLocation with the wrong translation unit and not the translation unit that it came from.

If you intend to sort source locations across translation units I think you should use an abstraction that includes the source location _and_ the ASTContext or ASTUnit (or something to identify the translation unit) that the source location came from, and use that for sorting (by checking whether the TU are the same, and if not sort appropriately with the TUs, before sorting the SourceLocations).
That way you don't need to 'allow' comparing source locations from different TUs, which IMO is a good sanity check to make sure the code did not mix-up the source locations by accident.

[akyrtzi]

FullSourceLoc could be useful, it wraps the SourceManager that the SourceLocation come from.

[xazax.hun]

In D34506#791089, @akyrtzi wrote:

Comparing SourceLocations from different translation units is not meaningful and my concern is that treating source locations like this can very easily lead to errors where by mistake the code is resolving a SourceLocation with the wrong translation unit and not the translation unit that it came from.

If you intend to sort source locations across translation units I think you should use an abstraction that includes the source location _and_ the ASTContext or ASTUnit (or something to identify the translation unit) that the source location came from, and use that for sorting (by checking whether the TU are the same, and if not sort appropriately with the TUs, before sorting the SourceLocations).
That way you don't need to 'allow' comparing source locations from different TUs, which IMO is a good sanity check to make sure the code did not mix-up the source locations by accident.

Thank you for the suggestions!
The use-case is to make the analyzer deterministic when reporting the diagnostics. Unfortunately, we are already using FullSourceLocs, and it does not help, because the imported AST (using the ASTImporter) has imported source locations that are using the same source manager as the original AST. But I will look into some workaround.

[xazax.hun]

• New approach to solve the original problem

[xazax.hun]

I created a new public API that is using a piece of code that was factored out from isBeforeInTranslationUnit. Using this new function it is possible to implement proper comparison of source locations within the Static Analyzer. What do you think?

[akyrtzi]

I'd prefer to avoid including whitespace-only changes (there are a couple of lines in the diff with only whitespace change), otherwise LGTM!

[xazax.hun]

• Removed the whitespace changes
• Factored out one more condition

[xazax.hun]

In D34506#792313, @akyrtzi wrote:

I'd prefer to avoid including whitespace-only changes (there are a couple of lines in the diff with only whitespace change), otherwise LGTM!

Great, thank you! If no one has objections I will commit this tomorrow.

cfe/trunk/include/clang/Basic/SourceManager.h

public:
   /// where 'foo' was expanded into.
   SourceLocation getMacroArgExpandedLocation(SourceLocation Loc) const;
 
   /// \brief Determines the order of 2 source locations in the translation unit.
   ///
   /// \returns true if LHS source location comes before RHS, false otherwise.
   bool isBeforeInTranslationUnit(SourceLocation LHS, SourceLocation RHS) const;
 
+  /// \brief Determines whether the two decomposed source location is in the
+  ///        same translation unit. As a byproduct, it also calculates the order
+  ///        of the source locations in case they are in the same TU.
+  ///
+  /// \returns Pair of bools the first component is true if the two locations
+  ///          are in the same TU. The second bool is true if the first is true
+  ///          and \p LOffs is before \p ROffs.
+  std::pair<bool, bool>
+  isInTheSameTranslationUnit(std::pair<FileID, unsigned> &LOffs,
+                             std::pair<FileID, unsigned> &ROffs) const;
+
   /// \brief Determines the order of 2 source locations in the "source location
   /// address space".
   bool isBeforeInSLocAddrSpace(SourceLocation LHS, SourceLocation RHS) const {
     return isBeforeInSLocAddrSpace(LHS, RHS.getOffset());
   }
 
   /// \brief Determines the order of a source location and a source location
   /// offset in the "source location address space".

cfe/trunk/lib/Basic/SourceManager.cpp

bool SourceManager::isBeforeInTranslationUnit(SourceLocation LHS,
   std::pair<FileID, unsigned> ROffs = getDecomposedLoc(RHS);
 
   // getDecomposedLoc may have failed to return a valid FileID because, e.g. it
   // is a serialized one referring to a file that was removed after we loaded
   // the PCH.
   if (LOffs.first.isInvalid() || ROffs.first.isInvalid())
     return LOffs.first.isInvalid() && !ROffs.first.isInvalid();
 
+  std::pair<bool, bool> InSameTU = isInTheSameTranslationUnit(LOffs, ROffs);
+  if (InSameTU.first)
+    return InSameTU.second;
+
+  // If we arrived here, the location is either in a built-ins buffer or
+  // associated with global inline asm. PR5662 and PR22576 are examples.
+
+  StringRef LB = getBuffer(LOffs.first)->getBufferIdentifier();
+  StringRef RB = getBuffer(ROffs.first)->getBufferIdentifier();
+  bool LIsBuiltins = LB == "<built-in>";
+  bool RIsBuiltins = RB == "<built-in>";
+  // Sort built-in before non-built-in.
+  if (LIsBuiltins || RIsBuiltins) {
+    if (LIsBuiltins != RIsBuiltins)
+      return LIsBuiltins;
+    // Both are in built-in buffers, but from different files. We just claim that
+    // lower IDs come first.
+    return LOffs.first < ROffs.first;
+  }
+  bool LIsAsm = LB == "<inline asm>";
+  bool RIsAsm = RB == "<inline asm>";
+  // Sort assembler after built-ins, but before the rest.
+  if (LIsAsm || RIsAsm) {
+    if (LIsAsm != RIsAsm)
+      return RIsAsm;
+    assert(LOffs.first == ROffs.first);
+    return false;
+  }
+  bool LIsScratch = LB == "<scratch space>";
+  bool RIsScratch = RB == "<scratch space>";
+  // Sort scratch after inline asm, but before the rest.
+  if (LIsScratch || RIsScratch) {
+    if (LIsScratch != RIsScratch)
+      return LIsScratch;
+    return LOffs.second < ROffs.second;
+  }
+  llvm_unreachable("Unsortable locations found");
+}
+
+std::pair<bool, bool> SourceManager::isInTheSameTranslationUnit(
+    std::pair<FileID, unsigned> &LOffs,
+    std::pair<FileID, unsigned> &ROffs) const {
   // If the source locations are in the same file, just compare offsets.
   if (LOffs.first == ROffs.first)
-    return LOffs.second < ROffs.second;
+    return std::make_pair(true, LOffs.second < ROffs.second);
 
   // If we are comparing a source location with multiple locations in the same
   // file, we get a big win by caching the result.
   InBeforeInTUCacheEntry &IsBeforeInTUCache =
     getInBeforeInTUCache(LOffs.first, ROffs.first);
 
   // 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);
+    return std::make_pair(
+        true, 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,
                           /*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.
std::pair<bool, bool> SourceManager::isInTheSameTranslationUnit(
   }
   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.
   if (LOffs.first == ROffs.first) {
     IsBeforeInTUCache.setCommonLoc(LOffs.first, LOffs.second, ROffs.second);
-    return IsBeforeInTUCache.getCachedResult(LOffs.second, ROffs.second);
+    return std::make_pair(
+        true, IsBeforeInTUCache.getCachedResult(LOffs.second, ROffs.second));
   }
-
-  // If we arrived here, the location is either in a built-ins buffer or
-  // associated with global inline asm. PR5662 and PR22576 are examples.
-
   // Clear the lookup cache, it depends on a common location.
   IsBeforeInTUCache.clear();
-  StringRef LB = getBuffer(LOffs.first)->getBufferIdentifier();
-  StringRef RB = getBuffer(ROffs.first)->getBufferIdentifier();
-  bool LIsBuiltins = LB == "<built-in>";
-  bool RIsBuiltins = RB == "<built-in>";
-  // Sort built-in before non-built-in.
-  if (LIsBuiltins || RIsBuiltins) {
-    if (LIsBuiltins != RIsBuiltins)
-      return LIsBuiltins;
-    // Both are in built-in buffers, but from different files. We just claim that
-    // lower IDs come first.
-    return LOffs.first < ROffs.first;
-  }
-  bool LIsAsm = LB == "<inline asm>";
-  bool RIsAsm = RB == "<inline asm>";
-  // Sort assembler after built-ins, but before the rest.
-  if (LIsAsm || RIsAsm) {
-    if (LIsAsm != RIsAsm)
-      return RIsAsm;
-    assert(LOffs.first == ROffs.first);
-    return false;
-  }
-  bool LIsScratch = LB == "<scratch space>";
-  bool RIsScratch = RB == "<scratch space>";
-  // Sort scratch after inline asm, but before the rest.
-  if (LIsScratch || RIsScratch) {
-    if (LIsScratch != RIsScratch)
-      return LIsScratch;
-    return LOffs.second < ROffs.second;
-  }
-  llvm_unreachable("Unsortable locations found");
+  return std::make_pair(false, false);
 }
 
 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() << LocalSLocEntryTable.size() << " local SLocEntry's allocated ("
                << llvm::capacity_in_bytes(LocalSLocEntryTable)