Naive handling of List#[] and List#[]=

sdk/lib/_internal/compiler/implementation/types/concrete_types_inferrer.dart

Index: sdk/lib/_internal/compiler/implementation/types/concrete_types_inferrer.dart
diff --git a/sdk/lib/_internal/compiler/implementation/types/concrete_types_inferrer.dart b/sdk/lib/_internal/compiler/implementation/types/concrete_types_inferrer.dart
index fae1650fc2fe17e7620f15ff32bf256a8411c612..0051c409f4b2b5ebfae09fcaebca4c523623a01a 100644
--- a/sdk/lib/_internal/compiler/implementation/types/concrete_types_inferrer.dart
+++ b/sdk/lib/_internal/compiler/implementation/types/concrete_types_inferrer.dart
@@ -277,15 +277,21 @@ class ConcreteTypeCartesianProductIterator
  * [BaseType] Constants.
  */
 class BaseTypes {
-  final BaseType intBaseType;
-  final BaseType doubleBaseType;
-  final BaseType numBaseType;
-  final BaseType boolBaseType;
-  final BaseType stringBaseType;
-  final BaseType listBaseType;
-  final BaseType mapBaseType;
-  final BaseType objectBaseType;
-  final BaseType typeBaseType;
+  final ClassBaseType intBaseType;
+  final ClassBaseType doubleBaseType;
+  final ClassBaseType numBaseType;
+  final ClassBaseType boolBaseType;
+  final ClassBaseType stringBaseType;
+  final ClassBaseType jsArrayBaseType;

[karlklose, 2013/01/23 13:16:55]

I would still call this listBaseType and perhaps add a comment in the function
that looks it up, that in the JsBackend this is a special implementation class.

[polux, 2013/01/24 13:12:22]

Done.

+  final ClassBaseType mapBaseType;
+  final ClassBaseType objectBaseType;
+  final ClassBaseType typeBaseType;
+
+  static _getJsArrayClass(Compiler compiler) {

[karlklose, 2013/01/23 13:16:55]

You could call it 'getNativeListClass' and then switch on the backend type.
It could make sense to run the analysis with dart2dart as a pure analysis tool.
Or even have a separate backend that produces a serialization of the analysis'
results to be used with other tools.

[polux, 2013/01/24 13:12:22]

Done.

+    // TODO(polux): bail out on non-javascript backends?
+    JavaScriptBackend backend = compiler.backend;
+    return backend.jsArrayClass;
+  }
 
   BaseTypes(Compiler compiler) :
     intBaseType = new ClassBaseType(compiler.intClass),
@@ -293,7 +299,7 @@ class BaseTypes {
     numBaseType = new ClassBaseType(compiler.numClass),
     boolBaseType = new ClassBaseType(compiler.boolClass),
     stringBaseType = new ClassBaseType(compiler.stringClass),
-    listBaseType = new ClassBaseType(compiler.listClass),
+    jsArrayBaseType = new ClassBaseType(_getJsArrayClass(compiler)),
     mapBaseType = new ClassBaseType(compiler.mapClass),
     objectBaseType = new ClassBaseType(compiler.objectClass),
     typeBaseType = new ClassBaseType(compiler.typeClass);
@@ -400,13 +406,34 @@ class ConcreteTypesInferrer {
   bool testMode = false;
 
   /**
-   * Constants representing builtin base types. Initialized in [analyzeMain]
+   * Constants representing builtin base types. Initialized in [initialize]

[karlklose, 2013/01/23 13:16:55]

The explanation why these are not directly initialized could be shared for the
next four fields. 

[polux, 2013/01/24 13:12:22]

Wasn't sure what you meant by "shared": I just erased the others. My concern was
that dartdoc doesn't preserve the declaration order but on the other hand, I'm
not sure we're ever gonna generate dartdoc for dart2js.

    * and not in the constructor because the compiler elements are not yet
    * populated.
    */
   BaseTypes baseTypes;
 
   /**
+   * Constant representing [:JsArray#[]:]. Initialized in [initialize]
+   * and not in the constructor because the compiler elements are not yet
+   * populated.
+   */
+  FunctionElement jsArrayBrackets;

[karlklose, 2013/01/23 13:16:55]

How about calling this 'listIndex' ...

[polux, 2013/01/24 13:12:22]

Done.

+
+  /**
+   * Constant representing [:JsArray#[]=:]. Initialized in [initialize]
+   * and not in the constructor because the compiler elements are not yet
+   * populated.
+   */
+  FunctionElement jsArrayBracketsEquals;

[karlklose, 2013/01/23 13:16:55]

... and this one 'listIndexSet'.

[polux, 2013/01/24 13:12:22]

Done.

+
+  /**
+   * Constant representing [:List():]. Initialized in [initialize]
+   * and not in the constructor because the compiler elements are not yet
+   * populated.
+   */
+  FunctionElement listConstructor;
+
+  /**
    * A cache from (function x argument base types) to concrete types,
    * used to memoize [analyzeMonoSend]. Another way of seeing [cache] is as a
    * map from [FunctionElement]s to "templates" in the sense of "The Cartesian
@@ -430,6 +457,9 @@ class ConcreteTypesInferrer {
   /** [: readers[field] :] is the list of [: field :]'s possible readers. */
   final Map<Element, Set<FunctionElement>> readers;
 
+  /** The inferred type of elements stored in Lists. */
+  ConcreteType listElementType;
+
   /**
    * A map from parameters to their inferred concrete types. It plays no role
    * in the analysis, it is write only.
@@ -445,7 +475,8 @@ class ConcreteTypesInferrer {
         inferredParameterTypes = new Map<VariableElement, ConcreteType>(),
         workQueue = new Queue<InferenceWorkItem>(),
         callers = new Map<FunctionElement, Set<FunctionElement>>(),
-        readers = new Map<Element, Set<FunctionElement>>() {
+        readers = new Map<Element, Set<FunctionElement>>(),
+        listElementType = new ConcreteType.empty() {
     unknownConcreteType = new ConcreteType.unknown();
     emptyConcreteType = new ConcreteType.empty();
   }
@@ -533,7 +564,7 @@ class ConcreteTypesInferrer {
    * Returns all the members with name [methodName].
    */
   List<Element> getMembersByName(SourceString methodName) {
-    // TODO(polux): make this faster!
+    // TODO(polux): memoize?
     var result = new List<Element>();
     for (ClassElement cls in compiler.enqueuer.resolution.seenClasses) {
       Element elem = cls.lookupLocalMember(methodName);
@@ -588,6 +619,15 @@ class ConcreteTypesInferrer {
     }
   }
 
+  /** Augment the inferred type of elements stored in Lists. */

[karlklose, 2013/01/23 13:16:55]

You can use /// instead of /** ... */ 

[polux, 2013/01/24 13:12:22]

Done.

+  void augmentListElementType(ConcreteType type) {
+    ConcreteType newType = union(listElementType, type);
+    if (newType != listElementType) {
+      invalidateCallers(jsArrayBrackets);
+      listElementType = newType;
+    }
+  }
+
   /**
    * Sets the concrete type associated to [parameter] to the union of the
    * inferred concrete type so far and [type].
@@ -626,6 +666,24 @@ class ConcreteTypesInferrer {
     }
   }
 
+  /**
+   * Add callers of [function] to the workqueue.
+   */
+  void invalidateCallers(FunctionElement function) {
+    Set<FunctionElement> methodCallers = callers[function];
+    if (methodCallers == null) return;
+    for (FunctionElement caller in methodCallers) {
+      Map<ConcreteTypesEnvironment, ConcreteType> callerInstances =
+          cache[caller];
+      if (callerInstances != null) {
+        callerInstances.forEach((environment, _) {
+          workQueue.addLast(
+              new InferenceWorkItem(caller, environment));
+        });
+      }
+    }
+  }
+
   // -- query --
 
   /**
@@ -759,6 +817,8 @@ class ConcreteTypesInferrer {
   ConcreteType getMonomorphicSendReturnType(
       FunctionElement function,
       ConcreteTypesEnvironment environment) {
+    ConcreteType specialType = getSpecialCaseReturnType(function, environment);
+    if (specialType != null) return specialType;
 
     Map<ConcreteTypesEnvironment, ConcreteType> template = cache[function];
     if (template == null) {
@@ -776,6 +836,34 @@ class ConcreteTypesInferrer {
     }
   }
 
+  /* Handles external methods that cannot be cached because they depend on some

[karlklose, 2013/01/23 13:16:55]

Make this a valid dart-doc comment.

[polux, 2013/01/24 13:12:22]

Done.

+   * other state of [ConcreteTypesInferrer] like [: List#[] :] and
+   * [: List#[]= :]. Returns null if [function] and [environment] don't form a
+   * special case
+   */
+  ConcreteType getSpecialCaseReturnType(FunctionElement function,
+                                        ConcreteTypesEnvironment environment) {
+    if (function == jsArrayBrackets) {
+      ConcreteType indexType = environment.lookupType(
+          jsArrayBrackets.functionSignature.requiredParameters.head);
+      if (!indexType.baseTypes.contains(baseTypes.intBaseType)) {
+        return new ConcreteType.empty();
+      }
+      return listElementType;
+    } else if (function == jsArrayBracketsEquals) {
+      Link<Element> parameters =
+          jsArrayBracketsEquals.functionSignature.requiredParameters;
+      ConcreteType indexType = environment.lookupType(parameters.head);
+      if (!indexType.baseTypes.contains(baseTypes.intBaseType)) {
+        return new ConcreteType.empty();
+      }
+      ConcreteType elementType = environment.lookupType(parameters.tail.head);
+      augmentListElementType(elementType);
+      return new ConcreteType.empty();
+    }
+    return null;
+  }
+
   ConcreteType analyze(FunctionElement element,
                        ConcreteTypesEnvironment environment) {
     return element.isGenerativeConstructor()
@@ -785,17 +873,19 @@ class ConcreteTypesInferrer {
 
   ConcreteType analyzeMethod(FunctionElement element,
                              ConcreteTypesEnvironment environment) {
-    FunctionExpression tree = element.parseNode(compiler);
-    // This should never happen since we only deal with concrete types, except
-    // for external methods whose typing rules have not been hardcoded yet.
-    if (!tree.hasBody()) {
-      return unknownConcreteType;
-    }
     TreeElements elements =
         compiler.enqueuer.resolution.resolvedElements[element];
-    Visitor visitor =
-        new TypeInferrerVisitor(elements, element, this, environment);
-    return tree.accept(visitor);
+    ConcreteType specialResult = handleSpecialMethod(element, environment);
+    if (specialResult != null) return specialResult;
+    FunctionExpression tree = element.parseNode(compiler);
+    if (tree.hasBody()) {
+      Visitor visitor =
+          new TypeInferrerVisitor(elements, element, this, environment);
+      return tree.accept(visitor);
+    } else {  // external method

[karlklose, 2013/01/23 13:16:55]

All external functions should be patched when we arrive here.

Could these be abstract methods, factory redirections or const constructors?

[polux, 2013/01/24 13:12:22]

As discussed, I'll handle this in an upcoming CL.

+      // TODO(polux): we might want to trust the declared type
+      return new ConcreteType.unknown();
+    }
   }
 
   ConcreteType analyzeConstructor(FunctionElement element,
@@ -846,8 +936,44 @@ class ConcreteTypesInferrer {
     return singletonConcreteType(new ClassBaseType(enclosingClass));
   }
 
-  void analyzeMain(Element element) {
+  /**
+   * Hook that performs side effects on some special method calls (like
+   * [:List(length):]) and possibly returns a concrete type
+   * (like [:{JsArray}:]).
+   */
+  ConcreteType handleSpecialMethod(FunctionElement element,
+                                   ConcreteTypesEnvironment environment) {
+    // When List([length]) is called with some length, we must augment
+    // listElementType with {null}.
+    if (element == listConstructor) {
+      Link<Element> parameters =
+          listConstructor.functionSignature.optionalParameters;
+      ConcreteType lengthType = environment.lookupType(parameters.head);
+      if (lengthType.baseTypes.contains(baseTypes.intBaseType)) {
+        augmentListElementType(singletonConcreteType(new NullBaseType()));
+      }
+      return singletonConcreteType(baseTypes.jsArrayBaseType);
+    }
+  }
+
+  /* Initialization code that cannot be run in the constructor because it
+   * requires the compiler's elements to be populated.
+   */
+  void initialize() {
     baseTypes = new BaseTypes(compiler);
+    ClassElement jsArrayClass = baseTypes.jsArrayBaseType.element;
+    jsArrayBrackets = jsArrayClass.lookupMember(const SourceString('[]'));
+    jsArrayBracketsEquals =
+        jsArrayClass.lookupMember(const SourceString('[]='));
+    listConstructor =
+        compiler.listClass.lookupConstructor(
+            new Selector.callConstructor(const SourceString(''),
+                                         compiler.listClass.getLibrary()));
+
+  }
+
+  void analyzeMain(Element element) {
+    initialize();
     cache[element] = new Map<ConcreteTypesEnvironment, ConcreteType>();
     populateCacheWithBuiltinRules();
     try {
@@ -859,17 +985,7 @@ class ConcreteTypesInferrer {
         var template = cache[item.method];
         if (template[item.environment] == concreteType) continue;
         template[item.environment] = concreteType;
-        final methodCallers = callers[item.method];
-        if (methodCallers == null) continue;
-        for (final caller in methodCallers) {
-          final callerInstances = cache[caller];
-          if (callerInstances != null) {
-            callerInstances.forEach((environment, _) {
-              workQueue.addLast(
-                  new InferenceWorkItem(caller, environment));
-            });
-          }
-        }
+        invalidateCallers(item.method);
       }
     } on CancelTypeInferenceException catch(e) {
       if (LOG_FAILURES) {
@@ -1133,7 +1249,6 @@ class TypeInferrerVisitor extends ResolvedVisitor<ConcreteType> {
     else return Elements.mapToUserOperatorOrNull(op);
   }
 
-  // TODO(polux): handle sendset as expression
   ConcreteType visitSendSet(SendSet node) {
     // Operator []= has a different behaviour than other send sets: it is
     // actually a send whose return type is that of its second argument.
@@ -1222,8 +1337,15 @@ class TypeInferrerVisitor extends ResolvedVisitor<ConcreteType> {
   }
 
   ConcreteType visitLiteralList(LiteralList node) {
-    visitNodeList(node.elements);
-    return inferrer.singletonConcreteType(inferrer.baseTypes.listBaseType);
+    ConcreteType elementsType = new ConcreteType.empty();
+    // We compute the union of the types of the list literal's elements.
+    for (Link<Node> link = node.elements.nodes;
+         !link.isEmpty;
+         link = link.tail) {
+      elementsType = inferrer.union(elementsType, analyze(link.head));
+    }
+    inferrer.augmentListElementType(elementsType);
+    return inferrer.singletonConcreteType(inferrer.baseTypes.jsArrayBaseType);
   }
 
   ConcreteType visitNodeList(NodeList node) {