FileCheck Enhancement - Expressions repeat for CHECK and CHECK-NEXT

[eklepilkina]

Summary

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

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");