[FileCheck] Fix -dump-input per-pattern diagnostic indexing

In input dump annotations, `check:2'1` indicates diagnostic 1 for the
`CHECK` directive on check file line 2.  Without this patch,
`-dump-input` computes the diagnostic index with the assumption that
FileCheck *consecutively* produces all diagnostics for the same
pattern.  Already, that can be a false assumption, as in the examples
below.  Moreover, it seems like a brittle assumption as FileCheck
evolves.  Finally, it actually complicates the implementation even if
it makes it slightly more efficient.

This patch avoids that assumption.  Examples below show results after
applying this patch.  Before applying this patch, `'N` is omitted
throughout these examples because the implementation doesn't notice
there's more than one diagnostic per pattern.

First, `CHECK-LABEL` violates the assumption because `CHECK-LABEL`
tries to match twice, and other directives can match in between:

```
$ cat check
CHECK: foobar
CHECK-LABEL: foobar

$ FileCheck -vv check < input |& tail -8
<<<<<<
           1: text
           2: foobar
label:2'0     ^~~~~~
check:1       ^~~~~~
label:2'1           X error: no match found
           3: text
>>>>>>
```

Second, `--implicit-check-not` is obviously processed many times among
other directives:

```
$ cat check
CHECK: foo
CHECK: foo

$ FileCheck -vv -dump-input=always -implicit-check-not=foo \
            check < input |& tail -16
<<<<<<
            1: text
not:imp1'0     X~~~~
            2: foo
check:1        ^~~
not:imp1'1        X
            3: text
not:imp1'1     ~~~~~
            4: foo
check:2        ^~~
not:imp1'2        X
            5: text
not:imp1'2     ~~~~~
            6:
eof:2          ^
>>>>>>
```

Reviewed By: thopre, jhenderson

Differential Revision: https://reviews.llvm.org/D97813

2 files changed, 131 insertions, 68 deletions

diff --git a/llvm/test/FileCheck/dump-input/annotations.txt b/llvm/test/FileCheck/dump-input/annotations.txt
index 0c91190..3118ef6 100644
--- a/llvm/test/FileCheck/dump-input/annotations.txt
+++ b/llvm/test/FileCheck/dump-input/annotations.txt
@@ -504,52 +504,104 @@
 ;--------------------------------------------------
 ; CHECK-LABEL
 ;
-; FIXME: Labels sometimes produce redundant diagnostics for good matches.
-; That bug is independent of but affects -dump-input.
+; Each CHECK-LABEL is processed twice: once before other patterns in the
+; preceding section, and once afterward.
+;
+; As expected, the search range for a negative pattern preceding a CHECK-LABEL
+; ends at the start of the CHECK-LABEL match.  not:7 and not:11 below
+; demonstrate this behavior.
+;
+; The search range for a positive pattern preceding a CHECK-LABEL ends at the
+; end of the CHECK-LABEL match.  check:3 and check:5 below demonstrate this
+; behavior.  As in the case of check:5, an effect of this behavior is that the
+; second CHECK-LABEL match might fail even though the first succeeded.
+;
+; FIXME: It seems like the search range for such a positive pattern should be
+; the same as in the case of a negative pattern.  Note that -dump-input is
+; correct here.  It's the matching behavior that's strange.
 ;--------------------------------------------------
 
