[FileCheck] Allow parenthesized expressions

[arichardson]

Summary

With this change it is be possible to write FileCheck expressions such
as #(VAR+1)-2. Currently, the only supported arithmetic operators are
plus and minus, so this is not particularly useful yet. However, it our
CHERI fork we have tests that benefit from having multiplication in
FileCheck expressions. Allowing parenthesized expressions is the simplest
way for us to work around the current lack of operator precedence in
FileCheck expressions.

[thopre]

Should there be some tests under llvm/test/FileCheck as well? Perhaps in numeric-expressions.txt?

llvm/lib/Support/FileCheckImpl.h

662–669

Maybe mentions parenthesized expression here?

[jhenderson]

Thanks for this. I think this is a good step in the right direction for FileCheck's numeric expression support. You should probably add something to the FileCheck documentation about operator precedence and also using parentheses.

llvm/unittests/Support/FileCheckTest.cpp

747

Do you think it might make sense for a test case for more closing parentheses than opening ones? E.g. ")" or "())" or maybe even "())("?

Perhaps also something like "(1)(2)" and "2(X)" too with no operation between the operands?

[arichardson]

• rebase on latest master
• add suggested test checks
• Mention parenthesized expressions in FileCheck.rst

[arichardson]

I haven't added tests to numeric-expressions.txt in this revision. Do you think the unit tests are sufficient?

[thopre]

In D77383#2055076, @arichardson wrote:

I haven't added tests to numeric-expressions.txt in this revision. Do you think the unit tests are sufficient?

Yes to test end-to-end. I think 2 tests would be enough: (i) one positive and one negative test. No need to repeat all the variants of positive and negative tests that you did in the unit test.

[jhenderson]

LGTM, with a few nits and once thopre's comments have been addressed. Approving now as I'm off tomorrow, so if you get them done before I'm back, I don't want to hold things up.

llvm/docs/CommandGuide/FileCheck.rst

697

This sentence reads slightly clunkily to me. How about "however, parentheses" -> "but"?

llvm/lib/Support/FileCheckImpl.h

668

Shouldn't it be \p Expr?

llvm/unittests/Support/FileCheckTest.cpp

755–756

If you plan on improving the situation, perhaps move the second sentence to a TODO comment on the next line.

[arichardson]

• add numeric-expression.txt test

[arichardson]

• Address latest review comments

[arichardson]

llvm/unittests/Support/FileCheckTest.cpp

755–756

I don't have any immediate plans since I have lots of other things on my TODO list.

[jhenderson]

llvm/test/FileCheck/numeric-expression.txt

167 ↗

