// 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;

/// 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)
///   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 as branch swapping in an if. In some
/// 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 the possible falsy values of the condition are known, we can sometimes
/// introduce a logical operator:
///
///   !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);
  }

  final FallthroughStack fallthrough = new FallthroughStack();

  @override
  void visitInnerFunction(FunctionDefinition node) {
    new LogicalRewriter().rewrite(node);
  }

  /// True if the given statement is equivalent to its fallthrough semantics.
  ///
  /// This means it will ultimately translate to an empty statement.
  bool isFallthrough(Statement node) {
    return node is Break && isFallthroughBreak(node) ||
           node is Continue && isFallthroughContinue(node) ||
           node is Return && isFallthroughReturn(node);
  }

  bool isFallthroughBreak(Break node) {
    Statement target = fallthrough.target;
    return node.target.binding.next == target ||
           target is Break && target.target == node.target;
  }

  bool isFallthroughContinue(Continue node) {
    Statement target = fallthrough.target;
    return node.target.binding == target ||
           target is Continue && target.target == node.target;
  }

  bool isFallthroughReturn(Return node) {
    return isNull(node.value) && fallthrough.target == null;
  }

  bool isTerminator(Statement node) {
    return (node is Jump || node is Return) && !isFallthrough(node) ||
           (node is ExpressionStatement && node.next is Unreachable) ||
           node is Throw;
  }

  Statement visitIf(If node) {
    // If one of the branches is empty (i.e. just a fallthrough), then that
    // 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.

    // Rewrite each branch and keep track of which ones might fall through.
    int usesBefore = fallthrough.useCount;
    node.thenStatement = visitStatement(node.thenStatement);
    int usesAfterThen = fallthrough.useCount;
    node.elseStatement = visitStatement(node.elseStatement);
    bool thenHasFallthrough = (fallthrough.useCount > usesBefore);
    bool elseHasFallthrough = (fallthrough.useCount > usesAfterThen);

    // Determine which branch is most beneficial as 'then' branch.
    const int THEN = 1;
    const int NEITHER = 0;
    const int ELSE = -1;
    int bestThenBranch = NEITHER;
    if (isFallthrough(node.thenStatement) &&
        !isFallthrough(node.elseStatement)) {
      // Put the empty statement in the 'else' branch.
      // if (E) {} else {S} ==> if (!E) {S}
      bestThenBranch = ELSE;
    } else if (isFallthrough(node.elseStatement) &&
               !isFallthrough(node.thenStatement)) {
      // Keep the empty statement in the 'else' branch.
      // if (E) {S} else {}
      bestThenBranch = THEN;
    } else if (thenHasFallthrough && !elseHasFallthrough) {
      // Put abrupt termination in the 'then' branch to omit 'else'.
      // if (E) {S1} else {S2; return v} ==> if (!E) {S2; return v}; S1
      bestThenBranch = ELSE;
    } else if (!thenHasFallthrough && elseHasFallthrough) {
      // Keep abrupt termination in the 'then' branch to omit 'else'.
      // if (E) {S1; return v}; S2
      bestThenBranch = THEN;
    } else if (isTerminator(node.elseStatement) &&
               !isTerminator(node.thenStatement)) {
      // Put early termination in the 'then' branch to reduce nesting depth.
      // if (E) {S}; return v ==> if (!E) return v; S
      bestThenBranch = ELSE;
    } else if (isTerminator(node.thenStatement) &&
               !isTerminator(node.elseStatement)) {
      // Keep early termination in the 'then' branch to reduce nesting depth.
      // if (E) {return v;} S
      bestThenBranch = THEN;
    }

    // Swap branches if 'else' is better as 'then'
    if (bestThenBranch == ELSE) {
      node.condition = new Not(node.condition);
      Statement tmp = node.thenStatement;
      node.thenStatement = node.elseStatement;
      node.elseStatement = tmp;
    }

    // If neither branch is better, eliminate a negation in the condition
    // if (!E) S1 else S2
    //   ==>
    // if (E) S2 else S1
    node.condition = makeCondition(node.condition, true,
                                   liftNots: bestThenBranch == NEITHER);
    if (bestThenBranch == NEITHER && 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 visitLabeledStatement(LabeledStatement node) {
    fallthrough.push(node.next);
    node.body = visitStatement(node.body);
    fallthrough.pop();
    node.next = visitStatement(node.next);
    return node;
  }

  Statement visitWhileTrue(WhileTrue node) {
    fallthrough.push(node);
    node.body = visitStatement(node.body);
    fallthrough.pop();
    return node;
  }

  Statement visitFor(For node) {
    fallthrough.push(node);
    node.condition = makeCondition(node.condition, true, liftNots: false);
    node.body = visitStatement(node.body);
    fallthrough.pop();
    node.next = visitStatement(node.next);
    return node;
  }

  Statement visitBreak(Break node) {
    if (isFallthroughBreak(node)) {
      fallthrough.use();
    }
    return node;
  }

  Statement visitContinue(Continue node) {
    if (isFallthroughContinue(node)) {
      fallthrough.use();
    }
    return node;
  }

  Statement visitReturn(Return node) {
    node.value = visitExpression(node.value);
    if (isFallthroughReturn(node)) {
      fallthrough.use();
    }
    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 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(
          visitExpression(node.condition),
          node.thenExpression);
    }
    // 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(
          visitExpression(node.condition),
          node.elseExpression);
    }
    // x ? y : true ==> !x || y
    if (isTrue(node.elseExpression)) {
      return new LogicalOperator.or(
          toBoolean(makeCondition(node.condition, false, liftNots: false)),
          node.thenExpression);
    }
    // x ? false : y ==> !x && y
    if (isFalse(node.thenExpression)) {
      return new LogicalOperator.and(
          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;
    }

    // x ? y : x ==> x && y
    if (isSameVariable(node.condition, node.elseExpression)) {
      destroyVariableUse(node.elseExpression);
      return new LogicalOperator.and(node.condition, node.thenExpression);
    }
    // x ? x : y ==> x || y
    if (isSameVariable(node.condition, node.thenExpression)) {
      destroyVariableUse(node.thenExpression);
      return new LogicalOperator.or(node.condition, node.elseExpression);
    }

    return node;
  }

  Expression visitLogicalOperator(LogicalOperator node) {
    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) ||
           e is Not ||
           e is LogicalOperator && isBooleanValuedLogicalOperator(e) ||
           e is ApplyBuiltinOperator && operatorReturnsBool(e.operator) ||
           e is TypeOperator && isBooleanValuedTypeOperator(e);
  }

  bool isBooleanValuedLogicalOperator(LogicalOperator e) {
    return isBooleanValued(e.left) && isBooleanValued(e.right);
  }

  /// True if the given operator always returns `true` or `false`.
  bool operatorReturnsBool(BuiltinOperator operator) {
    switch (operator) {
      case BuiltinOperator.StrictEq:
      case BuiltinOperator.StrictNeq:
      case BuiltinOperator.LooseEq:
      case BuiltinOperator.LooseNeq:
      case BuiltinOperator.NumLt:
      case BuiltinOperator.NumLe:
      case BuiltinOperator.NumGt:
      case BuiltinOperator.NumGe:
      case BuiltinOperator.IsNumber:
      case BuiltinOperator.IsNotNumber:
      case BuiltinOperator.IsFloor:
      case BuiltinOperator.IsNumberAndFloor:
      case BuiltinOperator.Identical:
        return true;
      default:
        return false;
    }
  }

  bool isBooleanValuedTypeOperator(TypeOperator e) {
    return e.isTypeTest;
  }

  BuiltinOperator negateBuiltin(BuiltinOperator operator) {
    switch (operator) {
      case BuiltinOperator.StrictEq: return BuiltinOperator.StrictNeq;
      case BuiltinOperator.StrictNeq: return BuiltinOperator.StrictEq;
      case BuiltinOperator.LooseEq: return BuiltinOperator.LooseNeq;
      case BuiltinOperator.LooseNeq: return BuiltinOperator.LooseEq;
      case BuiltinOperator.IsNumber: return BuiltinOperator.IsNotNumber;
      case BuiltinOperator.IsNotNumber: return BuiltinOperator.IsNumber;

      // Because of NaN, these do not have a negated form.
      case BuiltinOperator.NumLt:
      case BuiltinOperator.NumLe:
      case BuiltinOperator.NumGt:
      case BuiltinOperator.NumGe:
        return null;

      default:
        return null;
    }
  }

  /// 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 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) {
        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 ApplyBuiltinOperator && polarity == false) {
      BuiltinOperator negated = negateBuiltin(e.operator);
      if (negated != null) {
        e.operator = negated;
        return visitExpression(e);
      } else {
        return new Not(visitExpression(e));
      }
    }
    if (e is Conditional) {
      // Handle polarity by: !(x ? y : z) ==> x ? !y : !z
      // Rewrite individual branches now. The condition will be rewritten
      // when we know what polarity to use (depends on which rewrite is used).
      e.thenExpression = makeCondition(e.thenExpression, polarity);
      e.elseExpression = makeCondition(e.elseExpression, polarity);

      // x ? true : false ==> x
      if (isTrue(e.thenExpression) && isFalse(e.elseExpression)) {
        return makeCondition(e.condition, true, liftNots: liftNots);
      }
      // x ? false : true ==> !x
      if (isFalse(e.thenExpression) && isTrue(e.elseExpression)) {
        return makeCondition(e.condition, false, liftNots: liftNots);
      }
      // x ? true : y  ==> x || y
      if (isTrue(e.thenExpression)) {
        return makeOr(makeCondition(e.condition, true),
                      e.elseExpression,
                      liftNots: liftNots);
      }
      // x ? false : y  ==> !x && y
      if (isFalse(e.thenExpression)) {
        return makeAnd(makeCondition(e.condition, false),
                       e.elseExpression,
                       liftNots: liftNots);
      }
      // x ? y : true  ==> !x || y
      if (isTrue(e.elseExpression)) {
        return makeOr(makeCondition(e.condition, false),
                      e.thenExpression,
                      liftNots: liftNots);
      }
      // x ? y : false  ==> x && y
      if (isFalse(e.elseExpression)) {
        return makeAnd(makeCondition(e.condition, true),
                       e.thenExpression,
                       liftNots: liftNots);
      }

      e.condition = makeCondition(e.condition, true);

      // !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);
      }

      // x ? y : x ==> x && y
      if (isSameVariable(e.condition, e.elseExpression)) {
        destroyVariableUse(e.elseExpression);
        return new LogicalOperator.and(e.condition, e.thenExpression);
      }
      // x ? x : y ==> x || y
      if (isSameVariable(e.condition, e.thenExpression)) {
        destroyVariableUse(e.thenExpression);
        return new LogicalOperator.or(e.condition, e.elseExpression);
      }

      return e;
    }
    if (e is Constant && e.value.isBool) {
      // !true ==> false
      if (!polarity) {
        values.BoolConstantValue value = e.value;
        return new Constant.bool(value.negate());
      }
      return e;
    }
    e = visitExpression(e);
    return polarity ? e : new Not(e);
  }

  bool isNull(Expression e) {
    return e is Constant && e.value.isNull;
  }

  bool isTrue(Expression e) {
    return e is Constant && e.value.isTrue;
  }

  bool isFalse(Expression e) {
    return e is Constant && e.value.isFalse;
  }

  Expression makeAnd(Expression e1, Expression e2, {bool liftNots: true}) {
    if (e1 is Not && e2 is Not && liftNots) {
      return new Not(new LogicalOperator.or(e1.operand, e2.operand));
    } else {
      return new LogicalOperator.and(e1, e2);
    }
  }

  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);
    }
  }

  /// True if [e2] is known to return the same value as [e1] 
  /// (with no additional side effects) if evaluated immediately after [e1].
  /// 
  /// Concretely, this is true if [e1] and [e2] are uses of the same variable,
  /// or if [e2] is a use of a variable assigned by [e1].
  bool isSameVariable(Expression e1, Expression e2) {
    if (e1 is VariableUse) {
      return e2 is VariableUse && e1.variable == e2.variable;
    } else if (e1 is Assign) {
      return e2 is VariableUse && e1.variable == e2.variable;
    }
    return false;
  }

  void destroyVariableUse(VariableUse node) {
    --node.variable.readCount;
  }
}