xref: /llvm-project/llvm/lib/FileCheck/FileCheckImpl.h (revision cf57fcfa0256df8d69638ab1462267413755ba86)
1 //===-- FileCheckImpl.h - Private FileCheck Interface ------------*- C++ -*-==//
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 // This file defines the private interfaces of FileCheck. Its purpose is to
10 // allow unit testing of FileCheck and to separate the interface from the
11 // implementation. It is only meant to be used by FileCheck.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_LIB_FILECHECK_FILECHECKIMPL_H
16 #define LLVM_LIB_FILECHECK_FILECHECKIMPL_H
17 
18 #include "llvm/ADT/APInt.h"
19 #include "llvm/ADT/StringMap.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/FileCheck/FileCheck.h"
22 #include "llvm/Support/Error.h"
23 #include "llvm/Support/SourceMgr.h"
24 #include <map>
25 #include <optional>
26 #include <string>
27 #include <vector>
28 
29 namespace llvm {
30 
31 //===----------------------------------------------------------------------===//
32 // Numeric substitution handling code.
33 //===----------------------------------------------------------------------===//
34 
35 class ExpressionValue;
36 
37 /// Type representing the format an expression value should be textualized into
38 /// for matching. Used to represent both explicit format specifiers as well as
39 /// implicit format from using numeric variables.
40 struct ExpressionFormat {
41   enum class Kind {
42     /// Denote absence of format. Used for implicit format of literals and
43     /// empty expressions.
44     NoFormat,
45     /// Value is an unsigned integer and should be printed as a decimal number.
46     Unsigned,
47     /// Value is a signed integer and should be printed as a decimal number.
48     Signed,
49     /// Value should be printed as an uppercase hex number.
50     HexUpper,
51     /// Value should be printed as a lowercase hex number.
52     HexLower
53   };
54 
55 private:
56   Kind Value;
57   unsigned Precision = 0;
58   /// printf-like "alternate form" selected.
59   bool AlternateForm = false;
60 
61 public:
62   /// Evaluates a format to true if it can be used in a match.
63   explicit operator bool() const { return Value != Kind::NoFormat; }
64 
65   /// Define format equality: formats are equal if neither is NoFormat and
66   /// their kinds and precision are the same.
67   bool operator==(const ExpressionFormat &Other) const {
68     return Value != Kind::NoFormat && Value == Other.Value &&
69            Precision == Other.Precision && AlternateForm == Other.AlternateForm;
70   }
71 
72   bool operator!=(const ExpressionFormat &Other) const {
73     return !(*this == Other);
74   }
75 
76   bool operator==(Kind OtherValue) const { return Value == OtherValue; }
77 
78   bool operator!=(Kind OtherValue) const { return !(*this == OtherValue); }
79 
80   /// \returns the format specifier corresponding to this format as a string.
81   StringRef toString() const;
82 
83   ExpressionFormat() : Value(Kind::NoFormat){};
84   explicit ExpressionFormat(Kind Value) : Value(Value), Precision(0){};
85   explicit ExpressionFormat(Kind Value, unsigned Precision)
86       : Value(Value), Precision(Precision){};
87   explicit ExpressionFormat(Kind Value, unsigned Precision, bool AlternateForm)
88       : Value(Value), Precision(Precision), AlternateForm(AlternateForm){};
89 
90   /// \returns a wildcard regular expression string that matches any value in
91   /// the format represented by this instance and no other value, or an error
92   /// if the format is NoFormat.
93   Expected<std::string> getWildcardRegex() const;
94 
95   /// \returns the string representation of \p Value in the format represented
96   /// by this instance, or an error if conversion to this format failed or the
97   /// format is NoFormat.
98   Expected<std::string> getMatchingString(ExpressionValue Value) const;
99 
100   /// \returns the value corresponding to string representation \p StrVal
101   /// according to the matching format represented by this instance or an error
102   /// with diagnostic against \p SM if \p StrVal does not correspond to a valid
103   /// and representable value.
104   Expected<ExpressionValue> valueFromStringRepr(StringRef StrVal,
105                                                 const SourceMgr &SM) const;
106 };
107 
108 /// Class to represent an overflow error that might result when manipulating a
109 /// value.
110 class OverflowError : public ErrorInfo<OverflowError> {
111 public:
112   static char ID;
113 
114   std::error_code convertToErrorCode() const override {
115     return std::make_error_code(std::errc::value_too_large);
116   }
117 
118   void log(raw_ostream &OS) const override { OS << "overflow error"; }
119 };
120 
121 /// Class representing a numeric value.
122 class ExpressionValue {
123 private:
124   APInt Value;
125 
126 public:
127   // Store signed and unsigned 64-bit integers in a signed 65-bit APInt.
128   template <class T>
129   explicit ExpressionValue(T Val) : Value(65, Val, /*isSigned=*/Val < 0) {}
130 
131   bool operator==(const ExpressionValue &Other) const {
132     return Value == Other.Value;
133   }
134 
135   bool operator!=(const ExpressionValue &Other) const {
136     return !(*this == Other);
137   }
138 
139   /// Returns true if value is signed and negative, false otherwise.
140   bool isNegative() const { return Value.isNegative(); }
141 
142   /// \returns the value as a signed integer or an error if the value is out of
143   /// range.
144   Expected<int64_t> getSignedValue() const;
145 
146   /// \returns the value as an unsigned integer or an error if the value is out
147   /// of range.
148   Expected<uint64_t> getUnsignedValue() const;
149 
150   /// \returns an unsigned ExpressionValue instance whose value is the absolute
151   /// value to this object's value.
152   ExpressionValue getAbsolute() const;
153 };
154 
155 /// Performs operation and \returns its result or an error in case of failure,
156 /// such as if an overflow occurs.
157 Expected<ExpressionValue> operator+(const ExpressionValue &Lhs,
158                                     const ExpressionValue &Rhs);
159 Expected<ExpressionValue> operator-(const ExpressionValue &Lhs,
160                                     const ExpressionValue &Rhs);
161 Expected<ExpressionValue> operator*(const ExpressionValue &Lhs,
162                                     const ExpressionValue &Rhs);
163 Expected<ExpressionValue> operator/(const ExpressionValue &Lhs,
164                                     const ExpressionValue &Rhs);
165 Expected<ExpressionValue> max(const ExpressionValue &Lhs,
166                               const ExpressionValue &Rhs);
167 Expected<ExpressionValue> min(const ExpressionValue &Lhs,
168                               const ExpressionValue &Rhs);
169 
170 /// Base class representing the AST of a given expression.
171 class ExpressionAST {
172 private:
173   StringRef ExpressionStr;
174 
175 public:
176   ExpressionAST(StringRef ExpressionStr) : ExpressionStr(ExpressionStr) {}
177 
178   virtual ~ExpressionAST() = default;
179 
180   StringRef getExpressionStr() const { return ExpressionStr; }
181 
182   /// Evaluates and \returns the value of the expression represented by this
183   /// AST or an error if evaluation fails.
184   virtual Expected<ExpressionValue> eval() const = 0;
185 
186   /// \returns either the implicit format of this AST, a diagnostic against
187   /// \p SM if implicit formats of the AST's components conflict, or NoFormat
188   /// if the AST has no implicit format (e.g. AST is made up of a single
189   /// literal).
190   virtual Expected<ExpressionFormat>
191   getImplicitFormat(const SourceMgr &SM) const {
192     return ExpressionFormat();
193   }
194 };
195 
196 /// Class representing an unsigned literal in the AST of an expression.
197 class ExpressionLiteral : public ExpressionAST {
198 private:
199   /// Actual value of the literal.
200   ExpressionValue Value;
201 
202 public:
203   template <class T>
204   explicit ExpressionLiteral(StringRef ExpressionStr, T Val)
205       : ExpressionAST(ExpressionStr), Value(Val) {}
206 
207   /// \returns the literal's value.
208   Expected<ExpressionValue> eval() const override { return Value; }
209 };
210 
211 /// Class to represent an undefined variable error, which quotes that
212 /// variable's name when printed.
213 class UndefVarError : public ErrorInfo<UndefVarError> {
214 private:
215   StringRef VarName;
216 
217 public:
218   static char ID;
219 
220   UndefVarError(StringRef VarName) : VarName(VarName) {}
221 
222   StringRef getVarName() const { return VarName; }
223 
224   std::error_code convertToErrorCode() const override {
225     return inconvertibleErrorCode();
226   }
227 
228   /// Print name of variable associated with this error.
229   void log(raw_ostream &OS) const override {
230     OS << "undefined variable: " << VarName;
231   }
232 };
233 
234 /// Class representing an expression and its matching format.
235 class Expression {
236 private:
237   /// Pointer to AST of the expression.
238   std::unique_ptr<ExpressionAST> AST;
239 
240   /// Format to use (e.g. hex upper case letters) when matching the value.
241   ExpressionFormat Format;
242 
243 public:
244   /// Generic constructor for an expression represented by the given \p AST and
245   /// whose matching format is \p Format.
246   Expression(std::unique_ptr<ExpressionAST> AST, ExpressionFormat Format)
247       : AST(std::move(AST)), Format(Format) {}
248 
249   /// \returns pointer to AST of the expression. Pointer is guaranteed to be
250   /// valid as long as this object is.
251   ExpressionAST *getAST() const { return AST.get(); }
252 
253   ExpressionFormat getFormat() const { return Format; }
254 };
255 
256 /// Class representing a numeric variable and its associated current value.
257 class NumericVariable {
258 private:
259   /// Name of the numeric variable.
260   StringRef Name;
261 
262   /// Format to use for expressions using this variable without an explicit
263   /// format.
264   ExpressionFormat ImplicitFormat;
265 
266   /// Value of numeric variable, if defined, or std::nullopt otherwise.
267   std::optional<ExpressionValue> Value;
268 
269   /// The input buffer's string from which Value was parsed, or std::nullopt.
270   /// See comments on getStringValue for a discussion of the std::nullopt case.
271   std::optional<StringRef> StrValue;
272 
273   /// Line number where this variable is defined, or std::nullopt if defined
274   /// before input is parsed. Used to determine whether a variable is defined on
275   /// the same line as a given use.
276   std::optional<size_t> DefLineNumber;
277 
278 public:
279   /// Constructor for a variable \p Name with implicit format \p ImplicitFormat
280   /// defined at line \p DefLineNumber or defined before input is parsed if
281   /// \p DefLineNumber is std::nullopt.
282   explicit NumericVariable(StringRef Name, ExpressionFormat ImplicitFormat,
283                            std::optional<size_t> DefLineNumber = std::nullopt)
284       : Name(Name), ImplicitFormat(ImplicitFormat),
285         DefLineNumber(DefLineNumber) {}
286 
287   /// \returns name of this numeric variable.
288   StringRef getName() const { return Name; }
289 
290   /// \returns implicit format of this numeric variable.
291   ExpressionFormat getImplicitFormat() const { return ImplicitFormat; }
292 
293   /// \returns this variable's value.
294   std::optional<ExpressionValue> getValue() const { return Value; }
295 
296   /// \returns the input buffer's string from which this variable's value was
297   /// parsed, or std::nullopt if the value is not yet defined or was not parsed
298   /// from the input buffer.  For example, the value of @LINE is not parsed from
299   /// the input buffer, and some numeric variables are parsed from the command
300   /// line instead.
301   std::optional<StringRef> getStringValue() const { return StrValue; }
302 
303   /// Sets value of this numeric variable to \p NewValue, and sets the input
304   /// buffer string from which it was parsed to \p NewStrValue.  See comments on
305   /// getStringValue for a discussion of when the latter can be std::nullopt.
306   void setValue(ExpressionValue NewValue,
307                 std::optional<StringRef> NewStrValue = std::nullopt) {
308     Value = NewValue;
309     StrValue = NewStrValue;
310   }
311 
312   /// Clears value of this numeric variable, regardless of whether it is
313   /// currently defined or not.
314   void clearValue() {
315     Value = std::nullopt;
316     StrValue = std::nullopt;
317   }
318 
319   /// \returns the line number where this variable is defined, if any, or
320   /// std::nullopt if defined before input is parsed.
321   std::optional<size_t> getDefLineNumber() const { return DefLineNumber; }
322 };
323 
324 /// Class representing the use of a numeric variable in the AST of an
325 /// expression.
326 class NumericVariableUse : public ExpressionAST {
327 private:
328   /// Pointer to the class instance for the variable this use is about.
329   NumericVariable *Variable;
330 
331 public:
332   NumericVariableUse(StringRef Name, NumericVariable *Variable)
333       : ExpressionAST(Name), Variable(Variable) {}
334   /// \returns the value of the variable referenced by this instance.
335   Expected<ExpressionValue> eval() const override;
336 
337   /// \returns implicit format of this numeric variable.
338   Expected<ExpressionFormat>
339   getImplicitFormat(const SourceMgr &SM) const override {
340     return Variable->getImplicitFormat();
341   }
342 };
343 
344 /// Type of functions evaluating a given binary operation.
345 using binop_eval_t = Expected<ExpressionValue> (*)(const ExpressionValue &,
346                                                    const ExpressionValue &);
347 
348 /// Class representing a single binary operation in the AST of an expression.
349 class BinaryOperation : public ExpressionAST {
350 private:
351   /// Left operand.
352   std::unique_ptr<ExpressionAST> LeftOperand;
353 
354   /// Right operand.
355   std::unique_ptr<ExpressionAST> RightOperand;
356 
357   /// Pointer to function that can evaluate this binary operation.
358   binop_eval_t EvalBinop;
359 
360 public:
361   BinaryOperation(StringRef ExpressionStr, binop_eval_t EvalBinop,
362                   std::unique_ptr<ExpressionAST> LeftOp,
363                   std::unique_ptr<ExpressionAST> RightOp)
364       : ExpressionAST(ExpressionStr), EvalBinop(EvalBinop) {
365     LeftOperand = std::move(LeftOp);
366     RightOperand = std::move(RightOp);
367   }
368 
369   /// Evaluates the value of the binary operation represented by this AST,
370   /// using EvalBinop on the result of recursively evaluating the operands.
371   /// \returns the expression value or an error if an undefined numeric
372   /// variable is used in one of the operands.
373   Expected<ExpressionValue> eval() const override;
374 
375   /// \returns the implicit format of this AST, if any, a diagnostic against
376   /// \p SM if the implicit formats of the AST's components conflict, or no
377   /// format if the AST has no implicit format (e.g. AST is made of a single
378   /// literal).
379   Expected<ExpressionFormat>
380   getImplicitFormat(const SourceMgr &SM) const override;
381 };
382 
383 class FileCheckPatternContext;
384 
385 /// Class representing a substitution to perform in the RegExStr string.
386 class Substitution {
387 protected:
388   /// Pointer to a class instance holding, among other things, the table with
389   /// the values of live string variables at the start of any given CHECK line.
390   /// Used for substituting string variables with the text they were defined
391   /// as. Expressions are linked to the numeric variables they use at
392   /// parse time and directly access the value of the numeric variable to
393   /// evaluate their value.
394   FileCheckPatternContext *Context;
395 
396   /// The string that needs to be substituted for something else. For a
397   /// string variable this is its name, otherwise this is the whole expression.
398   StringRef FromStr;
399 
400   // Index in RegExStr of where to do the substitution.
401   size_t InsertIdx;
402 
403 public:
404   Substitution(FileCheckPatternContext *Context, StringRef VarName,
405                size_t InsertIdx)
406       : Context(Context), FromStr(VarName), InsertIdx(InsertIdx) {}
407 
408   virtual ~Substitution() = default;
409 
410   /// \returns the string to be substituted for something else.
411   StringRef getFromString() const { return FromStr; }
412 
413   /// \returns the index where the substitution is to be performed in RegExStr.
414   size_t getIndex() const { return InsertIdx; }
415 
416   /// \returns a string containing the result of the substitution represented
417   /// by this class instance or an error if substitution failed.
418   virtual Expected<std::string> getResult() const = 0;
419 };
420 
421 class StringSubstitution : public Substitution {
422 public:
423   StringSubstitution(FileCheckPatternContext *Context, StringRef VarName,
424                      size_t InsertIdx)
425       : Substitution(Context, VarName, InsertIdx) {}
426 
427   /// \returns the text that the string variable in this substitution matched
428   /// when defined, or an error if the variable is undefined.
429   Expected<std::string> getResult() const override;
430 };
431 
432 class NumericSubstitution : public Substitution {
433 private:
434   /// Pointer to the class representing the expression whose value is to be
435   /// substituted.
436   std::unique_ptr<Expression> ExpressionPointer;
437 
438 public:
439   NumericSubstitution(FileCheckPatternContext *Context, StringRef ExpressionStr,
440                       std::unique_ptr<Expression> ExpressionPointer,
441                       size_t InsertIdx)
442       : Substitution(Context, ExpressionStr, InsertIdx),
443         ExpressionPointer(std::move(ExpressionPointer)) {}
444 
445   /// \returns a string containing the result of evaluating the expression in
446   /// this substitution, or an error if evaluation failed.
447   Expected<std::string> getResult() const override;
448 };
449 
450 //===----------------------------------------------------------------------===//
451 // Pattern handling code.
452 //===----------------------------------------------------------------------===//
453 
454 /// Class holding the Pattern global state, shared by all patterns: tables
455 /// holding values of variables and whether they are defined or not at any
456 /// given time in the matching process.
457 class FileCheckPatternContext {
458   friend class Pattern;
459 
460 private:
461   /// When matching a given pattern, this holds the value of all the string
462   /// variables defined in previous patterns. In a pattern, only the last
463   /// definition for a given variable is recorded in this table.
464   /// Back-references are used for uses after any the other definition.
465   StringMap<StringRef> GlobalVariableTable;
466 
467   /// Map of all string variables defined so far. Used at parse time to detect
468   /// a name conflict between a numeric variable and a string variable when
469   /// the former is defined on a later line than the latter.
470   StringMap<bool> DefinedVariableTable;
471 
472   /// When matching a given pattern, this holds the pointers to the classes
473   /// representing the numeric variables defined in previous patterns. When
474   /// matching a pattern all definitions for that pattern are recorded in the
475   /// NumericVariableDefs table in the Pattern instance of that pattern.
476   StringMap<NumericVariable *> GlobalNumericVariableTable;
477 
478   /// Pointer to the class instance representing the @LINE pseudo variable for
479   /// easily updating its value.
480   NumericVariable *LineVariable = nullptr;
481 
482   /// Vector holding pointers to all parsed numeric variables. Used to
483   /// automatically free them once they are guaranteed to no longer be used.
484   std::vector<std::unique_ptr<NumericVariable>> NumericVariables;
485 
486   /// Vector holding pointers to all parsed expressions. Used to automatically
487   /// free the expressions once they are guaranteed to no longer be used.
488   std::vector<std::unique_ptr<Expression>> Expressions;
489 
490   /// Vector holding pointers to all substitutions. Used to automatically free
491   /// them once they are guaranteed to no longer be used.
492   std::vector<std::unique_ptr<Substitution>> Substitutions;
493 
494 public:
495   /// \returns the value of string variable \p VarName or an error if no such
496   /// variable has been defined.
497   Expected<StringRef> getPatternVarValue(StringRef VarName);
498 
499   /// Defines string and numeric variables from definitions given on the
500   /// command line, passed as a vector of [#]VAR=VAL strings in
501   /// \p CmdlineDefines. \returns an error list containing diagnostics against
502   /// \p SM for all definition parsing failures, if any, or Success otherwise.
503   Error defineCmdlineVariables(ArrayRef<StringRef> CmdlineDefines,
504                                SourceMgr &SM);
505 
506   /// Create @LINE pseudo variable. Value is set when pattern are being
507   /// matched.
508   void createLineVariable();
509 
510   /// Undefines local variables (variables whose name does not start with a '$'
511   /// sign), i.e. removes them from GlobalVariableTable and from
512   /// GlobalNumericVariableTable and also clears the value of numeric
513   /// variables.
514   void clearLocalVars();
515 
516 private:
517   /// Makes a new numeric variable and registers it for destruction when the
518   /// context is destroyed.
519   template <class... Types> NumericVariable *makeNumericVariable(Types... args);
520 
521   /// Makes a new string substitution and registers it for destruction when the
522   /// context is destroyed.
523   Substitution *makeStringSubstitution(StringRef VarName, size_t InsertIdx);
524 
525   /// Makes a new numeric substitution and registers it for destruction when
526   /// the context is destroyed.
527   Substitution *makeNumericSubstitution(StringRef ExpressionStr,
528                                         std::unique_ptr<Expression> Expression,
529                                         size_t InsertIdx);
530 };
531 
532 /// Class to represent an error holding a diagnostic with location information
533 /// used when printing it.
534 class ErrorDiagnostic : public ErrorInfo<ErrorDiagnostic> {
535 private:
536   SMDiagnostic Diagnostic;
537   SMRange Range;
538 
539 public:
540   static char ID;
541 
542   ErrorDiagnostic(SMDiagnostic &&Diag, SMRange Range)
543       : Diagnostic(Diag), Range(Range) {}
544 
545   std::error_code convertToErrorCode() const override {
546     return inconvertibleErrorCode();
547   }
548 
549   /// Print diagnostic associated with this error when printing the error.
550   void log(raw_ostream &OS) const override { Diagnostic.print(nullptr, OS); }
551 
552   StringRef getMessage() const { return Diagnostic.getMessage(); }
553   SMRange getRange() const { return Range; }
554 
555   static Error get(const SourceMgr &SM, SMLoc Loc, const Twine &ErrMsg,
556                    SMRange Range = std::nullopt) {
557     return make_error<ErrorDiagnostic>(
558         SM.GetMessage(Loc, SourceMgr::DK_Error, ErrMsg), Range);
559   }
560 
561   static Error get(const SourceMgr &SM, StringRef Buffer, const Twine &ErrMsg) {
562     SMLoc Start = SMLoc::getFromPointer(Buffer.data());
563     SMLoc End = SMLoc::getFromPointer(Buffer.data() + Buffer.size());
564     return get(SM, Start, ErrMsg, SMRange(Start, End));
565   }
566 };
567 
568 class NotFoundError : public ErrorInfo<NotFoundError> {
569 public:
570   static char ID;
571 
572   std::error_code convertToErrorCode() const override {
573     return inconvertibleErrorCode();
574   }
575 
576   /// Print diagnostic associated with this error when printing the error.
577   void log(raw_ostream &OS) const override {
578     OS << "String not found in input";
579   }
580 };
581 
582 /// An error that has already been reported.
583 ///
584 /// This class is designed to support a function whose callers may need to know
585 /// whether the function encountered and reported an error but never need to
586 /// know the nature of that error.  For example, the function has a return type
587 /// of \c Error and always returns either \c ErrorReported or \c ErrorSuccess.
588 /// That interface is similar to that of a function returning bool to indicate
589 /// an error except, in the former case, (1) there is no confusion over polarity
590 /// and (2) the caller must either check the result or explicitly ignore it with
591 /// a call like \c consumeError.
592 class ErrorReported final : public ErrorInfo<ErrorReported> {
593 public:
594   static char ID;
595 
596   std::error_code convertToErrorCode() const override {
597     return inconvertibleErrorCode();
598   }
599 
600   /// Print diagnostic associated with this error when printing the error.
601   void log(raw_ostream &OS) const override {
602     OS << "error previously reported";
603   }
604 
605   static inline Error reportedOrSuccess(bool HasErrorReported) {
606     if (HasErrorReported)
607       return make_error<ErrorReported>();
608     return Error::success();
609   }
610 };
611 
612 class Pattern {
613   SMLoc PatternLoc;
614 
615   /// A fixed string to match as the pattern or empty if this pattern requires
616   /// a regex match.
617   StringRef FixedStr;
618 
619   /// A regex string to match as the pattern or empty if this pattern requires
620   /// a fixed string to match.
621   std::string RegExStr;
622 
623   /// Entries in this vector represent a substitution of a string variable or
624   /// an expression in the RegExStr regex at match time. For example, in the
625   /// case of a CHECK directive with the pattern "foo[[bar]]baz[[#N+1]]",
626   /// RegExStr will contain "foobaz" and we'll get two entries in this vector
627   /// that tells us to insert the value of string variable "bar" at offset 3
628   /// and the value of expression "N+1" at offset 6.
629   std::vector<Substitution *> Substitutions;
630 
631   /// Maps names of string variables defined in a pattern to the number of
632   /// their parenthesis group in RegExStr capturing their last definition.
633   ///
634   /// E.g. for the pattern "foo[[bar:.*]]baz([[bar]][[QUUX]][[bar:.*]])",
635   /// RegExStr will be "foo(.*)baz(\1<quux value>(.*))" where <quux value> is
636   /// the value captured for QUUX on the earlier line where it was defined, and
637   /// VariableDefs will map "bar" to the third parenthesis group which captures
638   /// the second definition of "bar".
639   ///
640   /// Note: uses std::map rather than StringMap to be able to get the key when
641   /// iterating over values.
642   std::map<StringRef, unsigned> VariableDefs;
643 
644   /// Structure representing the definition of a numeric variable in a pattern.
645   /// It holds the pointer to the class instance holding the value and matching
646   /// format of the numeric variable whose value is being defined and the
647   /// number of the parenthesis group in RegExStr to capture that value.
648   struct NumericVariableMatch {
649     /// Pointer to class instance holding the value and matching format of the
650     /// numeric variable being defined.
651     NumericVariable *DefinedNumericVariable;
652 
653     /// Number of the parenthesis group in RegExStr that captures the value of
654     /// this numeric variable definition.
655     unsigned CaptureParenGroup;
656   };
657 
658   /// Holds the number of the parenthesis group in RegExStr and pointer to the
659   /// corresponding NumericVariable class instance of all numeric variable
660   /// definitions. Used to set the matched value of all those variables.
661   StringMap<NumericVariableMatch> NumericVariableDefs;
662 
663   /// Pointer to a class instance holding the global state shared by all
664   /// patterns:
665   /// - separate tables with the values of live string and numeric variables
666   ///   respectively at the start of any given CHECK line;
667   /// - table holding whether a string variable has been defined at any given
668   ///   point during the parsing phase.
669   FileCheckPatternContext *Context;
670 
671   Check::FileCheckType CheckTy;
672 
673   /// Line number for this CHECK pattern or std::nullopt if it is an implicit
674   /// pattern. Used to determine whether a variable definition is made on an
675   /// earlier line to the one with this CHECK.
676   std::optional<size_t> LineNumber;
677 
678   /// Ignore case while matching if set to true.
679   bool IgnoreCase = false;
680 
681 public:
682   Pattern(Check::FileCheckType Ty, FileCheckPatternContext *Context,
683           std::optional<size_t> Line = std::nullopt)
684       : Context(Context), CheckTy(Ty), LineNumber(Line) {}
685 
686   /// \returns the location in source code.
687   SMLoc getLoc() const { return PatternLoc; }
688 
689   /// \returns the pointer to the global state for all patterns in this
690   /// FileCheck instance.
691   FileCheckPatternContext *getContext() const { return Context; }
692 
693   /// \returns whether \p C is a valid first character for a variable name.
694   static bool isValidVarNameStart(char C);
695 
696   /// Parsing information about a variable.
697   struct VariableProperties {
698     StringRef Name;
699     bool IsPseudo;
700   };
701 
702   /// Parses the string at the start of \p Str for a variable name. \returns
703   /// a VariableProperties structure holding the variable name and whether it
704   /// is the name of a pseudo variable, or an error holding a diagnostic
705   /// against \p SM if parsing fail. If parsing was successful, also strips
706   /// \p Str from the variable name.
707   static Expected<VariableProperties> parseVariable(StringRef &Str,
708                                                     const SourceMgr &SM);
709   /// Parses \p Expr for a numeric substitution block at line \p LineNumber,
710   /// or before input is parsed if \p LineNumber is None. Parameter
711   /// \p IsLegacyLineExpr indicates whether \p Expr should be a legacy @LINE
712   /// expression and \p Context points to the class instance holding the live
713   /// string and numeric variables. \returns a pointer to the class instance
714   /// representing the expression whose value must be substitued, or an error
715   /// holding a diagnostic against \p SM if parsing fails. If substitution was
716   /// successful, sets \p DefinedNumericVariable to point to the class
717   /// representing the numeric variable defined in this numeric substitution
718   /// block, or std::nullopt if this block does not define any variable.
719   static Expected<std::unique_ptr<Expression>> parseNumericSubstitutionBlock(
720       StringRef Expr, std::optional<NumericVariable *> &DefinedNumericVariable,
721       bool IsLegacyLineExpr, std::optional<size_t> LineNumber,
722       FileCheckPatternContext *Context, const SourceMgr &SM);
723   /// Parses the pattern in \p PatternStr and initializes this Pattern instance
724   /// accordingly.
725   ///
726   /// \p Prefix provides which prefix is being matched, \p Req describes the
727   /// global options that influence the parsing such as whitespace
728   /// canonicalization, \p SM provides the SourceMgr used for error reports.
729   /// \returns true in case of an error, false otherwise.
730   bool parsePattern(StringRef PatternStr, StringRef Prefix, SourceMgr &SM,
731                     const FileCheckRequest &Req);
732   struct Match {
733     size_t Pos;
734     size_t Len;
735   };
736   struct MatchResult {
737     std::optional<Match> TheMatch;
738     Error TheError;
739     MatchResult(size_t MatchPos, size_t MatchLen, Error E)
740         : TheMatch(Match{MatchPos, MatchLen}), TheError(std::move(E)) {}
741     MatchResult(Match M, Error E) : TheMatch(M), TheError(std::move(E)) {}
742     MatchResult(Error E) : TheError(std::move(E)) {}
743   };
744   /// Matches the pattern string against the input buffer \p Buffer.
745   ///
746   /// \returns either (1) an error resulting in no match or (2) a match possibly
747   /// with an error encountered while processing the match.
748   ///
749   /// The GlobalVariableTable StringMap in the FileCheckPatternContext class
750   /// instance provides the current values of FileCheck string variables and is
751   /// updated if this match defines new values. Likewise, the
752   /// GlobalNumericVariableTable StringMap in the same class provides the
753   /// current values of FileCheck numeric variables and is updated if this
754   /// match defines new numeric values.
755   MatchResult match(StringRef Buffer, const SourceMgr &SM) const;
756   /// Prints the value of successful substitutions.
757   void printSubstitutions(const SourceMgr &SM, StringRef Buffer,
758                           SMRange MatchRange, FileCheckDiag::MatchType MatchTy,
759                           std::vector<FileCheckDiag> *Diags) const;
760   void printFuzzyMatch(const SourceMgr &SM, StringRef Buffer,
761                        std::vector<FileCheckDiag> *Diags) const;
762 
763   bool hasVariable() const {
764     return !(Substitutions.empty() && VariableDefs.empty());
765   }
766   void printVariableDefs(const SourceMgr &SM, FileCheckDiag::MatchType MatchTy,
767                          std::vector<FileCheckDiag> *Diags) const;
768 
769   Check::FileCheckType getCheckTy() const { return CheckTy; }
770 
771   int getCount() const { return CheckTy.getCount(); }
772 
773 private:
774   bool AddRegExToRegEx(StringRef RS, unsigned &CurParen, SourceMgr &SM);
775   void AddBackrefToRegEx(unsigned BackrefNum);
776   /// Computes an arbitrary estimate for the quality of matching this pattern
777   /// at the start of \p Buffer; a distance of zero should correspond to a
778   /// perfect match.
779   unsigned computeMatchDistance(StringRef Buffer) const;
780   /// Finds the closing sequence of a regex variable usage or definition.
781   ///
782   /// \p Str has to point in the beginning of the definition (right after the
783   /// opening sequence). \p SM holds the SourceMgr used for error reporting.
784   ///  \returns the offset of the closing sequence within Str, or npos if it
785   /// was not found.
786   static size_t FindRegexVarEnd(StringRef Str, SourceMgr &SM);
787 
788   /// Parses \p Expr for the name of a numeric variable to be defined at line
789   /// \p LineNumber, or before input is parsed if \p LineNumber is None.
790   /// \returns a pointer to the class instance representing that variable,
791   /// creating it if needed, or an error holding a diagnostic against \p SM
792   /// should defining such a variable be invalid.
793   static Expected<NumericVariable *> parseNumericVariableDefinition(
794       StringRef &Expr, FileCheckPatternContext *Context,
795       std::optional<size_t> LineNumber, ExpressionFormat ImplicitFormat,
796       const SourceMgr &SM);
797   /// Parses \p Name as a (pseudo if \p IsPseudo is true) numeric variable use
798   /// at line \p LineNumber, or before input is parsed if \p LineNumber is
799   /// None. Parameter \p Context points to the class instance holding the live
800   /// string and numeric variables. \returns the pointer to the class instance
801   /// representing that variable if successful, or an error holding a
802   /// diagnostic against \p SM otherwise.
803   static Expected<std::unique_ptr<NumericVariableUse>> parseNumericVariableUse(
804       StringRef Name, bool IsPseudo, std::optional<size_t> LineNumber,
805       FileCheckPatternContext *Context, const SourceMgr &SM);
806   enum class AllowedOperand { LineVar, LegacyLiteral, Any };
807   /// Parses \p Expr for use of a numeric operand at line \p LineNumber, or
808   /// before input is parsed if \p LineNumber is None. Accepts literal values,
809   /// numeric variables and function calls, depending on the value of \p AO.
810   /// \p MaybeInvalidConstraint indicates whether the text being parsed could
811   /// be an invalid constraint. \p Context points to the class instance holding
812   /// the live string and numeric variables. \returns the class representing
813   /// that operand in the AST of the expression or an error holding a
814   /// diagnostic against \p SM otherwise. If \p Expr starts with a "(" this
815   /// function will attempt to parse a parenthesized expression.
816   static Expected<std::unique_ptr<ExpressionAST>>
817   parseNumericOperand(StringRef &Expr, AllowedOperand AO, bool ConstraintParsed,
818                       std::optional<size_t> LineNumber,
819                       FileCheckPatternContext *Context, const SourceMgr &SM);
820   /// Parses and updates \p RemainingExpr for a binary operation at line
821   /// \p LineNumber, or before input is parsed if \p LineNumber is None. The
822   /// left operand of this binary operation is given in \p LeftOp and \p Expr
823   /// holds the string for the full expression, including the left operand.
824   /// Parameter \p IsLegacyLineExpr indicates whether we are parsing a legacy
825   /// @LINE expression. Parameter \p Context points to the class instance
826   /// holding the live string and numeric variables. \returns the class
827   /// representing the binary operation in the AST of the expression, or an
828   /// error holding a diagnostic against \p SM otherwise.
829   static Expected<std::unique_ptr<ExpressionAST>>
830   parseBinop(StringRef Expr, StringRef &RemainingExpr,
831              std::unique_ptr<ExpressionAST> LeftOp, bool IsLegacyLineExpr,
832              std::optional<size_t> LineNumber, FileCheckPatternContext *Context,
833              const SourceMgr &SM);
834 
835   /// Parses a parenthesized expression inside \p Expr at line \p LineNumber, or
836   /// before input is parsed if \p LineNumber is None. \p Expr must start with
837   /// a '('. Accepts both literal values and numeric variables. Parameter \p
838   /// Context points to the class instance holding the live string and numeric
839   /// variables. \returns the class representing that operand in the AST of the
840   /// expression or an error holding a diagnostic against \p SM otherwise.
841   static Expected<std::unique_ptr<ExpressionAST>>
842   parseParenExpr(StringRef &Expr, std::optional<size_t> LineNumber,
843                  FileCheckPatternContext *Context, const SourceMgr &SM);
844 
845   /// Parses \p Expr for an argument list belonging to a call to function \p
846   /// FuncName at line \p LineNumber, or before input is parsed if \p LineNumber
847   /// is None. Parameter \p FuncLoc is the source location used for diagnostics.
848   /// Parameter \p Context points to the class instance holding the live string
849   /// and numeric variables. \returns the class representing that call in the
850   /// AST of the expression or an error holding a diagnostic against \p SM
851   /// otherwise.
852   static Expected<std::unique_ptr<ExpressionAST>>
853   parseCallExpr(StringRef &Expr, StringRef FuncName,
854                 std::optional<size_t> LineNumber,
855                 FileCheckPatternContext *Context, const SourceMgr &SM);
856 };
857 
858 //===----------------------------------------------------------------------===//
859 // Check Strings.
860 //===----------------------------------------------------------------------===//
861 
862 /// A check that we found in the input file.
863 struct FileCheckString {
864   /// The pattern to match.
865   Pattern Pat;
866 
867   /// Which prefix name this check matched.
868   StringRef Prefix;
869 
870   /// The location in the match file that the check string was specified.
871   SMLoc Loc;
872 
873   /// All of the strings that are disallowed from occurring between this match
874   /// string and the previous one (or start of file).
875   std::vector<Pattern> DagNotStrings;
876 
877   FileCheckString(const Pattern &P, StringRef S, SMLoc L)
878       : Pat(P), Prefix(S), Loc(L) {}
879 
880   /// Matches check string and its "not strings" and/or "dag strings".
881   size_t Check(const SourceMgr &SM, StringRef Buffer, bool IsLabelScanMode,
882                size_t &MatchLen, FileCheckRequest &Req,
883                std::vector<FileCheckDiag> *Diags) const;
884 
885   /// Verifies that there is a single line in the given \p Buffer. Errors are
886   /// reported against \p SM.
887   bool CheckNext(const SourceMgr &SM, StringRef Buffer) const;
888   /// Verifies that there is no newline in the given \p Buffer. Errors are
889   /// reported against \p SM.
890   bool CheckSame(const SourceMgr &SM, StringRef Buffer) const;
891   /// Verifies that none of the strings in \p NotStrings are found in the given
892   /// \p Buffer. Errors are reported against \p SM and diagnostics recorded in
893   /// \p Diags according to the verbosity level set in \p Req.
894   bool CheckNot(const SourceMgr &SM, StringRef Buffer,
895                 const std::vector<const Pattern *> &NotStrings,
896                 const FileCheckRequest &Req,
897                 std::vector<FileCheckDiag> *Diags) const;
898   /// Matches "dag strings" and their mixed "not strings".
899   size_t CheckDag(const SourceMgr &SM, StringRef Buffer,
900                   std::vector<const Pattern *> &NotStrings,
901                   const FileCheckRequest &Req,
902                   std::vector<FileCheckDiag> *Diags) const;
903 };
904 
905 } // namespace llvm
906 
907 #endif
908