[FileCheck] Fix search ranges for DAG-NOT-DAG

[jdenny]

Summary

A DAG-NOT-DAG is a CHECK-DAG group, X, followed by a CHECK-NOT group,
N, followed by a CHECK-DAG group, Y. Let y be the initial directive
of Y. This patch makes the following changes to the behavior:

1. Directives in N can no longer match within part of Y's match range just because y happens not to be the earliest match from Y. Specifically, this patch withdraws N's search range end from y's match range start to Y's match range start.
2. y can no longer match within X's match range, where a y match produced a reordering complaint, which is thus no longer possible. Specifically, this patch withdraws y's search range start from X's permitted range start to X's match range end, which was already the search range start for other members of Y.

Both of these changes can only increase the number of test passes: #1
constrains the ability of CHECK-NOTs to match, and #2 expands the
ability of CHECK-DAGs to match without complaints.

These changes are based on discussions at:

<http://lists.llvm.org/pipermail/llvm-dev/2018-May/123550.html>
<https://reviews.llvm.org/D47106>

which conclude that:

1. These changes simplify the FileCheck conceptual model. First, it makes search ranges for DAG-NOT-DAG more consistent with other cases. Second, it was confusing that y was treated differently from the rest of Y.
2. These changes add theoretical use cases for DAG-NOT-DAG that had no obvious means to be expressed otherwise. We can justify the first half of this assertion with the observation that these changes can only increase the number of test passes.
3. Reordering detection for DAG-NOT-DAG had no obvious real benefit.

We don't have evidence from real uses cases to help us debate
conclusions #2 and #3, but #1 at least seems intuitive.

[jdenny]

Ping. Rebased.

[probinson]

Sorry, lost track of this one. One comment suggestion and LGTM.

llvm/utils/FileCheck/FileCheck.cpp

1299 ↗

