Implement tracing for function expressions and statements, and infer types of parameters of these c…

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

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file

[ngeoffray, 2013/12/10 17:11:02]

I plan to split this file into different files in another CL.

 // 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.
 
 part of type_graph_inferrer;
 
 /**
  * A set of selector names that [List] implements, that we know do not
  * change the element type of the list, or let the list escape to code
  * that might change the element type.
  */
@@ skipping 150 matching lines @@
     'shuffle',
     '[]=',
 
     // From JSArray.
     'checkMutable',
     'checkGrowable',
   ]);
 
 bool _VERBOSE = false;
 
-class ContainerTracerVisitor implements TypeInformationVisitor {
-  final ListTypeInformation container;
+abstract class TracerVisitor implements TypeInformationVisitor {
+  final TypeInformation tracedType;
   final TypeGraphInferrerEngine inferrer;
   final Compiler compiler;
 
+  static const int MAX_ANALYSIS_COUNT = 16;
+  final Setlet<Element> analyzedElements = new Setlet<Element>();
+
+  TracerVisitor(this.tracedType, inferrer)
+      : this.inferrer = inferrer, this.compiler = inferrer.compiler;
 
   // 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<ListTypeInformation> containersToAnalyze =
       <ListTypeInformation>[];
 
+  final Setlet<TypeInformation> flowsInto = new Setlet<TypeInformation>();
+
   // The current [TypeInformation] in the analysis.
   TypeInformation currentUser;
-
-  // The list of found assignments to the container.
-  final List<TypeInformation> assignments = <TypeInformation>[];
-
-  bool callsGrowableMethod = false;
   bool continueAnalyzing = true;
-  
-  static const int MAX_ANALYSIS_COUNT = 16;
-  final Setlet<Element> analyzedElements = new Setlet<Element>();
-
-  ContainerTracerVisitor(this.container, inferrer)
-      : this.inferrer = inferrer, this.compiler = inferrer.compiler;
 
   void addNewEscapeInformation(TypeInformation info) {
-    if (container.flowsInto.contains(info)) return;
-    container.flowsInto.add(info);
+    if (flowsInto.contains(info)) return;
+    flowsInto.add(info);
     workList.add(info);
   }
 
-  List<TypeInformation> run() {
+  void analyze() {
     // Collect the [TypeInformation] where the container can flow in,
     // as well as the operations done on all these [TypeInformation]s.
-    addNewEscapeInformation(container);
+    addNewEscapeInformation(tracedType);
     while (!workList.isEmpty) {
       currentUser = workList.removeLast();
       currentUser.users.forEach((TypeInformation info) {
         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');
         break;
       }
     }
-
-    if (continueAnalyzing) {
-      if (!callsGrowableMethod && container.inferredLength == null) {
-        container.inferredLength = container.originalLength;
-      }
-      return assignments;
-    }
-    return null;
   }
 
   void bailout(String reason) {
     if (_VERBOSE) {
-      ContainerTypeMask mask = container.type;
-      print('Bailing out on ${mask.allocationNode} ${mask.allocationElement} '
-            'because: $reason');
+      print('Bailing out on $tracedType because: $reason');
     }
     continueAnalyzing = false;
-    callsGrowableMethod = true;
   }
 
-  visitNarrowTypeInformation(NarrowTypeInformation info) {
+  void visitNarrowTypeInformation(NarrowTypeInformation info) {
     addNewEscapeInformation(info);
   }
 
-  visitPhiElementTypeInformation(PhiElementTypeInformation info) {
+  void visitPhiElementTypeInformation(PhiElementTypeInformation info) {
     addNewEscapeInformation(info);
   }
 
-  visitElementInContainerTypeInformation(
+  void visitElementInContainerTypeInformation(
       ElementInContainerTypeInformation info) {
     addNewEscapeInformation(info);
   }
 
   visitListTypeInformation(ListTypeInformation info) {
     containersToAnalyze.add(info);
   }
 
-  visitMapTypeInformation(MapTypeInformation info) {
-    bailout('Stored in a map');
-  }
+  void visitConcreteTypeInformation(ConcreteTypeInformation info) {}
 
-  visitConcreteTypeInformation(ConcreteTypeInformation info) {}
-
-  visitClosureCallSiteTypeInformation(ClosureCallSiteTypeInformation info) {
-    bailout('Passed to a closure');
-  }
+  void visitClosureTypeInformation(ConcreteTypeInformation info) {}
 
   visitStaticCallSiteTypeInformation(StaticCallSiteTypeInformation info) {
     Element called = info.calledElement;
-    if (called.isForeign(compiler) && called.name == 'JS') {
-      bailout('Used in JS ${info.call}');
-    }
     if (inferrer.types.getInferredTypeOf(called) == currentUser) {
       addNewEscapeInformation(info);
     }
   }
 
   void analyzeStoredIntoContainer(ListTypeInformation 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) {
+    if (info.arguments == null) return false;
     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]);
   }
 
+  void visitDynamicCallSiteTypeInformation(
+      DynamicCallSiteTypeInformation info) {
+    if (isAddedToContainer(info)) {
+      ContainerTypeMask mask = info.receiver.type;
+      if (mask.allocationNode != null) {
+        ListTypeInformation container =
+            inferrer.types.allocatedLists[mask.allocationNode];
+        containersToAnalyze.add(container);
+      } else {
+        // The [ContainerTypeMask] is a union of two containers, and
+        // we lose track of where these containers have been allocated
+        // at this point.
+        bailout('Stored in too many containers');
+      }
+    }
+
+    if (info.targets

[kasperl, 2013/12/11 07:35:35]

Consider using a local variable for the result of the map. Something like:

   Iterable<...> inferredTargetTypes = info.targets.map((element) =>
       inferrer.types.getInferredTypeOf(element));
   if (inferredTargetTypes.any((user) => currentUser == user)) {
     ...
   }

[ngeoffray, 2013/12/16 11:47:43]

Done.

+            .map((element) => inferrer.types.getInferredTypeOf(element))
+            .any((other) => other == currentUser)) {
+      addNewEscapeInformation(info);
+    }
+  }
+
+  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');
+  }
+
+  void visitElementTypeInformation(ElementTypeInformation info) {
+    if (isParameterOfListAddingMethod(info.element)) {
+      // These elements are being handled in
+      // [visitDynamicCallSiteTypeInformation].
+      return;
+    }
+    addNewEscapeInformation(info);
+  }
+}
+
+class ContainerTracerVisitor extends TracerVisitor {
+  // The list of found assignments to the container.
+  final List<TypeInformation> assignments = <TypeInformation>[];
+  bool callsGrowableMethod = false;
+  
+  ContainerTracerVisitor(tracedType, inferrer) : super(tracedType, inferrer);
+
+  List<TypeInformation> run() {
+    analyze();
+    ListTypeInformation container = tracedType;
+    if (continueAnalyzing) {
+      if (!callsGrowableMethod && container.inferredLength == null) {
+        container.inferredLength = container.originalLength;
+      }
+      container.flowsInto.addAll(flowsInto);
+      return assignments;
+    } else {
+      callsGrowableMethod = true;
+      return null;
+    }
+  }
+
+  visitMapTypeInformation(MapTypeInformation info) {
+    bailout('Stored in a map');
+  }
+
+  visitClosureCallSiteTypeInformation(ClosureCallSiteTypeInformation info) {
+    bailout('Passed to a closure');
+  }
+
+  visitStaticCallSiteTypeInformation(StaticCallSiteTypeInformation info) {
+    Element called = info.calledElement;
+    if (called.isForeign(compiler) && called.name == 'JS') {
+      bailout('Used in JS ${info.call}');
+    }
+    super.visitStaticCallSiteTypeInformation(info);

[kasperl, 2013/12/11 07:35:35]

Is it important to call the super method at the bottom of the method? It seems
"cleaner" to always call it at the beginning (repeated in a number of places).

[ngeoffray, 2013/12/16 11:47:43]

Done.

+  }
+
   visitDynamicCallSiteTypeInformation(DynamicCallSiteTypeInformation info) {
     Selector selector = info.selector;
     String selectorName = selector.name;
     if (currentUser == info.receiver) {
       if (!okSelectorsSet.contains(selectorName)) {
         if (selector.isCall()) {
           int positionalLength = info.arguments.positional.length;
           if (selectorName == 'add') {
             if (positionalLength == 1) {
               assignments.add(info.arguments.positional[0]);
@@ skipping 17 matching lines @@
         callsGrowableMethod = true;
       }
       if (selectorName == 'length' && selector.isSetter()) {
         callsGrowableMethod = true;
         assignments.add(inferrer.types.nullType);
       }
     } else if (selector.isCall()
                && !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) {
-        ListTypeInformation container =
-            inferrer.types.allocatedLists[mask.allocationNode];
-        containersToAnalyze.add(container);
-      } else {
-        // The [ContainerTypeMask] is a union of two containers, and
-        // we lose track of where these containers have been allocated
-        // at this point.
-        bailout('Stored in too many containers');
-      }
     }
-
-    if (info.targets
-            .map((element) => inferrer.types.getInferredTypeOf(element))
-            .any((other) => other == currentUser)) {
-      addNewEscapeInformation(info);
-    }
+    super.visitDynamicCallSiteTypeInformation(info);
   }
 
   bool isClosure(Element element) {
     if (!element.isFunction()) return false;
     Element outermost = element.getOutermostEnclosingMemberOrTopLevel();
     return outermost.declaration != element.declaration;
   }
 
-  bool isParameterOfListAddingMethod(Element element) {
-    if (!element.isParameter()) return false;
-    if (element.getEnclosingClass() != compiler.backend.listImplementation) {
-      return false;
+  visitElementTypeInformation(ElementTypeInformation info) {
+    if (isClosure(info.element)) {
+      bailout('Returned from a closure');
     }
-    Element method = element.enclosingElement;
-    return (method.name == '[]=')
-        || (method.name == 'add')
-        || (method.name == 'insert');
+    if (compiler.backend.isNeededForReflection(info.element)) {
+      bailout('Escape in reflection');
+    }
+    super.visitElementTypeInformation(info);
+  }
+}
+
+class ClosureTracerVisitor extends TracerVisitor {
+  ClosureTracerVisitor(tracedType, inferrer) : super(tracedType, inferrer);
+
+  void run() {
+    ClosureTypeInformation closure = tracedType;
+    FunctionElement element = closure.element;
+    element.functionSignature.forEachParameter((Element parameter) {
+      ElementTypeInformation info = inferrer.types.getInferredTypeOf(parameter);
+      info.abandonInferencing = false;
+    });
+    analyze();
+    element.functionSignature.forEachParameter((Element parameter) {
+      ElementTypeInformation info = inferrer.types.getInferredTypeOf(parameter);
+      if (continueAnalyzing) {
+        info.turnSpecialNonSpecial = true;
+      } else {
+        info.giveUp(inferrer);
+      }
+    });
+  }
+
+  visitMapTypeInformation(MapTypeInformation info) {
+    bailout('Stored in a map');
+  }
+
+  void analyzeCall(CallSiteTypeInformation info) {
+    ClosureTypeInformation closure = tracedType;
+    FunctionElement element = closure.element;
+    Selector selector = info.selector;
+    if (!selector.appliesUntyped(element, compiler)) return;
+    inferrer.updateParameterAssignments(
+        info, element, info.arguments, selector, remove: false,
+        addToQueue: false);
+  }
+
+  visitClosureCallSiteTypeInformation(ClosureCallSiteTypeInformation info) {
+    if (info.closure == currentUser) {
+      analyzeCall(info);
+    } else {
+      bailout('Passed to a closure');
+    }
+  }
+
+  visitStaticCallSiteTypeInformation(StaticCallSiteTypeInformation info) {
+    Element called = info.calledElement;
+    if (called.isForeign(compiler) && called.name == 'JS') {
+      bailout('Used in JS ${info.call}');
+    }
+    super.visitStaticCallSiteTypeInformation(info);
+  }
+
+  bool checkIfCurrentUser(element) {
+    return inferrer.types.getInferredTypeOf(element) == currentUser;
+  }
+
+  visitDynamicCallSiteTypeInformation(DynamicCallSiteTypeInformation info) {
+    if (info.selector.isCall()) {
+      if (info.arguments.contains(currentUser)
+          && !info.targets.every((element) => element.isFunction())) {
+        bailout('Passed to a closure');
+      } else if (info.targets.any((element) => checkIfCurrentUser(element))) {
+        analyzeCall(info);
+      }
+    }
+    super.visitDynamicCallSiteTypeInformation(info);
+  }
+
+  bool isClosure(Element element) {
+    if (!element.isFunction()) return false;
+    Element outermost = element.getOutermostEnclosingMemberOrTopLevel();
+    return outermost.declaration != element.declaration;
   }
 
   visitElementTypeInformation(ElementTypeInformation info) {
     if (isClosure(info.element)) {
       bailout('Returned from a closure');
     }
     if (compiler.backend.isNeededForReflection(info.element)) {
       bailout('Escape in reflection');
     }
-    if (isParameterOfListAddingMethod(info.element)) {
-      // These elements are being handled in
-      // [visitDynamicCallSiteTypeInformation].
-      return;
-    }
-    addNewEscapeInformation(info);
+    super.visitElementTypeInformation(info);
   }
 }