dart2dart: Logical operators and related rewrite rules in dart_tree.

sdk/lib/_internal/compiler/implementation/dart_backend/dart_tree.dart

 // Copyright (c) 2014, 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 dart_tree;
 
 import '../dart2jslib.dart' as dart2js;
 import '../elements/elements.dart'
     show Element, FunctionElement, FunctionSignature, ParameterElement,
          ClassElement;
@@ skipping 167 matching lines @@
 
   final bool isPure = false; // invokes toString
 
   accept(Visitor visitor) => visitor.visitConcatenateStrings(this);
 }
 
 /**
  * A constant.
  */
 class Constant extends Expression {
-  final dart2js.Constant value;
+  dart2js.Constant value;
 
   Constant(this.value);
 
   final bool isPure = true;
 
   accept(Visitor visitor) => visitor.visitConstant(this);
 }
 
 /// A conditional expression.
 class Conditional extends Expression {
   Expression condition;
   Expression thenExpression;
   Expression elseExpression;
 
   Conditional(this.condition, this.thenExpression, this.elseExpression);
 
   // TODO(asgerf): Repeatedly computing isPure is potentially expensive,
   // but caching isPure in a field is dangerous because a subexpression could
   // become impure during a transformation (e.g. assignment propagation).
   // Improve the situation somehow.
   bool get isPure => condition.isPure &&
                      thenExpression.isPure &&
                      elseExpression.isPure;
 
   accept(Visitor visitor) => visitor.visitConditional(this);
 }
 