-; Good match and no match.
-
-; RUN: echo 'lab0' > %t.in
-; RUN: echo 'foo' >> %t.in
-; RUN: echo 'lab1' >> %t.in
-; RUN: echo 'bar' >> %t.in
-
-; RUN: echo 'CHECK-LABEL: lab0' > %t.chk
-; RUN: echo 'CHECK: foo' >> %t.chk
-; RUN: echo 'CHECK-LABEL: lab2' >> %t.chk
+; RUN: echo 'text'   >  %t.in
+; RUN: echo 'labelA' >> %t.in
+; RUN: echo 'textA'  >> %t.in
+; RUN: echo 'labelB' >> %t.in
+; RUN: echo 'textB'  >> %t.in
+; RUN: echo 'labelC' >> %t.in
+; RUN: echo 'textC'  >> %t.in
+; RUN: echo 'labelD' >> %t.in
+; RUN: echo 'textD'  >> %t.in
+; RUN: echo 'labelE' >> %t.in
+; RUN: echo 'textE'  >> %t.in
+; RUN: echo 'labelF' >> %t.in
+
+; RUN: echo 'CHECK: text'         >  %t.chk
+; RUN: echo 'CHECK-LABEL: labelA' >> %t.chk
+; RUN: echo 'CHECK: foobar'       >> %t.chk
+; RUN: echo 'CHECK-LABEL: labelB' >> %t.chk
+; RUN: echo 'CHECK: labelC'       >> %t.chk
+; RUN: echo 'CHECK-LABEL: labelC' >> %t.chk
+; RUN: echo 'CHECK-NOT: foobar'   >> %t.chk
+; RUN: echo 'CHECK-LABEL: labelD' >> %t.chk
+; RUN: echo 'CHECK-NOT: textD'    >> %t.chk
+; RUN: echo 'CHECK-LABEL: labelE' >> %t.chk
+; RUN: echo 'CHECK-NOT: labelF'   >> %t.chk
+; RUN: echo 'CHECK-LABEL: labelF' >> %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=LAB \
-; RUN:             -implicit-check-not='remark:'
+; RUN: | FileCheck -match-full-lines %s -check-prefixes=LAB,LAB-Q \
+; RUN:             -implicit-check-not='{{remark:|error:}}'
 ; 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=LAB,LAB-V \
-; RUN:             -implicit-check-not='remark:'
+; RUN:             -implicit-check-not='{{remark:|error:}}'
 ; 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=LAB,LAB-V,LAB-VV \
-; RUN:             -implicit-check-not='remark:' -allow-unused-prefixes
+; RUN:             -implicit-check-not='{{remark:|error:}}'
 
 ; Verbose diagnostics are suppressed but not errors.
-; LAB: {{.*}}error:{{.*}}
-; LAB: {{.*}}possible intended match{{.*}}
-
-; LAB:         <<<<<<
-; LAB-NEXT:               1: lab0 
-; LAB-V-NEXT:  label:1'0     ^~~~
-; LAB-V-NEXT:  label:1'1     ^~~~
-; LAB-NEXT:    label:3'0         X error: no match found
-; LAB-NEXT:               2: foo 
-; LAB-NEXT:    label:3'0     ~~~~
-; LAB-NEXT:               3: lab1 
-; LAB-NEXT:    label:3'0     ~~~~~
-; LAB-NEXT:    label:3'1     ?     possible intended match
-; LAB-NEXT:               4: bar 
-; LAB-NEXT:    label:3'0     ~~~~
-; LAB-NEXT:    >>>>>>
-; LAB-NOT:     {{.}}
+; LAB:{{.*}}.chk:3:8: error: CHECK: expected string not found in input
+; LAB:{{.*}}.chk:6:14: error: CHECK-LABEL: expected string not found in input
+; LAB:{{.*}}.chk:9:12: error: CHECK-NOT: excluded string found in input
+
+;         LAB:<<<<<<
+;    LAB-NEXT:            1: text 
+;  LAB-V-NEXT:check:1        ^~~~
+;    LAB-NEXT:            2: labelA 
+;  LAB-V-NEXT:label:2'0      ^~~~~~
+;  LAB-V-NEXT:label:2'1      ^~~~~~
+;    LAB-NEXT:check:3              X error: no match found
+;    LAB-NEXT:            3: textA 
+;    LAB-NEXT:check:3        ~~~~~~
+;    LAB-NEXT:            4: labelB 
+;  LAB-V-NEXT:label:4        ^~~~~~
+;    LAB-NEXT:check:3        ~~~~~~
+;    LAB-NEXT:            5: textB 
+;    LAB-NEXT:            6: labelC 
+;  LAB-V-NEXT:label:6'0      ^~~~~~
+;  LAB-V-NEXT:check:5        ^~~~~~
+;  LAB-Q-NEXT:label:6              X error: no match found
+;  LAB-V-NEXT:label:6'1            X error: no match found
+; LAB-VV-NEXT:not:7                X
+;    LAB-NEXT:            7: textC 
+; LAB-VV-NEXT:not:7          ~~~~~~
+;    LAB-NEXT:            8: labelD 
+;  LAB-V-NEXT:label:8'0      ^~~~~~
+;  LAB-V-NEXT:label:8'1      ^~~~~~
+;    LAB-NEXT:            9: textD 
+;    LAB-NEXT:not:9          !~~~~  error: no match expected
+;    LAB-NEXT:           10: labelE 
+;  LAB-V-NEXT:label:10'0     ^~~~~~
+;  LAB-V-NEXT:label:10'1     ^~~~~~
+; LAB-VV-NEXT:not:11               X
+;    LAB-NEXT:           11: textE 
+; LAB-VV-NEXT:not:11         ~~~~~~
+;    LAB-NEXT:           12: labelF 
+;  LAB-V-NEXT:label:12'0     ^~~~~~
+;  LAB-V-NEXT:label:12'1     ^~~~~~
+;    LAB-NEXT:>>>>>>
+;     LAB-NOT:{{.}}
 
 ;--------------------------------------------------
 ; --implicit-check-not