(On Diff #156525)

Range-based for loops are now so canonical, you should have a comment explaining why this isn't. Especially because the reason is pretty far away in the source.

[jdenny]

In D48986#1170073, @probinson wrote:

Sorry, lost track of this one. One comment suggestion and LGTM.

Thanks! I'll make that change and commit soon.

llvm/trunk/test/FileCheck/check-dag-not-dag.txt

+;---------------------------------------------------------------------
+; RUN: FileCheck -input-file %s %s -check-prefix=NotSearchEnd
+
+The search range for the NOTs used to end at the start of the match range for
+the first DAG in the following DAG group.  Now it ends at the start of the
+match range for the entire following DAG group.
+
+__NotSearchEnd
+x0
+x1
+
+y1
+foobar
+y0
+
+z2
+foobar
+z1
+foobar
+z0
+__NotSearchEnd
+
+; NotSearchEnd:     {{^}}__NotSearchEnd
+; NotSearchEnd-DAG: {{^}}x0
+; NotSearchEnd-DAG: {{^}}x1
+; NotSearchEnd-NOT: {{^}}foobar
+; NotSearchEnd-DAG: {{^}}y0
+; NotSearchEnd-DAG: {{^}}y1
+; NotSearchEnd-NOT: {{^}}foobar
+; NotSearchEnd-DAG: {{^}}z0
+; NotSearchEnd-DAG: {{^}}z1
+; NotSearchEnd-DAG: {{^}}z2
+; NotSearchEnd:     {{^}}__NotSearchEnd
+
+;---------------------------------------------------------------------
+; RUN: FileCheck -input-file %s %s -check-prefix=Dag2SearchStart
+
+The start of the search range for the second or later DAG group used to be
+different for its first DAG than its other DAGs.  For the first DAG, it was
+the start of the permitted range for the preceding DAG group, and there was a
+reordering complaint if the match range was in the first DAG group's match
+range.  For the other DAGs, it was the end of the match range for the
+preceding DAG group, so reordering detection wasn't possible.  Now, the
+first DAG behaves like the others, and so reordering detection is no longer
+implemented.  As a result, matches that used to produce the reordering
+complaint are now skipped, permitting later matches to succeed.
+
+__Dag2SearchStart
+y0
+y1
+x0
+y0
+y1
+x1
+
+z1
+z0
+y1
+z1
+z0
+y0
+
+z0
+z1
+__Dag2SearchStart
+
+; Dag2SearchStart:     {{^}}__Dag2SearchStart
+; Dag2SearchStart-DAG: {{^}}x0
+; Dag2SearchStart-DAG: {{^}}x1
+; Dag2SearchStart-NOT: {{^}}foobar
+; Dag2SearchStart-DAG: {{^}}y0
+; Dag2SearchStart-DAG: {{^}}y1
+; Dag2SearchStart-NOT: {{^}}foobar
+; Dag2SearchStart-DAG: {{^}}z0
+; Dag2SearchStart-DAG: {{^}}z1
+; Dag2SearchStart:     {{^}}__Dag2SearchStart
 No newline at end of file

llvm/trunk/test/FileCheck/check-dag-overlap.txt

 ; RUN: not FileCheck -allow-deprecated-dag-overlap -input-file %s %s \
 ; RUN:               -check-prefix=DagNotDag
 ; RUN: FileCheck -input-file %s %s -check-prefix=DagNotDag
 
 Assume we have DAGs, NOTs, DAGs, NOTs, and then DAGs.  Let X, Y, and Z be
 the DAG groups such that the leading DAGs are x, y, and z.  y won't match
 overlaps with matches from:
 
-1. X.  Otherwise, we could get a spurious reordering complaint.
+1. X.  Otherwise, we used to get a spurious reordering complaint (back
+   when reordering complaints on DAG-NOT-DAG were still implemented).
 2. Y, because y is in Y.  To prevent these overlaps, the implementation must be
    careful not to drop y's match from the previous matches list when it drops
    matches from X to save search time.
 3. z.  This follows by applying rule #1 for z instead of y.
 
 __DagNotDag
 abcdefgh
 abcd

llvm/trunk/utils/FileCheck/FileCheck.cpp

 
 /// Match "dag strings" and their mixed "not strings".
 size_t CheckString::CheckDag(const SourceMgr &SM, StringRef Buffer,
                              std::vector<const Pattern *> &NotStrings,
                              StringMap<StringRef> &VariableTable) const {
   if (DagNotStrings.empty())
     return 0;
 
-  size_t LastPos = 0;
-  size_t StartPos = LastPos;
+  // The start of the search range.
+  size_t StartPos = 0;
 
-  // A sorted list of ranges for non-overlapping dag matches.
-  struct Match {
+  struct MatchRange {
     size_t Pos;
     size_t End;
   };
-  std::list<Match> Matches;
-
-  for (const Pattern &Pat : DagNotStrings) {
+  // A sorted list of ranges for non-overlapping CHECK-DAG matches.  Match
+  // ranges are erased from this list once they are no longer in the search
+  // range.
+  std::list<MatchRange> MatchRanges;
+
+  // We need PatItr and PatEnd later for detecting the end of a CHECK-DAG
+  // group, so we don't use a range-based for loop here.
+  for (auto PatItr = DagNotStrings.begin(), PatEnd = DagNotStrings.end();
+       PatItr != PatEnd; ++PatItr) {
+    const Pattern &Pat = *PatItr;
     assert((Pat.getCheckTy() == Check::CheckDAG ||
             Pat.getCheckTy() == Check::CheckNot) &&
            "Invalid CHECK-DAG or CHECK-NOT!");
 
     if (Pat.getCheckTy() == Check::CheckNot) {
       NotStrings.push_back(&Pat);
       continue;
     }
 
     assert((Pat.getCheckTy() == Check::CheckDAG) && "Expect CHECK-DAG!");
 
     // CHECK-DAG always matches from the start.
     size_t MatchLen = 0, MatchPos = StartPos;
 
     // Search for a match that doesn't overlap a previous match in this
     // CHECK-DAG group.
-    for (auto MI = Matches.begin(), ME = Matches.end(); true; ++MI) {
+    for (auto MI = MatchRanges.begin(), ME = MatchRanges.end(); true; ++MI) {
       StringRef MatchBuffer = Buffer.substr(MatchPos);
       size_t MatchPosBuf = Pat.Match(MatchBuffer, MatchLen, VariableTable);
       // With a group of CHECK-DAGs, a single mismatching means the match on
       // that group of CHECK-DAGs fails immediately.
       if (MatchPosBuf == StringRef::npos) {
         PrintNoMatch(true, SM, Prefix, Pat.getLoc(), Pat, MatchBuffer,
                      VariableTable);
         return StringRef::npos;
       }
       // Re-calc it as the offset relative to the start of the original string.
       MatchPos += MatchPosBuf;
       if (VerboseVerbose)
         PrintMatch(true, SM, Prefix, Pat.getLoc(), Pat, Buffer, VariableTable,
                    MatchPos, MatchLen);
-      if (AllowDeprecatedDagOverlap)
+      MatchRange M{MatchPos, MatchPos + MatchLen};
+      if (AllowDeprecatedDagOverlap) {
+        // We don't need to track all matches in this mode, so we just maintain
+        // one match range that encompasses the current CHECK-DAG group's
+        // matches.
+        if (MatchRanges.empty())
+          MatchRanges.insert(MatchRanges.end(), M);
+        else {
+          auto Block = MatchRanges.begin();
+          Block->Pos = std::min(Block->Pos, M.Pos);
+          Block->End = std::max(Block->End, M.End);
+        }
         break;
+      }
       // Iterate previous matches until overlapping match or insertion point.
-      Match M{MatchPos, MatchPos + MatchLen};
       bool Overlap = false;
       for (; MI != ME; ++MI) {
         if (M.Pos < MI->End) {
           // !Overlap => New match has no overlap and is before this old match.
           // Overlap => New match overlaps this old match.
           Overlap = MI->Pos < M.End;
           break;
         }
       }
       if (!Overlap) {
         // Insert non-overlapping match into list.
-        Matches.insert(MI, M);
+        MatchRanges.insert(MI, M);
         break;
       }
       if (VerboseVerbose) {
         SMLoc OldStart = SMLoc::getFromPointer(Buffer.data() + MI->Pos);
         SMLoc OldEnd = SMLoc::getFromPointer(Buffer.data() + MI->End);
         SMRange OldRange(OldStart, OldEnd);
         SM.PrintMessage(OldStart, SourceMgr::DK_Note,
                         "match discarded, overlaps earlier DAG match here",
                         {OldRange});
       }
       MatchPos = MI->End;
     }
     if (!VerboseVerbose)
       PrintMatch(true, SM, Prefix, Pat.getLoc(), Pat, Buffer, VariableTable,
                  MatchPos, MatchLen);
 
+    // Handle the end of a CHECK-DAG group.
+    if (std::next(PatItr) == PatEnd ||
+        std::next(PatItr)->getCheckTy() == Check::CheckNot) {
       if (!NotStrings.empty()) {
-      if (MatchPos < LastPos) {
-        // Reordered?
-        SM.PrintMessage(SMLoc::getFromPointer(Buffer.data() + MatchPos),
-                        SourceMgr::DK_Error,
-                        Prefix + "-DAG: found a match of CHECK-DAG"
-                                 " reordering across a CHECK-NOT");
-        SM.PrintMessage(SMLoc::getFromPointer(Buffer.data() + LastPos),
-                        SourceMgr::DK_Note,
-                        Prefix + "-DAG: the farthest match of CHECK-DAG"
-                                 " is found here");
-        SM.PrintMessage(NotStrings[0]->getLoc(), SourceMgr::DK_Note,
-                        Prefix + "-NOT: the crossed pattern specified"
-                                 " here");
-        SM.PrintMessage(Pat.getLoc(), SourceMgr::DK_Note,
-                        Prefix + "-DAG: the reordered pattern specified"
-                                 " here");
-        return StringRef::npos;
-      }
-      // All subsequent CHECK-DAGs should be matched from the farthest
-      // position of all precedent CHECK-DAGs (not including this one).
-      StartPos = LastPos;
-      // Don't waste time checking for (impossible) overlaps before that.
-      Matches.clear();
-      Matches.push_back(Match{MatchPos, MatchPos + MatchLen});
-      // If there's CHECK-NOTs between two CHECK-DAGs or from CHECK to
-      // CHECK-DAG, verify that there's no 'not' strings occurred in that
+        // If there are CHECK-NOTs between two CHECK-DAGs or from CHECK to
+        // CHECK-DAG, verify that there are no 'not' strings occurred in that
         // region.
-      StringRef SkippedRegion = Buffer.slice(LastPos, MatchPos);
+        StringRef SkippedRegion =
+            Buffer.slice(StartPos, MatchRanges.begin()->Pos);
         if (CheckNot(SM, SkippedRegion, NotStrings, VariableTable))
           return StringRef::npos;
         // Clear "not strings".
         NotStrings.clear();
       }
-
-    // Update the last position with CHECK-DAG matches.
-    LastPos = std::max(MatchPos + MatchLen, LastPos);
+      // All subsequent CHECK-DAGs and CHECK-NOTs should be matched from the
+      // end of this CHECK-DAG group's match range.
+      StartPos = MatchRanges.rbegin()->End;
+      // Don't waste time checking for (impossible) overlaps before that.
+      MatchRanges.clear();
+    }
   }
 
-  return LastPos;
+  return StartPos;
 }
 
 // A check prefix must contain only alphanumeric, hyphens and underscores.
 static bool ValidateCheckPrefix(StringRef CheckPrefix) {
   Regex Validator("^[a-zA-Z0-9_-]*$");
   return Validator.match(CheckPrefix);
 }