Revert "[FileCheck] Implement --ignore-case option."

This reverts commit r374339. It broke tests:
http://lab.llvm.org:8011/builders/clang-x86_64-debian-fast/builds/19066

llvm-svn: 374359

2 files changed, 2606 insertions, 2614 deletions

diff --git a/llvm/lib/Support/FileCheck.cpp b/llvm/lib/Support/FileCheck.cpp
index fb4bbba033b..c3f537b3524 100644
--- a/llvm/lib/Support/FileCheck.cpp
+++ b/llvm/lib/Support/FileCheck.cpp
@@ -1,1990 +1,1985 @@
-//===- FileCheck.cpp - Check that File's Contents match what is expected --===//

-//

-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

-// See https://llvm.org/LICENSE.txt for license information.

-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

-//

-//===----------------------------------------------------------------------===//

-//

-// FileCheck does a line-by line check of a file that validates whether it

-// contains the expected content.  This is useful for regression tests etc.

-//

-// This file implements most of the API that will be used by the FileCheck utility

-// as well as various unittests.

-//===----------------------------------------------------------------------===//

-

-#include "llvm/Support/FileCheck.h"

-#include "FileCheckImpl.h"

-#include "llvm/ADT/StringSet.h"

-#include "llvm/ADT/Twine.h"

-#include "llvm/Support/FormatVariadic.h"

-#include <cstdint>

-#include <list>

-#include <tuple>

-#include <utility>

-

-using namespace llvm;

-

-Expected<uint64_t> FileCheckNumericVariableUse::eval() const {

-  Optional<uint64_t> Value = NumericVariable->getValue();

-  if (Value)

-    return *Value;

-

-  return make_error<FileCheckUndefVarError>(Name);

-}

-

-Expected<uint64_t> FileCheckASTBinop::eval() const {

-  Expected<uint64_t> LeftOp = LeftOperand->eval();

-  Expected<uint64_t> RightOp = RightOperand->eval();

-

-  // Bubble up any error (e.g. undefined variables) in the recursive

-  // evaluation.

-  if (!LeftOp || !RightOp) {

-    Error Err = Error::success();

-    if (!LeftOp)

-      Err = joinErrors(std::move(Err), LeftOp.takeError());

-    if (!RightOp)

-      Err = joinErrors(std::move(Err), RightOp.takeError());

-    return std::move(Err);

-  }

-

-  return EvalBinop(*LeftOp, *RightOp);

-}

-

-Expected<std::string> FileCheckNumericSubstitution::getResult() const {

-  Expected<uint64_t> EvaluatedValue = ExpressionAST->eval();

-  if (!EvaluatedValue)

-    return EvaluatedValue.takeError();

-  return utostr(*EvaluatedValue);

-}

-

-Expected<std::string> FileCheckStringSubstitution::getResult() const {

-  // Look up the value and escape it so that we can put it into the regex.

-  Expected<StringRef> VarVal = Context->getPatternVarValue(FromStr);

-  if (!VarVal)

-    return VarVal.takeError();

-  return Regex::escape(*VarVal);

-}

-

-bool FileCheckPattern::isValidVarNameStart(char C) {

-  return C == '_' || isalpha(C);

-}

-

-Expected<FileCheckPattern::VariableProperties>

-FileCheckPattern::parseVariable(StringRef &Str, const SourceMgr &SM) {

-  if (Str.empty())

-    return FileCheckErrorDiagnostic::get(SM, Str, "empty variable name");

-

-  bool ParsedOneChar = false;

-  unsigned I = 0;

-  bool IsPseudo = Str[0] == '@';

-

-  // Global vars start with '$'.

-  if (Str[0] == '$' || IsPseudo)

-    ++I;

-

-  for (unsigned E = Str.size(); I != E; ++I) {

-    if (!ParsedOneChar && !isValidVarNameStart(Str[I]))

-      return FileCheckErrorDiagnostic::get(SM, Str, "invalid variable name");

-

-    // Variable names are composed of alphanumeric characters and underscores.

-    if (Str[I] != '_' && !isalnum(Str[I]))

-      break;

-    ParsedOneChar = true;

-  }

-

-  StringRef Name = Str.take_front(I);

-  Str = Str.substr(I);

-  return VariableProperties {Name, IsPseudo};

-}

-

-// StringRef holding all characters considered as horizontal whitespaces by

-// FileCheck input canonicalization.

-constexpr StringLiteral SpaceChars = " \t";

-

-// Parsing helper function that strips the first character in S and returns it.

-static char popFront(StringRef &S) {

-  char C = S.front();

-  S = S.drop_front();

-  return C;

-}

-

-char FileCheckUndefVarError::ID = 0;

-char FileCheckErrorDiagnostic::ID = 0;

-char FileCheckNotFoundError::ID = 0;

-

-Expected<FileCheckNumericVariable *>

-FileCheckPattern::parseNumericVariableDefinition(

-    StringRef &Expr, FileCheckPatternContext *Context,

-    Optional<size_t> LineNumber, const SourceMgr &SM) {

-  Expected<VariableProperties> ParseVarResult = parseVariable(Expr, SM);

-  if (!ParseVarResult)

-    return ParseVarResult.takeError();

-  StringRef Name = ParseVarResult->Name;

-

-  if (ParseVarResult->IsPseudo)

-    return FileCheckErrorDiagnostic::get(

-        SM, Name, "definition of pseudo numeric variable unsupported");

-

-  // Detect collisions between string and numeric variables when the latter

-  // is created later than the former.

-  if (Context->DefinedVariableTable.find(Name) !=

-      Context->DefinedVariableTable.end())

-    return FileCheckErrorDiagnostic::get(

-        SM, Name, "string variable with name '" + Name + "' already exists");

-

-  Expr = Expr.ltrim(SpaceChars);

-  if (!Expr.empty())

-    return FileCheckErrorDiagnostic::get(

-        SM, Expr, "unexpected characters after numeric variable name");

-

-  FileCheckNumericVariable *DefinedNumericVariable;

-  auto VarTableIter = Context->GlobalNumericVariableTable.find(Name);

-  if (VarTableIter != Context->GlobalNumericVariableTable.end())

-    DefinedNumericVariable = VarTableIter->second;

-  else

-    DefinedNumericVariable = Context->makeNumericVariable(Name, LineNumber);

-

-  return DefinedNumericVariable;

-}

-

-Expected<std::unique_ptr<FileCheckNumericVariableUse>>

-FileCheckPattern::parseNumericVariableUse(StringRef Name, bool IsPseudo,

-                                          Optional<size_t> LineNumber,

-                                          FileCheckPatternContext *Context,

-                                          const SourceMgr &SM) {

-  if (IsPseudo && !Name.equals("@LINE"))

-    return FileCheckErrorDiagnostic::get(

-        SM, Name, "invalid pseudo numeric variable '" + Name + "'");

-

-  // Numeric variable definitions and uses are parsed in the order in which

-  // they appear in the CHECK patterns. For each definition, the pointer to the

-  // class instance of the corresponding numeric variable definition is stored

-  // in GlobalNumericVariableTable in parsePattern. Therefore, if the pointer

-  // we get below is null, it means no such variable was defined before. When

-  // that happens, we create a dummy variable so that parsing can continue. All

-  // uses of undefined variables, whether string or numeric, are then diagnosed

-  // in printSubstitutions() after failing to match.

-  auto VarTableIter = Context->GlobalNumericVariableTable.find(Name);

-  FileCheckNumericVariable *NumericVariable;

-  if (VarTableIter != Context->GlobalNumericVariableTable.end())

-    NumericVariable = VarTableIter->second;

-  else {

-    NumericVariable = Context->makeNumericVariable(Name);

-    Context->GlobalNumericVariableTable[Name] = NumericVariable;

-  }

-

-  Optional<size_t> DefLineNumber = NumericVariable->getDefLineNumber();

-  if (DefLineNumber && LineNumber && *DefLineNumber == *LineNumber)

-    return FileCheckErrorDiagnostic::get(

-        SM, Name,

-        "numeric variable '" + Name +

-            "' defined earlier in the same CHECK directive");

-

-  return std::make_unique<FileCheckNumericVariableUse>(Name, NumericVariable);

-}

-

-Expected<std::unique_ptr<FileCheckExpressionAST>>

-FileCheckPattern::parseNumericOperand(StringRef &Expr, AllowedOperand AO,

-                                      Optional<size_t> LineNumber,

-                                      FileCheckPatternContext *Context,

-                                      const SourceMgr &SM) {

-  if (AO == AllowedOperand::LineVar || AO == AllowedOperand::Any) {

-    // Try to parse as a numeric variable use.

-    Expected<FileCheckPattern::VariableProperties> ParseVarResult =

-        parseVariable(Expr, SM);

-    if (ParseVarResult)

-      return parseNumericVariableUse(ParseVarResult->Name,

-                                     ParseVarResult->IsPseudo, LineNumber,

-                                     Context, SM);

-    if (AO == AllowedOperand::LineVar)

-      return ParseVarResult.takeError();

-    // Ignore the error and retry parsing as a literal.

-    consumeError(ParseVarResult.takeError());

-  }

-

-  // Otherwise, parse it as a literal.

-  uint64_t LiteralValue;

-  if (!Expr.consumeInteger(/*Radix=*/10, LiteralValue))

-    return std::make_unique<FileCheckExpressionLiteral>(LiteralValue);

-

-  return FileCheckErrorDiagnostic::get(SM, Expr,

-                                       "invalid operand format '" + Expr + "'");

-}

-

-static uint64_t add(uint64_t LeftOp, uint64_t RightOp) {

-  return LeftOp + RightOp;

-}

-

-static uint64_t sub(uint64_t LeftOp, uint64_t RightOp) {

-  return LeftOp - RightOp;

-}

-

-Expected<std::unique_ptr<FileCheckExpressionAST>> FileCheckPattern::parseBinop(

-    StringRef &Expr, std::unique_ptr<FileCheckExpressionAST> LeftOp,

-    bool IsLegacyLineExpr, Optional<size_t> LineNumber,

-    FileCheckPatternContext *Context, const SourceMgr &SM) {

-  Expr = Expr.ltrim(SpaceChars);

-  if (Expr.empty())

-    return std::move(LeftOp);

-

-  // Check if this is a supported operation and select a function to perform

-  // it.

-  SMLoc OpLoc = SMLoc::getFromPointer(Expr.data());

-  char Operator = popFront(Expr);

-  binop_eval_t EvalBinop;

-  switch (Operator) {

-  case '+':

-    EvalBinop = add;

-    break;

-  case '-':

-    EvalBinop = sub;

-    break;

-  default:

-    return FileCheckErrorDiagnostic::get(

-        SM, OpLoc, Twine("unsupported operation '") + Twine(Operator) + "'");

-  }

-

-  // Parse right operand.

-  Expr = Expr.ltrim(SpaceChars);

-  if (Expr.empty())

-    return FileCheckErrorDiagnostic::get(SM, Expr,

-                                         "missing operand in expression");

-  // The second operand in a legacy @LINE expression is always a literal.

-  AllowedOperand AO =

-      IsLegacyLineExpr ? AllowedOperand::Literal : AllowedOperand::Any;

-  Expected<std::unique_ptr<FileCheckExpressionAST>> RightOpResult =

-      parseNumericOperand(Expr, AO, LineNumber, Context, SM);

-  if (!RightOpResult)

-    return RightOpResult;

-

-  Expr = Expr.ltrim(SpaceChars);

-  return std::make_unique<FileCheckASTBinop>(EvalBinop, std::move(LeftOp),

-                                              std::move(*RightOpResult));

-}

-

-Expected<std::unique_ptr<FileCheckExpressionAST>>

-FileCheckPattern::parseNumericSubstitutionBlock(

-    StringRef Expr,

-    Optional<FileCheckNumericVariable *> &DefinedNumericVariable,

-    bool IsLegacyLineExpr, Optional<size_t> LineNumber,

-    FileCheckPatternContext *Context, const SourceMgr &SM) {

-  std::unique_ptr<FileCheckExpressionAST> ExpressionAST = nullptr;

-  StringRef DefExpr = StringRef();

-  DefinedNumericVariable = None;

-  // Save variable definition expression if any.

-  size_t DefEnd = Expr.find(':');

-  if (DefEnd != StringRef::npos) {

-    DefExpr = Expr.substr(0, DefEnd);

-    Expr = Expr.substr(DefEnd + 1);

-  }

-

-  // Parse the expression itself.

-  Expr = Expr.ltrim(SpaceChars);

-  if (!Expr.empty()) {

-    // The first operand in a legacy @LINE expression is always the @LINE

-    // pseudo variable.

-    AllowedOperand AO =

-        IsLegacyLineExpr ? AllowedOperand::LineVar : AllowedOperand::Any;

-    Expected<std::unique_ptr<FileCheckExpressionAST>> ParseResult =

-        parseNumericOperand(Expr, AO, LineNumber, Context, SM);

-    while (ParseResult && !Expr.empty()) {

-      ParseResult = parseBinop(Expr, std::move(*ParseResult), IsLegacyLineExpr,

-                               LineNumber, Context, SM);

-      // Legacy @LINE expressions only allow 2 operands.

-      if (ParseResult && IsLegacyLineExpr && !Expr.empty())

-        return FileCheckErrorDiagnostic::get(

-            SM, Expr,

-            "unexpected characters at end of expression '" + Expr + "'");

-    }

-    if (!ParseResult)

-      return ParseResult;

-    ExpressionAST = std::move(*ParseResult);

-  }

-

-  // Parse the numeric variable definition.

-  if (DefEnd != StringRef::npos) {

-    DefExpr = DefExpr.ltrim(SpaceChars);

-    Expected<FileCheckNumericVariable *> ParseResult =

-        parseNumericVariableDefinition(DefExpr, Context, LineNumber, SM);

-

-    if (!ParseResult)

-      return ParseResult.takeError();

-    DefinedNumericVariable = *ParseResult;

-  }

-

-  return std::move(ExpressionAST);

-}

-

-bool FileCheckPattern::parsePattern(StringRef PatternStr, StringRef Prefix,

-                                    SourceMgr &SM,

-                                    const FileCheckRequest &Req) {

-  bool MatchFullLinesHere = Req.MatchFullLines && CheckTy != Check::CheckNot;

-  IgnoreCase = Req.IgnoreCase;

-

-  PatternLoc = SMLoc::getFromPointer(PatternStr.data());

-

-  if (!(Req.NoCanonicalizeWhiteSpace && Req.MatchFullLines))

-    // Ignore trailing whitespace.

-    while (!PatternStr.empty() &&

-           (PatternStr.back() == ' ' || PatternStr.back() == '\t'))

-      PatternStr = PatternStr.substr(0, PatternStr.size() - 1);

-

-  // Check that there is something on the line.

-  if (PatternStr.empty() && CheckTy != Check::CheckEmpty) {

-    SM.PrintMessage(PatternLoc, SourceMgr::DK_Error,

-                    "found empty check string with prefix '" + Prefix + ":'");

-    return true;

-  }

-

-  if (!PatternStr.empty() && CheckTy == Check::CheckEmpty) {

-    SM.PrintMessage(

-        PatternLoc, SourceMgr::DK_Error,

-        "found non-empty check string for empty check with prefix '" + Prefix +

-            ":'");

-    return true;

-  }

-

-  if (CheckTy == Check::CheckEmpty) {

-    RegExStr = "(\n$)";

-    return false;

-  }

-

-  // Check to see if this is a fixed string, or if it has regex pieces.

-  if (!MatchFullLinesHere &&

-      (PatternStr.size() < 2 || (PatternStr.find("{{") == StringRef::npos &&

-                                 PatternStr.find("[[") == StringRef::npos))) {

-    FixedStr = PatternStr;

-    return false;

-  }

-

-  if (MatchFullLinesHere) {

-    RegExStr += '^';

-    if (!Req.NoCanonicalizeWhiteSpace)

-      RegExStr += " *";

-  }

-

-  // Paren value #0 is for the fully matched string.  Any new parenthesized

-  // values add from there.

-  unsigned CurParen = 1;

-

-  // Otherwise, there is at least one regex piece.  Build up the regex pattern

-  // by escaping scary characters in fixed strings, building up one big regex.

-  while (!PatternStr.empty()) {

-    // RegEx matches.

-    if (PatternStr.startswith("{{")) {

-      // This is the start of a regex match.  Scan for the }}.

-      size_t End = PatternStr.find("}}");

-      if (End == StringRef::npos) {

-        SM.PrintMessage(SMLoc::getFromPointer(PatternStr.data()),

-                        SourceMgr::DK_Error,

-                        "found start of regex string with no end '}}'");

-        return true;

-      }

-

-      // Enclose {{}} patterns in parens just like [[]] even though we're not

-      // capturing the result for any purpose.  This is required in case the

-      // expression contains an alternation like: CHECK:  abc{{x|z}}def.  We

-      // want this to turn into: "abc(x|z)def" not "abcx|zdef".

-      RegExStr += '(';

-      ++CurParen;

-

-      if (AddRegExToRegEx(PatternStr.substr(2, End - 2), CurParen, SM))

-        return true;

-      RegExStr += ')';

-

-      PatternStr = PatternStr.substr(End + 2);

-      continue;

-    }

-

-    // String and numeric substitution blocks. Pattern substitution blocks come

-    // in two forms: [[foo:.*]] and [[foo]]. The former matches .* (or some

-    // other regex) and assigns it to the string variable 'foo'. The latter

-    // substitutes foo's value. Numeric substitution blocks recognize the same

-    // form as string ones, but start with a '#' sign after the double

-    // brackets. They also accept a combined form which sets a numeric variable

-    // to the evaluation of an expression. Both string and numeric variable

-    // names must satisfy the regular expression "[a-zA-Z_][0-9a-zA-Z_]*" to be

-    // valid, as this helps catch some common errors.

-    if (PatternStr.startswith("[[")) {

-      StringRef UnparsedPatternStr = PatternStr.substr(2);

-      // Find the closing bracket pair ending the match.  End is going to be an

-      // offset relative to the beginning of the match string.

-      size_t End = FindRegexVarEnd(UnparsedPatternStr, SM);

-      StringRef MatchStr = UnparsedPatternStr.substr(0, End);

-      bool IsNumBlock = MatchStr.consume_front("#");

-

-      if (End == StringRef::npos) {

-        SM.PrintMessage(SMLoc::getFromPointer(PatternStr.data()),

-                        SourceMgr::DK_Error,

-                        "Invalid substitution block, no ]] found");

-        return true;

-      }

-      // Strip the substitution block we are parsing. End points to the start

-      // of the "]]" closing the expression so account for it in computing the

-      // index of the first unparsed character.

-      PatternStr = UnparsedPatternStr.substr(End + 2);

-

-      bool IsDefinition = false;

-      bool SubstNeeded = false;

-      // Whether the substitution block is a legacy use of @LINE with string

-      // substitution block syntax.

-      bool IsLegacyLineExpr = false;

-      StringRef DefName;

-      StringRef SubstStr;

-      StringRef MatchRegexp;

-      size_t SubstInsertIdx = RegExStr.size();

-

-      // Parse string variable or legacy @LINE expression.

-      if (!IsNumBlock) {

-        size_t VarEndIdx = MatchStr.find(":");

-        size_t SpacePos = MatchStr.substr(0, VarEndIdx).find_first_of(" \t");

-        if (SpacePos != StringRef::npos) {

-          SM.PrintMessage(SMLoc::getFromPointer(MatchStr.data() + SpacePos),

-                          SourceMgr::DK_Error, "unexpected whitespace");

-          return true;

-        }

-

-        // Get the name (e.g. "foo") and verify it is well formed.

-        StringRef OrigMatchStr = MatchStr;

-        Expected<FileCheckPattern::VariableProperties> ParseVarResult =

-            parseVariable(MatchStr, SM);

-        if (!ParseVarResult) {

-          logAllUnhandledErrors(ParseVarResult.takeError(), errs());

-          return true;

-        }

-        StringRef Name = ParseVarResult->Name;

-        bool IsPseudo = ParseVarResult->IsPseudo;

-

-        IsDefinition = (VarEndIdx != StringRef::npos);

-        SubstNeeded = !IsDefinition;

-        if (IsDefinition) {

-          if ((IsPseudo || !MatchStr.consume_front(":"))) {

-            SM.PrintMessage(SMLoc::getFromPointer(Name.data()),

-                            SourceMgr::DK_Error,

-                            "invalid name in string variable definition");

-            return true;

-          }

-

-          // Detect collisions between string and numeric variables when the

-          // former is created later than the latter.

-          if (Context->GlobalNumericVariableTable.find(Name) !=

-              Context->GlobalNumericVariableTable.end()) {

-            SM.PrintMessage(

-                SMLoc::getFromPointer(Name.data()), SourceMgr::DK_Error,

-                "numeric variable with name '" + Name + "' already exists");

-            return true;

-          }

-          DefName = Name;

-          MatchRegexp = MatchStr;

-        } else {

-          if (IsPseudo) {

-            MatchStr = OrigMatchStr;

-            IsLegacyLineExpr = IsNumBlock = true;

-          } else

-            SubstStr = Name;

-        }

-      }

-

-      // Parse numeric substitution block.

-      std::unique_ptr<FileCheckExpressionAST> ExpressionAST;

-      Optional<FileCheckNumericVariable *> DefinedNumericVariable;

-      if (IsNumBlock) {

-        Expected<std::unique_ptr<FileCheckExpressionAST>> ParseResult =

-            parseNumericSubstitutionBlock(MatchStr, DefinedNumericVariable,

-                                          IsLegacyLineExpr, LineNumber, Context,

-                                          SM);

-        if (!ParseResult) {

-          logAllUnhandledErrors(ParseResult.takeError(), errs());

-          return true;

-        }

-        ExpressionAST = std::move(*ParseResult);

-        SubstNeeded = ExpressionAST != nullptr;

-        if (DefinedNumericVariable) {

-          IsDefinition = true;

-          DefName = (*DefinedNumericVariable)->getName();

-        }

-        if (SubstNeeded)

-          SubstStr = MatchStr;

-        else

-          MatchRegexp = "[0-9]+";

-      }

-

-      // Handle variable definition: [[<def>:(...)]] and [[#(...)<def>:(...)]].

-      if (IsDefinition) {

-        RegExStr += '(';

-        ++SubstInsertIdx;

-

-        if (IsNumBlock) {

-          FileCheckNumericVariableMatch NumericVariableDefinition = {

-              *DefinedNumericVariable, CurParen};

-          NumericVariableDefs[DefName] = NumericVariableDefinition;

-          // This store is done here rather than in match() to allow

-          // parseNumericVariableUse() to get the pointer to the class instance

-          // of the right variable definition corresponding to a given numeric

-          // variable use.

-          Context->GlobalNumericVariableTable[DefName] =

-              *DefinedNumericVariable;

-        } else {

-          VariableDefs[DefName] = CurParen;

-          // Mark string variable as defined to detect collisions between

-          // string and numeric variables in parseNumericVariableUse() and

-          // defineCmdlineVariables() when the latter is created later than the

-          // former. We cannot reuse GlobalVariableTable for this by populating

-          // it with an empty string since we would then lose the ability to

-          // detect the use of an undefined variable in match().

-          Context->DefinedVariableTable[DefName] = true;

-        }

-

-        ++CurParen;

-      }

-

-      if (!MatchRegexp.empty() && AddRegExToRegEx(MatchRegexp, CurParen, SM))

-        return true;

-

-      if (IsDefinition)

-        RegExStr += ')';

-

-      // Handle substitutions: [[foo]] and [[#<foo expr>]].

-      if (SubstNeeded) {

-        // Handle substitution of string variables that were defined earlier on

-        // the same line by emitting a backreference. Expressions do not

-        // support substituting a numeric variable defined on the same line.

-        if (!IsNumBlock && VariableDefs.find(SubstStr) != VariableDefs.end()) {

-          unsigned CaptureParenGroup = VariableDefs[SubstStr];

-          if (CaptureParenGroup < 1 || CaptureParenGroup > 9) {

-            SM.PrintMessage(SMLoc::getFromPointer(SubstStr.data()),

-                            SourceMgr::DK_Error,

-                            "Can't back-reference more than 9 variables");

-            return true;

-          }

-          AddBackrefToRegEx(CaptureParenGroup);

-        } else {

-          // Handle substitution of string variables ([[<var>]]) defined in

-          // previous CHECK patterns, and substitution of expressions.

-          FileCheckSubstitution *Substitution =

-              IsNumBlock

-                  ? Context->makeNumericSubstitution(

-                        SubstStr, std::move(ExpressionAST), SubstInsertIdx)

-                  : Context->makeStringSubstitution(SubstStr, SubstInsertIdx);

-          Substitutions.push_back(Substitution);

-        }

-      }

-    }

-

-    // Handle fixed string matches.

-    // Find the end, which is the start of the next regex.

-    size_t FixedMatchEnd = PatternStr.find("{{");

-    FixedMatchEnd = std::min(FixedMatchEnd, PatternStr.find("[["));

-    RegExStr += Regex::escape(PatternStr.substr(0, FixedMatchEnd));

-    PatternStr = PatternStr.substr(FixedMatchEnd);

-  }

-

-  if (MatchFullLinesHere) {

-    if (!Req.NoCanonicalizeWhiteSpace)

-      RegExStr += " *";

-    RegExStr += '$';

-  }

-

-  return false;

-}

-

-bool FileCheckPattern::AddRegExToRegEx(StringRef RS, unsigned &CurParen, SourceMgr &SM) {

-  Regex R(RS);

-  std::string Error;

-  if (!R.isValid(Error)) {

-    SM.PrintMessage(SMLoc::getFromPointer(RS.data()), SourceMgr::DK_Error,

-                    "invalid regex: " + Error);

-    return true;

-  }

-

-  RegExStr += RS.str();

-  CurParen += R.getNumMatches();

-  return false;

-}

-

-void FileCheckPattern::AddBackrefToRegEx(unsigned BackrefNum) {

-  assert(BackrefNum >= 1 && BackrefNum <= 9 && "Invalid backref number");

-  std::string Backref = std::string("\\") + std::string(1, '0' + BackrefNum);

-  RegExStr += Backref;

-}

-

