FileCheck Enhancement - Expressions repeat for CHECK and CHECK-NEXT

[eklepilkina]

Summary

This patch adds opportunity to use quantifiers for CHECK and CHECK-NEXT directives.

[alexfh]

This patch brings up a number of questions:

1. What's your use case? Optimizing tests by replacing a known number of check lines with repeated patterns? Or is the number of patterns you expect not known in advance?
2. Are there possible usages of this feature in LLVM tests already?
3. How is this going to interact with [[@LINE]]?

[eklepilkina]

This comment was removed by eklepilkina.

[eklepilkina]

In D22501#551507, @alexfh wrote:

This patch brings up a number of questions:

1. What's your use case? Optimizing tests by replacing a known number of check lines with repeated patterns? Or is the number of patterns you expect not known in advance?

Both first and second case.

2. Are there possible usages of this feature in LLVM tests already?

I don't know LLVM tests well to answer this question.

3. How is this going to interact with [[@LINE]]?

I used FileCheck Match function in loop, so it will be real LINE value. I don't change matching.

docs/CommandGuide/FileCheck.rst

 
 .. code-block:: llvm
 
        DW_AT_location [DW_FORM_sec_offset]   (0x00000233)
        DW_AT_name [DW_FORM_strp]  ( .debug_str[0x000000c9] = "intd")
 
 letting us set the :program:`FileCheck` variable ``DLOC`` to the desired value 
 ``0x00000233``, extracted from the line immediately preceding "``intd``".
+
+Repeated checks
+~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Sometimes some checks should be repeated. In this cases you can use repeated checks.
+For example
+
+.. code-block:: llvm
+
+    //CHECK{3} : {{[a-z]+}}
+
+It’s equal to 
+
+.. code-block:: llvm
+
+    //CHECK: {{[a-z]+}}
+    //CHECK: {{[a-z]+}}
+    //CHECK: {{[a-z]+}}
+
+There can be used next quantifiers:
+* - The asterisk indicates zero or more occurrences of the preceding element. 
++ - The plus sign indicates one or more occurrences of the preceding element. 
+{n} - The preceding item is matched exactly n times.
+{min,}  - The preceding item is matched min or more times.
+{,max}  - The preceding item is matched zero or more times, but not more than max times.
+{min,max} - The preceding item is matched at least min times, but not more than max times.
+
+You should remember that there may be extra lines which can be matched with pattern. If you need check there is no more such pattern use CHECK-NOT or CHECK-NEXT
+Example:
+
+.. code-block:: llvm
+    sub1
+    sub2
+    sub3
+    sub4
+    add1
+
+    //CHECK{3} : {{[a-z]+}}
+    //CHECK: add1
+
+Check will be successful, because there are no limits for characters, which are between two checks.
+
+.. code-block:: llvm
+
+  //CHECK{3} : {{[a-z]+}}
+  //CHECK-NOT: {{[a-z]+}}
+  //CHECK: add1
+
+Check will be failed, because there is limit that same pattern can’t be between two matches.
+
+.. code-block:: llvm
+
+    //CHECK{3} : {{[a-z]+}}
+    //CHECK-NEXT: add1
+    
+Check will be failed, because there is limit that next match should be on next line.
 No newline at end of file

test/FileCheck/check-next-repeats.txt

+// RUN: FileCheck -input-file %s %s
+
+op1;
+op2;
+op3;
+first and
+second
+R0
+R2
+R5
+Reg3
+SOMETHING TWO TIMES
+SOMETHING TWO TIMES
+ADD R0, R2
+ADD R0, R7
+ADD R15, R18
+ADD Reg, reg1
+SUB R1, R0
+SUB
+// CHECK{3}: {{[a-z]+[0-9]+;}}
+// CHECK-NEXT{,4}: {{[a-z]+ *[a-z]*$}}
+// CHECK-NEXT: [[REG:R[0-9]+]]
+// CHECK-NEXT{1,3}: SOMETHING TWO {{TIMES}}
+// CHECK-NEXT+: ADD [[REG]], {{R[0-9]+}}
+// CHECK-NEXT*: SUB {{R[0-9]+}}, [[REG]]
+// CHECK-NEXT*: MUL [[REG]], [[REG]]

