pkg/compiler/lib/src/js/placeholder_safety.dart

// Copyright (c) 2015, 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 js.safety;

import "js.dart" as js;

typedef bool PositionPredicate(int position);

/// PlaceholderSafetyAnalysis determines which placeholders in a JavaScript
/// template may be replaced with an arbitrary expression. Placeholders may be
/// replaced with an arbitrary expression providied the template ensures the
/// placeholders are evaluated in the same left-to-right order with no
/// additional effects interleaved.
///
/// The result is semi-conservative, giving reasonable results for many simple
/// JS fragments. The non-conservative part is the assumption that arithmetic
/// operators are used on 'good' operands that do not force arbitrary code to be
/// executed via conversions (valueOf() and toString() methods).
class PlaceholderSafetyAnalysis extends js.BaseVisitor<int> {
  final PositionPredicate isNullableInput;
  int nextPosition = 0;
  int maxSafePosition = -1;
  bool safe = true;

  // We do a crude abstract interpretation to find operations that might throw
  // exceptions. The possible values of expressions are represented by
  // integers. Small non-negative integers 0, 1, 2, ... represent the values of
  // the placeholders. Other values are:
  static const int NONNULL_VALUE = -1; // Unknown but not null.
  static const int UNKNOWN_VALUE = -2; // Unknown and might be null.

  PlaceholderSafetyAnalysis._(this.isNullableInput);

  /// Returns the number of placeholders that can be substituted into the
  /// template AST [node] without changing the order of observable effects.
  /// [isNullableInput] is a function that takes the 0-based index of a
  /// placeholder and returns `true` if expression at run time may be null, and
  /// `false` if the value is never null.
  static int analyze(js.Node node, PositionPredicate isNullableInput) {
    PlaceholderSafetyAnalysis analysis =
        new PlaceholderSafetyAnalysis._(isNullableInput);
    analysis.visit(node);
    return analysis.maxSafePosition + 1;
  }

  bool canBeNull(int value) {
    if (value == NONNULL_VALUE) return false;
    if (value == UNKNOWN_VALUE) return true;
    return isNullableInput(value);
  }

  int unsafe(int value) {
    safe = false;
    return value;
  }

  int visit(js.Node node) {
    return node.accept(this);
  }

  int visitNode(js.Node node) {
    safe = false;
    super.visitNode(node);
    return UNKNOWN_VALUE;
  }

  int visitLiteralNull(js.LiteralNull node) {
    return UNKNOWN_VALUE;
  }

  int visitLiteral(js.Literal node) {
    return NONNULL_VALUE;
  }

  int handleInterpolatedNode(js.InterpolatedNode node) {
    assert(node.isPositional);
    int position = nextPosition++;
    if (safe) maxSafePosition = position;
    return position;
  }

  int visitInterpolatedExpression(js.InterpolatedExpression node) {
    return handleInterpolatedNode(node);
  }

  int visitInterpolatedLiteral(js.InterpolatedLiteral node) {
    return handleInterpolatedNode(node);
  }

  int visitInterpolatedSelector(js.InterpolatedSelector node) {
    return handleInterpolatedNode(node);
  }

  int visitInterpolatedStatement(js.InterpolatedStatement node) {
    return handleInterpolatedNode(node);
  }

  int visitInterpolatedDeclaration(js.InterpolatedDeclaration node) {
    return handleInterpolatedNode(node);
  }

  int visitObjectInitializer(js.ObjectInitializer node) {
    for (js.Property property in node.properties) {
      visit(property);
    }
    return NONNULL_VALUE;
  }

  int visitProperty(js.Property node) {
    visit(node.name);
    visit(node.value);
    return UNKNOWN_VALUE;
  }

  int visitArrayInitializer(js.ArrayInitializer node) {
    node.elements.forEach(visit);
    return NONNULL_VALUE;
  }

  int visitArrayHole(js.ArrayHole node) {
    return UNKNOWN_VALUE;
  }

  int visitAccess(js.PropertyAccess node) {
    int first = visit(node.receiver);
    int second = visit(node.selector);
    // TODO(sra): If the JS is annotated as never throwing, we can avoid this.
    if (canBeNull(first)) safe = false;
    return UNKNOWN_VALUE;
  }