-Expected<size_t> FileCheckPattern::match(StringRef Buffer, size_t &MatchLen,

-                                         const SourceMgr &SM) const {

-  // If this is the EOF pattern, match it immediately.

-  if (CheckTy == Check::CheckEOF) {

-    MatchLen = 0;

-    return Buffer.size();

-  }

-

-  // If this is a fixed string pattern, just match it now.

-  if (!FixedStr.empty()) {

-    MatchLen = FixedStr.size();

-    size_t Pos = IgnoreCase ? Buffer.find_lower(FixedStr)

-                            : Buffer.find(FixedStr);

-    if (Pos == StringRef::npos)

-      return make_error<FileCheckNotFoundError>();

-    return Pos;

-  }

-

-  // Regex match.

-

-  // If there are substitutions, we need to create a temporary string with the

-  // actual value.

-  StringRef RegExToMatch = RegExStr;

-  std::string TmpStr;

-  if (!Substitutions.empty()) {

-    TmpStr = RegExStr;

-    if (LineNumber)

-      Context->LineVariable->setValue(*LineNumber);

-

-    size_t InsertOffset = 0;

-    // Substitute all string variables and expressions whose values are only

-    // now known. Use of string variables defined on the same line are handled

-    // by back-references.

-    for (const auto &Substitution : Substitutions) {

-      // Substitute and check for failure (e.g. use of undefined variable).

-      Expected<std::string> Value = Substitution->getResult();

-      if (!Value)

-        return Value.takeError();

-

-      // Plop it into the regex at the adjusted offset.

-      TmpStr.insert(TmpStr.begin() + Substitution->getIndex() + InsertOffset,

-                    Value->begin(), Value->end());

-      InsertOffset += Value->size();

-    }

-

-    // Match the newly constructed regex.

-    RegExToMatch = TmpStr;

-  }

-

-  SmallVector<StringRef, 4> MatchInfo;

-  unsigned int Flags = Regex::Newline;

-  if (IgnoreCase)

-    Flags |= Regex::IgnoreCase;

-  if (!Regex(RegExToMatch, Flags).match(Buffer, &MatchInfo))

-    return make_error<FileCheckNotFoundError>();

-

-  // Successful regex match.

-  assert(!MatchInfo.empty() && "Didn't get any match");

-  StringRef FullMatch = MatchInfo[0];

-

-  // If this defines any string variables, remember their values.

-  for (const auto &VariableDef : VariableDefs) {

-    assert(VariableDef.second < MatchInfo.size() && "Internal paren error");

-    Context->GlobalVariableTable[VariableDef.first] =

-        MatchInfo[VariableDef.second];

-  }

-

-  // If this defines any numeric variables, remember their values.

-  for (const auto &NumericVariableDef : NumericVariableDefs) {

-    const FileCheckNumericVariableMatch &NumericVariableMatch =

-        NumericVariableDef.getValue();

-    unsigned CaptureParenGroup = NumericVariableMatch.CaptureParenGroup;

-    assert(CaptureParenGroup < MatchInfo.size() && "Internal paren error");

-    FileCheckNumericVariable *DefinedNumericVariable =

-        NumericVariableMatch.DefinedNumericVariable;

-

-    StringRef MatchedValue = MatchInfo[CaptureParenGroup];

-    uint64_t Val;

-    if (MatchedValue.getAsInteger(10, Val))

-      return FileCheckErrorDiagnostic::get(SM, MatchedValue,

-                                           "Unable to represent numeric value");

-    DefinedNumericVariable->setValue(Val);

-  }

-

-  // Like CHECK-NEXT, CHECK-EMPTY's match range is considered to start after

-  // the required preceding newline, which is consumed by the pattern in the

-  // case of CHECK-EMPTY but not CHECK-NEXT.

-  size_t MatchStartSkip = CheckTy == Check::CheckEmpty;

-  MatchLen = FullMatch.size() - MatchStartSkip;

-  return FullMatch.data() - Buffer.data() + MatchStartSkip;

-}

-

-unsigned FileCheckPattern::computeMatchDistance(StringRef Buffer) const {

-  // Just compute the number of matching characters. For regular expressions, we

-  // just compare against the regex itself and hope for the best.

-  //

-  // FIXME: One easy improvement here is have the regex lib generate a single

-  // example regular expression which matches, and use that as the example

-  // string.

-  StringRef ExampleString(FixedStr);

-  if (ExampleString.empty())

-    ExampleString = RegExStr;

-

-  // Only compare up to the first line in the buffer, or the string size.

-  StringRef BufferPrefix = Buffer.substr(0, ExampleString.size());

-  BufferPrefix = BufferPrefix.split('\n').first;

-  return BufferPrefix.edit_distance(ExampleString);

-}

-

-void FileCheckPattern::printSubstitutions(const SourceMgr &SM, StringRef Buffer,

-                                          SMRange MatchRange) const {

-  // Print what we know about substitutions.

-  if (!Substitutions.empty()) {

-    for (const auto &Substitution : Substitutions) {

-      SmallString<256> Msg;

-      raw_svector_ostream OS(Msg);

-      Expected<std::string> MatchedValue = Substitution->getResult();

-

-      // Substitution failed or is not known at match time, print the undefined

-      // variables it uses.

-      if (!MatchedValue) {

-        bool UndefSeen = false;

-        handleAllErrors(MatchedValue.takeError(),

-                        [](const FileCheckNotFoundError &E) {},

-                        // Handled in PrintNoMatch().

-                        [](const FileCheckErrorDiagnostic &E) {},

-                        [&](const FileCheckUndefVarError &E) {

-                          if (!UndefSeen) {

-                            OS << "uses undefined variable(s):";

-                            UndefSeen = true;

-                          }

-                          OS << " ";

-                          E.log(OS);

-                        });

-      } else {

-        // Substitution succeeded. Print substituted value.

-        OS << "with \"";

-        OS.write_escaped(Substitution->getFromString()) << "\" equal to \"";

-        OS.write_escaped(*MatchedValue) << "\"";

-      }

-

-      if (MatchRange.isValid())

-        SM.PrintMessage(MatchRange.Start, SourceMgr::DK_Note, OS.str(),

-                        {MatchRange});

-      else

-        SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()),

-                        SourceMgr::DK_Note, OS.str());

-    }

-  }

-}

-

-static SMRange ProcessMatchResult(FileCheckDiag::MatchType MatchTy,

-                                  const SourceMgr &SM, SMLoc Loc,

-                                  Check::FileCheckType CheckTy,

-                                  StringRef Buffer, size_t Pos, size_t Len,

-                                  std::vector<FileCheckDiag> *Diags,

-                                  bool AdjustPrevDiag = false) {

-  SMLoc Start = SMLoc::getFromPointer(Buffer.data() + Pos);

-  SMLoc End = SMLoc::getFromPointer(Buffer.data() + Pos + Len);

-  SMRange Range(Start, End);

-  if (Diags) {

-    if (AdjustPrevDiag)

-      Diags->rbegin()->MatchTy = MatchTy;

-    else

-      Diags->emplace_back(SM, CheckTy, Loc, MatchTy, Range);

-  }

-  return Range;

-}

-

-void FileCheckPattern::printFuzzyMatch(

-    const SourceMgr &SM, StringRef Buffer,

-    std::vector<FileCheckDiag> *Diags) const {

-  // Attempt to find the closest/best fuzzy match.  Usually an error happens

-  // because some string in the output didn't exactly match. In these cases, we

-  // would like to show the user a best guess at what "should have" matched, to

-  // save them having to actually check the input manually.

-  size_t NumLinesForward = 0;

-  size_t Best = StringRef::npos;

-  double BestQuality = 0;

-

-  // Use an arbitrary 4k limit on how far we will search.

-  for (size_t i = 0, e = std::min(size_t(4096), Buffer.size()); i != e; ++i) {

-    if (Buffer[i] == '\n')

-      ++NumLinesForward;

-

-    // Patterns have leading whitespace stripped, so skip whitespace when

-    // looking for something which looks like a pattern.

-    if (Buffer[i] == ' ' || Buffer[i] == '\t')

-      continue;

-

-    // Compute the "quality" of this match as an arbitrary combination of the

-    // match distance and the number of lines skipped to get to this match.

-    unsigned Distance = computeMatchDistance(Buffer.substr(i));

-    double Quality = Distance + (NumLinesForward / 100.);

-

-    if (Quality < BestQuality || Best == StringRef::npos) {

-      Best = i;

-      BestQuality = Quality;

-    }

-  }

-

-  // Print the "possible intended match here" line if we found something

-  // reasonable and not equal to what we showed in the "scanning from here"

-  // line.

-  if (Best && Best != StringRef::npos && BestQuality < 50) {

-    SMRange MatchRange =

-        ProcessMatchResult(FileCheckDiag::MatchFuzzy, SM, getLoc(),

-                           getCheckTy(), Buffer, Best, 0, Diags);

-    SM.PrintMessage(MatchRange.Start, SourceMgr::DK_Note,

-                    "possible intended match here");

-

-    // FIXME: If we wanted to be really friendly we would show why the match

-    // failed, as it can be hard to spot simple one character differences.

-  }

-}

-

-Expected<StringRef>

-FileCheckPatternContext::getPatternVarValue(StringRef VarName) {

-  auto VarIter = GlobalVariableTable.find(VarName);

-  if (VarIter == GlobalVariableTable.end())

-    return make_error<FileCheckUndefVarError>(VarName);

-

-  return VarIter->second;

-}

-

-template <class... Types>

-FileCheckNumericVariable *

-FileCheckPatternContext::makeNumericVariable(Types... args) {

-  NumericVariables.push_back(

-      std::make_unique<FileCheckNumericVariable>(args...));

-  return NumericVariables.back().get();

-}

-

-FileCheckSubstitution *

-FileCheckPatternContext::makeStringSubstitution(StringRef VarName,

-                                                size_t InsertIdx) {

-  Substitutions.push_back(

-      std::make_unique<FileCheckStringSubstitution>(this, VarName, InsertIdx));

-  return Substitutions.back().get();

-}

-

-FileCheckSubstitution *FileCheckPatternContext::makeNumericSubstitution(

-    StringRef ExpressionStr,

-    std::unique_ptr<FileCheckExpressionAST> ExpressionAST, size_t InsertIdx) {

-  Substitutions.push_back(std::make_unique<FileCheckNumericSubstitution>(

-      this, ExpressionStr, std::move(ExpressionAST), InsertIdx));

-  return Substitutions.back().get();

-}

-

-size_t FileCheckPattern::FindRegexVarEnd(StringRef Str, SourceMgr &SM) {

-  // Offset keeps track of the current offset within the input Str

-  size_t Offset = 0;

-  // [...] Nesting depth

-  size_t BracketDepth = 0;

-

-  while (!Str.empty()) {

-    if (Str.startswith("]]") && BracketDepth == 0)

-      return Offset;

-    if (Str[0] == '\\') {

-      // Backslash escapes the next char within regexes, so skip them both.

-      Str = Str.substr(2);

-      Offset += 2;

-    } else {

-      switch (Str[0]) {

-      default:

-        break;

-      case '[':

-        BracketDepth++;

-        break;

-      case ']':

-        if (BracketDepth == 0) {

-          SM.PrintMessage(SMLoc::getFromPointer(Str.data()),

-                          SourceMgr::DK_Error,

-                          "missing closing \"]\" for regex variable");

-          exit(1);

-        }

-        BracketDepth--;

-        break;

-      }

-      Str = Str.substr(1);

-      Offset++;

-    }

-  }

-

-  return StringRef::npos;

-}

-

-StringRef FileCheck::CanonicalizeFile(MemoryBuffer &MB,

-                                      SmallVectorImpl<char> &OutputBuffer) {

-  OutputBuffer.reserve(MB.getBufferSize());

-

-  for (const char *Ptr = MB.getBufferStart(), *End = MB.getBufferEnd();

-       Ptr != End; ++Ptr) {

-    // Eliminate trailing dosish \r.

-    if (Ptr <= End - 2 && Ptr[0] == '\r' && Ptr[1] == '\n') {

-      continue;

-    }

-

-    // If current char is not a horizontal whitespace or if horizontal

-    // whitespace canonicalization is disabled, dump it to output as is.

-    if (Req.NoCanonicalizeWhiteSpace || (*Ptr != ' ' && *Ptr != '\t')) {

-      OutputBuffer.push_back(*Ptr);

-      continue;

-    }

-

-    // Otherwise, add one space and advance over neighboring space.

-    OutputBuffer.push_back(' ');

-    while (Ptr + 1 != End && (Ptr[1] == ' ' || Ptr[1] == '\t'))

-      ++Ptr;

-  }

-

-  // Add a null byte and then return all but that byte.

-  OutputBuffer.push_back('\0');

-  return StringRef(OutputBuffer.data(), OutputBuffer.size() - 1);

-}

-

-FileCheckDiag::FileCheckDiag(const SourceMgr &SM,

-                             const Check::FileCheckType &CheckTy,

-                             SMLoc CheckLoc, MatchType MatchTy,

-                             SMRange InputRange)

-    : CheckTy(CheckTy), MatchTy(MatchTy) {

-  auto Start = SM.getLineAndColumn(InputRange.Start);

-  auto End = SM.getLineAndColumn(InputRange.End);

-  InputStartLine = Start.first;

-  InputStartCol = Start.second;

-  InputEndLine = End.first;

-  InputEndCol = End.second;

-  Start = SM.getLineAndColumn(CheckLoc);

-  CheckLine = Start.first;

-  CheckCol = Start.second;

-}

-

-static bool IsPartOfWord(char c) {

-  return (isalnum(c) || c == '-' || c == '_');

-}

-

-Check::FileCheckType &Check::FileCheckType::setCount(int C) {

-  assert(Count > 0 && "zero and negative counts are not supported");

-  assert((C == 1 || Kind == CheckPlain) &&

-         "count supported only for plain CHECK directives");

-  Count = C;

-  return *this;

-}

-

-std::string Check::FileCheckType::getDescription(StringRef Prefix) const {

-  switch (Kind) {

-  case Check::CheckNone:

-    return "invalid";

-  case Check::CheckPlain:

-    if (Count > 1)

-      return Prefix.str() + "-COUNT";

-    return Prefix;

-  case Check::CheckNext:

-    return Prefix.str() + "-NEXT";

-  case Check::CheckSame:

-    return Prefix.str() + "-SAME";

-  case Check::CheckNot:

-    return Prefix.str() + "-NOT";

-  case Check::CheckDAG:

-    return Prefix.str() + "-DAG";

-  case Check::CheckLabel:

-    return Prefix.str() + "-LABEL";

-  case Check::CheckEmpty:

-    return Prefix.str() + "-EMPTY";

-  case Check::CheckEOF:

-    return "implicit EOF";

-  case Check::CheckBadNot:

-    return "bad NOT";

-  case Check::CheckBadCount:

-    return "bad COUNT";

-  }

-  llvm_unreachable("unknown FileCheckType");

-}

-

-static std::pair<Check::FileCheckType, StringRef>

-FindCheckType(StringRef Buffer, StringRef Prefix) {

-  if (Buffer.size() <= Prefix.size())

-    return {Check::CheckNone, StringRef()};

-

-  char NextChar = Buffer[Prefix.size()];

-

-  StringRef Rest = Buffer.drop_front(Prefix.size() + 1);

-  // Verify that the : is present after the prefix.

-  if (NextChar == ':')

-    return {Check::CheckPlain, Rest};

-

-  if (NextChar != '-')

-    return {Check::CheckNone, StringRef()};

-

-  if (Rest.consume_front("COUNT-")) {

-    int64_t Count;

-    if (Rest.consumeInteger(10, Count))

-      // Error happened in parsing integer.

-      return {Check::CheckBadCount, Rest};

-    if (Count <= 0 || Count > INT32_MAX)

-      return {Check::CheckBadCount, Rest};

-    if (!Rest.consume_front(":"))

-      return {Check::CheckBadCount, Rest};

-    return {Check::FileCheckType(Check::CheckPlain).setCount(Count), Rest};

-  }

-

-  if (Rest.consume_front("NEXT:"))

-    return {Check::CheckNext, Rest};

-

-  if (Rest.consume_front("SAME:"))

-    return {Check::CheckSame, Rest};

-

-  if (Rest.consume_front("NOT:"))

-    return {Check::CheckNot, Rest};

-

-  if (Rest.consume_front("DAG:"))

-    return {Check::CheckDAG, Rest};

-

-  if (Rest.consume_front("LABEL:"))

-    return {Check::CheckLabel, Rest};

-

-  if (Rest.consume_front("EMPTY:"))

-    return {Check::CheckEmpty, Rest};

-

-  // 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:") ||

-      Rest.startswith("EMPTY-NOT:") || Rest.startswith("NOT-EMPTY:"))

-    return {Check::CheckBadNot, Rest};

-

-  return {Check::CheckNone, Rest};

-}

-

-// 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;

-}

-

-/// Searches the buffer for the first prefix in the prefix regular expression.

-///

-/// This searches the buffer using the provided regular expression, however it

-/// enforces constraints beyond that:

-/// 1) The found prefix must not be a suffix of something that looks like

-///    a valid prefix.

-/// 2) The found prefix must be followed by a valid check type suffix using \c

-///    FindCheckType above.

-///

-/// \returns a pair of StringRefs into the Buffer, which combines:

-///   - the first match of the regular expression to satisfy these two is

-///   returned,

-///     otherwise an empty StringRef is returned to indicate failure.

-///   - buffer rewound to the location right after parsed suffix, for parsing

-///     to continue from

-///

-/// If this routine returns a valid prefix, it will also shrink \p Buffer to

-/// start at the beginning of the returned prefix, increment \p LineNumber for

-/// each new line consumed from \p Buffer, and set \p CheckTy to the type of

-/// check found by examining the suffix.

-///

-/// If no valid prefix is found, the state of Buffer, LineNumber, and CheckTy

-/// is unspecified.

-static std::pair<StringRef, StringRef>

-FindFirstMatchingPrefix(Regex &PrefixRE, StringRef &Buffer,

-                        unsigned &LineNumber, Check::FileCheckType &CheckTy) {

-  SmallVector<StringRef, 2> Matches;

-

-  while (!Buffer.empty()) {

-    // Find the first (longest) match using the RE.

-    if (!PrefixRE.match(Buffer, &Matches))

-      // No match at all, bail.

-      return {StringRef(), StringRef()};

-

-    StringRef Prefix = Matches[0];

-    Matches.clear();

-

-    assert(Prefix.data() >= Buffer.data() &&

-           Prefix.data() < Buffer.data() + Buffer.size() &&

-           "Prefix doesn't start inside of buffer!");

-    size_t Loc = Prefix.data() - Buffer.data();

-    StringRef Skipped = Buffer.substr(0, Loc);

-    Buffer = Buffer.drop_front(Loc);

-    LineNumber += Skipped.count('\n');

-

-    // Check that the matched prefix isn't a suffix of some other check-like

-    // word.

-    // FIXME: This is a very ad-hoc check. it would be better handled in some

-    // other way. Among other things it seems hard to distinguish between

-    // intentional and unintentional uses of this feature.

-    if (Skipped.empty() || !IsPartOfWord(Skipped.back())) {

-      // Now extract the type.

-      StringRef AfterSuffix;

-      std::tie(CheckTy, AfterSuffix) = FindCheckType(Buffer, Prefix);

-

-      // If we've found a valid check type for this prefix, we're done.

-      if (CheckTy != Check::CheckNone)

-        return {Prefix, AfterSuffix};

-    }

-

-    // If we didn't successfully find a prefix, we need to skip this invalid

-    // prefix and continue scanning. We directly skip the prefix that was

-    // matched and any additional parts of that check-like word.

-    Buffer = Buffer.drop_front(SkipWord(Buffer, Prefix.size()));

-  }

-

-  // We ran out of buffer while skipping partial matches so give up.

-  return {StringRef(), StringRef()};

-}

-

-void FileCheckPatternContext::createLineVariable() {

-  assert(!LineVariable && "@LINE pseudo numeric variable already created");

-  StringRef LineName = "@LINE";

-  LineVariable = makeNumericVariable(LineName);

-  GlobalNumericVariableTable[LineName] = LineVariable;

-}

-

-FileCheck::FileCheck(FileCheckRequest Req)

-    : Req(Req), PatternContext(std::make_unique<FileCheckPatternContext>()),

-      CheckStrings(std::make_unique<std::vector<FileCheckString>>()) {}

-

-FileCheck::~FileCheck() = default;

-

-bool FileCheck::readCheckFile(SourceMgr &SM, StringRef Buffer,

-                              Regex &PrefixRE) {

-  Error DefineError =

-      PatternContext->defineCmdlineVariables(Req.GlobalDefines, SM);

-  if (DefineError) {

-    logAllUnhandledErrors(std::move(DefineError), errs());

-    return true;

-  }

-

-  PatternContext->createLineVariable();

-

-  std::vector<FileCheckPattern> ImplicitNegativeChecks;

-  for (const auto &PatternString : Req.ImplicitCheckNot) {

-    // Create a buffer with fake command line content in order to display the

-    // command line option responsible for the specific implicit CHECK-NOT.

-    std::string Prefix = "-implicit-check-not='";

-    std::string Suffix = "'";

-    std::unique_ptr<MemoryBuffer> CmdLine = MemoryBuffer::getMemBufferCopy(

-        Prefix + PatternString + Suffix, "command line");

-

-    StringRef PatternInBuffer =

-        CmdLine->getBuffer().substr(Prefix.size(), PatternString.size());

-    SM.AddNewSourceBuffer(std::move(CmdLine), SMLoc());

-

-    ImplicitNegativeChecks.push_back(

-        FileCheckPattern(Check::CheckNot, PatternContext.get()));

-    ImplicitNegativeChecks.back().parsePattern(PatternInBuffer,

-                                               "IMPLICIT-CHECK", SM, Req);

-  }

-

-  std::vector<FileCheckPattern> DagNotMatches = ImplicitNegativeChecks;

-

-  // LineNumber keeps track of the line on which CheckPrefix instances are

-  // found.

-  unsigned LineNumber = 1;

-

-  while (1) {

-    Check::FileCheckType CheckTy;

-

-    // See if a prefix occurs in the memory buffer.

-    StringRef UsedPrefix;

-    StringRef AfterSuffix;

-    std::tie(UsedPrefix, AfterSuffix) =

-        FindFirstMatchingPrefix(PrefixRE, Buffer, LineNumber, CheckTy);

-    if (UsedPrefix.empty())

-      break;

-    assert(UsedPrefix.data() == Buffer.data() &&

-           "Failed to move Buffer's start forward, or pointed prefix outside "

-           "of the buffer!");

-    assert(AfterSuffix.data() >= Buffer.data() &&

-           AfterSuffix.data() < Buffer.data() + Buffer.size() &&

-           "Parsing after suffix doesn't start inside of buffer!");

-

-    // Location to use for error messages.

-    const char *UsedPrefixStart = UsedPrefix.data();

-

-    // Skip the buffer to the end of parsed suffix (or just prefix, if no good

-    // suffix was processed).

-    Buffer = AfterSuffix.empty() ? Buffer.drop_front(UsedPrefix.size())

-                                 : AfterSuffix;

-

-    // 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;

-    }

-

-    // Complain about invalid count specification.

-    if (CheckTy == Check::CheckBadCount) {

-      SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Error,

-                      "invalid count in -COUNT specification on prefix '" +

-                          UsedPrefix + "'");

-      return true;

-    }

-

-    // Okay, we found the prefix, yay. Remember the rest of the line, but ignore

-    // leading whitespace.

-    if (!(Req.NoCanonicalizeWhiteSpace && Req.MatchFullLines))

-      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.

-    FileCheckPattern P(CheckTy, PatternContext.get(), LineNumber);

-    if (P.parsePattern(Buffer.substr(0, EOL), UsedPrefix, SM, Req))

-      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/SAME/EMPTY lines have at least one CHECK line before them.

-    if ((CheckTy == Check::CheckNext || CheckTy == Check::CheckSame ||

-         CheckTy == Check::CheckEmpty) &&

-        CheckStrings->empty()) {

-      StringRef Type = CheckTy == Check::CheckNext

-                           ? "NEXT"

-                           : CheckTy == Check::CheckEmpty ? "EMPTY" : "SAME";

-      SM.PrintMessage(SMLoc::getFromPointer(UsedPrefixStart),

-                      SourceMgr::DK_Error,

-                      "found '" + UsedPrefix + "-" + Type +

-                          "' without previous '" + UsedPrefix + ": line");

-      return true;

-    }

-

-    // Handle CHECK-DAG/-NOT.

-    if (CheckTy == Check::CheckDAG || CheckTy == Check::CheckNot) {

-      DagNotMatches.push_back(P);

-      continue;

-    }

-

-    // Okay, add the string we captured to the output vector and move on.

-    CheckStrings->emplace_back(P, UsedPrefix, PatternLoc);

-    std::swap(DagNotMatches, CheckStrings->back().DagNotStrings);

-    DagNotMatches = ImplicitNegativeChecks;

-  }

-

-  // Add an EOF pattern for any trailing CHECK-DAG/-NOTs, and use the first

-  // prefix as a filler for the error message.

-  if (!DagNotMatches.empty()) {

-    CheckStrings->emplace_back(

-        FileCheckPattern(Check::CheckEOF, PatternContext.get(), LineNumber + 1),

-        *Req.CheckPrefixes.begin(), SMLoc::getFromPointer(Buffer.data()));

-    std::swap(DagNotMatches, CheckStrings->back().DagNotStrings);

-  }

-

-  if (CheckStrings->empty()) {

-    errs() << "error: no check strings found with prefix"

-           << (Req.CheckPrefixes.size() > 1 ? "es " : " ");

-    auto I = Req.CheckPrefixes.begin();

-    auto E = Req.CheckPrefixes.end();

-    if (I != E) {

-      errs() << "\'" << *I << ":'";

-      ++I;

-    }

-    for (; I != E; ++I)

-      errs() << ", \'" << *I << ":'";

-

-    errs() << '\n';

-    return true;

-  }

-

-  return false;

-}

-

