Safety analysis for JS template placeholders.

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

Index: pkg/compiler/lib/src/js/placeholder_safety.dart
diff --git a/pkg/compiler/lib/src/js/placeholder_safety.dart b/pkg/compiler/lib/src/js/placeholder_safety.dart
new file mode 100644
index 0000000000000000000000000000000000000000..b3632b04b89b9bb537bd7f57577f23fbf6e97806
--- /dev/null
+++ b/pkg/compiler/lib/src/js/placeholder_safety.dart
@@ -0,0 +1,293 @@
+// 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 JavaScriptExpressionPredicate(js.Expression expression);
+
+/// 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<NativeThrowBehavior> {

[asgerf, 2015/12/08 11:40:37]

Extends BaseVisitor<NativeThrowBehavior> but all the visits return int.

[sra1, 2015/12/08 20:54:04]

Done.

+  final JavaScriptExpressionPredicate 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,
+                     JavaScriptExpressionPredicate 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;
+    print(node);

[asgerf, 2015/12/08 11:40:37]

Renegade print statement

[sra1, 2015/12/08 20:54:04]

Done.

+    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) {
+    safe = false;

[asgerf, 2015/12/08 11:40:37]

Why safe = false here?

[sra1, 2015/12/08 20:54:04]

Not sure why. It would occur only in the body of a function.

+    return handleInterpolatedNode(node);
+  }
+
+  int visitInterpolatedDeclaration(js.InterpolatedDeclaration node) {
+    safe = false;
+    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 visitAccess(js.PropertyAccess node) {
+    int first = visit(node.receiver);
+    int second = visit(node.selector);
+    if (canBeNull(first)) safe = false;

[asgerf, 2015/12/08 11:40:37]

If the JS fragment is annotated with throws:never we could avoid this. Might we
worth adding the throws annotation as an argument.

[sra1, 2015/12/08 20:54:04]

Acknowledged.

+    return UNKNOWN_VALUE;
+  }
+
+  int visitAssignment(js.Assignment node) {
+    js.Expression target = node.leftHandSide;
+
+    int leftToRight() {
+      visit(target);
+      visit(node.value);
+      return UNKNOWN_VALUE;
+    }
+
+    if (target is js.InterpolatedNode) {
+      // A bare interpolated expression should not be the LHS of an assignment.
+      safe = false;
+      return leftToRight();
+    }
+    
+    if (node.op == null) {
+      if (target is js.VariableReference) {
+        int value = visit(node.value); 
+        // Assignment could change a global or cause a ReferenceError.
+        safe = false;
+        return value;
+      } else if (target is js.PropertyAccess) {
+        // "a.x = b.y" detects a null `b` before a null `a`.

[asgerf, 2015/12/08 11:40:37]

It seems the relevant information is that the RHS is evaluated before the LHS
throws on a null receiver.  There is nothing here about the RHS itself throwing.

[sra1, 2015/12/08 20:54:04]

I have clarified the comment (I hope).

+        int receiver = visit(target.receiver);
+        int selector = visit(target.selector);
+        int value = visit(node.value);
+        if (canBeNull(receiver)) safe = false;
+        return value;
+      } else {
+        // 

[asgerf, 2015/12/08 11:40:37]

Blank comment

[sra1, 2015/12/08 20:54:04]

Done.

+        safe = false;
+        return leftToRight();
+      }
+    }
+    return leftToRight();
+  }
+
+  int visitCall(js.Call node) {
+    visit(node.target);
+    node.arguments.forEach(visit);
+    return unsafe(UNKNOWN_VALUE);
+  }
+
+  int visitNew(js.New node) {
+    // TODO(sra): `new Array(x)` where `x` is a small number.
+    visitCall(node);
+    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 UNKNOWN_VALUE;
+
+      case ',':
+        int left = visit(node.left);
+        int right = visit(node.right);
+        return right;
+
+      case "&&":
+      case "||":
+        int left = visit(node.left);
+        safe = false;

[asgerf, 2015/12/08 11:40:37]

Just an observation.

If there are no placeholders in the right operand there is no need for
everything after to be marked as unsafe. But it doesn't seem to make any
difference for our current set of JS templates.

[sra1, 2015/12/08 20:54:04]

Acknowledged.

+        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 visitThrow(js.Throw node) {
+    visit(node.expression);
+    return unsafe(UNKNOWN_VALUE);
+  }
+
+  int visitPrefix(js.Prefix node) {
+    if (node.op == 'typeof') {
+      // "typeof a" does not dereference "a".
+      if (node.argument is js.VariableUse) return NONNULL_VALUE;
+    }
+
+    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;

[asgerf, 2015/12/08 11:40:37]

The binary operators return UNKNOWN_VALUE. Is there a reason for this
difference?

[sra1, 2015/12/08 20:54:04]

No reason.  They all return numbers, strings, bools.

+
+      case 'typeof':
+        return NONNULL_VALUE;  // Always a string.
+
+      case 'void':
+        return UNKNOWN_VALUE;
+
+      default:

[asgerf, 2015/12/08 11:40:37]

What about prefix ++ and --?

[sra1, 2015/12/08 20:54:04]

Done.

+        safe = false;
+        return UNKNOWN_VALUE;
+    }
+  }
+
+  int visitPostfix(js.Postfix node) {
+    assert(node.op == '--' || node.op == '++');
+    visit(node.argument);
+    return UNKNOWN_VALUE;
+  }
+
+  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'.

[asgerf, 2015/12/08 11:40:37]

I think we could justify adding window and self to this list.

[sra1, 2015/12/08 20:54:04]

Done.

+    switch (node.name) {
+      case 'Array':
+      case 'Date':
+      case 'Function':
+      case 'Object':
+        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;
+  }
+}