+/// An && or || expression. The operator is internally represented as a boolean
+/// [isAnd] to simplify rewriting of logical operators.
+class LogicalOperator extends Expression {
+  Expression left;
+  bool isAnd;
+  Expression right;
+
+  LogicalOperator(this.left, this.right, this.isAnd);
+  LogicalOperator.and(this.left, this.right) : isAnd = true;
+  LogicalOperator.or(this.left, this.right) : isAnd = false;
+
+  String get operator => isAnd ? '&&' : '||';
+
+  bool get isPure => left.isPure && right.isPure;
+
+  accept(Visitor visitor) => visitor.visitLogicalOperator(this);
+}
+
+/// Logical negation.
+class Not extends Expression {
+  Expression operand;
+
+  Not(this.operand);
+
+  bool get isPure => operand.isPure;
+
+  accept(Visitor visitor) => visitor.visitNot(this);
+}
+
 /**
  * A labeled statement.  Breaks to the label within the labeled statement
  * target the successor statement.
  */
 class LabeledStatement extends Statement {
   Statement next;
   final Label label;
   Statement body;
 
   LabeledStatement(this.label, this.body, this.next) {
@@ skipping 97 matching lines @@
 
 abstract class Visitor<S, E> {
   E visitExpression(Expression e) => e.accept(this);
   E visitVariable(Variable node);
   E visitInvokeStatic(InvokeStatic node);
   E visitInvokeMethod(InvokeMethod node);
   E visitInvokeConstructor(InvokeConstructor node);
   E visitConcatenateStrings(ConcatenateStrings node);
   E visitConstant(Constant node);
   E visitConditional(Conditional node);
+  E visitLogicalOperator(LogicalOperator node);
+  E visitNot(Not node);
 
   S visitStatement(Statement s) => s.accept(this);
   S visitLabeledStatement(LabeledStatement node);
   S visitAssign(Assign node);
   S visitReturn(Return node);
   S visitBreak(Break node);
   S visitIf(If node);
   S visitExpressionStatement(ExpressionStatement node);
 }
 
@@ skipping 238 matching lines @@
     compiler.internalError(compiler.currentElement, 'Unexpected IR node.');
     return null;
   }
 
   Expression visitIsTrue(ir.IsTrue node) {
     return variables[node.value.definition];
   }
 }
 
 /**
  * Performs the following three transformations on the tree:

[Kevin Millikin (Google), 2014/05/19 11:36:41]

following three transformations ==> following transformations

[asgerf, 2014/05/19 13:29:07]

Done.

  * - Assignment propagation
  * - If-to-conditional conversion
+ * - Flatten nested ifs
  * - Break inlining
+ * - Redirect breaks
  *
  * The above transformations are performed in the same phase because each
  * transformation can introduce redexes of one of the others.
  *
  *
  * ASSIGNMENT PROPAGATION:
  * Single-use definitions are propagated to their use site when possible.
  * For example:
  *
  *   { v0 = foo(); return v0; }
@@ skipping 24 matching lines @@
  *   if (v0) { v1 = foo(); break L } else { v1 = bar(); break L }
  *     ==>
  *   { v1 = v0 ? foo() : bar(); break L }
  *
  * This can lead to inlining of L, which in turn can lead to further propagation
  * of the variable v1.
  *
  * See [visitIf].
  *
  *
+ * FLATTEN NESTED IFS:
+ * An if inside an if is converted to an if with a logical operator.
+ * For example:
+ *
+ *   if (E1) { if (E2) {S} else break L } else break L
+ *     ==>
+ *   if (E1 && E2) {S} else break L
+ *
+ * This may lead to inlining of L.
+ *
+ *
  * BREAK INLINING:
  * Single-use labels are inlined at [Break] statements.
  * For example:
  *
  *   L0: { v0 = foo(); break L0 }; return v0;
  *     ==>
  *   v0 = foo(); return v0;
  *
  * This can lead to propagation of v0.
  *
  * See [visitBreak] and [visitLabeledStatement].
+ *
+ *
+ * REDIRECT BREAKS:
+ * Labeled statements whose next is a break become flattened and all breaks
+ * to their label are redirected.
+ * For example:
+ *
+ *   L0: {... break L0 ...}; break L1
+ *     ==>
+ *   {... break L1 ...}
+ *
+ * This may trigger a flattening of nested ifs in case the eliminated label
+ * separated two ifs.
  */
 class TreeRewriter extends Visitor<Statement, Expression> {
   // The binding environment.  The rightmost element of the list is the nearest
   // enclosing binding.
   // We use null to mark an impure expressions that does not bind a variable.
   List<Assign> environment;
 
-  void apply(FunctionDefinition definition) {
+  /// Substitution map for labels. Any break to a label L should be substituted
+  /// for a break to L' if L maps to L'.
+  Map<Label,Label> labelRedirects = <Label,Label>{};

[Kevin Millikin (Google), 2014/05/19 11:36:41]

Space after comma: Map<Label, Label>

[asgerf, 2014/05/19 13:29:07]

Done.

+
+  /// Returns the redirect target of [label] or [label] itself if it should not
+  /// be redirected.
+  Label redirect(Label label) {
+    Label newTarget = labelRedirects[label];
+    return newTarget != null ? newTarget : label;
+  }
+
+  void rewrite(FunctionDefinition definition) {
     environment = <Assign>[];
     definition.body = visitStatement(definition.body);
 
     // TODO(kmillikin):  Allow definitions that are not propagated.  Here,
     // this means rebuilding the binding with a recursively unnamed definition,
     // or else introducing a variable definition and an assignment.
     assert(environment.isEmpty);
   }
 
   Expression visitExpression(Expression e) => e.processed ? e : e.accept(this);
@@ skipping 29 matching lines @@
       } else if (!environment[i].definition.isPure) {
         // Once the first impure definition is seen, impure definitions should
         // no longer be propagated.  Continue searching for a pure definition.
         seenImpure = true;
       }
     }
     // If the definition could not be propagated, leave the variable use.
     return node;
   }
 