-static void PrintMatch(bool ExpectedMatch, const SourceMgr &SM,

-                       StringRef Prefix, SMLoc Loc, const FileCheckPattern &Pat,

-                       int MatchedCount, StringRef Buffer, size_t MatchPos,

-                       size_t MatchLen, const FileCheckRequest &Req,

-                       std::vector<FileCheckDiag> *Diags) {

-  bool PrintDiag = true;

-  if (ExpectedMatch) {

-    if (!Req.Verbose)

-      return;

-    if (!Req.VerboseVerbose && Pat.getCheckTy() == Check::CheckEOF)

-      return;

-    // Due to their verbosity, we don't print verbose diagnostics here if we're

-    // gathering them for a different rendering, but we always print other

-    // diagnostics.

-    PrintDiag = !Diags;

-  }

-  SMRange MatchRange = ProcessMatchResult(

-      ExpectedMatch ? FileCheckDiag::MatchFoundAndExpected

-                    : FileCheckDiag::MatchFoundButExcluded,

-      SM, Loc, Pat.getCheckTy(), Buffer, MatchPos, MatchLen, Diags);

-  if (!PrintDiag)

-    return;

-

-  std::string Message = formatv("{0}: {1} string found in input",

-                                Pat.getCheckTy().getDescription(Prefix),

-                                (ExpectedMatch ? "expected" : "excluded"))

-                            .str();

-  if (Pat.getCount() > 1)

-    Message += formatv(" ({0} out of {1})", MatchedCount, Pat.getCount()).str();

-

-  SM.PrintMessage(

-      Loc, ExpectedMatch ? SourceMgr::DK_Remark : SourceMgr::DK_Error, Message);

-  SM.PrintMessage(MatchRange.Start, SourceMgr::DK_Note, "found here",

-                  {MatchRange});

-  Pat.printSubstitutions(SM, Buffer, MatchRange);

-}

-

-static void PrintMatch(bool ExpectedMatch, const SourceMgr &SM,

-                       const FileCheckString &CheckStr, int MatchedCount,

-                       StringRef Buffer, size_t MatchPos, size_t MatchLen,

-                       FileCheckRequest &Req,

-                       std::vector<FileCheckDiag> *Diags) {

-  PrintMatch(ExpectedMatch, SM, CheckStr.Prefix, CheckStr.Loc, CheckStr.Pat,

-             MatchedCount, Buffer, MatchPos, MatchLen, Req, Diags);

-}

-

-static void PrintNoMatch(bool ExpectedMatch, const SourceMgr &SM,

-                         StringRef Prefix, SMLoc Loc,

-                         const FileCheckPattern &Pat, int MatchedCount,

-                         StringRef Buffer, bool VerboseVerbose,

-                         std::vector<FileCheckDiag> *Diags, Error MatchErrors) {

-  assert(MatchErrors && "Called on successful match");

-  bool PrintDiag = true;

-  if (!ExpectedMatch) {

-    if (!VerboseVerbose) {

-      consumeError(std::move(MatchErrors));

-      return;

-    }

-    // Due to their verbosity, we don't print verbose diagnostics here if we're

-    // gathering them for a different rendering, but we always print other

-    // diagnostics.

-    PrintDiag = !Diags;

-  }

-

-  // If the current position is at the end of a line, advance to the start of

-  // the next line.

-  Buffer = Buffer.substr(Buffer.find_first_not_of(" \t\n\r"));

-  SMRange SearchRange = ProcessMatchResult(

-      ExpectedMatch ? FileCheckDiag::MatchNoneButExpected

-                    : FileCheckDiag::MatchNoneAndExcluded,

-      SM, Loc, Pat.getCheckTy(), Buffer, 0, Buffer.size(), Diags);

-  if (!PrintDiag) {

-    consumeError(std::move(MatchErrors));

-    return;

-  }

-

-  MatchErrors =

-      handleErrors(std::move(MatchErrors),

-                   [](const FileCheckErrorDiagnostic &E) { E.log(errs()); });

-

-  // No problem matching the string per se.

-  if (!MatchErrors)

-    return;

-  consumeError(std::move(MatchErrors));

-

-  // Print "not found" diagnostic.

-  std::string Message = formatv("{0}: {1} string not found in input",

-                                Pat.getCheckTy().getDescription(Prefix),

-                                (ExpectedMatch ? "expected" : "excluded"))

-                            .str();

-  if (Pat.getCount() > 1)

-    Message += formatv(" ({0} out of {1})", MatchedCount, Pat.getCount()).str();

-  SM.PrintMessage(

-      Loc, ExpectedMatch ? SourceMgr::DK_Error : SourceMgr::DK_Remark, Message);

-

-  // Print the "scanning from here" line.

-  SM.PrintMessage(SearchRange.Start, SourceMgr::DK_Note, "scanning from here");

-

-  // Allow the pattern to print additional information if desired.

-  Pat.printSubstitutions(SM, Buffer);

-

-  if (ExpectedMatch)

-    Pat.printFuzzyMatch(SM, Buffer, Diags);

-}

-

-static void PrintNoMatch(bool ExpectedMatch, const SourceMgr &SM,

-                         const FileCheckString &CheckStr, int MatchedCount,

-                         StringRef Buffer, bool VerboseVerbose,

-                         std::vector<FileCheckDiag> *Diags, Error MatchErrors) {

-  PrintNoMatch(ExpectedMatch, SM, CheckStr.Prefix, CheckStr.Loc, CheckStr.Pat,

-               MatchedCount, Buffer, VerboseVerbose, Diags,

-               std::move(MatchErrors));

-}

-

-/// Counts the number of newlines in the specified range.

-static unsigned CountNumNewlinesBetween(StringRef Range,

-                                        const char *&FirstNewLine) {

-  unsigned NumNewLines = 0;

-  while (1) {

-    // Scan for newline.

-    Range = Range.substr(Range.find_first_of("\n\r"));

-    if (Range.empty())

-      return NumNewLines;

-

-    ++NumNewLines;

-

-    // Handle \n\r and \r\n as a single newline.

-    if (Range.size() > 1 && (Range[1] == '\n' || Range[1] == '\r') &&

-        (Range[0] != Range[1]))

-      Range = Range.substr(1);

-    Range = Range.substr(1);

-

-    if (NumNewLines == 1)

-      FirstNewLine = Range.begin();

-  }

-}

-

-size_t FileCheckString::Check(const SourceMgr &SM, StringRef Buffer,

-                              bool IsLabelScanMode, size_t &MatchLen,

-                              FileCheckRequest &Req,

-                              std::vector<FileCheckDiag> *Diags) const {

-  size_t LastPos = 0;

-  std::vector<const FileCheckPattern *> NotStrings;

-

-  // IsLabelScanMode is true when we are scanning forward to find CHECK-LABEL

-  // bounds; we have not processed variable definitions within the bounded block

-  // yet so cannot handle any final CHECK-DAG yet; this is handled when going

-  // 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, Req, Diags);

-    if (LastPos == StringRef::npos)

-      return StringRef::npos;

-  }

-

-  // Match itself from the last position after matching CHECK-DAG.

-  size_t LastMatchEnd = LastPos;

-  size_t FirstMatchPos = 0;

-  // Go match the pattern Count times. Majority of patterns only match with

-  // count 1 though.

-  assert(Pat.getCount() != 0 && "pattern count can not be zero");

-  for (int i = 1; i <= Pat.getCount(); i++) {

-    StringRef MatchBuffer = Buffer.substr(LastMatchEnd);

-    size_t CurrentMatchLen;

-    // get a match at current start point

-    Expected<size_t> MatchResult = Pat.match(MatchBuffer, CurrentMatchLen, SM);

-

-    // report

-    if (!MatchResult) {

-      PrintNoMatch(true, SM, *this, i, MatchBuffer, Req.VerboseVerbose, Diags,

-                   MatchResult.takeError());

-      return StringRef::npos;

-    }

-    size_t MatchPos = *MatchResult;

-    PrintMatch(true, SM, *this, i, MatchBuffer, MatchPos, CurrentMatchLen, Req,

-               Diags);

-    if (i == 1)

-      FirstMatchPos = LastPos + MatchPos;

-

-    // move start point after the match

-    LastMatchEnd += MatchPos + CurrentMatchLen;

-  }

-  // Full match len counts from first match pos.

-  MatchLen = LastMatchEnd - FirstMatchPos;

-

-  // Similar to the above, in "label-scan mode" we can't yet handle CHECK-NEXT

-  // or CHECK-NOT

-  if (!IsLabelScanMode) {

-    size_t MatchPos = FirstMatchPos - LastPos;

-    StringRef MatchBuffer = Buffer.substr(LastPos);

-    StringRef SkippedRegion = Buffer.substr(LastPos, MatchPos);

-

-    // If this check is a "CHECK-NEXT", verify that the previous match was on

-    // the previous line (i.e. that there is one newline between them).

-    if (CheckNext(SM, SkippedRegion)) {

-      ProcessMatchResult(FileCheckDiag::MatchFoundButWrongLine, SM, Loc,

-                         Pat.getCheckTy(), MatchBuffer, MatchPos, MatchLen,

-                         Diags, Req.Verbose);

-      return StringRef::npos;

-    }

-

-    // If this check is a "CHECK-SAME", verify that the previous match was on

-    // the same line (i.e. that there is no newline between them).

-    if (CheckSame(SM, SkippedRegion)) {

-      ProcessMatchResult(FileCheckDiag::MatchFoundButWrongLine, SM, Loc,

-                         Pat.getCheckTy(), MatchBuffer, MatchPos, MatchLen,

-                         Diags, Req.Verbose);

-      return StringRef::npos;

-    }

-

-    // If this match had "not strings", verify that they don't exist in the

-    // skipped region.

-    if (CheckNot(SM, SkippedRegion, NotStrings, Req, Diags))

-      return StringRef::npos;

-  }

-

-  return FirstMatchPos;

-}

-

-bool FileCheckString::CheckNext(const SourceMgr &SM, StringRef Buffer) const {

-  if (Pat.getCheckTy() != Check::CheckNext &&

-      Pat.getCheckTy() != Check::CheckEmpty)

-    return false;

-

-  Twine CheckName =

-      Prefix +

-      Twine(Pat.getCheckTy() == Check::CheckEmpty ? "-EMPTY" : "-NEXT");

-

-  // Count the number of newlines between the previous match and this one.

-  const char *FirstNewLine = nullptr;

-  unsigned NumNewLines = CountNumNewlinesBetween(Buffer, FirstNewLine);

-

-  if (NumNewLines == 0) {

-    SM.PrintMessage(Loc, SourceMgr::DK_Error,

-                    CheckName + ": is on the same line as previous match");

-    SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), SourceMgr::DK_Note,

-                    "'next' match was here");

-    SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,

-                    "previous match ended here");

-    return true;

-  }

-

-  if (NumNewLines != 1) {

-    SM.PrintMessage(Loc, SourceMgr::DK_Error,

-                    CheckName +

-                        ": is not on the line after the previous match");

-    SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), SourceMgr::DK_Note,

-                    "'next' match was here");

-    SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,

-                    "previous match ended here");

-    SM.PrintMessage(SMLoc::getFromPointer(FirstNewLine), SourceMgr::DK_Note,

-                    "non-matching line after previous match is here");

-    return true;

-  }

-

-  return false;

-}

-

-bool FileCheckString::CheckSame(const SourceMgr &SM, StringRef Buffer) const {

-  if (Pat.getCheckTy() != Check::CheckSame)

-    return false;

-

-  // Count the number of newlines between the previous match and this one.

-  const char *FirstNewLine = nullptr;

-  unsigned NumNewLines = CountNumNewlinesBetween(Buffer, FirstNewLine);

-

-  if (NumNewLines != 0) {

-    SM.PrintMessage(Loc, SourceMgr::DK_Error,

-                    Prefix +

-                        "-SAME: is not on the same line as the previous match");

-    SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), SourceMgr::DK_Note,

-                    "'next' match was here");

-    SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,

-                    "previous match ended here");

-    return true;

-  }

-

-  return false;

-}

-

-bool FileCheckString::CheckNot(

-    const SourceMgr &SM, StringRef Buffer,

-    const std::vector<const FileCheckPattern *> &NotStrings,

-    const FileCheckRequest &Req, std::vector<FileCheckDiag> *Diags) const {

-  for (const FileCheckPattern *Pat : NotStrings) {

-    assert((Pat->getCheckTy() == Check::CheckNot) && "Expect CHECK-NOT!");

-

-    size_t MatchLen = 0;

-    Expected<size_t> MatchResult = Pat->match(Buffer, MatchLen, SM);

-

-    if (!MatchResult) {

-      PrintNoMatch(false, SM, Prefix, Pat->getLoc(), *Pat, 1, Buffer,

-                   Req.VerboseVerbose, Diags, MatchResult.takeError());

-      continue;

-    }

-    size_t Pos = *MatchResult;

-

-    PrintMatch(false, SM, Prefix, Pat->getLoc(), *Pat, 1, Buffer, Pos, MatchLen,

-               Req, Diags);

-

-    return true;

-  }

-

-  return false;

-}

-

-size_t

-FileCheckString::CheckDag(const SourceMgr &SM, StringRef Buffer,

-                          std::vector<const FileCheckPattern *> &NotStrings,

-                          const FileCheckRequest &Req,

-                          std::vector<FileCheckDiag> *Diags) const {

-  if (DagNotStrings.empty())

-    return 0;

-

-  // The start of the search range.

-  size_t StartPos = 0;

-

-  struct MatchRange {

-    size_t Pos;

-    size_t End;

-  };

-  // 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 FileCheckPattern &Pat = *PatItr;

-    assert((Pat.getCheckTy() == Check::CheckDAG ||

-            Pat.getCheckTy() == Check::CheckNot) &&

-           "Invalid CHECK-DAG or CHECK-NOT!");

-

-    if (Pat.getCheckTy() == Check::CheckNot) {

-      NotStrings.push_back(&Pat);

-      continue;

-    }

-

-    assert((Pat.getCheckTy() == Check::CheckDAG) && "Expect CHECK-DAG!");

-

-    // CHECK-DAG always matches from the start.

-    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 = MatchRanges.begin(), ME = MatchRanges.end(); true; ++MI) {

-      StringRef MatchBuffer = Buffer.substr(MatchPos);

-      Expected<size_t> MatchResult = Pat.match(MatchBuffer, MatchLen, SM);

-      // With a group of CHECK-DAGs, a single mismatching means the match on

-      // that group of CHECK-DAGs fails immediately.

-      if (!MatchResult) {

-        PrintNoMatch(true, SM, Prefix, Pat.getLoc(), Pat, 1, MatchBuffer,

-                     Req.VerboseVerbose, Diags, MatchResult.takeError());

-        return StringRef::npos;

-      }

-      size_t MatchPosBuf = *MatchResult;

-      // Re-calc it as the offset relative to the start of the original string.

-      MatchPos += MatchPosBuf;

-      if (Req.VerboseVerbose)

-        PrintMatch(true, SM, Prefix, Pat.getLoc(), Pat, 1, Buffer, MatchPos,

-                   MatchLen, Req, Diags);

-      MatchRange M{MatchPos, MatchPos + MatchLen};

-      if (Req.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.

-      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.

-        MatchRanges.insert(MI, M);

-        break;

-      }

-      if (Req.VerboseVerbose) {

-        // Due to their verbosity, we don't print verbose diagnostics here if

-        // we're gathering them for a different rendering, but we always print

-        // other diagnostics.

-        if (!Diags) {

-          SMLoc OldStart = SMLoc::getFromPointer(Buffer.data() + MI->Pos);

-          SMLoc OldEnd = SMLoc::getFromPointer(Buffer.data() + MI->End);

-          SMRange OldRange(OldStart, OldEnd);

-          SM.PrintMessage(OldStart, SourceMgr::DK_Note,

-                          "match discarded, overlaps earlier DAG match here",

-                          {OldRange});

-        } else

-          Diags->rbegin()->MatchTy = FileCheckDiag::MatchFoundButDiscarded;

-      }

-      MatchPos = MI->End;

-    }

-    if (!Req.VerboseVerbose)

-      PrintMatch(true, SM, Prefix, Pat.getLoc(), Pat, 1, Buffer, MatchPos,

-                 MatchLen, Req, Diags);

-

-    // 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, Req, Diags))

-          return StringRef::npos;

-        // Clear "not strings".

-        NotStrings.clear();

-      }

-      // 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.

-      MatchRanges.clear();

-    }

-  }

-

-  return StartPos;

-}

-

-// A check prefix must contain only alphanumeric, hyphens and underscores.

-static bool ValidateCheckPrefix(StringRef CheckPrefix) {

-  static const Regex Validator("^[a-zA-Z0-9_-]*$");

-  return Validator.match(CheckPrefix);

-}

-

-bool FileCheck::ValidateCheckPrefixes() {

-  StringSet<> PrefixSet;

-

-  for (StringRef Prefix : Req.CheckPrefixes) {

-    // Reject empty prefixes.

-    if (Prefix == "")

-      return false;

-

-    if (!PrefixSet.insert(Prefix).second)

-      return false;

-

-    if (!ValidateCheckPrefix(Prefix))

-      return false;

-  }

-

-  return true;

-}

-

-Regex FileCheck::buildCheckPrefixRegex() {

-  // I don't think there's a way to specify an initial value for cl::list,

-  // so if nothing was specified, add the default

-  if (Req.CheckPrefixes.empty())

-    Req.CheckPrefixes.push_back("CHECK");

-

-  // We already validated the contents of CheckPrefixes so just concatenate

-  // them as alternatives.

-  SmallString<32> PrefixRegexStr;

-  for (StringRef Prefix : Req.CheckPrefixes) {

-    if (Prefix != Req.CheckPrefixes.front())

-      PrefixRegexStr.push_back('|');

-

-    PrefixRegexStr.append(Prefix);

-  }

-

-  return Regex(PrefixRegexStr);

-}

-

-Error FileCheckPatternContext::defineCmdlineVariables(

-    std::vector<std::string> &CmdlineDefines, SourceMgr &SM) {

-  assert(GlobalVariableTable.empty() && GlobalNumericVariableTable.empty() &&

-         "Overriding defined variable with command-line variable definitions");

-

-  if (CmdlineDefines.empty())

-    return Error::success();

-

-  // Create a string representing the vector of command-line definitions. Each

-  // definition is on its own line and prefixed with a definition number to

-  // clarify which definition a given diagnostic corresponds to.

-  unsigned I = 0;

-  Error Errs = Error::success();

-  std::string CmdlineDefsDiag;

-  SmallVector<std::pair<size_t, size_t>, 4> CmdlineDefsIndices;

-  for (StringRef CmdlineDef : CmdlineDefines) {

-    std::string DefPrefix = ("Global define #" + Twine(++I) + ": ").str();

-    size_t EqIdx = CmdlineDef.find('=');

-    if (EqIdx == StringRef::npos) {

-      CmdlineDefsIndices.push_back(std::make_pair(CmdlineDefsDiag.size(), 0));

-      continue;

-    }

-    // Numeric variable definition.

-    if (CmdlineDef[0] == '#') {

-      // Append a copy of the command-line definition adapted to use the same

-      // format as in the input file to be able to reuse

-      // parseNumericSubstitutionBlock.

-      CmdlineDefsDiag += (DefPrefix + CmdlineDef + " (parsed as: [[").str();

-      std::string SubstitutionStr = CmdlineDef;

-      SubstitutionStr[EqIdx] = ':';

-      CmdlineDefsIndices.push_back(

-          std::make_pair(CmdlineDefsDiag.size(), SubstitutionStr.size()));

-      CmdlineDefsDiag += (SubstitutionStr + Twine("]])\n")).str();

-    } else {

-      CmdlineDefsDiag += DefPrefix;

-      CmdlineDefsIndices.push_back(

-          std::make_pair(CmdlineDefsDiag.size(), CmdlineDef.size()));

-      CmdlineDefsDiag += (CmdlineDef + "\n").str();

-    }

-  }

-

-  // Create a buffer with fake command line content in order to display

-  // parsing diagnostic with location information and point to the

-  // global definition with invalid syntax.

-  std::unique_ptr<MemoryBuffer> CmdLineDefsDiagBuffer =

-      MemoryBuffer::getMemBufferCopy(CmdlineDefsDiag, "Global defines");

-  StringRef CmdlineDefsDiagRef = CmdLineDefsDiagBuffer->getBuffer();

-  SM.AddNewSourceBuffer(std::move(CmdLineDefsDiagBuffer), SMLoc());

-

-  for (std::pair<size_t, size_t> CmdlineDefIndices : CmdlineDefsIndices) {

-    StringRef CmdlineDef = CmdlineDefsDiagRef.substr(CmdlineDefIndices.first,

-                                                     CmdlineDefIndices.second);

-    if (CmdlineDef.empty()) {

-      Errs = joinErrors(

-          std::move(Errs),

-          FileCheckErrorDiagnostic::get(

-              SM, CmdlineDef, "missing equal sign in global definition"));

-      continue;

-    }

-

-    // Numeric variable definition.

-    if (CmdlineDef[0] == '#') {

-      // Now parse the definition both to check that the syntax is correct and

-      // to create the necessary class instance.

-      StringRef CmdlineDefExpr = CmdlineDef.substr(1);

-      Optional<FileCheckNumericVariable *> DefinedNumericVariable;

-      Expected<std::unique_ptr<FileCheckExpressionAST>> ExpressionASTResult =

-          FileCheckPattern::parseNumericSubstitutionBlock(

-              CmdlineDefExpr, DefinedNumericVariable, false, None, this, SM);

-      if (!ExpressionASTResult) {

-        Errs = joinErrors(std::move(Errs), ExpressionASTResult.takeError());

-        continue;

-      }

-      std::unique_ptr<FileCheckExpressionAST> ExpressionAST =

-          std::move(*ExpressionASTResult);

-      // Now evaluate the expression whose value this variable should be set

-      // to, since the expression of a command-line variable definition should

-      // only use variables defined earlier on the command-line. If not, this

-      // is an error and we report it.

-      Expected<uint64_t> Value = ExpressionAST->eval();

-      if (!Value) {

-        Errs = joinErrors(std::move(Errs), Value.takeError());

-        continue;

-      }

-

-      assert(DefinedNumericVariable && "No variable defined");

-      (*DefinedNumericVariable)->setValue(*Value);

-

-      // Record this variable definition.

-      GlobalNumericVariableTable[(*DefinedNumericVariable)->getName()] =

-          *DefinedNumericVariable;

-    } else {

-      // String variable definition.

-      std::pair<StringRef, StringRef> CmdlineNameVal = CmdlineDef.split('=');

-      StringRef CmdlineName = CmdlineNameVal.first;

-      StringRef OrigCmdlineName = CmdlineName;

-      Expected<FileCheckPattern::VariableProperties> ParseVarResult =

-          FileCheckPattern::parseVariable(CmdlineName, SM);

-      if (!ParseVarResult) {

-        Errs = joinErrors(std::move(Errs), ParseVarResult.takeError());

-        continue;

-      }

-      // Check that CmdlineName does not denote a pseudo variable is only

-      // composed of the parsed numeric variable. This catches cases like

-      // "FOO+2" in a "FOO+2=10" definition.

-      if (ParseVarResult->IsPseudo || !CmdlineName.empty()) {

-        Errs = joinErrors(std::move(Errs),

-                          FileCheckErrorDiagnostic::get(

-                              SM, OrigCmdlineName,

-                              "invalid name in string variable definition '" +

-                                  OrigCmdlineName + "'"));

-        continue;

-      }

-      StringRef Name = ParseVarResult->Name;

-

-      // Detect collisions between string and numeric variables when the former

-      // is created later than the latter.

-      if (GlobalNumericVariableTable.find(Name) !=

-          GlobalNumericVariableTable.end()) {

-        Errs = joinErrors(std::move(Errs), FileCheckErrorDiagnostic::get(

-                                               SM, Name,

-                                               "numeric variable with name '" +

-                                                   Name + "' already exists"));

-        continue;

-      }

-      GlobalVariableTable.insert(CmdlineNameVal);

-      // Mark the string variable as defined to detect collisions between

-      // string and numeric variables in defineCmdlineVariables when the latter

-      // is created later than the former. We cannot reuse GlobalVariableTable

-      // for this by populating it with an empty string since we would then

-      // lose the ability to detect the use of an undefined variable in

-      // match().

-      DefinedVariableTable[Name] = true;

-    }

-  }

-

-  return Errs;

-}

-

-void FileCheckPatternContext::clearLocalVars() {

-  SmallVector<StringRef, 16> LocalPatternVars, LocalNumericVars;

-  for (const StringMapEntry<StringRef> &Var : GlobalVariableTable)

-    if (Var.first()[0] != '$')

-      LocalPatternVars.push_back(Var.first());

-

-  // Numeric substitution reads the value of a variable directly, not via

-  // GlobalNumericVariableTable. Therefore, we clear local variables by

-  // clearing their value which will lead to a numeric substitution failure. We

-  // also mark the variable for removal from GlobalNumericVariableTable since

-  // this is what defineCmdlineVariables checks to decide that no global

-  // variable has been defined.

-  for (const auto &Var : GlobalNumericVariableTable)

-    if (Var.first()[0] != '$') {

-      Var.getValue()->clearValue();

-      LocalNumericVars.push_back(Var.first());

-    }

-

-  for (const auto &Var : LocalPatternVars)

-    GlobalVariableTable.erase(Var);

-  for (const auto &Var : LocalNumericVars)

-    GlobalNumericVariableTable.erase(Var);

-}

-

-bool FileCheck::checkInput(SourceMgr &SM, StringRef Buffer,

-                           std::vector<FileCheckDiag> *Diags) {

-  bool ChecksFailed = false;

-

-  unsigned i = 0, j = 0, e = CheckStrings->size();

-  while (true) {

-    StringRef CheckRegion;

-    if (j == e) {

-      CheckRegion = Buffer;

-    } else {

-      const FileCheckString &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, Req, Diags);

-      if (MatchLabelPos == StringRef::npos)

-        // Immediately bail if CHECK-LABEL fails, nothing else we can do.

-        return false;

-

-      CheckRegion = Buffer.substr(0, MatchLabelPos + MatchLabelLen);

-      Buffer = Buffer.substr(MatchLabelPos + MatchLabelLen);

-      ++j;

-    }

-

-    // Do not clear the first region as it's the one before the first

-    // CHECK-LABEL and it would clear variables defined on the command-line

-    // before they get used.

-    if (i != 0 && Req.EnableVarScope)

-      PatternContext->clearLocalVars();

-

-    for (; i != j; ++i) {

-      const FileCheckString &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, Req, Diags);

-

-      if (MatchPos == StringRef::npos) {

-        ChecksFailed = true;

-        i = j;

-        break;

-      }

-

-      CheckRegion = CheckRegion.substr(MatchPos + MatchLen);

-    }

