xref: /openbsd-src/gnu/llvm/llvm/lib/FileCheck/FileCheck.cpp (revision d415bd752c734aee168c4ee86ff32e8cc249eb16)
173471bf0Spatrick //===- FileCheck.cpp - Check that File's Contents match what is expected --===//
273471bf0Spatrick //
373471bf0Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
473471bf0Spatrick // See https://llvm.org/LICENSE.txt for license information.
573471bf0Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
673471bf0Spatrick //
773471bf0Spatrick //===----------------------------------------------------------------------===//
873471bf0Spatrick //
973471bf0Spatrick // FileCheck does a line-by line check of a file that validates whether it
1073471bf0Spatrick // contains the expected content.  This is useful for regression tests etc.
1173471bf0Spatrick //
1273471bf0Spatrick // This file implements most of the API that will be used by the FileCheck utility
1373471bf0Spatrick // as well as various unittests.
1473471bf0Spatrick //===----------------------------------------------------------------------===//
1573471bf0Spatrick 
1673471bf0Spatrick #include "llvm/FileCheck/FileCheck.h"
1773471bf0Spatrick #include "FileCheckImpl.h"
1873471bf0Spatrick #include "llvm/ADT/STLExtras.h"
1973471bf0Spatrick #include "llvm/ADT/StringSet.h"
2073471bf0Spatrick #include "llvm/ADT/Twine.h"
2173471bf0Spatrick #include "llvm/Support/CheckedArithmetic.h"
2273471bf0Spatrick #include "llvm/Support/FormatVariadic.h"
2373471bf0Spatrick #include <cstdint>
2473471bf0Spatrick #include <list>
2573471bf0Spatrick #include <set>
2673471bf0Spatrick #include <tuple>
2773471bf0Spatrick #include <utility>
2873471bf0Spatrick 
2973471bf0Spatrick using namespace llvm;
3073471bf0Spatrick 
toString() const3173471bf0Spatrick StringRef ExpressionFormat::toString() const {
3273471bf0Spatrick   switch (Value) {
3373471bf0Spatrick   case Kind::NoFormat:
3473471bf0Spatrick     return StringRef("<none>");
3573471bf0Spatrick   case Kind::Unsigned:
3673471bf0Spatrick     return StringRef("%u");
3773471bf0Spatrick   case Kind::Signed:
3873471bf0Spatrick     return StringRef("%d");
3973471bf0Spatrick   case Kind::HexUpper:
4073471bf0Spatrick     return StringRef("%X");
4173471bf0Spatrick   case Kind::HexLower:
4273471bf0Spatrick     return StringRef("%x");
4373471bf0Spatrick   }
4473471bf0Spatrick   llvm_unreachable("unknown expression format");
4573471bf0Spatrick }
4673471bf0Spatrick 
getWildcardRegex() const4773471bf0Spatrick Expected<std::string> ExpressionFormat::getWildcardRegex() const {
4873471bf0Spatrick   StringRef AlternateFormPrefix = AlternateForm ? StringRef("0x") : StringRef();
4973471bf0Spatrick 
5073471bf0Spatrick   auto CreatePrecisionRegex = [&](StringRef S) {
5173471bf0Spatrick     return (Twine(AlternateFormPrefix) + S + Twine('{') + Twine(Precision) +
5273471bf0Spatrick             "}")
5373471bf0Spatrick         .str();
5473471bf0Spatrick   };
5573471bf0Spatrick 
5673471bf0Spatrick   switch (Value) {
5773471bf0Spatrick   case Kind::Unsigned:
5873471bf0Spatrick     if (Precision)
5973471bf0Spatrick       return CreatePrecisionRegex("([1-9][0-9]*)?[0-9]");
6073471bf0Spatrick     return std::string("[0-9]+");
6173471bf0Spatrick   case Kind::Signed:
6273471bf0Spatrick     if (Precision)
6373471bf0Spatrick       return CreatePrecisionRegex("-?([1-9][0-9]*)?[0-9]");
6473471bf0Spatrick     return std::string("-?[0-9]+");
6573471bf0Spatrick   case Kind::HexUpper:
6673471bf0Spatrick     if (Precision)
6773471bf0Spatrick       return CreatePrecisionRegex("([1-9A-F][0-9A-F]*)?[0-9A-F]");
6873471bf0Spatrick     return (Twine(AlternateFormPrefix) + Twine("[0-9A-F]+")).str();
6973471bf0Spatrick   case Kind::HexLower:
7073471bf0Spatrick     if (Precision)
7173471bf0Spatrick       return CreatePrecisionRegex("([1-9a-f][0-9a-f]*)?[0-9a-f]");
7273471bf0Spatrick     return (Twine(AlternateFormPrefix) + Twine("[0-9a-f]+")).str();
7373471bf0Spatrick   default:
7473471bf0Spatrick     return createStringError(std::errc::invalid_argument,
7573471bf0Spatrick                              "trying to match value with invalid format");
7673471bf0Spatrick   }
7773471bf0Spatrick }
7873471bf0Spatrick 
7973471bf0Spatrick Expected<std::string>
getMatchingString(ExpressionValue IntegerValue) const8073471bf0Spatrick ExpressionFormat::getMatchingString(ExpressionValue IntegerValue) const {
8173471bf0Spatrick   uint64_t AbsoluteValue;
8273471bf0Spatrick   StringRef SignPrefix = IntegerValue.isNegative() ? "-" : "";
8373471bf0Spatrick 
8473471bf0Spatrick   if (Value == Kind::Signed) {
8573471bf0Spatrick     Expected<int64_t> SignedValue = IntegerValue.getSignedValue();
8673471bf0Spatrick     if (!SignedValue)
8773471bf0Spatrick       return SignedValue.takeError();
8873471bf0Spatrick     if (*SignedValue < 0)
8973471bf0Spatrick       AbsoluteValue = cantFail(IntegerValue.getAbsolute().getUnsignedValue());
9073471bf0Spatrick     else
9173471bf0Spatrick       AbsoluteValue = *SignedValue;
9273471bf0Spatrick   } else {
9373471bf0Spatrick     Expected<uint64_t> UnsignedValue = IntegerValue.getUnsignedValue();
9473471bf0Spatrick     if (!UnsignedValue)
9573471bf0Spatrick       return UnsignedValue.takeError();
9673471bf0Spatrick     AbsoluteValue = *UnsignedValue;
9773471bf0Spatrick   }
9873471bf0Spatrick 
9973471bf0Spatrick   std::string AbsoluteValueStr;
10073471bf0Spatrick   switch (Value) {
10173471bf0Spatrick   case Kind::Unsigned:
10273471bf0Spatrick   case Kind::Signed:
10373471bf0Spatrick     AbsoluteValueStr = utostr(AbsoluteValue);
10473471bf0Spatrick     break;
10573471bf0Spatrick   case Kind::HexUpper:
10673471bf0Spatrick   case Kind::HexLower:
10773471bf0Spatrick     AbsoluteValueStr = utohexstr(AbsoluteValue, Value == Kind::HexLower);
10873471bf0Spatrick     break;
10973471bf0Spatrick   default:
11073471bf0Spatrick     return createStringError(std::errc::invalid_argument,
11173471bf0Spatrick                              "trying to match value with invalid format");
11273471bf0Spatrick   }
11373471bf0Spatrick 
11473471bf0Spatrick   StringRef AlternateFormPrefix = AlternateForm ? StringRef("0x") : StringRef();
11573471bf0Spatrick 
11673471bf0Spatrick   if (Precision > AbsoluteValueStr.size()) {
11773471bf0Spatrick     unsigned LeadingZeros = Precision - AbsoluteValueStr.size();
11873471bf0Spatrick     return (Twine(SignPrefix) + Twine(AlternateFormPrefix) +
11973471bf0Spatrick             std::string(LeadingZeros, '0') + AbsoluteValueStr)
12073471bf0Spatrick         .str();
12173471bf0Spatrick   }
12273471bf0Spatrick 
12373471bf0Spatrick   return (Twine(SignPrefix) + Twine(AlternateFormPrefix) + AbsoluteValueStr)
12473471bf0Spatrick       .str();
12573471bf0Spatrick }
12673471bf0Spatrick 
12773471bf0Spatrick Expected<ExpressionValue>
valueFromStringRepr(StringRef StrVal,const SourceMgr & SM) const12873471bf0Spatrick ExpressionFormat::valueFromStringRepr(StringRef StrVal,
12973471bf0Spatrick                                       const SourceMgr &SM) const {
13073471bf0Spatrick   bool ValueIsSigned = Value == Kind::Signed;
13173471bf0Spatrick   // Both the FileCheck utility and library only call this method with a valid
13273471bf0Spatrick   // value in StrVal. This is guaranteed by the regex returned by
13373471bf0Spatrick   // getWildcardRegex() above. Only underflow and overflow errors can thus
13473471bf0Spatrick   // occur. However new uses of this method could be added in the future so
13573471bf0Spatrick   // the error message does not make assumptions about StrVal.
13673471bf0Spatrick   StringRef IntegerParseErrorStr = "unable to represent numeric value";
13773471bf0Spatrick   if (ValueIsSigned) {
13873471bf0Spatrick     int64_t SignedValue;
13973471bf0Spatrick 
14073471bf0Spatrick     if (StrVal.getAsInteger(10, SignedValue))
14173471bf0Spatrick       return ErrorDiagnostic::get(SM, StrVal, IntegerParseErrorStr);
14273471bf0Spatrick 
14373471bf0Spatrick     return ExpressionValue(SignedValue);
14473471bf0Spatrick   }
14573471bf0Spatrick 
14673471bf0Spatrick   bool Hex = Value == Kind::HexUpper || Value == Kind::HexLower;
14773471bf0Spatrick   uint64_t UnsignedValue;
14873471bf0Spatrick   bool MissingFormPrefix = AlternateForm && !StrVal.consume_front("0x");
14973471bf0Spatrick   if (StrVal.getAsInteger(Hex ? 16 : 10, UnsignedValue))
15073471bf0Spatrick     return ErrorDiagnostic::get(SM, StrVal, IntegerParseErrorStr);
15173471bf0Spatrick 
15273471bf0Spatrick   // Error out for a missing prefix only now that we know we have an otherwise
15373471bf0Spatrick   // valid integer.  For example, "-0x18" is reported above instead.
15473471bf0Spatrick   if (MissingFormPrefix)
15573471bf0Spatrick     return ErrorDiagnostic::get(SM, StrVal, "missing alternate form prefix");
15673471bf0Spatrick 
15773471bf0Spatrick   return ExpressionValue(UnsignedValue);
15873471bf0Spatrick }
15973471bf0Spatrick 
getAsSigned(uint64_t UnsignedValue)16073471bf0Spatrick static int64_t getAsSigned(uint64_t UnsignedValue) {
16173471bf0Spatrick   // Use memcpy to reinterpret the bitpattern in Value since casting to
16273471bf0Spatrick   // signed is implementation-defined if the unsigned value is too big to be
16373471bf0Spatrick   // represented in the signed type and using an union violates type aliasing
16473471bf0Spatrick   // rules.
16573471bf0Spatrick   int64_t SignedValue;
16673471bf0Spatrick   memcpy(&SignedValue, &UnsignedValue, sizeof(SignedValue));
16773471bf0Spatrick   return SignedValue;
16873471bf0Spatrick }
16973471bf0Spatrick 
getSignedValue() const17073471bf0Spatrick Expected<int64_t> ExpressionValue::getSignedValue() const {
17173471bf0Spatrick   if (Negative)
17273471bf0Spatrick     return getAsSigned(Value);
17373471bf0Spatrick 
17473471bf0Spatrick   if (Value > (uint64_t)std::numeric_limits<int64_t>::max())
17573471bf0Spatrick     return make_error<OverflowError>();
17673471bf0Spatrick 
17773471bf0Spatrick   // Value is in the representable range of int64_t so we can use cast.
17873471bf0Spatrick   return static_cast<int64_t>(Value);
17973471bf0Spatrick }
18073471bf0Spatrick 
getUnsignedValue() const18173471bf0Spatrick Expected<uint64_t> ExpressionValue::getUnsignedValue() const {
18273471bf0Spatrick   if (Negative)
18373471bf0Spatrick     return make_error<OverflowError>();
18473471bf0Spatrick 
18573471bf0Spatrick   return Value;
18673471bf0Spatrick }
18773471bf0Spatrick 
getAbsolute() const18873471bf0Spatrick ExpressionValue ExpressionValue::getAbsolute() const {
18973471bf0Spatrick   if (!Negative)
19073471bf0Spatrick     return *this;
19173471bf0Spatrick 
19273471bf0Spatrick   int64_t SignedValue = getAsSigned(Value);
19373471bf0Spatrick   int64_t MaxInt64 = std::numeric_limits<int64_t>::max();
19473471bf0Spatrick   // Absolute value can be represented as int64_t.
19573471bf0Spatrick   if (SignedValue >= -MaxInt64)
19673471bf0Spatrick     return ExpressionValue(-getAsSigned(Value));
19773471bf0Spatrick 
19873471bf0Spatrick   // -X == -(max int64_t + Rem), negate each component independently.
19973471bf0Spatrick   SignedValue += MaxInt64;
20073471bf0Spatrick   uint64_t RemainingValueAbsolute = -SignedValue;
20173471bf0Spatrick   return ExpressionValue(MaxInt64 + RemainingValueAbsolute);
20273471bf0Spatrick }
20373471bf0Spatrick 
operator +(const ExpressionValue & LeftOperand,const ExpressionValue & RightOperand)20473471bf0Spatrick Expected<ExpressionValue> llvm::operator+(const ExpressionValue &LeftOperand,
20573471bf0Spatrick                                           const ExpressionValue &RightOperand) {
20673471bf0Spatrick   if (LeftOperand.isNegative() && RightOperand.isNegative()) {
20773471bf0Spatrick     int64_t LeftValue = cantFail(LeftOperand.getSignedValue());
20873471bf0Spatrick     int64_t RightValue = cantFail(RightOperand.getSignedValue());
209*d415bd75Srobert     std::optional<int64_t> Result = checkedAdd<int64_t>(LeftValue, RightValue);
21073471bf0Spatrick     if (!Result)
21173471bf0Spatrick       return make_error<OverflowError>();
21273471bf0Spatrick 
21373471bf0Spatrick     return ExpressionValue(*Result);
21473471bf0Spatrick   }
21573471bf0Spatrick 
21673471bf0Spatrick   // (-A) + B == B - A.
21773471bf0Spatrick   if (LeftOperand.isNegative())
21873471bf0Spatrick     return RightOperand - LeftOperand.getAbsolute();
21973471bf0Spatrick 
22073471bf0Spatrick   // A + (-B) == A - B.
22173471bf0Spatrick   if (RightOperand.isNegative())
22273471bf0Spatrick     return LeftOperand - RightOperand.getAbsolute();
22373471bf0Spatrick 
22473471bf0Spatrick   // Both values are positive at this point.
22573471bf0Spatrick   uint64_t LeftValue = cantFail(LeftOperand.getUnsignedValue());
22673471bf0Spatrick   uint64_t RightValue = cantFail(RightOperand.getUnsignedValue());
227*d415bd75Srobert   std::optional<uint64_t> Result =
22873471bf0Spatrick       checkedAddUnsigned<uint64_t>(LeftValue, RightValue);
22973471bf0Spatrick   if (!Result)
23073471bf0Spatrick     return make_error<OverflowError>();
23173471bf0Spatrick 
23273471bf0Spatrick   return ExpressionValue(*Result);
23373471bf0Spatrick }
23473471bf0Spatrick 
operator -(const ExpressionValue & LeftOperand,const ExpressionValue & RightOperand)23573471bf0Spatrick Expected<ExpressionValue> llvm::operator-(const ExpressionValue &LeftOperand,
23673471bf0Spatrick                                           const ExpressionValue &RightOperand) {
23773471bf0Spatrick   // Result will be negative and thus might underflow.
23873471bf0Spatrick   if (LeftOperand.isNegative() && !RightOperand.isNegative()) {
23973471bf0Spatrick     int64_t LeftValue = cantFail(LeftOperand.getSignedValue());
24073471bf0Spatrick     uint64_t RightValue = cantFail(RightOperand.getUnsignedValue());
24173471bf0Spatrick     // Result <= -1 - (max int64_t) which overflows on 1- and 2-complement.
24273471bf0Spatrick     if (RightValue > (uint64_t)std::numeric_limits<int64_t>::max())
24373471bf0Spatrick       return make_error<OverflowError>();
244*d415bd75Srobert     std::optional<int64_t> Result =
24573471bf0Spatrick         checkedSub(LeftValue, static_cast<int64_t>(RightValue));
24673471bf0Spatrick     if (!Result)
24773471bf0Spatrick       return make_error<OverflowError>();
24873471bf0Spatrick 
24973471bf0Spatrick     return ExpressionValue(*Result);
25073471bf0Spatrick   }
25173471bf0Spatrick 
25273471bf0Spatrick   // (-A) - (-B) == B - A.
25373471bf0Spatrick   if (LeftOperand.isNegative())
25473471bf0Spatrick     return RightOperand.getAbsolute() - LeftOperand.getAbsolute();
25573471bf0Spatrick 
25673471bf0Spatrick   // A - (-B) == A + B.
25773471bf0Spatrick   if (RightOperand.isNegative())
25873471bf0Spatrick     return LeftOperand + RightOperand.getAbsolute();
25973471bf0Spatrick 
26073471bf0Spatrick   // Both values are positive at this point.
26173471bf0Spatrick   uint64_t LeftValue = cantFail(LeftOperand.getUnsignedValue());
26273471bf0Spatrick   uint64_t RightValue = cantFail(RightOperand.getUnsignedValue());
26373471bf0Spatrick   if (LeftValue >= RightValue)
26473471bf0Spatrick     return ExpressionValue(LeftValue - RightValue);
26573471bf0Spatrick   else {
26673471bf0Spatrick     uint64_t AbsoluteDifference = RightValue - LeftValue;
26773471bf0Spatrick     uint64_t MaxInt64 = std::numeric_limits<int64_t>::max();
26873471bf0Spatrick     // Value might underflow.
26973471bf0Spatrick     if (AbsoluteDifference > MaxInt64) {
27073471bf0Spatrick       AbsoluteDifference -= MaxInt64;
27173471bf0Spatrick       int64_t Result = -MaxInt64;
27273471bf0Spatrick       int64_t MinInt64 = std::numeric_limits<int64_t>::min();
27373471bf0Spatrick       // Underflow, tested by:
27473471bf0Spatrick       //   abs(Result + (max int64_t)) > abs((min int64_t) + (max int64_t))
27573471bf0Spatrick       if (AbsoluteDifference > static_cast<uint64_t>(-(MinInt64 - Result)))
27673471bf0Spatrick         return make_error<OverflowError>();
27773471bf0Spatrick       Result -= static_cast<int64_t>(AbsoluteDifference);
27873471bf0Spatrick       return ExpressionValue(Result);
27973471bf0Spatrick     }
28073471bf0Spatrick 
28173471bf0Spatrick     return ExpressionValue(-static_cast<int64_t>(AbsoluteDifference));
28273471bf0Spatrick   }
28373471bf0Spatrick }
28473471bf0Spatrick 
operator *(const ExpressionValue & LeftOperand,const ExpressionValue & RightOperand)28573471bf0Spatrick Expected<ExpressionValue> llvm::operator*(const ExpressionValue &LeftOperand,
28673471bf0Spatrick                                           const ExpressionValue &RightOperand) {
28773471bf0Spatrick   // -A * -B == A * B
28873471bf0Spatrick   if (LeftOperand.isNegative() && RightOperand.isNegative())
28973471bf0Spatrick     return LeftOperand.getAbsolute() * RightOperand.getAbsolute();
29073471bf0Spatrick 
29173471bf0Spatrick   // A * -B == -B * A
29273471bf0Spatrick   if (RightOperand.isNegative())
29373471bf0Spatrick     return RightOperand * LeftOperand;
29473471bf0Spatrick 
29573471bf0Spatrick   assert(!RightOperand.isNegative() && "Unexpected negative operand!");
29673471bf0Spatrick 
29773471bf0Spatrick   // Result will be negative and can underflow.
29873471bf0Spatrick   if (LeftOperand.isNegative()) {
29973471bf0Spatrick     auto Result = LeftOperand.getAbsolute() * RightOperand.getAbsolute();
30073471bf0Spatrick     if (!Result)
30173471bf0Spatrick       return Result;
30273471bf0Spatrick 
30373471bf0Spatrick     return ExpressionValue(0) - *Result;
30473471bf0Spatrick   }
30573471bf0Spatrick 
30673471bf0Spatrick   // Result will be positive and can overflow.
30773471bf0Spatrick   uint64_t LeftValue = cantFail(LeftOperand.getUnsignedValue());
30873471bf0Spatrick   uint64_t RightValue = cantFail(RightOperand.getUnsignedValue());
309*d415bd75Srobert   std::optional<uint64_t> Result =
31073471bf0Spatrick       checkedMulUnsigned<uint64_t>(LeftValue, RightValue);
31173471bf0Spatrick   if (!Result)
31273471bf0Spatrick     return make_error<OverflowError>();
31373471bf0Spatrick 
31473471bf0Spatrick   return ExpressionValue(*Result);
31573471bf0Spatrick }
31673471bf0Spatrick 
operator /(const ExpressionValue & LeftOperand,const ExpressionValue & RightOperand)31773471bf0Spatrick Expected<ExpressionValue> llvm::operator/(const ExpressionValue &LeftOperand,
31873471bf0Spatrick                                           const ExpressionValue &RightOperand) {
31973471bf0Spatrick   // -A / -B == A / B
32073471bf0Spatrick   if (LeftOperand.isNegative() && RightOperand.isNegative())
32173471bf0Spatrick     return LeftOperand.getAbsolute() / RightOperand.getAbsolute();
32273471bf0Spatrick 
32373471bf0Spatrick   // Check for divide by zero.
32473471bf0Spatrick   if (RightOperand == ExpressionValue(0))
32573471bf0Spatrick     return make_error<OverflowError>();
32673471bf0Spatrick 
32773471bf0Spatrick   // Result will be negative and can underflow.
32873471bf0Spatrick   if (LeftOperand.isNegative() || RightOperand.isNegative())
32973471bf0Spatrick     return ExpressionValue(0) -
33073471bf0Spatrick            cantFail(LeftOperand.getAbsolute() / RightOperand.getAbsolute());
33173471bf0Spatrick 
33273471bf0Spatrick   uint64_t LeftValue = cantFail(LeftOperand.getUnsignedValue());
33373471bf0Spatrick   uint64_t RightValue = cantFail(RightOperand.getUnsignedValue());
33473471bf0Spatrick   return ExpressionValue(LeftValue / RightValue);
33573471bf0Spatrick }
33673471bf0Spatrick 
max(const ExpressionValue & LeftOperand,const ExpressionValue & RightOperand)33773471bf0Spatrick Expected<ExpressionValue> llvm::max(const ExpressionValue &LeftOperand,
33873471bf0Spatrick                                     const ExpressionValue &RightOperand) {
33973471bf0Spatrick   if (LeftOperand.isNegative() && RightOperand.isNegative()) {
34073471bf0Spatrick     int64_t LeftValue = cantFail(LeftOperand.getSignedValue());
34173471bf0Spatrick     int64_t RightValue = cantFail(RightOperand.getSignedValue());
34273471bf0Spatrick     return ExpressionValue(std::max(LeftValue, RightValue));
34373471bf0Spatrick   }
34473471bf0Spatrick 
34573471bf0Spatrick   if (!LeftOperand.isNegative() && !RightOperand.isNegative()) {
34673471bf0Spatrick     uint64_t LeftValue = cantFail(LeftOperand.getUnsignedValue());
34773471bf0Spatrick     uint64_t RightValue = cantFail(RightOperand.getUnsignedValue());
34873471bf0Spatrick     return ExpressionValue(std::max(LeftValue, RightValue));
34973471bf0Spatrick   }
35073471bf0Spatrick 
35173471bf0Spatrick   if (LeftOperand.isNegative())
35273471bf0Spatrick     return RightOperand;
35373471bf0Spatrick 
35473471bf0Spatrick   return LeftOperand;
35573471bf0Spatrick }
35673471bf0Spatrick 
min(const ExpressionValue & LeftOperand,const ExpressionValue & RightOperand)35773471bf0Spatrick Expected<ExpressionValue> llvm::min(const ExpressionValue &LeftOperand,
35873471bf0Spatrick                                     const ExpressionValue &RightOperand) {
35973471bf0Spatrick   if (cantFail(max(LeftOperand, RightOperand)) == LeftOperand)
36073471bf0Spatrick     return RightOperand;
36173471bf0Spatrick 
36273471bf0Spatrick   return LeftOperand;
36373471bf0Spatrick }
36473471bf0Spatrick 
eval() const36573471bf0Spatrick Expected<ExpressionValue> NumericVariableUse::eval() const {
366*d415bd75Srobert   std::optional<ExpressionValue> Value = Variable->getValue();
36773471bf0Spatrick   if (Value)
36873471bf0Spatrick     return *Value;
36973471bf0Spatrick 
37073471bf0Spatrick   return make_error<UndefVarError>(getExpressionStr());
37173471bf0Spatrick }
37273471bf0Spatrick 
eval() const37373471bf0Spatrick Expected<ExpressionValue> BinaryOperation::eval() const {
37473471bf0Spatrick   Expected<ExpressionValue> LeftOp = LeftOperand->eval();
37573471bf0Spatrick   Expected<ExpressionValue> RightOp = RightOperand->eval();
37673471bf0Spatrick 
37773471bf0Spatrick   // Bubble up any error (e.g. undefined variables) in the recursive
37873471bf0Spatrick   // evaluation.
37973471bf0Spatrick   if (!LeftOp || !RightOp) {
38073471bf0Spatrick     Error Err = Error::success();
38173471bf0Spatrick     if (!LeftOp)
38273471bf0Spatrick       Err = joinErrors(std::move(Err), LeftOp.takeError());
38373471bf0Spatrick     if (!RightOp)
38473471bf0Spatrick       Err = joinErrors(std::move(Err), RightOp.takeError());
38573471bf0Spatrick     return std::move(Err);
38673471bf0Spatrick   }
38773471bf0Spatrick 
38873471bf0Spatrick   return EvalBinop(*LeftOp, *RightOp);
38973471bf0Spatrick }
39073471bf0Spatrick 
39173471bf0Spatrick Expected<ExpressionFormat>
getImplicitFormat(const SourceMgr & SM) const39273471bf0Spatrick BinaryOperation::getImplicitFormat(const SourceMgr &SM) const {
39373471bf0Spatrick   Expected<ExpressionFormat> LeftFormat = LeftOperand->getImplicitFormat(SM);
39473471bf0Spatrick   Expected<ExpressionFormat> RightFormat = RightOperand->getImplicitFormat(SM);
39573471bf0Spatrick   if (!LeftFormat || !RightFormat) {
39673471bf0Spatrick     Error Err = Error::success();
39773471bf0Spatrick     if (!LeftFormat)
39873471bf0Spatrick       Err = joinErrors(std::move(Err), LeftFormat.takeError());
39973471bf0Spatrick     if (!RightFormat)
40073471bf0Spatrick       Err = joinErrors(std::move(Err), RightFormat.takeError());
40173471bf0Spatrick     return std::move(Err);
40273471bf0Spatrick   }
40373471bf0Spatrick 
40473471bf0Spatrick   if (*LeftFormat != ExpressionFormat::Kind::NoFormat &&
40573471bf0Spatrick       *RightFormat != ExpressionFormat::Kind::NoFormat &&
40673471bf0Spatrick       *LeftFormat != *RightFormat)
40773471bf0Spatrick     return ErrorDiagnostic::get(
40873471bf0Spatrick         SM, getExpressionStr(),
40973471bf0Spatrick         "implicit format conflict between '" + LeftOperand->getExpressionStr() +
41073471bf0Spatrick             "' (" + LeftFormat->toString() + ") and '" +
41173471bf0Spatrick             RightOperand->getExpressionStr() + "' (" + RightFormat->toString() +
41273471bf0Spatrick             "), need an explicit format specifier");
41373471bf0Spatrick 
41473471bf0Spatrick   return *LeftFormat != ExpressionFormat::Kind::NoFormat ? *LeftFormat
41573471bf0Spatrick                                                          : *RightFormat;
41673471bf0Spatrick }
41773471bf0Spatrick 
getResult() const41873471bf0Spatrick Expected<std::string> NumericSubstitution::getResult() const {
41973471bf0Spatrick   assert(ExpressionPointer->getAST() != nullptr &&
42073471bf0Spatrick          "Substituting empty expression");
42173471bf0Spatrick   Expected<ExpressionValue> EvaluatedValue =
42273471bf0Spatrick       ExpressionPointer->getAST()->eval();
42373471bf0Spatrick   if (!EvaluatedValue)
42473471bf0Spatrick     return EvaluatedValue.takeError();
42573471bf0Spatrick   ExpressionFormat Format = ExpressionPointer->getFormat();
42673471bf0Spatrick   return Format.getMatchingString(*EvaluatedValue);
42773471bf0Spatrick }
42873471bf0Spatrick 
getResult() const42973471bf0Spatrick Expected<std::string> StringSubstitution::getResult() const {
43073471bf0Spatrick   // Look up the value and escape it so that we can put it into the regex.
43173471bf0Spatrick   Expected<StringRef> VarVal = Context->getPatternVarValue(FromStr);
43273471bf0Spatrick   if (!VarVal)
43373471bf0Spatrick     return VarVal.takeError();
43473471bf0Spatrick   return Regex::escape(*VarVal);
43573471bf0Spatrick }
43673471bf0Spatrick 
isValidVarNameStart(char C)43773471bf0Spatrick bool Pattern::isValidVarNameStart(char C) { return C == '_' || isAlpha(C); }
43873471bf0Spatrick 
43973471bf0Spatrick Expected<Pattern::VariableProperties>
parseVariable(StringRef & Str,const SourceMgr & SM)44073471bf0Spatrick Pattern::parseVariable(StringRef &Str, const SourceMgr &SM) {
44173471bf0Spatrick   if (Str.empty())
44273471bf0Spatrick     return ErrorDiagnostic::get(SM, Str, "empty variable name");
44373471bf0Spatrick 
44473471bf0Spatrick   size_t I = 0;
44573471bf0Spatrick   bool IsPseudo = Str[0] == '@';
44673471bf0Spatrick 
44773471bf0Spatrick   // Global vars start with '$'.
44873471bf0Spatrick   if (Str[0] == '$' || IsPseudo)
44973471bf0Spatrick     ++I;
45073471bf0Spatrick 
45173471bf0Spatrick   if (!isValidVarNameStart(Str[I++]))
45273471bf0Spatrick     return ErrorDiagnostic::get(SM, Str, "invalid variable name");
45373471bf0Spatrick 
45473471bf0Spatrick   for (size_t E = Str.size(); I != E; ++I)
45573471bf0Spatrick     // Variable names are composed of alphanumeric characters and underscores.
45673471bf0Spatrick     if (Str[I] != '_' && !isAlnum(Str[I]))
45773471bf0Spatrick       break;
45873471bf0Spatrick 
45973471bf0Spatrick   StringRef Name = Str.take_front(I);
46073471bf0Spatrick   Str = Str.substr(I);
46173471bf0Spatrick   return VariableProperties {Name, IsPseudo};
46273471bf0Spatrick }
46373471bf0Spatrick 
46473471bf0Spatrick // StringRef holding all characters considered as horizontal whitespaces by
46573471bf0Spatrick // FileCheck input canonicalization.
46673471bf0Spatrick constexpr StringLiteral SpaceChars = " \t";
46773471bf0Spatrick 
46873471bf0Spatrick // Parsing helper function that strips the first character in S and returns it.
popFront(StringRef & S)46973471bf0Spatrick static char popFront(StringRef &S) {
47073471bf0Spatrick   char C = S.front();
47173471bf0Spatrick   S = S.drop_front();
47273471bf0Spatrick   return C;
47373471bf0Spatrick }
47473471bf0Spatrick 
47573471bf0Spatrick char OverflowError::ID = 0;
47673471bf0Spatrick char UndefVarError::ID = 0;
47773471bf0Spatrick char ErrorDiagnostic::ID = 0;
47873471bf0Spatrick char NotFoundError::ID = 0;
47973471bf0Spatrick char ErrorReported::ID = 0;
48073471bf0Spatrick 
parseNumericVariableDefinition(StringRef & Expr,FileCheckPatternContext * Context,std::optional<size_t> LineNumber,ExpressionFormat ImplicitFormat,const SourceMgr & SM)48173471bf0Spatrick Expected<NumericVariable *> Pattern::parseNumericVariableDefinition(
48273471bf0Spatrick     StringRef &Expr, FileCheckPatternContext *Context,
483*d415bd75Srobert     std::optional<size_t> LineNumber, ExpressionFormat ImplicitFormat,
48473471bf0Spatrick     const SourceMgr &SM) {
48573471bf0Spatrick   Expected<VariableProperties> ParseVarResult = parseVariable(Expr, SM);
48673471bf0Spatrick   if (!ParseVarResult)
48773471bf0Spatrick     return ParseVarResult.takeError();
48873471bf0Spatrick   StringRef Name = ParseVarResult->Name;
48973471bf0Spatrick 
49073471bf0Spatrick   if (ParseVarResult->IsPseudo)
49173471bf0Spatrick     return ErrorDiagnostic::get(
49273471bf0Spatrick         SM, Name, "definition of pseudo numeric variable unsupported");
49373471bf0Spatrick 
49473471bf0Spatrick   // Detect collisions between string and numeric variables when the latter
49573471bf0Spatrick   // is created later than the former.
49673471bf0Spatrick   if (Context->DefinedVariableTable.find(Name) !=
49773471bf0Spatrick       Context->DefinedVariableTable.end())
49873471bf0Spatrick     return ErrorDiagnostic::get(
49973471bf0Spatrick         SM, Name, "string variable with name '" + Name + "' already exists");
50073471bf0Spatrick 
50173471bf0Spatrick   Expr = Expr.ltrim(SpaceChars);
50273471bf0Spatrick   if (!Expr.empty())
50373471bf0Spatrick     return ErrorDiagnostic::get(
50473471bf0Spatrick         SM, Expr, "unexpected characters after numeric variable name");
50573471bf0Spatrick 
50673471bf0Spatrick   NumericVariable *DefinedNumericVariable;
50773471bf0Spatrick   auto VarTableIter = Context->GlobalNumericVariableTable.find(Name);
50873471bf0Spatrick   if (VarTableIter != Context->GlobalNumericVariableTable.end()) {
50973471bf0Spatrick     DefinedNumericVariable = VarTableIter->second;
51073471bf0Spatrick     if (DefinedNumericVariable->getImplicitFormat() != ImplicitFormat)
51173471bf0Spatrick       return ErrorDiagnostic::get(
51273471bf0Spatrick           SM, Expr, "format different from previous variable definition");
51373471bf0Spatrick   } else
51473471bf0Spatrick     DefinedNumericVariable =
51573471bf0Spatrick         Context->makeNumericVariable(Name, ImplicitFormat, LineNumber);
51673471bf0Spatrick 
51773471bf0Spatrick   return DefinedNumericVariable;
51873471bf0Spatrick }
51973471bf0Spatrick 
parseNumericVariableUse(StringRef Name,bool IsPseudo,std::optional<size_t> LineNumber,FileCheckPatternContext * Context,const SourceMgr & SM)52073471bf0Spatrick Expected<std::unique_ptr<NumericVariableUse>> Pattern::parseNumericVariableUse(
521*d415bd75Srobert     StringRef Name, bool IsPseudo, std::optional<size_t> LineNumber,
52273471bf0Spatrick     FileCheckPatternContext *Context, const SourceMgr &SM) {
52373471bf0Spatrick   if (IsPseudo && !Name.equals("@LINE"))
52473471bf0Spatrick     return ErrorDiagnostic::get(
52573471bf0Spatrick         SM, Name, "invalid pseudo numeric variable '" + Name + "'");
52673471bf0Spatrick 
52773471bf0Spatrick   // Numeric variable definitions and uses are parsed in the order in which
52873471bf0Spatrick   // they appear in the CHECK patterns. For each definition, the pointer to the
52973471bf0Spatrick   // class instance of the corresponding numeric variable definition is stored
53073471bf0Spatrick   // in GlobalNumericVariableTable in parsePattern. Therefore, if the pointer
53173471bf0Spatrick   // we get below is null, it means no such variable was defined before. When
53273471bf0Spatrick   // that happens, we create a dummy variable so that parsing can continue. All
53373471bf0Spatrick   // uses of undefined variables, whether string or numeric, are then diagnosed
53473471bf0Spatrick   // in printNoMatch() after failing to match.
53573471bf0Spatrick   auto VarTableIter = Context->GlobalNumericVariableTable.find(Name);
53673471bf0Spatrick   NumericVariable *NumericVariable;
53773471bf0Spatrick   if (VarTableIter != Context->GlobalNumericVariableTable.end())
53873471bf0Spatrick     NumericVariable = VarTableIter->second;
53973471bf0Spatrick   else {
54073471bf0Spatrick     NumericVariable = Context->makeNumericVariable(
54173471bf0Spatrick         Name, ExpressionFormat(ExpressionFormat::Kind::Unsigned));
54273471bf0Spatrick     Context->GlobalNumericVariableTable[Name] = NumericVariable;
54373471bf0Spatrick   }
54473471bf0Spatrick 
545*d415bd75Srobert   std::optional<size_t> DefLineNumber = NumericVariable->getDefLineNumber();
54673471bf0Spatrick   if (DefLineNumber && LineNumber && *DefLineNumber == *LineNumber)
54773471bf0Spatrick     return ErrorDiagnostic::get(
54873471bf0Spatrick         SM, Name,
54973471bf0Spatrick         "numeric variable '" + Name +
55073471bf0Spatrick             "' defined earlier in the same CHECK directive");
55173471bf0Spatrick 
55273471bf0Spatrick   return std::make_unique<NumericVariableUse>(Name, NumericVariable);
55373471bf0Spatrick }
55473471bf0Spatrick 
parseNumericOperand(StringRef & Expr,AllowedOperand AO,bool MaybeInvalidConstraint,std::optional<size_t> LineNumber,FileCheckPatternContext * Context,const SourceMgr & SM)55573471bf0Spatrick Expected<std::unique_ptr<ExpressionAST>> Pattern::parseNumericOperand(
55673471bf0Spatrick     StringRef &Expr, AllowedOperand AO, bool MaybeInvalidConstraint,
557*d415bd75Srobert     std::optional<size_t> LineNumber, FileCheckPatternContext *Context,
55873471bf0Spatrick     const SourceMgr &SM) {
55973471bf0Spatrick   if (Expr.startswith("(")) {
56073471bf0Spatrick     if (AO != AllowedOperand::Any)
56173471bf0Spatrick       return ErrorDiagnostic::get(
56273471bf0Spatrick           SM, Expr, "parenthesized expression not permitted here");
56373471bf0Spatrick     return parseParenExpr(Expr, LineNumber, Context, SM);
56473471bf0Spatrick   }
56573471bf0Spatrick 
56673471bf0Spatrick   if (AO == AllowedOperand::LineVar || AO == AllowedOperand::Any) {
56773471bf0Spatrick     // Try to parse as a numeric variable use.
56873471bf0Spatrick     Expected<Pattern::VariableProperties> ParseVarResult =
56973471bf0Spatrick         parseVariable(Expr, SM);
57073471bf0Spatrick     if (ParseVarResult) {
57173471bf0Spatrick       // Try to parse a function call.
57273471bf0Spatrick       if (Expr.ltrim(SpaceChars).startswith("(")) {
57373471bf0Spatrick         if (AO != AllowedOperand::Any)
57473471bf0Spatrick           return ErrorDiagnostic::get(SM, ParseVarResult->Name,
57573471bf0Spatrick                                       "unexpected function call");
57673471bf0Spatrick 
57773471bf0Spatrick         return parseCallExpr(Expr, ParseVarResult->Name, LineNumber, Context,
57873471bf0Spatrick                              SM);
57973471bf0Spatrick       }
58073471bf0Spatrick 
58173471bf0Spatrick       return parseNumericVariableUse(ParseVarResult->Name,
58273471bf0Spatrick                                      ParseVarResult->IsPseudo, LineNumber,
58373471bf0Spatrick                                      Context, SM);
58473471bf0Spatrick     }
58573471bf0Spatrick 
58673471bf0Spatrick     if (AO == AllowedOperand::LineVar)
58773471bf0Spatrick       return ParseVarResult.takeError();
58873471bf0Spatrick     // Ignore the error and retry parsing as a literal.
58973471bf0Spatrick     consumeError(ParseVarResult.takeError());
59073471bf0Spatrick   }
59173471bf0Spatrick 
59273471bf0Spatrick   // Otherwise, parse it as a literal.
59373471bf0Spatrick   int64_t SignedLiteralValue;
59473471bf0Spatrick   uint64_t UnsignedLiteralValue;
59573471bf0Spatrick   StringRef SaveExpr = Expr;
59673471bf0Spatrick   // Accept both signed and unsigned literal, default to signed literal.
59773471bf0Spatrick   if (!Expr.consumeInteger((AO == AllowedOperand::LegacyLiteral) ? 10 : 0,
59873471bf0Spatrick                            UnsignedLiteralValue))
59973471bf0Spatrick     return std::make_unique<ExpressionLiteral>(SaveExpr.drop_back(Expr.size()),
60073471bf0Spatrick                                                UnsignedLiteralValue);
60173471bf0Spatrick   Expr = SaveExpr;
60273471bf0Spatrick   if (AO == AllowedOperand::Any && !Expr.consumeInteger(0, SignedLiteralValue))
60373471bf0Spatrick     return std::make_unique<ExpressionLiteral>(SaveExpr.drop_back(Expr.size()),
60473471bf0Spatrick                                                SignedLiteralValue);
60573471bf0Spatrick 
60673471bf0Spatrick   return ErrorDiagnostic::get(
60773471bf0Spatrick       SM, Expr,
60873471bf0Spatrick       Twine("invalid ") +
60973471bf0Spatrick           (MaybeInvalidConstraint ? "matching constraint or " : "") +
61073471bf0Spatrick           "operand format");
61173471bf0Spatrick }
61273471bf0Spatrick 
61373471bf0Spatrick Expected<std::unique_ptr<ExpressionAST>>
parseParenExpr(StringRef & Expr,std::optional<size_t> LineNumber,FileCheckPatternContext * Context,const SourceMgr & SM)614*d415bd75Srobert Pattern::parseParenExpr(StringRef &Expr, std::optional<size_t> LineNumber,
61573471bf0Spatrick                         FileCheckPatternContext *Context, const SourceMgr &SM) {
61673471bf0Spatrick   Expr = Expr.ltrim(SpaceChars);
61773471bf0Spatrick   assert(Expr.startswith("("));
61873471bf0Spatrick 
61973471bf0Spatrick   // Parse right operand.
62073471bf0Spatrick   Expr.consume_front("(");
62173471bf0Spatrick   Expr = Expr.ltrim(SpaceChars);
62273471bf0Spatrick   if (Expr.empty())
62373471bf0Spatrick     return ErrorDiagnostic::get(SM, Expr, "missing operand in expression");
62473471bf0Spatrick 
62573471bf0Spatrick   // Note: parseNumericOperand handles nested opening parentheses.
62673471bf0Spatrick   Expected<std::unique_ptr<ExpressionAST>> SubExprResult = parseNumericOperand(
62773471bf0Spatrick       Expr, AllowedOperand::Any, /*MaybeInvalidConstraint=*/false, LineNumber,
62873471bf0Spatrick       Context, SM);
62973471bf0Spatrick   Expr = Expr.ltrim(SpaceChars);
63073471bf0Spatrick   while (SubExprResult && !Expr.empty() && !Expr.startswith(")")) {
63173471bf0Spatrick     StringRef OrigExpr = Expr;
63273471bf0Spatrick     SubExprResult = parseBinop(OrigExpr, Expr, std::move(*SubExprResult), false,
63373471bf0Spatrick                                LineNumber, Context, SM);
63473471bf0Spatrick     Expr = Expr.ltrim(SpaceChars);
63573471bf0Spatrick   }
63673471bf0Spatrick   if (!SubExprResult)
63773471bf0Spatrick     return SubExprResult;
63873471bf0Spatrick 
63973471bf0Spatrick   if (!Expr.consume_front(")")) {
64073471bf0Spatrick     return ErrorDiagnostic::get(SM, Expr,
64173471bf0Spatrick                                 "missing ')' at end of nested expression");
64273471bf0Spatrick   }
64373471bf0Spatrick   return SubExprResult;
64473471bf0Spatrick }
64573471bf0Spatrick 
64673471bf0Spatrick Expected<std::unique_ptr<ExpressionAST>>
parseBinop(StringRef Expr,StringRef & RemainingExpr,std::unique_ptr<ExpressionAST> LeftOp,bool IsLegacyLineExpr,std::optional<size_t> LineNumber,FileCheckPatternContext * Context,const SourceMgr & SM)64773471bf0Spatrick Pattern::parseBinop(StringRef Expr, StringRef &RemainingExpr,
64873471bf0Spatrick                     std::unique_ptr<ExpressionAST> LeftOp,
649*d415bd75Srobert                     bool IsLegacyLineExpr, std::optional<size_t> LineNumber,
65073471bf0Spatrick                     FileCheckPatternContext *Context, const SourceMgr &SM) {
65173471bf0Spatrick   RemainingExpr = RemainingExpr.ltrim(SpaceChars);
65273471bf0Spatrick   if (RemainingExpr.empty())
65373471bf0Spatrick     return std::move(LeftOp);
65473471bf0Spatrick 
65573471bf0Spatrick   // Check if this is a supported operation and select a function to perform
65673471bf0Spatrick   // it.
65773471bf0Spatrick   SMLoc OpLoc = SMLoc::getFromPointer(RemainingExpr.data());
65873471bf0Spatrick   char Operator = popFront(RemainingExpr);
65973471bf0Spatrick   binop_eval_t EvalBinop;
66073471bf0Spatrick   switch (Operator) {
66173471bf0Spatrick   case '+':
66273471bf0Spatrick     EvalBinop = operator+;
66373471bf0Spatrick     break;
66473471bf0Spatrick   case '-':
66573471bf0Spatrick     EvalBinop = operator-;
66673471bf0Spatrick     break;
66773471bf0Spatrick   default:
66873471bf0Spatrick     return ErrorDiagnostic::get(
66973471bf0Spatrick         SM, OpLoc, Twine("unsupported operation '") + Twine(Operator) + "'");
67073471bf0Spatrick   }
67173471bf0Spatrick 
67273471bf0Spatrick   // Parse right operand.
67373471bf0Spatrick   RemainingExpr = RemainingExpr.ltrim(SpaceChars);
67473471bf0Spatrick   if (RemainingExpr.empty())
67573471bf0Spatrick     return ErrorDiagnostic::get(SM, RemainingExpr,
67673471bf0Spatrick                                 "missing operand in expression");
67773471bf0Spatrick   // The second operand in a legacy @LINE expression is always a literal.
67873471bf0Spatrick   AllowedOperand AO =
67973471bf0Spatrick       IsLegacyLineExpr ? AllowedOperand::LegacyLiteral : AllowedOperand::Any;
68073471bf0Spatrick   Expected<std::unique_ptr<ExpressionAST>> RightOpResult =
68173471bf0Spatrick       parseNumericOperand(RemainingExpr, AO, /*MaybeInvalidConstraint=*/false,
68273471bf0Spatrick                           LineNumber, Context, SM);
68373471bf0Spatrick   if (!RightOpResult)
68473471bf0Spatrick     return RightOpResult;
68573471bf0Spatrick 
68673471bf0Spatrick   Expr = Expr.drop_back(RemainingExpr.size());
68773471bf0Spatrick   return std::make_unique<BinaryOperation>(Expr, EvalBinop, std::move(LeftOp),
68873471bf0Spatrick                                            std::move(*RightOpResult));
68973471bf0Spatrick }
69073471bf0Spatrick 
69173471bf0Spatrick Expected<std::unique_ptr<ExpressionAST>>
parseCallExpr(StringRef & Expr,StringRef FuncName,std::optional<size_t> LineNumber,FileCheckPatternContext * Context,const SourceMgr & SM)69273471bf0Spatrick Pattern::parseCallExpr(StringRef &Expr, StringRef FuncName,
693*d415bd75Srobert                        std::optional<size_t> LineNumber,
69473471bf0Spatrick                        FileCheckPatternContext *Context, const SourceMgr &SM) {
69573471bf0Spatrick   Expr = Expr.ltrim(SpaceChars);
69673471bf0Spatrick   assert(Expr.startswith("("));
69773471bf0Spatrick 
698*d415bd75Srobert   auto OptFunc = StringSwitch<binop_eval_t>(FuncName)
69973471bf0Spatrick                      .Case("add", operator+)
70073471bf0Spatrick                      .Case("div", operator/)
70173471bf0Spatrick                      .Case("max", max)
70273471bf0Spatrick                      .Case("min", min)
70373471bf0Spatrick                      .Case("mul", operator*)
70473471bf0Spatrick                      .Case("sub", operator-)
705*d415bd75Srobert                      .Default(nullptr);
70673471bf0Spatrick 
70773471bf0Spatrick   if (!OptFunc)
70873471bf0Spatrick     return ErrorDiagnostic::get(
70973471bf0Spatrick         SM, FuncName, Twine("call to undefined function '") + FuncName + "'");
71073471bf0Spatrick 
71173471bf0Spatrick   Expr.consume_front("(");
71273471bf0Spatrick   Expr = Expr.ltrim(SpaceChars);
71373471bf0Spatrick 
71473471bf0Spatrick   // Parse call arguments, which are comma separated.
71573471bf0Spatrick   SmallVector<std::unique_ptr<ExpressionAST>, 4> Args;
71673471bf0Spatrick   while (!Expr.empty() && !Expr.startswith(")")) {
71773471bf0Spatrick     if (Expr.startswith(","))
71873471bf0Spatrick       return ErrorDiagnostic::get(SM, Expr, "missing argument");
71973471bf0Spatrick 
72073471bf0Spatrick     // Parse the argument, which is an arbitary expression.
72173471bf0Spatrick     StringRef OuterBinOpExpr = Expr;
72273471bf0Spatrick     Expected<std::unique_ptr<ExpressionAST>> Arg = parseNumericOperand(
72373471bf0Spatrick         Expr, AllowedOperand::Any, /*MaybeInvalidConstraint=*/false, LineNumber,
72473471bf0Spatrick         Context, SM);
72573471bf0Spatrick     while (Arg && !Expr.empty()) {
72673471bf0Spatrick       Expr = Expr.ltrim(SpaceChars);
72773471bf0Spatrick       // Have we reached an argument terminator?
72873471bf0Spatrick       if (Expr.startswith(",") || Expr.startswith(")"))
72973471bf0Spatrick         break;
73073471bf0Spatrick 
73173471bf0Spatrick       // Arg = Arg <op> <expr>
73273471bf0Spatrick       Arg = parseBinop(OuterBinOpExpr, Expr, std::move(*Arg), false, LineNumber,
73373471bf0Spatrick                        Context, SM);
73473471bf0Spatrick     }
73573471bf0Spatrick 
73673471bf0Spatrick     // Prefer an expression error over a generic invalid argument message.
73773471bf0Spatrick     if (!Arg)
73873471bf0Spatrick       return Arg.takeError();
73973471bf0Spatrick     Args.push_back(std::move(*Arg));
74073471bf0Spatrick 
74173471bf0Spatrick     // Have we parsed all available arguments?
74273471bf0Spatrick     Expr = Expr.ltrim(SpaceChars);
74373471bf0Spatrick     if (!Expr.consume_front(","))
74473471bf0Spatrick       break;
74573471bf0Spatrick 
74673471bf0Spatrick     Expr = Expr.ltrim(SpaceChars);
74773471bf0Spatrick     if (Expr.startswith(")"))
74873471bf0Spatrick       return ErrorDiagnostic::get(SM, Expr, "missing argument");
74973471bf0Spatrick   }
75073471bf0Spatrick 
75173471bf0Spatrick   if (!Expr.consume_front(")"))
75273471bf0Spatrick     return ErrorDiagnostic::get(SM, Expr,
75373471bf0Spatrick                                 "missing ')' at end of call expression");
75473471bf0Spatrick 
75573471bf0Spatrick   const unsigned NumArgs = Args.size();
75673471bf0Spatrick   if (NumArgs == 2)
75773471bf0Spatrick     return std::make_unique<BinaryOperation>(Expr, *OptFunc, std::move(Args[0]),
75873471bf0Spatrick                                              std::move(Args[1]));
75973471bf0Spatrick 
76073471bf0Spatrick   // TODO: Support more than binop_eval_t.
76173471bf0Spatrick   return ErrorDiagnostic::get(SM, FuncName,
76273471bf0Spatrick                               Twine("function '") + FuncName +
76373471bf0Spatrick                                   Twine("' takes 2 arguments but ") +
76473471bf0Spatrick                                   Twine(NumArgs) + " given");
76573471bf0Spatrick }
76673471bf0Spatrick 
parseNumericSubstitutionBlock(StringRef Expr,std::optional<NumericVariable * > & DefinedNumericVariable,bool IsLegacyLineExpr,std::optional<size_t> LineNumber,FileCheckPatternContext * Context,const SourceMgr & SM)76773471bf0Spatrick Expected<std::unique_ptr<Expression>> Pattern::parseNumericSubstitutionBlock(
768*d415bd75Srobert     StringRef Expr, std::optional<NumericVariable *> &DefinedNumericVariable,
769*d415bd75Srobert     bool IsLegacyLineExpr, std::optional<size_t> LineNumber,
77073471bf0Spatrick     FileCheckPatternContext *Context, const SourceMgr &SM) {
77173471bf0Spatrick   std::unique_ptr<ExpressionAST> ExpressionASTPointer = nullptr;
77273471bf0Spatrick   StringRef DefExpr = StringRef();
773*d415bd75Srobert   DefinedNumericVariable = std::nullopt;
77473471bf0Spatrick   ExpressionFormat ExplicitFormat = ExpressionFormat();
77573471bf0Spatrick   unsigned Precision = 0;
77673471bf0Spatrick 
77773471bf0Spatrick   // Parse format specifier (NOTE: ',' is also an argument seperator).
77873471bf0Spatrick   size_t FormatSpecEnd = Expr.find(',');
77973471bf0Spatrick   size_t FunctionStart = Expr.find('(');
78073471bf0Spatrick   if (FormatSpecEnd != StringRef::npos && FormatSpecEnd < FunctionStart) {
78173471bf0Spatrick     StringRef FormatExpr = Expr.take_front(FormatSpecEnd);
78273471bf0Spatrick     Expr = Expr.drop_front(FormatSpecEnd + 1);
78373471bf0Spatrick     FormatExpr = FormatExpr.trim(SpaceChars);
78473471bf0Spatrick     if (!FormatExpr.consume_front("%"))
78573471bf0Spatrick       return ErrorDiagnostic::get(
78673471bf0Spatrick           SM, FormatExpr,
78773471bf0Spatrick           "invalid matching format specification in expression");
78873471bf0Spatrick 
78973471bf0Spatrick     // Parse alternate form flag.
79073471bf0Spatrick     SMLoc AlternateFormFlagLoc = SMLoc::getFromPointer(FormatExpr.data());
79173471bf0Spatrick     bool AlternateForm = FormatExpr.consume_front("#");
79273471bf0Spatrick 
79373471bf0Spatrick     // Parse precision.
79473471bf0Spatrick     if (FormatExpr.consume_front(".")) {
79573471bf0Spatrick       if (FormatExpr.consumeInteger(10, Precision))
79673471bf0Spatrick         return ErrorDiagnostic::get(SM, FormatExpr,
79773471bf0Spatrick                                     "invalid precision in format specifier");
79873471bf0Spatrick     }
79973471bf0Spatrick 
80073471bf0Spatrick     if (!FormatExpr.empty()) {
80173471bf0Spatrick       // Check for unknown matching format specifier and set matching format in
80273471bf0Spatrick       // class instance representing this expression.
80373471bf0Spatrick       SMLoc FmtLoc = SMLoc::getFromPointer(FormatExpr.data());
80473471bf0Spatrick       switch (popFront(FormatExpr)) {
80573471bf0Spatrick       case 'u':
80673471bf0Spatrick         ExplicitFormat =
80773471bf0Spatrick             ExpressionFormat(ExpressionFormat::Kind::Unsigned, Precision);
80873471bf0Spatrick         break;
80973471bf0Spatrick       case 'd':
81073471bf0Spatrick         ExplicitFormat =
81173471bf0Spatrick             ExpressionFormat(ExpressionFormat::Kind::Signed, Precision);
81273471bf0Spatrick         break;
81373471bf0Spatrick       case 'x':
81473471bf0Spatrick         ExplicitFormat = ExpressionFormat(ExpressionFormat::Kind::HexLower,
81573471bf0Spatrick                                           Precision, AlternateForm);
81673471bf0Spatrick         break;
81773471bf0Spatrick       case 'X':
81873471bf0Spatrick         ExplicitFormat = ExpressionFormat(ExpressionFormat::Kind::HexUpper,
81973471bf0Spatrick                                           Precision, AlternateForm);
82073471bf0Spatrick         break;
82173471bf0Spatrick       default:
82273471bf0Spatrick         return ErrorDiagnostic::get(SM, FmtLoc,
82373471bf0Spatrick                                     "invalid format specifier in expression");
82473471bf0Spatrick       }
82573471bf0Spatrick     }
82673471bf0Spatrick 
82773471bf0Spatrick     if (AlternateForm && ExplicitFormat != ExpressionFormat::Kind::HexLower &&
82873471bf0Spatrick         ExplicitFormat != ExpressionFormat::Kind::HexUpper)
82973471bf0Spatrick       return ErrorDiagnostic::get(
83073471bf0Spatrick           SM, AlternateFormFlagLoc,
83173471bf0Spatrick           "alternate form only supported for hex values");
83273471bf0Spatrick 
83373471bf0Spatrick     FormatExpr = FormatExpr.ltrim(SpaceChars);
83473471bf0Spatrick     if (!FormatExpr.empty())
83573471bf0Spatrick       return ErrorDiagnostic::get(
83673471bf0Spatrick           SM, FormatExpr,
83773471bf0Spatrick           "invalid matching format specification in expression");
83873471bf0Spatrick   }
83973471bf0Spatrick 
84073471bf0Spatrick   // Save variable definition expression if any.
84173471bf0Spatrick   size_t DefEnd = Expr.find(':');
84273471bf0Spatrick   if (DefEnd != StringRef::npos) {
84373471bf0Spatrick     DefExpr = Expr.substr(0, DefEnd);
84473471bf0Spatrick     Expr = Expr.substr(DefEnd + 1);
84573471bf0Spatrick   }
84673471bf0Spatrick 
84773471bf0Spatrick   // Parse matching constraint.
84873471bf0Spatrick   Expr = Expr.ltrim(SpaceChars);
84973471bf0Spatrick   bool HasParsedValidConstraint = false;
85073471bf0Spatrick   if (Expr.consume_front("=="))
85173471bf0Spatrick     HasParsedValidConstraint = true;
85273471bf0Spatrick 
85373471bf0Spatrick   // Parse the expression itself.
85473471bf0Spatrick   Expr = Expr.ltrim(SpaceChars);
85573471bf0Spatrick   if (Expr.empty()) {
85673471bf0Spatrick     if (HasParsedValidConstraint)
85773471bf0Spatrick       return ErrorDiagnostic::get(
85873471bf0Spatrick           SM, Expr, "empty numeric expression should not have a constraint");
85973471bf0Spatrick   } else {
86073471bf0Spatrick     Expr = Expr.rtrim(SpaceChars);
86173471bf0Spatrick     StringRef OuterBinOpExpr = Expr;
86273471bf0Spatrick     // The first operand in a legacy @LINE expression is always the @LINE
86373471bf0Spatrick     // pseudo variable.
86473471bf0Spatrick     AllowedOperand AO =
86573471bf0Spatrick         IsLegacyLineExpr ? AllowedOperand::LineVar : AllowedOperand::Any;
86673471bf0Spatrick     Expected<std::unique_ptr<ExpressionAST>> ParseResult = parseNumericOperand(
86773471bf0Spatrick         Expr, AO, !HasParsedValidConstraint, LineNumber, Context, SM);
86873471bf0Spatrick     while (ParseResult && !Expr.empty()) {
86973471bf0Spatrick       ParseResult = parseBinop(OuterBinOpExpr, Expr, std::move(*ParseResult),
87073471bf0Spatrick                                IsLegacyLineExpr, LineNumber, Context, SM);
87173471bf0Spatrick       // Legacy @LINE expressions only allow 2 operands.
87273471bf0Spatrick       if (ParseResult && IsLegacyLineExpr && !Expr.empty())
87373471bf0Spatrick         return ErrorDiagnostic::get(
87473471bf0Spatrick             SM, Expr,
87573471bf0Spatrick             "unexpected characters at end of expression '" + Expr + "'");
87673471bf0Spatrick     }
87773471bf0Spatrick     if (!ParseResult)
87873471bf0Spatrick       return ParseResult.takeError();
87973471bf0Spatrick     ExpressionASTPointer = std::move(*ParseResult);
88073471bf0Spatrick   }
88173471bf0Spatrick 
88273471bf0Spatrick   // Select format of the expression, i.e. (i) its explicit format, if any,
88373471bf0Spatrick   // otherwise (ii) its implicit format, if any, otherwise (iii) the default
88473471bf0Spatrick   // format (unsigned). Error out in case of conflicting implicit format
88573471bf0Spatrick   // without explicit format.
88673471bf0Spatrick   ExpressionFormat Format;
88773471bf0Spatrick   if (ExplicitFormat)
88873471bf0Spatrick     Format = ExplicitFormat;
88973471bf0Spatrick   else if (ExpressionASTPointer) {
89073471bf0Spatrick     Expected<ExpressionFormat> ImplicitFormat =
89173471bf0Spatrick         ExpressionASTPointer->getImplicitFormat(SM);
89273471bf0Spatrick     if (!ImplicitFormat)
89373471bf0Spatrick       return ImplicitFormat.takeError();
89473471bf0Spatrick     Format = *ImplicitFormat;
89573471bf0Spatrick   }
89673471bf0Spatrick   if (!Format)
89773471bf0Spatrick     Format = ExpressionFormat(ExpressionFormat::Kind::Unsigned, Precision);
89873471bf0Spatrick 
89973471bf0Spatrick   std::unique_ptr<Expression> ExpressionPointer =
90073471bf0Spatrick       std::make_unique<Expression>(std::move(ExpressionASTPointer), Format);
90173471bf0Spatrick 
90273471bf0Spatrick   // Parse the numeric variable definition.
90373471bf0Spatrick   if (DefEnd != StringRef::npos) {
90473471bf0Spatrick     DefExpr = DefExpr.ltrim(SpaceChars);
90573471bf0Spatrick     Expected<NumericVariable *> ParseResult = parseNumericVariableDefinition(
90673471bf0Spatrick         DefExpr, Context, LineNumber, ExpressionPointer->getFormat(), SM);
90773471bf0Spatrick 
90873471bf0Spatrick     if (!ParseResult)
90973471bf0Spatrick       return ParseResult.takeError();
91073471bf0Spatrick     DefinedNumericVariable = *ParseResult;
91173471bf0Spatrick   }
91273471bf0Spatrick 
91373471bf0Spatrick   return std::move(ExpressionPointer);
91473471bf0Spatrick }
91573471bf0Spatrick 
parsePattern(StringRef PatternStr,StringRef Prefix,SourceMgr & SM,const FileCheckRequest & Req)91673471bf0Spatrick bool Pattern::parsePattern(StringRef PatternStr, StringRef Prefix,
91773471bf0Spatrick                            SourceMgr &SM, const FileCheckRequest &Req) {
91873471bf0Spatrick   bool MatchFullLinesHere = Req.MatchFullLines && CheckTy != Check::CheckNot;
91973471bf0Spatrick   IgnoreCase = Req.IgnoreCase;
92073471bf0Spatrick 
92173471bf0Spatrick   PatternLoc = SMLoc::getFromPointer(PatternStr.data());
92273471bf0Spatrick 
92373471bf0Spatrick   if (!(Req.NoCanonicalizeWhiteSpace && Req.MatchFullLines))
92473471bf0Spatrick     // Ignore trailing whitespace.
92573471bf0Spatrick     while (!PatternStr.empty() &&
92673471bf0Spatrick            (PatternStr.back() == ' ' || PatternStr.back() == '\t'))
92773471bf0Spatrick       PatternStr = PatternStr.substr(0, PatternStr.size() - 1);
92873471bf0Spatrick 
92973471bf0Spatrick   // Check that there is something on the line.
93073471bf0Spatrick   if (PatternStr.empty() && CheckTy != Check::CheckEmpty) {
93173471bf0Spatrick     SM.PrintMessage(PatternLoc, SourceMgr::DK_Error,
93273471bf0Spatrick                     "found empty check string with prefix '" + Prefix + ":'");
93373471bf0Spatrick     return true;
93473471bf0Spatrick   }
93573471bf0Spatrick 
93673471bf0Spatrick   if (!PatternStr.empty() && CheckTy == Check::CheckEmpty) {
93773471bf0Spatrick     SM.PrintMessage(
93873471bf0Spatrick         PatternLoc, SourceMgr::DK_Error,
93973471bf0Spatrick         "found non-empty check string for empty check with prefix '" + Prefix +
94073471bf0Spatrick             ":'");
94173471bf0Spatrick     return true;
94273471bf0Spatrick   }
94373471bf0Spatrick 
94473471bf0Spatrick   if (CheckTy == Check::CheckEmpty) {
94573471bf0Spatrick     RegExStr = "(\n$)";
94673471bf0Spatrick     return false;
94773471bf0Spatrick   }
94873471bf0Spatrick 
94973471bf0Spatrick   // If literal check, set fixed string.
95073471bf0Spatrick   if (CheckTy.isLiteralMatch()) {
95173471bf0Spatrick     FixedStr = PatternStr;
95273471bf0Spatrick     return false;
95373471bf0Spatrick   }
95473471bf0Spatrick 
95573471bf0Spatrick   // Check to see if this is a fixed string, or if it has regex pieces.
95673471bf0Spatrick   if (!MatchFullLinesHere &&
957*d415bd75Srobert       (PatternStr.size() < 2 ||
958*d415bd75Srobert        (!PatternStr.contains("{{") && !PatternStr.contains("[[")))) {
95973471bf0Spatrick     FixedStr = PatternStr;
96073471bf0Spatrick     return false;
96173471bf0Spatrick   }
96273471bf0Spatrick 
96373471bf0Spatrick   if (MatchFullLinesHere) {
96473471bf0Spatrick     RegExStr += '^';
96573471bf0Spatrick     if (!Req.NoCanonicalizeWhiteSpace)
96673471bf0Spatrick       RegExStr += " *";
96773471bf0Spatrick   }
96873471bf0Spatrick 
96973471bf0Spatrick   // Paren value #0 is for the fully matched string.  Any new parenthesized
97073471bf0Spatrick   // values add from there.
97173471bf0Spatrick   unsigned CurParen = 1;
97273471bf0Spatrick 
97373471bf0Spatrick   // Otherwise, there is at least one regex piece.  Build up the regex pattern
97473471bf0Spatrick   // by escaping scary characters in fixed strings, building up one big regex.
97573471bf0Spatrick   while (!PatternStr.empty()) {
97673471bf0Spatrick     // RegEx matches.
97773471bf0Spatrick     if (PatternStr.startswith("{{")) {
97873471bf0Spatrick       // This is the start of a regex match.  Scan for the }}.
97973471bf0Spatrick       size_t End = PatternStr.find("}}");
98073471bf0Spatrick       if (End == StringRef::npos) {
98173471bf0Spatrick         SM.PrintMessage(SMLoc::getFromPointer(PatternStr.data()),
98273471bf0Spatrick                         SourceMgr::DK_Error,
98373471bf0Spatrick                         "found start of regex string with no end '}}'");
98473471bf0Spatrick         return true;
98573471bf0Spatrick       }
98673471bf0Spatrick 
98773471bf0Spatrick       // Enclose {{}} patterns in parens just like [[]] even though we're not
98873471bf0Spatrick       // capturing the result for any purpose.  This is required in case the
98973471bf0Spatrick       // expression contains an alternation like: CHECK:  abc{{x|z}}def.  We
99073471bf0Spatrick       // want this to turn into: "abc(x|z)def" not "abcx|zdef".
99173471bf0Spatrick       RegExStr += '(';
99273471bf0Spatrick       ++CurParen;
99373471bf0Spatrick 
99473471bf0Spatrick       if (AddRegExToRegEx(PatternStr.substr(2, End - 2), CurParen, SM))
99573471bf0Spatrick         return true;
99673471bf0Spatrick       RegExStr += ')';
99773471bf0Spatrick 
99873471bf0Spatrick       PatternStr = PatternStr.substr(End + 2);
99973471bf0Spatrick       continue;
100073471bf0Spatrick     }
100173471bf0Spatrick 
100273471bf0Spatrick     // String and numeric substitution blocks. Pattern substitution blocks come
100373471bf0Spatrick     // in two forms: [[foo:.*]] and [[foo]]. The former matches .* (or some
100473471bf0Spatrick     // other regex) and assigns it to the string variable 'foo'. The latter
100573471bf0Spatrick     // substitutes foo's value. Numeric substitution blocks recognize the same
100673471bf0Spatrick     // form as string ones, but start with a '#' sign after the double
100773471bf0Spatrick     // brackets. They also accept a combined form which sets a numeric variable
100873471bf0Spatrick     // to the evaluation of an expression. Both string and numeric variable
100973471bf0Spatrick     // names must satisfy the regular expression "[a-zA-Z_][0-9a-zA-Z_]*" to be
1010*d415bd75Srobert     // valid, as this helps catch some common errors. If there are extra '['s
1011*d415bd75Srobert     // before the "[[", treat them literally.
1012*d415bd75Srobert     if (PatternStr.startswith("[[") && !PatternStr.startswith("[[[")) {
101373471bf0Spatrick       StringRef UnparsedPatternStr = PatternStr.substr(2);
101473471bf0Spatrick       // Find the closing bracket pair ending the match.  End is going to be an
101573471bf0Spatrick       // offset relative to the beginning of the match string.
101673471bf0Spatrick       size_t End = FindRegexVarEnd(UnparsedPatternStr, SM);
101773471bf0Spatrick       StringRef MatchStr = UnparsedPatternStr.substr(0, End);
101873471bf0Spatrick       bool IsNumBlock = MatchStr.consume_front("#");
101973471bf0Spatrick 
102073471bf0Spatrick       if (End == StringRef::npos) {
102173471bf0Spatrick         SM.PrintMessage(SMLoc::getFromPointer(PatternStr.data()),
102273471bf0Spatrick                         SourceMgr::DK_Error,
102373471bf0Spatrick                         "Invalid substitution block, no ]] found");
102473471bf0Spatrick         return true;
102573471bf0Spatrick       }
102673471bf0Spatrick       // Strip the substitution block we are parsing. End points to the start
102773471bf0Spatrick       // of the "]]" closing the expression so account for it in computing the
102873471bf0Spatrick       // index of the first unparsed character.
102973471bf0Spatrick       PatternStr = UnparsedPatternStr.substr(End + 2);
103073471bf0Spatrick 
103173471bf0Spatrick       bool IsDefinition = false;
103273471bf0Spatrick       bool SubstNeeded = false;
103373471bf0Spatrick       // Whether the substitution block is a legacy use of @LINE with string
103473471bf0Spatrick       // substitution block syntax.
103573471bf0Spatrick       bool IsLegacyLineExpr = false;
103673471bf0Spatrick       StringRef DefName;
103773471bf0Spatrick       StringRef SubstStr;
1038*d415bd75Srobert       StringRef MatchRegexp;
1039*d415bd75Srobert       std::string WildcardRegexp;
104073471bf0Spatrick       size_t SubstInsertIdx = RegExStr.size();
104173471bf0Spatrick 
104273471bf0Spatrick       // Parse string variable or legacy @LINE expression.
104373471bf0Spatrick       if (!IsNumBlock) {
104473471bf0Spatrick         size_t VarEndIdx = MatchStr.find(':');
104573471bf0Spatrick         size_t SpacePos = MatchStr.substr(0, VarEndIdx).find_first_of(" \t");
104673471bf0Spatrick         if (SpacePos != StringRef::npos) {
104773471bf0Spatrick           SM.PrintMessage(SMLoc::getFromPointer(MatchStr.data() + SpacePos),
104873471bf0Spatrick                           SourceMgr::DK_Error, "unexpected whitespace");
104973471bf0Spatrick           return true;
105073471bf0Spatrick         }
105173471bf0Spatrick 
105273471bf0Spatrick         // Get the name (e.g. "foo") and verify it is well formed.
105373471bf0Spatrick         StringRef OrigMatchStr = MatchStr;
105473471bf0Spatrick         Expected<Pattern::VariableProperties> ParseVarResult =
105573471bf0Spatrick             parseVariable(MatchStr, SM);
105673471bf0Spatrick         if (!ParseVarResult) {
105773471bf0Spatrick           logAllUnhandledErrors(ParseVarResult.takeError(), errs());
105873471bf0Spatrick           return true;
105973471bf0Spatrick         }
106073471bf0Spatrick         StringRef Name = ParseVarResult->Name;
106173471bf0Spatrick         bool IsPseudo = ParseVarResult->IsPseudo;
106273471bf0Spatrick 
106373471bf0Spatrick         IsDefinition = (VarEndIdx != StringRef::npos);
106473471bf0Spatrick         SubstNeeded = !IsDefinition;
106573471bf0Spatrick         if (IsDefinition) {
106673471bf0Spatrick           if ((IsPseudo || !MatchStr.consume_front(":"))) {
106773471bf0Spatrick             SM.PrintMessage(SMLoc::getFromPointer(Name.data()),
106873471bf0Spatrick                             SourceMgr::DK_Error,
106973471bf0Spatrick                             "invalid name in string variable definition");
107073471bf0Spatrick             return true;
107173471bf0Spatrick           }
107273471bf0Spatrick 
107373471bf0Spatrick           // Detect collisions between string and numeric variables when the
107473471bf0Spatrick           // former is created later than the latter.
107573471bf0Spatrick           if (Context->GlobalNumericVariableTable.find(Name) !=
107673471bf0Spatrick               Context->GlobalNumericVariableTable.end()) {
107773471bf0Spatrick             SM.PrintMessage(
107873471bf0Spatrick                 SMLoc::getFromPointer(Name.data()), SourceMgr::DK_Error,
107973471bf0Spatrick                 "numeric variable with name '" + Name + "' already exists");
108073471bf0Spatrick             return true;
108173471bf0Spatrick           }
108273471bf0Spatrick           DefName = Name;
1083*d415bd75Srobert           MatchRegexp = MatchStr;
108473471bf0Spatrick         } else {
108573471bf0Spatrick           if (IsPseudo) {
108673471bf0Spatrick             MatchStr = OrigMatchStr;
108773471bf0Spatrick             IsLegacyLineExpr = IsNumBlock = true;
108873471bf0Spatrick           } else {
108973471bf0Spatrick             if (!MatchStr.empty()) {
109073471bf0Spatrick               SM.PrintMessage(SMLoc::getFromPointer(Name.data()),
109173471bf0Spatrick                               SourceMgr::DK_Error,
109273471bf0Spatrick                               "invalid name in string variable use");
109373471bf0Spatrick               return true;
109473471bf0Spatrick             }
109573471bf0Spatrick             SubstStr = Name;
109673471bf0Spatrick           }
109773471bf0Spatrick         }
109873471bf0Spatrick       }
109973471bf0Spatrick 
110073471bf0Spatrick       // Parse numeric substitution block.
110173471bf0Spatrick       std::unique_ptr<Expression> ExpressionPointer;
1102*d415bd75Srobert       std::optional<NumericVariable *> DefinedNumericVariable;
110373471bf0Spatrick       if (IsNumBlock) {
110473471bf0Spatrick         Expected<std::unique_ptr<Expression>> ParseResult =
110573471bf0Spatrick             parseNumericSubstitutionBlock(MatchStr, DefinedNumericVariable,
110673471bf0Spatrick                                           IsLegacyLineExpr, LineNumber, Context,
110773471bf0Spatrick                                           SM);
110873471bf0Spatrick         if (!ParseResult) {
110973471bf0Spatrick           logAllUnhandledErrors(ParseResult.takeError(), errs());
111073471bf0Spatrick           return true;
111173471bf0Spatrick         }
111273471bf0Spatrick         ExpressionPointer = std::move(*ParseResult);
111373471bf0Spatrick         SubstNeeded = ExpressionPointer->getAST() != nullptr;
111473471bf0Spatrick         if (DefinedNumericVariable) {
111573471bf0Spatrick           IsDefinition = true;
111673471bf0Spatrick           DefName = (*DefinedNumericVariable)->getName();
111773471bf0Spatrick         }
111873471bf0Spatrick         if (SubstNeeded)
111973471bf0Spatrick           SubstStr = MatchStr;
112073471bf0Spatrick         else {
112173471bf0Spatrick           ExpressionFormat Format = ExpressionPointer->getFormat();
1122*d415bd75Srobert           WildcardRegexp = cantFail(Format.getWildcardRegex());
1123*d415bd75Srobert           MatchRegexp = WildcardRegexp;
112473471bf0Spatrick         }
112573471bf0Spatrick       }
112673471bf0Spatrick 
112773471bf0Spatrick       // Handle variable definition: [[<def>:(...)]] and [[#(...)<def>:(...)]].
112873471bf0Spatrick       if (IsDefinition) {
112973471bf0Spatrick         RegExStr += '(';
113073471bf0Spatrick         ++SubstInsertIdx;
113173471bf0Spatrick 
113273471bf0Spatrick         if (IsNumBlock) {
113373471bf0Spatrick           NumericVariableMatch NumericVariableDefinition = {
113473471bf0Spatrick               *DefinedNumericVariable, CurParen};
113573471bf0Spatrick           NumericVariableDefs[DefName] = NumericVariableDefinition;
113673471bf0Spatrick           // This store is done here rather than in match() to allow
113773471bf0Spatrick           // parseNumericVariableUse() to get the pointer to the class instance
113873471bf0Spatrick           // of the right variable definition corresponding to a given numeric
113973471bf0Spatrick           // variable use.
114073471bf0Spatrick           Context->GlobalNumericVariableTable[DefName] =
114173471bf0Spatrick               *DefinedNumericVariable;
114273471bf0Spatrick         } else {
114373471bf0Spatrick           VariableDefs[DefName] = CurParen;
114473471bf0Spatrick           // Mark string variable as defined to detect collisions between
114573471bf0Spatrick           // string and numeric variables in parseNumericVariableUse() and
114673471bf0Spatrick           // defineCmdlineVariables() when the latter is created later than the
114773471bf0Spatrick           // former. We cannot reuse GlobalVariableTable for this by populating
114873471bf0Spatrick           // it with an empty string since we would then lose the ability to
114973471bf0Spatrick           // detect the use of an undefined variable in match().
115073471bf0Spatrick           Context->DefinedVariableTable[DefName] = true;
115173471bf0Spatrick         }
115273471bf0Spatrick 
115373471bf0Spatrick         ++CurParen;
115473471bf0Spatrick       }
115573471bf0Spatrick 
115673471bf0Spatrick       if (!MatchRegexp.empty() && AddRegExToRegEx(MatchRegexp, CurParen, SM))
115773471bf0Spatrick         return true;
115873471bf0Spatrick 
115973471bf0Spatrick       if (IsDefinition)
116073471bf0Spatrick         RegExStr += ')';
116173471bf0Spatrick 
116273471bf0Spatrick       // Handle substitutions: [[foo]] and [[#<foo expr>]].
116373471bf0Spatrick       if (SubstNeeded) {
116473471bf0Spatrick         // Handle substitution of string variables that were defined earlier on
116573471bf0Spatrick         // the same line by emitting a backreference. Expressions do not
116673471bf0Spatrick         // support substituting a numeric variable defined on the same line.
116773471bf0Spatrick         if (!IsNumBlock && VariableDefs.find(SubstStr) != VariableDefs.end()) {
116873471bf0Spatrick           unsigned CaptureParenGroup = VariableDefs[SubstStr];
116973471bf0Spatrick           if (CaptureParenGroup < 1 || CaptureParenGroup > 9) {
117073471bf0Spatrick             SM.PrintMessage(SMLoc::getFromPointer(SubstStr.data()),
117173471bf0Spatrick                             SourceMgr::DK_Error,
117273471bf0Spatrick                             "Can't back-reference more than 9 variables");
117373471bf0Spatrick             return true;
117473471bf0Spatrick           }
117573471bf0Spatrick           AddBackrefToRegEx(CaptureParenGroup);
117673471bf0Spatrick         } else {
117773471bf0Spatrick           // Handle substitution of string variables ([[<var>]]) defined in
117873471bf0Spatrick           // previous CHECK patterns, and substitution of expressions.
117973471bf0Spatrick           Substitution *Substitution =
118073471bf0Spatrick               IsNumBlock
118173471bf0Spatrick                   ? Context->makeNumericSubstitution(
118273471bf0Spatrick                         SubstStr, std::move(ExpressionPointer), SubstInsertIdx)
118373471bf0Spatrick                   : Context->makeStringSubstitution(SubstStr, SubstInsertIdx);
118473471bf0Spatrick           Substitutions.push_back(Substitution);
118573471bf0Spatrick         }
118673471bf0Spatrick       }
1187*d415bd75Srobert 
1188*d415bd75Srobert       continue;
118973471bf0Spatrick     }
119073471bf0Spatrick 
119173471bf0Spatrick     // Handle fixed string matches.
119273471bf0Spatrick     // Find the end, which is the start of the next regex.
1193*d415bd75Srobert     size_t FixedMatchEnd =
1194*d415bd75Srobert         std::min(PatternStr.find("{{", 1), PatternStr.find("[[", 1));
119573471bf0Spatrick     RegExStr += Regex::escape(PatternStr.substr(0, FixedMatchEnd));
119673471bf0Spatrick     PatternStr = PatternStr.substr(FixedMatchEnd);
119773471bf0Spatrick   }
119873471bf0Spatrick 
119973471bf0Spatrick   if (MatchFullLinesHere) {
120073471bf0Spatrick     if (!Req.NoCanonicalizeWhiteSpace)
120173471bf0Spatrick       RegExStr += " *";
120273471bf0Spatrick     RegExStr += '$';
120373471bf0Spatrick   }
120473471bf0Spatrick 
120573471bf0Spatrick   return false;
120673471bf0Spatrick }
120773471bf0Spatrick 
AddRegExToRegEx(StringRef RS,unsigned & CurParen,SourceMgr & SM)120873471bf0Spatrick bool Pattern::AddRegExToRegEx(StringRef RS, unsigned &CurParen, SourceMgr &SM) {
120973471bf0Spatrick   Regex R(RS);
121073471bf0Spatrick   std::string Error;
121173471bf0Spatrick   if (!R.isValid(Error)) {
121273471bf0Spatrick     SM.PrintMessage(SMLoc::getFromPointer(RS.data()), SourceMgr::DK_Error,
121373471bf0Spatrick                     "invalid regex: " + Error);
121473471bf0Spatrick     return true;
121573471bf0Spatrick   }
121673471bf0Spatrick 
121773471bf0Spatrick   RegExStr += RS.str();
121873471bf0Spatrick   CurParen += R.getNumMatches();
121973471bf0Spatrick   return false;
122073471bf0Spatrick }
122173471bf0Spatrick 
AddBackrefToRegEx(unsigned BackrefNum)122273471bf0Spatrick void Pattern::AddBackrefToRegEx(unsigned BackrefNum) {
122373471bf0Spatrick   assert(BackrefNum >= 1 && BackrefNum <= 9 && "Invalid backref number");
122473471bf0Spatrick   std::string Backref = std::string("\\") + std::string(1, '0' + BackrefNum);
122573471bf0Spatrick   RegExStr += Backref;
122673471bf0Spatrick }
122773471bf0Spatrick 
match(StringRef Buffer,const SourceMgr & SM) const122873471bf0Spatrick Pattern::MatchResult Pattern::match(StringRef Buffer,
122973471bf0Spatrick                                     const SourceMgr &SM) const {
123073471bf0Spatrick   // If this is the EOF pattern, match it immediately.
123173471bf0Spatrick   if (CheckTy == Check::CheckEOF)
123273471bf0Spatrick     return MatchResult(Buffer.size(), 0, Error::success());
123373471bf0Spatrick 
123473471bf0Spatrick   // If this is a fixed string pattern, just match it now.
123573471bf0Spatrick   if (!FixedStr.empty()) {
123673471bf0Spatrick     size_t Pos =
123773471bf0Spatrick         IgnoreCase ? Buffer.find_insensitive(FixedStr) : Buffer.find(FixedStr);
123873471bf0Spatrick     if (Pos == StringRef::npos)
123973471bf0Spatrick       return make_error<NotFoundError>();
124073471bf0Spatrick     return MatchResult(Pos, /*MatchLen=*/FixedStr.size(), Error::success());
124173471bf0Spatrick   }
124273471bf0Spatrick 
124373471bf0Spatrick   // Regex match.
124473471bf0Spatrick 
124573471bf0Spatrick   // If there are substitutions, we need to create a temporary string with the
124673471bf0Spatrick   // actual value.
124773471bf0Spatrick   StringRef RegExToMatch = RegExStr;
124873471bf0Spatrick   std::string TmpStr;
124973471bf0Spatrick   if (!Substitutions.empty()) {
125073471bf0Spatrick     TmpStr = RegExStr;
125173471bf0Spatrick     if (LineNumber)
125273471bf0Spatrick       Context->LineVariable->setValue(ExpressionValue(*LineNumber));
125373471bf0Spatrick 
125473471bf0Spatrick     size_t InsertOffset = 0;
125573471bf0Spatrick     // Substitute all string variables and expressions whose values are only
125673471bf0Spatrick     // now known. Use of string variables defined on the same line are handled
125773471bf0Spatrick     // by back-references.
125873471bf0Spatrick     Error Errs = Error::success();
125973471bf0Spatrick     for (const auto &Substitution : Substitutions) {
126073471bf0Spatrick       // Substitute and check for failure (e.g. use of undefined variable).
126173471bf0Spatrick       Expected<std::string> Value = Substitution->getResult();
126273471bf0Spatrick       if (!Value) {
126373471bf0Spatrick         // Convert to an ErrorDiagnostic to get location information. This is
126473471bf0Spatrick         // done here rather than printMatch/printNoMatch since now we know which
126573471bf0Spatrick         // substitution block caused the overflow.
126673471bf0Spatrick         Errs = joinErrors(std::move(Errs),
126773471bf0Spatrick                           handleErrors(
126873471bf0Spatrick                               Value.takeError(),
126973471bf0Spatrick                               [&](const OverflowError &E) {
127073471bf0Spatrick                                 return ErrorDiagnostic::get(
127173471bf0Spatrick                                     SM, Substitution->getFromString(),
127273471bf0Spatrick                                     "unable to substitute variable or "
127373471bf0Spatrick                                     "numeric expression: overflow error");
127473471bf0Spatrick                               },
127573471bf0Spatrick                               [&SM](const UndefVarError &E) {
127673471bf0Spatrick                                 return ErrorDiagnostic::get(SM, E.getVarName(),
127773471bf0Spatrick                                                             E.message());
127873471bf0Spatrick                               }));
127973471bf0Spatrick         continue;
128073471bf0Spatrick       }
128173471bf0Spatrick 
128273471bf0Spatrick       // Plop it into the regex at the adjusted offset.
128373471bf0Spatrick       TmpStr.insert(TmpStr.begin() + Substitution->getIndex() + InsertOffset,
128473471bf0Spatrick                     Value->begin(), Value->end());
128573471bf0Spatrick       InsertOffset += Value->size();
128673471bf0Spatrick     }
128773471bf0Spatrick     if (Errs)
128873471bf0Spatrick       return std::move(Errs);
128973471bf0Spatrick 
129073471bf0Spatrick     // Match the newly constructed regex.
129173471bf0Spatrick     RegExToMatch = TmpStr;
129273471bf0Spatrick   }
129373471bf0Spatrick 
129473471bf0Spatrick   SmallVector<StringRef, 4> MatchInfo;
129573471bf0Spatrick   unsigned int Flags = Regex::Newline;
129673471bf0Spatrick   if (IgnoreCase)
129773471bf0Spatrick     Flags |= Regex::IgnoreCase;
129873471bf0Spatrick   if (!Regex(RegExToMatch, Flags).match(Buffer, &MatchInfo))
129973471bf0Spatrick     return make_error<NotFoundError>();
130073471bf0Spatrick 
130173471bf0Spatrick   // Successful regex match.
130273471bf0Spatrick   assert(!MatchInfo.empty() && "Didn't get any match");
130373471bf0Spatrick   StringRef FullMatch = MatchInfo[0];
130473471bf0Spatrick 
130573471bf0Spatrick   // If this defines any string variables, remember their values.
130673471bf0Spatrick   for (const auto &VariableDef : VariableDefs) {
130773471bf0Spatrick     assert(VariableDef.second < MatchInfo.size() && "Internal paren error");
130873471bf0Spatrick     Context->GlobalVariableTable[VariableDef.first] =
130973471bf0Spatrick         MatchInfo[VariableDef.second];
131073471bf0Spatrick   }
131173471bf0Spatrick 
131273471bf0Spatrick   // Like CHECK-NEXT, CHECK-EMPTY's match range is considered to start after
131373471bf0Spatrick   // the required preceding newline, which is consumed by the pattern in the
131473471bf0Spatrick   // case of CHECK-EMPTY but not CHECK-NEXT.
131573471bf0Spatrick   size_t MatchStartSkip = CheckTy == Check::CheckEmpty;
131673471bf0Spatrick   Match TheMatch;
131773471bf0Spatrick   TheMatch.Pos = FullMatch.data() - Buffer.data() + MatchStartSkip;
131873471bf0Spatrick   TheMatch.Len = FullMatch.size() - MatchStartSkip;
131973471bf0Spatrick 
132073471bf0Spatrick   // If this defines any numeric variables, remember their values.
132173471bf0Spatrick   for (const auto &NumericVariableDef : NumericVariableDefs) {
132273471bf0Spatrick     const NumericVariableMatch &NumericVariableMatch =
132373471bf0Spatrick         NumericVariableDef.getValue();
132473471bf0Spatrick     unsigned CaptureParenGroup = NumericVariableMatch.CaptureParenGroup;
132573471bf0Spatrick     assert(CaptureParenGroup < MatchInfo.size() && "Internal paren error");
132673471bf0Spatrick     NumericVariable *DefinedNumericVariable =
132773471bf0Spatrick         NumericVariableMatch.DefinedNumericVariable;
132873471bf0Spatrick 
132973471bf0Spatrick     StringRef MatchedValue = MatchInfo[CaptureParenGroup];
133073471bf0Spatrick     ExpressionFormat Format = DefinedNumericVariable->getImplicitFormat();
133173471bf0Spatrick     Expected<ExpressionValue> Value =
133273471bf0Spatrick         Format.valueFromStringRepr(MatchedValue, SM);
133373471bf0Spatrick     if (!Value)
133473471bf0Spatrick       return MatchResult(TheMatch, Value.takeError());
133573471bf0Spatrick     DefinedNumericVariable->setValue(*Value, MatchedValue);
133673471bf0Spatrick   }
133773471bf0Spatrick 
133873471bf0Spatrick   return MatchResult(TheMatch, Error::success());
133973471bf0Spatrick }
134073471bf0Spatrick 
computeMatchDistance(StringRef Buffer) const134173471bf0Spatrick unsigned Pattern::computeMatchDistance(StringRef Buffer) const {
134273471bf0Spatrick   // Just compute the number of matching characters. For regular expressions, we
134373471bf0Spatrick   // just compare against the regex itself and hope for the best.
134473471bf0Spatrick   //
134573471bf0Spatrick   // FIXME: One easy improvement here is have the regex lib generate a single
134673471bf0Spatrick   // example regular expression which matches, and use that as the example
134773471bf0Spatrick   // string.
134873471bf0Spatrick   StringRef ExampleString(FixedStr);
134973471bf0Spatrick   if (ExampleString.empty())
135073471bf0Spatrick     ExampleString = RegExStr;
135173471bf0Spatrick 
135273471bf0Spatrick   // Only compare up to the first line in the buffer, or the string size.
135373471bf0Spatrick   StringRef BufferPrefix = Buffer.substr(0, ExampleString.size());
135473471bf0Spatrick   BufferPrefix = BufferPrefix.split('\n').first;
135573471bf0Spatrick   return BufferPrefix.edit_distance(ExampleString);
135673471bf0Spatrick }
135773471bf0Spatrick 
printSubstitutions(const SourceMgr & SM,StringRef Buffer,SMRange Range,FileCheckDiag::MatchType MatchTy,std::vector<FileCheckDiag> * Diags) const135873471bf0Spatrick void Pattern::printSubstitutions(const SourceMgr &SM, StringRef Buffer,
135973471bf0Spatrick                                  SMRange Range,
136073471bf0Spatrick                                  FileCheckDiag::MatchType MatchTy,
136173471bf0Spatrick                                  std::vector<FileCheckDiag> *Diags) const {
136273471bf0Spatrick   // Print what we know about substitutions.
136373471bf0Spatrick   if (!Substitutions.empty()) {
136473471bf0Spatrick     for (const auto &Substitution : Substitutions) {
136573471bf0Spatrick       SmallString<256> Msg;
136673471bf0Spatrick       raw_svector_ostream OS(Msg);
136773471bf0Spatrick 
136873471bf0Spatrick       Expected<std::string> MatchedValue = Substitution->getResult();
136973471bf0Spatrick       // Substitution failures are handled in printNoMatch().
137073471bf0Spatrick       if (!MatchedValue) {
137173471bf0Spatrick         consumeError(MatchedValue.takeError());
137273471bf0Spatrick         continue;
137373471bf0Spatrick       }
137473471bf0Spatrick 
137573471bf0Spatrick       OS << "with \"";
137673471bf0Spatrick       OS.write_escaped(Substitution->getFromString()) << "\" equal to \"";
137773471bf0Spatrick       OS.write_escaped(*MatchedValue) << "\"";
137873471bf0Spatrick 
137973471bf0Spatrick       // We report only the start of the match/search range to suggest we are
138073471bf0Spatrick       // reporting the substitutions as set at the start of the match/search.
138173471bf0Spatrick       // Indicating a non-zero-length range might instead seem to imply that the
138273471bf0Spatrick       // substitution matches or was captured from exactly that range.
138373471bf0Spatrick       if (Diags)
138473471bf0Spatrick         Diags->emplace_back(SM, CheckTy, getLoc(), MatchTy,
138573471bf0Spatrick                             SMRange(Range.Start, Range.Start), OS.str());
138673471bf0Spatrick       else
138773471bf0Spatrick         SM.PrintMessage(Range.Start, SourceMgr::DK_Note, OS.str());
138873471bf0Spatrick     }
138973471bf0Spatrick   }
139073471bf0Spatrick }
139173471bf0Spatrick 
printVariableDefs(const SourceMgr & SM,FileCheckDiag::MatchType MatchTy,std::vector<FileCheckDiag> * Diags) const139273471bf0Spatrick void Pattern::printVariableDefs(const SourceMgr &SM,
139373471bf0Spatrick                                 FileCheckDiag::MatchType MatchTy,
139473471bf0Spatrick                                 std::vector<FileCheckDiag> *Diags) const {
139573471bf0Spatrick   if (VariableDefs.empty() && NumericVariableDefs.empty())
139673471bf0Spatrick     return;
139773471bf0Spatrick   // Build list of variable captures.
139873471bf0Spatrick   struct VarCapture {
139973471bf0Spatrick     StringRef Name;
140073471bf0Spatrick     SMRange Range;
140173471bf0Spatrick   };
140273471bf0Spatrick   SmallVector<VarCapture, 2> VarCaptures;
140373471bf0Spatrick   for (const auto &VariableDef : VariableDefs) {
140473471bf0Spatrick     VarCapture VC;
140573471bf0Spatrick     VC.Name = VariableDef.first;
140673471bf0Spatrick     StringRef Value = Context->GlobalVariableTable[VC.Name];
140773471bf0Spatrick     SMLoc Start = SMLoc::getFromPointer(Value.data());
140873471bf0Spatrick     SMLoc End = SMLoc::getFromPointer(Value.data() + Value.size());
140973471bf0Spatrick     VC.Range = SMRange(Start, End);
141073471bf0Spatrick     VarCaptures.push_back(VC);
141173471bf0Spatrick   }
141273471bf0Spatrick   for (const auto &VariableDef : NumericVariableDefs) {
141373471bf0Spatrick     VarCapture VC;
141473471bf0Spatrick     VC.Name = VariableDef.getKey();
1415*d415bd75Srobert     std::optional<StringRef> StrValue =
141673471bf0Spatrick         VariableDef.getValue().DefinedNumericVariable->getStringValue();
141773471bf0Spatrick     if (!StrValue)
141873471bf0Spatrick       continue;
141973471bf0Spatrick     SMLoc Start = SMLoc::getFromPointer(StrValue->data());
142073471bf0Spatrick     SMLoc End = SMLoc::getFromPointer(StrValue->data() + StrValue->size());
142173471bf0Spatrick     VC.Range = SMRange(Start, End);
142273471bf0Spatrick     VarCaptures.push_back(VC);
142373471bf0Spatrick   }
142473471bf0Spatrick   // Sort variable captures by the order in which they matched the input.
142573471bf0Spatrick   // Ranges shouldn't be overlapping, so we can just compare the start.
142673471bf0Spatrick   llvm::sort(VarCaptures, [](const VarCapture &A, const VarCapture &B) {
1427*d415bd75Srobert     if (&A == &B)
1428*d415bd75Srobert       return false;
142973471bf0Spatrick     assert(A.Range.Start != B.Range.Start &&
143073471bf0Spatrick            "unexpected overlapping variable captures");
143173471bf0Spatrick     return A.Range.Start.getPointer() < B.Range.Start.getPointer();
143273471bf0Spatrick   });
143373471bf0Spatrick   // Create notes for the sorted captures.
143473471bf0Spatrick   for (const VarCapture &VC : VarCaptures) {
143573471bf0Spatrick     SmallString<256> Msg;
143673471bf0Spatrick     raw_svector_ostream OS(Msg);
143773471bf0Spatrick     OS << "captured var \"" << VC.Name << "\"";
143873471bf0Spatrick     if (Diags)
143973471bf0Spatrick       Diags->emplace_back(SM, CheckTy, getLoc(), MatchTy, VC.Range, OS.str());
144073471bf0Spatrick     else
144173471bf0Spatrick       SM.PrintMessage(VC.Range.Start, SourceMgr::DK_Note, OS.str(), VC.Range);
144273471bf0Spatrick   }
144373471bf0Spatrick }
144473471bf0Spatrick 
ProcessMatchResult(FileCheckDiag::MatchType MatchTy,const SourceMgr & SM,SMLoc Loc,Check::FileCheckType CheckTy,StringRef Buffer,size_t Pos,size_t Len,std::vector<FileCheckDiag> * Diags,bool AdjustPrevDiags=false)144573471bf0Spatrick static SMRange ProcessMatchResult(FileCheckDiag::MatchType MatchTy,
144673471bf0Spatrick                                   const SourceMgr &SM, SMLoc Loc,
144773471bf0Spatrick                                   Check::FileCheckType CheckTy,
144873471bf0Spatrick                                   StringRef Buffer, size_t Pos, size_t Len,
144973471bf0Spatrick                                   std::vector<FileCheckDiag> *Diags,
145073471bf0Spatrick                                   bool AdjustPrevDiags = false) {
145173471bf0Spatrick   SMLoc Start = SMLoc::getFromPointer(Buffer.data() + Pos);
145273471bf0Spatrick   SMLoc End = SMLoc::getFromPointer(Buffer.data() + Pos + Len);
145373471bf0Spatrick   SMRange Range(Start, End);
145473471bf0Spatrick   if (Diags) {
145573471bf0Spatrick     if (AdjustPrevDiags) {
145673471bf0Spatrick       SMLoc CheckLoc = Diags->rbegin()->CheckLoc;
145773471bf0Spatrick       for (auto I = Diags->rbegin(), E = Diags->rend();
145873471bf0Spatrick            I != E && I->CheckLoc == CheckLoc; ++I)
145973471bf0Spatrick         I->MatchTy = MatchTy;
146073471bf0Spatrick     } else
146173471bf0Spatrick       Diags->emplace_back(SM, CheckTy, Loc, MatchTy, Range);
146273471bf0Spatrick   }
146373471bf0Spatrick   return Range;
146473471bf0Spatrick }
146573471bf0Spatrick 
printFuzzyMatch(const SourceMgr & SM,StringRef Buffer,std::vector<FileCheckDiag> * Diags) const146673471bf0Spatrick void Pattern::printFuzzyMatch(const SourceMgr &SM, StringRef Buffer,
146773471bf0Spatrick                               std::vector<FileCheckDiag> *Diags) const {
146873471bf0Spatrick   // Attempt to find the closest/best fuzzy match.  Usually an error happens
146973471bf0Spatrick   // because some string in the output didn't exactly match. In these cases, we
147073471bf0Spatrick   // would like to show the user a best guess at what "should have" matched, to
147173471bf0Spatrick   // save them having to actually check the input manually.
147273471bf0Spatrick   size_t NumLinesForward = 0;
147373471bf0Spatrick   size_t Best = StringRef::npos;
147473471bf0Spatrick   double BestQuality = 0;
147573471bf0Spatrick 
147673471bf0Spatrick   // Use an arbitrary 4k limit on how far we will search.
147773471bf0Spatrick   for (size_t i = 0, e = std::min(size_t(4096), Buffer.size()); i != e; ++i) {
147873471bf0Spatrick     if (Buffer[i] == '\n')
147973471bf0Spatrick       ++NumLinesForward;
148073471bf0Spatrick 
148173471bf0Spatrick     // Patterns have leading whitespace stripped, so skip whitespace when
148273471bf0Spatrick     // looking for something which looks like a pattern.
148373471bf0Spatrick     if (Buffer[i] == ' ' || Buffer[i] == '\t')
148473471bf0Spatrick       continue;
148573471bf0Spatrick 
148673471bf0Spatrick     // Compute the "quality" of this match as an arbitrary combination of the
148773471bf0Spatrick     // match distance and the number of lines skipped to get to this match.
148873471bf0Spatrick     unsigned Distance = computeMatchDistance(Buffer.substr(i));
148973471bf0Spatrick     double Quality = Distance + (NumLinesForward / 100.);
149073471bf0Spatrick 
149173471bf0Spatrick     if (Quality < BestQuality || Best == StringRef::npos) {
149273471bf0Spatrick       Best = i;
149373471bf0Spatrick       BestQuality = Quality;
149473471bf0Spatrick     }
149573471bf0Spatrick   }
149673471bf0Spatrick 
149773471bf0Spatrick   // Print the "possible intended match here" line if we found something
149873471bf0Spatrick   // reasonable and not equal to what we showed in the "scanning from here"
149973471bf0Spatrick   // line.
150073471bf0Spatrick   if (Best && Best != StringRef::npos && BestQuality < 50) {
150173471bf0Spatrick     SMRange MatchRange =
150273471bf0Spatrick         ProcessMatchResult(FileCheckDiag::MatchFuzzy, SM, getLoc(),
150373471bf0Spatrick                            getCheckTy(), Buffer, Best, 0, Diags);
150473471bf0Spatrick     SM.PrintMessage(MatchRange.Start, SourceMgr::DK_Note,
150573471bf0Spatrick                     "possible intended match here");
150673471bf0Spatrick 
150773471bf0Spatrick     // FIXME: If we wanted to be really friendly we would show why the match
150873471bf0Spatrick     // failed, as it can be hard to spot simple one character differences.
150973471bf0Spatrick   }
151073471bf0Spatrick }
151173471bf0Spatrick 
151273471bf0Spatrick Expected<StringRef>
getPatternVarValue(StringRef VarName)151373471bf0Spatrick FileCheckPatternContext::getPatternVarValue(StringRef VarName) {
151473471bf0Spatrick   auto VarIter = GlobalVariableTable.find(VarName);
151573471bf0Spatrick   if (VarIter == GlobalVariableTable.end())
151673471bf0Spatrick     return make_error<UndefVarError>(VarName);
151773471bf0Spatrick 
151873471bf0Spatrick   return VarIter->second;
151973471bf0Spatrick }
152073471bf0Spatrick 
152173471bf0Spatrick template <class... Types>
makeNumericVariable(Types...args)152273471bf0Spatrick NumericVariable *FileCheckPatternContext::makeNumericVariable(Types... args) {
152373471bf0Spatrick   NumericVariables.push_back(std::make_unique<NumericVariable>(args...));
152473471bf0Spatrick   return NumericVariables.back().get();
152573471bf0Spatrick }
152673471bf0Spatrick 
152773471bf0Spatrick Substitution *
makeStringSubstitution(StringRef VarName,size_t InsertIdx)152873471bf0Spatrick FileCheckPatternContext::makeStringSubstitution(StringRef VarName,
152973471bf0Spatrick                                                 size_t InsertIdx) {
153073471bf0Spatrick   Substitutions.push_back(
153173471bf0Spatrick       std::make_unique<StringSubstitution>(this, VarName, InsertIdx));
153273471bf0Spatrick   return Substitutions.back().get();
153373471bf0Spatrick }
153473471bf0Spatrick 
makeNumericSubstitution(StringRef ExpressionStr,std::unique_ptr<Expression> Expression,size_t InsertIdx)153573471bf0Spatrick Substitution *FileCheckPatternContext::makeNumericSubstitution(
153673471bf0Spatrick     StringRef ExpressionStr, std::unique_ptr<Expression> Expression,
153773471bf0Spatrick     size_t InsertIdx) {
153873471bf0Spatrick   Substitutions.push_back(std::make_unique<NumericSubstitution>(
153973471bf0Spatrick       this, ExpressionStr, std::move(Expression), InsertIdx));
154073471bf0Spatrick   return Substitutions.back().get();
154173471bf0Spatrick }
154273471bf0Spatrick 
FindRegexVarEnd(StringRef Str,SourceMgr & SM)154373471bf0Spatrick size_t Pattern::FindRegexVarEnd(StringRef Str, SourceMgr &SM) {
154473471bf0Spatrick   // Offset keeps track of the current offset within the input Str
154573471bf0Spatrick   size_t Offset = 0;
154673471bf0Spatrick   // [...] Nesting depth
154773471bf0Spatrick   size_t BracketDepth = 0;
154873471bf0Spatrick 
154973471bf0Spatrick   while (!Str.empty()) {
155073471bf0Spatrick     if (Str.startswith("]]") && BracketDepth == 0)
155173471bf0Spatrick       return Offset;
155273471bf0Spatrick     if (Str[0] == '\\') {
155373471bf0Spatrick       // Backslash escapes the next char within regexes, so skip them both.
155473471bf0Spatrick       Str = Str.substr(2);
155573471bf0Spatrick       Offset += 2;
155673471bf0Spatrick     } else {
155773471bf0Spatrick       switch (Str[0]) {
155873471bf0Spatrick       default:
155973471bf0Spatrick         break;
156073471bf0Spatrick       case '[':
156173471bf0Spatrick         BracketDepth++;
156273471bf0Spatrick         break;
156373471bf0Spatrick       case ']':
156473471bf0Spatrick         if (BracketDepth == 0) {
156573471bf0Spatrick           SM.PrintMessage(SMLoc::getFromPointer(Str.data()),
156673471bf0Spatrick                           SourceMgr::DK_Error,
156773471bf0Spatrick                           "missing closing \"]\" for regex variable");
156873471bf0Spatrick           exit(1);
156973471bf0Spatrick         }
157073471bf0Spatrick         BracketDepth--;
157173471bf0Spatrick         break;
157273471bf0Spatrick       }
157373471bf0Spatrick       Str = Str.substr(1);
157473471bf0Spatrick       Offset++;
157573471bf0Spatrick     }
157673471bf0Spatrick   }
157773471bf0Spatrick 
157873471bf0Spatrick   return StringRef::npos;
157973471bf0Spatrick }
158073471bf0Spatrick 
CanonicalizeFile(MemoryBuffer & MB,SmallVectorImpl<char> & OutputBuffer)158173471bf0Spatrick StringRef FileCheck::CanonicalizeFile(MemoryBuffer &MB,
158273471bf0Spatrick                                       SmallVectorImpl<char> &OutputBuffer) {
158373471bf0Spatrick   OutputBuffer.reserve(MB.getBufferSize());
158473471bf0Spatrick 
158573471bf0Spatrick   for (const char *Ptr = MB.getBufferStart(), *End = MB.getBufferEnd();
158673471bf0Spatrick        Ptr != End; ++Ptr) {
158773471bf0Spatrick     // Eliminate trailing dosish \r.
158873471bf0Spatrick     if (Ptr <= End - 2 && Ptr[0] == '\r' && Ptr[1] == '\n') {
158973471bf0Spatrick       continue;
159073471bf0Spatrick     }
159173471bf0Spatrick 
159273471bf0Spatrick     // If current char is not a horizontal whitespace or if horizontal
159373471bf0Spatrick     // whitespace canonicalization is disabled, dump it to output as is.
159473471bf0Spatrick     if (Req.NoCanonicalizeWhiteSpace || (*Ptr != ' ' && *Ptr != '\t')) {
159573471bf0Spatrick       OutputBuffer.push_back(*Ptr);
159673471bf0Spatrick       continue;
159773471bf0Spatrick     }
159873471bf0Spatrick 
159973471bf0Spatrick     // Otherwise, add one space and advance over neighboring space.
160073471bf0Spatrick     OutputBuffer.push_back(' ');
160173471bf0Spatrick     while (Ptr + 1 != End && (Ptr[1] == ' ' || Ptr[1] == '\t'))
160273471bf0Spatrick       ++Ptr;
160373471bf0Spatrick   }
160473471bf0Spatrick 
160573471bf0Spatrick   // Add a null byte and then return all but that byte.
160673471bf0Spatrick   OutputBuffer.push_back('\0');
160773471bf0Spatrick   return StringRef(OutputBuffer.data(), OutputBuffer.size() - 1);
160873471bf0Spatrick }
160973471bf0Spatrick 
FileCheckDiag(const SourceMgr & SM,const Check::FileCheckType & CheckTy,SMLoc CheckLoc,MatchType MatchTy,SMRange InputRange,StringRef Note)161073471bf0Spatrick FileCheckDiag::FileCheckDiag(const SourceMgr &SM,
161173471bf0Spatrick                              const Check::FileCheckType &CheckTy,
161273471bf0Spatrick                              SMLoc CheckLoc, MatchType MatchTy,
161373471bf0Spatrick                              SMRange InputRange, StringRef Note)
161473471bf0Spatrick     : CheckTy(CheckTy), CheckLoc(CheckLoc), MatchTy(MatchTy), Note(Note) {
161573471bf0Spatrick   auto Start = SM.getLineAndColumn(InputRange.Start);
161673471bf0Spatrick   auto End = SM.getLineAndColumn(InputRange.End);
161773471bf0Spatrick   InputStartLine = Start.first;
161873471bf0Spatrick   InputStartCol = Start.second;
161973471bf0Spatrick   InputEndLine = End.first;
162073471bf0Spatrick   InputEndCol = End.second;
162173471bf0Spatrick }
162273471bf0Spatrick 
IsPartOfWord(char c)162373471bf0Spatrick static bool IsPartOfWord(char c) {
162473471bf0Spatrick   return (isAlnum(c) || c == '-' || c == '_');
162573471bf0Spatrick }
162673471bf0Spatrick 
setCount(int C)162773471bf0Spatrick Check::FileCheckType &Check::FileCheckType::setCount(int C) {
162873471bf0Spatrick   assert(Count > 0 && "zero and negative counts are not supported");
162973471bf0Spatrick   assert((C == 1 || Kind == CheckPlain) &&
163073471bf0Spatrick          "count supported only for plain CHECK directives");
163173471bf0Spatrick   Count = C;
163273471bf0Spatrick   return *this;
163373471bf0Spatrick }
163473471bf0Spatrick 
getModifiersDescription() const163573471bf0Spatrick std::string Check::FileCheckType::getModifiersDescription() const {
163673471bf0Spatrick   if (Modifiers.none())
163773471bf0Spatrick     return "";
163873471bf0Spatrick   std::string Ret;
163973471bf0Spatrick   raw_string_ostream OS(Ret);
164073471bf0Spatrick   OS << '{';
164173471bf0Spatrick   if (isLiteralMatch())
164273471bf0Spatrick     OS << "LITERAL";
164373471bf0Spatrick   OS << '}';
164473471bf0Spatrick   return OS.str();
164573471bf0Spatrick }
164673471bf0Spatrick 
getDescription(StringRef Prefix) const164773471bf0Spatrick std::string Check::FileCheckType::getDescription(StringRef Prefix) const {
164873471bf0Spatrick   // Append directive modifiers.
164973471bf0Spatrick   auto WithModifiers = [this, Prefix](StringRef Str) -> std::string {
165073471bf0Spatrick     return (Prefix + Str + getModifiersDescription()).str();
165173471bf0Spatrick   };
165273471bf0Spatrick 
165373471bf0Spatrick   switch (Kind) {
165473471bf0Spatrick   case Check::CheckNone:
165573471bf0Spatrick     return "invalid";
1656*d415bd75Srobert   case Check::CheckMisspelled:
1657*d415bd75Srobert     return "misspelled";
165873471bf0Spatrick   case Check::CheckPlain:
165973471bf0Spatrick     if (Count > 1)
166073471bf0Spatrick       return WithModifiers("-COUNT");
166173471bf0Spatrick     return WithModifiers("");
166273471bf0Spatrick   case Check::CheckNext:
166373471bf0Spatrick     return WithModifiers("-NEXT");
166473471bf0Spatrick   case Check::CheckSame:
166573471bf0Spatrick     return WithModifiers("-SAME");
166673471bf0Spatrick   case Check::CheckNot:
166773471bf0Spatrick     return WithModifiers("-NOT");
166873471bf0Spatrick   case Check::CheckDAG:
166973471bf0Spatrick     return WithModifiers("-DAG");
167073471bf0Spatrick   case Check::CheckLabel:
167173471bf0Spatrick     return WithModifiers("-LABEL");
167273471bf0Spatrick   case Check::CheckEmpty:
167373471bf0Spatrick     return WithModifiers("-EMPTY");
167473471bf0Spatrick   case Check::CheckComment:
167573471bf0Spatrick     return std::string(Prefix);
167673471bf0Spatrick   case Check::CheckEOF:
167773471bf0Spatrick     return "implicit EOF";
167873471bf0Spatrick   case Check::CheckBadNot:
167973471bf0Spatrick     return "bad NOT";
168073471bf0Spatrick   case Check::CheckBadCount:
168173471bf0Spatrick     return "bad COUNT";
168273471bf0Spatrick   }
168373471bf0Spatrick   llvm_unreachable("unknown FileCheckType");
168473471bf0Spatrick }
168573471bf0Spatrick 
168673471bf0Spatrick static std::pair<Check::FileCheckType, StringRef>
FindCheckType(const FileCheckRequest & Req,StringRef Buffer,StringRef Prefix,bool & Misspelled)1687*d415bd75Srobert FindCheckType(const FileCheckRequest &Req, StringRef Buffer, StringRef Prefix,
1688*d415bd75Srobert               bool &Misspelled) {
168973471bf0Spatrick   if (Buffer.size() <= Prefix.size())
169073471bf0Spatrick     return {Check::CheckNone, StringRef()};
169173471bf0Spatrick 
169273471bf0Spatrick   StringRef Rest = Buffer.drop_front(Prefix.size());
169373471bf0Spatrick   // Check for comment.
169473471bf0Spatrick   if (llvm::is_contained(Req.CommentPrefixes, Prefix)) {
169573471bf0Spatrick     if (Rest.consume_front(":"))
169673471bf0Spatrick       return {Check::CheckComment, Rest};
169773471bf0Spatrick     // Ignore a comment prefix if it has a suffix like "-NOT".
169873471bf0Spatrick     return {Check::CheckNone, StringRef()};
169973471bf0Spatrick   }
170073471bf0Spatrick 
170173471bf0Spatrick   auto ConsumeModifiers = [&](Check::FileCheckType Ret)
170273471bf0Spatrick       -> std::pair<Check::FileCheckType, StringRef> {
170373471bf0Spatrick     if (Rest.consume_front(":"))
170473471bf0Spatrick       return {Ret, Rest};
170573471bf0Spatrick     if (!Rest.consume_front("{"))
170673471bf0Spatrick       return {Check::CheckNone, StringRef()};
170773471bf0Spatrick 
170873471bf0Spatrick     // Parse the modifiers, speparated by commas.
170973471bf0Spatrick     do {
171073471bf0Spatrick       // Allow whitespace in modifiers list.
171173471bf0Spatrick       Rest = Rest.ltrim();
171273471bf0Spatrick       if (Rest.consume_front("LITERAL"))
171373471bf0Spatrick         Ret.setLiteralMatch();
171473471bf0Spatrick       else
171573471bf0Spatrick         return {Check::CheckNone, Rest};
171673471bf0Spatrick       // Allow whitespace in modifiers list.
171773471bf0Spatrick       Rest = Rest.ltrim();
171873471bf0Spatrick     } while (Rest.consume_front(","));
171973471bf0Spatrick     if (!Rest.consume_front("}:"))
172073471bf0Spatrick       return {Check::CheckNone, Rest};
172173471bf0Spatrick     return {Ret, Rest};
172273471bf0Spatrick   };
172373471bf0Spatrick 
172473471bf0Spatrick   // Verify that the prefix is followed by directive modifiers or a colon.
172573471bf0Spatrick   if (Rest.consume_front(":"))
172673471bf0Spatrick     return {Check::CheckPlain, Rest};
172773471bf0Spatrick   if (Rest.front() == '{')
172873471bf0Spatrick     return ConsumeModifiers(Check::CheckPlain);
172973471bf0Spatrick 
1730*d415bd75Srobert   if (Rest.consume_front("_"))
1731*d415bd75Srobert     Misspelled = true;
1732*d415bd75Srobert   else if (!Rest.consume_front("-"))
173373471bf0Spatrick     return {Check::CheckNone, StringRef()};
173473471bf0Spatrick 
173573471bf0Spatrick   if (Rest.consume_front("COUNT-")) {
173673471bf0Spatrick     int64_t Count;
173773471bf0Spatrick     if (Rest.consumeInteger(10, Count))
173873471bf0Spatrick       // Error happened in parsing integer.
173973471bf0Spatrick       return {Check::CheckBadCount, Rest};
174073471bf0Spatrick     if (Count <= 0 || Count > INT32_MAX)
174173471bf0Spatrick       return {Check::CheckBadCount, Rest};
174273471bf0Spatrick     if (Rest.front() != ':' && Rest.front() != '{')
174373471bf0Spatrick       return {Check::CheckBadCount, Rest};
174473471bf0Spatrick     return ConsumeModifiers(
174573471bf0Spatrick         Check::FileCheckType(Check::CheckPlain).setCount(Count));
174673471bf0Spatrick   }
174773471bf0Spatrick 
174873471bf0Spatrick   // You can't combine -NOT with another suffix.
174973471bf0Spatrick   if (Rest.startswith("DAG-NOT:") || Rest.startswith("NOT-DAG:") ||
175073471bf0Spatrick       Rest.startswith("NEXT-NOT:") || Rest.startswith("NOT-NEXT:") ||
175173471bf0Spatrick       Rest.startswith("SAME-NOT:") || Rest.startswith("NOT-SAME:") ||
175273471bf0Spatrick       Rest.startswith("EMPTY-NOT:") || Rest.startswith("NOT-EMPTY:"))
175373471bf0Spatrick     return {Check::CheckBadNot, Rest};
175473471bf0Spatrick 
175573471bf0Spatrick   if (Rest.consume_front("NEXT"))
175673471bf0Spatrick     return ConsumeModifiers(Check::CheckNext);
175773471bf0Spatrick 
175873471bf0Spatrick   if (Rest.consume_front("SAME"))
175973471bf0Spatrick     return ConsumeModifiers(Check::CheckSame);
176073471bf0Spatrick 
176173471bf0Spatrick   if (Rest.consume_front("NOT"))
176273471bf0Spatrick     return ConsumeModifiers(Check::CheckNot);
176373471bf0Spatrick 
176473471bf0Spatrick   if (Rest.consume_front("DAG"))
176573471bf0Spatrick     return ConsumeModifiers(Check::CheckDAG);
176673471bf0Spatrick 
176773471bf0Spatrick   if (Rest.consume_front("LABEL"))
176873471bf0Spatrick     return ConsumeModifiers(Check::CheckLabel);
176973471bf0Spatrick 
177073471bf0Spatrick   if (Rest.consume_front("EMPTY"))
177173471bf0Spatrick     return ConsumeModifiers(Check::CheckEmpty);
177273471bf0Spatrick 
177373471bf0Spatrick   return {Check::CheckNone, Rest};
177473471bf0Spatrick }
177573471bf0Spatrick 
1776*d415bd75Srobert static std::pair<Check::FileCheckType, StringRef>
FindCheckType(const FileCheckRequest & Req,StringRef Buffer,StringRef Prefix)1777*d415bd75Srobert FindCheckType(const FileCheckRequest &Req, StringRef Buffer, StringRef Prefix) {
1778*d415bd75Srobert   bool Misspelled = false;
1779*d415bd75Srobert   auto Res = FindCheckType(Req, Buffer, Prefix, Misspelled);
1780*d415bd75Srobert   if (Res.first != Check::CheckNone && Misspelled)
1781*d415bd75Srobert     return {Check::CheckMisspelled, Res.second};
1782*d415bd75Srobert   return Res;
1783*d415bd75Srobert }
1784*d415bd75Srobert 
178573471bf0Spatrick // From the given position, find the next character after the word.
SkipWord(StringRef Str,size_t Loc)178673471bf0Spatrick static size_t SkipWord(StringRef Str, size_t Loc) {
178773471bf0Spatrick   while (Loc < Str.size() && IsPartOfWord(Str[Loc]))
178873471bf0Spatrick     ++Loc;
178973471bf0Spatrick   return Loc;
179073471bf0Spatrick }
179173471bf0Spatrick 
179273471bf0Spatrick /// Searches the buffer for the first prefix in the prefix regular expression.
179373471bf0Spatrick ///
179473471bf0Spatrick /// This searches the buffer using the provided regular expression, however it
179573471bf0Spatrick /// enforces constraints beyond that:
179673471bf0Spatrick /// 1) The found prefix must not be a suffix of something that looks like
179773471bf0Spatrick ///    a valid prefix.
179873471bf0Spatrick /// 2) The found prefix must be followed by a valid check type suffix using \c
179973471bf0Spatrick ///    FindCheckType above.
180073471bf0Spatrick ///
180173471bf0Spatrick /// \returns a pair of StringRefs into the Buffer, which combines:
180273471bf0Spatrick ///   - the first match of the regular expression to satisfy these two is
180373471bf0Spatrick ///   returned,
180473471bf0Spatrick ///     otherwise an empty StringRef is returned to indicate failure.
180573471bf0Spatrick ///   - buffer rewound to the location right after parsed suffix, for parsing
180673471bf0Spatrick ///     to continue from
180773471bf0Spatrick ///
180873471bf0Spatrick /// If this routine returns a valid prefix, it will also shrink \p Buffer to
180973471bf0Spatrick /// start at the beginning of the returned prefix, increment \p LineNumber for
181073471bf0Spatrick /// each new line consumed from \p Buffer, and set \p CheckTy to the type of
181173471bf0Spatrick /// check found by examining the suffix.
181273471bf0Spatrick ///
181373471bf0Spatrick /// If no valid prefix is found, the state of Buffer, LineNumber, and CheckTy
181473471bf0Spatrick /// is unspecified.
181573471bf0Spatrick static std::pair<StringRef, StringRef>
FindFirstMatchingPrefix(const FileCheckRequest & Req,Regex & PrefixRE,StringRef & Buffer,unsigned & LineNumber,Check::FileCheckType & CheckTy)181673471bf0Spatrick FindFirstMatchingPrefix(const FileCheckRequest &Req, Regex &PrefixRE,
181773471bf0Spatrick                         StringRef &Buffer, unsigned &LineNumber,
181873471bf0Spatrick                         Check::FileCheckType &CheckTy) {
181973471bf0Spatrick   SmallVector<StringRef, 2> Matches;
182073471bf0Spatrick 
182173471bf0Spatrick   while (!Buffer.empty()) {
182273471bf0Spatrick     // Find the first (longest) match using the RE.
182373471bf0Spatrick     if (!PrefixRE.match(Buffer, &Matches))
182473471bf0Spatrick       // No match at all, bail.
182573471bf0Spatrick       return {StringRef(), StringRef()};
182673471bf0Spatrick 
182773471bf0Spatrick     StringRef Prefix = Matches[0];
182873471bf0Spatrick     Matches.clear();
182973471bf0Spatrick 
183073471bf0Spatrick     assert(Prefix.data() >= Buffer.data() &&
183173471bf0Spatrick            Prefix.data() < Buffer.data() + Buffer.size() &&
183273471bf0Spatrick            "Prefix doesn't start inside of buffer!");
183373471bf0Spatrick     size_t Loc = Prefix.data() - Buffer.data();
183473471bf0Spatrick     StringRef Skipped = Buffer.substr(0, Loc);
183573471bf0Spatrick     Buffer = Buffer.drop_front(Loc);
183673471bf0Spatrick     LineNumber += Skipped.count('\n');
183773471bf0Spatrick 
183873471bf0Spatrick     // Check that the matched prefix isn't a suffix of some other check-like
183973471bf0Spatrick     // word.
184073471bf0Spatrick     // FIXME: This is a very ad-hoc check. it would be better handled in some
184173471bf0Spatrick     // other way. Among other things it seems hard to distinguish between
184273471bf0Spatrick     // intentional and unintentional uses of this feature.
184373471bf0Spatrick     if (Skipped.empty() || !IsPartOfWord(Skipped.back())) {
184473471bf0Spatrick       // Now extract the type.
184573471bf0Spatrick       StringRef AfterSuffix;
184673471bf0Spatrick       std::tie(CheckTy, AfterSuffix) = FindCheckType(Req, Buffer, Prefix);
184773471bf0Spatrick 
184873471bf0Spatrick       // If we've found a valid check type for this prefix, we're done.
184973471bf0Spatrick       if (CheckTy != Check::CheckNone)
185073471bf0Spatrick         return {Prefix, AfterSuffix};
185173471bf0Spatrick     }
185273471bf0Spatrick 
185373471bf0Spatrick     // If we didn't successfully find a prefix, we need to skip this invalid
185473471bf0Spatrick     // prefix and continue scanning. We directly skip the prefix that was
185573471bf0Spatrick     // matched and any additional parts of that check-like word.
185673471bf0Spatrick     Buffer = Buffer.drop_front(SkipWord(Buffer, Prefix.size()));
185773471bf0Spatrick   }
185873471bf0Spatrick 
185973471bf0Spatrick   // We ran out of buffer while skipping partial matches so give up.
186073471bf0Spatrick   return {StringRef(), StringRef()};
186173471bf0Spatrick }
186273471bf0Spatrick 
createLineVariable()186373471bf0Spatrick void FileCheckPatternContext::createLineVariable() {
186473471bf0Spatrick   assert(!LineVariable && "@LINE pseudo numeric variable already created");
186573471bf0Spatrick   StringRef LineName = "@LINE";
186673471bf0Spatrick   LineVariable = makeNumericVariable(
186773471bf0Spatrick       LineName, ExpressionFormat(ExpressionFormat::Kind::Unsigned));
186873471bf0Spatrick   GlobalNumericVariableTable[LineName] = LineVariable;
186973471bf0Spatrick }
187073471bf0Spatrick 
FileCheck(FileCheckRequest Req)187173471bf0Spatrick FileCheck::FileCheck(FileCheckRequest Req)
187273471bf0Spatrick     : Req(Req), PatternContext(std::make_unique<FileCheckPatternContext>()),
187373471bf0Spatrick       CheckStrings(std::make_unique<std::vector<FileCheckString>>()) {}
187473471bf0Spatrick 
187573471bf0Spatrick FileCheck::~FileCheck() = default;
187673471bf0Spatrick 
readCheckFile(SourceMgr & SM,StringRef Buffer,Regex & PrefixRE,std::pair<unsigned,unsigned> * ImpPatBufferIDRange)187773471bf0Spatrick bool FileCheck::readCheckFile(
187873471bf0Spatrick     SourceMgr &SM, StringRef Buffer, Regex &PrefixRE,
187973471bf0Spatrick     std::pair<unsigned, unsigned> *ImpPatBufferIDRange) {
188073471bf0Spatrick   if (ImpPatBufferIDRange)
188173471bf0Spatrick     ImpPatBufferIDRange->first = ImpPatBufferIDRange->second = 0;
188273471bf0Spatrick 
188373471bf0Spatrick   Error DefineError =
188473471bf0Spatrick       PatternContext->defineCmdlineVariables(Req.GlobalDefines, SM);
188573471bf0Spatrick   if (DefineError) {
188673471bf0Spatrick     logAllUnhandledErrors(std::move(DefineError), errs());
188773471bf0Spatrick     return true;
188873471bf0Spatrick   }
188973471bf0Spatrick 
189073471bf0Spatrick   PatternContext->createLineVariable();
189173471bf0Spatrick 
189273471bf0Spatrick   std::vector<Pattern> ImplicitNegativeChecks;
189373471bf0Spatrick   for (StringRef PatternString : Req.ImplicitCheckNot) {
189473471bf0Spatrick     // Create a buffer with fake command line content in order to display the
189573471bf0Spatrick     // command line option responsible for the specific implicit CHECK-NOT.
189673471bf0Spatrick     std::string Prefix = "-implicit-check-not='";
189773471bf0Spatrick     std::string Suffix = "'";
189873471bf0Spatrick     std::unique_ptr<MemoryBuffer> CmdLine = MemoryBuffer::getMemBufferCopy(
189973471bf0Spatrick         (Prefix + PatternString + Suffix).str(), "command line");
190073471bf0Spatrick 
190173471bf0Spatrick     StringRef PatternInBuffer =
190273471bf0Spatrick         CmdLine->getBuffer().substr(Prefix.size(), PatternString.size());
190373471bf0Spatrick     unsigned BufferID = SM.AddNewSourceBuffer(std::move(CmdLine), SMLoc());
190473471bf0Spatrick     if (ImpPatBufferIDRange) {
190573471bf0Spatrick       if (ImpPatBufferIDRange->first == ImpPatBufferIDRange->second) {
190673471bf0Spatrick         ImpPatBufferIDRange->first = BufferID;
190773471bf0Spatrick         ImpPatBufferIDRange->second = BufferID + 1;
190873471bf0Spatrick       } else {
190973471bf0Spatrick         assert(BufferID == ImpPatBufferIDRange->second &&
191073471bf0Spatrick                "expected consecutive source buffer IDs");
191173471bf0Spatrick         ++ImpPatBufferIDRange->second;
191273471bf0Spatrick       }
191373471bf0Spatrick     }
191473471bf0Spatrick 
191573471bf0Spatrick     ImplicitNegativeChecks.push_back(
191673471bf0Spatrick         Pattern(Check::CheckNot, PatternContext.get()));
191773471bf0Spatrick     ImplicitNegativeChecks.back().parsePattern(PatternInBuffer,
191873471bf0Spatrick                                                "IMPLICIT-CHECK", SM, Req);
191973471bf0Spatrick   }
192073471bf0Spatrick 
192173471bf0Spatrick   std::vector<Pattern> DagNotMatches = ImplicitNegativeChecks;
192273471bf0Spatrick 
192373471bf0Spatrick   // LineNumber keeps track of the line on which CheckPrefix instances are
192473471bf0Spatrick   // found.
192573471bf0Spatrick   unsigned LineNumber = 1;
192673471bf0Spatrick 
192773471bf0Spatrick   std::set<StringRef> PrefixesNotFound(Req.CheckPrefixes.begin(),
192873471bf0Spatrick                                        Req.CheckPrefixes.end());
192973471bf0Spatrick   const size_t DistinctPrefixes = PrefixesNotFound.size();
193073471bf0Spatrick   while (true) {
193173471bf0Spatrick     Check::FileCheckType CheckTy;
193273471bf0Spatrick 
193373471bf0Spatrick     // See if a prefix occurs in the memory buffer.
193473471bf0Spatrick     StringRef UsedPrefix;
193573471bf0Spatrick     StringRef AfterSuffix;
193673471bf0Spatrick     std::tie(UsedPrefix, AfterSuffix) =
193773471bf0Spatrick         FindFirstMatchingPrefix(Req, PrefixRE, Buffer, LineNumber, CheckTy);
193873471bf0Spatrick     if (UsedPrefix.empty())
193973471bf0Spatrick       break;
194073471bf0Spatrick     if (CheckTy != Check::CheckComment)
194173471bf0Spatrick       PrefixesNotFound.erase(UsedPrefix);
194273471bf0Spatrick 
194373471bf0Spatrick     assert(UsedPrefix.data() == Buffer.data() &&
194473471bf0Spatrick            "Failed to move Buffer's start forward, or pointed prefix outside "
194573471bf0Spatrick            "of the buffer!");
194673471bf0Spatrick     assert(AfterSuffix.data() >= Buffer.data() &&
194773471bf0Spatrick            AfterSuffix.data() < Buffer.data() + Buffer.size() &&
194873471bf0Spatrick            "Parsing after suffix doesn't start inside of buffer!");
194973471bf0Spatrick 
195073471bf0Spatrick     // Location to use for error messages.
195173471bf0Spatrick     const char *UsedPrefixStart = UsedPrefix.data();
195273471bf0Spatrick 
195373471bf0Spatrick     // Skip the buffer to the end of parsed suffix (or just prefix, if no good
195473471bf0Spatrick     // suffix was processed).
195573471bf0Spatrick     Buffer = AfterSuffix.empty() ? Buffer.drop_front(UsedPrefix.size())
195673471bf0Spatrick                                  : AfterSuffix;
195773471bf0Spatrick 
1958*d415bd75Srobert     // Complain about misspelled directives.
1959*d415bd75Srobert     if (CheckTy == Check::CheckMisspelled) {
1960*d415bd75Srobert       StringRef UsedDirective(UsedPrefix.data(),
1961*d415bd75Srobert                               AfterSuffix.data() - UsedPrefix.data());
1962*d415bd75Srobert       SM.PrintMessage(SMLoc::getFromPointer(UsedDirective.data()),
1963*d415bd75Srobert                       SourceMgr::DK_Error,
1964*d415bd75Srobert                       "misspelled directive '" + UsedDirective + "'");
1965*d415bd75Srobert       return true;
1966*d415bd75Srobert     }
1967*d415bd75Srobert 
196873471bf0Spatrick     // Complain about useful-looking but unsupported suffixes.
196973471bf0Spatrick     if (CheckTy == Check::CheckBadNot) {
197073471bf0Spatrick       SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Error,
197173471bf0Spatrick                       "unsupported -NOT combo on prefix '" + UsedPrefix + "'");
197273471bf0Spatrick       return true;
197373471bf0Spatrick     }
197473471bf0Spatrick 
197573471bf0Spatrick     // Complain about invalid count specification.
197673471bf0Spatrick     if (CheckTy == Check::CheckBadCount) {
197773471bf0Spatrick       SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Error,
197873471bf0Spatrick                       "invalid count in -COUNT specification on prefix '" +
197973471bf0Spatrick                           UsedPrefix + "'");
198073471bf0Spatrick       return true;
198173471bf0Spatrick     }
198273471bf0Spatrick 
198373471bf0Spatrick     // Okay, we found the prefix, yay. Remember the rest of the line, but ignore
198473471bf0Spatrick     // leading whitespace.
198573471bf0Spatrick     if (!(Req.NoCanonicalizeWhiteSpace && Req.MatchFullLines))
198673471bf0Spatrick       Buffer = Buffer.substr(Buffer.find_first_not_of(" \t"));
198773471bf0Spatrick 
198873471bf0Spatrick     // Scan ahead to the end of line.
198973471bf0Spatrick     size_t EOL = Buffer.find_first_of("\n\r");
199073471bf0Spatrick 
199173471bf0Spatrick     // Remember the location of the start of the pattern, for diagnostics.
199273471bf0Spatrick     SMLoc PatternLoc = SMLoc::getFromPointer(Buffer.data());
199373471bf0Spatrick 
199473471bf0Spatrick     // Extract the pattern from the buffer.
199573471bf0Spatrick     StringRef PatternBuffer = Buffer.substr(0, EOL);
199673471bf0Spatrick     Buffer = Buffer.substr(EOL);
199773471bf0Spatrick 
199873471bf0Spatrick     // If this is a comment, we're done.
199973471bf0Spatrick     if (CheckTy == Check::CheckComment)
200073471bf0Spatrick       continue;
200173471bf0Spatrick 
200273471bf0Spatrick     // Parse the pattern.
200373471bf0Spatrick     Pattern P(CheckTy, PatternContext.get(), LineNumber);
200473471bf0Spatrick     if (P.parsePattern(PatternBuffer, UsedPrefix, SM, Req))
200573471bf0Spatrick       return true;
200673471bf0Spatrick 
200773471bf0Spatrick     // Verify that CHECK-LABEL lines do not define or use variables
200873471bf0Spatrick     if ((CheckTy == Check::CheckLabel) && P.hasVariable()) {
200973471bf0Spatrick       SM.PrintMessage(
201073471bf0Spatrick           SMLoc::getFromPointer(UsedPrefixStart), SourceMgr::DK_Error,
201173471bf0Spatrick           "found '" + UsedPrefix + "-LABEL:'"
201273471bf0Spatrick                                    " with variable definition or use");
201373471bf0Spatrick       return true;
201473471bf0Spatrick     }
201573471bf0Spatrick 
201673471bf0Spatrick     // Verify that CHECK-NEXT/SAME/EMPTY lines have at least one CHECK line before them.
201773471bf0Spatrick     if ((CheckTy == Check::CheckNext || CheckTy == Check::CheckSame ||
201873471bf0Spatrick          CheckTy == Check::CheckEmpty) &&
201973471bf0Spatrick         CheckStrings->empty()) {
202073471bf0Spatrick       StringRef Type = CheckTy == Check::CheckNext
202173471bf0Spatrick                            ? "NEXT"
202273471bf0Spatrick                            : CheckTy == Check::CheckEmpty ? "EMPTY" : "SAME";
202373471bf0Spatrick       SM.PrintMessage(SMLoc::getFromPointer(UsedPrefixStart),
202473471bf0Spatrick                       SourceMgr::DK_Error,
202573471bf0Spatrick                       "found '" + UsedPrefix + "-" + Type +
202673471bf0Spatrick                           "' without previous '" + UsedPrefix + ": line");
202773471bf0Spatrick       return true;
202873471bf0Spatrick     }
202973471bf0Spatrick 
203073471bf0Spatrick     // Handle CHECK-DAG/-NOT.
203173471bf0Spatrick     if (CheckTy == Check::CheckDAG || CheckTy == Check::CheckNot) {
203273471bf0Spatrick       DagNotMatches.push_back(P);
203373471bf0Spatrick       continue;
203473471bf0Spatrick     }
203573471bf0Spatrick 
203673471bf0Spatrick     // Okay, add the string we captured to the output vector and move on.
203773471bf0Spatrick     CheckStrings->emplace_back(P, UsedPrefix, PatternLoc);
203873471bf0Spatrick     std::swap(DagNotMatches, CheckStrings->back().DagNotStrings);
203973471bf0Spatrick     DagNotMatches = ImplicitNegativeChecks;
204073471bf0Spatrick   }
204173471bf0Spatrick 
204273471bf0Spatrick   // When there are no used prefixes we report an error except in the case that
204373471bf0Spatrick   // no prefix is specified explicitly but -implicit-check-not is specified.
204473471bf0Spatrick   const bool NoPrefixesFound = PrefixesNotFound.size() == DistinctPrefixes;
204573471bf0Spatrick   const bool SomePrefixesUnexpectedlyNotUsed =
204673471bf0Spatrick       !Req.AllowUnusedPrefixes && !PrefixesNotFound.empty();
204773471bf0Spatrick   if ((NoPrefixesFound || SomePrefixesUnexpectedlyNotUsed) &&
204873471bf0Spatrick       (ImplicitNegativeChecks.empty() || !Req.IsDefaultCheckPrefix)) {
204973471bf0Spatrick     errs() << "error: no check strings found with prefix"
205073471bf0Spatrick            << (PrefixesNotFound.size() > 1 ? "es " : " ");
205173471bf0Spatrick     bool First = true;
205273471bf0Spatrick     for (StringRef MissingPrefix : PrefixesNotFound) {
205373471bf0Spatrick       if (!First)
205473471bf0Spatrick         errs() << ", ";
205573471bf0Spatrick       errs() << "\'" << MissingPrefix << ":'";
205673471bf0Spatrick       First = false;
205773471bf0Spatrick     }
205873471bf0Spatrick     errs() << '\n';
205973471bf0Spatrick     return true;
206073471bf0Spatrick   }
206173471bf0Spatrick 
206273471bf0Spatrick   // Add an EOF pattern for any trailing --implicit-check-not/CHECK-DAG/-NOTs,
206373471bf0Spatrick   // and use the first prefix as a filler for the error message.
206473471bf0Spatrick   if (!DagNotMatches.empty()) {
206573471bf0Spatrick     CheckStrings->emplace_back(
206673471bf0Spatrick         Pattern(Check::CheckEOF, PatternContext.get(), LineNumber + 1),
206773471bf0Spatrick         *Req.CheckPrefixes.begin(), SMLoc::getFromPointer(Buffer.data()));
206873471bf0Spatrick     std::swap(DagNotMatches, CheckStrings->back().DagNotStrings);
206973471bf0Spatrick   }
207073471bf0Spatrick 
207173471bf0Spatrick   return false;
207273471bf0Spatrick }
207373471bf0Spatrick 
207473471bf0Spatrick /// Returns either (1) \c ErrorSuccess if there was no error or (2)
207573471bf0Spatrick /// \c ErrorReported if an error was reported, such as an unexpected match.
printMatch(bool ExpectedMatch,const SourceMgr & SM,StringRef Prefix,SMLoc Loc,const Pattern & Pat,int MatchedCount,StringRef Buffer,Pattern::MatchResult MatchResult,const FileCheckRequest & Req,std::vector<FileCheckDiag> * Diags)207673471bf0Spatrick static Error printMatch(bool ExpectedMatch, const SourceMgr &SM,
207773471bf0Spatrick                         StringRef Prefix, SMLoc Loc, const Pattern &Pat,
207873471bf0Spatrick                         int MatchedCount, StringRef Buffer,
207973471bf0Spatrick                         Pattern::MatchResult MatchResult,
208073471bf0Spatrick                         const FileCheckRequest &Req,
208173471bf0Spatrick                         std::vector<FileCheckDiag> *Diags) {
208273471bf0Spatrick   // Suppress some verbosity if there's no error.
208373471bf0Spatrick   bool HasError = !ExpectedMatch || MatchResult.TheError;
208473471bf0Spatrick   bool PrintDiag = true;
208573471bf0Spatrick   if (!HasError) {
208673471bf0Spatrick     if (!Req.Verbose)
208773471bf0Spatrick       return ErrorReported::reportedOrSuccess(HasError);
208873471bf0Spatrick     if (!Req.VerboseVerbose && Pat.getCheckTy() == Check::CheckEOF)
208973471bf0Spatrick       return ErrorReported::reportedOrSuccess(HasError);
209073471bf0Spatrick     // Due to their verbosity, we don't print verbose diagnostics here if we're
209173471bf0Spatrick     // gathering them for Diags to be rendered elsewhere, but we always print
209273471bf0Spatrick     // other diagnostics.
209373471bf0Spatrick     PrintDiag = !Diags;
209473471bf0Spatrick   }
209573471bf0Spatrick 
209673471bf0Spatrick   // Add "found" diagnostic, substitutions, and variable definitions to Diags.
209773471bf0Spatrick   FileCheckDiag::MatchType MatchTy = ExpectedMatch
209873471bf0Spatrick                                          ? FileCheckDiag::MatchFoundAndExpected
209973471bf0Spatrick                                          : FileCheckDiag::MatchFoundButExcluded;
210073471bf0Spatrick   SMRange MatchRange = ProcessMatchResult(MatchTy, SM, Loc, Pat.getCheckTy(),
210173471bf0Spatrick                                           Buffer, MatchResult.TheMatch->Pos,
210273471bf0Spatrick                                           MatchResult.TheMatch->Len, Diags);
210373471bf0Spatrick   if (Diags) {
210473471bf0Spatrick     Pat.printSubstitutions(SM, Buffer, MatchRange, MatchTy, Diags);
210573471bf0Spatrick     Pat.printVariableDefs(SM, MatchTy, Diags);
210673471bf0Spatrick   }
210773471bf0Spatrick   if (!PrintDiag) {
210873471bf0Spatrick     assert(!HasError && "expected to report more diagnostics for error");
210973471bf0Spatrick     return ErrorReported::reportedOrSuccess(HasError);
211073471bf0Spatrick   }
211173471bf0Spatrick 
211273471bf0Spatrick   // Print the match.
211373471bf0Spatrick   std::string Message = formatv("{0}: {1} string found in input",
211473471bf0Spatrick                                 Pat.getCheckTy().getDescription(Prefix),
211573471bf0Spatrick                                 (ExpectedMatch ? "expected" : "excluded"))
211673471bf0Spatrick                             .str();
211773471bf0Spatrick   if (Pat.getCount() > 1)
211873471bf0Spatrick     Message += formatv(" ({0} out of {1})", MatchedCount, Pat.getCount()).str();
211973471bf0Spatrick   SM.PrintMessage(
212073471bf0Spatrick       Loc, ExpectedMatch ? SourceMgr::DK_Remark : SourceMgr::DK_Error, Message);
212173471bf0Spatrick   SM.PrintMessage(MatchRange.Start, SourceMgr::DK_Note, "found here",
212273471bf0Spatrick                   {MatchRange});
212373471bf0Spatrick 
212473471bf0Spatrick   // Print additional information, which can be useful even if there are errors.
212573471bf0Spatrick   Pat.printSubstitutions(SM, Buffer, MatchRange, MatchTy, nullptr);
212673471bf0Spatrick   Pat.printVariableDefs(SM, MatchTy, nullptr);
212773471bf0Spatrick 
212873471bf0Spatrick   // Print errors and add them to Diags.  We report these errors after the match
212973471bf0Spatrick   // itself because we found them after the match.  If we had found them before
213073471bf0Spatrick   // the match, we'd be in printNoMatch.
213173471bf0Spatrick   handleAllErrors(std::move(MatchResult.TheError),
213273471bf0Spatrick                   [&](const ErrorDiagnostic &E) {
213373471bf0Spatrick                     E.log(errs());
213473471bf0Spatrick                     if (Diags) {
213573471bf0Spatrick                       Diags->emplace_back(SM, Pat.getCheckTy(), Loc,
213673471bf0Spatrick                                           FileCheckDiag::MatchFoundErrorNote,
213773471bf0Spatrick                                           E.getRange(), E.getMessage().str());
213873471bf0Spatrick                     }
213973471bf0Spatrick                   });
214073471bf0Spatrick   return ErrorReported::reportedOrSuccess(HasError);
214173471bf0Spatrick }
214273471bf0Spatrick 
214373471bf0Spatrick /// Returns either (1) \c ErrorSuccess if there was no error, or (2)
214473471bf0Spatrick /// \c ErrorReported if an error was reported, such as an expected match not
214573471bf0Spatrick /// found.
printNoMatch(bool ExpectedMatch,const SourceMgr & SM,StringRef Prefix,SMLoc Loc,const Pattern & Pat,int MatchedCount,StringRef Buffer,Error MatchError,bool VerboseVerbose,std::vector<FileCheckDiag> * Diags)214673471bf0Spatrick static Error printNoMatch(bool ExpectedMatch, const SourceMgr &SM,
214773471bf0Spatrick                           StringRef Prefix, SMLoc Loc, const Pattern &Pat,
214873471bf0Spatrick                           int MatchedCount, StringRef Buffer, Error MatchError,
214973471bf0Spatrick                           bool VerboseVerbose,
215073471bf0Spatrick                           std::vector<FileCheckDiag> *Diags) {
215173471bf0Spatrick   // Print any pattern errors, and record them to be added to Diags later.
215273471bf0Spatrick   bool HasError = ExpectedMatch;
215373471bf0Spatrick   bool HasPatternError = false;
215473471bf0Spatrick   FileCheckDiag::MatchType MatchTy = ExpectedMatch
215573471bf0Spatrick                                          ? FileCheckDiag::MatchNoneButExpected
215673471bf0Spatrick                                          : FileCheckDiag::MatchNoneAndExcluded;
215773471bf0Spatrick   SmallVector<std::string, 4> ErrorMsgs;
215873471bf0Spatrick   handleAllErrors(
215973471bf0Spatrick       std::move(MatchError),
216073471bf0Spatrick       [&](const ErrorDiagnostic &E) {
216173471bf0Spatrick         HasError = HasPatternError = true;
216273471bf0Spatrick         MatchTy = FileCheckDiag::MatchNoneForInvalidPattern;
216373471bf0Spatrick         E.log(errs());
216473471bf0Spatrick         if (Diags)
216573471bf0Spatrick           ErrorMsgs.push_back(E.getMessage().str());
216673471bf0Spatrick       },
216773471bf0Spatrick       // NotFoundError is why printNoMatch was invoked.
216873471bf0Spatrick       [](const NotFoundError &E) {});
216973471bf0Spatrick 
217073471bf0Spatrick   // Suppress some verbosity if there's no error.
217173471bf0Spatrick   bool PrintDiag = true;
217273471bf0Spatrick   if (!HasError) {
217373471bf0Spatrick     if (!VerboseVerbose)
217473471bf0Spatrick       return ErrorReported::reportedOrSuccess(HasError);
217573471bf0Spatrick     // Due to their verbosity, we don't print verbose diagnostics here if we're
217673471bf0Spatrick     // gathering them for Diags to be rendered elsewhere, but we always print
217773471bf0Spatrick     // other diagnostics.
217873471bf0Spatrick     PrintDiag = !Diags;
217973471bf0Spatrick   }
218073471bf0Spatrick 
218173471bf0Spatrick   // Add "not found" diagnostic, substitutions, and pattern errors to Diags.
218273471bf0Spatrick   //
218373471bf0Spatrick   // We handle Diags a little differently than the errors we print directly:
218473471bf0Spatrick   // we add the "not found" diagnostic to Diags even if there are pattern
218573471bf0Spatrick   // errors.  The reason is that we need to attach pattern errors as notes
218673471bf0Spatrick   // somewhere in the input, and the input search range from the "not found"
218773471bf0Spatrick   // diagnostic is all we have to anchor them.
218873471bf0Spatrick   SMRange SearchRange = ProcessMatchResult(MatchTy, SM, Loc, Pat.getCheckTy(),
218973471bf0Spatrick                                            Buffer, 0, Buffer.size(), Diags);
219073471bf0Spatrick   if (Diags) {
219173471bf0Spatrick     SMRange NoteRange = SMRange(SearchRange.Start, SearchRange.Start);
219273471bf0Spatrick     for (StringRef ErrorMsg : ErrorMsgs)
219373471bf0Spatrick       Diags->emplace_back(SM, Pat.getCheckTy(), Loc, MatchTy, NoteRange,
219473471bf0Spatrick                           ErrorMsg);
219573471bf0Spatrick     Pat.printSubstitutions(SM, Buffer, SearchRange, MatchTy, Diags);
219673471bf0Spatrick   }
219773471bf0Spatrick   if (!PrintDiag) {
219873471bf0Spatrick     assert(!HasError && "expected to report more diagnostics for error");
219973471bf0Spatrick     return ErrorReported::reportedOrSuccess(HasError);
220073471bf0Spatrick   }
220173471bf0Spatrick 
220273471bf0Spatrick   // Print "not found" diagnostic, except that's implied if we already printed a
220373471bf0Spatrick   // pattern error.
220473471bf0Spatrick   if (!HasPatternError) {
220573471bf0Spatrick     std::string Message = formatv("{0}: {1} string not found in input",
220673471bf0Spatrick                                   Pat.getCheckTy().getDescription(Prefix),
220773471bf0Spatrick                                   (ExpectedMatch ? "expected" : "excluded"))
220873471bf0Spatrick                               .str();
220973471bf0Spatrick     if (Pat.getCount() > 1)
221073471bf0Spatrick       Message +=
221173471bf0Spatrick           formatv(" ({0} out of {1})", MatchedCount, Pat.getCount()).str();
221273471bf0Spatrick     SM.PrintMessage(Loc,
221373471bf0Spatrick                     ExpectedMatch ? SourceMgr::DK_Error : SourceMgr::DK_Remark,
221473471bf0Spatrick                     Message);
221573471bf0Spatrick     SM.PrintMessage(SearchRange.Start, SourceMgr::DK_Note,
221673471bf0Spatrick                     "scanning from here");
221773471bf0Spatrick   }
221873471bf0Spatrick 
221973471bf0Spatrick   // Print additional information, which can be useful even after a pattern
222073471bf0Spatrick   // error.
222173471bf0Spatrick   Pat.printSubstitutions(SM, Buffer, SearchRange, MatchTy, nullptr);
222273471bf0Spatrick   if (ExpectedMatch)
222373471bf0Spatrick     Pat.printFuzzyMatch(SM, Buffer, Diags);
222473471bf0Spatrick   return ErrorReported::reportedOrSuccess(HasError);
222573471bf0Spatrick }
222673471bf0Spatrick 
222773471bf0Spatrick /// Returns either (1) \c ErrorSuccess if there was no error, or (2)
222873471bf0Spatrick /// \c ErrorReported if an error was reported.
reportMatchResult(bool ExpectedMatch,const SourceMgr & SM,StringRef Prefix,SMLoc Loc,const Pattern & Pat,int MatchedCount,StringRef Buffer,Pattern::MatchResult MatchResult,const FileCheckRequest & Req,std::vector<FileCheckDiag> * Diags)222973471bf0Spatrick static Error reportMatchResult(bool ExpectedMatch, const SourceMgr &SM,
223073471bf0Spatrick                                StringRef Prefix, SMLoc Loc, const Pattern &Pat,
223173471bf0Spatrick                                int MatchedCount, StringRef Buffer,
223273471bf0Spatrick                                Pattern::MatchResult MatchResult,
223373471bf0Spatrick                                const FileCheckRequest &Req,
223473471bf0Spatrick                                std::vector<FileCheckDiag> *Diags) {
223573471bf0Spatrick   if (MatchResult.TheMatch)
223673471bf0Spatrick     return printMatch(ExpectedMatch, SM, Prefix, Loc, Pat, MatchedCount, Buffer,
223773471bf0Spatrick                       std::move(MatchResult), Req, Diags);
223873471bf0Spatrick   return printNoMatch(ExpectedMatch, SM, Prefix, Loc, Pat, MatchedCount, Buffer,
223973471bf0Spatrick                       std::move(MatchResult.TheError), Req.VerboseVerbose,
224073471bf0Spatrick                       Diags);
224173471bf0Spatrick }
224273471bf0Spatrick 
224373471bf0Spatrick /// Counts the number of newlines in the specified range.
CountNumNewlinesBetween(StringRef Range,const char * & FirstNewLine)224473471bf0Spatrick static unsigned CountNumNewlinesBetween(StringRef Range,
224573471bf0Spatrick                                         const char *&FirstNewLine) {
224673471bf0Spatrick   unsigned NumNewLines = 0;
2247*d415bd75Srobert   while (true) {
224873471bf0Spatrick     // Scan for newline.
224973471bf0Spatrick     Range = Range.substr(Range.find_first_of("\n\r"));
225073471bf0Spatrick     if (Range.empty())
225173471bf0Spatrick       return NumNewLines;
225273471bf0Spatrick 
225373471bf0Spatrick     ++NumNewLines;
225473471bf0Spatrick 
225573471bf0Spatrick     // Handle \n\r and \r\n as a single newline.
225673471bf0Spatrick     if (Range.size() > 1 && (Range[1] == '\n' || Range[1] == '\r') &&
225773471bf0Spatrick         (Range[0] != Range[1]))
225873471bf0Spatrick       Range = Range.substr(1);
225973471bf0Spatrick     Range = Range.substr(1);
226073471bf0Spatrick 
226173471bf0Spatrick     if (NumNewLines == 1)
226273471bf0Spatrick       FirstNewLine = Range.begin();
226373471bf0Spatrick   }
226473471bf0Spatrick }
226573471bf0Spatrick 
Check(const SourceMgr & SM,StringRef Buffer,bool IsLabelScanMode,size_t & MatchLen,FileCheckRequest & Req,std::vector<FileCheckDiag> * Diags) const226673471bf0Spatrick size_t FileCheckString::Check(const SourceMgr &SM, StringRef Buffer,
226773471bf0Spatrick                               bool IsLabelScanMode, size_t &MatchLen,
226873471bf0Spatrick                               FileCheckRequest &Req,
226973471bf0Spatrick                               std::vector<FileCheckDiag> *Diags) const {
227073471bf0Spatrick   size_t LastPos = 0;
227173471bf0Spatrick   std::vector<const Pattern *> NotStrings;
227273471bf0Spatrick 
227373471bf0Spatrick   // IsLabelScanMode is true when we are scanning forward to find CHECK-LABEL
227473471bf0Spatrick   // bounds; we have not processed variable definitions within the bounded block
227573471bf0Spatrick   // yet so cannot handle any final CHECK-DAG yet; this is handled when going
227673471bf0Spatrick   // over the block again (including the last CHECK-LABEL) in normal mode.
227773471bf0Spatrick   if (!IsLabelScanMode) {
227873471bf0Spatrick     // Match "dag strings" (with mixed "not strings" if any).
227973471bf0Spatrick     LastPos = CheckDag(SM, Buffer, NotStrings, Req, Diags);
228073471bf0Spatrick     if (LastPos == StringRef::npos)
228173471bf0Spatrick       return StringRef::npos;
228273471bf0Spatrick   }
228373471bf0Spatrick 
228473471bf0Spatrick   // Match itself from the last position after matching CHECK-DAG.
228573471bf0Spatrick   size_t LastMatchEnd = LastPos;
228673471bf0Spatrick   size_t FirstMatchPos = 0;
228773471bf0Spatrick   // Go match the pattern Count times. Majority of patterns only match with
228873471bf0Spatrick   // count 1 though.
228973471bf0Spatrick   assert(Pat.getCount() != 0 && "pattern count can not be zero");
229073471bf0Spatrick   for (int i = 1; i <= Pat.getCount(); i++) {
229173471bf0Spatrick     StringRef MatchBuffer = Buffer.substr(LastMatchEnd);
229273471bf0Spatrick     // get a match at current start point
229373471bf0Spatrick     Pattern::MatchResult MatchResult = Pat.match(MatchBuffer, SM);
229473471bf0Spatrick 
229573471bf0Spatrick     // report
229673471bf0Spatrick     if (Error Err = reportMatchResult(/*ExpectedMatch=*/true, SM, Prefix, Loc,
229773471bf0Spatrick                                       Pat, i, MatchBuffer,
229873471bf0Spatrick                                       std::move(MatchResult), Req, Diags)) {
229973471bf0Spatrick       cantFail(handleErrors(std::move(Err), [&](const ErrorReported &E) {}));
230073471bf0Spatrick       return StringRef::npos;
230173471bf0Spatrick     }
230273471bf0Spatrick 
230373471bf0Spatrick     size_t MatchPos = MatchResult.TheMatch->Pos;
230473471bf0Spatrick     if (i == 1)
230573471bf0Spatrick       FirstMatchPos = LastPos + MatchPos;
230673471bf0Spatrick 
230773471bf0Spatrick     // move start point after the match
230873471bf0Spatrick     LastMatchEnd += MatchPos + MatchResult.TheMatch->Len;
230973471bf0Spatrick   }
231073471bf0Spatrick   // Full match len counts from first match pos.
231173471bf0Spatrick   MatchLen = LastMatchEnd - FirstMatchPos;
231273471bf0Spatrick 
231373471bf0Spatrick   // Similar to the above, in "label-scan mode" we can't yet handle CHECK-NEXT
231473471bf0Spatrick   // or CHECK-NOT
231573471bf0Spatrick   if (!IsLabelScanMode) {
231673471bf0Spatrick     size_t MatchPos = FirstMatchPos - LastPos;
231773471bf0Spatrick     StringRef MatchBuffer = Buffer.substr(LastPos);
231873471bf0Spatrick     StringRef SkippedRegion = Buffer.substr(LastPos, MatchPos);
231973471bf0Spatrick 
232073471bf0Spatrick     // If this check is a "CHECK-NEXT", verify that the previous match was on
232173471bf0Spatrick     // the previous line (i.e. that there is one newline between them).
232273471bf0Spatrick     if (CheckNext(SM, SkippedRegion)) {
232373471bf0Spatrick       ProcessMatchResult(FileCheckDiag::MatchFoundButWrongLine, SM, Loc,
232473471bf0Spatrick                          Pat.getCheckTy(), MatchBuffer, MatchPos, MatchLen,
232573471bf0Spatrick                          Diags, Req.Verbose);
232673471bf0Spatrick       return StringRef::npos;
232773471bf0Spatrick     }
232873471bf0Spatrick 
232973471bf0Spatrick     // If this check is a "CHECK-SAME", verify that the previous match was on
233073471bf0Spatrick     // the same line (i.e. that there is no newline between them).
233173471bf0Spatrick     if (CheckSame(SM, SkippedRegion)) {
233273471bf0Spatrick       ProcessMatchResult(FileCheckDiag::MatchFoundButWrongLine, SM, Loc,
233373471bf0Spatrick                          Pat.getCheckTy(), MatchBuffer, MatchPos, MatchLen,
233473471bf0Spatrick                          Diags, Req.Verbose);
233573471bf0Spatrick       return StringRef::npos;
233673471bf0Spatrick     }
233773471bf0Spatrick 
233873471bf0Spatrick     // If this match had "not strings", verify that they don't exist in the
233973471bf0Spatrick     // skipped region.
234073471bf0Spatrick     if (CheckNot(SM, SkippedRegion, NotStrings, Req, Diags))
234173471bf0Spatrick       return StringRef::npos;
234273471bf0Spatrick   }
234373471bf0Spatrick 
234473471bf0Spatrick   return FirstMatchPos;
234573471bf0Spatrick }
234673471bf0Spatrick 
CheckNext(const SourceMgr & SM,StringRef Buffer) const234773471bf0Spatrick bool FileCheckString::CheckNext(const SourceMgr &SM, StringRef Buffer) const {
234873471bf0Spatrick   if (Pat.getCheckTy() != Check::CheckNext &&
234973471bf0Spatrick       Pat.getCheckTy() != Check::CheckEmpty)
235073471bf0Spatrick     return false;
235173471bf0Spatrick 
235273471bf0Spatrick   Twine CheckName =
235373471bf0Spatrick       Prefix +
235473471bf0Spatrick       Twine(Pat.getCheckTy() == Check::CheckEmpty ? "-EMPTY" : "-NEXT");
235573471bf0Spatrick 
235673471bf0Spatrick   // Count the number of newlines between the previous match and this one.
235773471bf0Spatrick   const char *FirstNewLine = nullptr;
235873471bf0Spatrick   unsigned NumNewLines = CountNumNewlinesBetween(Buffer, FirstNewLine);
235973471bf0Spatrick 
236073471bf0Spatrick   if (NumNewLines == 0) {
236173471bf0Spatrick     SM.PrintMessage(Loc, SourceMgr::DK_Error,
236273471bf0Spatrick                     CheckName + ": is on the same line as previous match");
236373471bf0Spatrick     SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), SourceMgr::DK_Note,
236473471bf0Spatrick                     "'next' match was here");
236573471bf0Spatrick     SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,
236673471bf0Spatrick                     "previous match ended here");
236773471bf0Spatrick     return true;
236873471bf0Spatrick   }
236973471bf0Spatrick 
237073471bf0Spatrick   if (NumNewLines != 1) {
237173471bf0Spatrick     SM.PrintMessage(Loc, SourceMgr::DK_Error,
237273471bf0Spatrick                     CheckName +
237373471bf0Spatrick                         ": is not on the line after the previous match");
237473471bf0Spatrick     SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), SourceMgr::DK_Note,
237573471bf0Spatrick                     "'next' match was here");
237673471bf0Spatrick     SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,
237773471bf0Spatrick                     "previous match ended here");
237873471bf0Spatrick     SM.PrintMessage(SMLoc::getFromPointer(FirstNewLine), SourceMgr::DK_Note,
237973471bf0Spatrick                     "non-matching line after previous match is here");
238073471bf0Spatrick     return true;
238173471bf0Spatrick   }
238273471bf0Spatrick 
238373471bf0Spatrick   return false;
238473471bf0Spatrick }
238573471bf0Spatrick 
CheckSame(const SourceMgr & SM,StringRef Buffer) const238673471bf0Spatrick bool FileCheckString::CheckSame(const SourceMgr &SM, StringRef Buffer) const {
238773471bf0Spatrick   if (Pat.getCheckTy() != Check::CheckSame)
238873471bf0Spatrick     return false;
238973471bf0Spatrick 
239073471bf0Spatrick   // Count the number of newlines between the previous match and this one.
239173471bf0Spatrick   const char *FirstNewLine = nullptr;
239273471bf0Spatrick   unsigned NumNewLines = CountNumNewlinesBetween(Buffer, FirstNewLine);
239373471bf0Spatrick 
239473471bf0Spatrick   if (NumNewLines != 0) {
239573471bf0Spatrick     SM.PrintMessage(Loc, SourceMgr::DK_Error,
239673471bf0Spatrick                     Prefix +
239773471bf0Spatrick                         "-SAME: is not on the same line as the previous match");
239873471bf0Spatrick     SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), SourceMgr::DK_Note,
239973471bf0Spatrick                     "'next' match was here");
240073471bf0Spatrick     SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,
240173471bf0Spatrick                     "previous match ended here");
240273471bf0Spatrick     return true;
240373471bf0Spatrick   }
240473471bf0Spatrick 
240573471bf0Spatrick   return false;
240673471bf0Spatrick }
240773471bf0Spatrick 
CheckNot(const SourceMgr & SM,StringRef Buffer,const std::vector<const Pattern * > & NotStrings,const FileCheckRequest & Req,std::vector<FileCheckDiag> * Diags) const240873471bf0Spatrick bool FileCheckString::CheckNot(const SourceMgr &SM, StringRef Buffer,
240973471bf0Spatrick                                const std::vector<const Pattern *> &NotStrings,
241073471bf0Spatrick                                const FileCheckRequest &Req,
241173471bf0Spatrick                                std::vector<FileCheckDiag> *Diags) const {
241273471bf0Spatrick   bool DirectiveFail = false;
241373471bf0Spatrick   for (const Pattern *Pat : NotStrings) {
241473471bf0Spatrick     assert((Pat->getCheckTy() == Check::CheckNot) && "Expect CHECK-NOT!");
241573471bf0Spatrick     Pattern::MatchResult MatchResult = Pat->match(Buffer, SM);
241673471bf0Spatrick     if (Error Err = reportMatchResult(/*ExpectedMatch=*/false, SM, Prefix,
241773471bf0Spatrick                                       Pat->getLoc(), *Pat, 1, Buffer,
241873471bf0Spatrick                                       std::move(MatchResult), Req, Diags)) {
241973471bf0Spatrick       cantFail(handleErrors(std::move(Err), [&](const ErrorReported &E) {}));
242073471bf0Spatrick       DirectiveFail = true;
242173471bf0Spatrick       continue;
242273471bf0Spatrick     }
242373471bf0Spatrick   }
242473471bf0Spatrick   return DirectiveFail;
242573471bf0Spatrick }
242673471bf0Spatrick 
CheckDag(const SourceMgr & SM,StringRef Buffer,std::vector<const Pattern * > & NotStrings,const FileCheckRequest & Req,std::vector<FileCheckDiag> * Diags) const242773471bf0Spatrick size_t FileCheckString::CheckDag(const SourceMgr &SM, StringRef Buffer,
242873471bf0Spatrick                                  std::vector<const Pattern *> &NotStrings,
242973471bf0Spatrick                                  const FileCheckRequest &Req,
243073471bf0Spatrick                                  std::vector<FileCheckDiag> *Diags) const {
243173471bf0Spatrick   if (DagNotStrings.empty())
243273471bf0Spatrick     return 0;
243373471bf0Spatrick 
243473471bf0Spatrick   // The start of the search range.
243573471bf0Spatrick   size_t StartPos = 0;
243673471bf0Spatrick 
243773471bf0Spatrick   struct MatchRange {
243873471bf0Spatrick     size_t Pos;
243973471bf0Spatrick     size_t End;
244073471bf0Spatrick   };
244173471bf0Spatrick   // A sorted list of ranges for non-overlapping CHECK-DAG matches.  Match
244273471bf0Spatrick   // ranges are erased from this list once they are no longer in the search
244373471bf0Spatrick   // range.
244473471bf0Spatrick   std::list<MatchRange> MatchRanges;
244573471bf0Spatrick 
244673471bf0Spatrick   // We need PatItr and PatEnd later for detecting the end of a CHECK-DAG
244773471bf0Spatrick   // group, so we don't use a range-based for loop here.
244873471bf0Spatrick   for (auto PatItr = DagNotStrings.begin(), PatEnd = DagNotStrings.end();
244973471bf0Spatrick        PatItr != PatEnd; ++PatItr) {
245073471bf0Spatrick     const Pattern &Pat = *PatItr;
245173471bf0Spatrick     assert((Pat.getCheckTy() == Check::CheckDAG ||
245273471bf0Spatrick             Pat.getCheckTy() == Check::CheckNot) &&
245373471bf0Spatrick            "Invalid CHECK-DAG or CHECK-NOT!");
245473471bf0Spatrick 
245573471bf0Spatrick     if (Pat.getCheckTy() == Check::CheckNot) {
245673471bf0Spatrick       NotStrings.push_back(&Pat);
245773471bf0Spatrick       continue;
245873471bf0Spatrick     }
245973471bf0Spatrick 
246073471bf0Spatrick     assert((Pat.getCheckTy() == Check::CheckDAG) && "Expect CHECK-DAG!");
246173471bf0Spatrick 
246273471bf0Spatrick     // CHECK-DAG always matches from the start.
246373471bf0Spatrick     size_t MatchLen = 0, MatchPos = StartPos;
246473471bf0Spatrick 
246573471bf0Spatrick     // Search for a match that doesn't overlap a previous match in this
246673471bf0Spatrick     // CHECK-DAG group.
246773471bf0Spatrick     for (auto MI = MatchRanges.begin(), ME = MatchRanges.end(); true; ++MI) {
246873471bf0Spatrick       StringRef MatchBuffer = Buffer.substr(MatchPos);
246973471bf0Spatrick       Pattern::MatchResult MatchResult = Pat.match(MatchBuffer, SM);
247073471bf0Spatrick       // With a group of CHECK-DAGs, a single mismatching means the match on
247173471bf0Spatrick       // that group of CHECK-DAGs fails immediately.
247273471bf0Spatrick       if (MatchResult.TheError || Req.VerboseVerbose) {
247373471bf0Spatrick         if (Error Err = reportMatchResult(/*ExpectedMatch=*/true, SM, Prefix,
247473471bf0Spatrick                                           Pat.getLoc(), Pat, 1, MatchBuffer,
247573471bf0Spatrick                                           std::move(MatchResult), Req, Diags)) {
247673471bf0Spatrick           cantFail(
247773471bf0Spatrick               handleErrors(std::move(Err), [&](const ErrorReported &E) {}));
247873471bf0Spatrick           return StringRef::npos;
247973471bf0Spatrick         }
248073471bf0Spatrick       }
248173471bf0Spatrick       MatchLen = MatchResult.TheMatch->Len;
248273471bf0Spatrick       // Re-calc it as the offset relative to the start of the original
248373471bf0Spatrick       // string.
248473471bf0Spatrick       MatchPos += MatchResult.TheMatch->Pos;
248573471bf0Spatrick       MatchRange M{MatchPos, MatchPos + MatchLen};
248673471bf0Spatrick       if (Req.AllowDeprecatedDagOverlap) {
248773471bf0Spatrick         // We don't need to track all matches in this mode, so we just maintain
248873471bf0Spatrick         // one match range that encompasses the current CHECK-DAG group's
248973471bf0Spatrick         // matches.
249073471bf0Spatrick         if (MatchRanges.empty())
249173471bf0Spatrick           MatchRanges.insert(MatchRanges.end(), M);
249273471bf0Spatrick         else {
249373471bf0Spatrick           auto Block = MatchRanges.begin();
249473471bf0Spatrick           Block->Pos = std::min(Block->Pos, M.Pos);
249573471bf0Spatrick           Block->End = std::max(Block->End, M.End);
249673471bf0Spatrick         }
249773471bf0Spatrick         break;
249873471bf0Spatrick       }
249973471bf0Spatrick       // Iterate previous matches until overlapping match or insertion point.
250073471bf0Spatrick       bool Overlap = false;
250173471bf0Spatrick       for (; MI != ME; ++MI) {
250273471bf0Spatrick         if (M.Pos < MI->End) {
250373471bf0Spatrick           // !Overlap => New match has no overlap and is before this old match.
250473471bf0Spatrick           // Overlap => New match overlaps this old match.
250573471bf0Spatrick           Overlap = MI->Pos < M.End;
250673471bf0Spatrick           break;
250773471bf0Spatrick         }
250873471bf0Spatrick       }
250973471bf0Spatrick       if (!Overlap) {
251073471bf0Spatrick         // Insert non-overlapping match into list.
251173471bf0Spatrick         MatchRanges.insert(MI, M);
251273471bf0Spatrick         break;
251373471bf0Spatrick       }
251473471bf0Spatrick       if (Req.VerboseVerbose) {
251573471bf0Spatrick         // Due to their verbosity, we don't print verbose diagnostics here if
251673471bf0Spatrick         // we're gathering them for a different rendering, but we always print
251773471bf0Spatrick         // other diagnostics.
251873471bf0Spatrick         if (!Diags) {
251973471bf0Spatrick           SMLoc OldStart = SMLoc::getFromPointer(Buffer.data() + MI->Pos);
252073471bf0Spatrick           SMLoc OldEnd = SMLoc::getFromPointer(Buffer.data() + MI->End);
252173471bf0Spatrick           SMRange OldRange(OldStart, OldEnd);
252273471bf0Spatrick           SM.PrintMessage(OldStart, SourceMgr::DK_Note,
252373471bf0Spatrick                           "match discarded, overlaps earlier DAG match here",
252473471bf0Spatrick                           {OldRange});
252573471bf0Spatrick         } else {
252673471bf0Spatrick           SMLoc CheckLoc = Diags->rbegin()->CheckLoc;
252773471bf0Spatrick           for (auto I = Diags->rbegin(), E = Diags->rend();
252873471bf0Spatrick                I != E && I->CheckLoc == CheckLoc; ++I)
252973471bf0Spatrick             I->MatchTy = FileCheckDiag::MatchFoundButDiscarded;
253073471bf0Spatrick         }
253173471bf0Spatrick       }
253273471bf0Spatrick       MatchPos = MI->End;
253373471bf0Spatrick     }
253473471bf0Spatrick     if (!Req.VerboseVerbose)
253573471bf0Spatrick       cantFail(printMatch(
253673471bf0Spatrick           /*ExpectedMatch=*/true, SM, Prefix, Pat.getLoc(), Pat, 1, Buffer,
253773471bf0Spatrick           Pattern::MatchResult(MatchPos, MatchLen, Error::success()), Req,
253873471bf0Spatrick           Diags));
253973471bf0Spatrick 
254073471bf0Spatrick     // Handle the end of a CHECK-DAG group.
254173471bf0Spatrick     if (std::next(PatItr) == PatEnd ||
254273471bf0Spatrick         std::next(PatItr)->getCheckTy() == Check::CheckNot) {
254373471bf0Spatrick       if (!NotStrings.empty()) {
254473471bf0Spatrick         // If there are CHECK-NOTs between two CHECK-DAGs or from CHECK to
254573471bf0Spatrick         // CHECK-DAG, verify that there are no 'not' strings occurred in that
254673471bf0Spatrick         // region.
254773471bf0Spatrick         StringRef SkippedRegion =
254873471bf0Spatrick             Buffer.slice(StartPos, MatchRanges.begin()->Pos);
254973471bf0Spatrick         if (CheckNot(SM, SkippedRegion, NotStrings, Req, Diags))
255073471bf0Spatrick           return StringRef::npos;
255173471bf0Spatrick         // Clear "not strings".
255273471bf0Spatrick         NotStrings.clear();
255373471bf0Spatrick       }
255473471bf0Spatrick       // All subsequent CHECK-DAGs and CHECK-NOTs should be matched from the
255573471bf0Spatrick       // end of this CHECK-DAG group's match range.
255673471bf0Spatrick       StartPos = MatchRanges.rbegin()->End;
255773471bf0Spatrick       // Don't waste time checking for (impossible) overlaps before that.
255873471bf0Spatrick       MatchRanges.clear();
255973471bf0Spatrick     }
256073471bf0Spatrick   }
256173471bf0Spatrick 
256273471bf0Spatrick   return StartPos;
256373471bf0Spatrick }
256473471bf0Spatrick 
ValidatePrefixes(StringRef Kind,StringSet<> & UniquePrefixes,ArrayRef<StringRef> SuppliedPrefixes)256573471bf0Spatrick static bool ValidatePrefixes(StringRef Kind, StringSet<> &UniquePrefixes,
256673471bf0Spatrick                              ArrayRef<StringRef> SuppliedPrefixes) {
256773471bf0Spatrick   for (StringRef Prefix : SuppliedPrefixes) {
256873471bf0Spatrick     if (Prefix.empty()) {
256973471bf0Spatrick       errs() << "error: supplied " << Kind << " prefix must not be the empty "
257073471bf0Spatrick              << "string\n";
257173471bf0Spatrick       return false;
257273471bf0Spatrick     }
257373471bf0Spatrick     static const Regex Validator("^[a-zA-Z0-9_-]*$");
257473471bf0Spatrick     if (!Validator.match(Prefix)) {
257573471bf0Spatrick       errs() << "error: supplied " << Kind << " prefix must start with a "
257673471bf0Spatrick              << "letter and contain only alphanumeric characters, hyphens, and "
257773471bf0Spatrick              << "underscores: '" << Prefix << "'\n";
257873471bf0Spatrick       return false;
257973471bf0Spatrick     }
258073471bf0Spatrick     if (!UniquePrefixes.insert(Prefix).second) {
258173471bf0Spatrick       errs() << "error: supplied " << Kind << " prefix must be unique among "
258273471bf0Spatrick              << "check and comment prefixes: '" << Prefix << "'\n";
258373471bf0Spatrick       return false;
258473471bf0Spatrick     }
258573471bf0Spatrick   }
258673471bf0Spatrick   return true;
258773471bf0Spatrick }
258873471bf0Spatrick 
258973471bf0Spatrick static const char *DefaultCheckPrefixes[] = {"CHECK"};
259073471bf0Spatrick static const char *DefaultCommentPrefixes[] = {"COM", "RUN"};
259173471bf0Spatrick 
ValidateCheckPrefixes()259273471bf0Spatrick bool FileCheck::ValidateCheckPrefixes() {
259373471bf0Spatrick   StringSet<> UniquePrefixes;
259473471bf0Spatrick   // Add default prefixes to catch user-supplied duplicates of them below.
259573471bf0Spatrick   if (Req.CheckPrefixes.empty()) {
259673471bf0Spatrick     for (const char *Prefix : DefaultCheckPrefixes)
259773471bf0Spatrick       UniquePrefixes.insert(Prefix);
259873471bf0Spatrick   }
259973471bf0Spatrick   if (Req.CommentPrefixes.empty()) {
260073471bf0Spatrick     for (const char *Prefix : DefaultCommentPrefixes)
260173471bf0Spatrick       UniquePrefixes.insert(Prefix);
260273471bf0Spatrick   }
260373471bf0Spatrick   // Do not validate the default prefixes, or diagnostics about duplicates might
260473471bf0Spatrick   // incorrectly indicate that they were supplied by the user.
260573471bf0Spatrick   if (!ValidatePrefixes("check", UniquePrefixes, Req.CheckPrefixes))
260673471bf0Spatrick     return false;
260773471bf0Spatrick   if (!ValidatePrefixes("comment", UniquePrefixes, Req.CommentPrefixes))
260873471bf0Spatrick     return false;
260973471bf0Spatrick   return true;
261073471bf0Spatrick }
261173471bf0Spatrick 
buildCheckPrefixRegex()261273471bf0Spatrick Regex FileCheck::buildCheckPrefixRegex() {
261373471bf0Spatrick   if (Req.CheckPrefixes.empty()) {
261473471bf0Spatrick     for (const char *Prefix : DefaultCheckPrefixes)
261573471bf0Spatrick       Req.CheckPrefixes.push_back(Prefix);
261673471bf0Spatrick     Req.IsDefaultCheckPrefix = true;
261773471bf0Spatrick   }
261873471bf0Spatrick   if (Req.CommentPrefixes.empty()) {
261973471bf0Spatrick     for (const char *Prefix : DefaultCommentPrefixes)
262073471bf0Spatrick       Req.CommentPrefixes.push_back(Prefix);
262173471bf0Spatrick   }
262273471bf0Spatrick 
262373471bf0Spatrick   // We already validated the contents of CheckPrefixes and CommentPrefixes so
262473471bf0Spatrick   // just concatenate them as alternatives.
262573471bf0Spatrick   SmallString<32> PrefixRegexStr;
262673471bf0Spatrick   for (size_t I = 0, E = Req.CheckPrefixes.size(); I != E; ++I) {
262773471bf0Spatrick     if (I != 0)
262873471bf0Spatrick       PrefixRegexStr.push_back('|');
262973471bf0Spatrick     PrefixRegexStr.append(Req.CheckPrefixes[I]);
263073471bf0Spatrick   }
263173471bf0Spatrick   for (StringRef Prefix : Req.CommentPrefixes) {
263273471bf0Spatrick     PrefixRegexStr.push_back('|');
263373471bf0Spatrick     PrefixRegexStr.append(Prefix);
263473471bf0Spatrick   }
263573471bf0Spatrick 
263673471bf0Spatrick   return Regex(PrefixRegexStr);
263773471bf0Spatrick }
263873471bf0Spatrick 
defineCmdlineVariables(ArrayRef<StringRef> CmdlineDefines,SourceMgr & SM)263973471bf0Spatrick Error FileCheckPatternContext::defineCmdlineVariables(
264073471bf0Spatrick     ArrayRef<StringRef> CmdlineDefines, SourceMgr &SM) {
264173471bf0Spatrick   assert(GlobalVariableTable.empty() && GlobalNumericVariableTable.empty() &&
264273471bf0Spatrick          "Overriding defined variable with command-line variable definitions");
264373471bf0Spatrick 
264473471bf0Spatrick   if (CmdlineDefines.empty())
264573471bf0Spatrick     return Error::success();
264673471bf0Spatrick 
264773471bf0Spatrick   // Create a string representing the vector of command-line definitions. Each
264873471bf0Spatrick   // definition is on its own line and prefixed with a definition number to
264973471bf0Spatrick   // clarify which definition a given diagnostic corresponds to.
265073471bf0Spatrick   unsigned I = 0;
265173471bf0Spatrick   Error Errs = Error::success();
265273471bf0Spatrick   std::string CmdlineDefsDiag;
265373471bf0Spatrick   SmallVector<std::pair<size_t, size_t>, 4> CmdlineDefsIndices;
265473471bf0Spatrick   for (StringRef CmdlineDef : CmdlineDefines) {
265573471bf0Spatrick     std::string DefPrefix = ("Global define #" + Twine(++I) + ": ").str();
265673471bf0Spatrick     size_t EqIdx = CmdlineDef.find('=');
265773471bf0Spatrick     if (EqIdx == StringRef::npos) {
265873471bf0Spatrick       CmdlineDefsIndices.push_back(std::make_pair(CmdlineDefsDiag.size(), 0));
265973471bf0Spatrick       continue;
266073471bf0Spatrick     }
266173471bf0Spatrick     // Numeric variable definition.
266273471bf0Spatrick     if (CmdlineDef[0] == '#') {
266373471bf0Spatrick       // Append a copy of the command-line definition adapted to use the same
266473471bf0Spatrick       // format as in the input file to be able to reuse
266573471bf0Spatrick       // parseNumericSubstitutionBlock.
266673471bf0Spatrick       CmdlineDefsDiag += (DefPrefix + CmdlineDef + " (parsed as: [[").str();
266773471bf0Spatrick       std::string SubstitutionStr = std::string(CmdlineDef);
266873471bf0Spatrick       SubstitutionStr[EqIdx] = ':';
266973471bf0Spatrick       CmdlineDefsIndices.push_back(
267073471bf0Spatrick           std::make_pair(CmdlineDefsDiag.size(), SubstitutionStr.size()));
267173471bf0Spatrick       CmdlineDefsDiag += (SubstitutionStr + Twine("]])\n")).str();
267273471bf0Spatrick     } else {
267373471bf0Spatrick       CmdlineDefsDiag += DefPrefix;
267473471bf0Spatrick       CmdlineDefsIndices.push_back(
267573471bf0Spatrick           std::make_pair(CmdlineDefsDiag.size(), CmdlineDef.size()));
267673471bf0Spatrick       CmdlineDefsDiag += (CmdlineDef + "\n").str();
267773471bf0Spatrick     }
267873471bf0Spatrick   }
267973471bf0Spatrick 
268073471bf0Spatrick   // Create a buffer with fake command line content in order to display
268173471bf0Spatrick   // parsing diagnostic with location information and point to the
268273471bf0Spatrick   // global definition with invalid syntax.
268373471bf0Spatrick   std::unique_ptr<MemoryBuffer> CmdLineDefsDiagBuffer =
268473471bf0Spatrick       MemoryBuffer::getMemBufferCopy(CmdlineDefsDiag, "Global defines");
268573471bf0Spatrick   StringRef CmdlineDefsDiagRef = CmdLineDefsDiagBuffer->getBuffer();
268673471bf0Spatrick   SM.AddNewSourceBuffer(std::move(CmdLineDefsDiagBuffer), SMLoc());
268773471bf0Spatrick 
268873471bf0Spatrick   for (std::pair<size_t, size_t> CmdlineDefIndices : CmdlineDefsIndices) {
268973471bf0Spatrick     StringRef CmdlineDef = CmdlineDefsDiagRef.substr(CmdlineDefIndices.first,
269073471bf0Spatrick                                                      CmdlineDefIndices.second);
269173471bf0Spatrick     if (CmdlineDef.empty()) {
269273471bf0Spatrick       Errs = joinErrors(
269373471bf0Spatrick           std::move(Errs),
269473471bf0Spatrick           ErrorDiagnostic::get(SM, CmdlineDef,
269573471bf0Spatrick                                "missing equal sign in global definition"));
269673471bf0Spatrick       continue;
269773471bf0Spatrick     }
269873471bf0Spatrick 
269973471bf0Spatrick     // Numeric variable definition.
270073471bf0Spatrick     if (CmdlineDef[0] == '#') {
270173471bf0Spatrick       // Now parse the definition both to check that the syntax is correct and
270273471bf0Spatrick       // to create the necessary class instance.
270373471bf0Spatrick       StringRef CmdlineDefExpr = CmdlineDef.substr(1);
2704*d415bd75Srobert       std::optional<NumericVariable *> DefinedNumericVariable;
270573471bf0Spatrick       Expected<std::unique_ptr<Expression>> ExpressionResult =
2706*d415bd75Srobert           Pattern::parseNumericSubstitutionBlock(CmdlineDefExpr,
2707*d415bd75Srobert                                                  DefinedNumericVariable, false,
2708*d415bd75Srobert                                                  std::nullopt, this, SM);
270973471bf0Spatrick       if (!ExpressionResult) {
271073471bf0Spatrick         Errs = joinErrors(std::move(Errs), ExpressionResult.takeError());
271173471bf0Spatrick         continue;
271273471bf0Spatrick       }
271373471bf0Spatrick       std::unique_ptr<Expression> Expression = std::move(*ExpressionResult);
271473471bf0Spatrick       // Now evaluate the expression whose value this variable should be set
271573471bf0Spatrick       // to, since the expression of a command-line variable definition should
271673471bf0Spatrick       // only use variables defined earlier on the command-line. If not, this
271773471bf0Spatrick       // is an error and we report it.
271873471bf0Spatrick       Expected<ExpressionValue> Value = Expression->getAST()->eval();
271973471bf0Spatrick       if (!Value) {
272073471bf0Spatrick         Errs = joinErrors(std::move(Errs), Value.takeError());
272173471bf0Spatrick         continue;
272273471bf0Spatrick       }
272373471bf0Spatrick 
272473471bf0Spatrick       assert(DefinedNumericVariable && "No variable defined");
272573471bf0Spatrick       (*DefinedNumericVariable)->setValue(*Value);
272673471bf0Spatrick 
272773471bf0Spatrick       // Record this variable definition.
272873471bf0Spatrick       GlobalNumericVariableTable[(*DefinedNumericVariable)->getName()] =
272973471bf0Spatrick           *DefinedNumericVariable;
273073471bf0Spatrick     } else {
273173471bf0Spatrick       // String variable definition.
273273471bf0Spatrick       std::pair<StringRef, StringRef> CmdlineNameVal = CmdlineDef.split('=');
273373471bf0Spatrick       StringRef CmdlineName = CmdlineNameVal.first;
273473471bf0Spatrick       StringRef OrigCmdlineName = CmdlineName;
273573471bf0Spatrick       Expected<Pattern::VariableProperties> ParseVarResult =
273673471bf0Spatrick           Pattern::parseVariable(CmdlineName, SM);
273773471bf0Spatrick       if (!ParseVarResult) {
273873471bf0Spatrick         Errs = joinErrors(std::move(Errs), ParseVarResult.takeError());
273973471bf0Spatrick         continue;
274073471bf0Spatrick       }
274173471bf0Spatrick       // Check that CmdlineName does not denote a pseudo variable is only
274273471bf0Spatrick       // composed of the parsed numeric variable. This catches cases like
274373471bf0Spatrick       // "FOO+2" in a "FOO+2=10" definition.
274473471bf0Spatrick       if (ParseVarResult->IsPseudo || !CmdlineName.empty()) {
274573471bf0Spatrick         Errs = joinErrors(std::move(Errs),
274673471bf0Spatrick                           ErrorDiagnostic::get(
274773471bf0Spatrick                               SM, OrigCmdlineName,
274873471bf0Spatrick                               "invalid name in string variable definition '" +
274973471bf0Spatrick                                   OrigCmdlineName + "'"));
275073471bf0Spatrick         continue;
275173471bf0Spatrick       }
275273471bf0Spatrick       StringRef Name = ParseVarResult->Name;
275373471bf0Spatrick 
275473471bf0Spatrick       // Detect collisions between string and numeric variables when the former
275573471bf0Spatrick       // is created later than the latter.
275673471bf0Spatrick       if (GlobalNumericVariableTable.find(Name) !=
275773471bf0Spatrick           GlobalNumericVariableTable.end()) {
275873471bf0Spatrick         Errs = joinErrors(std::move(Errs),
275973471bf0Spatrick                           ErrorDiagnostic::get(SM, Name,
276073471bf0Spatrick                                                "numeric variable with name '" +
276173471bf0Spatrick                                                    Name + "' already exists"));
276273471bf0Spatrick         continue;
276373471bf0Spatrick       }
276473471bf0Spatrick       GlobalVariableTable.insert(CmdlineNameVal);
276573471bf0Spatrick       // Mark the string variable as defined to detect collisions between
276673471bf0Spatrick       // string and numeric variables in defineCmdlineVariables when the latter
276773471bf0Spatrick       // is created later than the former. We cannot reuse GlobalVariableTable
276873471bf0Spatrick       // for this by populating it with an empty string since we would then
276973471bf0Spatrick       // lose the ability to detect the use of an undefined variable in
277073471bf0Spatrick       // match().
277173471bf0Spatrick       DefinedVariableTable[Name] = true;
277273471bf0Spatrick     }
277373471bf0Spatrick   }
277473471bf0Spatrick 
277573471bf0Spatrick   return Errs;
277673471bf0Spatrick }
277773471bf0Spatrick 
clearLocalVars()277873471bf0Spatrick void FileCheckPatternContext::clearLocalVars() {
277973471bf0Spatrick   SmallVector<StringRef, 16> LocalPatternVars, LocalNumericVars;
278073471bf0Spatrick   for (const StringMapEntry<StringRef> &Var : GlobalVariableTable)
278173471bf0Spatrick     if (Var.first()[0] != '$')
278273471bf0Spatrick       LocalPatternVars.push_back(Var.first());
278373471bf0Spatrick 
278473471bf0Spatrick   // Numeric substitution reads the value of a variable directly, not via
278573471bf0Spatrick   // GlobalNumericVariableTable. Therefore, we clear local variables by
278673471bf0Spatrick   // clearing their value which will lead to a numeric substitution failure. We
278773471bf0Spatrick   // also mark the variable for removal from GlobalNumericVariableTable since
278873471bf0Spatrick   // this is what defineCmdlineVariables checks to decide that no global
278973471bf0Spatrick   // variable has been defined.
279073471bf0Spatrick   for (const auto &Var : GlobalNumericVariableTable)
279173471bf0Spatrick     if (Var.first()[0] != '$') {
279273471bf0Spatrick       Var.getValue()->clearValue();
279373471bf0Spatrick       LocalNumericVars.push_back(Var.first());
279473471bf0Spatrick     }
279573471bf0Spatrick 
279673471bf0Spatrick   for (const auto &Var : LocalPatternVars)
279773471bf0Spatrick     GlobalVariableTable.erase(Var);
279873471bf0Spatrick   for (const auto &Var : LocalNumericVars)
279973471bf0Spatrick     GlobalNumericVariableTable.erase(Var);
280073471bf0Spatrick }
280173471bf0Spatrick 
checkInput(SourceMgr & SM,StringRef Buffer,std::vector<FileCheckDiag> * Diags)280273471bf0Spatrick bool FileCheck::checkInput(SourceMgr &SM, StringRef Buffer,
280373471bf0Spatrick                            std::vector<FileCheckDiag> *Diags) {
280473471bf0Spatrick   bool ChecksFailed = false;
280573471bf0Spatrick 
280673471bf0Spatrick   unsigned i = 0, j = 0, e = CheckStrings->size();
280773471bf0Spatrick   while (true) {
280873471bf0Spatrick     StringRef CheckRegion;
280973471bf0Spatrick     if (j == e) {
281073471bf0Spatrick       CheckRegion = Buffer;
281173471bf0Spatrick     } else {
281273471bf0Spatrick       const FileCheckString &CheckLabelStr = (*CheckStrings)[j];
281373471bf0Spatrick       if (CheckLabelStr.Pat.getCheckTy() != Check::CheckLabel) {
281473471bf0Spatrick         ++j;
281573471bf0Spatrick         continue;
281673471bf0Spatrick       }
281773471bf0Spatrick 
281873471bf0Spatrick       // Scan to next CHECK-LABEL match, ignoring CHECK-NOT and CHECK-DAG
281973471bf0Spatrick       size_t MatchLabelLen = 0;
282073471bf0Spatrick       size_t MatchLabelPos =
282173471bf0Spatrick           CheckLabelStr.Check(SM, Buffer, true, MatchLabelLen, Req, Diags);
282273471bf0Spatrick       if (MatchLabelPos == StringRef::npos)
282373471bf0Spatrick         // Immediately bail if CHECK-LABEL fails, nothing else we can do.
282473471bf0Spatrick         return false;
282573471bf0Spatrick 
282673471bf0Spatrick       CheckRegion = Buffer.substr(0, MatchLabelPos + MatchLabelLen);
282773471bf0Spatrick       Buffer = Buffer.substr(MatchLabelPos + MatchLabelLen);
282873471bf0Spatrick       ++j;
282973471bf0Spatrick     }
283073471bf0Spatrick 
283173471bf0Spatrick     // Do not clear the first region as it's the one before the first
283273471bf0Spatrick     // CHECK-LABEL and it would clear variables defined on the command-line
283373471bf0Spatrick     // before they get used.
283473471bf0Spatrick     if (i != 0 && Req.EnableVarScope)
283573471bf0Spatrick       PatternContext->clearLocalVars();
283673471bf0Spatrick 
283773471bf0Spatrick     for (; i != j; ++i) {
283873471bf0Spatrick       const FileCheckString &CheckStr = (*CheckStrings)[i];
283973471bf0Spatrick 
284073471bf0Spatrick       // Check each string within the scanned region, including a second check
284173471bf0Spatrick       // of any final CHECK-LABEL (to verify CHECK-NOT and CHECK-DAG)
284273471bf0Spatrick       size_t MatchLen = 0;
284373471bf0Spatrick       size_t MatchPos =
284473471bf0Spatrick           CheckStr.Check(SM, CheckRegion, false, MatchLen, Req, Diags);
284573471bf0Spatrick 
284673471bf0Spatrick       if (MatchPos == StringRef::npos) {
284773471bf0Spatrick         ChecksFailed = true;
284873471bf0Spatrick         i = j;
284973471bf0Spatrick         break;
285073471bf0Spatrick       }
285173471bf0Spatrick 
285273471bf0Spatrick       CheckRegion = CheckRegion.substr(MatchPos + MatchLen);
285373471bf0Spatrick     }
285473471bf0Spatrick 
285573471bf0Spatrick     if (j == e)
285673471bf0Spatrick       break;
285773471bf0Spatrick   }
285873471bf0Spatrick 
285973471bf0Spatrick   // Success if no checks failed.
286073471bf0Spatrick   return !ChecksFailed;
286173471bf0Spatrick }
2862