Refactor and clean up the status file parsing code.

tools/testing/dart/status_expression.dart

 // Copyright (c) 2011, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
-library status_expression;
-
-/**
- * Parse and evaluate expressions in a .status file for Dart and V8.
- * There are set expressions and Boolean expressions in a .status file.
- * The grammar is:
- *   BooleanExpression := $variableName == value | $variableName != value |
- *                        $variableName | (BooleanExpression) |
- *                        BooleanExpression && BooleanExpression |
- *                        BooleanExpression || BooleanExpression
- *
- *   SetExpression := value | (SetExpression) |
- *                    SetExpression || SetExpression |
- *                    SetExpression if BooleanExpression |
- *                    SetExpression , SetExpression
- *
- *  Productions are listed in order of precedence, and the || and , operators
- *  both evaluate to set union, but with different precedence.
- *
- *  Values and variableNames are non-empty strings of word characters, matching
- *  the RegExp \w+.
- *
- *  Expressions evaluate as expected, with values of variables found in
- *  an environment passed to the evaluator.  The SetExpression "value"
- *  evaluates to a singleton set containing that value. "A if B" evaluates
- *  to A if B is true, and to the empty set if B is false.
- */
-
-class ExprEvaluationException {
-  String error;
-
-  ExprEvaluationException(this.error);
-
-  toString() => error;
-}
-
-class Token {
-  static const String LEFT_PAREN = "(";
-  static const String RIGHT_PAREN = ")";
-  static const String DOLLAR_SYMBOL = r"$";
-  static const String UNION = ",";
-  static const String EQUALS = "==";
-  static const String NOT_EQUALS = "!=";
-  static const String AND = "&&";
-  static const String OR = "||";
-}
-
-class Tokenizer {
-  String expression;
-  List<String> tokens;
-
-  Tokenizer(String this.expression) : tokens = new List<String>();
-
-  // Tokens are : "(", ")", "$", ",", "&&", "||", "==", "!=", and (maximal) \w+.
-  static final testRegexp =
-      new RegExp(r"^([()$\w\s,]|(\&\&)|(\|\|)|(\=\=)|(\!\=))+$");
-  static final regexp = new RegExp(r"[()$,]|(\&\&)|(\|\|)|(\=\=)|(\!\=)|\w+");
-
-  List<String> tokenize() {
-    if (!testRegexp.hasMatch(expression)) {
-      throw new FormatException("Syntax error in '$expression'");
-    }
-    for (Match match in regexp.allMatches(expression)) tokens.add(match[0]);
-    return tokens;
-  }
-}
-
-abstract class BooleanExpression {
-  bool evaluate(Map<String, String> environment);
-}
-
-abstract class SetExpression {
-  Set<String> evaluate(Map<String, String> environment);
-}
-
-class Comparison implements BooleanExpression {
-  TermVariable left;
-  TermConstant right;
-  bool negate;
-
-  Comparison(this.left, this.right, this.negate);
-
-  bool evaluate(environment) {
-    return negate !=
-        (left.termValue(environment) == right.termValue(environment));
-  }
-
-  String toString() =>
-      "(\$${left.name} ${negate ? '!=' : '=='} ${right.value})";
-}
-
-class TermVariable {
-  String name;
-
-  TermVariable(this.name);
-
-  String termValue(environment) {
+/// A parsed Boolean expression AST.
+abstract class Expression {

[kevmoo, 2017/05/15 21:06:48]

Possible? https://github.com/dart-lang/boolean_selector

[Bob Nystrom, 2017/05/15 22:42:51]

For test.dart, we try not to rely on any external dependencies since this is so
fundamental to the infrastructure. Also, switching this out might subtly change
the grammar in ways we don't expect.

+  /// Parses Boolean expressions in a .status file for Dart.
+  ///
+  /// The grammar is:
+  ///
+  ///     expression := or
+  ///     or         := and ( "||" and )*
+  ///     and        := primary ( "&&" primary )*
+  ///     primary    := "$" identifier ( ( "==" | "!=" ) identifier )? |
+  ///                   "(" expression ")"
+  ///     identifier := regex "\w+"
+  ///
+  /// Expressions evaluate as expected, with values of variables found in an
+  /// environment passed to the evaluator.
+  static Expression parse(String expression) =>
+      new _ExpressionParser(expression).parse();
+
+  /// Evaluates the expression where all variables are defined by the given
+  /// [environment].
+  bool evaluate(Map<String, dynamic> environment);
+}
+
+/// Keyword token strings.
+class _Token {
+  static const leftParen = "(";
+  static const rightParen = ")";
+  static const dollar = r"$";
+  static const equals = "==";
+  static const notEqual = "!=";
+  static const and = "&&";
+  static const or = "||";
+}
+
+/// A reference to a variable.
+class _Variable {
+  final String name;
+
+  _Variable(this.name);
+
+  dynamic lookup(Map<String, dynamic> environment) {
     var value = environment[name];
     if (value == null) {
-      throw new ExprEvaluationException("Could not find '$name' in environment "
+      throw new Exception("Could not find '$name' in environment "
           "while evaluating status file expression.");
     }
-    return value.toString();
-  }
-}
-
-class TermConstant {
-  String value;
-
-  TermConstant(String this.value);
-
-  String termValue(environment) => value;
-}
-
-class BooleanVariable implements BooleanExpression {
-  TermVariable variable;
-
-  BooleanVariable(this.variable);
-
-  bool evaluate(environment) => variable.termValue(environment) == 'true';
+
+    return value;
+  }
+}
+
+/// Tests whether a given variable is or is not equal some literal value, as in:
+///
+///     $variable == someValue
+class _ComparisonExpression implements Expression {
+  final _Variable left;
+  final String right;
+  final bool negate;
+
+  _ComparisonExpression(this.left, this.right, this.negate);
+
+  bool evaluate(Map<String, dynamic> environment) {
+    return negate != (left.lookup(environment) == right);
+  }
+
+  String toString() => "(\$${left.name} ${negate ? '!=' : '=='} $right)";
+}
+
+/// A reference to a variable defined in the environment. The variable's value
+/// should be Boolean and the expression is true when the value is "true".
+///
+///     $variable
+class _VariableExpression implements Expression {
+  final _Variable variable;
+
+  _VariableExpression(this.variable);
+
+  bool evaluate(Map<String, dynamic> environment) =>
+      variable.lookup(environment) == 'true';
+
   String toString() => "(bool \$${variable.name})";
 }
 
-class BooleanOperation implements BooleanExpression {
-  String op;
-  BooleanExpression left;
-  BooleanExpression right;
-
-  BooleanOperation(this.op, this.left, this.right);
-
-  bool evaluate(environment) => (op == Token.AND)
+/// A logical `||` or `&&` expression.
+class _LogicExpression implements Expression {
+  /// The operator, `||` or `&&`.
+  final String op;
+
+  final Expression left;
+  final Expression right;
+
+  _LogicExpression(this.op, this.left, this.right);
+
+  bool evaluate(Map<String, dynamic> environment) => (op == _Token.and)
       ? left.evaluate(environment) && right.evaluate(environment)
       : left.evaluate(environment) || right.evaluate(environment);
+
   String toString() => "($left $op $right)";
 }
 
-class SetUnion implements SetExpression {
-  SetExpression left;
-  SetExpression right;
-
-  SetUnion(this.left, this.right);
-
-  // Overwrites left.evaluate(env).
-  // Set.addAll does not return this.
-  Set<String> evaluate(environment) {
-    Set<String> result = left.evaluate(environment);
-    result.addAll(right.evaluate(environment));
-    return result;
-  }
-
-  String toString() => "($left || $right)";
-}
-
-class SetIf implements SetExpression {
-  SetExpression left;
-  BooleanExpression right;
-
-  SetIf(this.left, this.right);
-
-  Set<String> evaluate(environment) => right.evaluate(environment)
-      ? left.evaluate(environment)
-      : new Set<String>();
-  String toString() => "($left if $right)";
-}
-
-class SetConstant implements SetExpression {
-  String value;
-
-  SetConstant(String v) : value = v.toLowerCase();
-
-  Set<String> evaluate(environment) => [value].toSet();
-  String toString() => value;
-}
-
-// An iterator that allows peeking at the current token.
-class Scanner {
-  List<String> tokens;
-  Iterator tokenIterator;
-  String current;
-
-  Scanner(this.tokens) {
-    tokenIterator = tokens.iterator;
-    advance();
-  }
-
-  bool hasMore() => current != null;
-
-  void advance() {
-    current = tokenIterator.moveNext() ? tokenIterator.current : null;
-  }
-}
-
-class ExpressionParser {
-  Scanner scanner;
-
-  ExpressionParser(this.scanner);
-
-  SetExpression parseSetExpression() => parseSetUnion();
-
-  SetExpression parseSetUnion() {
-    SetExpression left = parseSetIf();
-    while (scanner.hasMore() && scanner.current == Token.UNION) {
-      scanner.advance();
-      SetExpression right = parseSetIf();
-      left = new SetUnion(left, right);
-    }
+/// Parser for Boolean expressions in a .status file for Dart.
+class _ExpressionParser {
+  final _Scanner _scanner;
+
+  _ExpressionParser(String expression) : _scanner = new _Scanner(expression);
+
+  Expression parse() {
+    var expression = _parseOr();
+
+    // Should consume entire string.
+    if (_scanner.hasMore) {
+      throw new FormatException("Unexpected input after expression");
+    }
+
+    return expression;
+  }
+
+  Expression _parseOr() {
+    var left = _parseAnd();
+    while (_scanner.match(_Token.or)) {
+      var right = _parseAnd();
+      left = new _LogicExpression(_Token.or, left, right);
+    }
+
     return left;
   }
 
-  SetExpression parseSetIf() {
-    SetExpression left = parseSetOr();
-    while (scanner.hasMore() && scanner.current == "if") {
-      scanner.advance();
-      BooleanExpression right = parseBooleanExpression();
-      left = new SetIf(left, right);
-    }
+  Expression _parseAnd() {
+    var left = _parsePrimary();
+    while (_scanner.match(_Token.and)) {
+      var right = _parsePrimary();
+      left = new _LogicExpression(_Token.and, left, right);
+    }
+
     return left;
   }
 
-  SetExpression parseSetOr() {
-    SetExpression left = parseSetAtomic();
-    while (scanner.hasMore() && scanner.current == Token.OR) {
-      scanner.advance();
-      SetExpression right = parseSetAtomic();
-      left = new SetUnion(left, right);
-    }
-    return left;
-  }
-
-  SetExpression parseSetAtomic() {
-    if (scanner.current == Token.LEFT_PAREN) {
-      scanner.advance();
-      SetExpression value = parseSetExpression();
-      if (scanner.current != Token.RIGHT_PAREN) {
+  Expression _parsePrimary() {
+    if (_scanner.match(_Token.leftParen)) {
+      var value = _parseOr();
+      if (!_scanner.match(_Token.rightParen)) {
         throw new FormatException("Missing right parenthesis in expression");
       }
-      scanner.advance();
-      return value;
-    }
-    if (!new RegExp(r"^\w+$").hasMatch(scanner.current)) {
-      throw new FormatException(
-          "Expected identifier in expression, got ${scanner.current}");
-    }
-    SetExpression value = new SetConstant(scanner.current);
-    scanner.advance();
-    return value;
-  }
-
-  BooleanExpression parseBooleanExpression() => parseBooleanOr();
-
-  BooleanExpression parseBooleanOr() {
-    BooleanExpression left = parseBooleanAnd();
-    while (scanner.hasMore() && scanner.current == Token.OR) {
-      scanner.advance();
-      BooleanExpression right = parseBooleanAnd();
-      left = new BooleanOperation(Token.OR, left, right);
-    }
-    return left;
-  }
-
-  BooleanExpression parseBooleanAnd() {
-    BooleanExpression left = parseBooleanAtomic();
-    while (scanner.hasMore() && scanner.current == Token.AND) {
-      scanner.advance();
-      BooleanExpression right = parseBooleanAtomic();
-      left = new BooleanOperation(Token.AND, left, right);
-    }
-    return left;
-  }
-
-  BooleanExpression parseBooleanAtomic() {
-    if (scanner.current == Token.LEFT_PAREN) {
-      scanner.advance();
-      BooleanExpression value = parseBooleanExpression();
-      if (scanner.current != Token.RIGHT_PAREN) {
-        throw new FormatException("Missing right parenthesis in expression");
-      }
-      scanner.advance();
+
       return value;
     }
 
     // The only atomic booleans are of the form $variable == value or
     // of the form $variable.
-    if (scanner.current != Token.DOLLAR_SYMBOL) {
+    if (!_scanner.match(_Token.dollar)) {
       throw new FormatException(
-          "Expected \$ in expression, got ${scanner.current}");
-    }
-    scanner.advance();
-    if (!new RegExp(r"^\w+$").hasMatch(scanner.current)) {
+          "Expected \$ in expression, got ${_scanner.current}");
+    }
+
+    if (!_scanner.isIdentifier) {
       throw new FormatException(
-          "Expected identifier in expression, got ${scanner.current}");
-    }
-    TermVariable left = new TermVariable(scanner.current);
-    scanner.advance();
-    if (scanner.current == Token.EQUALS ||
-        scanner.current == Token.NOT_EQUALS) {
-      bool negate = scanner.current == Token.NOT_EQUALS;
-      scanner.advance();
-      if (!new RegExp(r"^\w+$").hasMatch(scanner.current)) {
+          "Expected identifier in expression, got ${_scanner.current}");
+    }
+
+    var left = new _Variable(_scanner.current);
+    _scanner.advance();
+
+    if (_scanner.current == _Token.equals ||
+        _scanner.current == _Token.notEqual) {
+      var negate = _scanner.advance() == _Token.notEqual;
+
+      if (!_scanner.isIdentifier) {
         throw new FormatException(
-            "Expected value in expression, got ${scanner.current}");
+            "Expected value in expression, got ${_scanner.current}");
       }
-      TermConstant right = new TermConstant(scanner.current);
-      scanner.advance();
-      return new Comparison(left, right, negate);
+
+      var right = _scanner.advance();
+      return new _ComparisonExpression(left, right, negate);
     } else {
-      return new BooleanVariable(left);
-    }
-  }
-}
+      return new _VariableExpression(left);
+    }
+  }
+}
+
+/// An iterator that allows peeking at the current token.
+class _Scanner {
+  /// Tokens are "(", ")", "$", ",", "&&", "||", "==", "!=", and (maximal) \w+.
+  static final _testPattern =
+      new RegExp(r"^([()$\w\s,]|(\&\&)|(\|\|)|(\=\=)|(\!\=))+$");

[Bill Hesse, 2017/05/15 16:15:08]

I think you can remove ',' from the two regexps, if we aren't handling input
with ',' in it.

[Bob Nystrom, 2017/05/15 22:42:51]

Nice catch! Done.

+  static final _tokenPattern =
+      new RegExp(r"[()$,]|(\&\&)|(\|\|)|(\=\=)|(\!\=)|\w+");
+
+  static final _identifierPattern = new RegExp(r"^\w+$");
+
+  /// The token strings being iterated.
+  final Iterator<String> tokenIterator;
+
+  String current;
+
+  _Scanner(String expression) : tokenIterator = tokenize(expression).iterator {
+    advance();
+  }
+
+  static List<String> tokenize(String expression) {
+    if (!_testPattern.hasMatch(expression)) {
+      throw new FormatException("Syntax error in '$expression'");
+    }
+
+    return _tokenPattern
+        .allMatches(expression)

[Bill Hesse, 2017/05/15 16:15:09]

I had no idea that this was non-overlapping.  You learn something every day.

[Bob Nystrom, 2017/05/15 22:42:51]

Guess so. I did too! (This was in the original code as well, it just moved down
here.)

+        .map((match) => match[0])
+        .toList();
+  }
+
+  bool get hasMore => current != null;
+
+  /// Returns `true` if the current token is an identifier.
+  bool get isIdentifier => _identifierPattern.hasMatch(current);
+
+  /// If the current token is [token], consumes it and returns `true`.
+  bool match(String token) {
+    if (!hasMore || current != token) return false;
+
+    advance();
+    return true;
+  }
+
+  /// Consumes the current token and returns it.
+  String advance() {
+    var previous = current;
+    current = tokenIterator.moveNext() ? tokenIterator.current : null;
+    return previous;
+  }
+}