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