Compare SourceLocations from different TUs by FileID

[gamesh411]

Summary

The comparison of SourceLocations is extended to handle locations from different
translation units, making the comparison based on the corresponding FileID.

[gamesh411]

Hi!

This issue came up during the generation BugReports of BugPaths containing macro-expansions, where the spelling location and expansion locations were in different files.
With this change, we make such SourceLocations comparable by their FileIDs.

[lebedev.ri]

Test?

[Szelethus]

In D59934#1446051, @gamesh411 wrote:

Hi!

This issue came up during the generation BugReports of BugPaths containing macro-expansions, where the spelling location and expansion locations were in different files.
With this change, we make such SourceLocations comparable by their FileIDs.

Do you mean regular macro expansions or the one we're generating in the plist output via -analyzer-config expand-macros=true?

lib/Basic/SourceManager.cpp

1984

We should change this too.

[gamesh411]

In D59934#1446736, @Szelethus wrote:

In D59934#1446051, @gamesh411 wrote:

Hi!

This issue came up during the generation BugReports of BugPaths containing macro-expansions, where the spelling location and expansion locations were in different files.
With this change, we make such SourceLocations comparable by their FileIDs.

Do you mean regular macro expansions or the one we're generating in the plist output via -analyzer-config expand-macros=true?

I have confirmed, that this happens when -analyzer-config expand-macros=true is passed, and no unreachable line is triggered without this analyzer config.

[gamesh411]

Just to have a bit more context, I have the following information from a debug session at the execution point of the unreachable:

(rr) p LHS.dump(*this)
...................../tmux-2.8/compat/tree.h:721:9

(rr) p RHS.dump(*this)
...................../tmux-2.8/arguments.c:56:10

(rr) p LOffs.first
{ID = 1}
(rr) p ROffs.first
{ID = 2826}

(rr) p LB
{static npos = 18446744073709551615, Data = 0xe4f378 "...................../tmux-2.8/cmd-capture-pane.c", Length = 49}
(rr) p RB
{static npos = 18446744073709551615, Data = 0x5ff7a78 "...................../tmux-2.8/arguments.c", Length = 42}

Additionally, the source locations indicate that the following type of macros cause this situation:

// in tree.h
// ...
#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
// ...

// in arguments.c
// ...
return (RB_FIND(args_tree, &args->tree, &entry));
// ...

This example does not even seem to be trivially explainable, as the macro definition is directly accessible from the point of expansion via an include of tree.h.

[gamesh411]

In D59934#1446059, @lebedev.ri wrote:

Test?

Thanks for the remark :) I agree, that there should be at least a unit test asserting the right behaviour. I am working on it.

[Szelethus]

I would still like to learn more about this issue. I am somewhat afraid that the our macro expansion is faulty. Can you provide a stacktrace maybe?

[gamesh411]

In D59934#1449109, @Szelethus wrote:

I would still like to learn more about this issue. I am somewhat afraid that the our macro expansion is faulty. Can you provide a stacktrace maybe?

The stack trace that belongs to the same debug session I mentioned before:

#0  __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:51
#1  0x00007fdcf2121801 in __GI_abort () at abort.c:79
#2  0x00007fdcf589aa40 in llvm::llvm_unreachable_internal (msg=0x7fdcf4a179e5 "Unsortable locations found", 
    file=0x7fdcf4a05f01 "/llvm/tools/clang/lib/Basic/SourceManager.cpp", line=2038)
    at /llvm/lib/Support/ErrorHandling.cpp:221
#3  0x00007fdcf4b81115 in clang::SourceManager::isBeforeInTranslationUnit (this=0xdfefc0, LHS=..., RHS=...)
    at /llvm/tools/clang/lib/Basic/SourceManager.cpp:2038
#4  0x00007fdcef3f4359 in clang::MacroDirective::findDirectiveAtLoc (this=0x1144500, L=..., SM=...)
    at /llvm/tools/clang/lib/Lex/MacroInfo.cpp:207
#5  0x00007fdceb40e086 in getMacroInfoForLocation (PP=..., SM=..., II=0x1135898, Loc=...)
    at /llvm/tools/clang/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp:1115
