Trace lists when they are stored into other lists.

sdk/lib/_internal/compiler/implementation/inferrer/container_tracer.dart

Index: sdk/lib/_internal/compiler/implementation/inferrer/container_tracer.dart
===================================================================
--- sdk/lib/_internal/compiler/implementation/inferrer/container_tracer.dart	(revision 30937)
+++ sdk/lib/_internal/compiler/implementation/inferrer/container_tracer.dart	(working copy)
@@ -125,6 +125,48 @@
     'checkGrowable',
   ]);
 
+// A set of selectors we know do not escape the elements inside the
+// list.
+Set<String> doesNotEscapeElementSet = new Set<String>.from(

[kasperl, 2013/12/06 11:29:57]

Would it be possible to maintain this as annotations on the JSArray methods
long-term?

[ngeoffray, 2013/12/06 11:36:26]

For some yes, but how would you do it for methods on Object or Iterable? We
would need to explicitly call the super method.

+  const <String>[
+    // From Object.
+    '==',
+    'hashCode',
+    'toString',
+    'noSuchMethod',
+    'runtimeType',
+
+    // From Iterable.
+    'isEmpty',
+    'isNotEmpty',
+    'length',
+    'any',
+    'contains',
+    'every',
+    'join',
+
+    // From List.
+    'add',
+    'addAll',
+    'clear',
+    'fillRange',
+    'indexOf',
+    'insert',
+    'insertAll',
+    'lastIndexOf',
+    'remove',
+    'removeRange',
+    'replaceRange',
+    'setAll',
+    'setRange',
+    'shuffle',
+    '[]=',
+
+    // From JSArray.
+    'checkMutable',
+    'checkGrowable',
+  ]);
+
 bool _VERBOSE = false;
 
 class ContainerTracerVisitor implements TypeInformationVisitor {
@@ -132,14 +174,18 @@
   final TypeGraphInferrerEngine inferrer;
   final Compiler compiler;
 
-  // The set of [TypeInformation] where the traced container could
-  // flow in, and operations done on them.
-  final Setlet<TypeInformation> flowsInto = new Setlet<TypeInformation>();
 
   // Work list that gets populated with [TypeInformation] that could
   // contain the container.
   final List<TypeInformation> workList = <TypeInformation>[];
 
+  // Work list of containers to analyze after analyzing the users of a
+  // [TypeInformation] that may be [container]. We know [container]
+  // has been stored in these containers and we must check how
+  // [container] escapes from these containers.
+  final List<ContainerTypeInformation> containersToAnalyze =
+      <ContainerTypeInformation>[];
+
   // The current [TypeInformation] in the analysis.
   TypeInformation currentUser;
 
@@ -156,8 +202,8 @@
       : this.inferrer = inferrer, this.compiler = inferrer.compiler;
 
   void addNewEscapeInformation(TypeInformation info) {
-    if (flowsInto.contains(info)) return;
-    flowsInto.add(info);
+    if (container.flowsInto.contains(info)) return;
+    container.flowsInto.add(info);
     workList.add(info);
   }
 
@@ -171,6 +217,9 @@
         analyzedElements.add(info.owner);
         info.accept(this);
       });
+      while (!containersToAnalyze.isEmpty) {
+        analyzeStoredIntoContainer(containersToAnalyze.removeLast());
+      }
       if (!continueAnalyzing) break;
       if (analyzedElements.length > MAX_ANALYSIS_COUNT) {
         bailout('Too many users');
@@ -211,9 +260,7 @@
   }
 
   visitContainerTypeInformation(ContainerTypeInformation info) {
-    if (container != info) {
-      bailout('Stored in a container');
-    }
+    containersToAnalyze.add(info);
   }
 
   visitConcreteTypeInformation(ConcreteTypeInformation info) {}
@@ -232,6 +279,35 @@
     }
   }
 
+  void analyzeStoredIntoContainer(ContainerTypeInformation container) {
+    inferrer.analyzeContainer(container);
+    if (container.bailedOut) {
+      bailout('Stored in a container that bailed out');
+    } else {
+      container.flowsInto.forEach((flow) {
+        flow.users.forEach((user) {
+          if (user is !DynamicCallSiteTypeInformation) return;
+          if (user.receiver != flow) return;
+          if (returnsElementTypeSet.contains(user.selector)) {
+            addNewEscapeInformation(user);
+          } else if (!doesNotEscapeElementSet.contains(user.selector.name)) {
+            bailout('Escape from a container');
+          }
+        });
+      });
+    }
+  }
+
+  bool isAddedToContainer(DynamicCallSiteTypeInformation info) {
+    var receiverType = info.receiver.type;
+    if (!receiverType.isContainer) return false;
+    String selectorName = info.selector.name;
+    List<TypeInformation> arguments = info.arguments.positional;
+    return (selectorName == '[]=' && currentUser == arguments[1])
+        || (selectorName == 'insert' && currentUser == arguments[0])
+        || (selectorName == 'add' && currentUser == arguments[0]);
+  }
+
   visitDynamicCallSiteTypeInformation(DynamicCallSiteTypeInformation info) {
     Selector selector = info.selector;
     String selectorName = selector.name;
@@ -269,6 +345,15 @@
                && !info.targets.every((element) => element.isFunction())) {
       bailout('Passed to a closure');
       return;
+    } else if (isAddedToContainer(info)) {
+      ContainerTypeMask mask = info.receiver.type;
+      if (mask.allocationNode != null) {
+        ContainerTypeInformation container =
+            inferrer.types.allocatedContainers[mask.allocationNode];
+        containersToAnalyze.add(container);
+      } else {
+        bailout('Stored in too many containers');

[kasperl, 2013/12/06 11:29:57]

Add a comment that explains why a null allocationNode means that it's stored in
too many containers.

[ngeoffray, 2013/12/06 11:36:26]

Done.

+      }
     }
 
     if (info.targets
@@ -276,7 +361,6 @@
             .any((other) => other == currentUser)) {
       addNewEscapeInformation(info);
     }
-
   }
 
   bool isClosure(Element element) {
@@ -285,6 +369,17 @@
     return outermost.declaration != element.declaration;
   }
 
+  bool isParameterOfListAddingMethod(Element element) {
+    if (!element.isParameter()) return false;
+    if (element.getEnclosingClass() != compiler.backend.listImplementation) {
+      return false;
+    }
+    Element method = element.enclosingElement;
+    return (method.name == '[]=')
+        || (method.name == 'add')
+        || (method.name == 'insert');
+  }
+
   visitElementTypeInformation(ElementTypeInformation info) {
     if (isClosure(info.element)) {
       bailout('Returned from a closure');
@@ -292,6 +387,11 @@
     if (compiler.backend.isNeededForReflection(info.element)) {
       bailout('Escape in reflection');
     }
+    if (isParameterOfListAddingMethod(info.element)) {
+      // These elements are being handled in
+      // [visitDynamicCallSiteTypeInformation].
+      return;
+    }
     addNewEscapeInformation(info);
   }
 }