-

-    if (j == e)

-      break;

-  }

-

-  // Success if no checks failed.

-  return !ChecksFailed;

-}

+//===- FileCheck.cpp - Check that File's Contents match what is expected --===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// FileCheck does a line-by line check of a file that validates whether it
+// contains the expected content.  This is useful for regression tests etc.
+//
+// This file implements most of the API that will be used by the FileCheck utility
+// as well as various unittests.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/FileCheck.h"
+#include "FileCheckImpl.h"
+#include "llvm/ADT/StringSet.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/Support/FormatVariadic.h"
+#include <cstdint>
+#include <list>
+#include <tuple>
+#include <utility>
+
+using namespace llvm;
+
+Expected<uint64_t> FileCheckNumericVariableUse::eval() const {
+  Optional<uint64_t> Value = NumericVariable->getValue();
+  if (Value)
+    return *Value;
+
+  return make_error<FileCheckUndefVarError>(Name);
+}
+
+Expected<uint64_t> FileCheckASTBinop::eval() const {
+  Expected<uint64_t> LeftOp = LeftOperand->eval();
+  Expected<uint64_t> RightOp = RightOperand->eval();
+
+  // Bubble up any error (e.g. undefined variables) in the recursive
+  // evaluation.
+  if (!LeftOp || !RightOp) {
+    Error Err = Error::success();
+    if (!LeftOp)
+      Err = joinErrors(std::move(Err), LeftOp.takeError());
+    if (!RightOp)
+      Err = joinErrors(std::move(Err), RightOp.takeError());
+    return std::move(Err);
+  }
+
+  return EvalBinop(*LeftOp, *RightOp);
+}
+
+Expected<std::string> FileCheckNumericSubstitution::getResult() const {
+  Expected<uint64_t> EvaluatedValue = ExpressionAST->eval();
+  if (!EvaluatedValue)
+    return EvaluatedValue.takeError();
+  return utostr(*EvaluatedValue);
+}
+
+Expected<std::string> FileCheckStringSubstitution::getResult() const {
+  // Look up the value and escape it so that we can put it into the regex.
+  Expected<StringRef> VarVal = Context->getPatternVarValue(FromStr);
+  if (!VarVal)
+    return VarVal.takeError();
+  return Regex::escape(*VarVal);
+}
+
+bool FileCheckPattern::isValidVarNameStart(char C) {
+  return C == '_' || isalpha(C);
+}
+
+Expected<FileCheckPattern::VariableProperties>
+FileCheckPattern::parseVariable(StringRef &Str, const SourceMgr &SM) {
+  if (Str.empty())
+    return FileCheckErrorDiagnostic::get(SM, Str, "empty variable name");
+
+  bool ParsedOneChar = false;
+  unsigned I = 0;
+  bool IsPseudo = Str[0] == '@';
+
+  // Global vars start with '$'.
+  if (Str[0] == '$' || IsPseudo)
+    ++I;
+
+  for (unsigned E = Str.size(); I != E; ++I) {
+    if (!ParsedOneChar && !isValidVarNameStart(Str[I]))
+      return FileCheckErrorDiagnostic::get(SM, Str, "invalid variable name");
+
+    // Variable names are composed of alphanumeric characters and underscores.
+    if (Str[I] != '_' && !isalnum(Str[I]))
+      break;
+    ParsedOneChar = true;
+  }
+
+  StringRef Name = Str.take_front(I);
+  Str = Str.substr(I);
+  return VariableProperties {Name, IsPseudo};
+}
+
+// StringRef holding all characters considered as horizontal whitespaces by
+// FileCheck input canonicalization.
+constexpr StringLiteral SpaceChars = " \t";
+
+// Parsing helper function that strips the first character in S and returns it.
+static char popFront(StringRef &S) {
+  char C = S.front();
+  S = S.drop_front();
+  return C;
+}
+
+char FileCheckUndefVarError::ID = 0;
+char FileCheckErrorDiagnostic::ID = 0;
+char FileCheckNotFoundError::ID = 0;
+
+Expected<FileCheckNumericVariable *>
+FileCheckPattern::parseNumericVariableDefinition(
+    StringRef &Expr, FileCheckPatternContext *Context,
+    Optional<size_t> LineNumber, const SourceMgr &SM) {
+  Expected<VariableProperties> ParseVarResult = parseVariable(Expr, SM);
+  if (!ParseVarResult)
+    return ParseVarResult.takeError();
+  StringRef Name = ParseVarResult->Name;
+
+  if (ParseVarResult->IsPseudo)
+    return FileCheckErrorDiagnostic::get(
+        SM, Name, "definition of pseudo numeric variable unsupported");
+
+  // Detect collisions between string and numeric variables when the latter
+  // is created later than the former.
+  if (Context->DefinedVariableTable.find(Name) !=
+      Context->DefinedVariableTable.end())
+    return FileCheckErrorDiagnostic::get(
+        SM, Name, "string variable with name '" + Name + "' already exists");
+
+  Expr = Expr.ltrim(SpaceChars);
+  if (!Expr.empty())
+    return FileCheckErrorDiagnostic::get(
+        SM, Expr, "unexpected characters after numeric variable name");
+
+  FileCheckNumericVariable *DefinedNumericVariable;
+  auto VarTableIter = Context->GlobalNumericVariableTable.find(Name);
+  if (VarTableIter != Context->GlobalNumericVariableTable.end())
+    DefinedNumericVariable = VarTableIter->second;
+  else
+    DefinedNumericVariable = Context->makeNumericVariable(Name, LineNumber);
+
+  return DefinedNumericVariable;
+}
+
+Expected<std::unique_ptr<FileCheckNumericVariableUse>>
+FileCheckPattern::parseNumericVariableUse(StringRef Name, bool IsPseudo,
+                                          Optional<size_t> LineNumber,
+                                          FileCheckPatternContext *Context,
+                                          const SourceMgr &SM) {
+  if (IsPseudo && !Name.equals("@LINE"))
+    return FileCheckErrorDiagnostic::get(
+        SM, Name, "invalid pseudo numeric variable '" + Name + "'");
+
+  // Numeric variable definitions and uses are parsed in the order in which
+  // they appear in the CHECK patterns. For each definition, the pointer to the
+  // class instance of the corresponding numeric variable definition is stored
+  // in GlobalNumericVariableTable in parsePattern. Therefore, if the pointer
+  // we get below is null, it means no such variable was defined before. When
+  // that happens, we create a dummy variable so that parsing can continue. All
+  // uses of undefined variables, whether string or numeric, are then diagnosed
+  // in printSubstitutions() after failing to match.
+  auto VarTableIter = Context->GlobalNumericVariableTable.find(Name);
+  FileCheckNumericVariable *NumericVariable;
+  if (VarTableIter != Context->GlobalNumericVariableTable.end())
+    NumericVariable = VarTableIter->second;
+  else {
+    NumericVariable = Context->makeNumericVariable(Name);
+    Context->GlobalNumericVariableTable[Name] = NumericVariable;
+  }
+
+  Optional<size_t> DefLineNumber = NumericVariable->getDefLineNumber();
+  if (DefLineNumber && LineNumber && *DefLineNumber == *LineNumber)
+    return FileCheckErrorDiagnostic::get(
+        SM, Name,
+        "numeric variable '" + Name +
+            "' defined earlier in the same CHECK directive");
+
+  return std::make_unique<FileCheckNumericVariableUse>(Name, NumericVariable);
+}
+
+Expected<std::unique_ptr<FileCheckExpressionAST>>
+FileCheckPattern::parseNumericOperand(StringRef &Expr, AllowedOperand AO,
+                                      Optional<size_t> LineNumber,
+                                      FileCheckPatternContext *Context,
+                                      const SourceMgr &SM) {
+  if (AO == AllowedOperand::LineVar || AO == AllowedOperand::Any) {
+    // Try to parse as a numeric variable use.
+    Expected<FileCheckPattern::VariableProperties> ParseVarResult =
+        parseVariable(Expr, SM);
+    if (ParseVarResult)
+      return parseNumericVariableUse(ParseVarResult->Name,
+                                     ParseVarResult->IsPseudo, LineNumber,
+                                     Context, SM);
+    if (AO == AllowedOperand::LineVar)
+      return ParseVarResult.takeError();
+    // Ignore the error and retry parsing as a literal.
+    consumeError(ParseVarResult.takeError());
+  }
+
+  // Otherwise, parse it as a literal.
+  uint64_t LiteralValue;
+  if (!Expr.consumeInteger(/*Radix=*/10, LiteralValue))
+    return std::make_unique<FileCheckExpressionLiteral>(LiteralValue);
+
+  return FileCheckErrorDiagnostic::get(SM, Expr,
+                                       "invalid operand format '" + Expr + "'");
+}
+
+static uint64_t add(uint64_t LeftOp, uint64_t RightOp) {
+  return LeftOp + RightOp;
+}
+
+static uint64_t sub(uint64_t LeftOp, uint64_t RightOp) {
+  return LeftOp - RightOp;
+}
+
+Expected<std::unique_ptr<FileCheckExpressionAST>> FileCheckPattern::parseBinop(
+    StringRef &Expr, std::unique_ptr<FileCheckExpressionAST> LeftOp,
+    bool IsLegacyLineExpr, Optional<size_t> LineNumber,
+    FileCheckPatternContext *Context, const SourceMgr &SM) {
+  Expr = Expr.ltrim(SpaceChars);
+  if (Expr.empty())
+    return std::move(LeftOp);
+
+  // Check if this is a supported operation and select a function to perform
+  // it.
+  SMLoc OpLoc = SMLoc::getFromPointer(Expr.data());
+  char Operator = popFront(Expr);
+  binop_eval_t EvalBinop;
+  switch (Operator) {
+  case '+':
+    EvalBinop = add;
+    break;
+  case '-':
+    EvalBinop = sub;
+    break;
+  default:
+    return FileCheckErrorDiagnostic::get(
+        SM, OpLoc, Twine("unsupported operation '") + Twine(Operator) + "'");
+  }
+
+  // Parse right operand.
+  Expr = Expr.ltrim(SpaceChars);
+  if (Expr.empty())
+    return FileCheckErrorDiagnostic::get(SM, Expr,
+                                         "missing operand in expression");
+  // The second operand in a legacy @LINE expression is always a literal.
+  AllowedOperand AO =
+      IsLegacyLineExpr ? AllowedOperand::Literal : AllowedOperand::Any;
+  Expected<std::unique_ptr<FileCheckExpressionAST>> RightOpResult =
+      parseNumericOperand(Expr, AO, LineNumber, Context, SM);
+  if (!RightOpResult)
+    return RightOpResult;
+
+  Expr = Expr.ltrim(SpaceChars);
+  return std::make_unique<FileCheckASTBinop>(EvalBinop, std::move(LeftOp),
+                                              std::move(*RightOpResult));
+}
+
+Expected<std::unique_ptr<FileCheckExpressionAST>>
+FileCheckPattern::parseNumericSubstitutionBlock(
+    StringRef Expr,
+    Optional<FileCheckNumericVariable *> &DefinedNumericVariable,
+    bool IsLegacyLineExpr, Optional<size_t> LineNumber,
+    FileCheckPatternContext *Context, const SourceMgr &SM) {
+  std::unique_ptr<FileCheckExpressionAST> ExpressionAST = nullptr;
+  StringRef DefExpr = StringRef();
+  DefinedNumericVariable = None;
+  // Save variable definition expression if any.
+  size_t DefEnd = Expr.find(':');
+  if (DefEnd != StringRef::npos) {
+    DefExpr = Expr.substr(0, DefEnd);
+    Expr = Expr.substr(DefEnd + 1);
+  }
+
+  // Parse the expression itself.
+  Expr = Expr.ltrim(SpaceChars);
+  if (!Expr.empty()) {
+    // The first operand in a legacy @LINE expression is always the @LINE
+    // pseudo variable.
+    AllowedOperand AO =
+        IsLegacyLineExpr ? AllowedOperand::LineVar : AllowedOperand::Any;
+    Expected<std::unique_ptr<FileCheckExpressionAST>> ParseResult =
+        parseNumericOperand(Expr, AO, LineNumber, Context, SM);
+    while (ParseResult && !Expr.empty()) {
+      ParseResult = parseBinop(Expr, std::move(*ParseResult), IsLegacyLineExpr,
+                               LineNumber, Context, SM);
+      // Legacy @LINE expressions only allow 2 operands.
+      if (ParseResult && IsLegacyLineExpr && !Expr.empty())
+        return FileCheckErrorDiagnostic::get(
+            SM, Expr,
+            "unexpected characters at end of expression '" + Expr + "'");
+    }
+    if (!ParseResult)
+      return ParseResult;
+    ExpressionAST = std::move(*ParseResult);
+  }
+
+  // Parse the numeric variable definition.
+  if (DefEnd != StringRef::npos) {
+    DefExpr = DefExpr.ltrim(SpaceChars);
+    Expected<FileCheckNumericVariable *> ParseResult =
+        parseNumericVariableDefinition(DefExpr, Context, LineNumber, SM);
+
+    if (!ParseResult)
+      return ParseResult.takeError();
+    DefinedNumericVariable = *ParseResult;
+  }
+
+  return std::move(ExpressionAST);
+}
+
+bool FileCheckPattern::parsePattern(StringRef PatternStr, StringRef Prefix,
+                                    SourceMgr &SM,
+                                    const FileCheckRequest &Req) {
+  bool MatchFullLinesHere = Req.MatchFullLines && CheckTy != Check::CheckNot;
+
+  PatternLoc = SMLoc::getFromPointer(PatternStr.data());
+
+  if (!(Req.NoCanonicalizeWhiteSpace && Req.MatchFullLines))
+    // Ignore trailing whitespace.
+    while (!PatternStr.empty() &&
+           (PatternStr.back() == ' ' || PatternStr.back() == '\t'))
+      PatternStr = PatternStr.substr(0, PatternStr.size() - 1);
+
+  // Check that there is something on the line.
+  if (PatternStr.empty() && CheckTy != Check::CheckEmpty) {
+    SM.PrintMessage(PatternLoc, SourceMgr::DK_Error,
+                    "found empty check string with prefix '" + Prefix + ":'");
+    return true;
+  }
+
+  if (!PatternStr.empty() && CheckTy == Check::CheckEmpty) {
+    SM.PrintMessage(
+        PatternLoc, SourceMgr::DK_Error,
+        "found non-empty check string for empty check with prefix '" + Prefix +
+            ":'");
+    return true;
+  }
+
+  if (CheckTy == Check::CheckEmpty) {
+    RegExStr = "(\n$)";
+    return false;
+  }
+
+  // Check to see if this is a fixed string, or if it has regex pieces.
+  if (!MatchFullLinesHere &&
+      (PatternStr.size() < 2 || (PatternStr.find("{{") == StringRef::npos &&
+                                 PatternStr.find("[[") == StringRef::npos))) {
+    FixedStr = PatternStr;
+    return false;
+  }
+
+  if (MatchFullLinesHere) {
+    RegExStr += '^';
+    if (!Req.NoCanonicalizeWhiteSpace)
+      RegExStr += " *";
+  }
+
+  // Paren value #0 is for the fully matched string.  Any new parenthesized
+  // values add from there.
+  unsigned CurParen = 1;
+
+  // Otherwise, there is at least one regex piece.  Build up the regex pattern
+  // by escaping scary characters in fixed strings, building up one big regex.
+  while (!PatternStr.empty()) {
+    // RegEx matches.
+    if (PatternStr.startswith("{{")) {
+      // This is the start of a regex match.  Scan for the }}.
+      size_t End = PatternStr.find("}}");
+      if (End == StringRef::npos) {
+        SM.PrintMessage(SMLoc::getFromPointer(PatternStr.data()),
+                        SourceMgr::DK_Error,
+                        "found start of regex string with no end '}}'");
+        return true;
+      }
+
+      // Enclose {{}} patterns in parens just like [[]] even though we're not
+      // capturing the result for any purpose.  This is required in case the
+      // expression contains an alternation like: CHECK:  abc{{x|z}}def.  We
+      // want this to turn into: "abc(x|z)def" not "abcx|zdef".
+      RegExStr += '(';
+      ++CurParen;
+
+      if (AddRegExToRegEx(PatternStr.substr(2, End - 2), CurParen, SM))
+        return true;
+      RegExStr += ')';
+
+      PatternStr = PatternStr.substr(End + 2);
+      continue;
+    }
+
+    // String and numeric substitution blocks. Pattern substitution blocks come
+    // in two forms: [[foo:.*]] and [[foo]]. The former matches .* (or some
+    // other regex) and assigns it to the string variable 'foo'. The latter
+    // substitutes foo's value. Numeric substitution blocks recognize the same
+    // form as string ones, but start with a '#' sign after the double
+    // brackets. They also accept a combined form which sets a numeric variable
+    // to the evaluation of an expression. Both string and numeric variable
+    // names must satisfy the regular expression "[a-zA-Z_][0-9a-zA-Z_]*" to be
+    // valid, as this helps catch some common errors.
+    if (PatternStr.startswith("[[")) {
+      StringRef UnparsedPatternStr = PatternStr.substr(2);
+      // Find the closing bracket pair ending the match.  End is going to be an
+      // offset relative to the beginning of the match string.
+      size_t End = FindRegexVarEnd(UnparsedPatternStr, SM);
+      StringRef MatchStr = UnparsedPatternStr.substr(0, End);
+      bool IsNumBlock = MatchStr.consume_front("#");
+
+      if (End == StringRef::npos) {
+        SM.PrintMessage(SMLoc::getFromPointer(PatternStr.data()),
+                        SourceMgr::DK_Error,
+                        "Invalid substitution block, no ]] found");
+        return true;
+      }
+      // Strip the substitution block we are parsing. End points to the start
+      // of the "]]" closing the expression so account for it in computing the
+      // index of the first unparsed character.
+      PatternStr = UnparsedPatternStr.substr(End + 2);
+
+      bool IsDefinition = false;
+      bool SubstNeeded = false;
+      // Whether the substitution block is a legacy use of @LINE with string
+      // substitution block syntax.
+      bool IsLegacyLineExpr = false;
+      StringRef DefName;
+      StringRef SubstStr;
+      StringRef MatchRegexp;
+      size_t SubstInsertIdx = RegExStr.size();
+
+      // Parse string variable or legacy @LINE expression.
+      if (!IsNumBlock) {
+        size_t VarEndIdx = MatchStr.find(":");
+        size_t SpacePos = MatchStr.substr(0, VarEndIdx).find_first_of(" \t");
+        if (SpacePos != StringRef::npos) {
+          SM.PrintMessage(SMLoc::getFromPointer(MatchStr.data() + SpacePos),
+                          SourceMgr::DK_Error, "unexpected whitespace");
+          return true;
+        }
+
+        // Get the name (e.g. "foo") and verify it is well formed.
+        StringRef OrigMatchStr = MatchStr;
+        Expected<FileCheckPattern::VariableProperties> ParseVarResult =
+            parseVariable(MatchStr, SM);
+        if (!ParseVarResult) {
+          logAllUnhandledErrors(ParseVarResult.takeError(), errs());
+          return true;
+        }
+        StringRef Name = ParseVarResult->Name;
+        bool IsPseudo = ParseVarResult->IsPseudo;
+
+        IsDefinition = (VarEndIdx != StringRef::npos);
+        SubstNeeded = !IsDefinition;
+        if (IsDefinition) {
+          if ((IsPseudo || !MatchStr.consume_front(":"))) {
+            SM.PrintMessage(SMLoc::getFromPointer(Name.data()),
+                            SourceMgr::DK_Error,
+                            "invalid name in string variable definition");
+            return true;
+          }
+
+          // Detect collisions between string and numeric variables when the
+          // former is created later than the latter.
+          if (Context->GlobalNumericVariableTable.find(Name) !=
+              Context->GlobalNumericVariableTable.end()) {
+            SM.PrintMessage(
+                SMLoc::getFromPointer(Name.data()), SourceMgr::DK_Error,
+                "numeric variable with name '" + Name + "' already exists");
+            return true;
+          }
+          DefName = Name;
+          MatchRegexp = MatchStr;
+        } else {
+          if (IsPseudo) {
+            MatchStr = OrigMatchStr;
+            IsLegacyLineExpr = IsNumBlock = true;
+          } else
+            SubstStr = Name;
+        }
+      }
+
+      // Parse numeric substitution block.
+      std::unique_ptr<FileCheckExpressionAST> ExpressionAST;
+      Optional<FileCheckNumericVariable *> DefinedNumericVariable;
+      if (IsNumBlock) {
+        Expected<std::unique_ptr<FileCheckExpressionAST>> ParseResult =
+            parseNumericSubstitutionBlock(MatchStr, DefinedNumericVariable,
+                                          IsLegacyLineExpr, LineNumber, Context,
+                                          SM);
+        if (!ParseResult) {
+          logAllUnhandledErrors(ParseResult.takeError(), errs());
+          return true;
+        }
+        ExpressionAST = std::move(*ParseResult);
+        SubstNeeded = ExpressionAST != nullptr;
+        if (DefinedNumericVariable) {
+          IsDefinition = true;
+          DefName = (*DefinedNumericVariable)->getName();
+        }
+        if (SubstNeeded)
+          SubstStr = MatchStr;
+        else
+          MatchRegexp = "[0-9]+";
+      }
+
+      // Handle variable definition: [[<def>:(...)]] and [[#(...)<def>:(...)]].
+      if (IsDefinition) {
+        RegExStr += '(';
+        ++SubstInsertIdx;
+
+        if (IsNumBlock) {
+          FileCheckNumericVariableMatch NumericVariableDefinition = {
+              *DefinedNumericVariable, CurParen};
+          NumericVariableDefs[DefName] = NumericVariableDefinition;
+          // This store is done here rather than in match() to allow
+          // parseNumericVariableUse() to get the pointer to the class instance
+          // of the right variable definition corresponding to a given numeric
+          // variable use.
+          Context->GlobalNumericVariableTable[DefName] =
+              *DefinedNumericVariable;
+        } else {
+          VariableDefs[DefName] = CurParen;
+          // Mark string variable as defined to detect collisions between
+          // string and numeric variables in parseNumericVariableUse() and
+          // defineCmdlineVariables() when the latter is created later than the
+          // former. We cannot reuse GlobalVariableTable for this by populating
+          // it with an empty string since we would then lose the ability to
+          // detect the use of an undefined variable in match().
+          Context->DefinedVariableTable[DefName] = true;
+        }
+
+        ++CurParen;
+      }
+
+      if (!MatchRegexp.empty() && AddRegExToRegEx(MatchRegexp, CurParen, SM))
+        return true;
+
+      if (IsDefinition)
+        RegExStr += ')';
+
+      // Handle substitutions: [[foo]] and [[#<foo expr>]].
+      if (SubstNeeded) {
+        // Handle substitution of string variables that were defined earlier on
+        // the same line by emitting a backreference. Expressions do not
+        // support substituting a numeric variable defined on the same line.
+        if (!IsNumBlock && VariableDefs.find(SubstStr) != VariableDefs.end()) {
+          unsigned CaptureParenGroup = VariableDefs[SubstStr];
+          if (CaptureParenGroup < 1 || CaptureParenGroup > 9) {
+            SM.PrintMessage(SMLoc::getFromPointer(SubstStr.data()),
+                            SourceMgr::DK_Error,
+                            "Can't back-reference more than 9 variables");
+            return true;
+          }
+          AddBackrefToRegEx(CaptureParenGroup);
+        } else {
+          // Handle substitution of string variables ([[<var>]]) defined in
+          // previous CHECK patterns, and substitution of expressions.
+          FileCheckSubstitution *Substitution =
+              IsNumBlock
+                  ? Context->makeNumericSubstitution(
+                        SubstStr, std::move(ExpressionAST), SubstInsertIdx)
+                  : Context->makeStringSubstitution(SubstStr, SubstInsertIdx);
+          Substitutions.push_back(Substitution);
+        }
+      }
+    }
+
+    // Handle fixed string matches.
+    // Find the end, which is the start of the next regex.
+    size_t FixedMatchEnd = PatternStr.find("{{");
+    FixedMatchEnd = std::min(FixedMatchEnd, PatternStr.find("[["));
+    RegExStr += Regex::escape(PatternStr.substr(0, FixedMatchEnd));
+    PatternStr = PatternStr.substr(FixedMatchEnd);
+  }
+
+  if (MatchFullLinesHere) {
+    if (!Req.NoCanonicalizeWhiteSpace)
+      RegExStr += " *";
+    RegExStr += '$';
+  }
+
+  return false;
+}
+
+bool FileCheckPattern::AddRegExToRegEx(StringRef RS, unsigned &CurParen, SourceMgr &SM) {
+  Regex R(RS);
+  std::string Error;
+  if (!R.isValid(Error)) {
+    SM.PrintMessage(SMLoc::getFromPointer(RS.data()), SourceMgr::DK_Error,
+                    "invalid regex: " + Error);
+    return true;
+  }
+
+  RegExStr += RS.str();
+  CurParen += R.getNumMatches();
+  return false;
+}
+
+void FileCheckPattern::AddBackrefToRegEx(unsigned BackrefNum) {
+  assert(BackrefNum >= 1 && BackrefNum <= 9 && "Invalid backref number");
+  std::string Backref = std::string("\\") + std::string(1, '0' + BackrefNum);
+  RegExStr += Backref;
+}
+
+Expected<size_t> FileCheckPattern::match(StringRef Buffer, size_t &MatchLen,
+                                         const SourceMgr &SM) const {
+  // If this is the EOF pattern, match it immediately.
+  if (CheckTy == Check::CheckEOF) {
+    MatchLen = 0;
+    return Buffer.size();
+  }
+
+  // If this is a fixed string pattern, just match it now.
+  if (!FixedStr.empty()) {
+    MatchLen = FixedStr.size();
+    size_t Pos = Buffer.find(FixedStr);
+    if (Pos == StringRef::npos)
+      return make_error<FileCheckNotFoundError>();
+    return Pos;
+  }
+
+  // Regex match.
+
+  // If there are substitutions, we need to create a temporary string with the
+  // actual value.
+  StringRef RegExToMatch = RegExStr;
+  std::string TmpStr;
+  if (!Substitutions.empty()) {
+    TmpStr = RegExStr;
+    if (LineNumber)
+      Context->LineVariable->setValue(*LineNumber);
+
+    size_t InsertOffset = 0;
+    // Substitute all string variables and expressions whose values are only
+    // now known. Use of string variables defined on the same line are handled
+    // by back-references.
+    for (const auto &Substitution : Substitutions) {
+      // Substitute and check for failure (e.g. use of undefined variable).
+      Expected<std::string> Value = Substitution->getResult();
+      if (!Value)
+        return Value.takeError();
+
+      // Plop it into the regex at the adjusted offset.
+      TmpStr.insert(TmpStr.begin() + Substitution->getIndex() + InsertOffset,
+                    Value->begin(), Value->end());
+      InsertOffset += Value->size();
+    }
+
+    // Match the newly constructed regex.
+    RegExToMatch = TmpStr;
+  }
+
+  SmallVector<StringRef, 4> MatchInfo;
+  if (!Regex(RegExToMatch, Regex::Newline).match(Buffer, &MatchInfo))
+    return make_error<FileCheckNotFoundError>();
+
+  // Successful regex match.
+  assert(!MatchInfo.empty() && "Didn't get any match");
+  StringRef FullMatch = MatchInfo[0];
+
+  // If this defines any string variables, remember their values.
+  for (const auto &VariableDef : VariableDefs) {
+    assert(VariableDef.second < MatchInfo.size() && "Internal paren error");
+    Context->GlobalVariableTable[VariableDef.first] =
+        MatchInfo[VariableDef.second];
+  }
+
+  // If this defines any numeric variables, remember their values.
+  for (const auto &NumericVariableDef : NumericVariableDefs) {
+    const FileCheckNumericVariableMatch &NumericVariableMatch =
+        NumericVariableDef.getValue();
+    unsigned CaptureParenGroup = NumericVariableMatch.CaptureParenGroup;
+    assert(CaptureParenGroup < MatchInfo.size() && "Internal paren error");
+    FileCheckNumericVariable *DefinedNumericVariable =
+        NumericVariableMatch.DefinedNumericVariable;
+
+    StringRef MatchedValue = MatchInfo[CaptureParenGroup];
+    uint64_t Val;
+    if (MatchedValue.getAsInteger(10, Val))
+      return FileCheckErrorDiagnostic::get(SM, MatchedValue,
+                                           "Unable to represent numeric value");
+    DefinedNumericVariable->setValue(Val);
+  }
+
+  // Like CHECK-NEXT, CHECK-EMPTY's match range is considered to start after
+  // the required preceding newline, which is consumed by the pattern in the
+  // case of CHECK-EMPTY but not CHECK-NEXT.
+  size_t MatchStartSkip = CheckTy == Check::CheckEmpty;
+  MatchLen = FullMatch.size() - MatchStartSkip;
+  return FullMatch.data() - Buffer.data() + MatchStartSkip;
+}
+
+unsigned FileCheckPattern::computeMatchDistance(StringRef Buffer) const {
+  // Just compute the number of matching characters. For regular expressions, we
+  // just compare against the regex itself and hope for the best.
+  //
+  // FIXME: One easy improvement here is have the regex lib generate a single
+  // example regular expression which matches, and use that as the example
+  // string.
+  StringRef ExampleString(FixedStr);
+  if (ExampleString.empty())
+    ExampleString = RegExStr;
+
+  // Only compare up to the first line in the buffer, or the string size.
+  StringRef BufferPrefix = Buffer.substr(0, ExampleString.size());
+  BufferPrefix = BufferPrefix.split('\n').first;
+  return BufferPrefix.edit_distance(ExampleString);
+}
+
+void FileCheckPattern::printSubstitutions(const SourceMgr &SM, StringRef Buffer,
+                                          SMRange MatchRange) const {
+  // Print what we know about substitutions.
+  if (!Substitutions.empty()) {
+    for (const auto &Substitution : Substitutions) {
+      SmallString<256> Msg;
+      raw_svector_ostream OS(Msg);
+      Expected<std::string> MatchedValue = Substitution->getResult();
+
+      // Substitution failed or is not known at match time, print the undefined
+      // variables it uses.
+      if (!MatchedValue) {
+        bool UndefSeen = false;
+        handleAllErrors(MatchedValue.takeError(),
+                        [](const FileCheckNotFoundError &E) {},
+                        // Handled in PrintNoMatch().
+                        [](const FileCheckErrorDiagnostic &E) {},
+                        [&](const FileCheckUndefVarError &E) {
+                          if (!UndefSeen) {
+                            OS << "uses undefined variable(s):";
+                            UndefSeen = true;
+                          }
+                          OS << " ";
+                          E.log(OS);
+                        });
+      } else {
+        // Substitution succeeded. Print substituted value.
+        OS << "with \"";
+        OS.write_escaped(Substitution->getFromString()) << "\" equal to \"";
+        OS.write_escaped(*MatchedValue) << "\"";
+      }
+
+      if (MatchRange.isValid())
+        SM.PrintMessage(MatchRange.Start, SourceMgr::DK_Note, OS.str(),
+                        {MatchRange});
+      else
+        SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()),
+                        SourceMgr::DK_Note, OS.str());
+    }
+  }
+}
+
+static SMRange ProcessMatchResult(FileCheckDiag::MatchType MatchTy,
+                                  const SourceMgr &SM, SMLoc Loc,
+                                  Check::FileCheckType CheckTy,
+                                  StringRef Buffer, size_t Pos, size_t Len,
+                                  std::vector<FileCheckDiag> *Diags,
+                                  bool AdjustPrevDiag = false) {
+  SMLoc Start = SMLoc::getFromPointer(Buffer.data() + Pos);
+  SMLoc End = SMLoc::getFromPointer(Buffer.data() + Pos + Len);
+  SMRange Range(Start, End);
+  if (Diags) {
+    if (AdjustPrevDiag)
+      Diags->rbegin()->MatchTy = MatchTy;
+    else
+      Diags->emplace_back(SM, CheckTy, Loc, MatchTy, Range);
+  }
+  return Range;
+}
+
+void FileCheckPattern::printFuzzyMatch(
+    const SourceMgr &SM, StringRef Buffer,
+    std::vector<FileCheckDiag> *Diags) const {
+  // Attempt to find the closest/best fuzzy match.  Usually an error happens
+  // because some string in the output didn't exactly match. In these cases, we
+  // would like to show the user a best guess at what "should have" matched, to
+  // save them having to actually check the input manually.
+  size_t NumLinesForward = 0;
+  size_t Best = StringRef::npos;
+  double BestQuality = 0;
+
+  // Use an arbitrary 4k limit on how far we will search.
+  for (size_t i = 0, e = std::min(size_t(4096), Buffer.size()); i != e; ++i) {
+    if (Buffer[i] == '\n')
+      ++NumLinesForward;
+
+    // Patterns have leading whitespace stripped, so skip whitespace when
+    // looking for something which looks like a pattern.
+    if (Buffer[i] == ' ' || Buffer[i] == '\t')
+      continue;
+
+    // Compute the "quality" of this match as an arbitrary combination of the
+    // match distance and the number of lines skipped to get to this match.
+    unsigned Distance = computeMatchDistance(Buffer.substr(i));
+    double Quality = Distance + (NumLinesForward / 100.);
+
+    if (Quality < BestQuality || Best == StringRef::npos) {
+      Best = i;
+      BestQuality = Quality;
+    }
+  }
+
+  // Print the "possible intended match here" line if we found something
+  // reasonable and not equal to what we showed in the "scanning from here"
+  // line.
+  if (Best && Best != StringRef::npos && BestQuality < 50) {
+    SMRange MatchRange =
+        ProcessMatchResult(FileCheckDiag::MatchFuzzy, SM, getLoc(),
+                           getCheckTy(), Buffer, Best, 0, Diags);
+    SM.PrintMessage(MatchRange.Start, SourceMgr::DK_Note,
+                    "possible intended match here");
+
+    // FIXME: If we wanted to be really friendly we would show why the match
+    // failed, as it can be hard to spot simple one character differences.
+  }
+}
+
+Expected<StringRef>
+FileCheckPatternContext::getPatternVarValue(StringRef VarName) {
+  auto VarIter = GlobalVariableTable.find(VarName);
+  if (VarIter == GlobalVariableTable.end())
+    return make_error<FileCheckUndefVarError>(VarName);
+
+  return VarIter->second;
+}
+
+template <class... Types>
+FileCheckNumericVariable *
+FileCheckPatternContext::makeNumericVariable(Types... args) {
+  NumericVariables.push_back(
+      std::make_unique<FileCheckNumericVariable>(args...));
+  return NumericVariables.back().get();
+}
+
+FileCheckSubstitution *
+FileCheckPatternContext::makeStringSubstitution(StringRef VarName,
+                                                size_t InsertIdx) {
+  Substitutions.push_back(
+      std::make_unique<FileCheckStringSubstitution>(this, VarName, InsertIdx));
+  return Substitutions.back().get();
+}
+
+FileCheckSubstitution *FileCheckPatternContext::makeNumericSubstitution(
+    StringRef ExpressionStr,
+    std::unique_ptr<FileCheckExpressionAST> ExpressionAST, size_t InsertIdx) {
+  Substitutions.push_back(std::make_unique<FileCheckNumericSubstitution>(
+      this, ExpressionStr, std::move(ExpressionAST), InsertIdx));
+  return Substitutions.back().get();
+}
+
+size_t FileCheckPattern::FindRegexVarEnd(StringRef Str, SourceMgr &SM) {
+  // Offset keeps track of the current offset within the input Str
+  size_t Offset = 0;
+  // [...] Nesting depth
+  size_t BracketDepth = 0;
+
+  while (!Str.empty()) {
+    if (Str.startswith("]]") && BracketDepth == 0)
+      return Offset;
+    if (Str[0] == '\\') {
+      // Backslash escapes the next char within regexes, so skip them both.
+      Str = Str.substr(2);
+      Offset += 2;
+    } else {
+      switch (Str[0]) {
+      default:
+        break;
+      case '[':
+        BracketDepth++;
+        break;
+      case ']':
+        if (BracketDepth == 0) {
+          SM.PrintMessage(SMLoc::getFromPointer(Str.data()),
+                          SourceMgr::DK_Error,
+                          "missing closing \"]\" for regex variable");
+          exit(1);
+        }
+        BracketDepth--;
+        break;
+      }
+      Str = Str.substr(1);
+      Offset++;
+    }
+  }
+
+  return StringRef::npos;
+}
+
+StringRef FileCheck::CanonicalizeFile(MemoryBuffer &MB,
+                                      SmallVectorImpl<char> &OutputBuffer) {
+  OutputBuffer.reserve(MB.getBufferSize());
+
+  for (const char *Ptr = MB.getBufferStart(), *End = MB.getBufferEnd();
+       Ptr != End; ++Ptr) {
+    // Eliminate trailing dosish \r.
+    if (Ptr <= End - 2 && Ptr[0] == '\r' && Ptr[1] == '\n') {
+      continue;
+    }
+
+    // If current char is not a horizontal whitespace or if horizontal
+    // whitespace canonicalization is disabled, dump it to output as is.
+    if (Req.NoCanonicalizeWhiteSpace || (*Ptr != ' ' && *Ptr != '\t')) {
+      OutputBuffer.push_back(*Ptr);
+      continue;
+    }
+
+    // Otherwise, add one space and advance over neighboring space.
+    OutputBuffer.push_back(' ');
+    while (Ptr + 1 != End && (Ptr[1] == ' ' || Ptr[1] == '\t'))
+      ++Ptr;
+  }
+
+  // Add a null byte and then return all but that byte.
+  OutputBuffer.push_back('\0');
+  return StringRef(OutputBuffer.data(), OutputBuffer.size() - 1);
+}
+
+FileCheckDiag::FileCheckDiag(const SourceMgr &SM,
+                             const Check::FileCheckType &CheckTy,
+                             SMLoc CheckLoc, MatchType MatchTy,
+                             SMRange InputRange)
+    : CheckTy(CheckTy), MatchTy(MatchTy) {
+  auto Start = SM.getLineAndColumn(InputRange.Start);
+  auto End = SM.getLineAndColumn(InputRange.End);
+  InputStartLine = Start.first;
+  InputStartCol = Start.second;
+  InputEndLine = End.first;
+  InputEndCol = End.second;
+  Start = SM.getLineAndColumn(CheckLoc);
+  CheckLine = Start.first;
+  CheckCol = Start.second;
+}
+
+static bool IsPartOfWord(char c) {
+  return (isalnum(c) || c == '-' || c == '_');
+}
+
+Check::FileCheckType &Check::FileCheckType::setCount(int C) {
+  assert(Count > 0 && "zero and negative counts are not supported");
+  assert((C == 1 || Kind == CheckPlain) &&
+         "count supported only for plain CHECK directives");
+  Count = C;
+  return *this;
+}
+
+std::string Check::FileCheckType::getDescription(StringRef Prefix) const {
+  switch (Kind) {
+  case Check::CheckNone:
+    return "invalid";
+  case Check::CheckPlain:
+    if (Count > 1)
+      return Prefix.str() + "-COUNT";
+    return Prefix;
+  case Check::CheckNext:
+    return Prefix.str() + "-NEXT";
+  case Check::CheckSame:
+    return Prefix.str() + "-SAME";
+  case Check::CheckNot:
+    return Prefix.str() + "-NOT";
+  case Check::CheckDAG:
+    return Prefix.str() + "-DAG";
+  case Check::CheckLabel:
+    return Prefix.str() + "-LABEL";
+  case Check::CheckEmpty:
+    return Prefix.str() + "-EMPTY";
+  case Check::CheckEOF:
+    return "implicit EOF";
+  case Check::CheckBadNot:
+    return "bad NOT";
+  case Check::CheckBadCount:
+    return "bad COUNT";
+  }
+  llvm_unreachable("unknown FileCheckType");
+}
+
+static std::pair<Check::FileCheckType, StringRef>
+FindCheckType(StringRef Buffer, StringRef Prefix) {
+  if (Buffer.size() <= Prefix.size())
+    return {Check::CheckNone, StringRef()};
+
+  char NextChar = Buffer[Prefix.size()];
+
+  StringRef Rest = Buffer.drop_front(Prefix.size() + 1);
+  // Verify that the : is present after the prefix.
+  if (NextChar == ':')
+    return {Check::CheckPlain, Rest};
+
+  if (NextChar != '-')
+    return {Check::CheckNone, StringRef()};
+
+  if (Rest.consume_front("COUNT-")) {
+    int64_t Count;
+    if (Rest.consumeInteger(10, Count))
+      // Error happened in parsing integer.
+      return {Check::CheckBadCount, Rest};
+    if (Count <= 0 || Count > INT32_MAX)
+      return {Check::CheckBadCount, Rest};
+    if (!Rest.consume_front(":"))
+      return {Check::CheckBadCount, Rest};
+    return {Check::FileCheckType(Check::CheckPlain).setCount(Count), Rest};
+  }
+
+  if (Rest.consume_front("NEXT:"))
+    return {Check::CheckNext, Rest};
+
+  if (Rest.consume_front("SAME:"))
+    return {Check::CheckSame, Rest};
+
+  if (Rest.consume_front("NOT:"))
+    return {Check::CheckNot, Rest};
+
+  if (Rest.consume_front("DAG:"))
+    return {Check::CheckDAG, Rest};
+
+  if (Rest.consume_front("LABEL:"))
+    return {Check::CheckLabel, Rest};
+
+  if (Rest.consume_front("EMPTY:"))
+    return {Check::CheckEmpty, Rest};
+
+  // 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:") ||
+      Rest.startswith("EMPTY-NOT:") || Rest.startswith("NOT-EMPTY:"))
+    return {Check::CheckBadNot, Rest};
+
+  return {Check::CheckNone, Rest};
+}
+
+// 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;
+}
+
+/// Searches the buffer for the first prefix in the prefix regular expression.
+///
+/// This searches the buffer using the provided regular expression, however it
+/// enforces constraints beyond that:
+/// 1) The found prefix must not be a suffix of something that looks like
+///    a valid prefix.
+/// 2) The found prefix must be followed by a valid check type suffix using \c
+///    FindCheckType above.
+///
+/// \returns a pair of StringRefs into the Buffer, which combines:
+///   - the first match of the regular expression to satisfy these two is
+///   returned,
+///     otherwise an empty StringRef is returned to indicate failure.
+///   - buffer rewound to the location right after parsed suffix, for parsing
+///     to continue from
+///
+/// If this routine returns a valid prefix, it will also shrink \p Buffer to
+/// start at the beginning of the returned prefix, increment \p LineNumber for
+/// each new line consumed from \p Buffer, and set \p CheckTy to the type of
+/// check found by examining the suffix.
+///
+/// If no valid prefix is found, the state of Buffer, LineNumber, and CheckTy
+/// is unspecified.
+static std::pair<StringRef, StringRef>
+FindFirstMatchingPrefix(Regex &PrefixRE, StringRef &Buffer,
+                        unsigned &LineNumber, Check::FileCheckType &CheckTy) {
+  SmallVector<StringRef, 2> Matches;
+
+  while (!Buffer.empty()) {
+    // Find the first (longest) match using the RE.
+    if (!PrefixRE.match(Buffer, &Matches))
+      // No match at all, bail.
+      return {StringRef(), StringRef()};
+
+    StringRef Prefix = Matches[0];
+    Matches.clear();
+
+    assert(Prefix.data() >= Buffer.data() &&
+           Prefix.data() < Buffer.data() + Buffer.size() &&
+           "Prefix doesn't start inside of buffer!");
+    size_t Loc = Prefix.data() - Buffer.data();
+    StringRef Skipped = Buffer.substr(0, Loc);
+    Buffer = Buffer.drop_front(Loc);
+    LineNumber += Skipped.count('\n');
+
+    // Check that the matched prefix isn't a suffix of some other check-like
+    // word.
+    // FIXME: This is a very ad-hoc check. it would be better handled in some
+    // other way. Among other things it seems hard to distinguish between
+    // intentional and unintentional uses of this feature.
+    if (Skipped.empty() || !IsPartOfWord(Skipped.back())) {
+      // Now extract the type.
+      StringRef AfterSuffix;
+      std::tie(CheckTy, AfterSuffix) = FindCheckType(Buffer, Prefix);
+
+      // If we've found a valid check type for this prefix, we're done.
+      if (CheckTy != Check::CheckNone)
+        return {Prefix, AfterSuffix};
+    }
+
+    // If we didn't successfully find a prefix, we need to skip this invalid
+    // prefix and continue scanning. We directly skip the prefix that was
+    // matched and any additional parts of that check-like word.
+    Buffer = Buffer.drop_front(SkipWord(Buffer, Prefix.size()));
+  }
+
+  // We ran out of buffer while skipping partial matches so give up.
+  return {StringRef(), StringRef()};
+}
+
+void FileCheckPatternContext::createLineVariable() {
+  assert(!LineVariable && "@LINE pseudo numeric variable already created");
+  StringRef LineName = "@LINE";
+  LineVariable = makeNumericVariable(LineName);
+  GlobalNumericVariableTable[LineName] = LineVariable;
+}
+
+FileCheck::FileCheck(FileCheckRequest Req)
+    : Req(Req), PatternContext(std::make_unique<FileCheckPatternContext>()),
+      CheckStrings(std::make_unique<std::vector<FileCheckString>>()) {}
+
+FileCheck::~FileCheck() = default;
+
+bool FileCheck::readCheckFile(SourceMgr &SM, StringRef Buffer,
+                              Regex &PrefixRE) {
+  Error DefineError =
+      PatternContext->defineCmdlineVariables(Req.GlobalDefines, SM);
+  if (DefineError) {
+    logAllUnhandledErrors(std::move(DefineError), errs());
+    return true;
+  }
+
+  PatternContext->createLineVariable();
+
+  std::vector<FileCheckPattern> ImplicitNegativeChecks;
+  for (const auto &PatternString : Req.ImplicitCheckNot) {
+    // Create a buffer with fake command line content in order to display the
+    // command line option responsible for the specific implicit CHECK-NOT.
+    std::string Prefix = "-implicit-check-not='";
+    std::string Suffix = "'";
+    std::unique_ptr<MemoryBuffer> CmdLine = MemoryBuffer::getMemBufferCopy(
+        Prefix + PatternString + Suffix, "command line");
+
+    StringRef PatternInBuffer =
+        CmdLine->getBuffer().substr(Prefix.size(), PatternString.size());
+    SM.AddNewSourceBuffer(std::move(CmdLine), SMLoc());
+
+    ImplicitNegativeChecks.push_back(
+        FileCheckPattern(Check::CheckNot, PatternContext.get()));
+    ImplicitNegativeChecks.back().parsePattern(PatternInBuffer,
+                                               "IMPLICIT-CHECK", SM, Req);
+  }
+
+  std::vector<FileCheckPattern> DagNotMatches = ImplicitNegativeChecks;
+
+  // LineNumber keeps track of the line on which CheckPrefix instances are
+  // found.
+  unsigned LineNumber = 1;
+
+  while (1) {
+    Check::FileCheckType CheckTy;
+
+    // See if a prefix occurs in the memory buffer.
+    StringRef UsedPrefix;
+    StringRef AfterSuffix;
+    std::tie(UsedPrefix, AfterSuffix) =
+        FindFirstMatchingPrefix(PrefixRE, Buffer, LineNumber, CheckTy);
+    if (UsedPrefix.empty())
+      break;
+    assert(UsedPrefix.data() == Buffer.data() &&
+           "Failed to move Buffer's start forward, or pointed prefix outside "
+           "of the buffer!");
+    assert(AfterSuffix.data() >= Buffer.data() &&
+           AfterSuffix.data() < Buffer.data() + Buffer.size() &&
+           "Parsing after suffix doesn't start inside of buffer!");
+
+    // Location to use for error messages.
+    const char *UsedPrefixStart = UsedPrefix.data();
+
+    // Skip the buffer to the end of parsed suffix (or just prefix, if no good
+    // suffix was processed).
+    Buffer = AfterSuffix.empty() ? Buffer.drop_front(UsedPrefix.size())
+                                 : AfterSuffix;
+
+    // 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;
+    }
+
+    // Complain about invalid count specification.
+    if (CheckTy == Check::CheckBadCount) {
+      SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Error,
+                      "invalid count in -COUNT specification on prefix '" +
+                          UsedPrefix + "'");
+      return true;
+    }
+
+    // Okay, we found the prefix, yay. Remember the rest of the line, but ignore
+    // leading whitespace.
+    if (!(Req.NoCanonicalizeWhiteSpace && Req.MatchFullLines))
+      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.
+    FileCheckPattern P(CheckTy, PatternContext.get(), LineNumber);
+    if (P.parsePattern(Buffer.substr(0, EOL), UsedPrefix, SM, Req))
+      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/SAME/EMPTY lines have at least one CHECK line before them.
+    if ((CheckTy == Check::CheckNext || CheckTy == Check::CheckSame ||
+         CheckTy == Check::CheckEmpty) &&
+        CheckStrings->empty()) {
+      StringRef Type = CheckTy == Check::CheckNext
+                           ? "NEXT"
+                           : CheckTy == Check::CheckEmpty ? "EMPTY" : "SAME";
+      SM.PrintMessage(SMLoc::getFromPointer(UsedPrefixStart),
+                      SourceMgr::DK_Error,
+                      "found '" + UsedPrefix + "-" + Type +
+                          "' without previous '" + UsedPrefix + ": line");
+      return true;
+    }
+
+    // Handle CHECK-DAG/-NOT.
+    if (CheckTy == Check::CheckDAG || CheckTy == Check::CheckNot) {
+      DagNotMatches.push_back(P);
+      continue;
+    }
+
+    // Okay, add the string we captured to the output vector and move on.
+    CheckStrings->emplace_back(P, UsedPrefix, PatternLoc);
+    std::swap(DagNotMatches, CheckStrings->back().DagNotStrings);
+    DagNotMatches = ImplicitNegativeChecks;
+  }
+
+  // Add an EOF pattern for any trailing CHECK-DAG/-NOTs, and use the first
+  // prefix as a filler for the error message.
+  if (!DagNotMatches.empty()) {
+    CheckStrings->emplace_back(
+        FileCheckPattern(Check::CheckEOF, PatternContext.get(), LineNumber + 1),
+        *Req.CheckPrefixes.begin(), SMLoc::getFromPointer(Buffer.data()));
+    std::swap(DagNotMatches, CheckStrings->back().DagNotStrings);
+  }
+
+  if (CheckStrings->empty()) {
+    errs() << "error: no check strings found with prefix"
+           << (Req.CheckPrefixes.size() > 1 ? "es " : " ");
+    auto I = Req.CheckPrefixes.begin();
+    auto E = Req.CheckPrefixes.end();
+    if (I != E) {
+      errs() << "\'" << *I << ":'";
+      ++I;
+    }
+    for (; I != E; ++I)
+      errs() << ", \'" << *I << ":'";
+
+    errs() << '\n';
+    return true;
+  }
+
+  return false;
+}
+
+static void PrintMatch(bool ExpectedMatch, const SourceMgr &SM,
+                       StringRef Prefix, SMLoc Loc, const FileCheckPattern &Pat,
+                       int MatchedCount, StringRef Buffer, size_t MatchPos,
+                       size_t MatchLen, const FileCheckRequest &Req,
+                       std::vector<FileCheckDiag> *Diags) {
+  bool PrintDiag = true;
+  if (ExpectedMatch) {
+    if (!Req.Verbose)
+      return;
+    if (!Req.VerboseVerbose && Pat.getCheckTy() == Check::CheckEOF)
+      return;
+    // Due to their verbosity, we don't print verbose diagnostics here if we're
+    // gathering them for a different rendering, but we always print other
+    // diagnostics.
+    PrintDiag = !Diags;
+  }
+  SMRange MatchRange = ProcessMatchResult(
+      ExpectedMatch ? FileCheckDiag::MatchFoundAndExpected
+                    : FileCheckDiag::MatchFoundButExcluded,
+      SM, Loc, Pat.getCheckTy(), Buffer, MatchPos, MatchLen, Diags);
+  if (!PrintDiag)
+    return;
+
+  std::string Message = formatv("{0}: {1} string found in input",
+                                Pat.getCheckTy().getDescription(Prefix),
+                                (ExpectedMatch ? "expected" : "excluded"))
+                            .str();
+  if (Pat.getCount() > 1)
+    Message += formatv(" ({0} out of {1})", MatchedCount, Pat.getCount()).str();
+
+  SM.PrintMessage(
+      Loc, ExpectedMatch ? SourceMgr::DK_Remark : SourceMgr::DK_Error, Message);
+  SM.PrintMessage(MatchRange.Start, SourceMgr::DK_Note, "found here",
+                  {MatchRange});
+  Pat.printSubstitutions(SM, Buffer, MatchRange);
+}
+
+static void PrintMatch(bool ExpectedMatch, const SourceMgr &SM,
+                       const FileCheckString &CheckStr, int MatchedCount,
+                       StringRef Buffer, size_t MatchPos, size_t MatchLen,
+                       FileCheckRequest &Req,
+                       std::vector<FileCheckDiag> *Diags) {
+  PrintMatch(ExpectedMatch, SM, CheckStr.Prefix, CheckStr.Loc, CheckStr.Pat,
+             MatchedCount, Buffer, MatchPos, MatchLen, Req, Diags);
+}
+
+static void PrintNoMatch(bool ExpectedMatch, const SourceMgr &SM,
+                         StringRef Prefix, SMLoc Loc,
+                         const FileCheckPattern &Pat, int MatchedCount,
+                         StringRef Buffer, bool VerboseVerbose,
+                         std::vector<FileCheckDiag> *Diags, Error MatchErrors) {
+  assert(MatchErrors && "Called on successful match");
+  bool PrintDiag = true;
+  if (!ExpectedMatch) {
+    if (!VerboseVerbose) {
+      consumeError(std::move(MatchErrors));
+      return;
+    }
+    // Due to their verbosity, we don't print verbose diagnostics here if we're
+    // gathering them for a different rendering, but we always print other
+    // diagnostics.
+    PrintDiag = !Diags;
+  }
+
+  // If the current position is at the end of a line, advance to the start of
+  // the next line.
+  Buffer = Buffer.substr(Buffer.find_first_not_of(" \t\n\r"));
+  SMRange SearchRange = ProcessMatchResult(
+      ExpectedMatch ? FileCheckDiag::MatchNoneButExpected
+                    : FileCheckDiag::MatchNoneAndExcluded,
+      SM, Loc, Pat.getCheckTy(), Buffer, 0, Buffer.size(), Diags);
+  if (!PrintDiag) {
+    consumeError(std::move(MatchErrors));
+    return;
+  }
+
+  MatchErrors =
+      handleErrors(std::move(MatchErrors),
+                   [](const FileCheckErrorDiagnostic &E) { E.log(errs()); });
+
+  // No problem matching the string per se.
+  if (!MatchErrors)
+    return;
+  consumeError(std::move(MatchErrors));
+
+  // Print "not found" diagnostic.
+  std::string Message = formatv("{0}: {1} string not found in input",
+                                Pat.getCheckTy().getDescription(Prefix),
+                                (ExpectedMatch ? "expected" : "excluded"))
+                            .str();
+  if (Pat.getCount() > 1)
+    Message += formatv(" ({0} out of {1})", MatchedCount, Pat.getCount()).str();
+  SM.PrintMessage(
+      Loc, ExpectedMatch ? SourceMgr::DK_Error : SourceMgr::DK_Remark, Message);
+
+  // Print the "scanning from here" line.
+  SM.PrintMessage(SearchRange.Start, SourceMgr::DK_Note, "scanning from here");
+
+  // Allow the pattern to print additional information if desired.
+  Pat.printSubstitutions(SM, Buffer);
+
+  if (ExpectedMatch)
+    Pat.printFuzzyMatch(SM, Buffer, Diags);
+}
+
+static void PrintNoMatch(bool ExpectedMatch, const SourceMgr &SM,
+                         const FileCheckString &CheckStr, int MatchedCount,
+                         StringRef Buffer, bool VerboseVerbose,
+                         std::vector<FileCheckDiag> *Diags, Error MatchErrors) {
+  PrintNoMatch(ExpectedMatch, SM, CheckStr.Prefix, CheckStr.Loc, CheckStr.Pat,
+               MatchedCount, Buffer, VerboseVerbose, Diags,
+               std::move(MatchErrors));
+}
+
+/// Counts the number of newlines in the specified range.
+static unsigned CountNumNewlinesBetween(StringRef Range,
+                                        const char *&FirstNewLine) {
+  unsigned NumNewLines = 0;
+  while (1) {
+    // Scan for newline.
+    Range = Range.substr(Range.find_first_of("\n\r"));
+    if (Range.empty())
+      return NumNewLines;
+
+    ++NumNewLines;
+
+    // Handle \n\r and \r\n as a single newline.
+    if (Range.size() > 1 && (Range[1] == '\n' || Range[1] == '\r') &&
+        (Range[0] != Range[1]))
+      Range = Range.substr(1);
+    Range = Range.substr(1);
+
+    if (NumNewLines == 1)
+      FirstNewLine = Range.begin();
+  }
+}
+
+size_t FileCheckString::Check(const SourceMgr &SM, StringRef Buffer,
+                              bool IsLabelScanMode, size_t &MatchLen,
+                              FileCheckRequest &Req,
+                              std::vector<FileCheckDiag> *Diags) const {
+  size_t LastPos = 0;
+  std::vector<const FileCheckPattern *> NotStrings;
+
+  // IsLabelScanMode is true when we are scanning forward to find CHECK-LABEL
+  // bounds; we have not processed variable definitions within the bounded block
+  // yet so cannot handle any final CHECK-DAG yet; this is handled when going
+  // 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, Req, Diags);
+    if (LastPos == StringRef::npos)
+      return StringRef::npos;
+  }
+
+  // Match itself from the last position after matching CHECK-DAG.
+  size_t LastMatchEnd = LastPos;
+  size_t FirstMatchPos = 0;
+  // Go match the pattern Count times. Majority of patterns only match with
+  // count 1 though.
+  assert(Pat.getCount() != 0 && "pattern count can not be zero");
+  for (int i = 1; i <= Pat.getCount(); i++) {
+    StringRef MatchBuffer = Buffer.substr(LastMatchEnd);
+    size_t CurrentMatchLen;
+    // get a match at current start point
+    Expected<size_t> MatchResult = Pat.match(MatchBuffer, CurrentMatchLen, SM);
+
+    // report
+    if (!MatchResult) {
+      PrintNoMatch(true, SM, *this, i, MatchBuffer, Req.VerboseVerbose, Diags,
+                   MatchResult.takeError());
+      return StringRef::npos;
+    }
+    size_t MatchPos = *MatchResult;
+    PrintMatch(true, SM, *this, i, MatchBuffer, MatchPos, CurrentMatchLen, Req,
+               Diags);
+    if (i == 1)
+      FirstMatchPos = LastPos + MatchPos;
+
+    // move start point after the match
+    LastMatchEnd += MatchPos + CurrentMatchLen;
+  }
+  // Full match len counts from first match pos.
+  MatchLen = LastMatchEnd - FirstMatchPos;
+
+  // Similar to the above, in "label-scan mode" we can't yet handle CHECK-NEXT
+  // or CHECK-NOT
+  if (!IsLabelScanMode) {
+    size_t MatchPos = FirstMatchPos - LastPos;
+    StringRef MatchBuffer = Buffer.substr(LastPos);
+    StringRef SkippedRegion = Buffer.substr(LastPos, MatchPos);
+
+    // If this check is a "CHECK-NEXT", verify that the previous match was on
+    // the previous line (i.e. that there is one newline between them).
+    if (CheckNext(SM, SkippedRegion)) {
+      ProcessMatchResult(FileCheckDiag::MatchFoundButWrongLine, SM, Loc,
+                         Pat.getCheckTy(), MatchBuffer, MatchPos, MatchLen,
+                         Diags, Req.Verbose);
+      return StringRef::npos;
+    }
+
+    // If this check is a "CHECK-SAME", verify that the previous match was on
+    // the same line (i.e. that there is no newline between them).
+    if (CheckSame(SM, SkippedRegion)) {
+      ProcessMatchResult(FileCheckDiag::MatchFoundButWrongLine, SM, Loc,
+                         Pat.getCheckTy(), MatchBuffer, MatchPos, MatchLen,
+                         Diags, Req.Verbose);
+      return StringRef::npos;
+    }
+
+    // If this match had "not strings", verify that they don't exist in the
+    // skipped region.
+    if (CheckNot(SM, SkippedRegion, NotStrings, Req, Diags))
+      return StringRef::npos;
+  }
+
+  return FirstMatchPos;
+}
+
+bool FileCheckString::CheckNext(const SourceMgr &SM, StringRef Buffer) const {
+  if (Pat.getCheckTy() != Check::CheckNext &&
+      Pat.getCheckTy() != Check::CheckEmpty)
+    return false;
+
+  Twine CheckName =
+      Prefix +
+      Twine(Pat.getCheckTy() == Check::CheckEmpty ? "-EMPTY" : "-NEXT");
+
+  // Count the number of newlines between the previous match and this one.
+  const char *FirstNewLine = nullptr;
+  unsigned NumNewLines = CountNumNewlinesBetween(Buffer, FirstNewLine);
+
+  if (NumNewLines == 0) {
+    SM.PrintMessage(Loc, SourceMgr::DK_Error,
+                    CheckName + ": is on the same line as previous match");
+    SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), SourceMgr::DK_Note,
+                    "'next' match was here");
+    SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,
+                    "previous match ended here");
+    return true;
+  }
+
+  if (NumNewLines != 1) {
+    SM.PrintMessage(Loc, SourceMgr::DK_Error,
+                    CheckName +
+                        ": is not on the line after the previous match");
+    SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), SourceMgr::DK_Note,
+                    "'next' match was here");
+    SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,
+                    "previous match ended here");
+    SM.PrintMessage(SMLoc::getFromPointer(FirstNewLine), SourceMgr::DK_Note,
+                    "non-matching line after previous match is here");
+    return true;
+  }
+
+  return false;
+}
+
+bool FileCheckString::CheckSame(const SourceMgr &SM, StringRef Buffer) const {
+  if (Pat.getCheckTy() != Check::CheckSame)
+    return false;
+
+  // Count the number of newlines between the previous match and this one.
+  const char *FirstNewLine = nullptr;
+  unsigned NumNewLines = CountNumNewlinesBetween(Buffer, FirstNewLine);
+
+  if (NumNewLines != 0) {
+    SM.PrintMessage(Loc, SourceMgr::DK_Error,
+                    Prefix +
+                        "-SAME: is not on the same line as the previous match");
+    SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), SourceMgr::DK_Note,
+                    "'next' match was here");
+    SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,
+                    "previous match ended here");
+    return true;
+  }
+
+  return false;
+}
+
+bool FileCheckString::CheckNot(
+    const SourceMgr &SM, StringRef Buffer,
+    const std::vector<const FileCheckPattern *> &NotStrings,
+    const FileCheckRequest &Req, std::vector<FileCheckDiag> *Diags) const {
+  for (const FileCheckPattern *Pat : NotStrings) {
+    assert((Pat->getCheckTy() == Check::CheckNot) && "Expect CHECK-NOT!");
+
+    size_t MatchLen = 0;
+    Expected<size_t> MatchResult = Pat->match(Buffer, MatchLen, SM);
+
+    if (!MatchResult) {
+      PrintNoMatch(false, SM, Prefix, Pat->getLoc(), *Pat, 1, Buffer,
+                   Req.VerboseVerbose, Diags, MatchResult.takeError());
+      continue;
+    }
+    size_t Pos = *MatchResult;
+
+    PrintMatch(false, SM, Prefix, Pat->getLoc(), *Pat, 1, Buffer, Pos, MatchLen,
+               Req, Diags);
+
+    return true;
+  }
+
+  return false;
+}
+
+size_t
+FileCheckString::CheckDag(const SourceMgr &SM, StringRef Buffer,
+                          std::vector<const FileCheckPattern *> &NotStrings,
+                          const FileCheckRequest &Req,
+                          std::vector<FileCheckDiag> *Diags) const {
+  if (DagNotStrings.empty())
+    return 0;
+
+  // The start of the search range.
+  size_t StartPos = 0;
+
+  struct MatchRange {
+    size_t Pos;
+    size_t End;
+  };
+  // 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 FileCheckPattern &Pat = *PatItr;
+    assert((Pat.getCheckTy() == Check::CheckDAG ||
+            Pat.getCheckTy() == Check::CheckNot) &&
+           "Invalid CHECK-DAG or CHECK-NOT!");
+
+    if (Pat.getCheckTy() == Check::CheckNot) {
+      NotStrings.push_back(&Pat);
+      continue;
+    }
+
+    assert((Pat.getCheckTy() == Check::CheckDAG) && "Expect CHECK-DAG!");
+
+    // CHECK-DAG always matches from the start.
+    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 = MatchRanges.begin(), ME = MatchRanges.end(); true; ++MI) {
+      StringRef MatchBuffer = Buffer.substr(MatchPos);
+      Expected<size_t> MatchResult = Pat.match(MatchBuffer, MatchLen, SM);
+      // With a group of CHECK-DAGs, a single mismatching means the match on
+      // that group of CHECK-DAGs fails immediately.
+      if (!MatchResult) {
+        PrintNoMatch(true, SM, Prefix, Pat.getLoc(), Pat, 1, MatchBuffer,
+                     Req.VerboseVerbose, Diags, MatchResult.takeError());
+        return StringRef::npos;
+      }
+      size_t MatchPosBuf = *MatchResult;
+      // Re-calc it as the offset relative to the start of the original string.
+      MatchPos += MatchPosBuf;
+      if (Req.VerboseVerbose)
+        PrintMatch(true, SM, Prefix, Pat.getLoc(), Pat, 1, Buffer, MatchPos,
+                   MatchLen, Req, Diags);
+      MatchRange M{MatchPos, MatchPos + MatchLen};
+      if (Req.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.
+      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.
+        MatchRanges.insert(MI, M);
+        break;
+      }
+      if (Req.VerboseVerbose) {
+        // Due to their verbosity, we don't print verbose diagnostics here if
+        // we're gathering them for a different rendering, but we always print
+        // other diagnostics.
+        if (!Diags) {
+          SMLoc OldStart = SMLoc::getFromPointer(Buffer.data() + MI->Pos);
+          SMLoc OldEnd = SMLoc::getFromPointer(Buffer.data() + MI->End);
+          SMRange OldRange(OldStart, OldEnd);
+          SM.PrintMessage(OldStart, SourceMgr::DK_Note,
+                          "match discarded, overlaps earlier DAG match here",
+                          {OldRange});
+        } else
+          Diags->rbegin()->MatchTy = FileCheckDiag::MatchFoundButDiscarded;
+      }
+      MatchPos = MI->End;
+    }
+    if (!Req.VerboseVerbose)
+      PrintMatch(true, SM, Prefix, Pat.getLoc(), Pat, 1, Buffer, MatchPos,
+                 MatchLen, Req, Diags);
+
+    // 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, Req, Diags))
+          return StringRef::npos;
+        // Clear "not strings".
+        NotStrings.clear();
+      }
+      // 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.
+      MatchRanges.clear();
+    }
+  }
+
+  return StartPos;
+}
+
+// A check prefix must contain only alphanumeric, hyphens and underscores.
+static bool ValidateCheckPrefix(StringRef CheckPrefix) {
+  static const Regex Validator("^[a-zA-Z0-9_-]*$");
+  return Validator.match(CheckPrefix);
+}
+
+bool FileCheck::ValidateCheckPrefixes() {
+  StringSet<> PrefixSet;
+
+  for (StringRef Prefix : Req.CheckPrefixes) {
+    // Reject empty prefixes.
+    if (Prefix == "")
+      return false;
+
+    if (!PrefixSet.insert(Prefix).second)
+      return false;
+
+    if (!ValidateCheckPrefix(Prefix))
+      return false;
+  }
+
+  return true;
+}
+
+Regex FileCheck::buildCheckPrefixRegex() {
+  // I don't think there's a way to specify an initial value for cl::list,
+  // so if nothing was specified, add the default
+  if (Req.CheckPrefixes.empty())
+    Req.CheckPrefixes.push_back("CHECK");
+
+  // We already validated the contents of CheckPrefixes so just concatenate
+  // them as alternatives.
+  SmallString<32> PrefixRegexStr;
+  for (StringRef Prefix : Req.CheckPrefixes) {
+    if (Prefix != Req.CheckPrefixes.front())
+      PrefixRegexStr.push_back('|');
+
+    PrefixRegexStr.append(Prefix);
+  }
+
+  return Regex(PrefixRegexStr);
+}
+
+Error FileCheckPatternContext::defineCmdlineVariables(
+    std::vector<std::string> &CmdlineDefines, SourceMgr &SM) {
+  assert(GlobalVariableTable.empty() && GlobalNumericVariableTable.empty() &&
+         "Overriding defined variable with command-line variable definitions");
+
+  if (CmdlineDefines.empty())
+    return Error::success();
+
+  // Create a string representing the vector of command-line definitions. Each
+  // definition is on its own line and prefixed with a definition number to
+  // clarify which definition a given diagnostic corresponds to.
+  unsigned I = 0;
+  Error Errs = Error::success();
+  std::string CmdlineDefsDiag;
+  SmallVector<std::pair<size_t, size_t>, 4> CmdlineDefsIndices;
+  for (StringRef CmdlineDef : CmdlineDefines) {
+    std::string DefPrefix = ("Global define #" + Twine(++I) + ": ").str();
+    size_t EqIdx = CmdlineDef.find('=');
+    if (EqIdx == StringRef::npos) {
+      CmdlineDefsIndices.push_back(std::make_pair(CmdlineDefsDiag.size(), 0));
+      continue;
+    }
+    // Numeric variable definition.
+    if (CmdlineDef[0] == '#') {
+      // Append a copy of the command-line definition adapted to use the same
+      // format as in the input file to be able to reuse
+      // parseNumericSubstitutionBlock.
+      CmdlineDefsDiag += (DefPrefix + CmdlineDef + " (parsed as: [[").str();
+      std::string SubstitutionStr = CmdlineDef;
+      SubstitutionStr[EqIdx] = ':';
+      CmdlineDefsIndices.push_back(
+          std::make_pair(CmdlineDefsDiag.size(), SubstitutionStr.size()));
+      CmdlineDefsDiag += (SubstitutionStr + Twine("]])\n")).str();
+    } else {
+      CmdlineDefsDiag += DefPrefix;
+      CmdlineDefsIndices.push_back(
+          std::make_pair(CmdlineDefsDiag.size(), CmdlineDef.size()));
+      CmdlineDefsDiag += (CmdlineDef + "\n").str();
+    }
+  }
+
+  // Create a buffer with fake command line content in order to display
+  // parsing diagnostic with location information and point to the
+  // global definition with invalid syntax.
+  std::unique_ptr<MemoryBuffer> CmdLineDefsDiagBuffer =
+      MemoryBuffer::getMemBufferCopy(CmdlineDefsDiag, "Global defines");
+  StringRef CmdlineDefsDiagRef = CmdLineDefsDiagBuffer->getBuffer();
+  SM.AddNewSourceBuffer(std::move(CmdLineDefsDiagBuffer), SMLoc());
+
+  for (std::pair<size_t, size_t> CmdlineDefIndices : CmdlineDefsIndices) {
+    StringRef CmdlineDef = CmdlineDefsDiagRef.substr(CmdlineDefIndices.first,
+                                                     CmdlineDefIndices.second);
+    if (CmdlineDef.empty()) {
+      Errs = joinErrors(
+          std::move(Errs),
+          FileCheckErrorDiagnostic::get(
+              SM, CmdlineDef, "missing equal sign in global definition"));
+      continue;
+    }
+
+    // Numeric variable definition.
+    if (CmdlineDef[0] == '#') {
+      // Now parse the definition both to check that the syntax is correct and
+      // to create the necessary class instance.
+      StringRef CmdlineDefExpr = CmdlineDef.substr(1);
+      Optional<FileCheckNumericVariable *> DefinedNumericVariable;
+      Expected<std::unique_ptr<FileCheckExpressionAST>> ExpressionASTResult =
+          FileCheckPattern::parseNumericSubstitutionBlock(
+              CmdlineDefExpr, DefinedNumericVariable, false, None, this, SM);
+      if (!ExpressionASTResult) {
+        Errs = joinErrors(std::move(Errs), ExpressionASTResult.takeError());
+        continue;
+      }
+      std::unique_ptr<FileCheckExpressionAST> ExpressionAST =
+          std::move(*ExpressionASTResult);
+      // Now evaluate the expression whose value this variable should be set
+      // to, since the expression of a command-line variable definition should
+      // only use variables defined earlier on the command-line. If not, this
+      // is an error and we report it.
+      Expected<uint64_t> Value = ExpressionAST->eval();
+      if (!Value) {
+        Errs = joinErrors(std::move(Errs), Value.takeError());
+        continue;
+      }
+
+      assert(DefinedNumericVariable && "No variable defined");
+      (*DefinedNumericVariable)->setValue(*Value);
+
+      // Record this variable definition.
+      GlobalNumericVariableTable[(*DefinedNumericVariable)->getName()] =
+          *DefinedNumericVariable;
+    } else {
+      // String variable definition.
+      std::pair<StringRef, StringRef> CmdlineNameVal = CmdlineDef.split('=');
+      StringRef CmdlineName = CmdlineNameVal.first;
+      StringRef OrigCmdlineName = CmdlineName;
+      Expected<FileCheckPattern::VariableProperties> ParseVarResult =
+          FileCheckPattern::parseVariable(CmdlineName, SM);
+      if (!ParseVarResult) {
+        Errs = joinErrors(std::move(Errs), ParseVarResult.takeError());
+        continue;
+      }
+      // Check that CmdlineName does not denote a pseudo variable is only
+      // composed of the parsed numeric variable. This catches cases like
+      // "FOO+2" in a "FOO+2=10" definition.
+      if (ParseVarResult->IsPseudo || !CmdlineName.empty()) {
+        Errs = joinErrors(std::move(Errs),
+                          FileCheckErrorDiagnostic::get(
+                              SM, OrigCmdlineName,
+                              "invalid name in string variable definition '" +
+                                  OrigCmdlineName + "'"));
+        continue;
+      }
+      StringRef Name = ParseVarResult->Name;
+
+      // Detect collisions between string and numeric variables when the former
+      // is created later than the latter.
+      if (GlobalNumericVariableTable.find(Name) !=
+          GlobalNumericVariableTable.end()) {
+        Errs = joinErrors(std::move(Errs), FileCheckErrorDiagnostic::get(
+                                               SM, Name,
+                                               "numeric variable with name '" +
+                                                   Name + "' already exists"));
+        continue;
+      }
+      GlobalVariableTable.insert(CmdlineNameVal);
+      // Mark the string variable as defined to detect collisions between
+      // string and numeric variables in defineCmdlineVariables when the latter
+      // is created later than the former. We cannot reuse GlobalVariableTable
+      // for this by populating it with an empty string since we would then
+      // lose the ability to detect the use of an undefined variable in
+      // match().
+      DefinedVariableTable[Name] = true;
+    }
+  }
+
+  return Errs;
+}
+
+void FileCheckPatternContext::clearLocalVars() {
+  SmallVector<StringRef, 16> LocalPatternVars, LocalNumericVars;
+  for (const StringMapEntry<StringRef> &Var : GlobalVariableTable)
+    if (Var.first()[0] != '$')
+      LocalPatternVars.push_back(Var.first());
+
+  // Numeric substitution reads the value of a variable directly, not via
+  // GlobalNumericVariableTable. Therefore, we clear local variables by
+  // clearing their value which will lead to a numeric substitution failure. We
+  // also mark the variable for removal from GlobalNumericVariableTable since
+  // this is what defineCmdlineVariables checks to decide that no global
+  // variable has been defined.
+  for (const auto &Var : GlobalNumericVariableTable)
+    if (Var.first()[0] != '$') {
+      Var.getValue()->clearValue();
+      LocalNumericVars.push_back(Var.first());
+    }
+
+  for (const auto &Var : LocalPatternVars)
+    GlobalVariableTable.erase(Var);
+  for (const auto &Var : LocalNumericVars)
+    GlobalNumericVariableTable.erase(Var);
+}
+
+bool FileCheck::checkInput(SourceMgr &SM, StringRef Buffer,
+                           std::vector<FileCheckDiag> *Diags) {
+  bool ChecksFailed = false;
+
+  unsigned i = 0, j = 0, e = CheckStrings->size();
+  while (true) {
+    StringRef CheckRegion;
+    if (j == e) {
+      CheckRegion = Buffer;
+    } else {
+      const FileCheckString &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, Req, Diags);
+      if (MatchLabelPos == StringRef::npos)
+        // Immediately bail if CHECK-LABEL fails, nothing else we can do.
+        return false;
+
+      CheckRegion = Buffer.substr(0, MatchLabelPos + MatchLabelLen);
+      Buffer = Buffer.substr(MatchLabelPos + MatchLabelLen);
+      ++j;
+    }
+
+    // Do not clear the first region as it's the one before the first
+    // CHECK-LABEL and it would clear variables defined on the command-line
+    // before they get used.
+    if (i != 0 && Req.EnableVarScope)
+      PatternContext->clearLocalVars();
+
+    for (; i != j; ++i) {
+      const FileCheckString &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, Req, Diags);
+
+      if (MatchPos == StringRef::npos) {
+        ChecksFailed = true;
+        i = j;
+        break;
+      }
+
+      CheckRegion = CheckRegion.substr(MatchPos + MatchLen);
+    }
+
+    if (j == e)
+      break;
+  }
+
+  // Success if no checks failed.
+  return !ChecksFailed;
+}
diff --git a/llvm/lib/Support/FileCheckImpl.h b/llvm/lib/Support/FileCheckImpl.h
index 6581612a8e4..001b3589d5f 100644
--- a/llvm/lib/Support/FileCheckImpl.h
+++ b/llvm/lib/Support/FileCheckImpl.h
@@ -1,624 +1,621 @@
-//===-- FileCheckImpl.h - Private FileCheck Interface ------------*- C++ -*-==//