-  Statement visitLabeledStatement(LabeledStatement node) {
-    node.body = visitStatement(node.body);
-    if (node.label.breakCount == 0) {
-      // If the break was inlined, eliminate the label.
-      return node.body;
-    }
-    node.next = visitStatement(node.next);
-    return node;
-  }
 
   Statement visitAssign(Assign node) {
     environment.add(node);
     Statement next = visitStatement(node.next);
 
     if (!environment.isEmpty && environment.last == node) {
       // The definition could not be propagated.  Residualize the let binding.
       node.next = next;
       environment.removeLast();
       node.definition = visitExpression(node.definition);
@@ skipping 37 matching lines @@
     node.condition = visitExpression(node.condition);
 
     environment.add(null); // impure expressions may not propagate across branch
     node.thenExpression = visitExpression(node.thenExpression);
     node.elseExpression = visitExpression(node.elseExpression);
     environment.removeLast();
 
     return node;
   }
 
+  Expression visitLogicalOperator(LogicalOperator node) {
+    node.left = visitExpression(node.left);
+
+    environment.add(null); // impure expressions may not propagate across branch
+    node.right = visitExpression(node.right);
+    environment.removeLast();
+
+    return node;
+  }
+
+  Expression visitNot(Not node) {
+    node.operand = visitExpression(node.operand);
+    return node;
+  }
+
   Statement visitReturn(Return node) {
     node.value = visitExpression(node.value);
     return node;
   }
 
 
   Statement visitBreak(Break node) {
+    // Redirect through chain of breaks.
+    // Note that breakCount was accounted for at visitLabeledStatement.
+    node.target = redirect(node.target);
     if (node.target.breakCount == 1) {
       --node.target.breakCount;
       return visitStatement(node.target.binding.next);
     }
     return node;
   }
 
+  Statement visitLabeledStatement(LabeledStatement node) {
+    if (node.next is Break) {
+      // Eliminate label if next is just a break statement
+      // Breaks to this label are redirected to the outer label.
+      // Note that breakCount for the two labels is updated proactively here
+      // so breaks can reliably tell if they should inline their target.
+      Break next = node.next;
+      Label newTarget = labelRedirects[node.label] = redirect(next.target);

[Kevin Millikin (Google), 2014/05/19 11:36:41]

More readable:

Label newTarget = redirect(next.target);
labelRedirects[node.label] = newTarget;

[asgerf, 2014/05/19 13:29:07]

Done.

+      newTarget.breakCount += node.label.breakCount;
+      node.label.breakCount = 0;
+      Statement result = visitStatement(node.body);
+      labelRedirects.remove(node.label); // Save some space.

[Kevin Millikin (Google), 2014/05/19 11:36:41]

I wouldn't bother doing this here (or at all).

+      return result;
+    }
+
+    node.body = visitStatement(node.body);
+
+    if (node.label.breakCount == 0) {
+      // Eliminate the label if next was inlined at a break
+      return node.body;
+    }
+
+    node.next = visitStatement(node.next);
+    return node;
+  }
+
   Statement visitIf(If node) {
     node.condition = visitExpression(node.condition);
 
     environment.add(null); // impure expressions may not propagate across branch
     node.thenStatement = visitStatement(node.thenStatement);
     node.elseStatement = visitStatement(node.elseStatement);
     environment.removeLast();
 
+    // Repeatedly try to collapse nested ifs.
+    // The transformation is shrinking (destroys an if) so it remains linear.
+    // Here is an example where more than one iteration is required:
+    //
+    //   if (E1)
+    //     if (E2) break L2 else break L1
+    //   else
+    //     break L1
+    //
+    // L1.target ::=
+    //   if (E3) S else break L2
+    //
+    // After first collapse:
+    //
+    //   if (E1 && E2)
+    //     break L2
+    //   else
+    //     {if (E3) S else break L2}  (inlined from break L1)
+    //
+    // We can then do another collapse using the inlined nested if.
+    var changed = true;
+    while (changed) {
+      changed = false;
+      changed = changed || tryCollapseIf(node, true, true);
+      changed = changed || tryCollapseIf(node, true, false);
+      changed = changed || tryCollapseIf(node, false, true);
+      changed = changed || tryCollapseIf(node, false, false);
+    }
+
     Statement reduced = combineStatementsWithSubexpressions(
         node.thenStatement,
         node.elseStatement,
         (t,f) => new Conditional(node.condition, t, f)..processed = true);
     if (reduced != null) {
       if (reduced.next is Break) {
         // In case the break can now be inlined.
         reduced = visitStatement(reduced);
       }
       return reduced;
@@ skipping 11 matching lines @@
     if (!node.expression.isPure) {
       environment.add(null); // insert impurity marker (TODO: refactor)
     }
     node.next = visitStatement(node.next);
     if (!node.expression.isPure) {
       environment.removeLast();
     }
     return node;
   }
 
-
   /// If [s] and [t] are similar statements we extract their subexpressions
   /// and returns a new statement of the same type using expressions combined
   /// with the [combine] callback. For example:
   ///
   ///   combineStatements(Return E1, Return E2) = Return combine(E1, E2)
   ///
   /// If [combine] returns E1 then the unified statement is equivalent to [s],
   /// and if [combine] returns E2 the unified statement is equivalence to [t].
   ///
   /// It is guaranteed that no side effects occur between the beginning of the
@@ skipping 51 matching lines @@
     if (e1 == e2) { // Detect same variable reference
       // TODO(asgerf): This might turn the variable into a single-use,
       // but we currently don't discover this.
       return true;
     }
     if (e1 is Constant && e2 is Constant) {
       return e1.value == e2.value;
     }
     return false;
   }
+
+  /// Try to collapse nested ifs using && and || expressions.
+  /// For example:
+  ///
+  ///   if (E1) { if (E2) S else break L } else break L
+  ///     ==>
+  ///   if (E1 && E2) S else break L
+  ///
+  /// [branch1] and [branch2] control the position of the S statement.
+  ///
+  /// Returns true if another collapse redex might have been introduced.
+  bool tryCollapseIf(If outerIf, bool branch1, bool branch2) {

[Kevin Millikin (Google), 2014/05/19 11:36:41]

I don't think the caller should have to enumerate the possibilities for the
pattern.  It seems like a detail of the specific pattern leaking out to the call
site (is it ever useful to leave off a variation?).

I'd rather have this function handle the possibilities.  I'm not sure what's
best:

bool tryCollapseIf(If outerIf) {
  for (bool outerPolarity in [true, false]) {
    ...
  }
}

bool tryCollapseIf(If outerIf) {
  bool outerPolarity = true;
  do {
    ...
    outerPolarity = !outerPolarity;
  } while (!outerPolarity);  // Yuck?
}

or something else.

+    // NOTE: We name variables here as if S is in the then-then position.
+    Statement outerThen = getBranch(outerIf, branch1);
+    Statement outerElse = getBranch(outerIf, !branch1);
+    if (outerThen is If && outerElse is Break) {
+      If innerIf = outerThen;
+      Statement innerThen = getBranch(innerIf, branch2);
+      Statement innerElse = getBranch(innerIf, !branch2);
+      if (innerElse is Break && innerElse.target == outerElse.target) {
+        // We always put S in the then branch of the result, and adjust the
+        // condition expression if S was actually found in the else branch(es).
+        outerIf.condition = new LogicalOperator.and(
+            makeCondition(outerIf.condition, branch1),
+            makeCondition(innerIf.condition, branch2));
+        outerIf.thenStatement = innerThen;
+        --innerElse.target.breakCount;
+
+        // Try to inline the remaining break
+        environment.add(null); // Do not propagate impure definitions
+        outerIf.elseStatement = visitStatement(outerElse);
+        environment.removeLast();
+
+        return outerIf.elseStatement is If && innerThen is Break;
+      }
+    }
+    return false;
+  }
+
+  Expression makeCondition(Expression e, bool polarity) {
+    return polarity ? e : new Not(e);
+  }
+
+  Statement getBranch(If node, bool polarity) {
+    return polarity ? node.thenStatement : node.elseStatement;
+  }
 }
 
