[FileCheck] Don't permit overlapping CHECK-DAG

That is, make CHECK-DAG skip matches that overlap the matches of any
preceding consecutive CHECK-DAG directives.  This change makes
CHECK-DAG more consistent with other directives, and there is evidence
it makes CHECK-DAG more intuitive and less error-prone.  See the RFC
discussion starting at:

  http://lists.llvm.org/pipermail/llvm-dev/2018-May/123010.html

Moreover, this behavior enables CHECK-DAG groups for unordered,
non-unique strings or patterns.  For example, it is useful for
verifying output or logs from a parallel program, such as the OpenMP
runtime.

This patch also implements the command-line option
-allow-deprecated-dag-overlap, which reverts CHECK-DAG to the old
overlapping behavior.  This option should not be used in new tests.
It is meant only for the existing tests that are broken by this change
and that need time to update.

See the following bugzilla issue for tracking of such tests:

  https://bugs.llvm.org/show_bug.cgi?id=37532

Patches to add -allow-deprecated-dag-overlap to those tests will
follow immediately.

Reviewed By: probinson

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

llvm-svn: 336847

1 files changed, 53 insertions, 12 deletions

diff --git a/llvm/utils/FileCheck/FileCheck.cpp b/llvm/utils/FileCheck/FileCheck.cpp
index 74157343b43..cd3175f13f0 100644
--- a/llvm/utils/FileCheck/FileCheck.cpp
+++ b/llvm/utils/FileCheck/FileCheck.cpp
@@ -28,6 +28,7 @@
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cctype>
+#include <list>
 #include <map>
 #include <string>
 #include <system_error>
@@ -82,6 +83,13 @@ static cl::opt<bool> EnableVarScope(
              "do not start with '$' will be reset at the beginning of\n"
              "each CHECK-LABEL block."));
 
+static cl::opt<bool> AllowDeprecatedDagOverlap(
+    "allow-deprecated-dag-overlap", cl::init(false),
+    cl::desc("Enable overlapping among matches in a group of consecutive\n"
+             "CHECK-DAG directives.  This option is deprecated and is only\n"
+             "provided for convenience as old tests are migrated to the new\n"
+             "non-overlapping CHECK-DAG implementation.\n"));
+
 typedef cl::list<std::string>::const_iterator prefix_iterator;
 
 //===----------------------------------------------------------------------===//
@@ -1192,6 +1200,13 @@ size_t CheckString::CheckDag(const SourceMgr &SM, StringRef Buffer,
   size_t LastPos = 0;
   size_t StartPos = LastPos;
 
+  // A sorted list of ranges for non-overlapping dag matches.
+  struct Match {
+    size_t Pos;
+    size_t End;
+  };
+  std::list<Match> Matches;
+
   for (const Pattern &Pat : DagNotStrings) {
     assert((Pat.getCheckTy() == Check::CheckDAG ||
             Pat.getCheckTy() == Check::CheckNot) &&
@@ -1204,19 +1219,42 @@ size_t CheckString::CheckDag(const SourceMgr &SM, StringRef Buffer,
 
     assert((Pat.getCheckTy() == Check::CheckDAG) && "Expect CHECK-DAG!");
 
-    size_t MatchLen = 0, MatchPos;
-
     // CHECK-DAG always matches from the start.
-    StringRef MatchBuffer = Buffer.substr(StartPos);
-    MatchPos = 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 (MatchPos == StringRef::npos) {
-      PrintCheckFailed(SM, Pat.getLoc(), Pat, MatchBuffer, VariableTable);
-      return StringRef::npos;
+    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) {
+      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) {
+        PrintCheckFailed(SM, 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 (AllowDeprecatedDagOverlap)
+        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);
+        break;
+      }
+      MatchPos = MI->End;
     }
-    // Re-calc it as the offset relative to the start of the original string.
-    MatchPos += StartPos;
 
     if (!NotStrings.empty()) {
       if (MatchPos < LastPos) {
@@ -1238,8 +1276,11 @@ size_t CheckString::CheckDag(const SourceMgr &SM, StringRef Buffer,
         return StringRef::npos;
       }
       // All subsequent CHECK-DAGs should be matched from the farthest
-      // position of all precedent CHECK-DAGs (including this one.)
+      // 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
       // region.