dart2js cps: Use JS semantics for logical operators in the tree IR.

pkg/compiler/lib/src/tree_ir/optimization/logical_rewriter.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 tree_ir.optimization.logical_rewriter;
 
 import '../tree_ir_nodes.dart';
 import 'optimization.dart' show Pass;
 import '../../constants/values.dart' as values;
 
-// TODO(asgerf): Update this class to use JS semantics for && and ||.
-
 /// Rewrites logical expressions to be more compact in the Tree IR.
 ///
 /// 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 rules to [If] statements (see [visitIf]).
 ///
 ///   if (E) {} else S  ==>  if (!E) S else {}    (else can be omitted)
@@ skipping 19 matching lines @@
 ///
 ///   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:
+/// If the possible falsy values of the condition are known, we can sometimes
+/// 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])
+///   !x ? y : false  ==>  !x && y
 ///
 class LogicalRewriter extends RecursiveTransformer
                       implements Pass {
   String get passName => 'Logical rewriter';
 
   @override
   void rewrite(FunctionDefinition node) {
     node.body = visitStatement(node.body);
   }
 
@@ skipping 15 matching lines @@
     node.next = visitStatement(node.next);
     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.
+    // branch should preferably 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);
@@ skipping 28 matching lines @@
     node.condition = makeCondition(node.condition, true, liftNots: false);
     node.body = visitStatement(node.body);
     node.next = visitStatement(node.next);
     return node;
   }
 
   Expression visitNot(Not node) {
     return toBoolean(makeCondition(node.operand, false, liftNots: false));
   }
 
+  /// True if the only possible falsy return value of [condition] is [value].
+  ///
+  /// If [value] is `null` or a truthy value, false is returned. This is to make
+  /// pattern matching more convenient.
+  bool matchesFalsyValue(Expression condition, values.ConstantValue value) {
+    if (value == null) return false;
+    // TODO(asgerf): Here we could really use some more type information,
+    //               this is just the best we can do at the moment.
+    return isBooleanValued(condition) && value.isFalse;
+  }
+
+  /// True if the only possible truthy return value of [condition] is [value].
+  ///
+  /// If [value] is `null` or a falsy value, false is returned. This is to make
+  /// pattern matching more convenient.
+  bool matchesTruthyValue(Expression condition, values.ConstantValue value) {
+    if (value == null) return false;
+    // TODO(asgerf): Again, more type information could really beef this up.
+    return isBooleanValued(condition) && value.isTrue;
+  }
+
+  values.ConstantValue getConstant(Expression exp) {
+    return exp is Constant ? exp.value : null;
+  }
+
   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)) {
+    // x ? y : false ==> x && y  (if x is truthy or false)
+    // x ? y : null  ==> x && y  (if x is truthy or null)
+    // x ? y : 0     ==> x && y  (if x is truthy or zero) (and so on...)
+    if (matchesFalsyValue(node.condition, getConstant(node.elseExpression))) {
       return new LogicalOperator.and(
-          makeCondition(node.condition, true, liftNots:false),
-          putInBooleanContext(node.thenExpression));
+          visitExpression(node.condition),
+          node.thenExpression);
     }
-    // x ? y : true ==> !x || y  (if y is known to be a boolean)
-    if (isBooleanValued(node.thenExpression) && isTrue(node.elseExpression)) {
+    // x ? true : y ==> x || y  (if x is falsy or true)
+    // x ? 1    : y ==> x || y  (if x is falsy or one) (and so on...)
+    if (matchesTruthyValue(node.condition, getConstant(node.thenExpression))) {
       return new LogicalOperator.or(
-          makeCondition(node.condition, false, liftNots: false),
-          putInBooleanContext(node.thenExpression));
+          visitExpression(node.condition),
+          node.elseExpression);
     }
-    // x ? true : y ==> x || y  (if y if known to be boolean)
-    if (isBooleanValued(node.elseExpression) && isTrue(node.thenExpression)) {
+    // x ? y : true ==> !x || y
+    if (isTrue(node.elseExpression)) {
       return new LogicalOperator.or(
-          makeCondition(node.condition, true, liftNots: false),
-          putInBooleanContext(node.elseExpression));
+          toBoolean(makeCondition(node.condition, false, liftNots: false)),
+          node.thenExpression);
     }
-    // x ? false : y ==> !x && y  (if y is known to be a boolean)
-    if (isBooleanValued(node.elseExpression) && isFalse(node.thenExpression)) {
+    // x ? false : y ==> !x && y
+    if (isFalse(node.thenExpression)) {
       return new LogicalOperator.and(
-          makeCondition(node.condition, false, liftNots: false),
-          putInBooleanContext(node.elseExpression));
+          toBoolean(makeCondition(node.condition, false, liftNots: false)),
+          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) {
-    node.left = makeCondition(node.left, true);
-    node.right = makeCondition(node.right, true);
+    node.left = visitExpression(node.left);
+    node.right = visitExpression(node.right);
     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) ||
@@ skipping 31 matching lines @@
       case BuiltinOperator.NumLe:
       case BuiltinOperator.NumGt:
       case BuiltinOperator.NumGe:
         return null;
 
       default:
         return null;
     }
   }
 
-  /// 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
   /// 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.
+  /// the root of 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) {
@@ skipping 104 matching lines @@
 
   Expression makeOr(Expression e1, Expression e2, {bool liftNots: true}) {
     if (e1 is Not && e2 is Not && liftNots) {
       return new Not(new LogicalOperator.and(e1.operand, e2.operand));
     } else {
       return new LogicalOperator.or(e1, e2);
     }
   }
 }