@@ -566,20 +618,28 @@
 ; RUN: echo 'CHECK: wor' >> %t.chk
 ; RUN: echo 'CHECK: !' >> %t.chk
 
+; Prefixes used here:
+; IMPNOT    = quiet, -v, or -vv
+; IMPNOT-Q  = quiet
+; IMPNOT-V  = -v or -vv (-vv implies -v)
+; IMPNOT-VQ = -v and not -vv
+; IMPNOT-VV = -vv
+
 ; RUN: %ProtectFileCheckOutput \
 ; RUN: not FileCheck -dump-input=always -input-file=%t.in %t.chk 2>&1 \
 ; RUN:               --implicit-check-not='goodbye' \
 ; RUN:               --implicit-check-not='world' \
 ; RUN:               --implicit-check-not='again' \
-; RUN: | FileCheck -match-full-lines %s -check-prefix=IMPNOT \
-; RUN:             -implicit-check-not='remark:'
+; RUN: | FileCheck -match-full-lines %s -check-prefixes=IMPNOT,IMPNOT-Q \
+; RUN:             -implicit-check-not='{{remark:|error:}}'
 ; RUN: %ProtectFileCheckOutput \
 ; RUN: not FileCheck -dump-input=always -input-file=%t.in %t.chk -v 2>&1 \
 ; RUN:               --implicit-check-not='goodbye' \
 ; RUN:               --implicit-check-not='world' \
 ; RUN:               --implicit-check-not='again' \
-; RUN: | FileCheck -match-full-lines %s -check-prefixes=IMPNOT,IMPNOT-V \
-; RUN:             -implicit-check-not='remark:'
+; RUN: | FileCheck -match-full-lines %s \
+; RUN:             -check-prefixes=IMPNOT,IMPNOT-V,IMPNOT-VQ \
+; RUN:             -implicit-check-not='{{remark:|error:}}'
 ; RUN: %ProtectFileCheckOutput \
 ; RUN: not FileCheck -dump-input=always -input-file=%t.in %t.chk -vv 2>&1 \
 ; RUN:               --implicit-check-not='goodbye' \
@@ -587,25 +647,27 @@
 ; RUN:               --implicit-check-not='again' \
 ; RUN: | FileCheck -match-full-lines %s \
 ; RUN:             -check-prefixes=IMPNOT,IMPNOT-V,IMPNOT-VV \
-; RUN:             -implicit-check-not='remark:'
+; RUN:             -implicit-check-not='{{remark:|error:}}'
 
 ; Verbose diagnostics are suppressed but not errors.
-; IMPNOT:{{.*}}error:{{.*}}
+; IMPNOT:{{.*}}command line:1:22: error: CHECK-NOT: excluded string found in input
 
 ;         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-NEXT:            1: hello world again! 