+
+
+/// Rewrites logical expressions to be more compact.
+///
+/// In this class an expression is said to occur in "boolean context" if
+/// its result is immediately applied to boolean conversion.
+///
+/// IF STATEMENTS:
+///
+/// We apply the following two rule to [If] statements (see [visitIf]).

[Kevin Millikin (Google), 2014/05/19 11:36:41]

two rule ==> rules

+///
+///   if (E) {} else S  ==>  if (!E) S else {}    (else can be omitted)
+///   if (!E) S1 else S2  ==>  if (E) S2 else S1  (unless previous rule applied)
+///
+/// NEGATION:
+///
+/// De Morgan's Laws are used to rewrite negations of logical operators so
+/// negations are closer to the root:
+///
+///   !x && !y  -->  !(x || y)
+///
+/// This is to enable other rewrites, such branch swapping in an if. In some

[Kevin Millikin (Google), 2014/05/19 11:36:41]

such branch ==> such as branch

+/// contexts, the rule is reversed because we do not expect to apply a rewrite
+/// rule to the result. For example:
+///
+///   z = !(x || y)  ==>  z = !x && !y;
+///
+/// CONDITIONALS:
+///
+/// Conditionals with boolean constant operands occur frequently in the input.
+/// They can often the re-written to logical operators, for instance:
+///
+///   if (x ? y : false) S1 else S2
+///     ==>
+///   if (x && y) S1 else S2
+///
+/// Conditionals are tricky to rewrite when they occur out of boolean context.
+/// Here we must apply more conservative rules, such as:
+///
+///   x ? true : false  ==>  !!x
+///
+/// If an operand is known to be a boolean, we can introduce a logical operator:
+///
+///   x ? y : false  ==>  x && y   (if y is known to be a boolean)
+///
+/// The following sequence of rewrites demonstrates the merit of these rules:
+///
+///   x ? (y ? true : false) : false
+///   x ? !!y : false   (double negation introduced by [toBoolean])
+///   x && !!y          (!!y validated by [isBooleanValued])
+///   x && y            (double negation removed by [putInBooleanContext])
+///
+class LogicalRewriter extends Visitor<Statement, Expression> {
+
+  /// Statement to be executed next by natural fallthrough. Although fallthrough
+  /// is not introduced in this phase, we need to reason about fallthrough when
+  /// evaluating the benefit of swapping the branches of an [If].
+  Statement fallthrough;
+
+  void rewrite(FunctionDefinition definition) {
+    definition.body = visitStatement(definition.body);
+  }
+
+  Statement visitLabeledStatement(LabeledStatement node) {
+    Statement savedFallthrough = fallthrough;
+    fallthrough = node.next;
+    node.body = visitStatement(node.body);
+    fallthrough = savedFallthrough;
+    node.next = visitStatement(node.next);
+    return node;
+  }
+
+  Statement visitAssign(Assign node) {
+    node.definition = visitExpression(node.definition);
+    node.next = visitStatement(node.next);
+    return node;
+  }
+
+  Statement visitReturn(Return node) {
+    node.value = visitExpression(node.value);
+    return node;
+  }
+
+  Statement visitBreak(Break node) {
+    return node;
+  }
+
+  bool isFallthroughBreak(Statement node) {
+    return node is Break && node.target.binding.next == fallthrough;
+  }
+
+  Statement visitIf(If node) {
+    // If one of the branches is empty (i.e. just a fallthrough), then that
+    // branch should preferrably be the 'else' so we won't have to print it.
+    // In other words, we wish to perform this rewrite:
+    //   if (E) {} else {S}
+    //     ==>
+    //   if (!E) {S}
+    // In the tree language, empty statements do not exist yet, so we must check
+    // if one branch contains a break that can be eliminated by fallthrough.
+
+    // Swap branches if then is a fallthrough break.
+    if (isFallthroughBreak(node.thenStatement)) {
+      node.condition = new Not(node.condition);
+      Statement tmp = node.thenStatement;
+      node.thenStatement = node.elseStatement;
+      node.elseStatement = tmp;
+    }
+
+    // Can the else part be eliminated?
+    // (Either due to the above swap or if the break was already there).
+    bool emptyElse = isFallthroughBreak(node.elseStatement);
+
+    node.condition = makeCondition(node.condition, true, liftNots: !emptyElse);
+    node.thenStatement = visitStatement(node.thenStatement);
+    node.elseStatement = visitStatement(node.elseStatement);
+
+    // If neither branch is empty, eliminate a negation in the condition
+    // if (!E) S1 else S2
+    //   ==>
+    // if (E) S2 else S1
+    if (!emptyElse && node.condition is Not) {
+      node.condition = (node.condition as Not).operand;
+      Statement tmp = node.thenStatement;
+      node.thenStatement = node.elseStatement;
+      node.elseStatement = tmp;
+    }
+
+    return node;
+  }
+
+  Statement visitExpressionStatement(ExpressionStatement node) {
+    // TODO(asgerf): in non-checked mode we can remove Not from the expression.
+    node.expression = visitExpression(node.expression);
+    node.next = visitStatement(node.next);
+    return node;
+  }
+
+
+  Expression visitVariable(Variable node) {
+    return node;
+  }
+
+  Expression visitInvokeStatic(InvokeStatic node) {
+    for (int i=0; i<node.arguments.length; i++) {

[Kevin Millikin (Google), 2014/05/19 11:36:41]

Spaces around = and <.  Also below.

Maybe we should introduce a rewriting visitor class that does the left-to-right
rewriting visit of Tree by default.  What do you think?

[asgerf, 2014/05/19 13:29:07]

Good idea. I'll look at that in another CL.

+      node.arguments[i] = visitExpression(node.arguments[i]);
+    }
+    return node;
+  }
+
+  Expression visitInvokeMethod(InvokeMethod node) {
+    node.receiver = visitExpression(node.receiver);
+    for (int i=0; i<node.arguments.length; i++) {
+      node.arguments[i] = visitExpression(node.arguments[i]);
+    }
+    return node;
+  }
+
+  Expression visitInvokeConstructor(InvokeConstructor node) {
+    for (int i=0; i<node.arguments.length; i++) {
+      node.arguments[i] = visitExpression(node.arguments[i]);
+    }
+    return node;
+  }
+
+  Expression visitConcatenateStrings(ConcatenateStrings node) {
+    for (int i=0; i<node.arguments.length; i++) {
+      node.arguments[i] = visitExpression(node.arguments[i]);
+    }
+    return node;
+  }
+
+  Expression visitConstant(Constant node) {
+    return node;
+  }
+
+  Expression visitNot(Not node) {
+    return toBoolean(makeCondition(node.operand, false, liftNots: false));
+  }
+
+  Expression visitConditional(Conditional node) {
+    // node.condition will be visited after the then and else parts, because its
+    // polarity depends on what rewrite we use.
+    node.thenExpression = visitExpression(node.thenExpression);
+    node.elseExpression = visitExpression(node.elseExpression);
+
+    // In the following, we must take care not to eliminate or introduce a
+    // boolean conversion.
+
+    // x ? true : false --> !!x
+    if (isTrue(node.thenExpression) && isFalse(node.elseExpression)) {
+      return toBoolean(makeCondition(node.condition, true, liftNots: false));
+    }
+    // x ? false : true --> !x
+    if (isFalse(node.thenExpression) && isTrue(node.elseExpression)) {
+      return toBoolean(makeCondition(node.condition, false, liftNots: false));
+    }
+
+    // x ? y : false ==> x && y  (if y is known to be a boolean)
+    if (isBooleanValued(node.thenExpression) && isFalse(node.elseExpression)) {
+      return new LogicalOperator.and(
+          makeCondition(node.condition, true, liftNots:false),
+          putInBooleanContext(node.thenExpression));
+    }
+    // x ? y : true ==> !x || y  (if y is known to be a boolean)
+    if (isBooleanValued(node.thenExpression) && isTrue(node.elseExpression)) {
+      return new LogicalOperator.or(
+          makeCondition(node.condition, false, liftNots: false),
+          putInBooleanContext(node.thenExpression));
+    }
+    // x ? true : y ==> x || y  (if y if known to be boolean)
+    if (isBooleanValued(node.elseExpression) && isTrue(node.thenExpression)) {
+      return new LogicalOperator.or(
+          makeCondition(node.condition, true, liftNots: false),
+          putInBooleanContext(node.elseExpression));
+    }
+    // x ? false : y ==> !x && y  (if y is known to be a boolean)
+    if (isBooleanValued(node.elseExpression) && isTrue(node.thenExpression)) {
+      return new LogicalOperator.and(
+          makeCondition(node.condition, false, liftNots: false),
+          putInBooleanContext(node.elseExpression));
+    }
+
+    node.condition = makeCondition(node.condition, true);
+
+    // !x ? y : z ==> x ? z : y
+    if (node.condition is Not) {
+      node.condition = (node.condition as Not).operand;
+      Expression tmp = node.thenExpression;
+      node.thenExpression = node.elseExpression;
+      node.elseExpression = tmp;
+    }
+
+    return node;
+  }
+  Expression visitLogicalOperator(LogicalOperator node) {

[Kevin Millikin (Google), 2014/05/19 11:36:41]

Blank line between methods.

+    node.left = makeCondition(node.left, true);
+    node.right = makeCondition(node.right, true);
+    return node;
+  }
+
+  /// True if the given expression is known to evaluate to a boolean.
+  /// This will not recursively traverse [Conditional] expressions, but if
+  /// applied to the result of [visitExpression] conditionals will have been
+  /// rewritten anyway.
+  bool isBooleanValued(Expression e) {
+    return isTrue(e) || isFalse(e) || e is Not || e is LogicalOperator;
+  }
+
+  /// Rewrite an expression that was originally processed in a non-boolean
+  /// context.
+  Expression putInBooleanContext(Expression e) {
+    if (e is Not && e.operand is Not) {
+      return (e.operand as Not).operand;
+    } else {
+      return e;
+    }
+  }
+
+  /// Forces a boolean conversion of the given expression.
+  Expression toBoolean(Expression e) {
+    if (isBooleanValued(e))
+      return e;
+    else
+      return new Not(new Not(e));
+  }
+
+  /// Creates an equivalent boolean expression. The expression must occur in a

[Kevin Millikin (Google), 2014/05/19 11:36:41]

equivalent ==> equivalent simplified, perhaps?

Reasoning about the code below seems a bit easier if we state that the returned
expression is never a double negation Not(Not(...)).  Do you want to 'promise'
that?

+  /// context where its result is immediately subject to boolean conversion.
+  /// If [polarity] if false, the negated condition will be created instead.
+  /// If [liftNots] is true (default) then Not expressions will be lifted toward
+  /// the root the condition so they can be eliminated by the caller.
+  Expression makeCondition(Expression e, bool polarity, {bool liftNots:true}) {
+    if (e is Not) {
+      // !!E ==> E
+      return makeCondition(e.operand, !polarity, liftNots: liftNots);
+    }
+    if (e is LogicalOperator) {
+      // If polarity=false, then apply the rewrite !(x && y) ==> !x || !y
+      e.left = makeCondition(e.left, polarity);
+      e.right = makeCondition(e.right, polarity);
+      if (!polarity) {
+        e.isAnd = !e.isAnd;
+      }
+      // !x && !y ==> !(x || y)  (only if lifting nots)
+      if (e.left is Not && e.right is Not && liftNots) {
+        e.left = (e.left as Not).operand;
+        e.right = (e.right as Not).operand;
+        e.isAnd = !e.isAnd;
+        return new Not(e);
+      }
+      return e;
+    }
+    if (e is Conditional) {
+      // x ? true : false ==> x
+      if (isTrue(e.thenExpression) && isFalse(e.elseExpression)) {
+        return makeCondition(e.condition, polarity);
+      }
+      // x ? false : true ==> !x
+      if (isFalse(e.thenExpression) && isTrue(e.elseExpression)) {
+        return makeCondition(e.condition, !polarity);
+      }
+      // x ? true : y  ==> x || y

[Kevin Millikin (Google), 2014/05/19 11:36:41]

I could well be missing something here, but I think that if !polarity, this
needs to be &&.  That is, !x && !y.

+      if (isTrue(e.thenExpression)) {
+        return new LogicalOperator.or(
+            makeCondition(e.condition, polarity),
+            makeCondition(e.elseExpression, polarity));
+      }
+      // x ? false : y  ==> !x && y

[Kevin Millikin (Google), 2014/05/19 11:36:41]

Likewise, if !polarity this should be ||.  That is, x || !y.  Similarly for the
two other cases below.

+      if (isFalse(e.thenExpression)) {
+        return new LogicalOperator.and(
+            makeCondition(e.condition, !polarity),
+            makeCondition(e.elseExpression, polarity));
+      }
+      // x ? y : true  ==> !x || y
+      if (isTrue(e.elseExpression)) {
+        return new LogicalOperator.or(
+            makeCondition(e.condition, !polarity),
+            makeCondition(e.thenExpression, polarity));
+      }
+      // x ? y : false  ==> x && y
+      if (isFalse(e.elseExpression)) {
+        return new LogicalOperator.and(
+            makeCondition(e.condition, polarity),
+            makeCondition(e.thenExpression, polarity));
+      }
+
+      // Rewrite individual subconditions
+      // Handle polarity by: !(x ? y : z) ==> x ? !y : !z
+      e.condition = makeCondition(e.condition, true);
+      e.thenExpression = makeCondition(e.thenExpression, polarity);
+      e.elseExpression = makeCondition(e.elseExpression, polarity);
+
+      // !x ? y : z ==> x ? z : y
+      if (e.condition is Not) {
+        e.condition = (e.condition as Not).operand;
+        Expression tmp = e.thenExpression;
+        e.thenExpression = e.elseExpression;
+        e.elseExpression = tmp;
+      }
+      // x ? !y : !z ==> !(x ? y : z)  (only if lifting nots)
+      if (e.thenExpression is Not && e.elseExpression is Not && liftNots) {
+        e.thenExpression = (e.thenExpression as Not).operand;
+        e.elseExpression = (e.elseExpression as Not).operand;
+        return new Not(e);
+      }
+      return e;
+    }
+    if (e is Constant && e.value is dart2js.BoolConstant) {
+      // !true ==> false
+      if (!polarity) {
+        e.value = (e.value as dart2js.BoolConstant).negate();
+      }
+      return e;
+    }
+    e = visitExpression(e);
+    return polarity ? e : new Not(e);
+  }
+
+  bool isTrue(Expression e) {
+    return e is Constant && e.value is dart2js.TrueConstant;
+  }
+
+  bool isFalse(Expression e) {
+    return e is Constant && e.value is dart2js.FalseConstant;
+  }
+
+}