[FileCheck] Fix --dump-input annotation sort per input line

[jdenny]

Summary

Without this patch, --dump-input annotations on a single input line
are sorted by the associated directive's check-file line. That seemed
fine because that's often identical to the order in which FileCheck
looks for matches for those directives.

The first problem is that an --implicit-check-not pattern has no
check-file line. The logical equivalent is sorting in command-line
order, but that's not implemented.

The second problem is that, unlike a directive, an
--implicit-check-not pattern applies at many points, between many
different pairs of directives. However, sorting in command-line order
gathers all its associated diagnostics together at one point in an
input line's list of annotations.

In general, it seems to be easier to understand FileCheck's logic when
annotations on a single input line are sorted in the order FileCheck
produced the associated diagnostics, so this patch makes that change.
As documented in the patch, the annotation sort order is also
especially relevant to CHECK-LABEL, CHECK-NOT, and CHECK-DAG, so
this patch updates or extends tests to check the sort makes sense for
them. (However, the sort for CHECK-DAG annotations should not
actually be altered by this patch.)

[thopre]

llvm/test/FileCheck/dump-input-annotations.txt

586–600

With 3 CHECK directives, I would expect 4 blocks of implicit checks being tested:

1. - before directive 1
2. - between directive 1 and directive 2
3. - between directive 2 and directive 3
4. - after directive 3

Unless I misunderstood, I would expect directive #3 to fail, i.e. "again" is found between "wor" and '!'. However the implicit check that fail is shown after the third CHECK directive.

[jdenny]

llvm/test/FileCheck/dump-input-annotations.txt

586–600

After applying this patch, the annotations per input line are listed in the order FileCheck produces them (that is, temporal order). First, FileCheck matches check:1 (the first CHECK directive), as show in the annotation on test file line 588. Then...

With 3 CHECK directives, I would expect 4 blocks of implicit checks being tested:

• before directive 1

... FileCheck searches for the implicit patterns here. However, here is the empty string before "hello", so the search range for each implicit pattern is just an "X", as show in the annotations on test file lines 589-591.

Next, FileCheck matches check:2, as shown on test file line 592, and then...

• between directive 1 and directive 2

... FileCheck searches for the implicit patterns here, as shown in the annotations on test file lines 593-595.

Next, FileCheck matches check:3, as shown on test file line 596, and then...

• between directive 2 and directive 3

... FileCheck searches for the implicit patterns here, as shown in the annotations on test file lines 597-599. The third implicit pattern matches, and that's an error, so FileCheck terminates.

Thus, FileCheck never tries to match EOF, and...

• after directive 3

... FileCheck never tries to match the implicit patterns here.

Unless I misunderstood, I would expect directive #3 to fail, i.e. "again" is found between "wor" and '!'.

That's what happened.

However the implicit check that fail is shown after the third CHECK directive.

Because FileCheck doesn't know where to look for the implicit patterns until after matching the next CHECK directive.

[thopre]

LGTM. Thanks for this, I haven't used feature so far but that seems very useful with this patch.

llvm/test/FileCheck/dump-input-annotations.txt

586–600

Ah yes of course, it all makes sense. Thanks!

[jdenny]

In D77607#1970655, @thopre wrote:

LGTM. Thanks for this, I haven't used feature so far but that seems very useful with this patch.

Cool. Thanks for the review.

(By the way, some time ago I started developing patches to show variable captures as annotations on input lines. I've found that really helpful when debugging. They need more work, such as adding support for numeric variables. I'll try to get those into phabricator soon.)

[thopre]

In D77607#1970773, @jdenny wrote:

In D77607#1970655, @thopre wrote:

LGTM. Thanks for this, I haven't used feature so far but that seems very useful with this patch.

Cool. Thanks for the review.

(By the way, some time ago I started developing patches to show variable captures as annotations on input lines. I've found that really helpful when debugging. They need more work, such as adding support for numeric variables. I'll try to get those into phabricator soon.)

So you mean it show the value when it's captured as opposed to when it's used like what -vv shows? Or is there more to it?

[jdenny]

In D77607#1971405, @thopre wrote:

In D77607#1970773, @jdenny wrote:

(By the way, some time ago I started developing patches to show variable captures as annotations on input lines. I've found that really helpful when debugging. They need more work, such as adding support for numeric variables. I'll try to get those into phabricator soon.)

So you mean it show the value when it's captured as opposed to when it's used like what -vv shows? Or is there more to it?

