FileCheck Enhancement - CHECK-LABEL-DAG

[eklepilkina]

Summary

This patch adds new directive CHECK-LABEL-DAG, which allows the use of not sequential order of labels.

[alexfh]

IIUC, there was no consensus about usefulness of this change.

docs/CommandGuide/FileCheck.rst

 failures to be detected in a single invocation.
 
 There is no requirement that ``CHECK-LABEL:`` directives contain strings that
 correspond to actual syntactic labels in a source or output language: they must
 simply uniquely match a single line in the file being verified.
 
 ``CHECK-LABEL:`` directives cannot contain variable definitions or uses.
 
+The "CHECK-LABEL-DAG:" directive
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Directive CHECK-LABEL-DAG divides the input stream into separate blocks, each 
+of which is processed independently as CHECK-LABEL, but these blocks can be 
+matched in different order. 
+
+.. code-block:: llvm
+
+    // RUN: FileCheck -input-file %s %s
+
+    // CHECK-LABEL-DAG: {{^}}start first
+    // CHECK: 1
+    // CHECK-DAG:4
+    // CHECK-DAG:3
+    // CHECK-NEXT: {{[0-2]}}
+    // CHECK-SAME: 12
+
+    // CHECK-LABEL-DAG: {{^}}start second
+    // CHECK-DAG: sec3
+    // CHECK-DAG: sec1
+    // CHECK: second ends
+
+    start second
+    sec1
+    sec3
+    second ends
+    start first
+    1
+    3
+    4
+    2 12
+
+Firstly second block matches after that matches first. Order of description 
+has no matter.
+
+
 FileCheck Pattern Matching Syntax
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 All FileCheck directives take a pattern to match.
 For most uses of FileCheck, fixed string matching is perfectly sufficient.  For
 some things, a more flexible form of matching is desired.  To support this,
 FileCheck allows you to specify regular expressions in matching strings,
 surrounded by double braces: ``{{yourregex}}``.  Because we want to use fixed

test/FileCheck/check-label-dag-directive.txt

+// RUN: FileCheck -input-file %s %s
+
+// CHECK-LABEL-DAG: {{^}}start first
+// CHECK: 1
+// CHECK-DAG:4
+// CHECK-DAG:3
+// CHECK-NEXT: {{[0-2]}}
+// CHECK-SAME: 12
+
+// CHECK-LABEL-DAG: {{^}}start second
+// CHECK-DAG: sec3
+// CHECK-DAG: sec1
+// CHECK: second ends
+
+start second
+sec1
+sec3
+second ends
+
+start first
+
+1
+
+3
+
+4
+2 12

utils/FileCheck/FileCheck.cpp

namespace Check {
   enum CheckType {
     CheckNone = 0,
     CheckPlain,
     CheckNext,
     CheckSame,
     CheckNot,
     CheckDAG,
     CheckLabel,
+    CheckLabelDag,
 
     /// MatchEOF - When set, this pattern only matches the end of file. This is
     /// used for trailing CHECK-NOTs.
     CheckEOF,
     /// CheckBadNot - Found -NOT combined with another CHECK suffix.
     CheckBadNot
   };
 }
case Check::CheckNot:
     return sizeof("-NOT:") - 1;
 
   case Check::CheckDAG:
     return sizeof("-DAG:") - 1;
 
   case Check::CheckLabel:
     return sizeof("-LABEL:") - 1;
 
+  case Check::CheckLabelDag:
+    return sizeof("-LABEL-DAG:") - 1;
+
   case Check::CheckEOF:
     llvm_unreachable("Should not be using EOF size");
   }
 
   llvm_unreachable("Bad check type");
 }
 
 static Check::CheckType FindCheckType(StringRef Buffer, StringRef Prefix) {
if (Rest.startswith("NOT:"))
     return Check::CheckNot;
 
   if (Rest.startswith("DAG:"))
     return Check::CheckDAG;
 
   if (Rest.startswith("LABEL:"))
     return Check::CheckLabel;
 
+  if (Rest.startswith("LABEL-DAG:"))
+    return Check::CheckLabelDag;
+
   // You can't combine -NOT with another suffix.
   if (Rest.startswith("DAG-NOT:") || Rest.startswith("NOT-DAG:") ||
       Rest.startswith("NEXT-NOT:") || Rest.startswith("NOT-NEXT:") ||
       Rest.startswith("SAME-NOT:") || Rest.startswith("NOT-SAME:"))
     return Check::CheckBadNot;
 
   return Check::CheckNone;
 }
