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

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.

Reviewed By: probinson

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@337605 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 46 insertions, 46 deletions

diff --git a/utils/FileCheck/FileCheck.cpp b/utils/FileCheck/FileCheck.cpp
index 4efe535cecf..60b71200dd5 100644
--- a/utils/FileCheck/FileCheck.cpp
+++ b/utils/FileCheck/FileCheck.cpp
@@ -1283,17 +1283,23 @@ size_t CheckString::CheckDag(const SourceMgr &SM, StringRef Buffer,
   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!");
@@ -1310,7 +1316,7 @@ size_t CheckString::CheckDag(const SourceMgr &SM, StringRef Buffer,
 
     // 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
@@ -1325,10 +1331,21 @@ size_t CheckString::CheckDag(const SourceMgr &SM, StringRef Buffer,
       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) {
@@ -1340,7 +1357,7 @@ size_t CheckString::CheckDag(const SourceMgr &SM, StringRef Buffer,
       }
       if (!Overlap) {
         // Insert non-overlapping match into list.
-        Matches.insert(MI, M);
+        MatchRanges.insert(MI, M);
         break;
       }
       if (VerboseVerbose) {
@@ -1357,46 +1374,29 @@ size_t CheckString::CheckDag(const SourceMgr &SM, StringRef Buffer,
       PrintMatch(true, SM, Prefix, Pat.getLoc(), Pat, Buffer, VariableTable,
                  MatchPos, MatchLen);
 
-    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;
+    // Handle the end of a CHECK-DAG group.
+    if (std::next(PatItr) == PatEnd ||
+        std::next(PatItr)->getCheckTy() == Check::CheckNot) {
+      if (!NotStrings.empty()) {
+        // 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(StartPos, MatchRanges.begin()->Pos);
+        if (CheckNot(SM, SkippedRegion, NotStrings, VariableTable))
+          return StringRef::npos;
+        // Clear "not strings".
+        NotStrings.clear();
       }
-      // All subsequent CHECK-DAGs should be matched from the farthest
-      // position of all precedent CHECK-DAGs (not including this one).
-      StartPos = 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.
-      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
-      // region.
-      StringRef SkippedRegion = Buffer.slice(LastPos, MatchPos);
-      if (CheckNot(SM, SkippedRegion, NotStrings, VariableTable))
-        return StringRef::npos;
-      // Clear "not strings".
-      NotStrings.clear();
+      MatchRanges.clear();
     }
-
-    // Update the last position with CHECK-DAG matches.
-    LastPos = std::max(MatchPos + MatchLen, LastPos);
   }
 
-  return LastPos;
+  return StartPos;
 }
 
 // A check prefix must contain only alphanumeric, hyphens and underscores.