Refactor and clean up the status file parsing code.

tools/testing/dart/status_expression.dart

Index: tools/testing/dart/status_expression.dart
diff --git a/tools/testing/dart/status_expression.dart b/tools/testing/dart/status_expression.dart
index 3804d1daecb47f829a67aab2364539b2685bd7dc..d952078dd47eb1264e11334e0c99c068fe5af559 100644
--- a/tools/testing/dart/status_expression.dart
+++ b/tools/testing/dart/status_expression.dart
@@ -2,313 +2,232 @@
 // 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;
+/// 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);
 }
 
-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 = "||";
+/// 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 = "||";
 }
 
-class Tokenizer {
-  String expression;
-  List<String> tokens;
+/// A reference to a variable.
+class _Variable {
+  final String name;
 
-  Tokenizer(String this.expression) : tokens = new List<String>();
+  _Variable(this.name);
 
-  // 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) {
+  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';
-  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)
-      ? left.evaluate(environment) && right.evaluate(environment)
-      : left.evaluate(environment) || right.evaluate(environment);
-  String toString() => "($left $op $right)";
+    return value;
+  }
 }
 
-class SetUnion implements SetExpression {
-  SetExpression left;
-  SetExpression right;
+/// 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;
 
-  SetUnion(this.left, this.right);
+  _ComparisonExpression(this.left, this.right, this.negate);
 
-  // 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;
+  bool evaluate(Map<String, dynamic> environment) {
+    return negate != (left.lookup(environment) == right);
   }
 
-  String toString() => "($left || $right)";
+  String toString() => "(\$${left.name} ${negate ? '!=' : '=='} $right)";
 }
 
-class SetIf implements SetExpression {
-  SetExpression left;
-  BooleanExpression 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;
 
-  SetIf(this.left, this.right);
+  _VariableExpression(this.variable);
 
-  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();
+  bool evaluate(Map<String, dynamic> environment) =>
+      variable.lookup(environment) == 'true';
 
-  Set<String> evaluate(environment) => [value].toSet();
-  String toString() => value;
+  String toString() => "(bool \$${variable.name})";
 }
 
-// An iterator that allows peeking at the current token.
-class Scanner {
-  List<String> tokens;
-  Iterator tokenIterator;
-  String current;
+/// A logical `||` or `&&` expression.
+class _LogicExpression implements Expression {
+  /// The operator, `||` or `&&`.
+  final String op;
 
-  Scanner(this.tokens) {
-    tokenIterator = tokens.iterator;
-    advance();
-  }
+  final Expression left;
+  final Expression right;
 
-  bool hasMore() => current != null;
+  _LogicExpression(this.op, this.left, this.right);
 
-  void advance() {
-    current = tokenIterator.moveNext() ? tokenIterator.current : null;
-  }
-}
+  bool evaluate(Map<String, dynamic> environment) => (op == _Token.and)
+      ? left.evaluate(environment) && right.evaluate(environment)
+      : left.evaluate(environment) || right.evaluate(environment);
 
-class ExpressionParser {
-  Scanner scanner;
+  String toString() => "($left $op $right)";
+}
 
-  ExpressionParser(this.scanner);
+/// Parser for Boolean expressions in a .status file for Dart.
+class _ExpressionParser {
+  final _Scanner _scanner;
 
-  SetExpression parseSetExpression() => parseSetUnion();
+  _ExpressionParser(String expression) : _scanner = new _Scanner(expression);
 
-  SetExpression parseSetUnion() {
-    SetExpression left = parseSetIf();
-    while (scanner.hasMore() && scanner.current == Token.UNION) {
-      scanner.advance();
-      SetExpression right = parseSetIf();
-      left = new SetUnion(left, right);
-    }
-    return left;
-  }
+  Expression parse() {
+    var expression = _parseOr();
 
-  SetExpression parseSetIf() {
-    SetExpression left = parseSetOr();
-    while (scanner.hasMore() && scanner.current == "if") {
-      scanner.advance();
-      BooleanExpression right = parseBooleanExpression();
-      left = new SetIf(left, right);
+    // Should consume entire string.
+    if (_scanner.hasMore) {
+      throw new FormatException("Unexpected input after expression");
     }
-    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;
+    return expression;
   }
 
-  SetExpression parseSetAtomic() {
-    if (scanner.current == Token.LEFT_PAREN) {
-      scanner.advance();
-      SetExpression value = parseSetExpression();
-      if (scanner.current != Token.RIGHT_PAREN) {
-        throw new FormatException("Missing right parenthesis in expression");
-      }
-      scanner.advance();
-      return value;
+  Expression _parseOr() {
+    var left = _parseAnd();
+    while (_scanner.match(_Token.or)) {
+      var right = _parseAnd();
+      left = new _LogicExpression(_Token.or, left, right);
     }
-    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);
+  Expression _parseAnd() {
+    var left = _parsePrimary();
+    while (_scanner.match(_Token.and)) {
+      var right = _parsePrimary();
+      left = new _LogicExpression(_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) {
+  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;
     }
 
     // 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}");
+          "Expected \$ in expression, got ${_scanner.current}");
     }
-    scanner.advance();
-    if (!new RegExp(r"^\w+$").hasMatch(scanner.current)) {
+
+    if (!_scanner.isIdentifier) {
       throw new FormatException(
-          "Expected identifier in expression, got ${scanner.current}");
+          "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)) {
+
+    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;
+  }
+}