+;  IMPNOT-V-NEXT:check:1        ^~~
+; IMPNOT-VV-NEXT:not:imp1'0     X
+; IMPNOT-VV-NEXT:not:imp2'0     X
+; IMPNOT-VV-NEXT:not:imp3'0     X
+;  IMPNOT-V-NEXT:check:2              ^~~
+; IMPNOT-VV-NEXT:not:imp1'1        X~~
+; IMPNOT-VV-NEXT:not:imp2'1        X~~
+; IMPNOT-VV-NEXT:not:imp3'1        X~~
+;  IMPNOT-V-NEXT:check:3                         ^
+; IMPNOT-VV-NEXT:not:imp1'2              X~~~~~~~
+; IMPNOT-VV-NEXT:not:imp2'2              X~~~~~~~
+;  IMPNOT-Q-NEXT:not:imp3                   !~~~~   error: no match expected
+; IMPNOT-VQ-NEXT:not:imp3                   !~~~~   error: no match expected
+; IMPNOT-VV-NEXT:not:imp3'2                 !~~~~   error: no match expected
 ;    IMPNOT-NEXT:>>>>>>
 ;     IMPNOT-NOT:{{.}}
 
diff --git a/llvm/utils/FileCheck/FileCheck.cpp b/llvm/utils/FileCheck/FileCheck.cpp
index c1bb97f..0e97c711 100644
--- a/llvm/utils/FileCheck/FileCheck.cpp
+++ b/llvm/utils/FileCheck/FileCheck.cpp
@@ -22,6 +22,7 @@
 #include "llvm/Support/WithColor.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cmath>
+#include <map>
 using namespace llvm;
 
 static cl::extrahelp FileCheckOptsEnv(
@@ -378,16 +379,25 @@ BuildInputAnnotations(const SourceMgr &SM, unsigned CheckFileBufferID,
                       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;
+  struct CompareSMLoc {
+    bool operator()(const SMLoc &LHS, const SMLoc &RHS) {
+      return LHS.getPointer() < RHS.getPointer();
+    }
+  };
+  // How many diagnostics does each pattern have?
+  std::map<SMLoc, unsigned, CompareSMLoc> DiagCountPerPattern;
+  for (auto Diag : Diags)
+    ++DiagCountPerPattern[Diag.CheckLoc];
+  // How many diagnostics have we seen so far per pattern?
+  std::map<SMLoc, unsigned, CompareSMLoc> DiagIndexPerPattern;
+  // How many total diagnostics have we seen so far?
+  unsigned DiagIndex = 0;
   // What's the widest label?
   LabelWidth = 0;
   for (auto DiagItr = Diags.begin(), DiagEnd = Diags.end(); DiagItr != DiagEnd;
        ++DiagItr) {
     InputAnnotation A;
-    A.DiagIndex = DiagCount++;
+    A.DiagIndex = DiagIndex++;
 
     // Build label, which uniquely identifies this check result.
     unsigned CheckBufferID = SM.FindBufferContainingLoc(DiagItr->CheckLoc);
@@ -403,17 +413,8 @@ BuildInputAnnotations(const SourceMgr &SM, unsigned CheckFileBufferID,
     else
       llvm_unreachable("expected diagnostic's check location to be either in "
                        "the check file or for an implicit pattern");
-    unsigned CheckDiagIndex = UINT_MAX;
-    auto DiagNext = std::next(DiagItr);
-    if (DiagNext != DiagEnd && DiagItr->CheckTy == DiagNext->CheckTy &&
-        DiagItr->CheckLoc == DiagNext->CheckLoc)
-      CheckDiagIndex = CheckDiagCount++;
-    else if (CheckDiagCount) {
-      CheckDiagIndex = CheckDiagCount;
-      CheckDiagCount = 0;
-    }
-    if (CheckDiagIndex != UINT_MAX)
-      Label << "'" << CheckDiagIndex;
+    if (DiagCountPerPattern[DiagItr->CheckLoc] > 1)
+      Label << "'" << DiagIndexPerPattern[DiagItr->CheckLoc]++;
     Label.flush();
     LabelWidth = std::max((std::string::size_type)LabelWidth, A.Label.size());