As you say, substitutions/uses are printed already as diagnostics. One of my patches adds them to -dump-input annotations, where I find them to be useful too.

Another patch adds the definitions/captures both to the diagnostics and to -dump-input annotations.

(Of course, verbose diagnostics are suppressed when -dump-input is specified, so you won't get tons of this stuff twice.)

Finally, upon a failed match, another patch lists variables that the pattern is intended to capture. Someone pointed out once that, if you write a capturing expression without meaning to because the syntax of the language you're matching happens to look like FileCheck capturing syntax, it can be very confusing when the match fails. This patch should help.

llvm/test/FileCheck/dump-input-annotations.txt

 ; EMP:        <<<<<<
 ; EMP-NEXT:            1: hello
 ; EMP-V-NEXT: check:1     ^~~~~
 ; EMP-NEXT:            2:
 ; EMP-V-NEXT: empty:2     ^
 ; EMP-NEXT:            3: world
 ; EMP-NEXT:   empty:3     X~~~~ error: no match found
 ; EMP-NEXT:            4: label
-; EMP-NEXT:   empty:3     ~~~~~
 ; EMP-V-NEXT: label:4     ^~~~~
+; EMP-NEXT:   empty:3     ~~~~~
 ; EMP-NEXT:   >>>>>>
 ; EMP-NOT:    {{.}}
 
 ; Wrong-line match.
 
 ; RUN: echo 'hello' > %t.in
 ; RUN: echo 'world' >> %t.in
 

 
 ; NOT2:         <<<<<<
 ; NOT2-NEXT:             1: hello
 ; NOT2-VV-NEXT: not:1       X~~~~
 ; NOT2-NEXT:             2: world
 ; NOT2-VV-NEXT: not:1       ~~~~~
 ; NOT2-NEXT:    not:2       !~~~~ error: no match expected
 ; NOT2-NEXT:             3: again
-; NOT2-VV-NEXT: not:1       ~~
 ; NOT2-V-NEXT:  check:3       ^~~
+; NOT2-VV-NEXT: not:1       ~~
 ; NOT2-NEXT:    >>>>>>
 ; NOT2-NOT:     {{.}}
 
 ;--------------------------------------------------
 ; CHECK-DAG (also: matches in different order than directives, discarded match)
 ;--------------------------------------------------
 
 ; Good match, discarded match plus good match, and no match.

 ; DAG-VQ-NEXT: dag:3       ^~~
 ; DAG-VV-NEXT: dag:3'1     ^~~
 ; DAG-Q-NEXT:  dag:4       X~~ error: no match found
 ; DAG-VQ-NEXT: dag:4       X~~ error: no match found
 ; DAG-VV-NEXT: dag:4'1     X~~ error: no match found
 ; DAG-NEXT:    >>>>>>
 ; DAG-NOT:     {{.}}
 
+; Check sorting of annotations when the order of diagnostics across an input
+; line is different than the order of the associated directives in the check
+; file.  Try cases when diagnostics' input ranges overlap but are not
+; identical to check how that affects sorting.
+
+; RUN: echo 'abc def abc def' > %t.in
+
+; RUN: echo 'CHECK-DAG: def' > %t.chk
+; RUN: echo 'CHECK-DAG: bc' >> %t.chk
+; RUN: echo 'CHECK-DAG: abc' >> %t.chk
+; RUN: echo 'CHECK-DAG: de' >> %t.chk
+; RUN: echo 'CHECK-DAG: def' >> %t.chk
+
+; RUN: %ProtectFileCheckOutput \
+; RUN: not FileCheck -dump-input=always -input-file %t.in %t.chk 2>&1 \
+; RUN: | FileCheck -match-full-lines %s -check-prefixes=DAG1L,DAG1L-Q \
+; RUN:             -implicit-check-not='remark:'
+; RUN: %ProtectFileCheckOutput \
+; RUN: not FileCheck -dump-input=always -input-file %t.in %t.chk -v 2>&1 \
+; RUN: | FileCheck -match-full-lines %s -check-prefixes=DAG1L,DAG1L-V,DAG1L-VQ \
+; RUN:             -implicit-check-not='remark:'
+; RUN: %ProtectFileCheckOutput \
+; RUN: not FileCheck -dump-input=always -input-file %t.in %t.chk -vv 2>&1 \
+; RUN: | FileCheck -match-full-lines %s -check-prefixes=DAG1L,DAG1L-V,DAG1L-VV \
+; RUN:             -implicit-check-not='remark:'
+
+; Verbose diagnostics are suppressed but not errors.
+; DAG1L:{{.*}}error:{{.*}}
+
+;         DAG1L:<<<<<<
+;    DAG1L-NEXT:         1: abc def abc def
+;  DAG1L-V-NEXT:dag:1           ^~~
+;  DAG1L-V-NEXT:dag:2        ^~
+; DAG1L-VV-NEXT:dag:3'0     !~~             discard: overlaps earlier match
+; DAG1L-VQ-NEXT:dag:3               ^~~
+; DAG1L-VV-NEXT:dag:3'1             ^~~
+; DAG1L-VV-NEXT:dag:4'0         !~          discard: overlaps earlier match
+; DAG1L-VQ-NEXT:dag:4                   ^~
+; DAG1L-VV-NEXT:dag:4'1                 ^~
+; DAG1L-VV-NEXT:dag:5'0         !~~         discard: overlaps earlier match
+; DAG1L-VV-NEXT:dag:5'1                 !~~ discard: overlaps earlier match
+;  DAG1L-Q-NEXT:dag:5                     X error: no match found
+; DAG1L-VQ-NEXT:dag:5                     X error: no match found
+; DAG1L-VV-NEXT:dag:5'2                   X error: no match found
+;    DAG1L-NEXT:>>>>>>
+;     DAG1L-NOT:{{.}}
+
 ;--------------------------------------------------
 ; CHECK-LABEL
 ;
 ; FIXME: Labels sometimes produce redundant diagnostics for good matches.
 ; That bug is independent of but affects -dump-input.
 ;--------------------------------------------------
 
 ; Good match and no match.

 ; RUN:               --implicit-check-not='again' \
 ; RUN: | FileCheck -match-full-lines %s \
 ; RUN:             -check-prefixes=IMPNOT,IMPNOT-V,IMPNOT-VV \
 ; RUN:             -implicit-check-not='remark:'
 
 ; Verbose diagnostics are suppressed but not errors.
 ; IMPNOT:{{.*}}error:{{.*}}
 
-; FIXME: All occurrences of imp1, imp2, and imp3 are sorting after the first
-; directive.  They should instead be sorted by when they execute.
-
 ;         IMPNOT:<<<<<<
 ;    IMPNOT-NEXT:          1: hello world again!
 ;  IMPNOT-V-NEXT:check:1      ^~~
 ; IMPNOT-VV-NEXT:not:imp1     X
 ; IMPNOT-VV-NEXT:not:imp2     X
 ; IMPNOT-VV-NEXT:not:imp3     X
+;  IMPNOT-V-NEXT:check:2            ^~~
 ; IMPNOT-VV-NEXT:not:imp1        X~~
 ; IMPNOT-VV-NEXT:not:imp2        X~~
 ; IMPNOT-VV-NEXT:not:imp3        X~~
+;  IMPNOT-V-NEXT:check:3                       ^
 ; IMPNOT-VV-NEXT:not:imp1              X~~~~~~~
 ; IMPNOT-VV-NEXT:not:imp2              X~~~~~~~
 ;    IMPNOT-NEXT:not:imp3                 !~~~~  error: no match expected
-;  IMPNOT-V-NEXT:check:2            ^~~
-;  IMPNOT-V-NEXT:check:3                       ^
 ;    IMPNOT-NEXT:>>>>>>
 ;     IMPNOT-NOT:{{.}}

llvm/utils/FileCheck/FileCheck.cpp

static void DumpInputAnnotationHelp(raw_ostream &OS) {
   OS << ", ";
   WithColor(OS, raw_ostream::CYAN, true, true) << "unmatched input";
   OS << "\n\n"
      << "If you are not seeing color above or in input dumps, try: -color\n";
 }
 
 /// An annotation for a single input line.
 struct InputAnnotation {
-  /// The check file line (one-origin indexing) where the directive that
-  /// produced this annotation is located.
-  unsigned CheckLine;
-  /// The index of the match result for this check.
-  unsigned CheckDiagIndex;
+  /// The index of the match result across all checks
+  unsigned DiagIndex;
   /// The label for this annotation.
   std::string Label;
   /// What input line (one-origin indexing) this annotation marks.  This might
   /// be different from the starting line of the original diagnostic if this is
   /// a non-initial fragment of a diagnostic that has been broken across
   /// multiple lines.
   unsigned InputLine;
-  /// The column range (one-origin indexing, open end) in which to to mark the
+  /// The column range (one-origin indexing, open end) in which to mark the
   /// input line.  If InputEndCol is UINT_MAX, treat it as the last column
   /// before the newline.
   unsigned InputStartCol, InputEndCol;
   /// The marker to use.
   MarkerStyle Marker;
   /// Whether this annotation represents a good match for an expected pattern.
   bool FoundAndExpectedMatch;
 };

 }
 
 static void
 BuildInputAnnotations(const SourceMgr &SM, unsigned CheckFileBufferID,
                       const std::pair<unsigned, unsigned> &ImpPatBufferIDRange,
                       const std::vector<FileCheckDiag> &Diags,
                       std::vector<InputAnnotation> &Annotations,
                       unsigned &LabelWidth) {
+  // How many diagnostics have we seen so far?
+  unsigned DiagCount = 0;
   // How many diagnostics has the current check seen so far?
   unsigned CheckDiagCount = 0;
   // What's the widest label?
   LabelWidth = 0;
   for (auto DiagItr = Diags.begin(), DiagEnd = Diags.end(); DiagItr != DiagEnd;
        ++DiagItr) {
     InputAnnotation A;
+    A.DiagIndex = DiagCount++;
 
     // Build label, which uniquely identifies this check result.
     unsigned CheckBufferID = SM.FindBufferContainingLoc(DiagItr->CheckLoc);
     auto CheckLineAndCol =
         SM.getLineAndColumn(DiagItr->CheckLoc, CheckBufferID);
-    A.CheckLine = CheckLineAndCol.first;
     llvm::raw_string_ostream Label(A.Label);
     Label << GetCheckTypeAbbreviation(DiagItr->CheckTy) << ":";
     if (CheckBufferID == CheckFileBufferID)
       Label << CheckLineAndCol.first;
     else if (ImpPatBufferIDRange.first <= CheckBufferID &&
              CheckBufferID < ImpPatBufferIDRange.second)
       Label << "imp" << (CheckBufferID - ImpPatBufferIDRange.first + 1);
     else
       llvm_unreachable("expected diagnostic's check location to be either in "
                        "the check file or for an implicit pattern");
-    A.CheckDiagIndex = UINT_MAX;
+    unsigned CheckDiagIndex = UINT_MAX;
     auto DiagNext = std::next(DiagItr);
     if (DiagNext != DiagEnd && DiagItr->CheckTy == DiagNext->CheckTy &&
         DiagItr->CheckLoc == DiagNext->CheckLoc)
-      A.CheckDiagIndex = CheckDiagCount++;
+      CheckDiagIndex = CheckDiagCount++;
     else if (CheckDiagCount) {
-      A.CheckDiagIndex = CheckDiagCount;
+      CheckDiagIndex = CheckDiagCount;
       CheckDiagCount = 0;
     }
-    if (A.CheckDiagIndex != UINT_MAX)
-      Label << "'" << A.CheckDiagIndex;
-    else
-      A.CheckDiagIndex = 0;
+    if (CheckDiagIndex != UINT_MAX)
+      Label << "'" << CheckDiagIndex;
     Label.flush();
     LabelWidth = std::max((std::string::size_type)LabelWidth, A.Label.size());
 
     A.Marker = GetMarker(DiagItr->MatchTy);
     A.FoundAndExpectedMatch =
         DiagItr->MatchTy == FileCheckDiag::MatchFoundAndExpected;
 
     // Compute the mark location, and break annotation into multiple
if (DiagItr->InputStartLine == DiagItr->InputEndLine) {
       Annotations.push_back(A);
       for (unsigned L = DiagItr->InputStartLine + 1, E = DiagItr->InputEndLine;
            L <= E; ++L) {
         // If a range ends before the first column on a line, then it has no
         // characters on that line, so there's nothing to render.
         if (DiagItr->InputEndCol == 1 && L == E)
           break;
         InputAnnotation B;
-        B.CheckLine = A.CheckLine;
-        B.CheckDiagIndex = A.CheckDiagIndex;
+        B.DiagIndex = A.DiagIndex;
         B.Label = A.Label;
         B.InputLine = L;
         B.Marker = A.Marker;
         B.Marker.Lead = '~';
         B.Marker.Note = "";
         B.InputStartCol = 1;
         if (L != E)
           B.InputEndCol = UINT_MAX;
         else
           B.InputEndCol = DiagItr->InputEndCol;
         B.FoundAndExpectedMatch = A.FoundAndExpectedMatch;
         Annotations.push_back(B);
       }
     }
   }
 }
 
 static void DumpAnnotatedInput(raw_ostream &OS, const FileCheckRequest &Req,
                                StringRef InputFileText,
                                std::vector<InputAnnotation> &Annotations,
                                unsigned LabelWidth) {
   OS << "Full input was:\n<<<<<<\n";
 
   // Sort annotations.
-  //
-  // First, sort in the order of input lines to make it easier to find relevant
-  // annotations while iterating input lines in the implementation below.
-  // FileCheck diagnostics are not always reported and recorded in the order of
-  // input lines due to, for example, CHECK-DAG and CHECK-NOT.
-  //
-  // Second, for annotations for the same input line, sort in the order of the
-  // FileCheck directive's line in the check file (where there's at most one
-  // directive per line) and then by the index of the match result for that
-  // directive.  The rationale of this choice is that, for any input line, this
-  // sort establishes a total order of annotations that, with respect to match
-  // results, is consistent across multiple lines, thus making match results
-  // easier to track from one line to the next when they span multiple lines.
   std::sort(Annotations.begin(), Annotations.end(),
             [](const InputAnnotation &A, const InputAnnotation &B) {
+              // 1. Sort annotations in the order of the input lines.
+              //
+              // This makes it easier to find relevant annotations while
+              // iterating input lines in the implementation below.  FileCheck
+              // does not always produce diagnostics in the order of input
+              // lines due to, for example, CHECK-DAG and CHECK-NOT.
               if (A.InputLine != B.InputLine)
                 return A.InputLine < B.InputLine;
-              if (A.CheckLine != B.CheckLine)
-                return A.CheckLine < B.CheckLine;
-              // FIXME: Sometimes CHECK-LABEL reports its match twice with
-              // other diagnostics in between, and then diag index incrementing
-              // fails to work properly, and then this assert fails.  We should
-              // suppress one of those diagnostics or do a better job of
-              // computing this index.  For now, we just produce a redundant
-              // CHECK-LABEL annotation.
-              // assert(A.CheckDiagIndex != B.CheckDiagIndex &&
-              //        "expected diagnostic indices to be unique within a "
-              //        " check line");
-              return A.CheckDiagIndex < B.CheckDiagIndex;
+              // 2. Sort annotations in the temporal order FileCheck produced
+              // their associated diagnostics.
+              //
+              // This sort offers several benefits:
+              //
+              // A. On a single input line, the order of annotations reflects
+              //    the FileCheck logic for processing directives/patterns.
+              //    This can be helpful in understanding cases in which the
+              //    order of the associated directives/patterns in the check
+              //    file or on the command line either (i) does not match the
+              //    temporal order in which FileCheck looks for matches for the
+              //    directives/patterns (due to, for example, CHECK-LABEL,
+              //    CHECK-NOT, or `--implicit-check-not`) or (ii) does match
+              //    that order but does not match the order of those
+              //    diagnostics along an input line (due to, for example,
+              //    CHECK-DAG).
+              //
+              //    On the other hand, because our presentation format presents
+              //    input lines in order, there's no clear way to offer the
+              //    same benefit across input lines.  For consistency, it might
+              //    then seem worthwhile to have annotations on a single line
+              //    also sorted in input order (that is, by input column).
+              //    However, in practice, this appears to be more confusing
+              //    than helpful.  Perhaps it's intuitive to expect annotations
+              //    to be listed in the temporal order in which they were
+              //    produced except in cases the presentation format obviously
+              //    and inherently cannot support it (that is, across input
+              //    lines).
+              //
+              // B. When diagnostics' annotations are split among multiple
+              //    input lines, the user must track them from one input line
+              //    to the next.  One property of the sort chosen here is that
+              //    it facilitates the user in this regard by ensuring the
+              //    following: when comparing any two input lines, a
+              //    diagnostic's annotations are sorted in the same position
+              //    relative to all other diagnostics' annotations.
+              return A.DiagIndex < B.DiagIndex;
             });
 
   // Compute the width of the label column.
   const unsigned char *InputFilePtr = InputFileText.bytes_begin(),
                       *InputFileEnd = InputFileText.bytes_end();
   unsigned LineCount = InputFileText.count('\n');
   if (InputFileEnd[-1] != '\n')
     ++LineCount;