test/FileCheck/check-repeats.txt

+// RUN: FileCheck -input-file %s %s
+
+op1;
+op2;
+op3;
+// CHECK{3}: {{[a-z]+[0-9]+;}}
+
+first and
+second
+// CHECK{,4}: {{[a-z]+[ \t]*[a-z]*}}
+
+r0
+r2
+r5
+reg3
+// CHECK{2,3}: [[REG:r[0-9]+]]
+
+something two times
+something two times
+// CHECK{1,}: something two times
+
+ADD r5, r2
+ADD r5, r7
+ADD r15, r18
+ADD reg, reg1
+// CHECK+: ADD [[REG]], {{r[0-9]+}}
+
+SUB r1, r5
+SUB
+// CHECK*: SUB {{r[0-9]+}}, [[REG]]
+
+// CHECK*: MUL [[REG]], [[REG]]

utils/FileCheck/FileCheck.cpp

namespace Check {
   enum CheckType {
     CheckNone = 0,
     CheckPlain,
     CheckNext,
     CheckSame,
     CheckNot,
     CheckDAG,
     CheckLabel,
+    CheckRepeated,
+    CheckNextRepeated,
 
     /// 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
   };
 }
class Pattern {
   /// value of bar at offset 3.
   std::vector<std::pair<StringRef, unsigned> > VariableUses;
 
   /// VariableDefs - Maps definitions of variables to their parenthesized
   /// capture numbers.
   /// E.g. for the pattern "foo[[bar:.*]]baz", VariableDefs will map "bar" to 1.
   std::map<StringRef, unsigned> VariableDefs;
 
+  /// MinRepeatNumber - minimum number of repeats for repeated patten type.
+  int MinRepeatNumber;
+
+  /// MaxRepeatNumber - maximum number of repeats for repeated patten type. Infinity = -1.
+  int MaxRepeatNumber;
+
 public:
 
-  Pattern(Check::CheckType Ty)
-    : CheckTy(Ty) { }
+  Pattern(Check::CheckType Ty, int MinNumber = 0, int MaxNumber = -1)
+      : CheckTy(Ty), MinRepeatNumber(MinNumber), MaxRepeatNumber(MaxNumber) {}
 