int main(int argc, char **argv) {
 
   SM.AddNewSourceBuffer(std::move(F), SMLoc());
 
   /// VariableTable - This holds all the current filecheck variables.
   StringMap<StringRef> VariableTable;
 
   bool hasError = false;
 
-  unsigned i = 0, j = 0, e = CheckStrings.size();
+  unsigned i = 0, j = 0, k = 0, e = CheckStrings.size();
 
   while (true) {
     StringRef CheckRegion;
+    StringRef InnerCheckRegion;
+    std::map<size_t, unsigned> CheckLabelDagPositions;
+    std::vector<unsigned> CheckLabelDagsIndexes;
     if (j == e) {
       CheckRegion = Buffer;
     } else {
       const CheckString &CheckLabelStr = CheckStrings[j];
       if (CheckLabelStr.Pat.getCheckTy() != Check::CheckLabel) {
         ++j;
         continue;
       }
 
       // Scan to next CHECK-LABEL match, ignoring CHECK-NOT and CHECK-DAG
       size_t MatchLabelLen = 0;
       size_t MatchLabelPos = CheckLabelStr.Check(SM, Buffer, true,
                                                  MatchLabelLen, VariableTable);
       if (MatchLabelPos == StringRef::npos) {
         hasError = true;
         break;
       }
 
       CheckRegion = Buffer.substr(0, MatchLabelPos + MatchLabelLen);
       Buffer = Buffer.substr(MatchLabelPos + MatchLabelLen);
       ++j;
     }
 
-    for ( ; i != j; ++i) {
+    k = 0;
+    // Choose all CHECK-LABEL-DAG in current check region.
+    while  (k != j) {
+      const CheckString &CheckLabelDagStr = CheckStrings[k];
+      if (CheckLabelDagStr.Pat.getCheckTy() != Check::CheckLabelDag) {
+        ++k;
+        continue;
+      }
+
+      // Find and remember matches of all CHECK-LABEL-DAG
+      size_t MatchLabelLen = 0;
+      size_t MatchLabelPos = CheckLabelDagStr.Check(
+          SM, CheckRegion, true, MatchLabelLen, VariableTable);
+
+      if (MatchLabelPos == StringRef::npos) {
+        hasError = true;
+        break;
+      }
+      CheckLabelDagPositions.insert(
+          std::pair<size_t, unsigned>(MatchLabelPos + MatchLabelLen, k));
+      CheckLabelDagsIndexes.push_back(k);
+      k++;
+    }
+
+    size_t Before = 0;
+    bool wasLabelDag = false;
+    for (const auto &MatchLabelDag : CheckLabelDagPositions) {
+      
+      unsigned PrevLabelDagInDescription;
+      std::vector<unsigned>::iterator It;
+
+      // Get next label dag in description
+      It = find(CheckLabelDagsIndexes.begin(), CheckLabelDagsIndexes.end(),
+                MatchLabelDag.second);
+      if (It != CheckLabelDagsIndexes.begin()) {
+        PrevLabelDagInDescription = *(--It);
+      } else {
+        PrevLabelDagInDescription = -1;
+      }
+
+      // Create check region for usual checks
+      InnerCheckRegion =
+          CheckRegion.substr(Before, MatchLabelDag.first - Before);
+      Before = MatchLabelDag.first;
+
+      // For this check region run all checks between two label dags in
+      // description
+      for (i = wasLabelDag ? PrevLabelDagInDescription + 1 : 0;
+           i != wasLabelDag ? MatchLabelDag.second : CheckLabelDagsIndexes[0];
+           ++i) {
+        // Cycle
+        const CheckString &CheckStr = CheckStrings[i];
+
+        // Check each string within the scanned region, including a second check
+        // of any final CHECK-LABEL (to verify CHECK-NOT and CHECK-DAG)
+        size_t MatchLen = 0;
+        size_t MatchPos = CheckStr.Check(SM, InnerCheckRegion, false, MatchLen,
+                                       VariableTable);
+
+        if (MatchPos == StringRef::npos) {
+          hasError = true;
+          i = j;
+          break;
+        }
+
+        InnerCheckRegion = InnerCheckRegion.substr(MatchPos + MatchLen);
+      }
+      wasLabelDag = true;
+    }
+
+    for (; i != j && !wasLabelDag; ++i) {
       const CheckString &CheckStr = CheckStrings[i];
 
       // Check each string within the scanned region, including a second check
       // of any final CHECK-LABEL (to verify CHECK-NOT and CHECK-DAG)
       size_t MatchLen = 0;
       size_t MatchPos = CheckStr.Check(SM, CheckRegion, false, MatchLen,
                                        VariableTable);