#6  0x00007fdceb40d596 in getMacroNameAndArgs (ExpanLoc=..., PP=...)
    at /llvm/tools/clang/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp:980
#7  0x00007fdceb40ccf3 in getMacroNameAndPrintExpansion[abi:cxx11]((anonymous namespace)::TokenPrinter&, clang::SourceLocation, clang::Preprocessor const&, (anonymous namespace)::MacroArgMap const&, llvm::SmallPtrSet<clang::IdentifierInfo*, 8u>&) (Printer=..., MacroLoc=..., PP=..., PrevArgs=..., AlreadyProcessedTokens=...)
    at /llvm/tools/clang/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp:859
#8  0x00007fdceb40cb0e in getExpandedMacro (MacroLoc=..., PP=...)
    at /llvm/tools/clang/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp:845
#9  0x00007fdceb40b202 in (anonymous namespace)::PlistPrinter::ReportMacroExpansions (this=0x7ffe244b7ed0, 
    o=..., indent=4)
    at /llvm/tools/clang/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp:344
#10 0x00007fdceb40ab43 in printBugPath (o=..., FM=..., AnOpts=..., PP=..., Path=...)
    at /llvm/tools/clang/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp:479
#11 0x00007fdceb409764 in (anonymous namespace)::PlistDiagnostics::FlushDiagnosticsImpl (this=0xe0c610, 
    Diags=std::vector of length 1, capacity 1 = {...}, filesMade=0x7ffe244b8898)
    at /llvm/tools/clang/lib/StaticAnalyzer/Core/PlistDiagnostics.cpp:583
#12 0x00007fdceb3fc9d9 in clang::ento::PathDiagnosticConsumer::FlushDiagnostics (this=0xe0c610, 
    Files=0x7ffe244b8898)
    at /llvm/tools/clang/lib/StaticAnalyzer/Core/PathDiagnostic.cpp:483
#13 0x00007fdceb25aae9 in clang::ento::AnalysisManager::FlushDiagnostics (this=0xe14c20)
    at /llvm/tools/clang/lib/StaticAnalyzer/Core/AnalysisManager.cpp:59
#14 0x00007fdceb25a98c in clang::ento::AnalysisManager::~AnalysisManager (this=0xe14c20)
    at /llvm/tools/clang/lib/StaticAnalyzer/Core/AnalysisManager.cpp:47
#15 0x00007fdceb25ab3c in clang::ento::AnalysisManager::~AnalysisManager (this=0xe14c20)
    at /llvm/tools/clang/lib/StaticAnalyzer/Core/AnalysisManager.cpp:46
#16 0x00007fdcec72dc9f in std::default_delete<clang::ento::AnalysisManager>::operator() (this=0xe13a48, 
    __ptr=0xe14c20)
    at /usr/bin/../lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/bits/unique_ptr.h:78
#17 0x00007fdcec72eb3c in std::unique_ptr<clang::ento::AnalysisManager, std::default_delete<clang::ento::AnalysisManager> >::reset (this=0xe13a48, __p=0xe14c20)
    at /usr/bin/../lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/bits/unique_ptr.h:376
#18 0x00007fdcec6c4079 in (anonymous namespace)::AnalysisConsumer::HandleTranslationUnit (this=0xe138b0, C=...)
    at /llvm/tools/clang/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp:602
#19 0x00007fdceec204b6 in clang::ParseAST (S=..., PrintStats=false, SkipFunctionBodies=false)
    at /llvm/tools/clang/lib/Parse/ParseAST.cpp:169
#20 0x00007fdcf37b0eb2 in clang::ASTFrontendAction::ExecuteAction (this=0xdeb800)
    at /llvm/tools/clang/lib/Frontend/FrontendAction.cpp:1035
#21 0x00007fdcf37b08e3 in clang::FrontendAction::Execute (this=0xdeb800)
    at /llvm/tools/clang/lib/Frontend/FrontendAction.cpp:934
#22 0x00007fdcf372a2ba in clang::CompilerInstance::ExecuteAction (this=0xde68f0, Act=...)
    at /llvm/tools/clang/lib/Frontend/CompilerInstance.cpp:949
#23 0x00007fdcf33b14bb in clang::ExecuteCompilerInvocation (Clang=0xde68f0)
    at /llvm/tools/clang/lib/FrontendTool/ExecuteCompilerInvocation.cpp:271
