2782 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// FileCheck does a line-by line check of a file that validates whether it10// 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 utility13// as well as various unittests.14//===----------------------------------------------------------------------===//15 16#include "llvm/FileCheck/FileCheck.h"17#include "FileCheckImpl.h"18#include "llvm/ADT/STLExtras.h"19#include "llvm/ADT/StringExtras.h"20#include "llvm/ADT/StringSet.h"21#include "llvm/ADT/Twine.h"22#include "llvm/Support/FormatVariadic.h"23#include <cstdint>24#include <list>25#include <set>26#include <tuple>27#include <utility>28 29using namespace llvm;30 31StringRef ExpressionFormat::toString() const {32 switch (Value) {33 case Kind::NoFormat:34 return StringRef("<none>");35 case Kind::Unsigned:36 return StringRef("%u");37 case Kind::Signed:38 return StringRef("%d");39 case Kind::HexUpper:40 return StringRef("%X");41 case Kind::HexLower:42 return StringRef("%x");43 }44 llvm_unreachable("unknown expression format");45}46 47Expected<std::string> ExpressionFormat::getWildcardRegex() const {48 StringRef AlternateFormPrefix = AlternateForm ? StringRef("0x") : StringRef();49 50 auto CreatePrecisionRegex = [&](StringRef S) {51 return (Twine(AlternateFormPrefix) + S + Twine('{') + Twine(Precision) +52 "}")53 .str();54 };55 56 switch (Value) {57 case Kind::Unsigned:58 if (Precision)59 return CreatePrecisionRegex("([1-9][0-9]*)?[0-9]");60 return std::string("[0-9]+");61 case Kind::Signed:62 if (Precision)63 return CreatePrecisionRegex("-?([1-9][0-9]*)?[0-9]");64 return std::string("-?[0-9]+");65 case Kind::HexUpper:66 if (Precision)67 return CreatePrecisionRegex("([1-9A-F][0-9A-F]*)?[0-9A-F]");68 return (Twine(AlternateFormPrefix) + Twine("[0-9A-F]+")).str();69 case Kind::HexLower:70 if (Precision)71 return CreatePrecisionRegex("([1-9a-f][0-9a-f]*)?[0-9a-f]");72 return (Twine(AlternateFormPrefix) + Twine("[0-9a-f]+")).str();73 default:74 return createStringError(std::errc::invalid_argument,75 "trying to match value with invalid format");76 }77}78 79Expected<std::string>80ExpressionFormat::getMatchingString(APInt IntValue) const {81 if (Value != Kind::Signed && IntValue.isNegative())82 return make_error<OverflowError>();83 84 unsigned Radix;85 bool UpperCase = false;86 SmallString<8> AbsoluteValueStr;87 StringRef SignPrefix = IntValue.isNegative() ? "-" : "";88 switch (Value) {89 case Kind::Unsigned:90 case Kind::Signed:91 Radix = 10;92 break;93 case Kind::HexUpper:94 UpperCase = true;95 Radix = 16;96 break;97 case Kind::HexLower:98 Radix = 16;99 UpperCase = false;100 break;101 default:102 return createStringError(std::errc::invalid_argument,103 "trying to match value with invalid format");104 }105 IntValue.abs().toString(AbsoluteValueStr, Radix, /*Signed=*/false,106 /*formatAsCLiteral=*/false,107 /*UpperCase=*/UpperCase);108 109 StringRef AlternateFormPrefix = AlternateForm ? StringRef("0x") : StringRef();110 111 if (Precision > AbsoluteValueStr.size()) {112 unsigned LeadingZeros = Precision - AbsoluteValueStr.size();113 return (Twine(SignPrefix) + Twine(AlternateFormPrefix) +114 std::string(LeadingZeros, '0') + AbsoluteValueStr)115 .str();116 }117 118 return (Twine(SignPrefix) + Twine(AlternateFormPrefix) + AbsoluteValueStr)119 .str();120}121 122static unsigned nextAPIntBitWidth(unsigned BitWidth) {123 return (BitWidth < APInt::APINT_BITS_PER_WORD) ? APInt::APINT_BITS_PER_WORD124 : BitWidth * 2;125}126 127static APInt toSigned(APInt AbsVal, bool Negative) {128 if (AbsVal.isSignBitSet())129 AbsVal = AbsVal.zext(nextAPIntBitWidth(AbsVal.getBitWidth()));130 APInt Result = AbsVal;131 if (Negative)132 Result.negate();133 return Result;134}135 136APInt ExpressionFormat::valueFromStringRepr(StringRef StrVal,137 const SourceMgr &SM) const {138 bool ValueIsSigned = Value == Kind::Signed;139 bool Negative = StrVal.consume_front("-");140 bool Hex = Value == Kind::HexUpper || Value == Kind::HexLower;141 bool MissingFormPrefix =142 !ValueIsSigned && AlternateForm && !StrVal.consume_front("0x");143 (void)MissingFormPrefix;144 assert(!MissingFormPrefix && "missing alternate form prefix");145 APInt ResultValue;146 [[maybe_unused]] bool ParseFailure =147 StrVal.getAsInteger(Hex ? 16 : 10, ResultValue);148 // Both the FileCheck utility and library only call this method with a valid149 // value in StrVal. This is guaranteed by the regex returned by150 // getWildcardRegex() above.151 assert(!ParseFailure && "unable to represent numeric value");152 return toSigned(ResultValue, Negative);153}154 155Expected<APInt> llvm::exprAdd(const APInt &LeftOperand,156 const APInt &RightOperand, bool &Overflow) {157 return LeftOperand.sadd_ov(RightOperand, Overflow);158}159 160Expected<APInt> llvm::exprSub(const APInt &LeftOperand,161 const APInt &RightOperand, bool &Overflow) {162 return LeftOperand.ssub_ov(RightOperand, Overflow);163}164 165Expected<APInt> llvm::exprMul(const APInt &LeftOperand,166 const APInt &RightOperand, bool &Overflow) {167 return LeftOperand.smul_ov(RightOperand, Overflow);168}169 170Expected<APInt> llvm::exprDiv(const APInt &LeftOperand,171 const APInt &RightOperand, bool &Overflow) {172 // Check for division by zero.173 if (RightOperand.isZero())174 return make_error<OverflowError>();175 176 return LeftOperand.sdiv_ov(RightOperand, Overflow);177}178 179Expected<APInt> llvm::exprMax(const APInt &LeftOperand,180 const APInt &RightOperand, bool &Overflow) {181 Overflow = false;182 return LeftOperand.slt(RightOperand) ? RightOperand : LeftOperand;183}184 185Expected<APInt> llvm::exprMin(const APInt &LeftOperand,186 const APInt &RightOperand, bool &Overflow) {187 Overflow = false;188 if (cantFail(exprMax(LeftOperand, RightOperand, Overflow)) == LeftOperand)189 return RightOperand;190 191 return LeftOperand;192}193 194Expected<APInt> NumericVariableUse::eval() const {195 std::optional<APInt> Value = Variable->getValue();196 if (Value)197 return *Value;198 199 return make_error<UndefVarError>(getExpressionStr());200}201 202Expected<APInt> BinaryOperation::eval() const {203 Expected<APInt> MaybeLeftOp = LeftOperand->eval();204 Expected<APInt> MaybeRightOp = RightOperand->eval();205 206 // Bubble up any error (e.g. undefined variables) in the recursive207 // evaluation.208 if (!MaybeLeftOp || !MaybeRightOp) {209 Error Err = Error::success();210 if (!MaybeLeftOp)211 Err = joinErrors(std::move(Err), MaybeLeftOp.takeError());212 if (!MaybeRightOp)213 Err = joinErrors(std::move(Err), MaybeRightOp.takeError());214 return std::move(Err);215 }216 217 APInt LeftOp = *MaybeLeftOp;218 APInt RightOp = *MaybeRightOp;219 bool Overflow;220 // Ensure both operands have the same bitwidth.221 unsigned LeftBitWidth = LeftOp.getBitWidth();222 unsigned RightBitWidth = RightOp.getBitWidth();223 unsigned NewBitWidth = std::max(LeftBitWidth, RightBitWidth);224 LeftOp = LeftOp.sext(NewBitWidth);225 RightOp = RightOp.sext(NewBitWidth);226 do {227 Expected<APInt> MaybeResult = EvalBinop(LeftOp, RightOp, Overflow);228 if (!MaybeResult)229 return MaybeResult.takeError();230 231 if (!Overflow)232 return MaybeResult;233 234 NewBitWidth = nextAPIntBitWidth(NewBitWidth);235 LeftOp = LeftOp.sext(NewBitWidth);236 RightOp = RightOp.sext(NewBitWidth);237 } while (true);238}239 240Expected<ExpressionFormat>241BinaryOperation::getImplicitFormat(const SourceMgr &SM) const {242 Expected<ExpressionFormat> LeftFormat = LeftOperand->getImplicitFormat(SM);243 Expected<ExpressionFormat> RightFormat = RightOperand->getImplicitFormat(SM);244 if (!LeftFormat || !RightFormat) {245 Error Err = Error::success();246 if (!LeftFormat)247 Err = joinErrors(std::move(Err), LeftFormat.takeError());248 if (!RightFormat)249 Err = joinErrors(std::move(Err), RightFormat.takeError());250 return std::move(Err);251 }252 253 if (*LeftFormat != ExpressionFormat::Kind::NoFormat &&254 *RightFormat != ExpressionFormat::Kind::NoFormat &&255 *LeftFormat != *RightFormat)256 return ErrorDiagnostic::get(257 SM, getExpressionStr(),258 "implicit format conflict between '" + LeftOperand->getExpressionStr() +259 "' (" + LeftFormat->toString() + ") and '" +260 RightOperand->getExpressionStr() + "' (" + RightFormat->toString() +261 "), need an explicit format specifier");262 263 return *LeftFormat != ExpressionFormat::Kind::NoFormat ? *LeftFormat264 : *RightFormat;265}266 267Expected<std::string> NumericSubstitution::getResultRegex() const {268 assert(ExpressionPointer->getAST() != nullptr &&269 "Substituting empty expression");270 Expected<APInt> EvaluatedValue = ExpressionPointer->getAST()->eval();271 if (!EvaluatedValue)272 return EvaluatedValue.takeError();273 ExpressionFormat Format = ExpressionPointer->getFormat();274 return Format.getMatchingString(*EvaluatedValue);275}276 277Expected<std::string> NumericSubstitution::getResultForDiagnostics() const {278 // The "regex" returned by getResultRegex() is just a numeric value279 // like '42', '0x2A', '-17', 'DEADBEEF' etc. This is already suitable for use280 // in diagnostics.281 Expected<std::string> Literal = getResultRegex();282 if (!Literal)283 return Literal;284 285 return "\"" + std::move(*Literal) + "\"";286}287 288Expected<std::string> StringSubstitution::getResultRegex() const {289 // Look up the value and escape it so that we can put it into the regex.290 Expected<StringRef> VarVal = Context->getPatternVarValue(FromStr);291 if (!VarVal)292 return VarVal.takeError();293 return Regex::escape(*VarVal);294}295 296Expected<std::string> StringSubstitution::getResultForDiagnostics() const {297 Expected<StringRef> VarVal = Context->getPatternVarValue(FromStr);298 if (!VarVal)299 return VarVal.takeError();300 301 std::string Result;302 Result.reserve(VarVal->size() + 2);303 raw_string_ostream OS(Result);304 305 OS << '"';306 // Escape the string if it contains any characters that307 // make it hard to read, such as non-printable characters (including all308 // whitespace except space) and double quotes. These are the characters that309 // are escaped by write_escaped(), except we do not include backslashes,310 // because they are common in Windows paths and escaping them would make the311 // output harder to read. However, when we do escape, backslashes are escaped312 // as well, otherwise the output would be ambiguous.313 const bool NeedsEscaping =314 llvm::any_of(*VarVal, [](char C) { return !isPrint(C) || C == '"'; });315 if (NeedsEscaping)316 OS.write_escaped(*VarVal);317 else318 OS << *VarVal;319 OS << '"';320 if (NeedsEscaping)321 OS << " (escaped value)";322 323 return Result;324}325 326bool Pattern::isValidVarNameStart(char C) { return C == '_' || isAlpha(C); }327 328Expected<Pattern::VariableProperties>329Pattern::parseVariable(StringRef &Str, const SourceMgr &SM) {330 if (Str.empty())331 return ErrorDiagnostic::get(SM, Str, "empty variable name");332 333 size_t I = 0;334 bool IsPseudo = Str[0] == '@';335 336 // Global vars start with '$'.337 if (Str[0] == '$' || IsPseudo)338 ++I;339 340 if (I == Str.size())341 return ErrorDiagnostic::get(SM, Str.substr(I),342 StringRef("empty ") +343 (IsPseudo ? "pseudo " : "global ") +344 "variable name");345 346 if (!isValidVarNameStart(Str[I++]))347 return ErrorDiagnostic::get(SM, Str, "invalid variable name");348 349 for (size_t E = Str.size(); I != E; ++I)350 // Variable names are composed of alphanumeric characters and underscores.351 if (Str[I] != '_' && !isAlnum(Str[I]))352 break;353 354 StringRef Name = Str.take_front(I);355 Str = Str.substr(I);356 return VariableProperties {Name, IsPseudo};357}358 359// StringRef holding all characters considered as horizontal whitespaces by360// FileCheck input canonicalization.361constexpr StringLiteral SpaceChars = " \t";362 363// Parsing helper function that strips the first character in S and returns it.364static char popFront(StringRef &S) {365 char C = S.front();366 S = S.drop_front();367 return C;368}369 370char OverflowError::ID = 0;371char UndefVarError::ID = 0;372char ErrorDiagnostic::ID = 0;373char NotFoundError::ID = 0;374char ErrorReported::ID = 0;375 376Expected<NumericVariable *> Pattern::parseNumericVariableDefinition(377 StringRef &Expr, FileCheckPatternContext *Context,378 std::optional<size_t> LineNumber, ExpressionFormat ImplicitFormat,379 const SourceMgr &SM) {380 Expected<VariableProperties> ParseVarResult = parseVariable(Expr, SM);381 if (!ParseVarResult)382 return ParseVarResult.takeError();383 StringRef Name = ParseVarResult->Name;384 385 if (ParseVarResult->IsPseudo)386 return ErrorDiagnostic::get(387 SM, Name, "definition of pseudo numeric variable unsupported");388 389 // Detect collisions between string and numeric variables when the latter390 // is created later than the former.391 if (Context->DefinedVariableTable.contains(Name))392 return ErrorDiagnostic::get(393 SM, Name, "string variable with name '" + Name + "' already exists");394 395 Expr = Expr.ltrim(SpaceChars);396 if (!Expr.empty())397 return ErrorDiagnostic::get(398 SM, Expr, "unexpected characters after numeric variable name");399 400 NumericVariable *DefinedNumericVariable;401 auto VarTableIter = Context->GlobalNumericVariableTable.find(Name);402 if (VarTableIter != Context->GlobalNumericVariableTable.end()) {403 DefinedNumericVariable = VarTableIter->second;404 if (DefinedNumericVariable->getImplicitFormat() != ImplicitFormat)405 return ErrorDiagnostic::get(406 SM, Expr, "format different from previous variable definition");407 } else408 DefinedNumericVariable =409 Context->makeNumericVariable(Name, ImplicitFormat, LineNumber);410 411 return DefinedNumericVariable;412}413 414Expected<std::unique_ptr<NumericVariableUse>> Pattern::parseNumericVariableUse(415 StringRef Name, bool IsPseudo, std::optional<size_t> LineNumber,416 FileCheckPatternContext *Context, const SourceMgr &SM) {417 if (IsPseudo && Name != "@LINE")418 return ErrorDiagnostic::get(419 SM, Name, "invalid pseudo numeric variable '" + Name + "'");420 421 // Numeric variable definitions and uses are parsed in the order in which422 // they appear in the CHECK patterns. For each definition, the pointer to the423 // class instance of the corresponding numeric variable definition is stored424 // in GlobalNumericVariableTable in parsePattern. Therefore, if the pointer425 // we get below is null, it means no such variable was defined before. When426 // that happens, we create a dummy variable so that parsing can continue. All427 // uses of undefined variables, whether string or numeric, are then diagnosed428 // in printNoMatch() after failing to match.429 auto [VarTableIter, Inserted] =430 Context->GlobalNumericVariableTable.try_emplace(Name);431 if (Inserted)432 VarTableIter->second = Context->makeNumericVariable(433 Name, ExpressionFormat(ExpressionFormat::Kind::Unsigned));434 NumericVariable *NumericVariable = VarTableIter->second;435 436 std::optional<size_t> DefLineNumber = NumericVariable->getDefLineNumber();437 if (DefLineNumber && LineNumber && *DefLineNumber == *LineNumber)438 return ErrorDiagnostic::get(439 SM, Name,440 "numeric variable '" + Name +441 "' defined earlier in the same CHECK directive");442 443 return std::make_unique<NumericVariableUse>(Name, NumericVariable);444}445 446Expected<std::unique_ptr<ExpressionAST>> Pattern::parseNumericOperand(447 StringRef &Expr, AllowedOperand AO, bool MaybeInvalidConstraint,448 std::optional<size_t> LineNumber, FileCheckPatternContext *Context,449 const SourceMgr &SM) {450 if (Expr.starts_with("(")) {451 if (AO != AllowedOperand::Any)452 return ErrorDiagnostic::get(453 SM, Expr, "parenthesized expression not permitted here");454 return parseParenExpr(Expr, LineNumber, Context, SM);455 }456 457 if (AO == AllowedOperand::LineVar || AO == AllowedOperand::Any) {458 // Try to parse as a numeric variable use.459 Expected<Pattern::VariableProperties> ParseVarResult =460 parseVariable(Expr, SM);461 if (ParseVarResult) {462 // Try to parse a function call.463 if (Expr.ltrim(SpaceChars).starts_with("(")) {464 if (AO != AllowedOperand::Any)465 return ErrorDiagnostic::get(SM, ParseVarResult->Name,466 "unexpected function call");467 468 return parseCallExpr(Expr, ParseVarResult->Name, LineNumber, Context,469 SM);470 }471 472 return parseNumericVariableUse(ParseVarResult->Name,473 ParseVarResult->IsPseudo, LineNumber,474 Context, SM);475 }476 477 if (AO == AllowedOperand::LineVar)478 return ParseVarResult.takeError();479 // Ignore the error and retry parsing as a literal.480 consumeError(ParseVarResult.takeError());481 }482 483 // Otherwise, parse it as a literal.484 APInt LiteralValue;485 StringRef SaveExpr = Expr;486 bool Negative = Expr.consume_front("-");487 if (!Expr.consumeInteger((AO == AllowedOperand::LegacyLiteral) ? 10 : 0,488 LiteralValue)) {489 LiteralValue = toSigned(LiteralValue, Negative);490 return std::make_unique<ExpressionLiteral>(SaveExpr.drop_back(Expr.size()),491 LiteralValue);492 }493 return ErrorDiagnostic::get(494 SM, SaveExpr,495 Twine("invalid ") +496 (MaybeInvalidConstraint ? "matching constraint or " : "") +497 "operand format");498}499 500Expected<std::unique_ptr<ExpressionAST>>501Pattern::parseParenExpr(StringRef &Expr, std::optional<size_t> LineNumber,502 FileCheckPatternContext *Context, const SourceMgr &SM) {503 Expr = Expr.ltrim(SpaceChars);504 assert(Expr.starts_with("("));505 506 // Parse right operand.507 Expr.consume_front("(");508 Expr = Expr.ltrim(SpaceChars);509 if (Expr.empty())510 return ErrorDiagnostic::get(SM, Expr, "missing operand in expression");511 512 // Note: parseNumericOperand handles nested opening parentheses.513 Expected<std::unique_ptr<ExpressionAST>> SubExprResult = parseNumericOperand(514 Expr, AllowedOperand::Any, /*MaybeInvalidConstraint=*/false, LineNumber,515 Context, SM);516 Expr = Expr.ltrim(SpaceChars);517 while (SubExprResult && !Expr.empty() && !Expr.starts_with(")")) {518 StringRef OrigExpr = Expr;519 SubExprResult = parseBinop(OrigExpr, Expr, std::move(*SubExprResult), false,520 LineNumber, Context, SM);521 Expr = Expr.ltrim(SpaceChars);522 }523 if (!SubExprResult)524 return SubExprResult;525 526 if (!Expr.consume_front(")")) {527 return ErrorDiagnostic::get(SM, Expr,528 "missing ')' at end of nested expression");529 }530 return SubExprResult;531}532 533Expected<std::unique_ptr<ExpressionAST>>534Pattern::parseBinop(StringRef Expr, StringRef &RemainingExpr,535 std::unique_ptr<ExpressionAST> LeftOp,536 bool IsLegacyLineExpr, std::optional<size_t> LineNumber,537 FileCheckPatternContext *Context, const SourceMgr &SM) {538 RemainingExpr = RemainingExpr.ltrim(SpaceChars);539 if (RemainingExpr.empty())540 return std::move(LeftOp);541 542 // Check if this is a supported operation and select a function to perform543 // it.544 SMLoc OpLoc = SMLoc::getFromPointer(RemainingExpr.data());545 char Operator = popFront(RemainingExpr);546 binop_eval_t EvalBinop;547 switch (Operator) {548 case '+':549 EvalBinop = exprAdd;550 break;551 case '-':552 EvalBinop = exprSub;553 break;554 default:555 return ErrorDiagnostic::get(556 SM, OpLoc, Twine("unsupported operation '") + Twine(Operator) + "'");557 }558 559 // Parse right operand.560 RemainingExpr = RemainingExpr.ltrim(SpaceChars);561 if (RemainingExpr.empty())562 return ErrorDiagnostic::get(SM, RemainingExpr,563 "missing operand in expression");564 // The second operand in a legacy @LINE expression is always a literal.565 AllowedOperand AO =566 IsLegacyLineExpr ? AllowedOperand::LegacyLiteral : AllowedOperand::Any;567 Expected<std::unique_ptr<ExpressionAST>> RightOpResult =568 parseNumericOperand(RemainingExpr, AO, /*MaybeInvalidConstraint=*/false,569 LineNumber, Context, SM);570 if (!RightOpResult)571 return RightOpResult;572 573 Expr = Expr.drop_back(RemainingExpr.size());574 return std::make_unique<BinaryOperation>(Expr, EvalBinop, std::move(LeftOp),575 std::move(*RightOpResult));576}577 578Expected<std::unique_ptr<ExpressionAST>>579Pattern::parseCallExpr(StringRef &Expr, StringRef FuncName,580 std::optional<size_t> LineNumber,581 FileCheckPatternContext *Context, const SourceMgr &SM) {582 Expr = Expr.ltrim(SpaceChars);583 assert(Expr.starts_with("("));584 585 auto OptFunc = StringSwitch<binop_eval_t>(FuncName)586 .Case("add", exprAdd)587 .Case("div", exprDiv)588 .Case("max", exprMax)589 .Case("min", exprMin)590 .Case("mul", exprMul)591 .Case("sub", exprSub)592 .Default(nullptr);593 594 if (!OptFunc)595 return ErrorDiagnostic::get(596 SM, FuncName, Twine("call to undefined function '") + FuncName + "'");597 598 Expr.consume_front("(");599 Expr = Expr.ltrim(SpaceChars);600 601 // Parse call arguments, which are comma separated.602 SmallVector<std::unique_ptr<ExpressionAST>, 4> Args;603 while (!Expr.empty() && !Expr.starts_with(")")) {604 if (Expr.starts_with(","))605 return ErrorDiagnostic::get(SM, Expr, "missing argument");606 607 // Parse the argument, which is an arbitary expression.608 StringRef OuterBinOpExpr = Expr;609 Expected<std::unique_ptr<ExpressionAST>> Arg = parseNumericOperand(610 Expr, AllowedOperand::Any, /*MaybeInvalidConstraint=*/false, LineNumber,611 Context, SM);612 while (Arg && !Expr.empty()) {613 Expr = Expr.ltrim(SpaceChars);614 // Have we reached an argument terminator?615 if (Expr.starts_with(",") || Expr.starts_with(")"))616 break;617 618 // Arg = Arg <op> <expr>619 Arg = parseBinop(OuterBinOpExpr, Expr, std::move(*Arg), false, LineNumber,620 Context, SM);621 }622 623 // Prefer an expression error over a generic invalid argument message.624 if (!Arg)625 return Arg.takeError();626 Args.push_back(std::move(*Arg));627 628 // Have we parsed all available arguments?629 Expr = Expr.ltrim(SpaceChars);630 if (!Expr.consume_front(","))631 break;632 633 Expr = Expr.ltrim(SpaceChars);634 if (Expr.starts_with(")"))635 return ErrorDiagnostic::get(SM, Expr, "missing argument");636 }637 638 if (!Expr.consume_front(")"))639 return ErrorDiagnostic::get(SM, Expr,640 "missing ')' at end of call expression");641 642 const unsigned NumArgs = Args.size();643 if (NumArgs == 2)644 return std::make_unique<BinaryOperation>(Expr, *OptFunc, std::move(Args[0]),645 std::move(Args[1]));646 647 // TODO: Support more than binop_eval_t.648 return ErrorDiagnostic::get(SM, FuncName,649 Twine("function '") + FuncName +650 Twine("' takes 2 arguments but ") +651 Twine(NumArgs) + " given");652}653 654Expected<std::unique_ptr<Expression>> Pattern::parseNumericSubstitutionBlock(655 StringRef Expr, std::optional<NumericVariable *> &DefinedNumericVariable,656 bool IsLegacyLineExpr, std::optional<size_t> LineNumber,657 FileCheckPatternContext *Context, const SourceMgr &SM) {658 std::unique_ptr<ExpressionAST> ExpressionASTPointer = nullptr;659 StringRef DefExpr = StringRef();660 DefinedNumericVariable = std::nullopt;661 ExpressionFormat ExplicitFormat = ExpressionFormat();662 unsigned Precision = 0;663 664 // Parse format specifier (NOTE: ',' is also an argument separator).665 size_t FormatSpecEnd = Expr.find(',');666 size_t FunctionStart = Expr.find('(');667 if (FormatSpecEnd != StringRef::npos && FormatSpecEnd < FunctionStart) {668 StringRef FormatExpr = Expr.take_front(FormatSpecEnd);669 Expr = Expr.drop_front(FormatSpecEnd + 1);670 FormatExpr = FormatExpr.trim(SpaceChars);671 if (!FormatExpr.consume_front("%"))672 return ErrorDiagnostic::get(673 SM, FormatExpr,674 "invalid matching format specification in expression");675 676 // Parse alternate form flag.677 SMLoc AlternateFormFlagLoc = SMLoc::getFromPointer(FormatExpr.data());678 bool AlternateForm = FormatExpr.consume_front("#");679 680 // Parse precision.681 if (FormatExpr.consume_front(".")) {682 if (FormatExpr.consumeInteger(10, Precision))683 return ErrorDiagnostic::get(SM, FormatExpr,684 "invalid precision in format specifier");685 }686 687 if (!FormatExpr.empty()) {688 // Check for unknown matching format specifier and set matching format in689 // class instance representing this expression.690 SMLoc FmtLoc = SMLoc::getFromPointer(FormatExpr.data());691 switch (popFront(FormatExpr)) {692 case 'u':693 ExplicitFormat =694 ExpressionFormat(ExpressionFormat::Kind::Unsigned, Precision);695 break;696 case 'd':697 ExplicitFormat =698 ExpressionFormat(ExpressionFormat::Kind::Signed, Precision);699 break;700 case 'x':701 ExplicitFormat = ExpressionFormat(ExpressionFormat::Kind::HexLower,702 Precision, AlternateForm);703 break;704 case 'X':705 ExplicitFormat = ExpressionFormat(ExpressionFormat::Kind::HexUpper,706 Precision, AlternateForm);707 break;708 default:709 return ErrorDiagnostic::get(SM, FmtLoc,710 "invalid format specifier in expression");711 }712 }713 714 if (AlternateForm && ExplicitFormat != ExpressionFormat::Kind::HexLower &&715 ExplicitFormat != ExpressionFormat::Kind::HexUpper)716 return ErrorDiagnostic::get(717 SM, AlternateFormFlagLoc,718 "alternate form only supported for hex values");719 720 FormatExpr = FormatExpr.ltrim(SpaceChars);721 if (!FormatExpr.empty())722 return ErrorDiagnostic::get(723 SM, FormatExpr,724 "invalid matching format specification in expression");725 }726 727 // Save variable definition expression if any.728 size_t DefEnd = Expr.find(':');729 if (DefEnd != StringRef::npos) {730 DefExpr = Expr.substr(0, DefEnd);731 Expr = Expr.substr(DefEnd + 1);732 }733 734 // Parse matching constraint.735 Expr = Expr.ltrim(SpaceChars);736 bool HasParsedValidConstraint = Expr.consume_front("==");737 738 // Parse the expression itself.739 Expr = Expr.ltrim(SpaceChars);740 if (Expr.empty()) {741 if (HasParsedValidConstraint)742 return ErrorDiagnostic::get(743 SM, Expr, "empty numeric expression should not have a constraint");744 } else {745 Expr = Expr.rtrim(SpaceChars);746 StringRef OuterBinOpExpr = Expr;747 // The first operand in a legacy @LINE expression is always the @LINE748 // pseudo variable.749 AllowedOperand AO =750 IsLegacyLineExpr ? AllowedOperand::LineVar : AllowedOperand::Any;751 Expected<std::unique_ptr<ExpressionAST>> ParseResult = parseNumericOperand(752 Expr, AO, !HasParsedValidConstraint, LineNumber, Context, SM);753 while (ParseResult && !Expr.empty()) {754 ParseResult = parseBinop(OuterBinOpExpr, Expr, std::move(*ParseResult),755 IsLegacyLineExpr, LineNumber, Context, SM);756 // Legacy @LINE expressions only allow 2 operands.757 if (ParseResult && IsLegacyLineExpr && !Expr.empty())758 return ErrorDiagnostic::get(759 SM, Expr,760 "unexpected characters at end of expression '" + Expr + "'");761 }762 if (!ParseResult)763 return ParseResult.takeError();764 ExpressionASTPointer = std::move(*ParseResult);765 }766 767 // Select format of the expression, i.e. (i) its explicit format, if any,768 // otherwise (ii) its implicit format, if any, otherwise (iii) the default769 // format (unsigned). Error out in case of conflicting implicit format770 // without explicit format.771 ExpressionFormat Format;772 if (ExplicitFormat)773 Format = ExplicitFormat;774 else if (ExpressionASTPointer) {775 Expected<ExpressionFormat> ImplicitFormat =776 ExpressionASTPointer->getImplicitFormat(SM);777 if (!ImplicitFormat)778 return ImplicitFormat.takeError();779 Format = *ImplicitFormat;780 }781 if (!Format)782 Format = ExpressionFormat(ExpressionFormat::Kind::Unsigned, Precision);783 784 std::unique_ptr<Expression> ExpressionPointer =785 std::make_unique<Expression>(std::move(ExpressionASTPointer), Format);786 787 // Parse the numeric variable definition.788 if (DefEnd != StringRef::npos) {789 DefExpr = DefExpr.ltrim(SpaceChars);790 Expected<NumericVariable *> ParseResult = parseNumericVariableDefinition(791 DefExpr, Context, LineNumber, ExpressionPointer->getFormat(), SM);792 793 if (!ParseResult)794 return ParseResult.takeError();795 DefinedNumericVariable = *ParseResult;796 }797 798 return std::move(ExpressionPointer);799}800 801bool Pattern::parsePattern(StringRef PatternStr, StringRef Prefix,802 SourceMgr &SM, const FileCheckRequest &Req) {803 bool MatchFullLinesHere = Req.MatchFullLines && CheckTy != Check::CheckNot;804 IgnoreCase = Req.IgnoreCase;805 806 PatternLoc = SMLoc::getFromPointer(PatternStr.data());807 808 if (!(Req.NoCanonicalizeWhiteSpace && Req.MatchFullLines))809 // Ignore trailing whitespace.810 PatternStr = PatternStr.rtrim(" \t");811 812 // Check that there is something on the line.813 if (PatternStr.empty() && CheckTy != Check::CheckEmpty) {814 SM.PrintMessage(PatternLoc, SourceMgr::DK_Error,815 "found empty check string with prefix '" + Prefix + ":'");816 return true;817 }818 819 if (!PatternStr.empty() && CheckTy == Check::CheckEmpty) {820 SM.PrintMessage(821 PatternLoc, SourceMgr::DK_Error,822 "found non-empty check string for empty check with prefix '" + Prefix +823 ":'");824 return true;825 }826 827 if (CheckTy == Check::CheckEmpty) {828 RegExStr = "(\n$)";829 return false;830 }831 832 // If literal check, set fixed string.833 if (CheckTy.isLiteralMatch()) {834 FixedStr = PatternStr;835 return false;836 }837 838 // Check to see if this is a fixed string, or if it has regex pieces.839 if (!MatchFullLinesHere &&840 (PatternStr.size() < 2 ||841 (!PatternStr.contains("{{") && !PatternStr.contains("[[")))) {842 FixedStr = PatternStr;843 return false;844 }845 846 if (MatchFullLinesHere) {847 RegExStr += '^';848 if (!Req.NoCanonicalizeWhiteSpace)849 RegExStr += " *";850 }851 852 // Paren value #0 is for the fully matched string. Any new parenthesized853 // values add from there.854 unsigned CurParen = 1;855 856 // Otherwise, there is at least one regex piece. Build up the regex pattern857 // by escaping scary characters in fixed strings, building up one big regex.858 while (!PatternStr.empty()) {859 // RegEx matches.860 if (PatternStr.starts_with("{{")) {861 // This is the start of a regex match. Scan for the }}.862 size_t End = PatternStr.find("}}");863 if (End == StringRef::npos) {864 SM.PrintMessage(SMLoc::getFromPointer(PatternStr.data()),865 SourceMgr::DK_Error,866 "found start of regex string with no end '}}'");867 return true;868 }869 870 // Enclose {{}} patterns in parens just like [[]] even though we're not871 // capturing the result for any purpose. This is required in case the872 // expression contains an alternation like: CHECK: abc{{x|z}}def. We873 // want this to turn into: "abc(x|z)def" not "abcx|zdef".874 bool HasAlternation = PatternStr.contains('|');875 if (HasAlternation) {876 RegExStr += '(';877 ++CurParen;878 }879 880 if (AddRegExToRegEx(PatternStr.substr(2, End - 2), CurParen, SM))881 return true;882 if (HasAlternation)883 RegExStr += ')';884 885 PatternStr = PatternStr.substr(End + 2);886 continue;887 }888 889 // String and numeric substitution blocks. Pattern substitution blocks come890 // in two forms: [[foo:.*]] and [[foo]]. The former matches .* (or some891 // other regex) and assigns it to the string variable 'foo'. The latter892 // substitutes foo's value. Numeric substitution blocks recognize the same893 // form as string ones, but start with a '#' sign after the double894 // brackets. They also accept a combined form which sets a numeric variable895 // to the evaluation of an expression. Both string and numeric variable896 // names must satisfy the regular expression "[a-zA-Z_][0-9a-zA-Z_]*" to be897 // valid, as this helps catch some common errors. If there are extra '['s898 // before the "[[", treat them literally.899 if (PatternStr.starts_with("[[") && !PatternStr.starts_with("[[[")) {900 StringRef UnparsedPatternStr = PatternStr.substr(2);901 // Find the closing bracket pair ending the match. End is going to be an902 // offset relative to the beginning of the match string.903 size_t End = FindRegexVarEnd(UnparsedPatternStr, SM);904 StringRef MatchStr = UnparsedPatternStr.substr(0, End);905 bool IsNumBlock = MatchStr.consume_front("#");906 907 if (End == StringRef::npos) {908 SM.PrintMessage(SMLoc::getFromPointer(PatternStr.data()),909 SourceMgr::DK_Error,910 "Invalid substitution block, no ]] found");911 return true;912 }913 // Strip the substitution block we are parsing. End points to the start914 // of the "]]" closing the expression so account for it in computing the915 // index of the first unparsed character.916 PatternStr = UnparsedPatternStr.substr(End + 2);917 918 bool IsDefinition = false;919 bool SubstNeeded = false;920 // Whether the substitution block is a legacy use of @LINE with string921 // substitution block syntax.922 bool IsLegacyLineExpr = false;923 StringRef DefName;924 StringRef SubstStr;925 StringRef MatchRegexp;926 std::string WildcardRegexp;927 size_t SubstInsertIdx = RegExStr.size();928 929 // Parse string variable or legacy @LINE expression.930 if (!IsNumBlock) {931 size_t VarEndIdx = MatchStr.find(':');932 size_t SpacePos = MatchStr.substr(0, VarEndIdx).find_first_of(" \t");933 if (SpacePos != StringRef::npos) {934 SM.PrintMessage(SMLoc::getFromPointer(MatchStr.data() + SpacePos),935 SourceMgr::DK_Error, "unexpected whitespace");936 return true;937 }938 939 // Get the name (e.g. "foo") and verify it is well formed.940 StringRef OrigMatchStr = MatchStr;941 Expected<Pattern::VariableProperties> ParseVarResult =942 parseVariable(MatchStr, SM);943 if (!ParseVarResult) {944 logAllUnhandledErrors(ParseVarResult.takeError(), errs());945 return true;946 }947 StringRef Name = ParseVarResult->Name;948 bool IsPseudo = ParseVarResult->IsPseudo;949 950 IsDefinition = (VarEndIdx != StringRef::npos);951 SubstNeeded = !IsDefinition;952 if (IsDefinition) {953 if ((IsPseudo || !MatchStr.consume_front(":"))) {954 SM.PrintMessage(SMLoc::getFromPointer(Name.data()),955 SourceMgr::DK_Error,956 "invalid name in string variable definition");957 return true;958 }959 960 // Detect collisions between string and numeric variables when the961 // former is created later than the latter.962 if (Context->GlobalNumericVariableTable.contains(Name)) {963 SM.PrintMessage(964 SMLoc::getFromPointer(Name.data()), SourceMgr::DK_Error,965 "numeric variable with name '" + Name + "' already exists");966 return true;967 }968 DefName = Name;969 MatchRegexp = MatchStr;970 } else {971 if (IsPseudo) {972 MatchStr = OrigMatchStr;973 IsLegacyLineExpr = IsNumBlock = true;974 } else {975 if (!MatchStr.empty()) {976 SM.PrintMessage(SMLoc::getFromPointer(Name.data()),977 SourceMgr::DK_Error,978 "invalid name in string variable use");979 return true;980 }981 SubstStr = Name;982 }983 }984 }985 986 // Parse numeric substitution block.987 std::unique_ptr<Expression> ExpressionPointer;988 std::optional<NumericVariable *> DefinedNumericVariable;989 if (IsNumBlock) {990 Expected<std::unique_ptr<Expression>> ParseResult =991 parseNumericSubstitutionBlock(MatchStr, DefinedNumericVariable,992 IsLegacyLineExpr, LineNumber, Context,993 SM);994 if (!ParseResult) {995 logAllUnhandledErrors(ParseResult.takeError(), errs());996 return true;997 }998 ExpressionPointer = std::move(*ParseResult);999 SubstNeeded = ExpressionPointer->getAST() != nullptr;1000 if (DefinedNumericVariable) {1001 IsDefinition = true;1002 DefName = (*DefinedNumericVariable)->getName();1003 }1004 if (SubstNeeded)1005 SubstStr = MatchStr;1006 else {1007 ExpressionFormat Format = ExpressionPointer->getFormat();1008 WildcardRegexp = cantFail(Format.getWildcardRegex());1009 MatchRegexp = WildcardRegexp;1010 }1011 }1012 1013 // Handle variable definition: [[<def>:(...)]] and [[#(...)<def>:(...)]].1014 if (IsDefinition) {1015 RegExStr += '(';1016 ++SubstInsertIdx;1017 1018 if (IsNumBlock) {1019 NumericVariableMatch NumericVariableDefinition = {1020 *DefinedNumericVariable, CurParen};1021 NumericVariableDefs[DefName] = NumericVariableDefinition;1022 // This store is done here rather than in match() to allow1023 // parseNumericVariableUse() to get the pointer to the class instance1024 // of the right variable definition corresponding to a given numeric1025 // variable use.1026 Context->GlobalNumericVariableTable[DefName] =1027 *DefinedNumericVariable;1028 } else {1029 VariableDefs[DefName] = CurParen;1030 // Mark string variable as defined to detect collisions between1031 // string and numeric variables in parseNumericVariableUse() and1032 // defineCmdlineVariables() when the latter is created later than the1033 // former. We cannot reuse GlobalVariableTable for this by populating1034 // it with an empty string since we would then lose the ability to1035 // detect the use of an undefined variable in match().1036 Context->DefinedVariableTable[DefName] = true;1037 }1038 1039 ++CurParen;1040 }1041 1042 if (!MatchRegexp.empty() && AddRegExToRegEx(MatchRegexp, CurParen, SM))1043 return true;1044 1045 if (IsDefinition)1046 RegExStr += ')';1047 1048 // Handle substitutions: [[foo]] and [[#<foo expr>]].1049 if (SubstNeeded) {1050 // Handle substitution of string variables that were defined earlier on1051 // the same line by emitting a backreference. Expressions do not1052 // support substituting a numeric variable defined on the same line.1053 decltype(VariableDefs)::iterator It;1054 if (!IsNumBlock &&1055 (It = VariableDefs.find(SubstStr)) != VariableDefs.end()) {1056 unsigned CaptureParenGroup = It->second;1057 if (CaptureParenGroup < 1 || CaptureParenGroup > 9) {1058 SM.PrintMessage(SMLoc::getFromPointer(SubstStr.data()),1059 SourceMgr::DK_Error,1060 "Can't back-reference more than 9 variables");1061 return true;1062 }1063 AddBackrefToRegEx(CaptureParenGroup);1064 } else {1065 // Handle substitution of string variables ([[<var>]]) defined in1066 // previous CHECK patterns, and substitution of expressions.1067 Substitution *Substitution =1068 IsNumBlock1069 ? Context->makeNumericSubstitution(1070 SubstStr, std::move(ExpressionPointer), SubstInsertIdx)1071 : Context->makeStringSubstitution(SubstStr, SubstInsertIdx);1072 Substitutions.push_back(Substitution);1073 }1074 }1075 1076 continue;1077 }1078 1079 // Handle fixed string matches.1080 // Find the end, which is the start of the next regex.1081 size_t FixedMatchEnd =1082 std::min(PatternStr.find("{{", 1), PatternStr.find("[[", 1));1083 RegExStr += Regex::escape(PatternStr.substr(0, FixedMatchEnd));1084 PatternStr = PatternStr.substr(FixedMatchEnd);1085 }1086 1087 if (MatchFullLinesHere) {1088 if (!Req.NoCanonicalizeWhiteSpace)1089 RegExStr += " *";1090 RegExStr += '$';1091 }1092 1093 return false;1094}1095 1096bool Pattern::AddRegExToRegEx(StringRef RS, unsigned &CurParen, SourceMgr &SM) {1097 Regex R(RS);1098 std::string Error;1099 if (!R.isValid(Error)) {1100 SM.PrintMessage(SMLoc::getFromPointer(RS.data()), SourceMgr::DK_Error,1101 "invalid regex: " + Error);1102 return true;1103 }1104 1105 RegExStr += RS.str();1106 CurParen += R.getNumMatches();1107 return false;1108}1109 1110void Pattern::AddBackrefToRegEx(unsigned BackrefNum) {1111 assert(BackrefNum >= 1 && BackrefNum <= 9 && "Invalid backref number");1112 std::string Backref = std::string("\\") + std::string(1, '0' + BackrefNum);1113 RegExStr += Backref;1114}1115 1116Pattern::MatchResult Pattern::match(StringRef Buffer,1117 const SourceMgr &SM) const {1118 // If this is the EOF pattern, match it immediately.1119 if (CheckTy == Check::CheckEOF)1120 return MatchResult(Buffer.size(), 0, Error::success());1121 1122 // If this is a fixed string pattern, just match it now.1123 if (!FixedStr.empty()) {1124 size_t Pos =1125 IgnoreCase ? Buffer.find_insensitive(FixedStr) : Buffer.find(FixedStr);1126 if (Pos == StringRef::npos)1127 return make_error<NotFoundError>();1128 return MatchResult(Pos, /*MatchLen=*/FixedStr.size(), Error::success());1129 }1130 1131 // Regex match.1132 1133 // If there are substitutions, we need to create a temporary string with the1134 // actual value.1135 StringRef RegExToMatch = RegExStr;1136 std::string TmpStr;1137 if (!Substitutions.empty()) {1138 TmpStr = RegExStr;1139 if (LineNumber)1140 Context->LineVariable->setValue(1141 APInt(sizeof(*LineNumber) * 8, *LineNumber));1142 1143 size_t InsertOffset = 0;1144 // Substitute all string variables and expressions whose values are only1145 // now known. Use of string variables defined on the same line are handled1146 // by back-references.1147 Error Errs = Error::success();1148 for (const auto &Substitution : Substitutions) {1149 // Substitute and check for failure (e.g. use of undefined variable).1150 Expected<std::string> Value = Substitution->getResultRegex();1151 if (!Value) {1152 // Convert to an ErrorDiagnostic to get location information. This is1153 // done here rather than printMatch/printNoMatch since now we know which1154 // substitution block caused the overflow.1155 Errs = joinErrors(std::move(Errs),1156 handleErrors(1157 Value.takeError(),1158 [&](const OverflowError &E) {1159 return ErrorDiagnostic::get(1160 SM, Substitution->getFromString(),1161 "unable to substitute variable or "1162 "numeric expression: overflow error");1163 },1164 [&SM](const UndefVarError &E) {1165 return ErrorDiagnostic::get(SM, E.getVarName(),1166 E.message());1167 }));1168 continue;1169 }1170 1171 // Plop it into the regex at the adjusted offset.1172 TmpStr.insert(TmpStr.begin() + Substitution->getIndex() + InsertOffset,1173 Value->begin(), Value->end());1174 InsertOffset += Value->size();1175 }1176 if (Errs)1177 return std::move(Errs);1178 1179 // Match the newly constructed regex.1180 RegExToMatch = TmpStr;1181 }1182 1183 SmallVector<StringRef, 4> MatchInfo;1184 unsigned int Flags = Regex::Newline;1185 if (IgnoreCase)1186 Flags |= Regex::IgnoreCase;1187 if (!Regex(RegExToMatch, Flags).match(Buffer, &MatchInfo))1188 return make_error<NotFoundError>();1189 1190 // Successful regex match.1191 assert(!MatchInfo.empty() && "Didn't get any match");1192 StringRef FullMatch = MatchInfo[0];1193 1194 // If this defines any string variables, remember their values.1195 for (const auto &VariableDef : VariableDefs) {1196 assert(VariableDef.second < MatchInfo.size() && "Internal paren error");1197 Context->GlobalVariableTable[VariableDef.first] =1198 MatchInfo[VariableDef.second];1199 }1200 1201 // Like CHECK-NEXT, CHECK-EMPTY's match range is considered to start after1202 // the required preceding newline, which is consumed by the pattern in the1203 // case of CHECK-EMPTY but not CHECK-NEXT.1204 size_t MatchStartSkip = CheckTy == Check::CheckEmpty;1205 Match TheMatch;1206 TheMatch.Pos = FullMatch.data() - Buffer.data() + MatchStartSkip;1207 TheMatch.Len = FullMatch.size() - MatchStartSkip;1208 1209 // If this defines any numeric variables, remember their values.1210 for (const auto &NumericVariableDef : NumericVariableDefs) {1211 const NumericVariableMatch &NumericVariableMatch =1212 NumericVariableDef.getValue();1213 unsigned CaptureParenGroup = NumericVariableMatch.CaptureParenGroup;1214 assert(CaptureParenGroup < MatchInfo.size() && "Internal paren error");1215 NumericVariable *DefinedNumericVariable =1216 NumericVariableMatch.DefinedNumericVariable;1217 1218 StringRef MatchedValue = MatchInfo[CaptureParenGroup];1219 ExpressionFormat Format = DefinedNumericVariable->getImplicitFormat();1220 APInt Value = Format.valueFromStringRepr(MatchedValue, SM);1221 // Numeric variables are already inserted into GlobalNumericVariableTable1222 // during parsing, but clearLocalVars might remove them, so we must1223 // reinsert them. Numeric-variable resolution does not access1224 // GlobalNumericVariableTable; it directly uses a pointer to the variable.1225 // However, other functions (such as clearLocalVars) may require active1226 // variables to be in the table.1227 Context->GlobalNumericVariableTable.try_emplace(NumericVariableDef.getKey(),1228 DefinedNumericVariable);1229 DefinedNumericVariable->setValue(Value, MatchedValue);1230 }1231 1232 return MatchResult(TheMatch, Error::success());1233}1234 1235unsigned Pattern::computeMatchDistance(StringRef Buffer) const {1236 // Just compute the number of matching characters. For regular expressions, we1237 // just compare against the regex itself and hope for the best.1238 //1239 // FIXME: One easy improvement here is have the regex lib generate a single1240 // example regular expression which matches, and use that as the example1241 // string.1242 StringRef ExampleString(FixedStr);1243 if (ExampleString.empty())1244 ExampleString = RegExStr;1245 1246 // Only compare up to the first line in the buffer, or the string size.1247 StringRef BufferPrefix = Buffer.substr(0, ExampleString.size());1248 BufferPrefix = BufferPrefix.split('\n').first;1249 return BufferPrefix.edit_distance(ExampleString);1250}1251 1252void Pattern::printSubstitutions(const SourceMgr &SM, StringRef Buffer,1253 SMRange Range,1254 FileCheckDiag::MatchType MatchTy,1255 std::vector<FileCheckDiag> *Diags) const {1256 // Print what we know about substitutions.1257 if (!Substitutions.empty()) {1258 for (const auto &Substitution : Substitutions) {1259 SmallString<256> Msg;1260 raw_svector_ostream OS(Msg);1261 1262 Expected<std::string> MatchedValue =1263 Substitution->getResultForDiagnostics();1264 // Substitution failures are handled in printNoMatch().1265 if (!MatchedValue) {1266 consumeError(MatchedValue.takeError());1267 continue;1268 }1269 1270 OS << "with \"";1271 OS.write_escaped(Substitution->getFromString()) << "\" equal to ";1272 OS << *MatchedValue;1273 1274 // We report only the start of the match/search range to suggest we are1275 // reporting the substitutions as set at the start of the match/search.1276 // Indicating a non-zero-length range might instead seem to imply that the1277 // substitution matches or was captured from exactly that range.1278 if (Diags)1279 Diags->emplace_back(SM, CheckTy, getLoc(), MatchTy,1280 SMRange(Range.Start, Range.Start), OS.str());1281 else1282 SM.PrintMessage(Range.Start, SourceMgr::DK_Note, OS.str());1283 }1284 }1285}1286 1287void Pattern::printVariableDefs(const SourceMgr &SM,1288 FileCheckDiag::MatchType MatchTy,1289 std::vector<FileCheckDiag> *Diags) const {1290 if (VariableDefs.empty() && NumericVariableDefs.empty())1291 return;1292 // Build list of variable captures.1293 struct VarCapture {1294 StringRef Name;1295 SMRange Range;1296 };1297 SmallVector<VarCapture, 2> VarCaptures;1298 for (const auto &VariableDef : VariableDefs) {1299 VarCapture VC;1300 VC.Name = VariableDef.first;1301 StringRef Value = Context->GlobalVariableTable[VC.Name];1302 SMLoc Start = SMLoc::getFromPointer(Value.data());1303 SMLoc End = SMLoc::getFromPointer(Value.data() + Value.size());1304 VC.Range = SMRange(Start, End);1305 VarCaptures.push_back(VC);1306 }1307 for (const auto &VariableDef : NumericVariableDefs) {1308 VarCapture VC;1309 VC.Name = VariableDef.getKey();1310 std::optional<StringRef> StrValue =1311 VariableDef.getValue().DefinedNumericVariable->getStringValue();1312 if (!StrValue)1313 continue;1314 SMLoc Start = SMLoc::getFromPointer(StrValue->data());1315 SMLoc End = SMLoc::getFromPointer(StrValue->data() + StrValue->size());1316 VC.Range = SMRange(Start, End);1317 VarCaptures.push_back(VC);1318 }1319 // Sort variable captures by the order in which they matched the input.1320 // Ranges shouldn't be overlapping, so we can just compare the start.1321 llvm::sort(VarCaptures, [](const VarCapture &A, const VarCapture &B) {1322 if (&A == &B)1323 return false;1324 assert(A.Range.Start != B.Range.Start &&1325 "unexpected overlapping variable captures");1326 return A.Range.Start.getPointer() < B.Range.Start.getPointer();1327 });1328 // Create notes for the sorted captures.1329 for (const VarCapture &VC : VarCaptures) {1330 SmallString<256> Msg;1331 raw_svector_ostream OS(Msg);1332 OS << "captured var \"" << VC.Name << "\"";1333 if (Diags)1334 Diags->emplace_back(SM, CheckTy, getLoc(), MatchTy, VC.Range, OS.str());1335 else1336 SM.PrintMessage(VC.Range.Start, SourceMgr::DK_Note, OS.str(), VC.Range);1337 }1338}1339 1340static SMRange ProcessMatchResult(FileCheckDiag::MatchType MatchTy,1341 const SourceMgr &SM, SMLoc Loc,1342 Check::FileCheckType CheckTy,1343 StringRef Buffer, size_t Pos, size_t Len,1344 std::vector<FileCheckDiag> *Diags,1345 bool AdjustPrevDiags = false) {1346 SMLoc Start = SMLoc::getFromPointer(Buffer.data() + Pos);1347 SMLoc End = SMLoc::getFromPointer(Buffer.data() + Pos + Len);1348 SMRange Range(Start, End);1349 if (Diags) {1350 if (AdjustPrevDiags) {1351 SMLoc CheckLoc = Diags->rbegin()->CheckLoc;1352 for (auto I = Diags->rbegin(), E = Diags->rend();1353 I != E && I->CheckLoc == CheckLoc; ++I)1354 I->MatchTy = MatchTy;1355 } else1356 Diags->emplace_back(SM, CheckTy, Loc, MatchTy, Range);1357 }1358 return Range;1359}1360 1361void Pattern::printFuzzyMatch(const SourceMgr &SM, StringRef Buffer,1362 std::vector<FileCheckDiag> *Diags) const {1363 // Attempt to find the closest/best fuzzy match. Usually an error happens1364 // because some string in the output didn't exactly match. In these cases, we1365 // would like to show the user a best guess at what "should have" matched, to1366 // save them having to actually check the input manually.1367 size_t NumLinesForward = 0;1368 size_t Best = StringRef::npos;1369 double BestQuality = 0;1370 1371 // Arbitrarily limit quadratic search behavior stemming from long CHECK lines.1372 if (size_t(4096) * size_t(2048) <1373 std::min(size_t(4096), Buffer.size()) *1374 std::max(FixedStr.size(), RegExStr.size()))1375 return;1376 1377 // Use an arbitrary 4k limit on how far we will search.1378 for (size_t i = 0, e = std::min(size_t(4096), Buffer.size()); i != e; ++i) {1379 if (Buffer[i] == '\n')1380 ++NumLinesForward;1381 1382 // Patterns have leading whitespace stripped, so skip whitespace when1383 // looking for something which looks like a pattern.1384 if (Buffer[i] == ' ' || Buffer[i] == '\t')1385 continue;1386 1387 // Compute the "quality" of this match as an arbitrary combination of the1388 // match distance and the number of lines skipped to get to this match.1389 unsigned Distance = computeMatchDistance(Buffer.substr(i));1390 double Quality = Distance + (NumLinesForward / 100.);1391 1392 if (Quality < BestQuality || Best == StringRef::npos) {1393 Best = i;1394 BestQuality = Quality;1395 }1396 }1397 1398 // Print the "possible intended match here" line if we found something1399 // reasonable and not equal to what we showed in the "scanning from here"1400 // line.1401 if (Best && Best != StringRef::npos && BestQuality < 50) {1402 SMRange MatchRange =1403 ProcessMatchResult(FileCheckDiag::MatchFuzzy, SM, getLoc(),1404 getCheckTy(), Buffer, Best, 0, Diags);1405 SM.PrintMessage(MatchRange.Start, SourceMgr::DK_Note,1406 "possible intended match here");1407 1408 // FIXME: If we wanted to be really friendly we would show why the match1409 // failed, as it can be hard to spot simple one character differences.1410 }1411}1412 1413Expected<StringRef>1414FileCheckPatternContext::getPatternVarValue(StringRef VarName) {1415 auto VarIter = GlobalVariableTable.find(VarName);1416 if (VarIter == GlobalVariableTable.end())1417 return make_error<UndefVarError>(VarName);1418 1419 return VarIter->second;1420}1421 1422template <class... Types>1423NumericVariable *FileCheckPatternContext::makeNumericVariable(Types... args) {1424 NumericVariables.push_back(std::make_unique<NumericVariable>(args...));1425 return NumericVariables.back().get();1426}1427 1428Substitution *1429FileCheckPatternContext::makeStringSubstitution(StringRef VarName,1430 size_t InsertIdx) {1431 Substitutions.push_back(1432 std::make_unique<StringSubstitution>(this, VarName, InsertIdx));1433 return Substitutions.back().get();1434}1435 1436Substitution *FileCheckPatternContext::makeNumericSubstitution(1437 StringRef ExpressionStr, std::unique_ptr<Expression> Expression,1438 size_t InsertIdx) {1439 Substitutions.push_back(std::make_unique<NumericSubstitution>(1440 this, ExpressionStr, std::move(Expression), InsertIdx));1441 return Substitutions.back().get();1442}1443 1444size_t Pattern::FindRegexVarEnd(StringRef Str, SourceMgr &SM) {1445 // Offset keeps track of the current offset within the input Str1446 size_t Offset = 0;1447 // [...] Nesting depth1448 size_t BracketDepth = 0;1449 1450 while (!Str.empty()) {1451 if (Str.starts_with("]]") && BracketDepth == 0)1452 return Offset;1453 if (Str[0] == '\\') {1454 // Backslash escapes the next char within regexes, so skip them both.1455 Str = Str.substr(2);1456 Offset += 2;1457 } else {1458 switch (Str[0]) {1459 default:1460 break;1461 case '[':1462 BracketDepth++;1463 break;1464 case ']':1465 if (BracketDepth == 0) {1466 SM.PrintMessage(SMLoc::getFromPointer(Str.data()),1467 SourceMgr::DK_Error,1468 "missing closing \"]\" for regex variable");1469 exit(1);1470 }1471 BracketDepth--;1472 break;1473 }1474 Str = Str.substr(1);1475 Offset++;1476 }1477 }1478 1479 return StringRef::npos;1480}1481 1482StringRef FileCheck::CanonicalizeFile(MemoryBuffer &MB,1483 SmallVectorImpl<char> &OutputBuffer) {1484 OutputBuffer.reserve(MB.getBufferSize());1485 1486 for (const char *Ptr = MB.getBufferStart(), *End = MB.getBufferEnd();1487 Ptr != End; ++Ptr) {1488 // Eliminate trailing dosish \r.1489 if (Ptr <= End - 2 && Ptr[0] == '\r' && Ptr[1] == '\n') {1490 continue;1491 }1492 1493 // If current char is not a horizontal whitespace or if horizontal1494 // whitespace canonicalization is disabled, dump it to output as is.1495 if (Req.NoCanonicalizeWhiteSpace || (*Ptr != ' ' && *Ptr != '\t')) {1496 OutputBuffer.push_back(*Ptr);1497 continue;1498 }1499 1500 // Otherwise, add one space and advance over neighboring space.1501 OutputBuffer.push_back(' ');1502 while (Ptr + 1 != End && (Ptr[1] == ' ' || Ptr[1] == '\t'))1503 ++Ptr;1504 }1505 1506 // Add a null byte and then return all but that byte.1507 OutputBuffer.push_back('\0');1508 return StringRef(OutputBuffer.data(), OutputBuffer.size() - 1);1509}1510 1511FileCheckDiag::FileCheckDiag(const SourceMgr &SM,1512 const Check::FileCheckType &CheckTy,1513 SMLoc CheckLoc, MatchType MatchTy,1514 SMRange InputRange, StringRef Note)1515 : CheckTy(CheckTy), CheckLoc(CheckLoc), MatchTy(MatchTy), Note(Note) {1516 auto Start = SM.getLineAndColumn(InputRange.Start);1517 auto End = SM.getLineAndColumn(InputRange.End);1518 InputStartLine = Start.first;1519 InputStartCol = Start.second;1520 InputEndLine = End.first;1521 InputEndCol = End.second;1522}1523 1524static bool IsPartOfWord(char c) {1525 return (isAlnum(c) || c == '-' || c == '_');1526}1527 1528Check::FileCheckType &Check::FileCheckType::setCount(int C) {1529 assert(Count > 0 && "zero and negative counts are not supported");1530 assert((C == 1 || Kind == CheckPlain) &&1531 "count supported only for plain CHECK directives");1532 Count = C;1533 return *this;1534}1535 1536std::string Check::FileCheckType::getModifiersDescription() const {1537 if (Modifiers.none())1538 return "";1539 std::string Ret;1540 raw_string_ostream OS(Ret);1541 OS << '{';1542 if (isLiteralMatch())1543 OS << "LITERAL";1544 OS << '}';1545 return Ret;1546}1547 1548std::string Check::FileCheckType::getDescription(StringRef Prefix) const {1549 // Append directive modifiers.1550 auto WithModifiers = [this, Prefix](StringRef Str) -> std::string {1551 return (Prefix + Str + getModifiersDescription()).str();1552 };1553 1554 switch (Kind) {1555 case Check::CheckNone:1556 return "invalid";1557 case Check::CheckMisspelled:1558 return "misspelled";1559 case Check::CheckPlain:1560 if (Count > 1)1561 return WithModifiers("-COUNT");1562 return WithModifiers("");1563 case Check::CheckNext:1564 return WithModifiers("-NEXT");1565 case Check::CheckSame:1566 return WithModifiers("-SAME");1567 case Check::CheckNot:1568 return WithModifiers("-NOT");1569 case Check::CheckDAG:1570 return WithModifiers("-DAG");1571 case Check::CheckLabel:1572 return WithModifiers("-LABEL");1573 case Check::CheckEmpty:1574 return WithModifiers("-EMPTY");1575 case Check::CheckComment:1576 return std::string(Prefix);1577 case Check::CheckEOF:1578 return "implicit EOF";1579 case Check::CheckBadNot:1580 return "bad NOT";1581 case Check::CheckBadCount:1582 return "bad COUNT";1583 }1584 llvm_unreachable("unknown FileCheckType");1585}1586 1587static std::pair<Check::FileCheckType, StringRef>1588FindCheckType(const FileCheckRequest &Req, StringRef Buffer, StringRef Prefix,1589 bool &Misspelled) {1590 if (Buffer.size() <= Prefix.size())1591 return {Check::CheckNone, StringRef()};1592 1593 StringRef Rest = Buffer.drop_front(Prefix.size());1594 // Check for comment.1595 if (llvm::is_contained(Req.CommentPrefixes, Prefix)) {1596 if (Rest.consume_front(":"))1597 return {Check::CheckComment, Rest};1598 // Ignore a comment prefix if it has a suffix like "-NOT".1599 return {Check::CheckNone, StringRef()};1600 }1601 1602 auto ConsumeModifiers = [&](Check::FileCheckType Ret)1603 -> std::pair<Check::FileCheckType, StringRef> {1604 if (Rest.consume_front(":"))1605 return {Ret, Rest};1606 if (!Rest.consume_front("{"))1607 return {Check::CheckNone, StringRef()};1608 1609 // Parse the modifiers, speparated by commas.1610 do {1611 // Allow whitespace in modifiers list.1612 Rest = Rest.ltrim();1613 if (Rest.consume_front("LITERAL"))1614 Ret.setLiteralMatch();1615 else1616 return {Check::CheckNone, Rest};1617 // Allow whitespace in modifiers list.1618 Rest = Rest.ltrim();1619 } while (Rest.consume_front(","));1620 if (!Rest.consume_front("}:"))1621 return {Check::CheckNone, Rest};1622 return {Ret, Rest};1623 };1624 1625 // Verify that the prefix is followed by directive modifiers or a colon.1626 if (Rest.consume_front(":"))1627 return {Check::CheckPlain, Rest};1628 if (Rest.front() == '{')1629 return ConsumeModifiers(Check::CheckPlain);1630 1631 if (Rest.consume_front("_"))1632 Misspelled = true;1633 else if (!Rest.consume_front("-"))1634 return {Check::CheckNone, StringRef()};1635 1636 if (Rest.consume_front("COUNT-")) {1637 int64_t Count;1638 if (Rest.consumeInteger(10, Count))1639 // Error happened in parsing integer.1640 return {Check::CheckBadCount, Rest};1641 if (Count <= 0 || Count > INT32_MAX)1642 return {Check::CheckBadCount, Rest};1643 if (Rest.front() != ':' && Rest.front() != '{')1644 return {Check::CheckBadCount, Rest};1645 return ConsumeModifiers(1646 Check::FileCheckType(Check::CheckPlain).setCount(Count));1647 }1648 1649 // You can't combine -NOT with another suffix.1650 if (Rest.starts_with("DAG-NOT:") || Rest.starts_with("NOT-DAG:") ||1651 Rest.starts_with("NEXT-NOT:") || Rest.starts_with("NOT-NEXT:") ||1652 Rest.starts_with("SAME-NOT:") || Rest.starts_with("NOT-SAME:") ||1653 Rest.starts_with("EMPTY-NOT:") || Rest.starts_with("NOT-EMPTY:"))1654 return {Check::CheckBadNot, Rest};1655 1656 if (Rest.consume_front("NEXT"))1657 return ConsumeModifiers(Check::CheckNext);1658 1659 if (Rest.consume_front("SAME"))1660 return ConsumeModifiers(Check::CheckSame);1661 1662 if (Rest.consume_front("NOT"))1663 return ConsumeModifiers(Check::CheckNot);1664 1665 if (Rest.consume_front("DAG"))1666 return ConsumeModifiers(Check::CheckDAG);1667 1668 if (Rest.consume_front("LABEL"))1669 return ConsumeModifiers(Check::CheckLabel);1670 1671 if (Rest.consume_front("EMPTY"))1672 return ConsumeModifiers(Check::CheckEmpty);1673 1674 return {Check::CheckNone, Rest};1675}1676 1677static std::pair<Check::FileCheckType, StringRef>1678FindCheckType(const FileCheckRequest &Req, StringRef Buffer, StringRef Prefix) {1679 bool Misspelled = false;1680 auto Res = FindCheckType(Req, Buffer, Prefix, Misspelled);1681 if (Res.first != Check::CheckNone && Misspelled)1682 return {Check::CheckMisspelled, Res.second};1683 return Res;1684}1685 1686// From the given position, find the next character after the word.1687static size_t SkipWord(StringRef Str, size_t Loc) {1688 while (Loc < Str.size() && IsPartOfWord(Str[Loc]))1689 ++Loc;1690 return Loc;1691}1692 1693static const char *DefaultCheckPrefixes[] = {"CHECK"};1694static const char *DefaultCommentPrefixes[] = {"COM", "RUN"};1695 1696static void addDefaultPrefixes(FileCheckRequest &Req) {1697 if (Req.CheckPrefixes.empty()) {1698 llvm::append_range(Req.CheckPrefixes, DefaultCheckPrefixes);1699 Req.IsDefaultCheckPrefix = true;1700 }1701 if (Req.CommentPrefixes.empty())1702 llvm::append_range(Req.CommentPrefixes, DefaultCommentPrefixes);1703}1704 1705struct PrefixMatcher {1706 /// Prefixes and their first occurrence past the current position.1707 SmallVector<std::pair<StringRef, size_t>> Prefixes;1708 StringRef Input;1709 1710 PrefixMatcher(ArrayRef<StringRef> CheckPrefixes,1711 ArrayRef<StringRef> CommentPrefixes, StringRef Input)1712 : Input(Input) {1713 for (StringRef Prefix : CheckPrefixes)1714 Prefixes.push_back({Prefix, Input.find(Prefix)});1715 for (StringRef Prefix : CommentPrefixes)1716 Prefixes.push_back({Prefix, Input.find(Prefix)});1717 1718 // Sort by descending length.1719 llvm::sort(Prefixes,1720 [](auto A, auto B) { return A.first.size() > B.first.size(); });1721 }1722 1723 /// Find the next match of a prefix in Buffer.1724 /// Returns empty StringRef if not found.1725 StringRef match(StringRef Buffer) {1726 assert(Buffer.data() >= Input.data() &&1727 Buffer.data() + Buffer.size() == Input.data() + Input.size() &&1728 "Buffer must be suffix of Input");1729 1730 size_t From = Buffer.data() - Input.data();1731 StringRef Match;1732 for (auto &[Prefix, Pos] : Prefixes) {1733 // If the last occurrence was before From, find the next one after From.1734 if (Pos < From)1735 Pos = Input.find(Prefix, From);1736 // Find the first prefix with the lowest position.1737 if (Pos != StringRef::npos &&1738 (Match.empty() || size_t(Match.data() - Input.data()) > Pos))1739 Match = StringRef(Input.substr(Pos, Prefix.size()));1740 }1741 return Match;1742 }1743};1744 1745/// Searches the buffer for the first prefix in the prefix regular expression.1746///1747/// This searches the buffer using the provided regular expression, however it1748/// enforces constraints beyond that:1749/// 1) The found prefix must not be a suffix of something that looks like1750/// a valid prefix.1751/// 2) The found prefix must be followed by a valid check type suffix using \c1752/// FindCheckType above.1753///1754/// \returns a pair of StringRefs into the Buffer, which combines:1755/// - the first match of the regular expression to satisfy these two is1756/// returned,1757/// otherwise an empty StringRef is returned to indicate failure.1758/// - buffer rewound to the location right after parsed suffix, for parsing1759/// to continue from1760///1761/// If this routine returns a valid prefix, it will also shrink \p Buffer to1762/// start at the beginning of the returned prefix, increment \p LineNumber for1763/// each new line consumed from \p Buffer, and set \p CheckTy to the type of1764/// check found by examining the suffix.1765///1766/// If no valid prefix is found, the state of Buffer, LineNumber, and CheckTy1767/// is unspecified.1768static std::pair<StringRef, StringRef>1769FindFirstMatchingPrefix(const FileCheckRequest &Req, PrefixMatcher &Matcher,1770 StringRef &Buffer, unsigned &LineNumber,1771 Check::FileCheckType &CheckTy) {1772 while (!Buffer.empty()) {1773 // Find the first (longest) prefix match.1774 StringRef Prefix = Matcher.match(Buffer);1775 if (Prefix.empty())1776 // No match at all, bail.1777 return {StringRef(), StringRef()};1778 1779 assert(Prefix.data() >= Buffer.data() &&1780 Prefix.data() < Buffer.data() + Buffer.size() &&1781 "Prefix doesn't start inside of buffer!");1782 size_t Loc = Prefix.data() - Buffer.data();1783 StringRef Skipped = Buffer.substr(0, Loc);1784 Buffer = Buffer.drop_front(Loc);1785 LineNumber += Skipped.count('\n');1786 1787 // Check that the matched prefix isn't a suffix of some other check-like1788 // word.1789 // FIXME: This is a very ad-hoc check. it would be better handled in some1790 // other way. Among other things it seems hard to distinguish between1791 // intentional and unintentional uses of this feature.1792 if (Skipped.empty() || !IsPartOfWord(Skipped.back())) {1793 // Now extract the type.1794 StringRef AfterSuffix;1795 std::tie(CheckTy, AfterSuffix) = FindCheckType(Req, Buffer, Prefix);1796 1797 // If we've found a valid check type for this prefix, we're done.1798 if (CheckTy != Check::CheckNone)1799 return {Prefix, AfterSuffix};1800 }1801 1802 // If we didn't successfully find a prefix, we need to skip this invalid1803 // prefix and continue scanning. We directly skip the prefix that was1804 // matched and any additional parts of that check-like word.1805 Buffer = Buffer.drop_front(SkipWord(Buffer, Prefix.size()));1806 }1807 1808 // We ran out of buffer while skipping partial matches so give up.1809 return {StringRef(), StringRef()};1810}1811 1812void FileCheckPatternContext::createLineVariable() {1813 assert(!LineVariable && "@LINE pseudo numeric variable already created");1814 StringRef LineName = "@LINE";1815 LineVariable = makeNumericVariable(1816 LineName, ExpressionFormat(ExpressionFormat::Kind::Unsigned));1817 GlobalNumericVariableTable[LineName] = LineVariable;1818}1819 1820FileCheck::FileCheck(FileCheckRequest Req)1821 : Req(Req), PatternContext(std::make_unique<FileCheckPatternContext>()) {}1822 1823FileCheck::~FileCheck() = default;1824 1825bool FileCheck::readCheckFile(1826 SourceMgr &SM, StringRef Buffer,1827 std::pair<unsigned, unsigned> *ImpPatBufferIDRange) {1828 if (ImpPatBufferIDRange)1829 ImpPatBufferIDRange->first = ImpPatBufferIDRange->second = 0;1830 1831 Error DefineError =1832 PatternContext->defineCmdlineVariables(Req.GlobalDefines, SM);1833 if (DefineError) {1834 logAllUnhandledErrors(std::move(DefineError), errs());1835 return true;1836 }1837 1838 PatternContext->createLineVariable();1839 1840 std::vector<FileCheckString::DagNotPrefixInfo> ImplicitNegativeChecks;1841 for (StringRef PatternString : Req.ImplicitCheckNot) {1842 // Create a buffer with fake command line content in order to display the1843 // command line option responsible for the specific implicit CHECK-NOT.1844 std::string Prefix = "-implicit-check-not='";1845 std::string Suffix = "'";1846 std::unique_ptr<MemoryBuffer> CmdLine = MemoryBuffer::getMemBufferCopy(1847 (Prefix + PatternString + Suffix).str(), "command line");1848 1849 StringRef PatternInBuffer =1850 CmdLine->getBuffer().substr(Prefix.size(), PatternString.size());1851 unsigned BufferID = SM.AddNewSourceBuffer(std::move(CmdLine), SMLoc());1852 if (ImpPatBufferIDRange) {1853 if (ImpPatBufferIDRange->first == ImpPatBufferIDRange->second) {1854 ImpPatBufferIDRange->first = BufferID;1855 ImpPatBufferIDRange->second = BufferID + 1;1856 } else {1857 assert(BufferID == ImpPatBufferIDRange->second &&1858 "expected consecutive source buffer IDs");1859 ++ImpPatBufferIDRange->second;1860 }1861 }1862 1863 ImplicitNegativeChecks.emplace_back(1864 Pattern(Check::CheckNot, PatternContext.get()),1865 StringRef("IMPLICIT-CHECK"));1866 ImplicitNegativeChecks.back().DagNotPat.parsePattern(1867 PatternInBuffer, "IMPLICIT-CHECK", SM, Req);1868 }1869 1870 std::vector<FileCheckString::DagNotPrefixInfo> DagNotMatches =1871 ImplicitNegativeChecks;1872 // LineNumber keeps track of the line on which CheckPrefix instances are1873 // found.1874 unsigned LineNumber = 1;1875 1876 addDefaultPrefixes(Req);1877 PrefixMatcher Matcher(Req.CheckPrefixes, Req.CommentPrefixes, Buffer);1878 std::set<StringRef> PrefixesNotFound(Req.CheckPrefixes.begin(),1879 Req.CheckPrefixes.end());1880 const size_t DistinctPrefixes = PrefixesNotFound.size();1881 while (true) {1882 Check::FileCheckType CheckTy;1883 1884 // See if a prefix occurs in the memory buffer.1885 StringRef UsedPrefix;1886 StringRef AfterSuffix;1887 std::tie(UsedPrefix, AfterSuffix) =1888 FindFirstMatchingPrefix(Req, Matcher, Buffer, LineNumber, CheckTy);1889 if (UsedPrefix.empty())1890 break;1891 if (CheckTy != Check::CheckComment)1892 PrefixesNotFound.erase(UsedPrefix);1893 1894 assert(UsedPrefix.data() == Buffer.data() &&1895 "Failed to move Buffer's start forward, or pointed prefix outside "1896 "of the buffer!");1897 assert(AfterSuffix.data() >= Buffer.data() &&1898 AfterSuffix.data() < Buffer.data() + Buffer.size() &&1899 "Parsing after suffix doesn't start inside of buffer!");1900 1901 // Location to use for error messages.1902 const char *UsedPrefixStart = UsedPrefix.data();1903 1904 // Skip the buffer to the end of parsed suffix (or just prefix, if no good1905 // suffix was processed).1906 Buffer = AfterSuffix.empty() ? Buffer.drop_front(UsedPrefix.size())1907 : AfterSuffix;1908 1909 // Complain about misspelled directives.1910 if (CheckTy == Check::CheckMisspelled) {1911 StringRef UsedDirective(UsedPrefix.data(),1912 AfterSuffix.data() - UsedPrefix.data());1913 SM.PrintMessage(SMLoc::getFromPointer(UsedDirective.data()),1914 SourceMgr::DK_Error,1915 "misspelled directive '" + UsedDirective + "'");1916 return true;1917 }1918 1919 // Complain about useful-looking but unsupported suffixes.1920 if (CheckTy == Check::CheckBadNot) {1921 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Error,1922 "unsupported -NOT combo on prefix '" + UsedPrefix + "'");1923 return true;1924 }1925 1926 // Complain about invalid count specification.1927 if (CheckTy == Check::CheckBadCount) {1928 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Error,1929 "invalid count in -COUNT specification on prefix '" +1930 UsedPrefix + "'");1931 return true;1932 }1933 1934 // Okay, we found the prefix, yay. Remember the rest of the line, but ignore1935 // leading whitespace.1936 if (!(Req.NoCanonicalizeWhiteSpace && Req.MatchFullLines))1937 Buffer = Buffer.substr(Buffer.find_first_not_of(" \t"));1938 1939 // Scan ahead to the end of line.1940 size_t EOL = Buffer.find_first_of("\n\r");1941 1942 // Remember the location of the start of the pattern, for diagnostics.1943 SMLoc PatternLoc = SMLoc::getFromPointer(Buffer.data());1944 1945 // Extract the pattern from the buffer.1946 StringRef PatternBuffer = Buffer.substr(0, EOL);1947 Buffer = Buffer.substr(EOL);1948 1949 // If this is a comment, we're done.1950 if (CheckTy == Check::CheckComment)1951 continue;1952 1953 // Parse the pattern.1954 Pattern P(CheckTy, PatternContext.get(), LineNumber);1955 if (P.parsePattern(PatternBuffer, UsedPrefix, SM, Req))1956 return true;1957 1958 // Verify that CHECK-LABEL lines do not define or use variables1959 if ((CheckTy == Check::CheckLabel) && P.hasVariable()) {1960 SM.PrintMessage(1961 SMLoc::getFromPointer(UsedPrefixStart), SourceMgr::DK_Error,1962 "found '" + UsedPrefix + "-LABEL:'"1963 " with variable definition or use");1964 return true;1965 }1966 1967 // Verify that CHECK-NEXT/SAME/EMPTY lines have at least one CHECK line before them.1968 if ((CheckTy == Check::CheckNext || CheckTy == Check::CheckSame ||1969 CheckTy == Check::CheckEmpty) &&1970 CheckStrings.empty()) {1971 StringRef Type = CheckTy == Check::CheckNext1972 ? "NEXT"1973 : CheckTy == Check::CheckEmpty ? "EMPTY" : "SAME";1974 SM.PrintMessage(SMLoc::getFromPointer(UsedPrefixStart),1975 SourceMgr::DK_Error,1976 "found '" + UsedPrefix + "-" + Type +1977 "' without previous '" + UsedPrefix + ": line");1978 return true;1979 }1980 1981 // Handle CHECK-DAG/-NOT.1982 if (CheckTy == Check::CheckDAG || CheckTy == Check::CheckNot) {1983 DagNotMatches.emplace_back(P, UsedPrefix);1984 continue;1985 }1986 1987 // Okay, add the string we captured to the output vector and move on.1988 CheckStrings.emplace_back(std::move(P), UsedPrefix, PatternLoc,1989 std::move(DagNotMatches));1990 DagNotMatches = ImplicitNegativeChecks;1991 }1992 1993 // When there are no used prefixes we report an error except in the case that1994 // no prefix is specified explicitly but -implicit-check-not is specified.1995 const bool NoPrefixesFound = PrefixesNotFound.size() == DistinctPrefixes;1996 const bool SomePrefixesUnexpectedlyNotUsed =1997 !Req.AllowUnusedPrefixes && !PrefixesNotFound.empty();1998 if ((NoPrefixesFound || SomePrefixesUnexpectedlyNotUsed) &&1999 (ImplicitNegativeChecks.empty() || !Req.IsDefaultCheckPrefix)) {2000 errs() << "error: no check strings found with prefix"2001 << (PrefixesNotFound.size() > 1 ? "es " : " ");2002 bool First = true;2003 for (StringRef MissingPrefix : PrefixesNotFound) {2004 if (!First)2005 errs() << ", ";2006 errs() << "\'" << MissingPrefix << ":'";2007 First = false;2008 }2009 errs() << '\n';2010 return true;2011 }2012 2013 // Add an EOF pattern for any trailing --implicit-check-not/CHECK-DAG/-NOTs,2014 // and use the first prefix as a filler for the error message.2015 if (!DagNotMatches.empty()) {2016 CheckStrings.emplace_back(2017 Pattern(Check::CheckEOF, PatternContext.get(), LineNumber + 1),2018 *Req.CheckPrefixes.begin(), SMLoc::getFromPointer(Buffer.data()),2019 std::move(DagNotMatches));2020 }2021 2022 return false;2023}2024 2025/// Returns either (1) \c ErrorSuccess if there was no error or (2)2026/// \c ErrorReported if an error was reported, such as an unexpected match.2027static Error printMatch(bool ExpectedMatch, const SourceMgr &SM,2028 StringRef Prefix, SMLoc Loc, const Pattern &Pat,2029 int MatchedCount, StringRef Buffer,2030 Pattern::MatchResult MatchResult,2031 const FileCheckRequest &Req,2032 std::vector<FileCheckDiag> *Diags) {2033 // Suppress some verbosity if there's no error.2034 bool HasError = !ExpectedMatch || MatchResult.TheError;2035 bool PrintDiag = true;2036 if (!HasError) {2037 if (!Req.Verbose)2038 return ErrorReported::reportedOrSuccess(HasError);2039 if (!Req.VerboseVerbose && Pat.getCheckTy() == Check::CheckEOF)2040 return ErrorReported::reportedOrSuccess(HasError);2041 // Due to their verbosity, we don't print verbose diagnostics here if we're2042 // gathering them for Diags to be rendered elsewhere, but we always print2043 // other diagnostics.2044 PrintDiag = !Diags;2045 }2046 2047 // Add "found" diagnostic, substitutions, and variable definitions to Diags.2048 FileCheckDiag::MatchType MatchTy = ExpectedMatch2049 ? FileCheckDiag::MatchFoundAndExpected2050 : FileCheckDiag::MatchFoundButExcluded;2051 SMRange MatchRange = ProcessMatchResult(MatchTy, SM, Loc, Pat.getCheckTy(),2052 Buffer, MatchResult.TheMatch->Pos,2053 MatchResult.TheMatch->Len, Diags);2054 if (Diags) {2055 Pat.printSubstitutions(SM, Buffer, MatchRange, MatchTy, Diags);2056 Pat.printVariableDefs(SM, MatchTy, Diags);2057 }2058 if (!PrintDiag) {2059 assert(!HasError && "expected to report more diagnostics for error");2060 return ErrorReported::reportedOrSuccess(HasError);2061 }2062 2063 // Print the match.2064 std::string Message = formatv("{0}: {1} string found in input",2065 Pat.getCheckTy().getDescription(Prefix),2066 (ExpectedMatch ? "expected" : "excluded"))2067 .str();2068 if (Pat.getCount() > 1)2069 Message += formatv(" ({0} out of {1})", MatchedCount, Pat.getCount()).str();2070 SM.PrintMessage(2071 Loc, ExpectedMatch ? SourceMgr::DK_Remark : SourceMgr::DK_Error, Message);2072 SM.PrintMessage(MatchRange.Start, SourceMgr::DK_Note, "found here",2073 {MatchRange});2074 2075 // Print additional information, which can be useful even if there are errors.2076 Pat.printSubstitutions(SM, Buffer, MatchRange, MatchTy, nullptr);2077 Pat.printVariableDefs(SM, MatchTy, nullptr);2078 2079 // Print errors and add them to Diags. We report these errors after the match2080 // itself because we found them after the match. If we had found them before2081 // the match, we'd be in printNoMatch.2082 handleAllErrors(std::move(MatchResult.TheError),2083 [&](const ErrorDiagnostic &E) {2084 E.log(errs());2085 if (Diags) {2086 Diags->emplace_back(SM, Pat.getCheckTy(), Loc,2087 FileCheckDiag::MatchFoundErrorNote,2088 E.getRange(), E.getMessage().str());2089 }2090 });2091 return ErrorReported::reportedOrSuccess(HasError);2092}2093 2094/// Returns either (1) \c ErrorSuccess if there was no error, or (2)2095/// \c ErrorReported if an error was reported, such as an expected match not2096/// found.2097static Error printNoMatch(bool ExpectedMatch, const SourceMgr &SM,2098 StringRef Prefix, SMLoc Loc, const Pattern &Pat,2099 int MatchedCount, StringRef Buffer, Error MatchError,2100 bool VerboseVerbose,2101 std::vector<FileCheckDiag> *Diags) {2102 // Print any pattern errors, and record them to be added to Diags later.2103 bool HasError = ExpectedMatch;2104 bool HasPatternError = false;2105 FileCheckDiag::MatchType MatchTy = ExpectedMatch2106 ? FileCheckDiag::MatchNoneButExpected2107 : FileCheckDiag::MatchNoneAndExcluded;2108 SmallVector<std::string, 4> ErrorMsgs;2109 handleAllErrors(2110 std::move(MatchError),2111 [&](const ErrorDiagnostic &E) {2112 HasError = HasPatternError = true;2113 MatchTy = FileCheckDiag::MatchNoneForInvalidPattern;2114 E.log(errs());2115 if (Diags)2116 ErrorMsgs.push_back(E.getMessage().str());2117 },2118 // NotFoundError is why printNoMatch was invoked.2119 [](const NotFoundError &E) {});2120 2121 // Suppress some verbosity if there's no error.2122 bool PrintDiag = true;2123 if (!HasError) {2124 if (!VerboseVerbose)2125 return ErrorReported::reportedOrSuccess(HasError);2126 // Due to their verbosity, we don't print verbose diagnostics here if we're2127 // gathering them for Diags to be rendered elsewhere, but we always print2128 // other diagnostics.2129 PrintDiag = !Diags;2130 }2131 2132 // Add "not found" diagnostic, substitutions, and pattern errors to Diags.2133 //2134 // We handle Diags a little differently than the errors we print directly:2135 // we add the "not found" diagnostic to Diags even if there are pattern2136 // errors. The reason is that we need to attach pattern errors as notes2137 // somewhere in the input, and the input search range from the "not found"2138 // diagnostic is all we have to anchor them.2139 SMRange SearchRange = ProcessMatchResult(MatchTy, SM, Loc, Pat.getCheckTy(),2140 Buffer, 0, Buffer.size(), Diags);2141 if (Diags) {2142 SMRange NoteRange = SMRange(SearchRange.Start, SearchRange.Start);2143 for (StringRef ErrorMsg : ErrorMsgs)2144 Diags->emplace_back(SM, Pat.getCheckTy(), Loc, MatchTy, NoteRange,2145 ErrorMsg);2146 Pat.printSubstitutions(SM, Buffer, SearchRange, MatchTy, Diags);2147 }2148 if (!PrintDiag) {2149 assert(!HasError && "expected to report more diagnostics for error");2150 return ErrorReported::reportedOrSuccess(HasError);2151 }2152 2153 // Print "not found" diagnostic, except that's implied if we already printed a2154 // pattern error.2155 if (!HasPatternError) {2156 std::string Message = formatv("{0}: {1} string not found in input",2157 Pat.getCheckTy().getDescription(Prefix),2158 (ExpectedMatch ? "expected" : "excluded"))2159 .str();2160 if (Pat.getCount() > 1)2161 Message +=2162 formatv(" ({0} out of {1})", MatchedCount, Pat.getCount()).str();2163 SM.PrintMessage(Loc,2164 ExpectedMatch ? SourceMgr::DK_Error : SourceMgr::DK_Remark,2165 Message);2166 SM.PrintMessage(SearchRange.Start, SourceMgr::DK_Note,2167 "scanning from here");2168 }2169 2170 // Print additional information, which can be useful even after a pattern2171 // error.2172 Pat.printSubstitutions(SM, Buffer, SearchRange, MatchTy, nullptr);2173 if (ExpectedMatch)2174 Pat.printFuzzyMatch(SM, Buffer, Diags);2175 return ErrorReported::reportedOrSuccess(HasError);2176}2177 2178/// Returns either (1) \c ErrorSuccess if there was no error, or (2)2179/// \c ErrorReported if an error was reported.2180static Error reportMatchResult(bool ExpectedMatch, const SourceMgr &SM,2181 StringRef Prefix, SMLoc Loc, const Pattern &Pat,2182 int MatchedCount, StringRef Buffer,2183 Pattern::MatchResult MatchResult,2184 const FileCheckRequest &Req,2185 std::vector<FileCheckDiag> *Diags) {2186 if (MatchResult.TheMatch)2187 return printMatch(ExpectedMatch, SM, Prefix, Loc, Pat, MatchedCount, Buffer,2188 std::move(MatchResult), Req, Diags);2189 return printNoMatch(ExpectedMatch, SM, Prefix, Loc, Pat, MatchedCount, Buffer,2190 std::move(MatchResult.TheError), Req.VerboseVerbose,2191 Diags);2192}2193 2194/// Counts the number of newlines in the specified range.2195static unsigned CountNumNewlinesBetween(StringRef Range,2196 const char *&FirstNewLine) {2197 unsigned NumNewLines = 0;2198 while (true) {2199 // Scan for newline.2200 Range = Range.substr(Range.find_first_of("\n\r"));2201 if (Range.empty())2202 return NumNewLines;2203 2204 ++NumNewLines;2205 2206 // Handle \n\r and \r\n as a single newline.2207 if (Range.size() > 1 && (Range[1] == '\n' || Range[1] == '\r') &&2208 (Range[0] != Range[1]))2209 Range = Range.substr(1);2210 Range = Range.substr(1);2211 2212 if (NumNewLines == 1)2213 FirstNewLine = Range.begin();2214 }2215}2216 2217size_t FileCheckString::Check(const SourceMgr &SM, StringRef Buffer,2218 bool IsLabelScanMode, size_t &MatchLen,2219 FileCheckRequest &Req,2220 std::vector<FileCheckDiag> *Diags) const {2221 size_t LastPos = 0;2222 std::vector<const DagNotPrefixInfo *> NotStrings;2223 2224 // IsLabelScanMode is true when we are scanning forward to find CHECK-LABEL2225 // bounds; we have not processed variable definitions within the bounded block2226 // yet so cannot handle any final CHECK-DAG yet; this is handled when going2227 // over the block again (including the last CHECK-LABEL) in normal mode.2228 if (!IsLabelScanMode) {2229 // Match "dag strings" (with mixed "not strings" if any).2230 LastPos = CheckDag(SM, Buffer, NotStrings, Req, Diags);2231 if (LastPos == StringRef::npos)2232 return StringRef::npos;2233 }2234 2235 // Match itself from the last position after matching CHECK-DAG.2236 size_t LastMatchEnd = LastPos;2237 size_t FirstMatchPos = 0;2238 // Go match the pattern Count times. Majority of patterns only match with2239 // count 1 though.2240 assert(Pat.getCount() != 0 && "pattern count can not be zero");2241 for (int i = 1; i <= Pat.getCount(); i++) {2242 StringRef MatchBuffer = Buffer.substr(LastMatchEnd);2243 // get a match at current start point2244 Pattern::MatchResult MatchResult = Pat.match(MatchBuffer, SM);2245 2246 // report2247 if (Error Err = reportMatchResult(/*ExpectedMatch=*/true, SM, Prefix, Loc,2248 Pat, i, MatchBuffer,2249 std::move(MatchResult), Req, Diags)) {2250 cantFail(handleErrors(std::move(Err), [&](const ErrorReported &E) {}));2251 return StringRef::npos;2252 }2253 2254 size_t MatchPos = MatchResult.TheMatch->Pos;2255 if (i == 1)2256 FirstMatchPos = LastPos + MatchPos;2257 2258 // move start point after the match2259 LastMatchEnd += MatchPos + MatchResult.TheMatch->Len;2260 }2261 // Full match len counts from first match pos.2262 MatchLen = LastMatchEnd - FirstMatchPos;2263 2264 // Similar to the above, in "label-scan mode" we can't yet handle CHECK-NEXT2265 // or CHECK-NOT2266 if (!IsLabelScanMode) {2267 size_t MatchPos = FirstMatchPos - LastPos;2268 StringRef MatchBuffer = Buffer.substr(LastPos);2269 StringRef SkippedRegion = Buffer.substr(LastPos, MatchPos);2270 2271 // If this check is a "CHECK-NEXT", verify that the previous match was on2272 // the previous line (i.e. that there is one newline between them).2273 if (CheckNext(SM, SkippedRegion)) {2274 ProcessMatchResult(FileCheckDiag::MatchFoundButWrongLine, SM, Loc,2275 Pat.getCheckTy(), MatchBuffer, MatchPos, MatchLen,2276 Diags, Req.Verbose);2277 return StringRef::npos;2278 }2279 2280 // If this check is a "CHECK-SAME", verify that the previous match was on2281 // the same line (i.e. that there is no newline between them).2282 if (CheckSame(SM, SkippedRegion)) {2283 ProcessMatchResult(FileCheckDiag::MatchFoundButWrongLine, SM, Loc,2284 Pat.getCheckTy(), MatchBuffer, MatchPos, MatchLen,2285 Diags, Req.Verbose);2286 return StringRef::npos;2287 }2288 2289 // If this match had "not strings", verify that they don't exist in the2290 // skipped region.2291 if (CheckNot(SM, SkippedRegion, NotStrings, Req, Diags))2292 return StringRef::npos;2293 }2294 2295 return FirstMatchPos;2296}2297 2298bool FileCheckString::CheckNext(const SourceMgr &SM, StringRef Buffer) const {2299 if (Pat.getCheckTy() != Check::CheckNext &&2300 Pat.getCheckTy() != Check::CheckEmpty)2301 return false;2302 2303 Twine CheckName =2304 Prefix +2305 Twine(Pat.getCheckTy() == Check::CheckEmpty ? "-EMPTY" : "-NEXT");2306 2307 // Count the number of newlines between the previous match and this one.2308 const char *FirstNewLine = nullptr;2309 unsigned NumNewLines = CountNumNewlinesBetween(Buffer, FirstNewLine);2310 2311 if (NumNewLines == 0) {2312 SM.PrintMessage(Loc, SourceMgr::DK_Error,2313 CheckName + ": is on the same line as previous match");2314 SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), SourceMgr::DK_Note,2315 "'next' match was here");2316 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,2317 "previous match ended here");2318 return true;2319 }2320 2321 if (NumNewLines != 1) {2322 SM.PrintMessage(Loc, SourceMgr::DK_Error,2323 CheckName +2324 ": is not on the line after the previous match");2325 SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), SourceMgr::DK_Note,2326 "'next' match was here");2327 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,2328 "previous match ended here");2329 SM.PrintMessage(SMLoc::getFromPointer(FirstNewLine), SourceMgr::DK_Note,2330 "non-matching line after previous match is here");2331 return true;2332 }2333 2334 return false;2335}2336 2337bool FileCheckString::CheckSame(const SourceMgr &SM, StringRef Buffer) const {2338 if (Pat.getCheckTy() != Check::CheckSame)2339 return false;2340 2341 // Count the number of newlines between the previous match and this one.2342 const char *FirstNewLine = nullptr;2343 unsigned NumNewLines = CountNumNewlinesBetween(Buffer, FirstNewLine);2344 2345 if (NumNewLines != 0) {2346 SM.PrintMessage(Loc, SourceMgr::DK_Error,2347 Prefix +2348 "-SAME: is not on the same line as the previous match");2349 SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), SourceMgr::DK_Note,2350 "'next' match was here");2351 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,2352 "previous match ended here");2353 return true;2354 }2355 2356 return false;2357}2358 2359bool FileCheckString::CheckNot(2360 const SourceMgr &SM, StringRef Buffer,2361 const std::vector<const DagNotPrefixInfo *> &NotStrings,2362 const FileCheckRequest &Req, std::vector<FileCheckDiag> *Diags) const {2363 bool DirectiveFail = false;2364 for (auto NotInfo : NotStrings) {2365 assert((NotInfo->DagNotPat.getCheckTy() == Check::CheckNot) &&2366 "Expect CHECK-NOT!");2367 Pattern::MatchResult MatchResult = NotInfo->DagNotPat.match(Buffer, SM);2368 if (Error Err = reportMatchResult(2369 /*ExpectedMatch=*/false, SM, NotInfo->DagNotPrefix,2370 NotInfo->DagNotPat.getLoc(), NotInfo->DagNotPat, 1, Buffer,2371 std::move(MatchResult), Req, Diags)) {2372 cantFail(handleErrors(std::move(Err), [&](const ErrorReported &E) {}));2373 DirectiveFail = true;2374 continue;2375 }2376 }2377 return DirectiveFail;2378}2379 2380size_t2381FileCheckString::CheckDag(const SourceMgr &SM, StringRef Buffer,2382 std::vector<const DagNotPrefixInfo *> &NotStrings,2383 const FileCheckRequest &Req,2384 std::vector<FileCheckDiag> *Diags) const {2385 if (DagNotStrings.empty())2386 return 0;2387 2388 // The start of the search range.2389 size_t StartPos = 0;2390 2391 struct MatchRange {2392 size_t Pos;2393 size_t End;2394 };2395 // A sorted list of ranges for non-overlapping CHECK-DAG matches. Match2396 // ranges are erased from this list once they are no longer in the search2397 // range.2398 std::list<MatchRange> MatchRanges;2399 2400 // We need PatItr and PatEnd later for detecting the end of a CHECK-DAG2401 // group, so we don't use a range-based for loop here.2402 for (auto PatItr = DagNotStrings.begin(), PatEnd = DagNotStrings.end();2403 PatItr != PatEnd; ++PatItr) {2404 const Pattern &Pat = PatItr->DagNotPat;2405 const StringRef DNPrefix = PatItr->DagNotPrefix;2406 assert((Pat.getCheckTy() == Check::CheckDAG ||2407 Pat.getCheckTy() == Check::CheckNot) &&2408 "Invalid CHECK-DAG or CHECK-NOT!");2409 2410 if (Pat.getCheckTy() == Check::CheckNot) {2411 NotStrings.push_back(&*PatItr);2412 continue;2413 }2414 2415 assert((Pat.getCheckTy() == Check::CheckDAG) && "Expect CHECK-DAG!");2416 2417 // CHECK-DAG always matches from the start.2418 size_t MatchLen = 0, MatchPos = StartPos;2419 2420 // Search for a match that doesn't overlap a previous match in this2421 // CHECK-DAG group.2422 for (auto MI = MatchRanges.begin(), ME = MatchRanges.end(); true; ++MI) {2423 StringRef MatchBuffer = Buffer.substr(MatchPos);2424 Pattern::MatchResult MatchResult = Pat.match(MatchBuffer, SM);2425 // With a group of CHECK-DAGs, a single mismatching means the match on2426 // that group of CHECK-DAGs fails immediately.2427 if (MatchResult.TheError || Req.VerboseVerbose) {2428 if (Error Err = reportMatchResult(/*ExpectedMatch=*/true, SM, DNPrefix,2429 Pat.getLoc(), Pat, 1, MatchBuffer,2430 std::move(MatchResult), Req, Diags)) {2431 cantFail(2432 handleErrors(std::move(Err), [&](const ErrorReported &E) {}));2433 return StringRef::npos;2434 }2435 }2436 MatchLen = MatchResult.TheMatch->Len;2437 // Re-calc it as the offset relative to the start of the original2438 // string.2439 MatchPos += MatchResult.TheMatch->Pos;2440 MatchRange M{MatchPos, MatchPos + MatchLen};2441 if (Req.AllowDeprecatedDagOverlap) {2442 // We don't need to track all matches in this mode, so we just maintain2443 // one match range that encompasses the current CHECK-DAG group's2444 // matches.2445 if (MatchRanges.empty())2446 MatchRanges.insert(MatchRanges.end(), M);2447 else {2448 auto Block = MatchRanges.begin();2449 Block->Pos = std::min(Block->Pos, M.Pos);2450 Block->End = std::max(Block->End, M.End);2451 }2452 break;2453 }2454 // Iterate previous matches until overlapping match or insertion point.2455 bool Overlap = false;2456 for (; MI != ME; ++MI) {2457 if (M.Pos < MI->End) {2458 // !Overlap => New match has no overlap and is before this old match.2459 // Overlap => New match overlaps this old match.2460 Overlap = MI->Pos < M.End;2461 break;2462 }2463 }2464 if (!Overlap) {2465 // Insert non-overlapping match into list.2466 MatchRanges.insert(MI, M);2467 break;2468 }2469 if (Req.VerboseVerbose) {2470 // Due to their verbosity, we don't print verbose diagnostics here if2471 // we're gathering them for a different rendering, but we always print2472 // other diagnostics.2473 if (!Diags) {2474 SMLoc OldStart = SMLoc::getFromPointer(Buffer.data() + MI->Pos);2475 SMLoc OldEnd = SMLoc::getFromPointer(Buffer.data() + MI->End);2476 SMRange OldRange(OldStart, OldEnd);2477 SM.PrintMessage(OldStart, SourceMgr::DK_Note,2478 "match discarded, overlaps earlier DAG match here",2479 {OldRange});2480 } else {2481 SMLoc CheckLoc = Diags->rbegin()->CheckLoc;2482 for (auto I = Diags->rbegin(), E = Diags->rend();2483 I != E && I->CheckLoc == CheckLoc; ++I)2484 I->MatchTy = FileCheckDiag::MatchFoundButDiscarded;2485 }2486 }2487 MatchPos = MI->End;2488 }2489 if (!Req.VerboseVerbose)2490 cantFail(printMatch(2491 /*ExpectedMatch=*/true, SM, DNPrefix, Pat.getLoc(), Pat, 1, Buffer,2492 Pattern::MatchResult(MatchPos, MatchLen, Error::success()), Req,2493 Diags));2494 2495 // Handle the end of a CHECK-DAG group.2496 if (std::next(PatItr) == PatEnd ||2497 std::next(PatItr)->DagNotPat.getCheckTy() == Check::CheckNot) {2498 if (!NotStrings.empty()) {2499 // If there are CHECK-NOTs between two CHECK-DAGs or from CHECK to2500 // CHECK-DAG, verify that there are no 'not' strings occurred in that2501 // region.2502 StringRef SkippedRegion =2503 Buffer.slice(StartPos, MatchRanges.begin()->Pos);2504 if (CheckNot(SM, SkippedRegion, NotStrings, Req, Diags))2505 return StringRef::npos;2506 // Clear "not strings".2507 NotStrings.clear();2508 }2509 // All subsequent CHECK-DAGs and CHECK-NOTs should be matched from the2510 // end of this CHECK-DAG group's match range.2511 StartPos = MatchRanges.rbegin()->End;2512 // Don't waste time checking for (impossible) overlaps before that.2513 MatchRanges.clear();2514 }2515 }2516 2517 return StartPos;2518}2519 2520static bool ValidatePrefixes(StringRef Kind, StringSet<> &UniquePrefixes,2521 ArrayRef<StringRef> SuppliedPrefixes) {2522 for (StringRef Prefix : SuppliedPrefixes) {2523 if (Prefix.empty()) {2524 errs() << "error: supplied " << Kind << " prefix must not be the empty "2525 << "string\n";2526 return false;2527 }2528 static const Regex Validator("^[a-zA-Z0-9_-]*$");2529 if (!Validator.match(Prefix)) {2530 errs() << "error: supplied " << Kind << " prefix must start with a "2531 << "letter and contain only alphanumeric characters, hyphens, and "2532 << "underscores: '" << Prefix << "'\n";2533 return false;2534 }2535 if (!UniquePrefixes.insert(Prefix).second) {2536 errs() << "error: supplied " << Kind << " prefix must be unique among "2537 << "check and comment prefixes: '" << Prefix << "'\n";2538 return false;2539 }2540 }2541 return true;2542}2543 2544bool FileCheck::ValidateCheckPrefixes() {2545 StringSet<> UniquePrefixes;2546 // Add default prefixes to catch user-supplied duplicates of them below.2547 if (Req.CheckPrefixes.empty())2548 UniquePrefixes.insert_range(DefaultCheckPrefixes);2549 if (Req.CommentPrefixes.empty())2550 UniquePrefixes.insert_range(DefaultCommentPrefixes);2551 // Do not validate the default prefixes, or diagnostics about duplicates might2552 // incorrectly indicate that they were supplied by the user.2553 if (!ValidatePrefixes("check", UniquePrefixes, Req.CheckPrefixes))2554 return false;2555 if (!ValidatePrefixes("comment", UniquePrefixes, Req.CommentPrefixes))2556 return false;2557 return true;2558}2559 2560Error FileCheckPatternContext::defineCmdlineVariables(2561 ArrayRef<StringRef> CmdlineDefines, SourceMgr &SM) {2562 assert(GlobalVariableTable.empty() && GlobalNumericVariableTable.empty() &&2563 "Overriding defined variable with command-line variable definitions");2564 2565 if (CmdlineDefines.empty())2566 return Error::success();2567 2568 // Create a string representing the vector of command-line definitions. Each2569 // definition is on its own line and prefixed with a definition number to2570 // clarify which definition a given diagnostic corresponds to.2571 unsigned I = 0;2572 Error Errs = Error::success();2573 std::string CmdlineDefsDiag;2574 SmallVector<std::pair<size_t, size_t>, 4> CmdlineDefsIndices;2575 for (StringRef CmdlineDef : CmdlineDefines) {2576 std::string DefPrefix = ("Global define #" + Twine(++I) + ": ").str();2577 size_t EqIdx = CmdlineDef.find('=');2578 if (EqIdx == StringRef::npos) {2579 CmdlineDefsIndices.push_back(std::make_pair(CmdlineDefsDiag.size(), 0));2580 continue;2581 }2582 // Numeric variable definition.2583 if (CmdlineDef[0] == '#') {2584 // Append a copy of the command-line definition adapted to use the same2585 // format as in the input file to be able to reuse2586 // parseNumericSubstitutionBlock.2587 CmdlineDefsDiag += (DefPrefix + CmdlineDef + " (parsed as: [[").str();2588 std::string SubstitutionStr = std::string(CmdlineDef);2589 SubstitutionStr[EqIdx] = ':';2590 CmdlineDefsIndices.push_back(2591 std::make_pair(CmdlineDefsDiag.size(), SubstitutionStr.size()));2592 CmdlineDefsDiag += (SubstitutionStr + Twine("]])\n")).str();2593 } else {2594 CmdlineDefsDiag += DefPrefix;2595 CmdlineDefsIndices.push_back(2596 std::make_pair(CmdlineDefsDiag.size(), CmdlineDef.size()));2597 CmdlineDefsDiag += (CmdlineDef + "\n").str();2598 }2599 }2600 2601 // Create a buffer with fake command line content in order to display2602 // parsing diagnostic with location information and point to the2603 // global definition with invalid syntax.2604 std::unique_ptr<MemoryBuffer> CmdLineDefsDiagBuffer =2605 MemoryBuffer::getMemBufferCopy(CmdlineDefsDiag, "Global defines");2606 StringRef CmdlineDefsDiagRef = CmdLineDefsDiagBuffer->getBuffer();2607 SM.AddNewSourceBuffer(std::move(CmdLineDefsDiagBuffer), SMLoc());2608 2609 for (std::pair<size_t, size_t> CmdlineDefIndices : CmdlineDefsIndices) {2610 StringRef CmdlineDef = CmdlineDefsDiagRef.substr(CmdlineDefIndices.first,2611 CmdlineDefIndices.second);2612 if (CmdlineDef.empty()) {2613 Errs = joinErrors(2614 std::move(Errs),2615 ErrorDiagnostic::get(SM, CmdlineDef,2616 "missing equal sign in global definition"));2617 continue;2618 }2619 2620 // Numeric variable definition.2621 if (CmdlineDef[0] == '#') {2622 // Now parse the definition both to check that the syntax is correct and2623 // to create the necessary class instance.2624 StringRef CmdlineDefExpr = CmdlineDef.substr(1);2625 std::optional<NumericVariable *> DefinedNumericVariable;2626 Expected<std::unique_ptr<Expression>> ExpressionResult =2627 Pattern::parseNumericSubstitutionBlock(CmdlineDefExpr,2628 DefinedNumericVariable, false,2629 std::nullopt, this, SM);2630 if (!ExpressionResult) {2631 Errs = joinErrors(std::move(Errs), ExpressionResult.takeError());2632 continue;2633 }2634 std::unique_ptr<Expression> Expression = std::move(*ExpressionResult);2635 // Now evaluate the expression whose value this variable should be set2636 // to, since the expression of a command-line variable definition should2637 // only use variables defined earlier on the command-line. If not, this2638 // is an error and we report it.2639 Expected<APInt> Value = Expression->getAST()->eval();2640 if (!Value) {2641 Errs = joinErrors(std::move(Errs), Value.takeError());2642 continue;2643 }2644 2645 assert(DefinedNumericVariable && "No variable defined");2646 (*DefinedNumericVariable)->setValue(*Value);2647 2648 // Record this variable definition.2649 GlobalNumericVariableTable[(*DefinedNumericVariable)->getName()] =2650 *DefinedNumericVariable;2651 } else {2652 // String variable definition.2653 std::pair<StringRef, StringRef> CmdlineNameVal = CmdlineDef.split('=');2654 StringRef CmdlineName = CmdlineNameVal.first;2655 StringRef OrigCmdlineName = CmdlineName;2656 Expected<Pattern::VariableProperties> ParseVarResult =2657 Pattern::parseVariable(CmdlineName, SM);2658 if (!ParseVarResult) {2659 Errs = joinErrors(std::move(Errs), ParseVarResult.takeError());2660 continue;2661 }2662 // Check that CmdlineName does not denote a pseudo variable is only2663 // composed of the parsed numeric variable. This catches cases like2664 // "FOO+2" in a "FOO+2=10" definition.2665 if (ParseVarResult->IsPseudo || !CmdlineName.empty()) {2666 Errs = joinErrors(std::move(Errs),2667 ErrorDiagnostic::get(2668 SM, OrigCmdlineName,2669 "invalid name in string variable definition '" +2670 OrigCmdlineName + "'"));2671 continue;2672 }2673 StringRef Name = ParseVarResult->Name;2674 2675 // Detect collisions between string and numeric variables when the former2676 // is created later than the latter.2677 if (GlobalNumericVariableTable.contains(Name)) {2678 Errs = joinErrors(std::move(Errs),2679 ErrorDiagnostic::get(SM, Name,2680 "numeric variable with name '" +2681 Name + "' already exists"));2682 continue;2683 }2684 GlobalVariableTable.insert(CmdlineNameVal);2685 // Mark the string variable as defined to detect collisions between2686 // string and numeric variables in defineCmdlineVariables when the latter2687 // is created later than the former. We cannot reuse GlobalVariableTable2688 // for this by populating it with an empty string since we would then2689 // lose the ability to detect the use of an undefined variable in2690 // match().2691 DefinedVariableTable[Name] = true;2692 }2693 }2694 2695 return Errs;2696}2697 2698void FileCheckPatternContext::clearLocalVars() {2699 SmallVector<StringRef, 16> LocalPatternVars, LocalNumericVars;2700 for (const StringMapEntry<StringRef> &Var : GlobalVariableTable)2701 if (Var.first()[0] != '$')2702 LocalPatternVars.push_back(Var.first());2703 2704 // Numeric substitution reads the value of a variable directly, not via2705 // GlobalNumericVariableTable. Therefore, we clear local variables by2706 // clearing their value which will lead to a numeric substitution failure. We2707 // also mark the variable for removal from GlobalNumericVariableTable since2708 // this is what defineCmdlineVariables checks to decide that no global2709 // variable has been defined.2710 for (const auto &Var : GlobalNumericVariableTable)2711 if (Var.first()[0] != '$') {2712 Var.getValue()->clearValue();2713 LocalNumericVars.push_back(Var.first());2714 }2715 2716 for (const auto &Var : LocalPatternVars)2717 GlobalVariableTable.erase(Var);2718 for (const auto &Var : LocalNumericVars)2719 GlobalNumericVariableTable.erase(Var);2720}2721 2722bool FileCheck::checkInput(SourceMgr &SM, StringRef Buffer,2723 std::vector<FileCheckDiag> *Diags) {2724 bool ChecksFailed = false;2725 2726 unsigned i = 0, j = 0, e = CheckStrings.size();2727 while (true) {2728 StringRef CheckRegion;2729 if (j == e) {2730 CheckRegion = Buffer;2731 } else {2732 const FileCheckString &CheckLabelStr = CheckStrings[j];2733 if (CheckLabelStr.Pat.getCheckTy() != Check::CheckLabel) {2734 ++j;2735 continue;2736 }2737 2738 // Scan to next CHECK-LABEL match, ignoring CHECK-NOT and CHECK-DAG2739 size_t MatchLabelLen = 0;2740 size_t MatchLabelPos =2741 CheckLabelStr.Check(SM, Buffer, true, MatchLabelLen, Req, Diags);2742 if (MatchLabelPos == StringRef::npos)2743 // Immediately bail if CHECK-LABEL fails, nothing else we can do.2744 return false;2745 2746 CheckRegion = Buffer.substr(0, MatchLabelPos + MatchLabelLen);2747 Buffer = Buffer.substr(MatchLabelPos + MatchLabelLen);2748 ++j;2749 }2750 2751 // Do not clear the first region as it's the one before the first2752 // CHECK-LABEL and it would clear variables defined on the command-line2753 // before they get used.2754 if (i != 0 && Req.EnableVarScope)2755 PatternContext->clearLocalVars();2756 2757 for (; i != j; ++i) {2758 const FileCheckString &CheckStr = CheckStrings[i];2759 2760 // Check each string within the scanned region, including a second check2761 // of any final CHECK-LABEL (to verify CHECK-NOT and CHECK-DAG)2762 size_t MatchLen = 0;2763 size_t MatchPos =2764 CheckStr.Check(SM, CheckRegion, false, MatchLen, Req, Diags);2765 2766 if (MatchPos == StringRef::npos) {2767 ChecksFailed = true;2768 i = j;2769 break;2770 }2771 2772 CheckRegion = CheckRegion.substr(MatchPos + MatchLen);2773 }2774 2775 if (j == e)2776 break;2777 }2778 2779 // Success if no checks failed.2780 return !ChecksFailed;2781}2782