-//

-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

-// See https://llvm.org/LICENSE.txt for license information.

-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

-//

-//===----------------------------------------------------------------------===//

-//

-// This file defines the private interfaces of FileCheck. Its purpose is to

-// allow unit testing of FileCheck and to separate the interface from the

-// implementation. It is only meant to be used by FileCheck.

-//

-//===----------------------------------------------------------------------===//

-

-#ifndef LLVM_LIB_SUPPORT_FILECHECKIMPL_H

-#define LLVM_LIB_SUPPORT_FILECHECKIMPL_H

-

-#include "llvm/ADT/Optional.h"

-#include "llvm/ADT/StringMap.h"

-#include "llvm/ADT/StringRef.h"

-#include "llvm/Support/Error.h"

-#include "llvm/Support/SourceMgr.h"

-#include <map>

-#include <string>

-#include <vector>

-

-namespace llvm {

-

-//===----------------------------------------------------------------------===//

-// Numeric substitution handling code.

-//===----------------------------------------------------------------------===//

-

-/// Base class representing the AST of a given expression.

-class FileCheckExpressionAST {

-public:

-  virtual ~FileCheckExpressionAST() = default;

-

-  /// Evaluates and \returns the value of the expression represented by this

-  /// AST or an error if evaluation fails.

-  virtual Expected<uint64_t> eval() const = 0;

-};

-

-/// Class representing an unsigned literal in the AST of an expression.

-class FileCheckExpressionLiteral : public FileCheckExpressionAST {

-private:

-  /// Actual value of the literal.

-  uint64_t Value;

-

-public:

-  /// Constructs a literal with the specified value.

-  FileCheckExpressionLiteral(uint64_t Val) : Value(Val) {}

-

-  /// \returns the literal's value.

-  Expected<uint64_t> eval() const { return Value; }

-};

-

-/// Class to represent an undefined variable error, which quotes that

-/// variable's name when printed.

-class FileCheckUndefVarError : public ErrorInfo<FileCheckUndefVarError> {

-private:

-  StringRef VarName;

-

-public:

-  static char ID;

-

-  FileCheckUndefVarError(StringRef VarName) : VarName(VarName) {}

-

-  StringRef getVarName() const { return VarName; }

-

-  std::error_code convertToErrorCode() const override {

-    return inconvertibleErrorCode();

-  }

-

-  /// Print name of variable associated with this error.

-  void log(raw_ostream &OS) const override {

-    OS << "\"";

-    OS.write_escaped(VarName) << "\"";

-  }

-};

-

-/// Class representing a numeric variable and its associated current value.

-class FileCheckNumericVariable {

-private:

-  /// Name of the numeric variable.

-  StringRef Name;

-

-  /// Value of numeric variable, if defined, or None otherwise.

-  Optional<uint64_t> Value;

-

-  /// Line number where this variable is defined, or None if defined before

-  /// input is parsed. Used to determine whether a variable is defined on the

-  /// same line as a given use.

-  Optional<size_t> DefLineNumber;

-

-public:

-  /// Constructor for a variable \p Name defined at line \p DefLineNumber or

-  /// defined before input is parsed if \p DefLineNumber is None.

-  explicit FileCheckNumericVariable(StringRef Name,

-                                    Optional<size_t> DefLineNumber = None)

-      : Name(Name), DefLineNumber(DefLineNumber) {}

-

-  /// \returns name of this numeric variable.

-  StringRef getName() const { return Name; }

-

-  /// \returns this variable's value.

-  Optional<uint64_t> getValue() const { return Value; }

-

-  /// Sets value of this numeric variable to \p NewValue.

-  void setValue(uint64_t NewValue) { Value = NewValue; }

-

-  /// Clears value of this numeric variable, regardless of whether it is

-  /// currently defined or not.

-  void clearValue() { Value = None; }

-

-  /// \returns the line number where this variable is defined, if any, or None

-  /// if defined before input is parsed.

-  Optional<size_t> getDefLineNumber() { return DefLineNumber; }

-};

-

-/// Class representing the use of a numeric variable in the AST of an

-/// expression.

-class FileCheckNumericVariableUse : public FileCheckExpressionAST {

-private:

-  /// Name of the numeric variable.

-  StringRef Name;

-

-  /// Pointer to the class instance for the variable this use is about.

-  FileCheckNumericVariable *NumericVariable;

-

-public:

-  FileCheckNumericVariableUse(StringRef Name,

-                              FileCheckNumericVariable *NumericVariable)

-      : Name(Name), NumericVariable(NumericVariable) {}

-

-  /// \returns the value of the variable referenced by this instance.

-  Expected<uint64_t> eval() const;

-};

-

-/// Type of functions evaluating a given binary operation.

-using binop_eval_t = uint64_t (*)(uint64_t, uint64_t);

-

-/// Class representing a single binary operation in the AST of an expression.

-class FileCheckASTBinop : public FileCheckExpressionAST {

-private:

-  /// Left operand.

-  std::unique_ptr<FileCheckExpressionAST> LeftOperand;

-

-  /// Right operand.

-  std::unique_ptr<FileCheckExpressionAST> RightOperand;

-

-  /// Pointer to function that can evaluate this binary operation.

-  binop_eval_t EvalBinop;

-

-public:

-  FileCheckASTBinop(binop_eval_t EvalBinop,

-                    std::unique_ptr<FileCheckExpressionAST> LeftOp,

-                    std::unique_ptr<FileCheckExpressionAST> RightOp)

-      : EvalBinop(EvalBinop) {

-    LeftOperand = std::move(LeftOp);

-    RightOperand = std::move(RightOp);

-  }

-

-  /// Evaluates the value of the binary operation represented by this AST,

-  /// using EvalBinop on the result of recursively evaluating the operands.

-  /// \returns the expression value or an error if an undefined numeric

-  /// variable is used in one of the operands.

-  Expected<uint64_t> eval() const;

-};

-

-class FileCheckPatternContext;

-

-/// Class representing a substitution to perform in the RegExStr string.

-class FileCheckSubstitution {

-protected:

-  /// Pointer to a class instance holding, among other things, the table with

-  /// the values of live string variables at the start of any given CHECK line.

-  /// Used for substituting string variables with the text they were defined

-  /// as. Expressions are linked to the numeric variables they use at

-  /// parse time and directly access the value of the numeric variable to

-  /// evaluate their value.

-  FileCheckPatternContext *Context;

-

-  /// The string that needs to be substituted for something else. For a

-  /// string variable this is its name, otherwise this is the whole expression.

-  StringRef FromStr;

-

-  // Index in RegExStr of where to do the substitution.

-  size_t InsertIdx;

-

-public:

-  FileCheckSubstitution(FileCheckPatternContext *Context, StringRef VarName,

-                        size_t InsertIdx)

-      : Context(Context), FromStr(VarName), InsertIdx(InsertIdx) {}

-

-  virtual ~FileCheckSubstitution() = default;

-

-  /// \returns the string to be substituted for something else.

-  StringRef getFromString() const { return FromStr; }

-

-  /// \returns the index where the substitution is to be performed in RegExStr.

-  size_t getIndex() const { return InsertIdx; }

-

-  /// \returns a string containing the result of the substitution represented

-  /// by this class instance or an error if substitution failed.

-  virtual Expected<std::string> getResult() const = 0;

-};

-

-class FileCheckStringSubstitution : public FileCheckSubstitution {

-public:

-  FileCheckStringSubstitution(FileCheckPatternContext *Context,

-                              StringRef VarName, size_t InsertIdx)

-      : FileCheckSubstitution(Context, VarName, InsertIdx) {}

-

-  /// \returns the text that the string variable in this substitution matched

-  /// when defined, or an error if the variable is undefined.

-  Expected<std::string> getResult() const override;

-};

-

-class FileCheckNumericSubstitution : public FileCheckSubstitution {

-private:

-  /// Pointer to the class representing the expression whose value is to be

-  /// substituted.

-  std::unique_ptr<FileCheckExpressionAST> ExpressionAST;

-

-public:

-  FileCheckNumericSubstitution(FileCheckPatternContext *Context, StringRef Expr,

-                               std::unique_ptr<FileCheckExpressionAST> ExprAST,

-                               size_t InsertIdx)

-      : FileCheckSubstitution(Context, Expr, InsertIdx) {

-    ExpressionAST = std::move(ExprAST);

-  }

-

-  /// \returns a string containing the result of evaluating the expression in

-  /// this substitution, or an error if evaluation failed.

-  Expected<std::string> getResult() const override;

-};

-

-//===----------------------------------------------------------------------===//

-// Pattern handling code.

-//===----------------------------------------------------------------------===//

-

-struct FileCheckDiag;

-

-/// Class holding the FileCheckPattern global state, shared by all patterns:

-/// tables holding values of variables and whether they are defined or not at

-/// any given time in the matching process.

-class FileCheckPatternContext {

-  friend class FileCheckPattern;

-

-private:

-  /// When matching a given pattern, this holds the value of all the string

-  /// variables defined in previous patterns. In a pattern, only the last

-  /// definition for a given variable is recorded in this table.

-  /// Back-references are used for uses after any the other definition.

-  StringMap<StringRef> GlobalVariableTable;

-

-  /// Map of all string variables defined so far. Used at parse time to detect

-  /// a name conflict between a numeric variable and a string variable when

-  /// the former is defined on a later line than the latter.

-  StringMap<bool> DefinedVariableTable;

-

-  /// When matching a given pattern, this holds the pointers to the classes

-  /// representing the numeric variables defined in previous patterns. When

-  /// matching a pattern all definitions for that pattern are recorded in the

-  /// NumericVariableDefs table in the FileCheckPattern instance of that

-  /// pattern.

-  StringMap<FileCheckNumericVariable *> GlobalNumericVariableTable;

-

-  /// Pointer to the class instance representing the @LINE pseudo variable for

-  /// easily updating its value.

-  FileCheckNumericVariable *LineVariable = nullptr;

-

-  /// Vector holding pointers to all parsed numeric variables. Used to

-  /// automatically free them once they are guaranteed to no longer be used.

-  std::vector<std::unique_ptr<FileCheckNumericVariable>> NumericVariables;

-

-  /// Vector holding pointers to all substitutions. Used to automatically free

-  /// them once they are guaranteed to no longer be used.

-  std::vector<std::unique_ptr<FileCheckSubstitution>> Substitutions;

-

-public:

-  /// \returns the value of string variable \p VarName or an error if no such

-  /// variable has been defined.

-  Expected<StringRef> getPatternVarValue(StringRef VarName);

-

-  /// Defines string and numeric variables from definitions given on the

-  /// command line, passed as a vector of [#]VAR=VAL strings in

-  /// \p CmdlineDefines. \returns an error list containing diagnostics against

-  /// \p SM for all definition parsing failures, if any, or Success otherwise.

-  Error defineCmdlineVariables(std::vector<std::string> &CmdlineDefines,

-                               SourceMgr &SM);

-

-  /// Create @LINE pseudo variable. Value is set when pattern are being

-  /// matched.

-  void createLineVariable();

-

-  /// Undefines local variables (variables whose name does not start with a '$'

-  /// sign), i.e. removes them from GlobalVariableTable and from

-  /// GlobalNumericVariableTable and also clears the value of numeric

-  /// variables.

-  void clearLocalVars();

-

-private:

-  /// Makes a new numeric variable and registers it for destruction when the

-  /// context is destroyed.

-  template <class... Types>

-  FileCheckNumericVariable *makeNumericVariable(Types... args);

-

-  /// Makes a new string substitution and registers it for destruction when the

-  /// context is destroyed.

-  FileCheckSubstitution *makeStringSubstitution(StringRef VarName,

-                                                size_t InsertIdx);

-

-  /// Makes a new numeric substitution and registers it for destruction when

-  /// the context is destroyed.

-  FileCheckSubstitution *

-  makeNumericSubstitution(StringRef ExpressionStr,

-                          std::unique_ptr<FileCheckExpressionAST> ExpressionAST,

-                          size_t InsertIdx);

-};

-

-/// Class to represent an error holding a diagnostic with location information

-/// used when printing it.

-class FileCheckErrorDiagnostic : public ErrorInfo<FileCheckErrorDiagnostic> {

-private:

-  SMDiagnostic Diagnostic;

-

-public:

-  static char ID;

-

-  FileCheckErrorDiagnostic(SMDiagnostic &&Diag) : Diagnostic(Diag) {}

-

-  std::error_code convertToErrorCode() const override {

-    return inconvertibleErrorCode();

-  }

-

-  /// Print diagnostic associated with this error when printing the error.

-  void log(raw_ostream &OS) const override { Diagnostic.print(nullptr, OS); }

-

-  static Error get(const SourceMgr &SM, SMLoc Loc, const Twine &ErrMsg) {

-    return make_error<FileCheckErrorDiagnostic>(

-        SM.GetMessage(Loc, SourceMgr::DK_Error, ErrMsg));

-  }

-

-  static Error get(const SourceMgr &SM, StringRef Buffer, const Twine &ErrMsg) {

-    return get(SM, SMLoc::getFromPointer(Buffer.data()), ErrMsg);

-  }

-};

-

-class FileCheckNotFoundError : public ErrorInfo<FileCheckNotFoundError> {

-public:

-  static char ID;

-

-  std::error_code convertToErrorCode() const override {

-    return inconvertibleErrorCode();

-  }

-

-  /// Print diagnostic associated with this error when printing the error.

-  void log(raw_ostream &OS) const override {

-    OS << "String not found in input";

-  }

-};

-

-class FileCheckPattern {

-  SMLoc PatternLoc;

-

-  /// A fixed string to match as the pattern or empty if this pattern requires

-  /// a regex match.

-  StringRef FixedStr;

-

-  /// A regex string to match as the pattern or empty if this pattern requires

-  /// a fixed string to match.

-  std::string RegExStr;

-

-  /// Entries in this vector represent a substitution of a string variable or

-  /// an expression in the RegExStr regex at match time. For example, in the

-  /// case of a CHECK directive with the pattern "foo[[bar]]baz[[#N+1]]",

-  /// RegExStr will contain "foobaz" and we'll get two entries in this vector

-  /// that tells us to insert the value of string variable "bar" at offset 3

-  /// and the value of expression "N+1" at offset 6.

-  std::vector<FileCheckSubstitution *> Substitutions;

-

-  /// Maps names of string variables defined in a pattern to the number of

-  /// their parenthesis group in RegExStr capturing their last definition.

-  ///

-  /// E.g. for the pattern "foo[[bar:.*]]baz([[bar]][[QUUX]][[bar:.*]])",

-  /// RegExStr will be "foo(.*)baz(\1<quux value>(.*))" where <quux value> is

-  /// the value captured for QUUX on the earlier line where it was defined, and

-  /// VariableDefs will map "bar" to the third parenthesis group which captures

-  /// the second definition of "bar".

-  ///

-  /// Note: uses std::map rather than StringMap to be able to get the key when

-  /// iterating over values.

-  std::map<StringRef, unsigned> VariableDefs;

-

-  /// Structure representing the definition of a numeric variable in a pattern.

-  /// It holds the pointer to the class representing the numeric variable whose

-  /// value is being defined and the number of the parenthesis group in

-  /// RegExStr to capture that value.

-  struct FileCheckNumericVariableMatch {

-    /// Pointer to class representing the numeric variable whose value is being

-    /// defined.

-    FileCheckNumericVariable *DefinedNumericVariable;

-

-    /// Number of the parenthesis group in RegExStr that captures the value of

-    /// this numeric variable definition.

-    unsigned CaptureParenGroup;

-  };

-

-  /// Holds the number of the parenthesis group in RegExStr and pointer to the

-  /// corresponding FileCheckNumericVariable class instance of all numeric

-  /// variable definitions. Used to set the matched value of all those

-  /// variables.

-  StringMap<FileCheckNumericVariableMatch> NumericVariableDefs;

-

-  /// Pointer to a class instance holding the global state shared by all

-  /// patterns:

-  /// - separate tables with the values of live string and numeric variables

-  ///   respectively at the start of any given CHECK line;

-  /// - table holding whether a string variable has been defined at any given

-  ///   point during the parsing phase.

-  FileCheckPatternContext *Context;

-

-  Check::FileCheckType CheckTy;

-

-  /// Line number for this CHECK pattern or None if it is an implicit pattern.

-  /// Used to determine whether a variable definition is made on an earlier

-  /// line to the one with this CHECK.

-  Optional<size_t> LineNumber;

-

-  /// Ignore case while matching if set to true.

-  bool IgnoreCase = false;

-

-public:

-  FileCheckPattern(Check::FileCheckType Ty, FileCheckPatternContext *Context,

-                   Optional<size_t> Line = None)

-      : Context(Context), CheckTy(Ty), LineNumber(Line) {}

-

-  /// \returns the location in source code.

-  SMLoc getLoc() const { return PatternLoc; }

-

-  /// \returns the pointer to the global state for all patterns in this

-  /// FileCheck instance.

-  FileCheckPatternContext *getContext() const { return Context; }

-

-  /// \returns whether \p C is a valid first character for a variable name.

-  static bool isValidVarNameStart(char C);

-

-  /// Parsing information about a variable.

-  struct VariableProperties {

-    StringRef Name;

-    bool IsPseudo;

-  };

-

-  /// Parses the string at the start of \p Str for a variable name. \returns

-  /// a VariableProperties structure holding the variable name and whether it

-  /// is the name of a pseudo variable, or an error holding a diagnostic

-  /// against \p SM if parsing fail. If parsing was successful, also strips

-  /// \p Str from the variable name.

-  static Expected<VariableProperties> parseVariable(StringRef &Str,

-                                                    const SourceMgr &SM);

-  /// Parses \p Expr for a numeric substitution block at line \p LineNumber,

-  /// or before input is parsed if \p LineNumber is None. Parameter

-  /// \p IsLegacyLineExpr indicates whether \p Expr should be a legacy @LINE

-  /// expression and \p Context points to the class instance holding the live

-  /// string and numeric variables. \returns a pointer to the class instance

-  /// representing the AST of the expression whose value must be substitued, or

-  /// an error holding a diagnostic against \p SM if parsing fails. If

-  /// substitution was successful, sets \p DefinedNumericVariable to point to

-  /// the class representing the numeric variable defined in this numeric

-  /// substitution block, or None if this block does not define any variable.

-  static Expected<std::unique_ptr<FileCheckExpressionAST>>

-  parseNumericSubstitutionBlock(

-      StringRef Expr,

-      Optional<FileCheckNumericVariable *> &DefinedNumericVariable,

-      bool IsLegacyLineExpr, Optional<size_t> LineNumber,

-      FileCheckPatternContext *Context, const SourceMgr &SM);

-  /// Parses the pattern in \p PatternStr and initializes this FileCheckPattern

-  /// instance accordingly.

-  ///

-  /// \p Prefix provides which prefix is being matched, \p Req describes the

-  /// global options that influence the parsing such as whitespace

-  /// canonicalization, \p SM provides the SourceMgr used for error reports.

-  /// \returns true in case of an error, false otherwise.

-  bool parsePattern(StringRef PatternStr, StringRef Prefix, SourceMgr &SM,

-                    const FileCheckRequest &Req);

-  /// Matches the pattern string against the input buffer \p Buffer

-  ///

-  /// \returns the position that is matched or an error indicating why matching

-  /// failed. If there is a match, updates \p MatchLen with the size of the

-  /// matched string.

-  ///

-  /// The GlobalVariableTable StringMap in the FileCheckPatternContext class

-  /// instance provides the current values of FileCheck string variables and

-  /// is updated if this match defines new values. Likewise, the

-  /// GlobalNumericVariableTable StringMap in the same class provides the

-  /// current values of FileCheck numeric variables and is updated if this

-  /// match defines new numeric values.

-  Expected<size_t> match(StringRef Buffer, size_t &MatchLen,

-                         const SourceMgr &SM) const;

-  /// Prints the value of successful substitutions or the name of the undefined

-  /// string or numeric variables preventing a successful substitution.

-  void printSubstitutions(const SourceMgr &SM, StringRef Buffer,

-                          SMRange MatchRange = None) const;

-  void printFuzzyMatch(const SourceMgr &SM, StringRef Buffer,

-                       std::vector<FileCheckDiag> *Diags) const;

-

-  bool hasVariable() const {

-    return !(Substitutions.empty() && VariableDefs.empty());

-  }

-

-  Check::FileCheckType getCheckTy() const { return CheckTy; }

-

-  int getCount() const { return CheckTy.getCount(); }

-

-private:

-  bool AddRegExToRegEx(StringRef RS, unsigned &CurParen, SourceMgr &SM);

-  void AddBackrefToRegEx(unsigned BackrefNum);

-  /// Computes an arbitrary estimate for the quality of matching this pattern

-  /// at the start of \p Buffer; a distance of zero should correspond to a

-  /// perfect match.

-  unsigned computeMatchDistance(StringRef Buffer) const;

-  /// Finds the closing sequence of a regex variable usage or definition.

-  ///

-  /// \p Str has to point in the beginning of the definition (right after the

-  /// opening sequence). \p SM holds the SourceMgr used for error repporting.

-  ///  \returns the offset of the closing sequence within Str, or npos if it

-  /// was not found.

-  size_t FindRegexVarEnd(StringRef Str, SourceMgr &SM);

-

-  /// Parses \p Expr for the name of a numeric variable to be defined at line

-  /// \p LineNumber, or before input is parsed if \p LineNumber is None.

-  /// \returns a pointer to the class instance representing that variable,

-  /// creating it if needed, or an error holding a diagnostic against \p SM

-  /// should defining such a variable be invalid.

-  static Expected<FileCheckNumericVariable *> parseNumericVariableDefinition(

-      StringRef &Expr, FileCheckPatternContext *Context,

-      Optional<size_t> LineNumber, const SourceMgr &SM);

-  /// Parses \p Name as a (pseudo if \p IsPseudo is true) numeric variable use

-  /// at line \p LineNumber, or before input is parsed if \p LineNumber is

-  /// None. Parameter \p Context points to the class instance holding the live

-  /// string and numeric variables. \returns the pointer to the class instance

-  /// representing that variable if successful, or an error holding a

-  /// diagnostic against \p SM otherwise.

-  static Expected<std::unique_ptr<FileCheckNumericVariableUse>>

-  parseNumericVariableUse(StringRef Name, bool IsPseudo,

-                          Optional<size_t> LineNumber,

-                          FileCheckPatternContext *Context,

-                          const SourceMgr &SM);

-  enum class AllowedOperand { LineVar, Literal, Any };

-  /// Parses \p Expr for use of a numeric operand at line \p LineNumber, or

-  /// before input is parsed if \p LineNumber is None. Accepts both literal

-  /// values and numeric variables, depending on the value of \p AO. Parameter

-  /// \p Context points to the class instance holding the live string and

-  /// numeric variables. \returns the class representing that operand in the

-  /// AST of the expression or an error holding a diagnostic against \p SM

-  /// otherwise.

-  static Expected<std::unique_ptr<FileCheckExpressionAST>>

-  parseNumericOperand(StringRef &Expr, AllowedOperand AO,

-                      Optional<size_t> LineNumber,

-                      FileCheckPatternContext *Context, const SourceMgr &SM);

-  /// Parses \p Expr for a binary operation at line \p LineNumber, or before

-  /// input is parsed if \p LineNumber is None. The left operand of this binary

-  /// operation is given in \p LeftOp and \p IsLegacyLineExpr indicates whether

-  /// we are parsing a legacy @LINE expression. Parameter \p Context points to

-  /// the class instance holding the live string and numeric variables.

-  /// \returns the class representing the binary operation in the AST of the

-  /// expression, or an error holding a diagnostic against \p SM otherwise.

-  static Expected<std::unique_ptr<FileCheckExpressionAST>>

-  parseBinop(StringRef &Expr, std::unique_ptr<FileCheckExpressionAST> LeftOp,

-             bool IsLegacyLineExpr, Optional<size_t> LineNumber,

-             FileCheckPatternContext *Context, const SourceMgr &SM);

-};

-

-//===----------------------------------------------------------------------===//

-// Check Strings.

-//===----------------------------------------------------------------------===//

-

-/// A check that we found in the input file.

-struct FileCheckString {

-  /// The pattern to match.

-  FileCheckPattern Pat;

-

-  /// Which prefix name this check matched.

-  StringRef Prefix;

-

-  /// The location in the match file that the check string was specified.

-  SMLoc Loc;

-

-  /// All of the strings that are disallowed from occurring between this match

-  /// string and the previous one (or start of file).

-  std::vector<FileCheckPattern> DagNotStrings;

-

-  FileCheckString(const FileCheckPattern &P, StringRef S, SMLoc L)

-      : Pat(P), Prefix(S), Loc(L) {}

-

-  /// Matches check string and its "not strings" and/or "dag strings".

-  size_t Check(const SourceMgr &SM, StringRef Buffer, bool IsLabelScanMode,

-               size_t &MatchLen, FileCheckRequest &Req,

-               std::vector<FileCheckDiag> *Diags) const;

-

-  /// Verifies that there is a single line in the given \p Buffer. Errors are

-  /// reported against \p SM.

-  bool CheckNext(const SourceMgr &SM, StringRef Buffer) const;

-  /// Verifies that there is no newline in the given \p Buffer. Errors are

-  /// reported against \p SM.

-  bool CheckSame(const SourceMgr &SM, StringRef Buffer) const;

-  /// Verifies that none of the strings in \p NotStrings are found in the given

-  /// \p Buffer. Errors are reported against \p SM and diagnostics recorded in

-  /// \p Diags according to the verbosity level set in \p Req.

-  bool CheckNot(const SourceMgr &SM, StringRef Buffer,

-                const std::vector<const FileCheckPattern *> &NotStrings,

-                const FileCheckRequest &Req,

-                std::vector<FileCheckDiag> *Diags) const;

-  /// Matches "dag strings" and their mixed "not strings".

-  size_t CheckDag(const SourceMgr &SM, StringRef Buffer,

-                  std::vector<const FileCheckPattern *> &NotStrings,

-                  const FileCheckRequest &Req,

-                  std::vector<FileCheckDiag> *Diags) const;

-};

-

-} // namespace llvm