  int visitAssignment(js.Assignment node) {
    js.Expression left = node.leftHandSide;
    js.Expression right = node.value;

    int leftToRight() {
      visit(left);
      visit(right);
      return UNKNOWN_VALUE;
    }

    if (left is js.InterpolatedNode) {
      // A bare interpolated expression should not be the LHS of an assignment.
      safe = false;
      return leftToRight();
    }

    // Assignment operators dereference the LHS before evaluating the RHS.
    if (node.op != null) return leftToRight();

    // Assignment (1) evaluates the LHS as a Reference `lval`, (2) evaluates the
    // RHS as a value, (3) dereferences the `lval` in PutValue.
    if (left is js.VariableReference) {
      int value = visit(right);
      // Assignment could change an observed global or cause a ReferenceError.
      safe = false;
      return value;
    }
    if (left is js.PropertyAccess) {
      // "a.b.x = c.y" gives a TypeError for null values in this order: `a`,
      // `c`, `a.b`.
      int receiver = visit(left.receiver);
      int selector = visit(left.selector);
      int value = visit(right);
      if (canBeNull(receiver)) safe = false;
      return value;
    }
    // Be conserative with unrecognized LHS expressions.
    safe = false;
    return leftToRight();
  }

  int visitCall(js.Call node) {
    // TODO(sra): Recognize JavaScript built-ins like
    // 'Object.prototype.hasOwnProperty.call'.
    visit(node.target);
    node.arguments.forEach(visit);
    return unsafe(UNKNOWN_VALUE);
  }

  int visitNew(js.New node) {
    visit(node.target);
    node.arguments.forEach(visit);
    return unsafe(NONNULL_VALUE);
  }

  int visitBinary(js.Binary node) {
    switch (node.op) {
      // We make the non-conservative assumption that these operations are not
      // used in ways that force calling arbitrary code via valueOf() or
      // toString().
      case "*":
      case "/":
      case "%":
      case "+":
      case "-":
      case "<<":
      case ">>":
      case ">>>":
      case "<":
      case ">":
      case "<=":
      case ">=":
      case "==":
      case "===":
      case "!=":
      case "!==":
      case "&":
      case "^":
      case "|":
        int left = visit(node.left);
        int right = visit(node.right);
        return NONNULL_VALUE; // Number, String, Boolean.

      case ',':
        int left = visit(node.left);
        int right = visit(node.right);
        return right;

      case "&&":
      case "||":
        int left = visit(node.left);
        // TODO(sra): Might be safe, e.g.  "x || 0".
        safe = false;
        int right = visit(node.right);
        return UNKNOWN_VALUE;

      case "instanceof":
      case "in":
        int left = visit(node.left);
        int right = visit(node.right);
        return UNKNOWN_VALUE;

      default:
        return unsafe(UNKNOWN_VALUE);
    }
  }

  int visitConditional(js.Conditional node) {
    int cond = visit(node.condition);
    // TODO(sra): Might be safe, e.g.  "# ? 1 : 2".
    safe = false;
    int thenValue = visit(node.then);
    int elseValue = visit(node.otherwise);
    return UNKNOWN_VALUE;
  }

  int visitThrow(js.Throw node) {
    visit(node.expression);
    return unsafe(UNKNOWN_VALUE);
  }

  int visitPrefix(js.Prefix node) {
    if (node.op == 'typeof') {
      // "typeof a" first evaluates to a Reference. If the Reference is to a
      // variable that is not present, "undefined" is returned without
      // dereferencing.
      if (node.argument is js.VariableUse) return NONNULL_VALUE; // A string.
    }

    visit(node.argument);

    switch (node.op) {
      case '+':
      case '-':
      case '!':
      case '~':
        // Non-conservative assumption that these operators are used on values
        // that do not call arbitrary code via valueOf() or toString().
        return NONNULL_VALUE;

      case 'typeof':
        return NONNULL_VALUE; // Always a string.

      case 'void':
        return UNKNOWN_VALUE;

      case '--':
      case '++':
        return NONNULL_VALUE; // Always a number.

      default:
        safe = false;
        return UNKNOWN_VALUE;
    }
  }

  int visitPostfix(js.Postfix node) {
    assert(node.op == '--' || node.op == '++');
    visit(node.argument);
    return NONNULL_VALUE; // Always a number, even for "(a=null, a++)".
  }

  int visitVariableUse(js.VariableUse node) {
    // We could get a ReferenceError unless the variable is in scope.  For JS
    // fragments, the only use of VariableUse outside a `function(){...}` should
    // be for global references. Certain global names are almost certainly not
    // reference errors, e.g 'Array'.
    switch (node.name) {
      case 'Array':
      case 'Date':
      case 'Function':
      case 'Math':
      case 'Number':
      case 'Object':
      case 'RegExp':
      case 'String':
      case 'self':
      case 'window':
        return NONNULL_VALUE;
      default:
        return unsafe(UNKNOWN_VALUE);
    }
  }

  int visitFun(js.Fun node) {
    bool oldSafe = safe;
    int oldNextPosition = nextPosition;
    visit(node.body);
    // Creating a function has no effect on order unless there are embedded
    // placeholders.
    safe = (nextPosition == oldNextPosition) && oldSafe;
    return NONNULL_VALUE;
  }
}