   /// getLoc - Return the location in source code.
   SMLoc getLoc() const { return PatternLoc; }
 
+  int getMinRepeatNumber() const { return MinRepeatNumber; }
+
+  int getMaxRepeatNumber() const { return MaxRepeatNumber; }
+
   /// ParsePattern - Parse the given string into the Pattern. Prefix provides
   /// which prefix is being matched, SM provides the SourceMgr used for error
   /// reports, and LineNumber is the line number in the input file from which
   /// the pattern string was read.  Returns true in case of an error, false
   /// otherwise.
   bool ParsePattern(StringRef PatternStr,
                     StringRef Prefix,
                     SourceMgr &SM,
CanonicalizeInputFile(std::unique_ptr<MemoryBuffer> MB,
   return std::unique_ptr<MemoryBuffer>(
       MemoryBuffer::getMemBufferCopy(NewFile.str(), MB->getBufferIdentifier()));
 }
 
 static bool IsPartOfWord(char c) {
   return (isalnum(c) || c == '-' || c == '_');
 }
 
-// Get the size of the prefix extension.
-static size_t CheckTypeSize(Check::CheckType Ty) {
-  switch (Ty) {
-  case Check::CheckNone:
-  case Check::CheckBadNot:
-    return 0;
-
-  case Check::CheckPlain:
-    return sizeof(":") - 1;
-
-  case Check::CheckNext:
-    return sizeof("-NEXT:") - 1;
+static Check::CheckType FindCheckType(StringRef Buffer, StringRef Prefix,
+                                      size_t &CheckTypeSize,
+                                      int &MinRepeatNumber,
+                                      int &MaxRepeatNumber) {
+  MinRepeatNumber = 0;
+  MaxRepeatNumber = -1;
+  CheckTypeSize = 0;
+  bool NextStatement = false;
 
-  case Check::CheckSame:
-    return sizeof("-SAME:") - 1;
+  size_t StringEnd = Buffer.find(':');
 
-  case Check::CheckNot:
-    return sizeof("-NOT:") - 1;
+  if (StringEnd == StringRef::npos) {
+    return Check::CheckNone;
+  }
+  std::string StringForMatch;
+  StringRef Rest;
 
-  case Check::CheckDAG:
-    return sizeof("-DAG:") - 1;
+  StringForMatch =
+      Buffer.substr(Prefix.size(), StringEnd - Prefix.size() + 1).str();
+  Rest = Buffer.drop_front(Prefix.size());
 
-  case Check::CheckLabel:
-    return sizeof("-LABEL:") - 1;
+  if (Rest.startswith("-NEXT")) {
+    CheckTypeSize += sizeof("-NEXT") - 1;
+    StringForMatch = StringForMatch.substr(5);
+    NextStatement = true;
+  }
 
-  case Check::CheckEOF:
-    llvm_unreachable("Should not be using EOF size");
+  SmallVector<StringRef, 20> Matches;
+  StringRef MatchedString = StringRef(StringForMatch);
+  // Verify that the : is present after the prefix.
+  if (MatchedString.startswith(":")) {
+    CheckTypeSize += 1;
+    if (NextStatement) {
+      return Check::CheckNext;
+    }
+    return Check::CheckPlain;
   }
   
-  llvm_unreachable("Bad check type");
+  if (Regex(StringRef("^((\\{([0-9]+)\\})|(\\{([0-9]*),([0-9]*)\\})):"),
+            Regex::Newline)
+          .match(MatchedString, &Matches)) {
+    CheckTypeSize += Matches[0].size();
+    // Was match with exact number.
+    if (Matches[3].size() != 0) {
+      MinRepeatNumber = std::stoi(Matches[3].str().c_str());
+      MaxRepeatNumber = MinRepeatNumber;
+    } else {
+      if (Matches[5].size() == 0 && Matches[6].size() == 0) {
+        return Check::CheckNone;
+      }
+      if (Matches[5].size() != 0) {
+        MinRepeatNumber = std::stoi(Matches[5].str().c_str());
+      }
+      if (Matches[6].size() != 0) {
+        MaxRepeatNumber = std::stoi(Matches[6].str().c_str());
+      }
     }
 
-static Check::CheckType FindCheckType(StringRef Buffer, StringRef Prefix) {
-  char NextChar = Buffer[Prefix.size()];
+    if (NextStatement) {
+      return Check::CheckNextRepeated;
+    }
+    return Check::CheckRepeated;
+  }
 
-  // Verify that the : is present after the prefix.
-  if (NextChar == ':')
-    return Check::CheckPlain;
+  if (MatchedString.startswith("*:")) {
+    CheckTypeSize += 2;
+    if (NextStatement) {
+      return Check::CheckNextRepeated;
+    }
+    return Check::CheckRepeated;
+  }
 
-  if (NextChar != '-')
-    return Check::CheckNone;
+  if (MatchedString.startswith("+:")) {
+    CheckTypeSize += 2;
+    MinRepeatNumber = 1;
+    if (NextStatement) {
+      return Check::CheckNextRepeated;
+    }
+    return Check::CheckRepeated;
+  }
 
-  StringRef Rest = Buffer.drop_front(Prefix.size() + 1);
-  if (Rest.startswith("NEXT:"))
-    return Check::CheckNext;
+  if (NextStatement) {
+    return Check::CheckBadNot;
+  }
 
-  if (Rest.startswith("SAME:"))
+  if (MatchedString.startswith("-SAME:")) {
+    CheckTypeSize = sizeof("-SAME:") - 1;
     return Check::CheckSame;
+  }
 
-  if (Rest.startswith("NOT:"))
+  if (MatchedString.startswith("-NOT:")) {
+    CheckTypeSize = sizeof("-NOT:") - 1;
     return Check::CheckNot;
+  }
 
-  if (Rest.startswith("DAG:"))
+  if (MatchedString.startswith("-DAG:")) {
+    CheckTypeSize = sizeof("-DAG:") - 1;
     return Check::CheckDAG;
+  }
 
-  if (Rest.startswith("LABEL:"))
+  if (MatchedString.startswith("-LABEL:")) {
+    CheckTypeSize = sizeof("-LABEL:") - 1;
     return Check::CheckLabel;
+  }
 
   // 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:"))
+  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;
 }
 
 // From the given position, find the next character after the word.
 static size_t SkipWord(StringRef Str, size_t Loc) {
   while (Loc < Str.size() && IsPartOfWord(Str[Loc]))
     ++Loc;
   return Loc;
 }
 
 // Try to find the first match in buffer for any prefix. If a valid match is
 // found, return that prefix and set its type and location.  If there are almost
 // matches (e.g. the actual prefix string is found, but is not an actual check
 // string), but no valid match, return an empty string and set the position to
 // resume searching from. If no partial matches are found, return an empty
 // string and the location will be StringRef::npos. If one prefix is a substring
 // of another, the maximal match should be found. e.g. if "A" and "AA" are
 // prefixes then AA-CHECK: should match the second one.
 static StringRef FindFirstCandidateMatch(StringRef &Buffer,
                                          Check::CheckType &CheckTy,
-                                         size_t &CheckLoc) {
+                                         size_t &CheckLoc,
+                                         size_t &CheckTypeSize,
+                                         int &MinRepeatNumber, 
+                                         int &MaxRepeatNumber) {
   StringRef FirstPrefix;
   size_t FirstLoc = StringRef::npos;
+  size_t FirstTypeSize = StringRef::npos;
   size_t SearchLoc = StringRef::npos;
   Check::CheckType FirstTy = Check::CheckNone;
 
   CheckTy = Check::CheckNone;
   CheckLoc = StringRef::npos;
 
   for (StringRef Prefix : CheckPrefixes) {
     size_t PrefixLoc = Buffer.find(Prefix);
for (StringRef Prefix : CheckPrefixes) {
 
     StringRef Rest = Buffer.drop_front(PrefixLoc);
     // Make sure we have actually found the prefix, and not a word containing
     // it. This should also prevent matching the wrong prefix when one is a
     // substring of another.
     if (PrefixLoc != 0 && IsPartOfWord(Buffer[PrefixLoc - 1]))
       FirstTy = Check::CheckNone;
     else
-      FirstTy = FindCheckType(Rest, Prefix);
+      FirstTy = FindCheckType(Rest, Prefix, FirstTypeSize, MinRepeatNumber,
+                              MaxRepeatNumber);
 
     FirstLoc = PrefixLoc;
     FirstPrefix = Prefix;
   }
 
   // If the first prefix is invalid, we should continue the search after it.
   if (FirstTy == Check::CheckNone) {
     CheckLoc = SearchLoc;
     return "";
   }
 
   CheckTy = FirstTy;
   CheckLoc = FirstLoc;
+  CheckTypeSize = FirstTypeSize;
   return FirstPrefix;
 }
 
 static StringRef FindFirstMatchingPrefix(StringRef &Buffer,
                                          unsigned &LineNumber,
                                          Check::CheckType &CheckTy,
-                                         size_t &CheckLoc) {
+                                         size_t &CheckLoc,
+                                         size_t &CheckTypeSize, 
+                                         int &MinRepeatNumber, 
+                                         int &MaxRepeatNumber) {
   while (!Buffer.empty()) {
-    StringRef Prefix = FindFirstCandidateMatch(Buffer, CheckTy, CheckLoc);
+    StringRef Prefix =
+        FindFirstCandidateMatch(Buffer, CheckTy, CheckLoc, CheckTypeSize,
+                                MinRepeatNumber, MaxRepeatNumber);
     // If we found a real match, we are done.
     if (!Prefix.empty()) {
       LineNumber += Buffer.substr(0, CheckLoc).count('\n');
       return Prefix;
     }
 
     // We didn't find any almost matches either, we are also done.
     if (CheckLoc == StringRef::npos)
static bool ReadCheckFile(SourceMgr &SM,
   std::vector<Pattern> DagNotMatches = ImplicitNegativeChecks;
 
   // LineNumber keeps track of the line on which CheckPrefix instances are
   // found.
   unsigned LineNumber = 1;
 
   while (1) {
     Check::CheckType CheckTy;
+    int MinRepeatNumber;
+    int MaxRepeatNumber;
     size_t PrefixLoc;
+    size_t CheckTypeSize;
 
     // See if a prefix occurs in the memory buffer.
     StringRef UsedPrefix = FindFirstMatchingPrefix(Buffer,
                                                    LineNumber,
                                                    CheckTy,
-                                                   PrefixLoc);
+                                                   PrefixLoc, 
+                                                   CheckTypeSize,
+                                                   MinRepeatNumber,
+                                                   MaxRepeatNumber);
     if (UsedPrefix.empty())
       break;
 
     Buffer = Buffer.drop_front(PrefixLoc);
 
     // Location to use for error messages.
     const char *UsedPrefixStart = Buffer.data() + (PrefixLoc == 0 ? 0 : 1);
 
     // PrefixLoc is to the start of the prefix. Skip to the end.
-    Buffer = Buffer.drop_front(UsedPrefix.size() + CheckTypeSize(CheckTy));
+    Buffer = Buffer.drop_front(UsedPrefix.size() + CheckTypeSize);
 
     // Complain about useful-looking but unsupported suffixes.
     if (CheckTy == Check::CheckBadNot) {
       SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()),
                       SourceMgr::DK_Error,
                       "unsupported -NOT combo on prefix '" + UsedPrefix + "'");
       return true;
     }
 
     // Okay, we found the prefix, yay. Remember the rest of the line, but ignore
     // leading and trailing whitespace.
     Buffer = Buffer.substr(Buffer.find_first_not_of(" \t"));
 
     // Scan ahead to the end of line.
     size_t EOL = Buffer.find_first_of("\n\r");
 
     // Remember the location of the start of the pattern, for diagnostics.
     SMLoc PatternLoc = SMLoc::getFromPointer(Buffer.data());
 
     // Parse the pattern.
-    Pattern P(CheckTy);
+    Pattern P(CheckTy, MinRepeatNumber, MaxRepeatNumber);
     if (P.ParsePattern(Buffer.substr(0, EOL), UsedPrefix, SM, LineNumber))
       return true;
 
     // Verify that CHECK-LABEL lines do not define or use variables
     if ((CheckTy == Check::CheckLabel) && P.hasVariable()) {
       SM.PrintMessage(SMLoc::getFromPointer(UsedPrefixStart),
                       SourceMgr::DK_Error,
                       "found '" + UsedPrefix + "-LABEL:'"
                       " with variable definition or use");
       return true;
     }
 
     Buffer = Buffer.substr(EOL);
 
     // Verify that CHECK-NEXT lines have at least one CHECK line before them.
-    if ((CheckTy == Check::CheckNext || CheckTy == Check::CheckSame) &&
+    if ((CheckTy == Check::CheckNext || CheckTy == Check::CheckNextRepeated ||
+         CheckTy == Check::CheckSame) &&
         CheckStrings.empty()) {
-      StringRef Type = CheckTy == Check::CheckNext ? "NEXT" : "SAME";
+      StringRef Type =
+          CheckTy == Check::CheckNext || CheckTy == Check::CheckNextRepeated
+              ? "NEXT"
+              : "SAME";
       SM.PrintMessage(SMLoc::getFromPointer(UsedPrefixStart),
                       SourceMgr::DK_Error,
                       "found '" + UsedPrefix + "-" + Type + "' without previous '"
                       + UsedPrefix + ": line");
       return true;
     }
 
     // Handle CHECK-DAG/-NOT.
size_t CheckString::Check(const SourceMgr &SM, StringRef Buffer,
   // over the block again (including the last CHECK-LABEL) in normal mode.
   if (!IsLabelScanMode) {
     // Match "dag strings" (with mixed "not strings" if any).
     LastPos = CheckDag(SM, Buffer, NotStrings, VariableTable);
     if (LastPos == StringRef::npos)
       return StringRef::npos;
   }
 
-  // Match itself from the last position after matching CHECK-DAG.
   StringRef MatchBuffer = Buffer.substr(LastPos);
+
+  // If pattern should be checked several times.
+  if (Pat.getCheckTy() == Check::CheckType::CheckRepeated ||
+      Pat.getCheckTy() == Check::CheckType::CheckNextRepeated) {
+    size_t MatchPos = 0;
+    int count = 0;
+    size_t PrevMatchLen = 0;
+    bool NextFall = false;
+    size_t BackupMatchLen = MatchLen;
+    size_t BackupMatchPos = MatchPos;
+    size_t BackupPrevMatchLen = MatchLen;
+
+    // Match much as possible.
+    while (
+        MatchPos != StringRef::npos && !NextFall &&
+        (Pat.getMaxRepeatNumber() == -1 || count < Pat.getMaxRepeatNumber())) {
+      StringRef MatchBuffer = Buffer.substr(LastPos);
+      BackupMatchLen = MatchLen;
+      BackupMatchPos = MatchPos;
+      MatchPos = Pat.Match(MatchBuffer, MatchLen, VariableTable);
+      if (MatchPos != StringRef::npos) {
+        BackupPrevMatchLen = PrevMatchLen;
+        PrevMatchLen = MatchLen;
+        LastPos += MatchPos + MatchLen;
+        count++;
+      }
+      if (!IsLabelScanMode) {
+        StringRef SkippedRegion = Buffer.substr(LastPos, MatchPos);
+        if (CheckNext(SM, SkippedRegion)) {
+          NextFall = true;
+          MatchLen = BackupMatchLen;
+          MatchPos = BackupMatchPos;
+          PrevMatchLen = BackupPrevMatchLen;
+        }
+      }
+
+    }
+
+    if (count < Pat.getMinRepeatNumber()) {
+      PrintCheckFailed(SM, *this, MatchBuffer, VariableTable);
+      return StringRef::npos;
+    }
+
+    return LastPos - PrevMatchLen;
+  }
+
+  // Match itself from the last position after matching CHECK-DAG.
+  MatchBuffer = Buffer.substr(LastPos);
   size_t MatchPos = Pat.Match(MatchBuffer, MatchLen, VariableTable);
   if (MatchPos == StringRef::npos) {
     PrintCheckFailed(SM, *this, MatchBuffer, VariableTable);
     return StringRef::npos;
   }
 
   // Similar to the above, in "label-scan mode" we can't yet handle CHECK-NEXT
   // or CHECK-NOT
if (!IsLabelScanMode) {
     if (CheckNot(SM, SkippedRegion, NotStrings, VariableTable))
       return StringRef::npos;
   }
 
   return LastPos + MatchPos;
 }
 
 bool CheckString::CheckNext(const SourceMgr &SM, StringRef Buffer) const {
-  if (Pat.getCheckTy() != Check::CheckNext)
+  if (Pat.getCheckTy() != Check::CheckNext &&
+      Pat.getCheckTy() != Check::CheckNextRepeated)
     return false;
 
   // Count the number of newlines between the previous match and this one.
   assert(Buffer.data() !=
          SM.getMemoryBuffer(
            SM.FindBufferContainingLoc(
              SMLoc::getFromPointer(Buffer.data())))->getBufferStart() &&
          "CHECK-NEXT can't be the first check in a file");