-

-#endif

+//===-- FileCheckImpl.h - Private FileCheck Interface ------------*- C++ -*-==//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the private interfaces of FileCheck. Its purpose is to
+// allow unit testing of FileCheck and to separate the interface from the
+// implementation. It is only meant to be used by FileCheck.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_SUPPORT_FILECHECKIMPL_H
+#define LLVM_LIB_SUPPORT_FILECHECKIMPL_H
+
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/SourceMgr.h"
+#include <map>
+#include <string>
+#include <vector>
+
+namespace llvm {
+
+//===----------------------------------------------------------------------===//
+// Numeric substitution handling code.
+//===----------------------------------------------------------------------===//
+
+/// Base class representing the AST of a given expression.
+class FileCheckExpressionAST {
+public:
+  virtual ~FileCheckExpressionAST() = default;
+
+  /// Evaluates and \returns the value of the expression represented by this
+  /// AST or an error if evaluation fails.
+  virtual Expected<uint64_t> eval() const = 0;
+};
+
+/// Class representing an unsigned literal in the AST of an expression.
+class FileCheckExpressionLiteral : public FileCheckExpressionAST {
+private:
+  /// Actual value of the literal.
+  uint64_t Value;
+
+public:
+  /// Constructs a literal with the specified value.
+  FileCheckExpressionLiteral(uint64_t Val) : Value(Val) {}
+
+  /// \returns the literal's value.
+  Expected<uint64_t> eval() const { return Value; }
+};
+
+/// Class to represent an undefined variable error, which quotes that
+/// variable's name when printed.
+class FileCheckUndefVarError : public ErrorInfo<FileCheckUndefVarError> {
+private:
+  StringRef VarName;
+
+public:
+  static char ID;
+
+  FileCheckUndefVarError(StringRef VarName) : VarName(VarName) {}
+
+  StringRef getVarName() const { return VarName; }
+
+  std::error_code convertToErrorCode() const override {
+    return inconvertibleErrorCode();
+  }
+
+  /// Print name of variable associated with this error.
+  void log(raw_ostream &OS) const override {
+    OS << "\"";
+    OS.write_escaped(VarName) << "\"";
+  }
+};
+
+/// Class representing a numeric variable and its associated current value.
+class FileCheckNumericVariable {
+private:
+  /// Name of the numeric variable.
+  StringRef Name;
+
+  /// Value of numeric variable, if defined, or None otherwise.
+  Optional<uint64_t> Value;
+
+  /// Line number where this variable is defined, or None if defined before
+  /// input is parsed. Used to determine whether a variable is defined on the
+  /// same line as a given use.
+  Optional<size_t> DefLineNumber;
+
+public:
+  /// Constructor for a variable \p Name defined at line \p DefLineNumber or
+  /// defined before input is parsed if \p DefLineNumber is None.
+  explicit FileCheckNumericVariable(StringRef Name,
+                                    Optional<size_t> DefLineNumber = None)
+      : Name(Name), DefLineNumber(DefLineNumber) {}
+
+  /// \returns name of this numeric variable.
+  StringRef getName() const { return Name; }
+
+  /// \returns this variable's value.
+  Optional<uint64_t> getValue() const { return Value; }
+
+  /// Sets value of this numeric variable to \p NewValue.
+  void setValue(uint64_t NewValue) { Value = NewValue; }
+
+  /// Clears value of this numeric variable, regardless of whether it is
+  /// currently defined or not.
+  void clearValue() { Value = None; }
+
+  /// \returns the line number where this variable is defined, if any, or None
+  /// if defined before input is parsed.
+  Optional<size_t> getDefLineNumber() { return DefLineNumber; }
+};
+
+/// Class representing the use of a numeric variable in the AST of an
+/// expression.
+class FileCheckNumericVariableUse : public FileCheckExpressionAST {
+private:
+  /// Name of the numeric variable.
+  StringRef Name;
+
+  /// Pointer to the class instance for the variable this use is about.
+  FileCheckNumericVariable *NumericVariable;
+
+public:
+  FileCheckNumericVariableUse(StringRef Name,
+                              FileCheckNumericVariable *NumericVariable)
+      : Name(Name), NumericVariable(NumericVariable) {}
+
+  /// \returns the value of the variable referenced by this instance.
+  Expected<uint64_t> eval() const;
+};
+
+/// Type of functions evaluating a given binary operation.
+using binop_eval_t = uint64_t (*)(uint64_t, uint64_t);
+
+/// Class representing a single binary operation in the AST of an expression.
+class FileCheckASTBinop : public FileCheckExpressionAST {
+private:
+  /// Left operand.
+  std::unique_ptr<FileCheckExpressionAST> LeftOperand;
+
+  /// Right operand.
+  std::unique_ptr<FileCheckExpressionAST> RightOperand;
+
+  /// Pointer to function that can evaluate this binary operation.
+  binop_eval_t EvalBinop;
+
+public:
+  FileCheckASTBinop(binop_eval_t EvalBinop,
+                    std::unique_ptr<FileCheckExpressionAST> LeftOp,
+                    std::unique_ptr<FileCheckExpressionAST> RightOp)
+      : EvalBinop(EvalBinop) {
+    LeftOperand = std::move(LeftOp);
+    RightOperand = std::move(RightOp);
+  }
+
+  /// Evaluates the value of the binary operation represented by this AST,
+  /// using EvalBinop on the result of recursively evaluating the operands.
+  /// \returns the expression value or an error if an undefined numeric
+  /// variable is used in one of the operands.
+  Expected<uint64_t> eval() const;
+};
+
+class FileCheckPatternContext;
+
+/// Class representing a substitution to perform in the RegExStr string.
+class FileCheckSubstitution {
+protected:
+  /// Pointer to a class instance holding, among other things, the table with
+  /// the values of live string variables at the start of any given CHECK line.
+  /// Used for substituting string variables with the text they were defined
+  /// as. Expressions are linked to the numeric variables they use at
+  /// parse time and directly access the value of the numeric variable to
+  /// evaluate their value.
+  FileCheckPatternContext *Context;
+
+  /// The string that needs to be substituted for something else. For a
+  /// string variable this is its name, otherwise this is the whole expression.
+  StringRef FromStr;
+
+  // Index in RegExStr of where to do the substitution.
+  size_t InsertIdx;
+
+public:
+  FileCheckSubstitution(FileCheckPatternContext *Context, StringRef VarName,
+                        size_t InsertIdx)
+      : Context(Context), FromStr(VarName), InsertIdx(InsertIdx) {}
+
+  virtual ~FileCheckSubstitution() = default;
+
+  /// \returns the string to be substituted for something else.
+  StringRef getFromString() const { return FromStr; }
+
+  /// \returns the index where the substitution is to be performed in RegExStr.
+  size_t getIndex() const { return InsertIdx; }
+
+  /// \returns a string containing the result of the substitution represented
+  /// by this class instance or an error if substitution failed.
+  virtual Expected<std::string> getResult() const = 0;
+};
+
+class FileCheckStringSubstitution : public FileCheckSubstitution {
+public:
+  FileCheckStringSubstitution(FileCheckPatternContext *Context,
+                              StringRef VarName, size_t InsertIdx)
+      : FileCheckSubstitution(Context, VarName, InsertIdx) {}
+
+  /// \returns the text that the string variable in this substitution matched
+  /// when defined, or an error if the variable is undefined.
+  Expected<std::string> getResult() const override;
+};
+
+class FileCheckNumericSubstitution : public FileCheckSubstitution {
+private:
+  /// Pointer to the class representing the expression whose value is to be
+  /// substituted.
+  std::unique_ptr<FileCheckExpressionAST> ExpressionAST;
+
+public:
+  FileCheckNumericSubstitution(FileCheckPatternContext *Context, StringRef Expr,
+                               std::unique_ptr<FileCheckExpressionAST> ExprAST,
+                               size_t InsertIdx)
+      : FileCheckSubstitution(Context, Expr, InsertIdx) {
+    ExpressionAST = std::move(ExprAST);
+  }
+
+  /// \returns a string containing the result of evaluating the expression in
+  /// this substitution, or an error if evaluation failed.
+  Expected<std::string> getResult() const override;
+};
+
+//===----------------------------------------------------------------------===//
+// Pattern handling code.
+//===----------------------------------------------------------------------===//
+
+struct FileCheckDiag;
+
+/// Class holding the FileCheckPattern global state, shared by all patterns:
+/// tables holding values of variables and whether they are defined or not at
+/// any given time in the matching process.
+class FileCheckPatternContext {
+  friend class FileCheckPattern;
+
+private:
+  /// When matching a given pattern, this holds the value of all the string
+  /// variables defined in previous patterns. In a pattern, only the last
+  /// definition for a given variable is recorded in this table.
+  /// Back-references are used for uses after any the other definition.
+  StringMap<StringRef> GlobalVariableTable;
+
+  /// Map of all string variables defined so far. Used at parse time to detect
+  /// a name conflict between a numeric variable and a string variable when
+  /// the former is defined on a later line than the latter.
+  StringMap<bool> DefinedVariableTable;
+
+  /// When matching a given pattern, this holds the pointers to the classes
+  /// representing the numeric variables defined in previous patterns. When
+  /// matching a pattern all definitions for that pattern are recorded in the
+  /// NumericVariableDefs table in the FileCheckPattern instance of that
+  /// pattern.
+  StringMap<FileCheckNumericVariable *> GlobalNumericVariableTable;
+
+  /// Pointer to the class instance representing the @LINE pseudo variable for
+  /// easily updating its value.
+  FileCheckNumericVariable *LineVariable = nullptr;
+
+  /// Vector holding pointers to all parsed numeric variables. Used to
+  /// automatically free them once they are guaranteed to no longer be used.
+  std::vector<std::unique_ptr<FileCheckNumericVariable>> NumericVariables;
+
+  /// Vector holding pointers to all substitutions. Used to automatically free
+  /// them once they are guaranteed to no longer be used.
+  std::vector<std::unique_ptr<FileCheckSubstitution>> Substitutions;
+
+public:
+  /// \returns the value of string variable \p VarName or an error if no such
+  /// variable has been defined.
+  Expected<StringRef> getPatternVarValue(StringRef VarName);
+
+  /// Defines string and numeric variables from definitions given on the
+  /// command line, passed as a vector of [#]VAR=VAL strings in
+  /// \p CmdlineDefines. \returns an error list containing diagnostics against
+  /// \p SM for all definition parsing failures, if any, or Success otherwise.
+  Error defineCmdlineVariables(std::vector<std::string> &CmdlineDefines,
+                               SourceMgr &SM);
+
+  /// Create @LINE pseudo variable. Value is set when pattern are being
+  /// matched.
+  void createLineVariable();
+
+  /// Undefines local variables (variables whose name does not start with a '$'
+  /// sign), i.e. removes them from GlobalVariableTable and from
+  /// GlobalNumericVariableTable and also clears the value of numeric
+  /// variables.
+  void clearLocalVars();
+
+private:
+  /// Makes a new numeric variable and registers it for destruction when the
+  /// context is destroyed.
+  template <class... Types>
+  FileCheckNumericVariable *makeNumericVariable(Types... args);
+
+  /// Makes a new string substitution and registers it for destruction when the
+  /// context is destroyed.
+  FileCheckSubstitution *makeStringSubstitution(StringRef VarName,
+                                                size_t InsertIdx);
+
+  /// Makes a new numeric substitution and registers it for destruction when
+  /// the context is destroyed.
+  FileCheckSubstitution *
+  makeNumericSubstitution(StringRef ExpressionStr,
+                          std::unique_ptr<FileCheckExpressionAST> ExpressionAST,
+                          size_t InsertIdx);
+};
+
+/// Class to represent an error holding a diagnostic with location information
+/// used when printing it.
+class FileCheckErrorDiagnostic : public ErrorInfo<FileCheckErrorDiagnostic> {
+private:
+  SMDiagnostic Diagnostic;
+
+public:
+  static char ID;
+
+  FileCheckErrorDiagnostic(SMDiagnostic &&Diag) : Diagnostic(Diag) {}
+
+  std::error_code convertToErrorCode() const override {
+    return inconvertibleErrorCode();
+  }
+
+  /// Print diagnostic associated with this error when printing the error.
+  void log(raw_ostream &OS) const override { Diagnostic.print(nullptr, OS); }
+
+  static Error get(const SourceMgr &SM, SMLoc Loc, const Twine &ErrMsg) {
+    return make_error<FileCheckErrorDiagnostic>(
+        SM.GetMessage(Loc, SourceMgr::DK_Error, ErrMsg));
+  }
+
+  static Error get(const SourceMgr &SM, StringRef Buffer, const Twine &ErrMsg) {
+    return get(SM, SMLoc::getFromPointer(Buffer.data()), ErrMsg);
+  }
+};
+
+class FileCheckNotFoundError : public ErrorInfo<FileCheckNotFoundError> {
+public:
+  static char ID;
+
+  std::error_code convertToErrorCode() const override {
+    return inconvertibleErrorCode();
+  }
+
+  /// Print diagnostic associated with this error when printing the error.
+  void log(raw_ostream &OS) const override {
+    OS << "String not found in input";
+  }
+};
+
+class FileCheckPattern {
+  SMLoc PatternLoc;
+
+  /// A fixed string to match as the pattern or empty if this pattern requires
+  /// a regex match.
+  StringRef FixedStr;
+
+  /// A regex string to match as the pattern or empty if this pattern requires
+  /// a fixed string to match.
+  std::string RegExStr;
+
+  /// Entries in this vector represent a substitution of a string variable or
+  /// an expression in the RegExStr regex at match time. For example, in the
+  /// case of a CHECK directive with the pattern "foo[[bar]]baz[[#N+1]]",
+  /// RegExStr will contain "foobaz" and we'll get two entries in this vector
+  /// that tells us to insert the value of string variable "bar" at offset 3
+  /// and the value of expression "N+1" at offset 6.
+  std::vector<FileCheckSubstitution *> Substitutions;
+
+  /// Maps names of string variables defined in a pattern to the number of
+  /// their parenthesis group in RegExStr capturing their last definition.
+  ///
+  /// E.g. for the pattern "foo[[bar:.*]]baz([[bar]][[QUUX]][[bar:.*]])",
+  /// RegExStr will be "foo(.*)baz(\1<quux value>(.*))" where <quux value> is
+  /// the value captured for QUUX on the earlier line where it was defined, and
+  /// VariableDefs will map "bar" to the third parenthesis group which captures
+  /// the second definition of "bar".
+  ///
+  /// Note: uses std::map rather than StringMap to be able to get the key when
+  /// iterating over values.
+  std::map<StringRef, unsigned> VariableDefs;
+
+  /// Structure representing the definition of a numeric variable in a pattern.
+  /// It holds the pointer to the class representing the numeric variable whose
+  /// value is being defined and the number of the parenthesis group in
+  /// RegExStr to capture that value.
+  struct FileCheckNumericVariableMatch {
+    /// Pointer to class representing the numeric variable whose value is being
+    /// defined.
+    FileCheckNumericVariable *DefinedNumericVariable;
+
+    /// Number of the parenthesis group in RegExStr that captures the value of
+    /// this numeric variable definition.
+    unsigned CaptureParenGroup;
+  };
+
+  /// Holds the number of the parenthesis group in RegExStr and pointer to the
+  /// corresponding FileCheckNumericVariable class instance of all numeric
+  /// variable definitions. Used to set the matched value of all those
+  /// variables.
+  StringMap<FileCheckNumericVariableMatch> NumericVariableDefs;
+
+  /// Pointer to a class instance holding the global state shared by all
+  /// patterns:
+  /// - separate tables with the values of live string and numeric variables
+  ///   respectively at the start of any given CHECK line;
+  /// - table holding whether a string variable has been defined at any given
+  ///   point during the parsing phase.
+  FileCheckPatternContext *Context;
+
+  Check::FileCheckType CheckTy;
+
+  /// Line number for this CHECK pattern or None if it is an implicit pattern.
+  /// Used to determine whether a variable definition is made on an earlier
+  /// line to the one with this CHECK.
+  Optional<size_t> LineNumber;
+
+public:
+  FileCheckPattern(Check::FileCheckType Ty, FileCheckPatternContext *Context,
+                   Optional<size_t> Line = None)
+      : Context(Context), CheckTy(Ty), LineNumber(Line) {}
+
+  /// \returns the location in source code.
+  SMLoc getLoc() const { return PatternLoc; }
+
+  /// \returns the pointer to the global state for all patterns in this
+  /// FileCheck instance.
+  FileCheckPatternContext *getContext() const { return Context; }
+
+  /// \returns whether \p C is a valid first character for a variable name.
+  static bool isValidVarNameStart(char C);
+
+  /// Parsing information about a variable.
+  struct VariableProperties {
+    StringRef Name;
+    bool IsPseudo;
+  };
+
+  /// Parses the string at the start of \p Str for a variable name. \returns
+  /// a VariableProperties structure holding the variable name and whether it
+  /// is the name of a pseudo variable, or an error holding a diagnostic
+  /// against \p SM if parsing fail. If parsing was successful, also strips
+  /// \p Str from the variable name.
+  static Expected<VariableProperties> parseVariable(StringRef &Str,
+                                                    const SourceMgr &SM);
+  /// Parses \p Expr for a numeric substitution block at line \p LineNumber,
+  /// or before input is parsed if \p LineNumber is None. Parameter
+  /// \p IsLegacyLineExpr indicates whether \p Expr should be a legacy @LINE
+  /// expression and \p Context points to the class instance holding the live
+  /// string and numeric variables. \returns a pointer to the class instance
+  /// representing the AST of the expression whose value must be substitued, or
+  /// an error holding a diagnostic against \p SM if parsing fails. If
+  /// substitution was successful, sets \p DefinedNumericVariable to point to
+  /// the class representing the numeric variable defined in this numeric
+  /// substitution block, or None if this block does not define any variable.
+  static Expected<std::unique_ptr<FileCheckExpressionAST>>
+  parseNumericSubstitutionBlock(
+      StringRef Expr,
+      Optional<FileCheckNumericVariable *> &DefinedNumericVariable,
+      bool IsLegacyLineExpr, Optional<size_t> LineNumber,
+      FileCheckPatternContext *Context, const SourceMgr &SM);
+  /// Parses the pattern in \p PatternStr and initializes this FileCheckPattern
+  /// instance accordingly.
+  ///
+  /// \p Prefix provides which prefix is being matched, \p Req describes the
+  /// global options that influence the parsing such as whitespace
+  /// canonicalization, \p SM provides the SourceMgr used for error reports.
+  /// \returns true in case of an error, false otherwise.
+  bool parsePattern(StringRef PatternStr, StringRef Prefix, SourceMgr &SM,
+                    const FileCheckRequest &Req);
+  /// Matches the pattern string against the input buffer \p Buffer
+  ///
+  /// \returns the position that is matched or an error indicating why matching
+  /// failed. If there is a match, updates \p MatchLen with the size of the
+  /// matched string.
+  ///
+  /// The GlobalVariableTable StringMap in the FileCheckPatternContext class
+  /// instance provides the current values of FileCheck string variables and
+  /// is updated if this match defines new values. Likewise, the
+  /// GlobalNumericVariableTable StringMap in the same class provides the
+  /// current values of FileCheck numeric variables and is updated if this
+  /// match defines new numeric values.
+  Expected<size_t> match(StringRef Buffer, size_t &MatchLen,
+                         const SourceMgr &SM) const;
+  /// Prints the value of successful substitutions or the name of the undefined
+  /// string or numeric variables preventing a successful substitution.
+  void printSubstitutions(const SourceMgr &SM, StringRef Buffer,
+                          SMRange MatchRange = None) const;
+  void printFuzzyMatch(const SourceMgr &SM, StringRef Buffer,
+                       std::vector<FileCheckDiag> *Diags) const;
+
+  bool hasVariable() const {
+    return !(Substitutions.empty() && VariableDefs.empty());
+  }
+
+  Check::FileCheckType getCheckTy() const { return CheckTy; }
+
+  int getCount() const { return CheckTy.getCount(); }
+
+private:
+  bool AddRegExToRegEx(StringRef RS, unsigned &CurParen, SourceMgr &SM);
+  void AddBackrefToRegEx(unsigned BackrefNum);
+  /// Computes an arbitrary estimate for the quality of matching this pattern
+  /// at the start of \p Buffer; a distance of zero should correspond to a
+  /// perfect match.
+  unsigned computeMatchDistance(StringRef Buffer) const;
+  /// Finds the closing sequence of a regex variable usage or definition.
+  ///
+  /// \p Str has to point in the beginning of the definition (right after the
+  /// opening sequence). \p SM holds the SourceMgr used for error repporting.
+  ///  \returns the offset of the closing sequence within Str, or npos if it
+  /// was not found.
+  size_t FindRegexVarEnd(StringRef Str, SourceMgr &SM);
+
+  /// Parses \p Expr for the name of a numeric variable to be defined at line
+  /// \p LineNumber, or before input is parsed if \p LineNumber is None.
+  /// \returns a pointer to the class instance representing that variable,
+  /// creating it if needed, or an error holding a diagnostic against \p SM
+  /// should defining such a variable be invalid.
+  static Expected<FileCheckNumericVariable *> parseNumericVariableDefinition(
+      StringRef &Expr, FileCheckPatternContext *Context,
+      Optional<size_t> LineNumber, const SourceMgr &SM);
+  /// Parses \p Name as a (pseudo if \p IsPseudo is true) numeric variable use
+  /// at line \p LineNumber, or before input is parsed if \p LineNumber is
+  /// None. Parameter \p Context points to the class instance holding the live
+  /// string and numeric variables. \returns the pointer to the class instance
+  /// representing that variable if successful, or an error holding a
+  /// diagnostic against \p SM otherwise.
+  static Expected<std::unique_ptr<FileCheckNumericVariableUse>>
+  parseNumericVariableUse(StringRef Name, bool IsPseudo,
+                          Optional<size_t> LineNumber,
+                          FileCheckPatternContext *Context,
+                          const SourceMgr &SM);
+  enum class AllowedOperand { LineVar, Literal, Any };
+  /// Parses \p Expr for use of a numeric operand at line \p LineNumber, or
+  /// before input is parsed if \p LineNumber is None. Accepts both literal
+  /// values and numeric variables, depending on the value of \p AO. Parameter
+  /// \p Context points to the class instance holding the live string and
+  /// numeric variables. \returns the class representing that operand in the
+  /// AST of the expression or an error holding a diagnostic against \p SM
+  /// otherwise.
+  static Expected<std::unique_ptr<FileCheckExpressionAST>>
+  parseNumericOperand(StringRef &Expr, AllowedOperand AO,
+                      Optional<size_t> LineNumber,
+                      FileCheckPatternContext *Context, const SourceMgr &SM);
+  /// Parses \p Expr for a binary operation at line \p LineNumber, or before
+  /// input is parsed if \p LineNumber is None. The left operand of this binary
+  /// operation is given in \p LeftOp and \p IsLegacyLineExpr indicates whether
+  /// we are parsing a legacy @LINE expression. Parameter \p Context points to
+  /// the class instance holding the live string and numeric variables.
+  /// \returns the class representing the binary operation in the AST of the
+  /// expression, or an error holding a diagnostic against \p SM otherwise.
+  static Expected<std::unique_ptr<FileCheckExpressionAST>>
+  parseBinop(StringRef &Expr, std::unique_ptr<FileCheckExpressionAST> LeftOp,
+             bool IsLegacyLineExpr, Optional<size_t> LineNumber,
+             FileCheckPatternContext *Context, const SourceMgr &SM);
+};
+
+//===----------------------------------------------------------------------===//
+// Check Strings.
+//===----------------------------------------------------------------------===//
+
+/// A check that we found in the input file.
+struct FileCheckString {
+  /// The pattern to match.
+  FileCheckPattern Pat;
+
+  /// Which prefix name this check matched.
+  StringRef Prefix;
+
+  /// The location in the match file that the check string was specified.
+  SMLoc Loc;
+
+  /// All of the strings that are disallowed from occurring between this match
+  /// string and the previous one (or start of file).
+  std::vector<FileCheckPattern> DagNotStrings;
+
+  FileCheckString(const FileCheckPattern &P, StringRef S, SMLoc L)
+      : Pat(P), Prefix(S), Loc(L) {}
+
+  /// Matches check string and its "not strings" and/or "dag strings".
+  size_t Check(const SourceMgr &SM, StringRef Buffer, bool IsLabelScanMode,
+               size_t &MatchLen, FileCheckRequest &Req,
+               std::vector<FileCheckDiag> *Diags) const;
+
+  /// Verifies that there is a single line in the given \p Buffer. Errors are
+  /// reported against \p SM.
+  bool CheckNext(const SourceMgr &SM, StringRef Buffer) const;
+  /// Verifies that there is no newline in the given \p Buffer. Errors are
+  /// reported against \p SM.
+  bool CheckSame(const SourceMgr &SM, StringRef Buffer) const;
+  /// Verifies that none of the strings in \p NotStrings are found in the given
+  /// \p Buffer. Errors are reported against \p SM and diagnostics recorded in
+  /// \p Diags according to the verbosity level set in \p Req.
+  bool CheckNot(const SourceMgr &SM, StringRef Buffer,
+                const std::vector<const FileCheckPattern *> &NotStrings,
+                const FileCheckRequest &Req,
+                std::vector<FileCheckDiag> *Diags) const;
+  /// Matches "dag strings" and their mixed "not strings".
+  size_t CheckDag(const SourceMgr &SM, StringRef Buffer,
+                  std::vector<const FileCheckPattern *> &NotStrings,
+                  const FileCheckRequest &Req,
+                  std::vector<FileCheckDiag> *Diags) const;
+};
+
+} // namespace llvm
+
+#endif