#24 0x000000000023f7b4 in cc1_main (Argv=..., 
    Argv0=0x7ffe244bc18a "/clang-build-debug/bin/clang-9", 
    MainAddr=0x2320f0 <GetExecutablePath[abi:cxx11](char const*, bool)>)
    at /llvm/tools/clang/tools/driver/cc1_main.cpp:218
#25 0x000000000023349f in ExecuteCC1Tool (argv=..., Tool=...)
    at /llvm/tools/clang/tools/driver/driver.cpp:309
#26 0x0000000000232864 in main (argc_=339, argv_=0x7ffe244bb0e8)
    at /llvm/tools/clang/tools/driver/driver.cpp:381

I can also confirm that this only comes up when I run the analysis in CTU mode AND with expand-macros=true.

[Szelethus]

Hmm. Is your clang recent enough to contain @bruntib's patch D57892? Is it possible that this patch solves the same issue? With this patch applied, are you able to get a macro expansions from a different TU in the plist output, or does this patch only resolve the regression?

[gamesh411]

In D59934#1449221, @Szelethus wrote:

Hmm. Is your clang recent enough to contain @bruntib's patch D57892? Is it possible that this patch solves the same issue? With this patch applied, are you able to get a macro expansions from a different TU in the plist output, or does this patch only resolve the regression?

This happens even with D57892 applied.

[balazske]

The problem has not necessarily do something with macro expansion. If a function is imported in CTU mode and for any reason source locations inside it are compared against source locations in the ("To") TU these locations are (from SourceManager point of view) in different TUs. But from TU point of view these are in the same TU because the AST import (AST import keeps the original filename and location in the new source location, so the new SourceLocation is in the same TU but different source file).

It looks like that MacroDirective::findDirectiveAtLoc can not give correct result if the change is applied. The isBeforeInTranslationUnit should work (as its name says) only if the locations are in the same TU so I do not like the proposed change. Maybe something other must be changed, macro expansions should be fetched from the original (not imported) TU.

[balazske]

The following ASTImporterTest reproduces the assert:

TEST_P(ASTImporterOptionSpecificTestBase, SourceLocationDifferentTU) {
  TranslationUnitDecl *ToTU = getToTuDecl("void f1();", Lang_CXX11);
  Decl *FromTU = getTuDecl("void f2();", Lang_CXX11, "input.cc");
  auto *ToF1 = FirstDeclMatcher<FunctionDecl>().match(ToTU, functionDecl());
  auto *FromF2 = FirstDeclMatcher<FunctionDecl>().match(FromTU, functionDecl());

  auto *ToF2 = Import(FromF2, Lang_CXX11);

  bool Before1 = ToTU->getASTContext().getSourceManager().isBeforeInTranslationUnit(ToF1->getLocation(), ToF2->getLocation());
  bool Before2 = ToTU->getASTContext().getSourceManager().isBeforeInTranslationUnit(ToF2->getLocation(), ToF1->getLocation());
  EXPECT_NE(Before1, Before2);
}

[balazske]

Is it a better fix to change getMacroInfoForLocation?

static const MacroInfo *getMacroInfoForLocation(const Preprocessor &PP,
                                                const SourceManager &SM,
                                                const IdentifierInfo *II,
                                                SourceLocation Loc) {

  // Can not get macro information for locations not in main TU.
  std::pair<FileID, unsigned> DecMainLoc =
      std::make_pair(SM.getMainFileID(), 0);
  std::pair<FileID, unsigned> DecLoc = SM.getDecomposedLoc(Loc);
  if (!SM.isInTheSameTranslationUnit(DecMainLoc, DecLoc).first)
    return nullptr;
...

[gamesh411]

32f220c5fbe5 is the more sophisticated solution to the problem.

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;
 }
 
 /// 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;
 
bool SourceManager::isBeforeInTranslationUnit(SourceLocation LHS,
   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");
+
+  // If SourceLocations originate from different TUs, but cannot be handled
+  // by one of the previous cases, just compare the FileIDs directly.
+  return LOffs.first < ROffs.first;
 }
 
 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 std::make_pair(true, LOffs.second < ROffs.second);