Compile Time Constants cycle check

compiler/java/com/google/dart/compiler/resolver/CompileTimeConstantAnalyzer.java

+// Copyright (c) 2011, 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.
+
+package com.google.dart.compiler.resolver;
+
+import com.google.common.collect.Lists;
+import com.google.common.collect.Maps;
+import com.google.common.collect.Sets;
+import com.google.dart.compiler.DartCompilationError;
+import com.google.dart.compiler.DartCompilationPhase;
+import com.google.dart.compiler.DartCompilerContext;
+import com.google.dart.compiler.InternalCompilerException;
+import com.google.dart.compiler.ast.DartArrayLiteral;
+import com.google.dart.compiler.ast.DartBinaryExpression;
+import com.google.dart.compiler.ast.DartBooleanLiteral;
+import com.google.dart.compiler.ast.DartDoubleLiteral;
+import com.google.dart.compiler.ast.DartExpression;
+import com.google.dart.compiler.ast.DartField;
+import com.google.dart.compiler.ast.DartFunction;
+import com.google.dart.compiler.ast.DartFunctionObjectInvocation;
+import com.google.dart.compiler.ast.DartIdentifier;
+import com.google.dart.compiler.ast.DartIntegerLiteral;
+import com.google.dart.compiler.ast.DartInvocation;
+import com.google.dart.compiler.ast.DartMapLiteral;
+import com.google.dart.compiler.ast.DartMapLiteralEntry;
+import com.google.dart.compiler.ast.DartMethodDefinition;
+import com.google.dart.compiler.ast.DartMethodInvocation;
+import com.google.dart.compiler.ast.DartNewExpression;
+import com.google.dart.compiler.ast.DartNode;
+import com.google.dart.compiler.ast.DartNodeTraverser;
+import com.google.dart.compiler.ast.DartParameter;
+import com.google.dart.compiler.ast.DartParenthesizedExpression;
+import com.google.dart.compiler.ast.DartPropertyAccess;
+import com.google.dart.compiler.ast.DartRedirectConstructorInvocation;
+import com.google.dart.compiler.ast.DartStringInterpolation;
+import com.google.dart.compiler.ast.DartStringLiteral;
+import com.google.dart.compiler.ast.DartSuperExpression;
+import com.google.dart.compiler.ast.DartThisExpression;
+import com.google.dart.compiler.ast.DartUnaryExpression;
+import com.google.dart.compiler.ast.DartUnit;
+import com.google.dart.compiler.ast.DartUnqualifiedInvocation;
+import com.google.dart.compiler.ast.DartVariable;
+import com.google.dart.compiler.ast.DartVariableStatement;
+import com.google.dart.compiler.ast.Modifiers;
+import com.google.dart.compiler.common.Symbol;
+import com.google.dart.compiler.type.Type;
+
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Given an expression, Determines if the expression matches all the rules for a

[mmendez, 2011/11/17 15:32:10]

Nit: Determines -> determines

