contrib/llvm/lib/Support/FileCheck.cpp

   1 //===- FileCheck.cpp - Check that File's Contents match what is expected --===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // FileCheck does a line-by line check of a file that validates whether it
  10 // contains the expected content.  This is useful for regression tests etc.
  11 //
  12 // This file implements most of the API that will be used by the FileCheck utility
  13 // as well as various unittests.
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Support/FileCheck.h"
  17 #include "llvm/ADT/StringSet.h"
  18 #include "llvm/Support/FormatVariadic.h"
  19 #include <cstdint>
  20 #include <list>
  21 #include <map>
  22 #include <tuple>
  23 #include <utility>
  24
  25 using namespace llvm;
  26
  27 void FileCheckNumericVariable::setValue(uint64_t NewValue) {
  28   assert(!Value && "Overwriting numeric variable's value is not allowed");
  29   Value = NewValue;
  30 }
  31
  32 void FileCheckNumericVariable::clearValue() {
  33   if (!Value)
  34     return;
  35   Value = None;
  36 }
  37
  38 Expected<uint64_t> FileCheckNumericVariableUse::eval() const {
  39   Optional<uint64_t> Value = NumericVariable->getValue();
  40   if (Value)
  41     return *Value;
  42   return make_error<FileCheckUndefVarError>(Name);
  43 }
  44
  45 Expected<uint64_t> FileCheckASTBinop::eval() const {
  46   Expected<uint64_t> LeftOp = LeftOperand->eval();
  47   Expected<uint64_t> RightOp = RightOperand->eval();
  48
  49   // Bubble up any error (e.g. undefined variables) in the recursive
  50   // evaluation.
  51   if (!LeftOp || !RightOp) {
  52     Error Err = Error::success();
  53     if (!LeftOp)
  54       Err = joinErrors(std::move(Err), LeftOp.takeError());
  55     if (!RightOp)
  56       Err = joinErrors(std::move(Err), RightOp.takeError());
  57     return std::move(Err);
  58   }
  59
  60   return EvalBinop(*LeftOp, *RightOp);
  61 }
  62
  63 Expected<std::string> FileCheckNumericSubstitution::getResult() const {
  64   Expected<uint64_t> EvaluatedValue = ExpressionAST->eval();
  65   if (!EvaluatedValue)
  66     return EvaluatedValue.takeError();
  67   return utostr(*EvaluatedValue);
  68 }
  69
  70 Expected<std::string> FileCheckStringSubstitution::getResult() const {
  71   // Look up the value and escape it so that we can put it into the regex.
  72   Expected<StringRef> VarVal = Context->getPatternVarValue(FromStr);
  73   if (!VarVal)
  74     return VarVal.takeError();
  75   return Regex::escape(*VarVal);
  76 }
  77
  78 bool FileCheckPattern::isValidVarNameStart(char C) {
  79   return C == '_' || isalpha(C);
  80 }
  81
  82 Expected<FileCheckPattern::VariableProperties>
  83 FileCheckPattern::parseVariable(StringRef &Str, const SourceMgr &SM) {
  84   if (Str.empty())
  85     return FileCheckErrorDiagnostic::get(SM, Str, "empty variable name");
  86
  87   bool ParsedOneChar = false;
  88   unsigned I = 0;
  89   bool IsPseudo = Str[0] == '@';
  90
  91   // Global vars start with '$'.
  92   if (Str[0] == '$' || IsPseudo)
  93     ++I;
  94
  95   for (unsigned E = Str.size(); I != E; ++I) {
  96     if (!ParsedOneChar && !isValidVarNameStart(Str[I]))
  97       return FileCheckErrorDiagnostic::get(SM, Str, "invalid variable name");
  98
  99     // Variable names are composed of alphanumeric characters and underscores.
 100     if (Str[I] != '_' && !isalnum(Str[I]))
 101       break;
 102     ParsedOneChar = true;
 103   }
 104
 105   StringRef Name = Str.take_front(I);
 106   Str = Str.substr(I);
 107   return VariableProperties {Name, IsPseudo};
 108 }
 109
 110 // StringRef holding all characters considered as horizontal whitespaces by
 111 // FileCheck input canonicalization.
 112 StringRef SpaceChars = " \t";
 113
 114 // Parsing helper function that strips the first character in S and returns it.
 115 static char popFront(StringRef &S) {
 116   char C = S.front();
 117   S = S.drop_front();
 118   return C;
 119 }
 120
 121 char FileCheckUndefVarError::ID = 0;
 122 char FileCheckErrorDiagnostic::ID = 0;
 123 char FileCheckNotFoundError::ID = 0;
 124
 125 Expected<FileCheckNumericVariable *>
 126 FileCheckPattern::parseNumericVariableDefinition(
 127     StringRef &Expr, FileCheckPatternContext *Context,
 128     Optional<size_t> LineNumber, const SourceMgr &SM) {
 129   Expected<VariableProperties> ParseVarResult = parseVariable(Expr, SM);
 130   if (!ParseVarResult)
 131     return ParseVarResult.takeError();
 132   StringRef Name = ParseVarResult->Name;
 133
 134   if (ParseVarResult->IsPseudo)
 135     return FileCheckErrorDiagnostic::get(
 136         SM, Name, "definition of pseudo numeric variable unsupported");
 137
 138   // Detect collisions between string and numeric variables when the latter
 139   // is created later than the former.
 140   if (Context->DefinedVariableTable.find(Name) !=
 141       Context->DefinedVariableTable.end())
 142     return FileCheckErrorDiagnostic::get(
 143         SM, Name, "string variable with name '" + Name + "' already exists");
 144
 145   Expr = Expr.ltrim(SpaceChars);
 146   if (!Expr.empty())
 147     return FileCheckErrorDiagnostic::get(
 148         SM, Expr, "unexpected characters after numeric variable name");
 149
 150   FileCheckNumericVariable *DefinedNumericVariable;
 151   auto VarTableIter = Context->GlobalNumericVariableTable.find(Name);
 152   if (VarTableIter != Context->GlobalNumericVariableTable.end())
 153     DefinedNumericVariable = VarTableIter->second;
 154   else
 155     DefinedNumericVariable = Context->makeNumericVariable(Name, LineNumber);
 156
 157   return DefinedNumericVariable;
 158 }
 159
 160 Expected<std::unique_ptr<FileCheckNumericVariableUse>>
 161 FileCheckPattern::parseNumericVariableUse(StringRef Name, bool IsPseudo,
 162                                           const SourceMgr &SM) const {
 163   if (IsPseudo && !Name.equals("@LINE"))
 164     return FileCheckErrorDiagnostic::get(
 165         SM, Name, "invalid pseudo numeric variable '" + Name + "'");
 166
 167   // Numeric variable definitions and uses are parsed in the order in which
 168   // they appear in the CHECK patterns. For each definition, the pointer to the
 169   // class instance of the corresponding numeric variable definition is stored
 170   // in GlobalNumericVariableTable in parsePattern. Therefore, if the pointer
 171   // we get below is null, it means no such variable was defined before. When
 172   // that happens, we create a dummy variable so that parsing can continue. All
 173   // uses of undefined variables, whether string or numeric, are then diagnosed
 174   // in printSubstitutions() after failing to match.
 175   auto VarTableIter = Context->GlobalNumericVariableTable.find(Name);
 176   FileCheckNumericVariable *NumericVariable;
 177   if (VarTableIter != Context->GlobalNumericVariableTable.end())
 178     NumericVariable = VarTableIter->second;
 179   else {
 180     NumericVariable = Context->makeNumericVariable(Name);
 181     Context->GlobalNumericVariableTable[Name] = NumericVariable;
 182   }
 183
 184   Optional<size_t> DefLineNumber = NumericVariable->getDefLineNumber();
 185   if (DefLineNumber && LineNumber && *DefLineNumber == *LineNumber)
 186     return FileCheckErrorDiagnostic::get(
 187         SM, Name,
 188         "numeric variable '" + Name + "' defined on the same line as used");
 189
 190   return llvm::make_unique<FileCheckNumericVariableUse>(Name, NumericVariable);
 191 }
 192
 193 Expected<std::unique_ptr<FileCheckExpressionAST>>
 194 FileCheckPattern::parseNumericOperand(StringRef &Expr, AllowedOperand AO,
 195                                       const SourceMgr &SM) const {
 196   if (AO == AllowedOperand::LineVar || AO == AllowedOperand::Any) {
 197     // Try to parse as a numeric variable use.
 198     Expected<FileCheckPattern::VariableProperties> ParseVarResult =
 199         parseVariable(Expr, SM);
 200     if (ParseVarResult)
 201       return parseNumericVariableUse(ParseVarResult->Name,
 202                                      ParseVarResult->IsPseudo, SM);
 203     if (AO == AllowedOperand::LineVar)
 204       return ParseVarResult.takeError();
 205     // Ignore the error and retry parsing as a literal.
 206     consumeError(ParseVarResult.takeError());
 207   }
 208
 209   // Otherwise, parse it as a literal.
 210   uint64_t LiteralValue;
 211   if (!Expr.consumeInteger(/*Radix=*/10, LiteralValue))
 212     return llvm::make_unique<FileCheckExpressionLiteral>(LiteralValue);
 213
 214   return FileCheckErrorDiagnostic::get(SM, Expr,
 215                                        "invalid operand format '" + Expr + "'");
 216 }
 217
 218 static uint64_t add(uint64_t LeftOp, uint64_t RightOp) {
 219   return LeftOp + RightOp;
 220 }
 221
 222 static uint64_t sub(uint64_t LeftOp, uint64_t RightOp) {
 223   return LeftOp - RightOp;
 224 }
 225
 226 Expected<std::unique_ptr<FileCheckExpressionAST>>
 227 FileCheckPattern::parseBinop(StringRef &Expr,
 228                              std::unique_ptr<FileCheckExpressionAST> LeftOp,
 229                              bool IsLegacyLineExpr, const SourceMgr &SM) const {
 230   Expr = Expr.ltrim(SpaceChars);
 231   if (Expr.empty())
 232     return std::move(LeftOp);
 233
 234   // Check if this is a supported operation and select a function to perform
 235   // it.
 236   SMLoc OpLoc = SMLoc::getFromPointer(Expr.data());
 237   char Operator = popFront(Expr);
 238   binop_eval_t EvalBinop;
 239   switch (Operator) {
 240   case '+':
 241     EvalBinop = add;
 242     break;
 243   case '-':
 244     EvalBinop = sub;
 245     break;
 246   default:
 247     return FileCheckErrorDiagnostic::get(
 248         SM, OpLoc, Twine("unsupported operation '") + Twine(Operator) + "'");
 249   }
 250
 251   // Parse right operand.
 252   Expr = Expr.ltrim(SpaceChars);
 253   if (Expr.empty())
 254     return FileCheckErrorDiagnostic::get(SM, Expr,
 255                                          "missing operand in expression");
 256   // The second operand in a legacy @LINE expression is always a literal.
 257   AllowedOperand AO =
 258       IsLegacyLineExpr ? AllowedOperand::Literal : AllowedOperand::Any;
 259   Expected<std::unique_ptr<FileCheckExpressionAST>> RightOpResult =
 260       parseNumericOperand(Expr, AO, SM);
 261   if (!RightOpResult)
 262     return RightOpResult;
 263
 264   Expr = Expr.ltrim(SpaceChars);
 265   return llvm::make_unique<FileCheckASTBinop>(EvalBinop, std::move(LeftOp),
 266                                               std::move(*RightOpResult));
 267 }
 268
 269 Expected<std::unique_ptr<FileCheckExpressionAST>>
 270 FileCheckPattern::parseNumericSubstitutionBlock(
 271     StringRef Expr,
 272     Optional<FileCheckNumericVariable *> &DefinedNumericVariable,
 273     bool IsLegacyLineExpr, const SourceMgr &SM) const {
 274   // Parse the numeric variable definition.
 275   DefinedNumericVariable = None;
 276   size_t DefEnd = Expr.find(':');
 277   if (DefEnd != StringRef::npos) {
 278     StringRef DefExpr = Expr.substr(0, DefEnd);
 279     StringRef UseExpr = Expr.substr(DefEnd + 1);
 280
 281     UseExpr = UseExpr.ltrim(SpaceChars);
 282     if (!UseExpr.empty())
 283       return FileCheckErrorDiagnostic::get(
 284           SM, UseExpr,
 285           "unexpected string after variable definition: '" + UseExpr + "'");
 286
 287     DefExpr = DefExpr.ltrim(SpaceChars);
 288     Expected<FileCheckNumericVariable *> ParseResult =
 289         parseNumericVariableDefinition(DefExpr, Context, LineNumber, SM);
 290     if (!ParseResult)
 291       return ParseResult.takeError();
 292     DefinedNumericVariable = *ParseResult;
 293
 294     return nullptr;
 295   }
 296
 297   // Parse the expression itself.
 298   Expr = Expr.ltrim(SpaceChars);
 299   // The first operand in a legacy @LINE expression is always the @LINE pseudo
 300   // variable.
 301   AllowedOperand AO =
 302       IsLegacyLineExpr ? AllowedOperand::LineVar : AllowedOperand::Any;
 303   Expected<std::unique_ptr<FileCheckExpressionAST>> ParseResult =
 304       parseNumericOperand(Expr, AO, SM);
 305   while (ParseResult && !Expr.empty()) {
 306     ParseResult =
 307         parseBinop(Expr, std::move(*ParseResult), IsLegacyLineExpr, SM);
 308     // Legacy @LINE expressions only allow 2 operands.
 309     if (ParseResult && IsLegacyLineExpr && !Expr.empty())
 310       return FileCheckErrorDiagnostic::get(
 311           SM, Expr,
 312           "unexpected characters at end of expression '" + Expr + "'");
 313   }
 314   if (!ParseResult)
 315     return ParseResult;
 316   return std::move(*ParseResult);
 317 }
 318
 319 bool FileCheckPattern::parsePattern(StringRef PatternStr, StringRef Prefix,
 320                                     SourceMgr &SM,
 321                                     const FileCheckRequest &Req) {
 322   bool MatchFullLinesHere = Req.MatchFullLines && CheckTy != Check::CheckNot;
 323
 324   PatternLoc = SMLoc::getFromPointer(PatternStr.data());
 325
 326   if (!(Req.NoCanonicalizeWhiteSpace && Req.MatchFullLines))
 327     // Ignore trailing whitespace.
 328     while (!PatternStr.empty() &&
 329            (PatternStr.back() == ' ' || PatternStr.back() == '\t'))
 330       PatternStr = PatternStr.substr(0, PatternStr.size() - 1);
 331
 332   // Check that there is something on the line.
 333   if (PatternStr.empty() && CheckTy != Check::CheckEmpty) {
 334     SM.PrintMessage(PatternLoc, SourceMgr::DK_Error,
 335                     "found empty check string with prefix '" + Prefix + ":'");
 336     return true;
 337   }
 338
 339   if (!PatternStr.empty() && CheckTy == Check::CheckEmpty) {
 340     SM.PrintMessage(
 341         PatternLoc, SourceMgr::DK_Error,
 342         "found non-empty check string for empty check with prefix '" + Prefix +
 343             ":'");
 344     return true;
 345   }
 346
 347   if (CheckTy == Check::CheckEmpty) {
 348     RegExStr = "(\n$)";
 349     return false;
 350   }
 351
 352   // Check to see if this is a fixed string, or if it has regex pieces.
 353   if (!MatchFullLinesHere &&
 354       (PatternStr.size() < 2 || (PatternStr.find("{{") == StringRef::npos &&
 355                                  PatternStr.find("[[") == StringRef::npos))) {
 356     FixedStr = PatternStr;
 357     return false;
 358   }
 359
 360   if (MatchFullLinesHere) {
 361     RegExStr += '^';
 362     if (!Req.NoCanonicalizeWhiteSpace)
 363       RegExStr += " *";
 364   }
 365
 366   // Paren value #0 is for the fully matched string.  Any new parenthesized
 367   // values add from there.
 368   unsigned CurParen = 1;
 369
 370   // Otherwise, there is at least one regex piece.  Build up the regex pattern
 371   // by escaping scary characters in fixed strings, building up one big regex.
 372   while (!PatternStr.empty()) {
 373     // RegEx matches.
 374     if (PatternStr.startswith("{{")) {
 375       // This is the start of a regex match.  Scan for the }}.
 376       size_t End = PatternStr.find("}}");
 377       if (End == StringRef::npos) {
 378         SM.PrintMessage(SMLoc::getFromPointer(PatternStr.data()),
 379                         SourceMgr::DK_Error,
 380                         "found start of regex string with no end '}}'");
 381         return true;
 382       }
 383
 384       // Enclose {{}} patterns in parens just like [[]] even though we're not
 385       // capturing the result for any purpose.  This is required in case the
 386       // expression contains an alternation like: CHECK:  abc{{x|z}}def.  We
 387       // want this to turn into: "abc(x|z)def" not "abcx|zdef".
 388       RegExStr += '(';
 389       ++CurParen;
 390
 391       if (AddRegExToRegEx(PatternStr.substr(2, End - 2), CurParen, SM))
 392         return true;
 393       RegExStr += ')';
 394
 395       PatternStr = PatternStr.substr(End + 2);
 396       continue;
 397     }
 398
 399     // String and numeric substitution blocks. String substitution blocks come
 400     // in two forms: [[foo:.*]] and [[foo]]. The former matches .* (or some
 401     // other regex) and assigns it to the string variable 'foo'. The latter
 402     // substitutes foo's value. Numeric substitution blocks work the same way
 403     // as string ones, but start with a '#' sign after the double brackets.
 404     // Both string and numeric variable names must satisfy the regular
 405     // expression "[a-zA-Z_][0-9a-zA-Z_]*" to be valid, as this helps catch
 406     // some common errors.
 407     if (PatternStr.startswith("[[")) {
 408       StringRef UnparsedPatternStr = PatternStr.substr(2);
 409       // Find the closing bracket pair ending the match.  End is going to be an
 410       // offset relative to the beginning of the match string.
 411       size_t End = FindRegexVarEnd(UnparsedPatternStr, SM);
 412       StringRef MatchStr = UnparsedPatternStr.substr(0, End);
 413       bool IsNumBlock = MatchStr.consume_front("#");
 414
 415       if (End == StringRef::npos) {
 416         SM.PrintMessage(SMLoc::getFromPointer(PatternStr.data()),
 417                         SourceMgr::DK_Error,
 418                         "Invalid substitution block, no ]] found");
 419         return true;
 420       }
 421       // Strip the substitution block we are parsing. End points to the start
 422       // of the "]]" closing the expression so account for it in computing the
 423       // index of the first unparsed character.
 424       PatternStr = UnparsedPatternStr.substr(End + 2);
 425
 426       bool IsDefinition = false;
 427       // Whether the substitution block is a legacy use of @LINE with string
 428       // substitution block syntax.
 429       bool IsLegacyLineExpr = false;
 430       StringRef DefName;
 431       StringRef SubstStr;
 432       StringRef MatchRegexp;
 433       size_t SubstInsertIdx = RegExStr.size();
 434
 435       // Parse string variable or legacy @LINE expression.
 436       if (!IsNumBlock) {
 437         size_t VarEndIdx = MatchStr.find(":");
 438         size_t SpacePos = MatchStr.substr(0, VarEndIdx).find_first_of(" \t");
 439         if (SpacePos != StringRef::npos) {
 440           SM.PrintMessage(SMLoc::getFromPointer(MatchStr.data() + SpacePos),
 441                           SourceMgr::DK_Error, "unexpected whitespace");
 442           return true;
 443         }
 444
 445         // Get the name (e.g. "foo") and verify it is well formed.
 446         StringRef OrigMatchStr = MatchStr;
 447         Expected<FileCheckPattern::VariableProperties> ParseVarResult =
 448             parseVariable(MatchStr, SM);
 449         if (!ParseVarResult) {
 450           logAllUnhandledErrors(ParseVarResult.takeError(), errs());
 451           return true;
 452         }
 453         StringRef Name = ParseVarResult->Name;
 454         bool IsPseudo = ParseVarResult->IsPseudo;
 455
 456         IsDefinition = (VarEndIdx != StringRef::npos);
 457         if (IsDefinition) {
 458           if ((IsPseudo || !MatchStr.consume_front(":"))) {
 459             SM.PrintMessage(SMLoc::getFromPointer(Name.data()),
 460                             SourceMgr::DK_Error,
 461                             "invalid name in string variable definition");
 462             return true;
 463           }
 464
 465           // Detect collisions between string and numeric variables when the
 466           // former is created later than the latter.
 467           if (Context->GlobalNumericVariableTable.find(Name) !=
 468               Context->GlobalNumericVariableTable.end()) {
 469             SM.PrintMessage(
 470                 SMLoc::getFromPointer(Name.data()), SourceMgr::DK_Error,
 471                 "numeric variable with name '" + Name + "' already exists");
 472             return true;
 473           }
 474           DefName = Name;
 475           MatchRegexp = MatchStr;
 476         } else {
 477           if (IsPseudo) {
 478             MatchStr = OrigMatchStr;
 479             IsLegacyLineExpr = IsNumBlock = true;
 480           } else
 481             SubstStr = Name;
 482         }
 483       }
 484
 485       // Parse numeric substitution block.
 486       std::unique_ptr<FileCheckExpressionAST> ExpressionAST;
 487       Optional<FileCheckNumericVariable *> DefinedNumericVariable;
 488       if (IsNumBlock) {
 489         Expected<std::unique_ptr<FileCheckExpressionAST>> ParseResult =
 490             parseNumericSubstitutionBlock(MatchStr, DefinedNumericVariable,
 491                                           IsLegacyLineExpr, SM);
 492         if (!ParseResult) {
 493           logAllUnhandledErrors(ParseResult.takeError(), errs());
 494           return true;
 495         }
 496         ExpressionAST = std::move(*ParseResult);
 497         if (DefinedNumericVariable) {
 498           IsDefinition = true;
 499           DefName = (*DefinedNumericVariable)->getName();
 500           MatchRegexp = StringRef("[0-9]+");
 501         } else
 502           SubstStr = MatchStr;
 503       }
 504
 505       // Handle substitutions: [[foo]] and [[#<foo expr>]].
 506       if (!IsDefinition) {
 507         // Handle substitution of string variables that were defined earlier on
 508         // the same line by emitting a backreference. Expressions do not
 509         // support substituting a numeric variable defined on the same line.
 510         if (!IsNumBlock && VariableDefs.find(SubstStr) != VariableDefs.end()) {
 511           unsigned CaptureParenGroup = VariableDefs[SubstStr];
 512           if (CaptureParenGroup < 1 || CaptureParenGroup > 9) {
 513             SM.PrintMessage(SMLoc::getFromPointer(SubstStr.data()),
 514                             SourceMgr::DK_Error,
 515                             "Can't back-reference more than 9 variables");
 516             return true;
 517           }
 518           AddBackrefToRegEx(CaptureParenGroup);
 519         } else {
 520           // Handle substitution of string variables ([[<var>]]) defined in
 521           // previous CHECK patterns, and substitution of expressions.
 522           FileCheckSubstitution *Substitution =
 523               IsNumBlock
 524                   ? Context->makeNumericSubstitution(
 525                         SubstStr, std::move(ExpressionAST), SubstInsertIdx)
 526                   : Context->makeStringSubstitution(SubstStr, SubstInsertIdx);
 527           Substitutions.push_back(Substitution);
 528         }
 529         continue;
 530       }
 531
 532       // Handle variable definitions: [[<def>:(...)]] and
 533       // [[#(...)<def>:(...)]].
 534       if (IsNumBlock) {
 535         FileCheckNumericVariableMatch NumericVariableDefinition = {
 536             *DefinedNumericVariable, CurParen};
 537         NumericVariableDefs[DefName] = NumericVariableDefinition;
 538         // This store is done here rather than in match() to allow
 539         // parseNumericVariableUse() to get the pointer to the class instance
 540         // of the right variable definition corresponding to a given numeric
 541         // variable use.
 542         Context->GlobalNumericVariableTable[DefName] = *DefinedNumericVariable;
 543       } else {
 544         VariableDefs[DefName] = CurParen;
 545         // Mark the string variable as defined to detect collisions between
 546         // string and numeric variables in parseNumericVariableUse() and
 547         // DefineCmdlineVariables() when the latter is created later than the
 548         // former. We cannot reuse GlobalVariableTable for this by populating
 549         // it with an empty string since we would then lose the ability to
 550         // detect the use of an undefined variable in match().
 551         Context->DefinedVariableTable[DefName] = true;
 552       }
 553       RegExStr += '(';
 554       ++CurParen;
 555
 556       if (AddRegExToRegEx(MatchRegexp, CurParen, SM))
 557         return true;
 558
 559       RegExStr += ')';
 560     }
 561
 562     // Handle fixed string matches.
 563     // Find the end, which is the start of the next regex.
 564     size_t FixedMatchEnd = PatternStr.find("{{");
 565     FixedMatchEnd = std::min(FixedMatchEnd, PatternStr.find("[["));
 566     RegExStr += Regex::escape(PatternStr.substr(0, FixedMatchEnd));
 567     PatternStr = PatternStr.substr(FixedMatchEnd);
 568   }
 569
 570   if (MatchFullLinesHere) {
 571     if (!Req.NoCanonicalizeWhiteSpace)
 572       RegExStr += " *";
 573     RegExStr += '$';
 574   }
 575
 576   return false;
 577 }
 578
 579 bool FileCheckPattern::AddRegExToRegEx(StringRef RS, unsigned &CurParen, SourceMgr &SM) {
 580   Regex R(RS);
 581   std::string Error;
 582   if (!R.isValid(Error)) {
 583     SM.PrintMessage(SMLoc::getFromPointer(RS.data()), SourceMgr::DK_Error,
 584                     "invalid regex: " + Error);
 585     return true;
 586   }
 587
 588   RegExStr += RS.str();
 589   CurParen += R.getNumMatches();
 590   return false;
 591 }
 592
 593 void FileCheckPattern::AddBackrefToRegEx(unsigned BackrefNum) {
 594   assert(BackrefNum >= 1 && BackrefNum <= 9 && "Invalid backref number");
 595   std::string Backref = std::string("\\") + std::string(1, '0' + BackrefNum);
 596   RegExStr += Backref;
 597 }
 598
 599 Expected<size_t> FileCheckPattern::match(StringRef Buffer, size_t &MatchLen,
 600                                          const SourceMgr &SM) const {
 601   // If this is the EOF pattern, match it immediately.
 602   if (CheckTy == Check::CheckEOF) {
 603     MatchLen = 0;
 604     return Buffer.size();
 605   }
 606
 607   // If this is a fixed string pattern, just match it now.
 608   if (!FixedStr.empty()) {
 609     MatchLen = FixedStr.size();
 610     size_t Pos = Buffer.find(FixedStr);
 611     if (Pos == StringRef::npos)
 612       return make_error<FileCheckNotFoundError>();
 613     return Pos;
 614   }
 615
 616   // Regex match.
 617
 618   // If there are substitutions, we need to create a temporary string with the
 619   // actual value.
 620   StringRef RegExToMatch = RegExStr;
 621   std::string TmpStr;
 622   if (!Substitutions.empty()) {
 623     TmpStr = RegExStr;
 624     if (LineNumber)
 625       Context->LineVariable->setValue(*LineNumber);
 626
 627     size_t InsertOffset = 0;
 628     // Substitute all string variables and expressions whose values are only
 629     // now known. Use of string variables defined on the same line are handled
 630     // by back-references.
 631     for (const auto &Substitution : Substitutions) {
 632       // Substitute and check for failure (e.g. use of undefined variable).
 633       Expected<std::string> Value = Substitution->getResult();
 634       if (!Value) {
 635         Context->LineVariable->clearValue();
 636         return Value.takeError();
 637       }
 638
 639       // Plop it into the regex at the adjusted offset.
 640       TmpStr.insert(TmpStr.begin() + Substitution->getIndex() + InsertOffset,
 641                     Value->begin(), Value->end());
 642       InsertOffset += Value->size();
 643     }
 644
 645     // Match the newly constructed regex.
 646     RegExToMatch = TmpStr;
 647     Context->LineVariable->clearValue();
 648   }
 649
 650   SmallVector<StringRef, 4> MatchInfo;
 651   if (!Regex(RegExToMatch, Regex::Newline).match(Buffer, &MatchInfo))
 652     return make_error<FileCheckNotFoundError>();
 653
 654   // Successful regex match.
 655   assert(!MatchInfo.empty() && "Didn't get any match");
 656   StringRef FullMatch = MatchInfo[0];
 657
 658   // If this defines any string variables, remember their values.
 659   for (const auto &VariableDef : VariableDefs) {
 660     assert(VariableDef.second < MatchInfo.size() && "Internal paren error");
 661     Context->GlobalVariableTable[VariableDef.first] =
 662         MatchInfo[VariableDef.second];
 663   }
 664
 665   // If this defines any numeric variables, remember their values.
 666   for (const auto &NumericVariableDef : NumericVariableDefs) {
 667     const FileCheckNumericVariableMatch &NumericVariableMatch =
 668         NumericVariableDef.getValue();
 669     unsigned CaptureParenGroup = NumericVariableMatch.CaptureParenGroup;
 670     assert(CaptureParenGroup < MatchInfo.size() && "Internal paren error");
 671     FileCheckNumericVariable *DefinedNumericVariable =
 672         NumericVariableMatch.DefinedNumericVariable;
 673
 674     StringRef MatchedValue = MatchInfo[CaptureParenGroup];
 675     uint64_t Val;
 676     if (MatchedValue.getAsInteger(10, Val))
 677       return FileCheckErrorDiagnostic::get(SM, MatchedValue,
 678                                            "Unable to represent numeric value");
 679     DefinedNumericVariable->setValue(Val);
 680   }
 681
 682   // Like CHECK-NEXT, CHECK-EMPTY's match range is considered to start after
 683   // the required preceding newline, which is consumed by the pattern in the
 684   // case of CHECK-EMPTY but not CHECK-NEXT.
 685   size_t MatchStartSkip = CheckTy == Check::CheckEmpty;
 686   MatchLen = FullMatch.size() - MatchStartSkip;
 687   return FullMatch.data() - Buffer.data() + MatchStartSkip;
 688 }
 689
 690 unsigned FileCheckPattern::computeMatchDistance(StringRef Buffer) const {
 691   // Just compute the number of matching characters. For regular expressions, we
 692   // just compare against the regex itself and hope for the best.
 693   //
 694   // FIXME: One easy improvement here is have the regex lib generate a single
 695   // example regular expression which matches, and use that as the example
 696   // string.
 697   StringRef ExampleString(FixedStr);
 698   if (ExampleString.empty())
 699     ExampleString = RegExStr;
 700
 701   // Only compare up to the first line in the buffer, or the string size.
 702   StringRef BufferPrefix = Buffer.substr(0, ExampleString.size());
 703   BufferPrefix = BufferPrefix.split('\n').first;
 704   return BufferPrefix.edit_distance(ExampleString);
 705 }
 706
 707 void FileCheckPattern::printSubstitutions(const SourceMgr &SM, StringRef Buffer,
 708                                           SMRange MatchRange) const {
 709   // Print what we know about substitutions.
 710   if (!Substitutions.empty()) {
 711     for (const auto &Substitution : Substitutions) {
 712       SmallString<256> Msg;
 713       raw_svector_ostream OS(Msg);
 714       Expected<std::string> MatchedValue = Substitution->getResult();
 715
 716       // Substitution failed or is not known at match time, print the undefined
 717       // variables it uses.
 718       if (!MatchedValue) {
 719         bool UndefSeen = false;
 720         handleAllErrors(MatchedValue.takeError(),
 721                         [](const FileCheckNotFoundError &E) {},
 722                         // Handled in PrintNoMatch().
 723                         [](const FileCheckErrorDiagnostic &E) {},
 724                         [&](const FileCheckUndefVarError &E) {
 725                           if (!UndefSeen) {
 726                             OS << "uses undefined variable(s):";
 727                             UndefSeen = true;
 728                           }
 729                           OS << " ";
 730                           E.log(OS);
 731                         });
 732       } else {
 733         // Substitution succeeded. Print substituted value.
 734         OS << "with \"";
 735         OS.write_escaped(Substitution->getFromString()) << "\" equal to \"";
 736         OS.write_escaped(*MatchedValue) << "\"";
 737       }
 738
 739       if (MatchRange.isValid())
 740         SM.PrintMessage(MatchRange.Start, SourceMgr::DK_Note, OS.str(),
 741                         {MatchRange});
 742       else
 743         SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()),
 744                         SourceMgr::DK_Note, OS.str());
 745     }
 746   }
 747 }
 748
 749 static SMRange ProcessMatchResult(FileCheckDiag::MatchType MatchTy,
 750                                   const SourceMgr &SM, SMLoc Loc,
 751                                   Check::FileCheckType CheckTy,
 752                                   StringRef Buffer, size_t Pos, size_t Len,
 753                                   std::vector<FileCheckDiag> *Diags,
 754                                   bool AdjustPrevDiag = false) {
 755   SMLoc Start = SMLoc::getFromPointer(Buffer.data() + Pos);
 756   SMLoc End = SMLoc::getFromPointer(Buffer.data() + Pos + Len);
 757   SMRange Range(Start, End);
 758   if (Diags) {
 759     if (AdjustPrevDiag)
 760       Diags->rbegin()->MatchTy = MatchTy;
 761     else
 762       Diags->emplace_back(SM, CheckTy, Loc, MatchTy, Range);
 763   }
 764   return Range;
 765 }
 766
 767 void FileCheckPattern::printFuzzyMatch(
 768     const SourceMgr &SM, StringRef Buffer,
 769     std::vector<FileCheckDiag> *Diags) const {
 770   // Attempt to find the closest/best fuzzy match.  Usually an error happens
 771   // because some string in the output didn't exactly match. In these cases, we
 772   // would like to show the user a best guess at what "should have" matched, to
 773   // save them having to actually check the input manually.
 774   size_t NumLinesForward = 0;
 775   size_t Best = StringRef::npos;
 776   double BestQuality = 0;
 777
 778   // Use an arbitrary 4k limit on how far we will search.
 779   for (size_t i = 0, e = std::min(size_t(4096), Buffer.size()); i != e; ++i) {
 780     if (Buffer[i] == '\n')
 781       ++NumLinesForward;
 782
 783     // Patterns have leading whitespace stripped, so skip whitespace when
 784     // looking for something which looks like a pattern.
 785     if (Buffer[i] == ' ' || Buffer[i] == '\t')
 786       continue;
 787
 788     // Compute the "quality" of this match as an arbitrary combination of the
 789     // match distance and the number of lines skipped to get to this match.
 790     unsigned Distance = computeMatchDistance(Buffer.substr(i));
 791     double Quality = Distance + (NumLinesForward / 100.);
 792
 793     if (Quality < BestQuality || Best == StringRef::npos) {
 794       Best = i;
 795       BestQuality = Quality;
 796     }
 797   }
 798
 799   // Print the "possible intended match here" line if we found something
 800   // reasonable and not equal to what we showed in the "scanning from here"
 801   // line.
 802   if (Best && Best != StringRef::npos && BestQuality < 50) {
 803     SMRange MatchRange =
 804         ProcessMatchResult(FileCheckDiag::MatchFuzzy, SM, getLoc(),
 805                            getCheckTy(), Buffer, Best, 0, Diags);
 806     SM.PrintMessage(MatchRange.Start, SourceMgr::DK_Note,
 807                     "possible intended match here");
 808
 809     // FIXME: If we wanted to be really friendly we would show why the match
 810     // failed, as it can be hard to spot simple one character differences.
 811   }
 812 }
 813
 814 Expected<StringRef>
 815 FileCheckPatternContext::getPatternVarValue(StringRef VarName) {
 816   auto VarIter = GlobalVariableTable.find(VarName);
 817   if (VarIter == GlobalVariableTable.end())
 818     return make_error<FileCheckUndefVarError>(VarName);
 819
 820   return VarIter->second;
 821 }
 822
 823 template <class... Types>
 824 FileCheckNumericVariable *
 825 FileCheckPatternContext::makeNumericVariable(Types... args) {
 826   NumericVariables.push_back(
 827       llvm::make_unique<FileCheckNumericVariable>(args...));
 828   return NumericVariables.back().get();
 829 }
 830
 831 FileCheckSubstitution *
 832 FileCheckPatternContext::makeStringSubstitution(StringRef VarName,
 833                                                 size_t InsertIdx) {
 834   Substitutions.push_back(
 835       llvm::make_unique<FileCheckStringSubstitution>(this, VarName, InsertIdx));
 836   return Substitutions.back().get();
 837 }
 838
 839 FileCheckSubstitution *FileCheckPatternContext::makeNumericSubstitution(
 840     StringRef ExpressionStr,
 841     std::unique_ptr<FileCheckExpressionAST> ExpressionAST, size_t InsertIdx) {
 842   Substitutions.push_back(llvm::make_unique<FileCheckNumericSubstitution>(
 843       this, ExpressionStr, std::move(ExpressionAST), InsertIdx));
 844   return Substitutions.back().get();
 845 }
 846
 847 size_t FileCheckPattern::FindRegexVarEnd(StringRef Str, SourceMgr &SM) {
 848   // Offset keeps track of the current offset within the input Str
 849   size_t Offset = 0;
 850   // [...] Nesting depth
 851   size_t BracketDepth = 0;
 852
 853   while (!Str.empty()) {
 854     if (Str.startswith("]]") && BracketDepth == 0)
 855       return Offset;
 856     if (Str[0] == '\\') {
 857       // Backslash escapes the next char within regexes, so skip them both.
 858       Str = Str.substr(2);
 859       Offset += 2;
 860     } else {
 861       switch (Str[0]) {
 862       default:
 863         break;
 864       case '[':
 865         BracketDepth++;
 866         break;
 867       case ']':
 868         if (BracketDepth == 0) {
 869           SM.PrintMessage(SMLoc::getFromPointer(Str.data()),
 870                           SourceMgr::DK_Error,
 871                           "missing closing \"]\" for regex variable");
 872           exit(1);
 873         }
 874         BracketDepth--;
 875         break;
 876       }
 877       Str = Str.substr(1);
 878       Offset++;
 879     }
 880   }
 881
 882   return StringRef::npos;
 883 }
 884
 885 StringRef FileCheck::CanonicalizeFile(MemoryBuffer &MB,
 886                                       SmallVectorImpl<char> &OutputBuffer) {
 887   OutputBuffer.reserve(MB.getBufferSize());
 888
 889   for (const char *Ptr = MB.getBufferStart(), *End = MB.getBufferEnd();
 890        Ptr != End; ++Ptr) {
 891     // Eliminate trailing dosish \r.
 892     if (Ptr <= End - 2 && Ptr[0] == '\r' && Ptr[1] == '\n') {
 893       continue;
 894     }
 895
 896     // If current char is not a horizontal whitespace or if horizontal
 897     // whitespace canonicalization is disabled, dump it to output as is.
 898     if (Req.NoCanonicalizeWhiteSpace || (*Ptr != ' ' && *Ptr != '\t')) {
 899       OutputBuffer.push_back(*Ptr);
 900       continue;
 901     }
 902
 903     // Otherwise, add one space and advance over neighboring space.
 904     OutputBuffer.push_back(' ');
 905     while (Ptr + 1 != End && (Ptr[1] == ' ' || Ptr[1] == '\t'))
 906       ++Ptr;
 907   }
 908
 909   // Add a null byte and then return all but that byte.
 910   OutputBuffer.push_back('\0');
 911   return StringRef(OutputBuffer.data(), OutputBuffer.size() - 1);
 912 }
 913
 914 FileCheckDiag::FileCheckDiag(const SourceMgr &SM,
 915                              const Check::FileCheckType &CheckTy,
 916                              SMLoc CheckLoc, MatchType MatchTy,
 917                              SMRange InputRange)
 918     : CheckTy(CheckTy), MatchTy(MatchTy) {
 919   auto Start = SM.getLineAndColumn(InputRange.Start);
 920   auto End = SM.getLineAndColumn(InputRange.End);
 921   InputStartLine = Start.first;
 922   InputStartCol = Start.second;
 923   InputEndLine = End.first;
 924   InputEndCol = End.second;
 925   Start = SM.getLineAndColumn(CheckLoc);
 926   CheckLine = Start.first;
 927   CheckCol = Start.second;
 928 }
 929
 930 static bool IsPartOfWord(char c) {
 931   return (isalnum(c) || c == '-' || c == '_');
 932 }
 933
 934 Check::FileCheckType &Check::FileCheckType::setCount(int C) {
 935   assert(Count > 0 && "zero and negative counts are not supported");
 936   assert((C == 1 || Kind == CheckPlain) &&
 937          "count supported only for plain CHECK directives");
 938   Count = C;
 939   return *this;
 940 }
 941
 942 std::string Check::FileCheckType::getDescription(StringRef Prefix) const {
 943   switch (Kind) {
 944   case Check::CheckNone:
 945     return "invalid";
 946   case Check::CheckPlain:
 947     if (Count > 1)
 948       return Prefix.str() + "-COUNT";
 949     return Prefix;
 950   case Check::CheckNext:
 951     return Prefix.str() + "-NEXT";
 952   case Check::CheckSame:
 953     return Prefix.str() + "-SAME";
 954   case Check::CheckNot:
 955     return Prefix.str() + "-NOT";
 956   case Check::CheckDAG:
 957     return Prefix.str() + "-DAG";
 958   case Check::CheckLabel:
 959     return Prefix.str() + "-LABEL";
 960   case Check::CheckEmpty:
 961     return Prefix.str() + "-EMPTY";
 962   case Check::CheckEOF:
 963     return "implicit EOF";
 964   case Check::CheckBadNot:
 965     return "bad NOT";
 966   case Check::CheckBadCount:
 967     return "bad COUNT";
 968   }
 969   llvm_unreachable("unknown FileCheckType");
 970 }
 971
 972 static std::pair<Check::FileCheckType, StringRef>
 973 FindCheckType(StringRef Buffer, StringRef Prefix) {
 974   if (Buffer.size() <= Prefix.size())
 975     return {Check::CheckNone, StringRef()};
 976
 977   char NextChar = Buffer[Prefix.size()];
 978
 979   StringRef Rest = Buffer.drop_front(Prefix.size() + 1);
 980   // Verify that the : is present after the prefix.
 981   if (NextChar == ':')
 982     return {Check::CheckPlain, Rest};
 983
 984   if (NextChar != '-')
 985     return {Check::CheckNone, StringRef()};
 986
 987   if (Rest.consume_front("COUNT-")) {
 988     int64_t Count;
 989     if (Rest.consumeInteger(10, Count))
 990       // Error happened in parsing integer.
 991       return {Check::CheckBadCount, Rest};
 992     if (Count <= 0 || Count > INT32_MAX)
 993       return {Check::CheckBadCount, Rest};
 994     if (!Rest.consume_front(":"))
 995       return {Check::CheckBadCount, Rest};
 996     return {Check::FileCheckType(Check::CheckPlain).setCount(Count), Rest};
 997   }
 998
 999   if (Rest.consume_front("NEXT:"))
1000     return {Check::CheckNext, Rest};
1001
1002   if (Rest.consume_front("SAME:"))
1003     return {Check::CheckSame, Rest};
1004
1005   if (Rest.consume_front("NOT:"))
1006     return {Check::CheckNot, Rest};
1007
1008   if (Rest.consume_front("DAG:"))
1009     return {Check::CheckDAG, Rest};
1010
1011   if (Rest.consume_front("LABEL:"))
1012     return {Check::CheckLabel, Rest};
1013
1014   if (Rest.consume_front("EMPTY:"))
1015     return {Check::CheckEmpty, Rest};
1016
1017   // You can't combine -NOT with another suffix.
1018   if (Rest.startswith("DAG-NOT:") || Rest.startswith("NOT-DAG:") ||
1019       Rest.startswith("NEXT-NOT:") || Rest.startswith("NOT-NEXT:") ||
1020       Rest.startswith("SAME-NOT:") || Rest.startswith("NOT-SAME:") ||
1021       Rest.startswith("EMPTY-NOT:") || Rest.startswith("NOT-EMPTY:"))
1022     return {Check::CheckBadNot, Rest};
1023
1024   return {Check::CheckNone, Rest};
1025 }
1026
1027 // From the given position, find the next character after the word.
1028 static size_t SkipWord(StringRef Str, size_t Loc) {
1029   while (Loc < Str.size() && IsPartOfWord(Str[Loc]))
1030     ++Loc;
1031   return Loc;
1032 }
1033
1034 /// Searches the buffer for the first prefix in the prefix regular expression.
1035 ///
1036 /// This searches the buffer using the provided regular expression, however it
1037 /// enforces constraints beyond that:
1038 /// 1) The found prefix must not be a suffix of something that looks like
1039 ///    a valid prefix.
1040 /// 2) The found prefix must be followed by a valid check type suffix using \c
1041 ///    FindCheckType above.
1042 ///
1043 /// \returns a pair of StringRefs into the Buffer, which combines:
1044 ///   - the first match of the regular expression to satisfy these two is
1045 ///   returned,
1046 ///     otherwise an empty StringRef is returned to indicate failure.
1047 ///   - buffer rewound to the location right after parsed suffix, for parsing
1048 ///     to continue from
1049 ///
1050 /// If this routine returns a valid prefix, it will also shrink \p Buffer to
1051 /// start at the beginning of the returned prefix, increment \p LineNumber for
1052 /// each new line consumed from \p Buffer, and set \p CheckTy to the type of
1053 /// check found by examining the suffix.
1054 ///
1055 /// If no valid prefix is found, the state of Buffer, LineNumber, and CheckTy
1056 /// is unspecified.
1057 static std::pair<StringRef, StringRef>
1058 FindFirstMatchingPrefix(Regex &PrefixRE, StringRef &Buffer,
1059                         unsigned &LineNumber, Check::FileCheckType &CheckTy) {
1060   SmallVector<StringRef, 2> Matches;
1061
1062   while (!Buffer.empty()) {
1063     // Find the first (longest) match using the RE.
1064     if (!PrefixRE.match(Buffer, &Matches))
1065       // No match at all, bail.
1066       return {StringRef(), StringRef()};
1067
1068     StringRef Prefix = Matches[0];
1069     Matches.clear();
1070
1071     assert(Prefix.data() >= Buffer.data() &&
1072            Prefix.data() < Buffer.data() + Buffer.size() &&
1073            "Prefix doesn't start inside of buffer!");
1074     size_t Loc = Prefix.data() - Buffer.data();
1075     StringRef Skipped = Buffer.substr(0, Loc);
1076     Buffer = Buffer.drop_front(Loc);
1077     LineNumber += Skipped.count('\n');
1078
1079     // Check that the matched prefix isn't a suffix of some other check-like
1080     // word.
1081     // FIXME: This is a very ad-hoc check. it would be better handled in some
1082     // other way. Among other things it seems hard to distinguish between
1083     // intentional and unintentional uses of this feature.
1084     if (Skipped.empty() || !IsPartOfWord(Skipped.back())) {
1085       // Now extract the type.
1086       StringRef AfterSuffix;
1087       std::tie(CheckTy, AfterSuffix) = FindCheckType(Buffer, Prefix);
1088
1089       // If we've found a valid check type for this prefix, we're done.
1090       if (CheckTy != Check::CheckNone)
1091         return {Prefix, AfterSuffix};
1092     }
1093
1094     // If we didn't successfully find a prefix, we need to skip this invalid
1095     // prefix and continue scanning. We directly skip the prefix that was
1096     // matched and any additional parts of that check-like word.
1097     Buffer = Buffer.drop_front(SkipWord(Buffer, Prefix.size()));
1098   }
1099
1100   // We ran out of buffer while skipping partial matches so give up.
1101   return {StringRef(), StringRef()};
1102 }
1103
1104 void FileCheckPatternContext::createLineVariable() {
1105   assert(!LineVariable && "@LINE pseudo numeric variable already created");
1106   StringRef LineName = "@LINE";
1107   LineVariable = makeNumericVariable(LineName);
1108   GlobalNumericVariableTable[LineName] = LineVariable;
1109 }
1110
1111 bool FileCheck::ReadCheckFile(SourceMgr &SM, StringRef Buffer, Regex &PrefixRE,
1112                               std::vector<FileCheckString> &CheckStrings) {
1113   Error DefineError =
1114       PatternContext.defineCmdlineVariables(Req.GlobalDefines, SM);
1115   if (DefineError) {
1116     logAllUnhandledErrors(std::move(DefineError), errs());
1117     return true;
1118   }
1119
1120   PatternContext.createLineVariable();
1121
1122   std::vector<FileCheckPattern> ImplicitNegativeChecks;
1123   for (const auto &PatternString : Req.ImplicitCheckNot) {
1124     // Create a buffer with fake command line content in order to display the
1125     // command line option responsible for the specific implicit CHECK-NOT.
1126     std::string Prefix = "-implicit-check-not='";
1127     std::string Suffix = "'";
1128     std::unique_ptr<MemoryBuffer> CmdLine = MemoryBuffer::getMemBufferCopy(
1129         Prefix + PatternString + Suffix, "command line");
1130
1131     StringRef PatternInBuffer =
1132         CmdLine->getBuffer().substr(Prefix.size(), PatternString.size());
1133     SM.AddNewSourceBuffer(std::move(CmdLine), SMLoc());
1134
1135     ImplicitNegativeChecks.push_back(
1136         FileCheckPattern(Check::CheckNot, &PatternContext));
1137     ImplicitNegativeChecks.back().parsePattern(PatternInBuffer,
1138                                                "IMPLICIT-CHECK", SM, Req);
1139   }
1140
1141   std::vector<FileCheckPattern> DagNotMatches = ImplicitNegativeChecks;
1142
1143   // LineNumber keeps track of the line on which CheckPrefix instances are
1144   // found.
1145   unsigned LineNumber = 1;
1146
1147   while (1) {
1148     Check::FileCheckType CheckTy;
1149
1150     // See if a prefix occurs in the memory buffer.
1151     StringRef UsedPrefix;
1152     StringRef AfterSuffix;
1153     std::tie(UsedPrefix, AfterSuffix) =
1154         FindFirstMatchingPrefix(PrefixRE, Buffer, LineNumber, CheckTy);
1155     if (UsedPrefix.empty())
1156       break;
1157     assert(UsedPrefix.data() == Buffer.data() &&
1158            "Failed to move Buffer's start forward, or pointed prefix outside "
1159            "of the buffer!");
1160     assert(AfterSuffix.data() >= Buffer.data() &&
1161            AfterSuffix.data() < Buffer.data() + Buffer.size() &&
1162            "Parsing after suffix doesn't start inside of buffer!");
1163
1164     // Location to use for error messages.
1165     const char *UsedPrefixStart = UsedPrefix.data();
1166
1167     // Skip the buffer to the end of parsed suffix (or just prefix, if no good
1168     // suffix was processed).
1169     Buffer = AfterSuffix.empty() ? Buffer.drop_front(UsedPrefix.size())
1170                                  : AfterSuffix;
1171
1172     // Complain about useful-looking but unsupported suffixes.
1173     if (CheckTy == Check::CheckBadNot) {
1174       SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Error,
1175                       "unsupported -NOT combo on prefix '" + UsedPrefix + "'");
1176       return true;
1177     }
1178
1179     // Complain about invalid count specification.
1180     if (CheckTy == Check::CheckBadCount) {
1181       SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Error,
1182                       "invalid count in -COUNT specification on prefix '" +
1183                           UsedPrefix + "'");
1184       return true;
1185     }
1186
1187     // Okay, we found the prefix, yay. Remember the rest of the line, but ignore
1188     // leading whitespace.
1189     if (!(Req.NoCanonicalizeWhiteSpace && Req.MatchFullLines))
1190       Buffer = Buffer.substr(Buffer.find_first_not_of(" \t"));
1191
1192     // Scan ahead to the end of line.
1193     size_t EOL = Buffer.find_first_of("\n\r");
1194
1195     // Remember the location of the start of the pattern, for diagnostics.
1196     SMLoc PatternLoc = SMLoc::getFromPointer(Buffer.data());
1197
1198     // Parse the pattern.
1199     FileCheckPattern P(CheckTy, &PatternContext, LineNumber);
1200     if (P.parsePattern(Buffer.substr(0, EOL), UsedPrefix, SM, Req))
1201       return true;
1202
1203     // Verify that CHECK-LABEL lines do not define or use variables
1204     if ((CheckTy == Check::CheckLabel) && P.hasVariable()) {
1205       SM.PrintMessage(
1206           SMLoc::getFromPointer(UsedPrefixStart), SourceMgr::DK_Error,
1207           "found '" + UsedPrefix + "-LABEL:'"
1208                                    " with variable definition or use");
1209       return true;
1210     }
1211
1212     Buffer = Buffer.substr(EOL);
1213
1214     // Verify that CHECK-NEXT/SAME/EMPTY lines have at least one CHECK line before them.
1215     if ((CheckTy == Check::CheckNext || CheckTy == Check::CheckSame ||
1216          CheckTy == Check::CheckEmpty) &&
1217         CheckStrings.empty()) {
1218       StringRef Type = CheckTy == Check::CheckNext
1219                            ? "NEXT"
1220                            : CheckTy == Check::CheckEmpty ? "EMPTY" : "SAME";
1221       SM.PrintMessage(SMLoc::getFromPointer(UsedPrefixStart),
1222                       SourceMgr::DK_Error,
1223                       "found '" + UsedPrefix + "-" + Type +
1224                           "' without previous '" + UsedPrefix + ": line");
1225       return true;
1226     }
1227
1228     // Handle CHECK-DAG/-NOT.
1229     if (CheckTy == Check::CheckDAG || CheckTy == Check::CheckNot) {
1230       DagNotMatches.push_back(P);
1231       continue;
1232     }
1233
1234     // Okay, add the string we captured to the output vector and move on.
1235     CheckStrings.emplace_back(P, UsedPrefix, PatternLoc);
1236     std::swap(DagNotMatches, CheckStrings.back().DagNotStrings);
1237     DagNotMatches = ImplicitNegativeChecks;
1238   }
1239
1240   // Add an EOF pattern for any trailing CHECK-DAG/-NOTs, and use the first
1241   // prefix as a filler for the error message.
1242   if (!DagNotMatches.empty()) {
1243     CheckStrings.emplace_back(
1244         FileCheckPattern(Check::CheckEOF, &PatternContext, LineNumber + 1),
1245         *Req.CheckPrefixes.begin(), SMLoc::getFromPointer(Buffer.data()));
1246     std::swap(DagNotMatches, CheckStrings.back().DagNotStrings);
1247   }
1248
1249   if (CheckStrings.empty()) {
1250     errs() << "error: no check strings found with prefix"
1251            << (Req.CheckPrefixes.size() > 1 ? "es " : " ");
1252     auto I = Req.CheckPrefixes.begin();
1253     auto E = Req.CheckPrefixes.end();
1254     if (I != E) {
1255       errs() << "\'" << *I << ":'";
1256       ++I;
1257     }
1258     for (; I != E; ++I)
1259       errs() << ", \'" << *I << ":'";
1260
1261     errs() << '\n';
1262     return true;
1263   }
1264
1265   return false;
1266 }
1267
1268 static void PrintMatch(bool ExpectedMatch, const SourceMgr &SM,
1269                        StringRef Prefix, SMLoc Loc, const FileCheckPattern &Pat,
1270                        int MatchedCount, StringRef Buffer, size_t MatchPos,
1271                        size_t MatchLen, const FileCheckRequest &Req,
1272                        std::vector<FileCheckDiag> *Diags) {
1273   bool PrintDiag = true;
1274   if (ExpectedMatch) {
1275     if (!Req.Verbose)
1276       return;
1277     if (!Req.VerboseVerbose && Pat.getCheckTy() == Check::CheckEOF)
1278       return;
1279     // Due to their verbosity, we don't print verbose diagnostics here if we're
1280     // gathering them for a different rendering, but we always print other
1281     // diagnostics.
1282     PrintDiag = !Diags;
1283   }
1284   SMRange MatchRange = ProcessMatchResult(
1285       ExpectedMatch ? FileCheckDiag::MatchFoundAndExpected
1286                     : FileCheckDiag::MatchFoundButExcluded,
1287       SM, Loc, Pat.getCheckTy(), Buffer, MatchPos, MatchLen, Diags);
1288   if (!PrintDiag)
1289     return;
1290
1291   std::string Message = formatv("{0}: {1} string found in input",
1292                                 Pat.getCheckTy().getDescription(Prefix),
1293                                 (ExpectedMatch ? "expected" : "excluded"))
1294                             .str();
1295   if (Pat.getCount() > 1)
1296     Message += formatv(" ({0} out of {1})", MatchedCount, Pat.getCount()).str();
1297
1298   SM.PrintMessage(
1299       Loc, ExpectedMatch ? SourceMgr::DK_Remark : SourceMgr::DK_Error, Message);
1300   SM.PrintMessage(MatchRange.Start, SourceMgr::DK_Note, "found here",
1301                   {MatchRange});
1302   Pat.printSubstitutions(SM, Buffer, MatchRange);
1303 }
1304
1305 static void PrintMatch(bool ExpectedMatch, const SourceMgr &SM,
1306                        const FileCheckString &CheckStr, int MatchedCount,
1307                        StringRef Buffer, size_t MatchPos, size_t MatchLen,
1308                        FileCheckRequest &Req,
1309                        std::vector<FileCheckDiag> *Diags) {
1310   PrintMatch(ExpectedMatch, SM, CheckStr.Prefix, CheckStr.Loc, CheckStr.Pat,
1311              MatchedCount, Buffer, MatchPos, MatchLen, Req, Diags);
1312 }
1313
1314 static void PrintNoMatch(bool ExpectedMatch, const SourceMgr &SM,
1315                          StringRef Prefix, SMLoc Loc,
1316                          const FileCheckPattern &Pat, int MatchedCount,
1317                          StringRef Buffer, bool VerboseVerbose,
1318                          std::vector<FileCheckDiag> *Diags, Error MatchErrors) {
1319   assert(MatchErrors && "Called on successful match");
1320   bool PrintDiag = true;
1321   if (!ExpectedMatch) {
1322     if (!VerboseVerbose) {
1323       consumeError(std::move(MatchErrors));
1324       return;
1325     }
1326     // Due to their verbosity, we don't print verbose diagnostics here if we're
1327     // gathering them for a different rendering, but we always print other
1328     // diagnostics.
1329     PrintDiag = !Diags;
1330   }
1331
1332   // If the current position is at the end of a line, advance to the start of
1333   // the next line.
1334   Buffer = Buffer.substr(Buffer.find_first_not_of(" \t\n\r"));
1335   SMRange SearchRange = ProcessMatchResult(
1336       ExpectedMatch ? FileCheckDiag::MatchNoneButExpected
1337                     : FileCheckDiag::MatchNoneAndExcluded,
1338       SM, Loc, Pat.getCheckTy(), Buffer, 0, Buffer.size(), Diags);
1339   if (!PrintDiag) {
1340     consumeError(std::move(MatchErrors));
1341     return;
1342   }
1343
1344   MatchErrors =
1345       handleErrors(std::move(MatchErrors),
1346                    [](const FileCheckErrorDiagnostic &E) { E.log(errs()); });
1347
1348   // No problem matching the string per se.
1349   if (!MatchErrors)
1350     return;
1351   consumeError(std::move(MatchErrors));
1352
1353   // Print "not found" diagnostic.
1354   std::string Message = formatv("{0}: {1} string not found in input",
1355                                 Pat.getCheckTy().getDescription(Prefix),
1356                                 (ExpectedMatch ? "expected" : "excluded"))
1357                             .str();
1358   if (Pat.getCount() > 1)
1359     Message += formatv(" ({0} out of {1})", MatchedCount, Pat.getCount()).str();
1360   SM.PrintMessage(
1361       Loc, ExpectedMatch ? SourceMgr::DK_Error : SourceMgr::DK_Remark, Message);
1362
1363   // Print the "scanning from here" line.
1364   SM.PrintMessage(SearchRange.Start, SourceMgr::DK_Note, "scanning from here");
1365
1366   // Allow the pattern to print additional information if desired.
1367   Pat.printSubstitutions(SM, Buffer);
1368
1369   if (ExpectedMatch)
1370     Pat.printFuzzyMatch(SM, Buffer, Diags);
1371 }
1372
1373 static void PrintNoMatch(bool ExpectedMatch, const SourceMgr &SM,
1374                          const FileCheckString &CheckStr, int MatchedCount,
1375                          StringRef Buffer, bool VerboseVerbose,
1376                          std::vector<FileCheckDiag> *Diags, Error MatchErrors) {
1377   PrintNoMatch(ExpectedMatch, SM, CheckStr.Prefix, CheckStr.Loc, CheckStr.Pat,
1378                MatchedCount, Buffer, VerboseVerbose, Diags,
1379                std::move(MatchErrors));
1380 }
1381
1382 /// Counts the number of newlines in the specified range.
1383 static unsigned CountNumNewlinesBetween(StringRef Range,
1384                                         const char *&FirstNewLine) {
1385   unsigned NumNewLines = 0;
1386   while (1) {
1387     // Scan for newline.
1388     Range = Range.substr(Range.find_first_of("\n\r"));
1389     if (Range.empty())
1390       return NumNewLines;
1391
1392     ++NumNewLines;
1393
1394     // Handle \n\r and \r\n as a single newline.
1395     if (Range.size() > 1 && (Range[1] == '\n' || Range[1] == '\r') &&
1396         (Range[0] != Range[1]))
1397       Range = Range.substr(1);
1398     Range = Range.substr(1);
1399
1400     if (NumNewLines == 1)
1401       FirstNewLine = Range.begin();
1402   }
1403 }
1404
1405 size_t FileCheckString::Check(const SourceMgr &SM, StringRef Buffer,
1406                               bool IsLabelScanMode, size_t &MatchLen,
1407                               FileCheckRequest &Req,
1408                               std::vector<FileCheckDiag> *Diags) const {
1409   size_t LastPos = 0;
1410   std::vector<const FileCheckPattern *> NotStrings;
1411
1412   // IsLabelScanMode is true when we are scanning forward to find CHECK-LABEL
1413   // bounds; we have not processed variable definitions within the bounded block
1414   // yet so cannot handle any final CHECK-DAG yet; this is handled when going
1415   // over the block again (including the last CHECK-LABEL) in normal mode.
1416   if (!IsLabelScanMode) {
1417     // Match "dag strings" (with mixed "not strings" if any).
1418     LastPos = CheckDag(SM, Buffer, NotStrings, Req, Diags);
1419     if (LastPos == StringRef::npos)
1420       return StringRef::npos;
1421   }
1422
1423   // Match itself from the last position after matching CHECK-DAG.
1424   size_t LastMatchEnd = LastPos;
1425   size_t FirstMatchPos = 0;
1426   // Go match the pattern Count times. Majority of patterns only match with
1427   // count 1 though.
1428   assert(Pat.getCount() != 0 && "pattern count can not be zero");
1429   for (int i = 1; i <= Pat.getCount(); i++) {
1430     StringRef MatchBuffer = Buffer.substr(LastMatchEnd);
1431     size_t CurrentMatchLen;
1432     // get a match at current start point
1433     Expected<size_t> MatchResult = Pat.match(MatchBuffer, CurrentMatchLen, SM);
1434
1435     // report
1436     if (!MatchResult) {
1437       PrintNoMatch(true, SM, *this, i, MatchBuffer, Req.VerboseVerbose, Diags,
1438                    MatchResult.takeError());
1439       return StringRef::npos;
1440     }
1441     size_t MatchPos = *MatchResult;
1442     PrintMatch(true, SM, *this, i, MatchBuffer, MatchPos, CurrentMatchLen, Req,
1443                Diags);
1444     if (i == 1)
1445       FirstMatchPos = LastPos + MatchPos;
1446
1447     // move start point after the match
1448     LastMatchEnd += MatchPos + CurrentMatchLen;
1449   }
1450   // Full match len counts from first match pos.
1451   MatchLen = LastMatchEnd - FirstMatchPos;
1452
1453   // Similar to the above, in "label-scan mode" we can't yet handle CHECK-NEXT
1454   // or CHECK-NOT
1455   if (!IsLabelScanMode) {
1456     size_t MatchPos = FirstMatchPos - LastPos;
1457     StringRef MatchBuffer = Buffer.substr(LastPos);
1458     StringRef SkippedRegion = Buffer.substr(LastPos, MatchPos);
1459
1460     // If this check is a "CHECK-NEXT", verify that the previous match was on
1461     // the previous line (i.e. that there is one newline between them).
1462     if (CheckNext(SM, SkippedRegion)) {
1463       ProcessMatchResult(FileCheckDiag::MatchFoundButWrongLine, SM, Loc,
1464                          Pat.getCheckTy(), MatchBuffer, MatchPos, MatchLen,
1465                          Diags, Req.Verbose);
1466       return StringRef::npos;
1467     }
1468
1469     // If this check is a "CHECK-SAME", verify that the previous match was on
1470     // the same line (i.e. that there is no newline between them).
1471     if (CheckSame(SM, SkippedRegion)) {
1472       ProcessMatchResult(FileCheckDiag::MatchFoundButWrongLine, SM, Loc,
1473                          Pat.getCheckTy(), MatchBuffer, MatchPos, MatchLen,
1474                          Diags, Req.Verbose);
1475       return StringRef::npos;
1476     }
1477
1478     // If this match had "not strings", verify that they don't exist in the
1479     // skipped region.
1480     if (CheckNot(SM, SkippedRegion, NotStrings, Req, Diags))
1481       return StringRef::npos;
1482   }
1483
1484   return FirstMatchPos;
1485 }
1486
1487 bool FileCheckString::CheckNext(const SourceMgr &SM, StringRef Buffer) const {
1488   if (Pat.getCheckTy() != Check::CheckNext &&
1489       Pat.getCheckTy() != Check::CheckEmpty)
1490     return false;
1491
1492   Twine CheckName =
1493       Prefix +
1494       Twine(Pat.getCheckTy() == Check::CheckEmpty ? "-EMPTY" : "-NEXT");
1495
1496   // Count the number of newlines between the previous match and this one.
1497   const char *FirstNewLine = nullptr;
1498   unsigned NumNewLines = CountNumNewlinesBetween(Buffer, FirstNewLine);
1499
1500   if (NumNewLines == 0) {
1501     SM.PrintMessage(Loc, SourceMgr::DK_Error,
1502                     CheckName + ": is on the same line as previous match");
1503     SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), SourceMgr::DK_Note,
1504                     "'next' match was here");
1505     SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,
1506                     "previous match ended here");
1507     return true;
1508   }
1509
1510   if (NumNewLines != 1) {
1511     SM.PrintMessage(Loc, SourceMgr::DK_Error,
1512                     CheckName +
1513                         ": is not on the line after the previous match");
1514     SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), SourceMgr::DK_Note,
1515                     "'next' match was here");
1516     SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,
1517                     "previous match ended here");
1518     SM.PrintMessage(SMLoc::getFromPointer(FirstNewLine), SourceMgr::DK_Note,
1519                     "non-matching line after previous match is here");
1520     return true;
1521   }
1522
1523   return false;
1524 }
1525
1526 bool FileCheckString::CheckSame(const SourceMgr &SM, StringRef Buffer) const {
1527   if (Pat.getCheckTy() != Check::CheckSame)
1528     return false;
1529
1530   // Count the number of newlines between the previous match and this one.
1531   const char *FirstNewLine = nullptr;
1532   unsigned NumNewLines = CountNumNewlinesBetween(Buffer, FirstNewLine);
1533
1534   if (NumNewLines != 0) {
1535     SM.PrintMessage(Loc, SourceMgr::DK_Error,
1536                     Prefix +
1537                         "-SAME: is not on the same line as the previous match");
1538     SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), SourceMgr::DK_Note,
1539                     "'next' match was here");
1540     SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,
1541                     "previous match ended here");
1542     return true;
1543   }
1544
1545   return false;
1546 }
1547
1548 bool FileCheckString::CheckNot(
1549     const SourceMgr &SM, StringRef Buffer,
1550     const std::vector<const FileCheckPattern *> &NotStrings,
1551     const FileCheckRequest &Req, std::vector<FileCheckDiag> *Diags) const {
1552   for (const FileCheckPattern *Pat : NotStrings) {
1553     assert((Pat->getCheckTy() == Check::CheckNot) && "Expect CHECK-NOT!");
1554
1555     size_t MatchLen = 0;
1556     Expected<size_t> MatchResult = Pat->match(Buffer, MatchLen, SM);
1557
1558     if (!MatchResult) {
1559       PrintNoMatch(false, SM, Prefix, Pat->getLoc(), *Pat, 1, Buffer,
1560                    Req.VerboseVerbose, Diags, MatchResult.takeError());
1561       continue;
1562     }
1563     size_t Pos = *MatchResult;
1564
1565     PrintMatch(false, SM, Prefix, Pat->getLoc(), *Pat, 1, Buffer, Pos, MatchLen,
1566                Req, Diags);
1567
1568     return true;
1569   }
1570
1571   return false;
1572 }
1573
1574 size_t
1575 FileCheckString::CheckDag(const SourceMgr &SM, StringRef Buffer,
1576                           std::vector<const FileCheckPattern *> &NotStrings,
1577                           const FileCheckRequest &Req,
1578                           std::vector<FileCheckDiag> *Diags) const {
1579   if (DagNotStrings.empty())
1580     return 0;
1581
1582   // The start of the search range.
1583   size_t StartPos = 0;
1584
1585   struct MatchRange {
1586     size_t Pos;
1587     size_t End;
1588   };
1589   // A sorted list of ranges for non-overlapping CHECK-DAG matches.  Match
1590   // ranges are erased from this list once they are no longer in the search
1591   // range.
1592   std::list<MatchRange> MatchRanges;
1593
1594   // We need PatItr and PatEnd later for detecting the end of a CHECK-DAG
1595   // group, so we don't use a range-based for loop here.
1596   for (auto PatItr = DagNotStrings.begin(), PatEnd = DagNotStrings.end();
1597        PatItr != PatEnd; ++PatItr) {
1598     const FileCheckPattern &Pat = *PatItr;
1599     assert((Pat.getCheckTy() == Check::CheckDAG ||
1600             Pat.getCheckTy() == Check::CheckNot) &&
1601            "Invalid CHECK-DAG or CHECK-NOT!");
1602
1603     if (Pat.getCheckTy() == Check::CheckNot) {
1604       NotStrings.push_back(&Pat);
1605       continue;
1606     }
1607
1608     assert((Pat.getCheckTy() == Check::CheckDAG) && "Expect CHECK-DAG!");
1609
1610     // CHECK-DAG always matches from the start.
1611     size_t MatchLen = 0, MatchPos = StartPos;
1612
1613     // Search for a match that doesn't overlap a previous match in this
1614     // CHECK-DAG group.
1615     for (auto MI = MatchRanges.begin(), ME = MatchRanges.end(); true; ++MI) {
1616       StringRef MatchBuffer = Buffer.substr(MatchPos);
1617       Expected<size_t> MatchResult = Pat.match(MatchBuffer, MatchLen, SM);
1618       // With a group of CHECK-DAGs, a single mismatching means the match on
1619       // that group of CHECK-DAGs fails immediately.
1620       if (!MatchResult) {
1621         PrintNoMatch(true, SM, Prefix, Pat.getLoc(), Pat, 1, MatchBuffer,
1622                      Req.VerboseVerbose, Diags, MatchResult.takeError());
1623         return StringRef::npos;
1624       }
1625       size_t MatchPosBuf = *MatchResult;
1626       // Re-calc it as the offset relative to the start of the original string.
1627       MatchPos += MatchPosBuf;
1628       if (Req.VerboseVerbose)
1629         PrintMatch(true, SM, Prefix, Pat.getLoc(), Pat, 1, Buffer, MatchPos,
1630                    MatchLen, Req, Diags);
1631       MatchRange M{MatchPos, MatchPos + MatchLen};
1632       if (Req.AllowDeprecatedDagOverlap) {
1633         // We don't need to track all matches in this mode, so we just maintain
1634         // one match range that encompasses the current CHECK-DAG group's
1635         // matches.
1636         if (MatchRanges.empty())
1637           MatchRanges.insert(MatchRanges.end(), M);
1638         else {
1639           auto Block = MatchRanges.begin();
1640           Block->Pos = std::min(Block->Pos, M.Pos);
1641           Block->End = std::max(Block->End, M.End);
1642         }
1643         break;
1644       }
1645       // Iterate previous matches until overlapping match or insertion point.
1646       bool Overlap = false;
1647       for (; MI != ME; ++MI) {
1648         if (M.Pos < MI->End) {
1649           // !Overlap => New match has no overlap and is before this old match.
1650           // Overlap => New match overlaps this old match.
1651           Overlap = MI->Pos < M.End;
1652           break;
1653         }
1654       }
1655       if (!Overlap) {
1656         // Insert non-overlapping match into list.
1657         MatchRanges.insert(MI, M);
1658         break;
1659       }
1660       if (Req.VerboseVerbose) {
1661         // Due to their verbosity, we don't print verbose diagnostics here if
1662         // we're gathering them for a different rendering, but we always print
1663         // other diagnostics.
1664         if (!Diags) {
1665           SMLoc OldStart = SMLoc::getFromPointer(Buffer.data() + MI->Pos);
1666           SMLoc OldEnd = SMLoc::getFromPointer(Buffer.data() + MI->End);
1667           SMRange OldRange(OldStart, OldEnd);
1668           SM.PrintMessage(OldStart, SourceMgr::DK_Note,
1669                           "match discarded, overlaps earlier DAG match here",
1670                           {OldRange});
1671         } else
1672           Diags->rbegin()->MatchTy = FileCheckDiag::MatchFoundButDiscarded;
1673       }
1674       MatchPos = MI->End;
1675     }
1676     if (!Req.VerboseVerbose)
1677       PrintMatch(true, SM, Prefix, Pat.getLoc(), Pat, 1, Buffer, MatchPos,
1678                  MatchLen, Req, Diags);
1679
1680     // Handle the end of a CHECK-DAG group.
1681     if (std::next(PatItr) == PatEnd ||
1682         std::next(PatItr)->getCheckTy() == Check::CheckNot) {
1683       if (!NotStrings.empty()) {
1684         // If there are CHECK-NOTs between two CHECK-DAGs or from CHECK to
1685         // CHECK-DAG, verify that there are no 'not' strings occurred in that
1686         // region.
1687         StringRef SkippedRegion =
1688             Buffer.slice(StartPos, MatchRanges.begin()->Pos);
1689         if (CheckNot(SM, SkippedRegion, NotStrings, Req, Diags))
1690           return StringRef::npos;
1691         // Clear "not strings".
1692         NotStrings.clear();
1693       }
1694       // All subsequent CHECK-DAGs and CHECK-NOTs should be matched from the
1695       // end of this CHECK-DAG group's match range.
1696       StartPos = MatchRanges.rbegin()->End;
1697       // Don't waste time checking for (impossible) overlaps before that.
1698       MatchRanges.clear();
1699     }
1700   }
1701
1702   return StartPos;
1703 }
1704
1705 // A check prefix must contain only alphanumeric, hyphens and underscores.
1706 static bool ValidateCheckPrefix(StringRef CheckPrefix) {
1707   Regex Validator("^[a-zA-Z0-9_-]*$");
1708   return Validator.match(CheckPrefix);
1709 }
1710
1711 bool FileCheck::ValidateCheckPrefixes() {
1712   StringSet<> PrefixSet;
1713
1714   for (StringRef Prefix : Req.CheckPrefixes) {
1715     // Reject empty prefixes.
1716     if (Prefix == "")
1717       return false;
1718
1719     if (!PrefixSet.insert(Prefix).second)
1720       return false;
1721
1722     if (!ValidateCheckPrefix(Prefix))
1723       return false;
1724   }
1725
1726   return true;
1727 }
1728
1729 Regex FileCheck::buildCheckPrefixRegex() {
1730   // I don't think there's a way to specify an initial value for cl::list,
1731   // so if nothing was specified, add the default
1732   if (Req.CheckPrefixes.empty())
1733     Req.CheckPrefixes.push_back("CHECK");
1734
1735   // We already validated the contents of CheckPrefixes so just concatenate
1736   // them as alternatives.
1737   SmallString<32> PrefixRegexStr;
1738   for (StringRef Prefix : Req.CheckPrefixes) {
1739     if (Prefix != Req.CheckPrefixes.front())
1740       PrefixRegexStr.push_back('|');
1741
1742     PrefixRegexStr.append(Prefix);
1743   }
1744
1745   return Regex(PrefixRegexStr);
1746 }
1747
1748 Error FileCheckPatternContext::defineCmdlineVariables(
1749     std::vector<std::string> &CmdlineDefines, SourceMgr &SM) {
1750   assert(GlobalVariableTable.empty() && GlobalNumericVariableTable.empty() &&
1751          "Overriding defined variable with command-line variable definitions");
1752
1753   if (CmdlineDefines.empty())
1754     return Error::success();
1755
1756   // Create a string representing the vector of command-line definitions. Each
1757   // definition is on its own line and prefixed with a definition number to
1758   // clarify which definition a given diagnostic corresponds to.
1759   unsigned I = 0;
1760   Error Errs = Error::success();
1761   std::string CmdlineDefsDiag;
1762   StringRef Prefix1 = "Global define #";
1763   StringRef Prefix2 = ": ";
1764   for (StringRef CmdlineDef : CmdlineDefines)
1765     CmdlineDefsDiag +=
1766         (Prefix1 + Twine(++I) + Prefix2 + CmdlineDef + "\n").str();
1767
1768   // Create a buffer with fake command line content in order to display
1769   // parsing diagnostic with location information and point to the
1770   // global definition with invalid syntax.
1771   std::unique_ptr<MemoryBuffer> CmdLineDefsDiagBuffer =
1772       MemoryBuffer::getMemBufferCopy(CmdlineDefsDiag, "Global defines");
1773   StringRef CmdlineDefsDiagRef = CmdLineDefsDiagBuffer->getBuffer();
1774   SM.AddNewSourceBuffer(std::move(CmdLineDefsDiagBuffer), SMLoc());
1775
1776   SmallVector<StringRef, 4> CmdlineDefsDiagVec;
1777   CmdlineDefsDiagRef.split(CmdlineDefsDiagVec, '\n', -1 /*MaxSplit*/,
1778                            false /*KeepEmpty*/);
1779   for (StringRef CmdlineDefDiag : CmdlineDefsDiagVec) {
1780     unsigned DefStart = CmdlineDefDiag.find(Prefix2) + Prefix2.size();
1781     StringRef CmdlineDef = CmdlineDefDiag.substr(DefStart);
1782     size_t EqIdx = CmdlineDef.find('=');
1783     if (EqIdx == StringRef::npos) {
1784       Errs = joinErrors(
1785           std::move(Errs),
1786           FileCheckErrorDiagnostic::get(
1787               SM, CmdlineDef, "missing equal sign in global definition"));
1788       continue;
1789     }
1790
1791     // Numeric variable definition.
1792     if (CmdlineDef[0] == '#') {
1793       StringRef CmdlineName = CmdlineDef.substr(1, EqIdx - 1);
1794       Expected<FileCheckNumericVariable *> ParseResult =
1795           FileCheckPattern::parseNumericVariableDefinition(CmdlineName, this,
1796                                                            None, SM);
1797       if (!ParseResult) {
1798         Errs = joinErrors(std::move(Errs), ParseResult.takeError());
1799         continue;
1800       }
1801
1802       StringRef CmdlineVal = CmdlineDef.substr(EqIdx + 1);
1803       uint64_t Val;
1804       if (CmdlineVal.getAsInteger(10, Val)) {
1805         Errs = joinErrors(std::move(Errs),
1806                           FileCheckErrorDiagnostic::get(
1807                               SM, CmdlineVal,
1808                               "invalid value in numeric variable definition '" +
1809                                   CmdlineVal + "'"));
1810         continue;
1811       }
1812       FileCheckNumericVariable *DefinedNumericVariable = *ParseResult;
1813       DefinedNumericVariable->setValue(Val);
1814
1815       // Record this variable definition.
1816       GlobalNumericVariableTable[DefinedNumericVariable->getName()] =
1817           DefinedNumericVariable;
1818     } else {
1819       // String variable definition.
1820       std::pair<StringRef, StringRef> CmdlineNameVal = CmdlineDef.split('=');
1821       StringRef CmdlineName = CmdlineNameVal.first;
1822       StringRef OrigCmdlineName = CmdlineName;
1823       Expected<FileCheckPattern::VariableProperties> ParseVarResult =
1824           FileCheckPattern::parseVariable(CmdlineName, SM);
1825       if (!ParseVarResult) {
1826         Errs = joinErrors(std::move(Errs), ParseVarResult.takeError());
1827         continue;
1828       }
1829       // Check that CmdlineName does not denote a pseudo variable is only
1830       // composed of the parsed numeric variable. This catches cases like
1831       // "FOO+2" in a "FOO+2=10" definition.
1832       if (ParseVarResult->IsPseudo || !CmdlineName.empty()) {
1833         Errs = joinErrors(std::move(Errs),
1834                           FileCheckErrorDiagnostic::get(
1835                               SM, OrigCmdlineName,
1836                               "invalid name in string variable definition '" +
1837                                   OrigCmdlineName + "'"));
1838         continue;
1839       }
1840       StringRef Name = ParseVarResult->Name;
1841
1842       // Detect collisions between string and numeric variables when the former
1843       // is created later than the latter.
1844       if (GlobalNumericVariableTable.find(Name) !=
1845           GlobalNumericVariableTable.end()) {
1846         Errs = joinErrors(std::move(Errs), FileCheckErrorDiagnostic::get(
1847                                                SM, Name,
1848                                                "numeric variable with name '" +
1849                                                    Name + "' already exists"));
1850         continue;
1851       }
1852       GlobalVariableTable.insert(CmdlineNameVal);
1853       // Mark the string variable as defined to detect collisions between
1854       // string and numeric variables in DefineCmdlineVariables when the latter
1855       // is created later than the former. We cannot reuse GlobalVariableTable
1856       // for this by populating it with an empty string since we would then
1857       // lose the ability to detect the use of an undefined variable in
1858       // match().
1859       DefinedVariableTable[Name] = true;
1860     }
1861   }
1862
1863   return Errs;
1864 }
1865
1866 void FileCheckPatternContext::clearLocalVars() {
1867   SmallVector<StringRef, 16> LocalPatternVars, LocalNumericVars;
1868   for (const StringMapEntry<StringRef> &Var : GlobalVariableTable)
1869     if (Var.first()[0] != '$')
1870       LocalPatternVars.push_back(Var.first());
1871
1872   // Numeric substitution reads the value of a variable directly, not via
1873   // GlobalNumericVariableTable. Therefore, we clear local variables by
1874   // clearing their value which will lead to a numeric substitution failure. We
1875   // also mark the variable for removal from GlobalNumericVariableTable since
1876   // this is what defineCmdlineVariables checks to decide that no global
1877   // variable has been defined.
1878   for (const auto &Var : GlobalNumericVariableTable)
1879     if (Var.first()[0] != '$') {
1880       Var.getValue()->clearValue();
1881       LocalNumericVars.push_back(Var.first());
1882     }
1883
1884   for (const auto &Var : LocalPatternVars)
1885     GlobalVariableTable.erase(Var);
1886   for (const auto &Var : LocalNumericVars)
1887     GlobalNumericVariableTable.erase(Var);
1888 }
1889
1890 bool FileCheck::CheckInput(SourceMgr &SM, StringRef Buffer,
1891                            ArrayRef<FileCheckString> CheckStrings,
1892                            std::vector<FileCheckDiag> *Diags) {
1893   bool ChecksFailed = false;
1894
1895   unsigned i = 0, j = 0, e = CheckStrings.size();
1896   while (true) {
1897     StringRef CheckRegion;
1898     if (j == e) {
1899       CheckRegion = Buffer;
1900     } else {
1901       const FileCheckString &CheckLabelStr = CheckStrings[j];
1902       if (CheckLabelStr.Pat.getCheckTy() != Check::CheckLabel) {
1903         ++j;
1904         continue;
1905       }
1906
1907       // Scan to next CHECK-LABEL match, ignoring CHECK-NOT and CHECK-DAG
1908       size_t MatchLabelLen = 0;
1909       size_t MatchLabelPos =
1910           CheckLabelStr.Check(SM, Buffer, true, MatchLabelLen, Req, Diags);
1911       if (MatchLabelPos == StringRef::npos)
1912         // Immediately bail if CHECK-LABEL fails, nothing else we can do.
1913         return false;
1914
1915       CheckRegion = Buffer.substr(0, MatchLabelPos + MatchLabelLen);
1916       Buffer = Buffer.substr(MatchLabelPos + MatchLabelLen);
1917       ++j;
1918     }
1919
1920     // Do not clear the first region as it's the one before the first
1921     // CHECK-LABEL and it would clear variables defined on the command-line
1922     // before they get used.
1923     if (i != 0 && Req.EnableVarScope)
1924       PatternContext.clearLocalVars();
1925
1926     for (; i != j; ++i) {
1927       const FileCheckString &CheckStr = CheckStrings[i];
1928
1929       // Check each string within the scanned region, including a second check
1930       // of any final CHECK-LABEL (to verify CHECK-NOT and CHECK-DAG)
1931       size_t MatchLen = 0;
1932       size_t MatchPos =
1933           CheckStr.Check(SM, CheckRegion, false, MatchLen, Req, Diags);
1934
1935       if (MatchPos == StringRef::npos) {
1936         ChecksFailed = true;
1937         i = j;
1938         break;
1939       }
1940
1941       CheckRegion = CheckRegion.substr(MatchPos + MatchLen);
1942     }
1943
1944     if (j == e)
1945       break;
1946   }
1947
1948   // Success if no checks failed.
1949   return !ChecksFailed;
1950 }