(On Diff #266458)

Nit: too many blank lines

179–180 ↗

(On Diff #266458)

Are you able to put these on the same lines as the value themselves, like in the other examples above?

PAREN EXPRESSIONS: // PAREN-OP-LABEL: PAREN EXPRESSIONS
11 // PAREN-OP-NEXT: [[#(NUMVAR+2)-1]]
11 // PAREN-OP-NEXT: [[#NUMVAR+(2-1)]]

[arichardson]

• improve test.

[arichardson]

• really fix test

[jhenderson]

LGTM. as before.

[thopre]

LGTM, thanks! I'll adapt the testcase once there's signed values to show precedence by using a variable using max uint64_t and once there's multiplication operand we can use that instead.

llvm/docs/CommandGuide/FileCheck.rst

* ``<expr>`` is an expression. An expression is in turn recursively defined
   as:
 
   * a numeric operand, or
   * an expression followed by an operator and a numeric operand.
 
   A numeric operand is a previously defined numeric variable, or an integer
   literal. The supported operators are ``+`` and ``-``. Spaces are accepted
   before, after and between any of these elements.
+  There is currently no support for operator precendence, however, parentheses
+  can be used to change the evaluation order.
 
 For example:
 
 .. code-block:: llvm
 
     ; CHECK: load r[[#REG:]], [r0]
     ; CHECK: load r[[#REG+1]], [r1]
     ; CHECK: Loading from 0x[[#%x,ADDR:]]

llvm/lib/Support/FileCheck.cpp

return ErrorDiagnostic::get(
             "' defined earlier in the same CHECK directive");
 
   return std::make_unique<NumericVariableUse>(Name, NumericVariable);
 }
 
 Expected<std::unique_ptr<ExpressionAST>> Pattern::parseNumericOperand(
     StringRef &Expr, AllowedOperand AO, Optional<size_t> LineNumber,
     FileCheckPatternContext *Context, const SourceMgr &SM) {
+  if (Expr.startswith("(")) {
+    if (AO != AllowedOperand::Any)
+      return ErrorDiagnostic::get(
+          SM, Expr, "parenthesized expression not permitted here");
+    return parseParenExpr(Expr, LineNumber, Context, SM);
+  }
+
   if (AO == AllowedOperand::LineVar || AO == AllowedOperand::Any) {
     // Try to parse as a numeric variable use.
     Expected<Pattern::VariableProperties> ParseVarResult =
         parseVariable(Expr, SM);
     if (ParseVarResult)
       return parseNumericVariableUse(ParseVarResult->Name,
                                      ParseVarResult->IsPseudo, LineNumber,
                                      Context, SM);
if (!Expr.consumeInteger((AO == AllowedOperand::LegacyLiteral) ? 10 : 0,
     return std::make_unique<ExpressionLiteral>(
         OperandExpr.drop_back(Expr.size()), LiteralValue);
   }
 
   return ErrorDiagnostic::get(SM, Expr,
                               "invalid operand format '" + Expr + "'");
 }
 
+Expected<std::unique_ptr<ExpressionAST>>
+Pattern::parseParenExpr(StringRef &Expr, Optional<size_t> LineNumber,
+                        FileCheckPatternContext *Context, const SourceMgr &SM) {
+  Expr = Expr.ltrim(SpaceChars);
+  assert(Expr.startswith("("));
+
+  // Parse right operand.
+  Expr.consume_front("(");
+  Expr = Expr.ltrim(SpaceChars);
+  if (Expr.empty())
+    return ErrorDiagnostic::get(SM, Expr, "missing operand in expression");
+
+  // Note: parseNumericOperand handles nested opening parentheses.
+  Expected<std::unique_ptr<ExpressionAST>> SubExprResult =
+      parseNumericOperand(Expr, AllowedOperand::Any, LineNumber, Context, SM);
+  Expr = Expr.ltrim(SpaceChars);
+  while (SubExprResult && !Expr.empty() && !Expr.startswith(")")) {
+    StringRef OrigExpr = Expr;
+    SubExprResult = parseBinop(OrigExpr, Expr, std::move(*SubExprResult), false,
+                               LineNumber, Context, SM);
+    Expr = Expr.ltrim(SpaceChars);
+  }
+  if (!SubExprResult)
+    return SubExprResult;
+
+  if (!Expr.consume_front(")")) {
+    return ErrorDiagnostic::get(SM, Expr,
+                                "missing ')' at end of nested expression");
+  }
+  return SubExprResult;
+}
+
 static uint64_t add(uint64_t LeftOp, uint64_t RightOp) {
   return LeftOp + RightOp;
 }
 
 static uint64_t sub(uint64_t LeftOp, uint64_t RightOp) {
   return LeftOp - RightOp;
 }
 

llvm/lib/Support/FileCheckImpl.h

private:
   /// None. Parameter \p Context points to the class instance holding the live
   /// string and numeric variables. \returns the pointer to the class instance
   /// representing that variable if successful, or an error holding a
   /// diagnostic against \p SM otherwise.
   static Expected<std::unique_ptr<NumericVariableUse>> parseNumericVariableUse(
       StringRef Name, bool IsPseudo, Optional<size_t> LineNumber,
       FileCheckPatternContext *Context, const SourceMgr &SM);
   enum class AllowedOperand { LineVar, LegacyLiteral, Any };
   /// Parses \p Expr for use of a numeric operand at line \p LineNumber, or
   /// before input is parsed if \p LineNumber is None. Accepts both literal
   /// values and numeric variables, depending on the value of \p AO. Parameter
   /// \p Context points to the class instance holding the live string and
   /// numeric variables. \returns the class representing that operand in the
   /// AST of the expression or an error holding a diagnostic against \p SM
-  /// otherwise.
+  /// otherwise. If @p Expr starts with a "(" this function will attempt to
+  /// parse a parenthesized expression.
   static Expected<std::unique_ptr<ExpressionAST>>
   parseNumericOperand(StringRef &Expr, AllowedOperand AO,
                       Optional<size_t> LineNumber,
                       FileCheckPatternContext *Context, const SourceMgr &SM);
   /// Parses and updates \p RemainingExpr for a binary operation at line
   /// \p LineNumber, or before input is parsed if \p LineNumber is None. The
   /// left operand of this binary operation is given in \p LeftOp and \p Expr
   /// holds the string for the full expression, including the left operand.
   /// Parameter \p IsLegacyLineExpr indicates whether we are parsing a legacy
   /// @LINE expression. Parameter \p Context points to the class instance
   /// holding the live string and numeric variables. \returns the class
   /// representing the binary operation in the AST of the expression, or an
   /// error holding a diagnostic against \p SM otherwise.
   static Expected<std::unique_ptr<ExpressionAST>>
   parseBinop(StringRef Expr, StringRef &RemainingExpr,
              std::unique_ptr<ExpressionAST> LeftOp, bool IsLegacyLineExpr,
              Optional<size_t> LineNumber, FileCheckPatternContext *Context,
              const SourceMgr &SM);
+
+  /// Parses a parenthesized expression inside \p Expr at line \p LineNumber, or
+  /// before input is parsed if \p LineNumber is None. \p Expr must start with
+  /// a '('. Accepts both literal values and numeric variables. Parameter \p
+  /// Context points to the class instance holding the live string and numeric
+  /// variables. \returns the class representing that operand in the AST of the
+  /// expression or an error holding a diagnostic against \p SM otherwise.
+  static Expected<std::unique_ptr<ExpressionAST>>
+  parseParenExpr(StringRef &Expr, Optional<size_t> LineNumber,
+                 FileCheckPatternContext *Context, const SourceMgr &SM);
 };
 
 //===----------------------------------------------------------------------===//
 // Check Strings.
 //===----------------------------------------------------------------------===//
 
 /// A check that we found in the input file.
 struct FileCheckString {

llvm/unittests/Support/FileCheckTest.cpp

TEST_F(FileCheckTest, ParseNumericSubstitutionBlock) {
   // Valid implicit format conflict in presence of explicit formats.
   EXPECT_THAT_EXPECTED(Tester.parseSubst("%X,FOO+VAR_LOWER_HEX"), Succeeded());
 
   // Implicit format conflict.
   expectDiagnosticError(
       "implicit format conflict between 'FOO' (%u) and "
       "'VAR_LOWER_HEX' (%x), need an explicit format specifier",
       Tester.parseSubst("FOO+VAR_LOWER_HEX").takeError());
+
+  // Simple parenthesized expressions:
+  EXPECT_THAT_EXPECTED(Tester.parseSubst("(1)"), Succeeded());
+  EXPECT_THAT_EXPECTED(Tester.parseSubst("(1+1)"), Succeeded());
+  EXPECT_THAT_EXPECTED(Tester.parseSubst("(1)+1"), Succeeded());
+  EXPECT_THAT_EXPECTED(Tester.parseSubst("((1)+1)"), Succeeded());
+  EXPECT_THAT_EXPECTED(Tester.parseSubst("((1)+X)"), Succeeded());
+  EXPECT_THAT_EXPECTED(Tester.parseSubst("((X)+Y)"), Succeeded());
+
+  expectDiagnosticError("missing operand in expression",
+                        Tester.parseSubst("(").takeError());
+  expectDiagnosticError("missing ')' at end of nested expression",
+                        Tester.parseSubst("(1").takeError());
+  expectDiagnosticError("missing operand in expression",
+                        Tester.parseSubst("(1+").takeError());
+  expectDiagnosticError("missing ')' at end of nested expression",
+                        Tester.parseSubst("(1+1").takeError());
+  expectDiagnosticError("missing ')' at end of nested expression",
+                        Tester.parseSubst("((1+2+3").takeError());
+  expectDiagnosticError("missing ')' at end of nested expression",
+                        Tester.parseSubst("((1+2)+3").takeError());
+
+  // Test missing operation between operands:
+  expectDiagnosticError("unsupported operation '('",
+                        Tester.parseSubst("(1)(2)").takeError());
+  expectDiagnosticError("unsupported operation '('",
+                        Tester.parseSubst("2(X)").takeError());
+
+  // Test more closing than opening parentheses. The diagnostic messages are
+  // not ideal, but for now simply check that we reject invalid input.
+  expectDiagnosticError("invalid operand format ')'",
+                        Tester.parseSubst(")").takeError());
+  expectDiagnosticError("unsupported operation ')'",
+                        Tester.parseSubst("1)").takeError());
+  expectDiagnosticError("unsupported operation ')'",
+                        Tester.parseSubst("(1+2))").takeError());
+  expectDiagnosticError("unsupported operation ')'",
+                        Tester.parseSubst("(2))").takeError());
+  expectDiagnosticError("unsupported operation ')'",
+                        Tester.parseSubst("(1))(").takeError());
 }
 
 TEST_F(FileCheckTest, ParsePattern) {
   PatternTester Tester;
 
   // Invalid space in string substitution.
   EXPECT_TRUE(Tester.parsePattern("[[ BAR]]"));
 
TEST_F(FileCheckTest, Match) {
   Tester.initNextPattern();
   // Check that @LINE matches the later (given the calls to initNextPattern())
   // line number.
   EXPECT_FALSE(Tester.parsePattern("[[#@LINE]]"));
   EXPECT_THAT_EXPECTED(Tester.match(std::to_string(Tester.getLineNumber())),
                        Succeeded());
 }
 
+TEST_F(FileCheckTest, MatchParen) {
+  PatternTester Tester;
+  // Check simple parenthesized expressions
+  Tester.initNextPattern();
+  ASSERT_FALSE(Tester.parsePattern("[[#NUMVAR:]]"));
+  expectNotFoundError(Tester.match("FAIL").takeError());
+  expectNotFoundError(Tester.match("").takeError());
+  EXPECT_THAT_EXPECTED(Tester.match("18"), Succeeded());
+
+  Tester.initNextPattern();
+  ASSERT_FALSE(Tester.parsePattern("[[#NUMVAR + (2 + 2)]]"));
+  expectNotFoundError(Tester.match("21").takeError());
+  EXPECT_THAT_EXPECTED(Tester.match("22"), Succeeded());
+  Tester.initNextPattern();
+  ASSERT_FALSE(Tester.parsePattern("[[#NUMVAR + (2)]]"));
+  EXPECT_THAT_EXPECTED(Tester.match("20"), Succeeded());
+  Tester.initNextPattern();
+  ASSERT_FALSE(Tester.parsePattern("[[#NUMVAR+(2)]]"));
+  EXPECT_THAT_EXPECTED(Tester.match("20"), Succeeded());
+  Tester.initNextPattern();
+  ASSERT_FALSE(Tester.parsePattern("[[#NUMVAR+(NUMVAR)]]"));
+  EXPECT_THAT_EXPECTED(Tester.match("36"), Succeeded());
+
+  // Check nested parenthesized expressions:
+  Tester.initNextPattern();
+  ASSERT_FALSE(Tester.parsePattern("[[#NUMVAR+(2+(2))]]"));
+  EXPECT_THAT_EXPECTED(Tester.match("22"), Succeeded());
+  Tester.initNextPattern();
+  ASSERT_FALSE(Tester.parsePattern("[[#NUMVAR+(2+(NUMVAR))]]"));
+  EXPECT_THAT_EXPECTED(Tester.match("38"), Succeeded());
+  Tester.initNextPattern();
+  ASSERT_FALSE(Tester.parsePattern("[[#NUMVAR+((((NUMVAR))))]]"));
+  EXPECT_THAT_EXPECTED(Tester.match("36"), Succeeded());
+  Tester.initNextPattern();
+  ASSERT_FALSE(Tester.parsePattern("[[#NUMVAR+((((NUMVAR)))-1)-1]]"));
+  EXPECT_THAT_EXPECTED(Tester.match("34"), Succeeded());
+
+  // Parentheses can also be the first character after the '#':
+  Tester.initNextPattern();
+  ASSERT_FALSE(Tester.parsePattern("[[#(NUMVAR)]]"));
+  EXPECT_THAT_EXPECTED(Tester.match("18"), Succeeded());
+  Tester.initNextPattern();
+  ASSERT_FALSE(Tester.parsePattern("[[#(NUMVAR+2)]]"));
+  EXPECT_THAT_EXPECTED(Tester.match("20"), Succeeded());
+}
+
 TEST_F(FileCheckTest, Substitution) {
   SourceMgr SM;
   FileCheckPatternContext Context;
   EXPECT_THAT_ERROR(Context.defineCmdlineVariables({"FOO=BAR"}, SM),
                     Succeeded());
 
   // Substitution of an undefined string variable fails and error holds that
   // variable's name.