+ * compile-time constant expression and emits a resolution error if not.
+ *
+ * This script doesn't just resolve expressions, it also sets types to the
+ * extent needed to validate compile-time constant expressions (boolean, int,
+ * double, and string types might be set)
+ *
+ */
+public class CompileTimeConstantAnalyzer extends DartNodeTraverser<Void> {

[mmendez, 2011/11/17 15:32:10]

Nit: not sure if you meant for this to be a visitor itself or whether the
visitor should be a nested class.

[zundel, 2011/11/17 16:26:42]

Created a nested class.

+
+  public static class Phase implements DartCompilationPhase {
+    /**
+     * Executes symbol resolution on the given compilation unit.
+     *
+     * @param context The listener through which compilation errors are reported
+     *          (not <code>null</code>)
+     */
+    @Override
+    public DartUnit exec(DartUnit unit, DartCompilerContext context,
+                         CoreTypeProvider typeProvider) {
+      new CompileTimeConstantAnalyzer(typeProvider, context).exec(unit);
+      return unit;
+    }
+  }
+  private class ExpressionVisitor extends DartNodeTraverser<Void> {
+    private ExpressionVisitor() {
+    }
+
+    private boolean checkBoolean(DartNode x, Type type) {
+      if (!type.equals(boolType)) {
+        context.onError(new DartCompilationError(x,
+            ResolverErrorCode.EXPECTED_CONSTANT_EXPRESSION_BOOLEAN, type
+                .toString()));
+        return false;
+      }
+      return true;
+    }
+
+    private boolean checkInt(DartNode x, Type type) {
+      if (!type.equals(intType)) {
+        context
+            .onError(new DartCompilationError(x,
+                ResolverErrorCode.EXPECTED_CONSTANT_EXPRESSION_INT, type
+                    .toString()));
+        return false;
+      }
+      return true;
+    }
+
+    private boolean checkNumber(DartNode x, Type type) {
+      if (!(type.equals(numType) || type.equals(intType) || type
+          .equals(doubleType))) {
+        context.onError(new DartCompilationError(x,
+            ResolverErrorCode.EXPECTED_CONSTANT_EXPRESSION_NUMBER, type
+                .toString()));
+
+        return false;
+      }
+      return true;
+    }
+
+    private boolean checkNumberBooleanOrStringType(DartNode x, Type type) {
+      if (!type.equals(intType) && !type.equals(boolType)
+          && !type.equals(numType) && !type.equals(doubleType)
+          && !type.equals(stringType)) {
+        context.onError(new DartCompilationError(x,
+            ResolverErrorCode.EXPECTED_CONSTANT_EXPRESSION_STRING_NUMBER_BOOL,
+            type.toString()));
+        return false;
+      }
+      return true;
+    }
+
+    /**
+     * Logs a general message "expected a constant expression" error. Use a more
+     * specific error message when possible.
+     */
+    private void expectedConstant(DartNode x) {
+      context.onError(new DartCompilationError(x,
+          ResolverErrorCode.EXPECTED_CONSTANT_EXPRESSION));
+    }
+
+    /**
+     * Determine the most specific type assigned to an expression node. Prefer
+     * the setting in the expression's symbol if present. Otherwise, use a type
+     * tagged in the expression node itself.
+     *
+     * @return a non <code>null</code> type value. Dynamic if none other can be
+     * determined.
+     */
+    private Type getMostSpecificType(DartNode node) {
+      Element element = (Element) node.getSymbol();
+      Type type = inferredTypes.get(node);
+      if (type != null) {
+        return type;
+      }
+
+      switch (ElementKind.of(element)) {

[mmendez, 2011/11/17 15:32:10]

Can't you have the FIELD, METHOD, VARIABLE and CONSTRUCTOR cases share the same
code (type = element.getType()).

I'm not sure about the ICE since it is a larger issue and every author on the
compiler has done things slightly differently.  Would it be better to just
return dynamic and let a compilation error be generated?

[zundel, 2011/11/17 16:26:42]

Done.

+        case FIELD:
+          type = ((FieldElement) element).getType();
+          break;
+        case METHOD:
+          type = ((MethodElement) element).getType();
+          break;
+        case VARIABLE:
+          type = ((VariableElement) element).getType();
+          break;
+        case CONSTRUCTOR:
+          type = ((ConstructorElement) element).getType();
+          break;
+        case NONE:
+          if (node.getType() != null) {
+            return node.getType();
+          }
+          return dynamicType;
+        default:
+          throw new InternalCompilerException("Unexpected element "

[mmendez, 2011/11/17 15:32:10]

I think that this will ICE if you access a constant from a library and them
import uses a prefix.

[zundel, 2011/11/17 16:26:42]

I don't think so. that happens all the time in the Dart core library.

+              + node.toString() + " kind: " + ElementKind.of(element)
+              + "evaluating type for compile-time constant expression.");
+      }
+      if (type == null) {
+        return node.getType();

[mmendez, 2011/11/17 15:32:10]

Could you add a comment explaining under which circumstances this happens?

[zundel, 2011/11/17 16:26:42]

It was happening when diet parsed files didn't have symbols resolved in compile
time constant expressions.  Since that is fixed, I can greatly simplify.

+      }
+      return type;
+    }
+
+    private void setType(DartNode x, Type type) {

[mmendez, 2011/11/17 15:32:10]

Rename to cache type for node?  It doesn't actually set the type of the node.

[zundel, 2011/11/17 16:26:42]

renamed

+      if (type != null && ! type.equals(dynamicType)) {
+        inferredTypes.put(x,  type);
+      }
+    }
+
+    @Override
+    public Void visitArrayLiteral(DartArrayLiteral x) {
+      if (!x.isConst()) {
+        expectedConstant(x);
+      } else {
+        for (DartExpression expr : x.getExpressions()) {
+          expr.accept(this);
+        }
+      }
+      return null;
+    }
+
+    @Override
+    public Void visitBinaryExpression(DartBinaryExpression x) {
+      x.visitChildren(this);
+
+      DartExpression lhs = x.getArg1();
+      DartExpression rhs = x.getArg2();
+      Type lhsType = getMostSpecificType(lhs);
+      Type rhsType = getMostSpecificType(rhs);
+      if (lhsType == null) {
+        lhsType = dynamicType;
+      }
+      if (rhsType == null) {
+        rhsType = dynamicType;
+      }
+
+      switch (x.getOperator()) {
+        case NE:
+        case EQ:
+        case NE_STRICT:
+        case EQ_STRICT:
+          if (checkNumberBooleanOrStringType(lhs, lhsType)
+              && checkNumberBooleanOrStringType(rhs, rhsType)) {
+            setType(x, boolType);
+          }
+          break;
+
+        case AND:
+        case OR:
+          if (checkBoolean(lhs, lhsType) && checkBoolean(rhs, rhsType)) {
+            setType(x, boolType);
+          }
+          break;
+
+        case BIT_NOT:
+        case TRUNC:
+        case BIT_XOR:
+        case BIT_AND:
+        case BIT_OR:
+        case SAR:
+        case SHL:
+          if (checkInt(lhs, lhsType) && checkInt(rhs, rhsType)) {
+            setType(x, intType);
+          }
+          break;
+
+        case ADD:
+        case SUB:
+        case MUL:
+        case DIV:
+        case MOD:
+          if (checkNumber(lhs, lhsType) && checkNumber(rhs, rhsType)) {
+            setType(x, numType);
+          }
+          break;
+        case LT:
+        case GT:
+        case LTE:
+        case GTE:
+          if (checkNumber(lhs, lhsType) && checkNumber(rhs, rhsType)) {
+            setType(x, boolType);
+          }
+          break;
+
+        default:
+          // all other operators...
+          expectedConstant(x);
+      }
+      return null;
+    }
+
+    @Override
+    public Void visitBooleanLiteral(DartBooleanLiteral x) {

[mmendez, 2011/11/17 15:32:10]

Nit: Not part of your patch, but I would have a expected the literal to have the
boolType set on it already.

[zundel, 2011/11/17 16:26:42]

Doesn't get set until Resolver is run.  That is never run on diet parse files.

+      setType(x, boolType);
+      return null;
+    }
+
+    @Override
+    public Void visitDoubleLiteral(DartDoubleLiteral x) {
+      setType(x, doubleType);
+      return null;
+    }
+
+    @Override
+    public Void visitField(DartField x) {
+      x.visitChildren(this);
+      if (x.getType() == null || x.getType().equals(dynamicType)) {
+        Type type = getMostSpecificType(x.getValue());
+        setType(x, type);
+      }
+      return null;
+    }
+
+    @Override
+    public Void visitFunction(DartFunction x) {
+      // No need to traverse, functions are always disallowed.
+      expectedConstant(x);
+      return null;
+    }
+
+    @Override
+    public Void visitFunctionObjectInvocation(DartFunctionObjectInvocation x) {
+      // No need to traverse, function object invocations are always disallowed.
+      expectedConstant(x);
+      return null;
+    }
+
+    @Override
+    public Void visitIdentifier(DartIdentifier x) {
+      x.visitChildren(this);
+
+      Element element = x.getSymbol();
+      switch (ElementKind.of(element)) {
+        case CLASS:
+        case PARAMETER:
+          // OK
+          break;
+        case FIELD:
+        case VARIABLE:
+
+          if (element != null && visitedSymbols.contains(element)) {
+            context.onError(new DartCompilationError(x,
+                ResolverErrorCode.CIRCULAR_REFERENCE));
+            setType(x, getMostSpecificType(x));
+            return null;
+          }
+          visitedSymbols.add(element);
+
+          if (!element.getModifiers().isConstant()) {
+            expectedConstant(x);
+          }
+          DartNode identifierNode = element.getNode();
+
+          switch (ElementKind.of(element)) {
+            case FIELD:
+              setType(x, getMostSpecificType(x));
+              break;
+          }
+          this.visit(Lists.newArrayList(identifierNode));
+
+          visitedSymbols.remove(element);
+
+          switch (ElementKind.of(element)) {

[mmendez, 2011/11/17 15:32:10]

Won't this reset the value set on line 332?  Maybe add a comment explaining why
this is necessary?

[zundel, 2011/11/17 16:26:42]

There is a tree walk in the middle.  The type was set beforehand in case the
current symbol was null BUT that shouldnt happen now that I've added the
CompileTimeConstantResolver, so we can get rid of it.

Afterward, we want to set the value of this identifier to any assigment we found
for the symbol while traversing the expression.

+            case FIELD:
+              setType(x, getMostSpecificType(identifierNode));
+              break;
+          }
+
+          break;
+
+        case CONSTRUCTOR:
+          if (!element.getModifiers().isConstant()) {
+            expectedConstant(x);
+          }
+          setType(x, getMostSpecificType(x));
+          break;
+
+        case NONE:
+          Type type = getMostSpecificType(x);
+          if (dynamicType.equals(type)) {
+            // TODO(zundel) This is the case for unresolved identifiers that
+            // need to be recursively
+            // checked.
+            expectedConstant(x);
+          }
+          setType(x, type);
+          break;
+        default:
+          throw new InternalCompilerException("Unexpected element "
+              + x.toString() + " kind: " + ElementKind.of(element)
+              + " evaluating type for compile-time constant expression.");
+      }
+      return null;
+    }
+
+
+    @Override
+    public Void visitIntegerLiteral(DartIntegerLiteral x) {
+      setType(x, intType);
+      return null;
+    }
+
+    @Override
+    public Void visitInvocation(DartInvocation x) {
+      // No need to traverse, invocations are always disallowed.
+      expectedConstant(x);
+      return null;
+    }
+
+    @Override
+    public Void visitMapLiteral(DartMapLiteral x) {
+      if (!x.isConst()) {
+        expectedConstant(x);
+      } else {
+        for (DartMapLiteralEntry entry : x.getEntries()) {
+          entry.accept(this);
+        }
+      }
+      return null;
+    }
+
+    @Override
+    public Void visitMethodInvocation(DartMethodInvocation x) {
+      // No need to traverse, method invocations are always disallowed.
+      expectedConstant(x);
+      return null;
+    }
+
+    @Override
+    public Void visitNewExpression(DartNewExpression x) {
+      if (!x.isConst()) {
+        expectedConstant(x);
+      } else {
+        for (DartExpression arg : x.getArgs()) {
+          arg.accept(this);
+        }
+      }
+      setType(x, x.getConstructor().getType());
+      return null;
+    }
+
+    @Override
+    public Void visitParenthesizedExpression(DartParenthesizedExpression x) {
+      x.visitChildren(this);
+      Type type = getMostSpecificType(x.getExpression());
+      setType(x, type);
+      return null;
+    }
+
+    @Override
+    public Void visitPropertyAccess(DartPropertyAccess x) {
+      x.visitChildren(this);
+      switch (ElementKind.of(x.getQualifier().getSymbol())) {
+        case CLASS:
+        case LIBRARY:
+        case NONE:
+          // OK.
+          break;
+        default:
+          expectedConstant(x);
+          return null;
+      }
+      Element element = x.getName().getSymbol();
+      if (element != null && !element.getModifiers().isConstant()) {
+        expectedConstant(x);
+      }
+      Type type = getMostSpecificType(x.getName());
+      setType(x, type);
+      return null;
+    }
+
+    @Override
+    public Void visitRedirectConstructorInvocation(DartRedirectConstructorInvocation x) {
+      Element element = x.getSymbol();
+      if (element != null) {
+        if (!element.getModifiers().isConstant()) {
+          expectedConstant(x);
+        }
+      }
+      x.visitChildren(this);
+      return null;
+    }
+
+    @Override
+    public Void visitStringInterpolation(DartStringInterpolation x) {
+      expectedConstant(x);
+      return null;
+    }
+
+    @Override
+    public Void visitStringLiteral(DartStringLiteral x) {
+      setType(x, stringType);
+      return null;
+    }
+
+    @Override
+    public Void visitSuperExpression(DartSuperExpression x) {
+      // No need to traverse further - super() expressions are never constant
+      expectedConstant(x);
+      return null;
+    }
+
+    @Override
+    public Void visitThisExpression(DartThisExpression x) {
+      // No need to traverse, this expressions are always disallowed.
+      expectedConstant(x);
+      return null;
+    }
+
+    @Override
+    public Void visitUnaryExpression(DartUnaryExpression x) {
+      x.visitChildren(this);
+
+      Type type = getMostSpecificType(x.getArg());
+      switch (x.getOperator()) {
+        case NOT:
+          if (checkBoolean(x, type)) {
+            setType(x, boolType);
+          }
+          break;
+        case SUB:
+          if (checkNumber(x, type)) {
+            setType(x, numType);
+          }
+          break;
+        case BIT_NOT:
+          if (checkInt(x, type)) {
+            setType(x, intType);
+          }
+          break;
+        default:
+          expectedConstant(x);
+      }
+      return null;
+    }
+
+    @Override
+    public Void visitUnqualifiedInvocation(DartUnqualifiedInvocation x) {
+      // No need to traverse, always disallowed.
+      expectedConstant(x);
+      return null;
+    }
+  }
+
+  public void exec (DartUnit unit) {
+    unit.accept(this);
+  }
+
+  public Set<Symbol> visitedSymbols = Sets.newHashSet();
+
+  public Map<DartNode, Type> inferredTypes = Maps.newHashMap();
+
+  private final DartCompilerContext context;
+  private final Type boolType;
+  private final Type doubleType;
+  private final Type intType;
+  private final Type numType;
+  private final Type stringType;
+  private final Type dynamicType;
+
+  public CompileTimeConstantAnalyzer(CoreTypeProvider typeProvider,
+      DartCompilerContext context) {
+    this.context = context;
+    this.boolType = typeProvider.getBoolType();
+    this.doubleType = typeProvider.getDoubleType();
+    this.intType = typeProvider.getIntType();
+    this.numType = typeProvider.getNumType();
+    this.stringType = typeProvider.getStringType();
+    this.dynamicType = typeProvider.getDynamicType();
+  }
+
+  private void checkConstantExpression(DartExpression expression) {
+    if (expression != null) {
+      expression.accept(new ExpressionVisitor());
+    }
+  }
+
+  @Override
+  public Void visitField(DartField node) {
+    checkConstantExpression(node.getValue());
+    return null;
+  }
+
+  @Override
+  public Void visitMethodDefinition(DartMethodDefinition node) {
+    DartFunction functionNode = node.getFunction();
+    List<DartParameter> parameters = functionNode.getParams();
+    for (DartParameter parameter : parameters) {
+      // Then resolve the default values.
+      checkConstantExpression(parameter.getDefaultExpr());
+    }
+    return null;
+  }
+
+  @Override
+  public Void visitNewExpression(DartNewExpression node) {
+    if (node.isConst()) {
+      for (DartExpression arg : node.getArgs()) {
+       checkConstantExpression(arg);
+      }
+    }
+    return null;
+  }
+
+  @Override
+  public Void visitParameter(DartParameter node) {
+    checkConstantExpression(node.getDefaultExpr());
+    return null;
+  }
+
+  @Override
+  public Void visitVariableStatement(DartVariableStatement node) {
+    for (DartVariable variable : node.getVariables()) {
+      Modifiers modifiers = node.getModifiers();
+      if (modifiers.isStatic() && modifiers.isFinal() && variable.getValue() != null) {
+        checkConstantExpression(variable.getValue());
+      }
+    }
+    return null;
+  }
+}