Flatten inferrer implementation

pkg/compiler/lib/src/inferrer/inferrer_engine.dart

-// Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
+// Copyright (c) 2017, 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 type_graph_inferrer;
-
-import 'dart:collection' show Queue;
-
 import '../common.dart';
-import '../common/names.dart' show Identifiers;
-import '../compiler.dart' show Compiler;
-import '../constants/expressions.dart' show ConstantExpression;
+import '../common/names.dart';
+import '../compiler.dart';
+import '../constants/expressions.dart';
 import '../constants/values.dart';
-import '../elements/resolution_types.dart' show ResolutionDartType;
+import '../core_types.dart';
 import '../elements/elements.dart';
-import '../js_backend/js_backend.dart' show Annotations, JavaScriptBackend;
-import '../resolution/tree_elements.dart' show TreeElementMapping;
-import '../tree/dartstring.dart' show DartString;
-import '../tree/tree.dart' as ast show Node, LiteralBool, TryStatement;
-import '../types/constants.dart' show computeTypeMask;
-import '../types/masks.dart'
-    show CommonMasks, ContainerTypeMask, MapTypeMask, TypeMask;
-import '../types/types.dart' show TypesInferrer;
-import '../universe/call_structure.dart' show CallStructure;
-import '../universe/selector.dart' show Selector;
-import '../universe/side_effects.dart' show SideEffects;
-import '../util/util.dart' show Setlet;
-import '../world.dart' show ClosedWorld, ClosedWorldRefiner;
+import '../js_backend/js_backend.dart';
+import '../native/behavior.dart' as native;
+import '../resolution/tree_elements.dart';
+import '../tree/nodes.dart' as ast;
+import '../types/constants.dart';
+import '../types/types.dart';
+import '../universe/call_structure.dart';
+import '../universe/selector.dart';
+import '../universe/side_effects.dart';
+import '../util/util.dart';
+import '../world.dart';
 import 'closure_tracer.dart';
 import 'debug.dart' as debug;
-import 'inferrer_visitor.dart' show ArgumentsTypes, TypeSystem;
+import 'inferrer_visitor.dart';
 import 'list_tracer.dart';
 import 'map_tracer.dart';
 import 'simple_types_inferrer.dart';
 import 'type_graph_dump.dart';
+import 'type_graph_inferrer.dart';
 import 'type_graph_nodes.dart';
-
-class TypeInformationSystem extends TypeSystem<TypeInformation> {
-  final ClosedWorld closedWorld;
-
-  /// [ElementTypeInformation]s for elements.
-  final Map<Element, TypeInformation> typeInformations =
-      new Map<Element, TypeInformation>();
-
-  /// [ListTypeInformation] for allocated lists.
-  final Map<ast.Node, TypeInformation> allocatedLists =
-      new Map<ast.Node, TypeInformation>();
-
-  /// [MapTypeInformation] for allocated Maps.
-  final Map<ast.Node, TypeInformation> allocatedMaps =
-      new Map<ast.Node, TypeInformation>();
-
-  /// Closures found during the analysis.
-  final Set<TypeInformation> allocatedClosures = new Set<TypeInformation>();
-
-  /// Cache of [ConcreteTypeInformation].
-  final Map<TypeMask, TypeInformation> concreteTypes =
-      new Map<TypeMask, TypeInformation>();
-
-  /// List of [TypeInformation]s allocated inside method bodies (calls,
-  /// narrowing, phis, and containers).
-  final List<TypeInformation> allocatedTypes = <TypeInformation>[];
-
-  Iterable<TypeInformation> get allTypes => [
-        typeInformations.values,
-        allocatedLists.values,
-        allocatedMaps.values,
-        allocatedClosures,
-        concreteTypes.values,
-        allocatedTypes
-      ].expand((x) => x);
-
-  TypeInformationSystem(this.closedWorld) {
-    nonNullEmptyType = getConcreteTypeFor(commonMasks.emptyType);
-  }
-
-  CommonMasks get commonMasks => closedWorld.commonMasks;
-
-  /// Used to group [TypeInformation] nodes by the element that triggered their
-  /// creation.
-  MemberTypeInformation _currentMember = null;
-  MemberTypeInformation get currentMember => _currentMember;
-
-  void withMember(MemberElement element, action) {
-    assert(invariant(element, _currentMember == null,
-        message: "Already constructing graph for $_currentMember."));
-    _currentMember = getInferredTypeOf(element);
-    action();
-    _currentMember = null;
-  }
-
-  TypeInformation nullTypeCache;
-  TypeInformation get nullType {
-    if (nullTypeCache != null) return nullTypeCache;
-    return nullTypeCache = getConcreteTypeFor(commonMasks.nullType);
-  }
-
-  TypeInformation intTypeCache;
-  TypeInformation get intType {
-    if (intTypeCache != null) return intTypeCache;
-    return intTypeCache = getConcreteTypeFor(commonMasks.intType);
-  }
-
-  TypeInformation uint32TypeCache;
-  TypeInformation get uint32Type {
-    if (uint32TypeCache != null) return uint32TypeCache;
-    return uint32TypeCache = getConcreteTypeFor(commonMasks.uint32Type);
-  }
-
-  TypeInformation uint31TypeCache;
-  TypeInformation get uint31Type {
-    if (uint31TypeCache != null) return uint31TypeCache;
-    return uint31TypeCache = getConcreteTypeFor(commonMasks.uint31Type);
-  }
-
-  TypeInformation positiveIntTypeCache;
-  TypeInformation get positiveIntType {
-    if (positiveIntTypeCache != null) return positiveIntTypeCache;
-    return positiveIntTypeCache =
-        getConcreteTypeFor(commonMasks.positiveIntType);
-  }
-
-  TypeInformation doubleTypeCache;
-  TypeInformation get doubleType {
-    if (doubleTypeCache != null) return doubleTypeCache;
-    return doubleTypeCache = getConcreteTypeFor(commonMasks.doubleType);
-  }
-
-  TypeInformation numTypeCache;
-  TypeInformation get numType {
-    if (numTypeCache != null) return numTypeCache;
-    return numTypeCache = getConcreteTypeFor(commonMasks.numType);
-  }
-
-  TypeInformation boolTypeCache;
-  TypeInformation get boolType {
-    if (boolTypeCache != null) return boolTypeCache;
-    return boolTypeCache = getConcreteTypeFor(commonMasks.boolType);
-  }
-
-  TypeInformation functionTypeCache;
-  TypeInformation get functionType {
-    if (functionTypeCache != null) return functionTypeCache;
-    return functionTypeCache = getConcreteTypeFor(commonMasks.functionType);
-  }
-
-  TypeInformation listTypeCache;
-  TypeInformation get listType {
-    if (listTypeCache != null) return listTypeCache;
-    return listTypeCache = getConcreteTypeFor(commonMasks.listType);
-  }
-
-  TypeInformation constListTypeCache;
-  TypeInformation get constListType {
-    if (constListTypeCache != null) return constListTypeCache;
-    return constListTypeCache = getConcreteTypeFor(commonMasks.constListType);
-  }
-
-  TypeInformation fixedListTypeCache;
-  TypeInformation get fixedListType {
-    if (fixedListTypeCache != null) return fixedListTypeCache;
-    return fixedListTypeCache = getConcreteTypeFor(commonMasks.fixedListType);
-  }
-
-  TypeInformation growableListTypeCache;
-  TypeInformation get growableListType {
-    if (growableListTypeCache != null) return growableListTypeCache;
-    return growableListTypeCache =
-        getConcreteTypeFor(commonMasks.growableListType);
-  }
-
-  TypeInformation mapTypeCache;
-  TypeInformation get mapType {
-    if (mapTypeCache != null) return mapTypeCache;
-    return mapTypeCache = getConcreteTypeFor(commonMasks.mapType);
-  }
-
-  TypeInformation constMapTypeCache;
-  TypeInformation get constMapType {
-    if (constMapTypeCache != null) return constMapTypeCache;
-    return constMapTypeCache = getConcreteTypeFor(commonMasks.constMapType);
-  }
-
-  TypeInformation stringTypeCache;
-  TypeInformation get stringType {
-    if (stringTypeCache != null) return stringTypeCache;
-    return stringTypeCache = getConcreteTypeFor(commonMasks.stringType);
-  }
-
-  TypeInformation typeTypeCache;
-  TypeInformation get typeType {
-    if (typeTypeCache != null) return typeTypeCache;
-    return typeTypeCache = getConcreteTypeFor(commonMasks.typeType);
-  }
-
-  TypeInformation dynamicTypeCache;
-  TypeInformation get dynamicType {
-    if (dynamicTypeCache != null) return dynamicTypeCache;
-    return dynamicTypeCache = getConcreteTypeFor(commonMasks.dynamicType);
-  }
-
-  TypeInformation asyncFutureTypeCache;
-  TypeInformation get asyncFutureType {
-    if (asyncFutureTypeCache != null) return asyncFutureTypeCache;
-    return asyncFutureTypeCache =
-        getConcreteTypeFor(commonMasks.asyncFutureType);
-  }
-
-  TypeInformation syncStarIterableTypeCache;
-  TypeInformation get syncStarIterableType {
-    if (syncStarIterableTypeCache != null) return syncStarIterableTypeCache;
-    return syncStarIterableTypeCache =
-        getConcreteTypeFor(commonMasks.syncStarIterableType);
-  }
-
-  TypeInformation asyncStarStreamTypeCache;
-  TypeInformation get asyncStarStreamType {
-    if (asyncStarStreamTypeCache != null) return asyncStarStreamTypeCache;
-    return asyncStarStreamTypeCache =
-        getConcreteTypeFor(commonMasks.asyncStarStreamType);
-  }
-
-  TypeInformation nonNullEmptyType;
-
-  TypeInformation stringLiteralType(DartString value) {
-    return new StringLiteralTypeInformation(value, commonMasks.stringType);
-  }
-
-  TypeInformation boolLiteralType(ast.LiteralBool value) {
-    return new BoolLiteralTypeInformation(value, commonMasks.boolType);
-  }
-
-  TypeInformation computeLUB(
-      TypeInformation firstType, TypeInformation secondType) {
-    if (firstType == null) return secondType;
-    if (firstType == secondType) return firstType;
-    if (firstType == nonNullEmptyType) return secondType;
-    if (secondType == nonNullEmptyType) return firstType;
-    if (firstType == dynamicType || secondType == dynamicType) {
-      return dynamicType;
-    }
-    return getConcreteTypeFor(
-        firstType.type.union(secondType.type, closedWorld));
-  }
-
-  bool selectorNeedsUpdate(TypeInformation info, TypeMask mask) {
-    return info.type != mask;
-  }
-
-  TypeInformation refineReceiver(Selector selector, TypeMask mask,
-      TypeInformation receiver, bool isConditional) {
-    if (receiver.type.isExact) return receiver;
-    TypeMask otherType = closedWorld.allFunctions.receiverType(selector, mask);
-    // Conditional sends (a?.b) can still narrow the possible types of `a`,
-    // however, we still need to consider that `a` may be null.
-    if (isConditional) {
-      // Note: we don't check that receiver.type.isNullable here because this is
-      // called during the graph construction.
-      otherType = otherType.nullable();
-    }
-    // If this is refining to nullable subtype of `Object` just return
-    // the receiver. We know the narrowing is useless.
-    if (otherType.isNullable && otherType.containsAll(closedWorld)) {
-      return receiver;
-    }
-    assert(TypeMask.assertIsNormalized(otherType, closedWorld));
-    TypeInformation newType = new NarrowTypeInformation(receiver, otherType);
-    allocatedTypes.add(newType);
-    return newType;
-  }
-
-  TypeInformation narrowType(
-      TypeInformation type, ResolutionDartType annotation,
-      {bool isNullable: true}) {
-    if (annotation.treatAsDynamic) return type;
-    if (annotation.isVoid) return nullType;
-    if (annotation.element == closedWorld.commonElements.objectClass &&
-        isNullable) {
-      return type;
-    }
-    TypeMask otherType;
-    if (annotation.isTypedef || annotation.isFunctionType) {
-      otherType = functionType.type;
-    } else if (annotation.isTypeVariable) {
-      // TODO(ngeoffray): Narrow to bound.
-      return type;
-    } else {
-      assert(annotation.isInterfaceType);
-      otherType = annotation.element == closedWorld.commonElements.objectClass
-          ? dynamicType.type.nonNullable()
-          : new TypeMask.nonNullSubtype(annotation.element, closedWorld);
-    }
-    if (isNullable) otherType = otherType.nullable();
-    if (type.type.isExact) {
-      return type;
-    } else {
-      assert(TypeMask.assertIsNormalized(otherType, closedWorld));
-      TypeInformation newType = new NarrowTypeInformation(type, otherType);
-      allocatedTypes.add(newType);
-      return newType;
-    }
-  }
-
-  TypeInformation narrowNotNull(TypeInformation type) {
-    if (type.type.isExact && !type.type.isNullable) {
-      return type;
-    }
-    TypeInformation newType =
-        new NarrowTypeInformation(type, dynamicType.type.nonNullable());
-    allocatedTypes.add(newType);
-    return newType;
-  }
-
-  ElementTypeInformation getInferredTypeOf(Element element) {
-    element = element.implementation;
-    return typeInformations.putIfAbsent(element, () {
-      return new ElementTypeInformation(element, this);
-    });
-  }
-
-  ConcreteTypeInformation getConcreteTypeFor(TypeMask mask) {
-    assert(mask != null);
-    return concreteTypes.putIfAbsent(mask, () {
-      return new ConcreteTypeInformation(mask);
-    });
-  }
-
-  String getInferredSignatureOf(FunctionElement function) {
-    ElementTypeInformation info = getInferredTypeOf(function);
-    FunctionElement impl = function.implementation;
-    FunctionSignature signature = impl.functionSignature;
-    var res = "";
-    signature.forEachParameter((Element parameter) {
-      TypeInformation type = getInferredTypeOf(parameter);
-      res += "${res.isEmpty ? '(' : ', '}${type.type} ${parameter.name}";
-    });
-    res += ") -> ${info.type}";
-    return res;
-  }
-
-  TypeInformation nonNullSubtype(ClassElement type) {
-    return getConcreteTypeFor(
-        new TypeMask.nonNullSubtype(type.declaration, closedWorld));
-  }
-
-  TypeInformation nonNullSubclass(ClassElement type) {
-    return getConcreteTypeFor(
-        new TypeMask.nonNullSubclass(type.declaration, closedWorld));
-  }
-
-  TypeInformation nonNullExact(ClassElement type) {
-    return getConcreteTypeFor(
-        new TypeMask.nonNullExact(type.declaration, closedWorld));
-  }
-
-  TypeInformation nonNullEmpty() {
-    return nonNullEmptyType;
-  }
-
-  bool isNull(TypeInformation type) {
-    return type == nullType;
-  }
-
-  TypeInformation allocateList(
-      TypeInformation type, ast.Node node, Element enclosing,
-      [TypeInformation elementType, int length]) {
-    ClassElement typedDataClass = closedWorld.commonElements.typedDataClass;
-    bool isTypedArray = typedDataClass != null &&
-        closedWorld.isInstantiated(typedDataClass) &&
-        type.type.satisfies(typedDataClass, closedWorld);
-    bool isConst = (type.type == commonMasks.constListType);
-    bool isFixed =
-        (type.type == commonMasks.fixedListType) || isConst || isTypedArray;
-    bool isElementInferred = isConst || isTypedArray;
-
-    int inferredLength = isFixed ? length : null;
-    TypeMask elementTypeMask =
-        isElementInferred ? elementType.type : dynamicType.type;
-    ContainerTypeMask mask = new ContainerTypeMask(
-        type.type, node, enclosing, elementTypeMask, inferredLength);
-    ElementInContainerTypeInformation element =
-        new ElementInContainerTypeInformation(currentMember, elementType);
-    element.inferred = isElementInferred;
-
-    allocatedTypes.add(element);
-    return allocatedLists[node] =
-        new ListTypeInformation(currentMember, mask, element, length);
-  }
-
-  TypeInformation allocateClosure(ast.Node node, Element element) {
-    TypeInformation result =
-        new ClosureTypeInformation(currentMember, node, element);
-    allocatedClosures.add(result);
-    return result;
-  }
-
-  TypeInformation allocateMap(
-      ConcreteTypeInformation type, ast.Node node, Element element,
-      [List<TypeInformation> keyTypes, List<TypeInformation> valueTypes]) {
-    assert(keyTypes.length == valueTypes.length);
-    bool isFixed = (type.type == commonMasks.constMapType);
-
-    TypeMask keyType, valueType;
-    if (isFixed) {
-      keyType = keyTypes.fold(nonNullEmptyType.type,
-          (type, info) => type.union(info.type, closedWorld));
-      valueType = valueTypes.fold(nonNullEmptyType.type,
-          (type, info) => type.union(info.type, closedWorld));
-    } else {
-      keyType = valueType = dynamicType.type;
-    }
-    MapTypeMask mask =
-        new MapTypeMask(type.type, node, element, keyType, valueType);
-
-    TypeInformation keyTypeInfo =
-        new KeyInMapTypeInformation(currentMember, null);
-    TypeInformation valueTypeInfo =
-        new ValueInMapTypeInformation(currentMember, null);
-    allocatedTypes.add(keyTypeInfo);
-    allocatedTypes.add(valueTypeInfo);
-
-    MapTypeInformation map =
-        new MapTypeInformation(currentMember, mask, keyTypeInfo, valueTypeInfo);
-
-    for (int i = 0; i < keyTypes.length; ++i) {
-      TypeInformation newType =
-          map.addEntryAssignment(keyTypes[i], valueTypes[i], true);
-      if (newType != null) allocatedTypes.add(newType);
-    }
-
-    // Shortcut: If we already have a first approximation of the key/value type,
-    // start propagating it early.
-    if (isFixed) map.markAsInferred();
-
-    allocatedMaps[node] = map;
-    return map;
-  }
-
-  TypeMask newTypedSelector(TypeInformation info, TypeMask mask) {
-    // Only type the selector if [info] is concrete, because the other
-    // kinds of [TypeInformation] have the empty type at this point of
-    // analysis.
-    return info.isConcrete ? info.type : mask;
-  }
-
-  TypeInformation allocateDiamondPhi(
-      TypeInformation firstInput, TypeInformation secondInput) {
-    PhiElementTypeInformation result =
-        new PhiElementTypeInformation(currentMember, null, false, null);
-    result.addAssignment(firstInput);
-    result.addAssignment(secondInput);
-    allocatedTypes.add(result);
-    return result;
-  }
-
-  PhiElementTypeInformation _addPhi(
-      ast.Node node, Local variable, inputType, bool isLoop) {
-    PhiElementTypeInformation result =
-        new PhiElementTypeInformation(currentMember, node, isLoop, variable);
-    allocatedTypes.add(result);
-    result.addAssignment(inputType);
-    return result;
-  }
-
-  PhiElementTypeInformation allocatePhi(
-      ast.Node node, Local variable, inputType) {
-    // Check if [inputType] is a phi for a local updated in
-    // the try/catch block [node]. If it is, no need to allocate a new
-    // phi.
-    if (inputType is PhiElementTypeInformation &&
-        inputType.branchNode == node &&
-        inputType.branchNode is ast.TryStatement) {
-      return inputType;
-    }
-    return _addPhi(node, variable, inputType, false);
-  }
-
-  PhiElementTypeInformation allocateLoopPhi(
-      ast.Node node, Local variable, inputType) {
-    return _addPhi(node, variable, inputType, true);
-  }
-
-  TypeInformation simplifyPhi(
-      ast.Node node, Local variable, PhiElementTypeInformation phiType) {
-    assert(phiType.branchNode == node);
-    if (phiType.assignments.length == 1) return phiType.assignments.first;
-    return phiType;
-  }
-
-  PhiElementTypeInformation addPhiInput(Local variable,
-      PhiElementTypeInformation phiType, TypeInformation newType) {
-    phiType.addAssignment(newType);
-    return phiType;
-  }
-
-  TypeMask computeTypeMask(Iterable<TypeInformation> assignments) {
-    return joinTypeMasks(assignments.map((e) => e.type));
-  }
-
-  TypeMask joinTypeMasks(Iterable<TypeMask> masks) {
-    var dynamicType = commonMasks.dynamicType;
-    // Optimization: we are iterating over masks twice, but because `masks` is a
-    // mapped iterable, we save the intermediate results to avoid computing them
-    // again.
-    var list = [];
-    for (TypeMask mask in masks) {
-      // Don't do any work on computing unions if we know that after all that
-      // work the result will be `dynamic`.
-      // TODO(sigmund): change to `mask == dynamicType` so we can continue to
-      // track the non-nullable bit.
-      if (mask.containsAll(closedWorld)) return dynamicType;
-      list.add(mask);
-    }
-
-    TypeMask newType = null;
-    for (TypeMask mask in list) {
-      newType = newType == null ? mask : newType.union(mask, closedWorld);
-      // Likewise - stop early if we already reach dynamic.
-      if (newType.containsAll(closedWorld)) return dynamicType;
-    }
-
-    return newType ?? const TypeMask.nonNullEmpty();
-  }
-}
-
-/**
- * A work queue for the inferrer. It filters out nodes that are tagged as
- * [TypeInformation.doNotEnqueue], as well as ensures through
- * [TypeInformation.inQueue] that a node is in the queue only once at
- * a time.
- */
-class WorkQueue {
-  final Queue<TypeInformation> queue = new Queue<TypeInformation>();
-
-  void add(TypeInformation element) {
-    if (element.doNotEnqueue) return;
-    if (element.inQueue) return;
-    queue.addLast(element);
-    element.inQueue = true;
-  }
-
-  void addAll(Iterable<TypeInformation> all) {
-    all.forEach(add);
-  }
-
-  TypeInformation remove() {
-    TypeInformation element = queue.removeFirst();
-    element.inQueue = false;
-    return element;
-  }
-
-  bool get isEmpty => queue.isEmpty;
-
-  int get length => queue.length;
-}
+import 'type_system.dart';
 
 /**
  * An inferencing engine that computes a call graph of
  * [TypeInformation] nodes by visiting the AST of the application, and
  * then does the inferencing on the graph.
- *
  */
-class TypeGraphInferrerEngine
-    extends InferrerEngine<TypeInformation, TypeInformationSystem> {
+class InferrerEngine {
   final Map<Element, TypeInformation> defaultTypeOfParameter =
       new Map<Element, TypeInformation>();
   final List<CallSiteTypeInformation> allocatedCalls =
       <CallSiteTypeInformation>[];
   final WorkQueue workQueue = new WorkQueue();
   final Element mainElement;
   final Set<Element> analyzedElements = new Set<Element>();
 
   /// The maximum number of times we allow a node in the graph to
   /// change types. If a node reaches that limit, we give up
   /// inferencing on it and give it the dynamic type.
   final int MAX_CHANGE_COUNT = 6;
 
   int overallRefineCount = 0;
   int addedInGraph = 0;
 
-  TypeGraphInferrerEngine(Compiler compiler, ClosedWorld closedWorld,
-      ClosedWorldRefiner closedWorldRefiner, this.mainElement)
-      : super(compiler, closedWorld, closedWorldRefiner,
-            new TypeInformationSystem(closedWorld));
+  final Compiler compiler;
+
+  /// The [ClosedWorld] on which inference reasoning is based.
+  final ClosedWorld closedWorld;
+
+  final ClosedWorldRefiner closedWorldRefiner;
+  final TypeSystem types;
+  final Map<ast.Node, TypeInformation> concreteTypes =
+      new Map<ast.Node, TypeInformation>();
+  final Set<Element> generativeConstructorsExposingThis = new Set<Element>();
+
+  /// Data computed internally within elements, like the type-mask of a send a
+  /// list allocation, or a for-in loop.
+  final Map<Element, GlobalTypeInferenceElementData> inTreeData =
+      new Map<Element, GlobalTypeInferenceElementData>();
+
+  InferrerEngine(this.compiler, ClosedWorld closedWorld,
+      this.closedWorldRefiner, this.mainElement)
+      : this.types = new TypeSystem(closedWorld),
+        this.closedWorld = closedWorld;
+
+  CommonElements get commonElements => closedWorld.commonElements;
+
+  /**
+   * Applies [f] to all elements in the universe that match
+   * [selector] and [mask]. If [f] returns false, aborts the iteration.
+   */
+  void forEachElementMatching(
+      Selector selector, TypeMask mask, bool f(Element element)) {
+    Iterable<Element> elements =
+        closedWorld.allFunctions.filter(selector, mask);
+    for (Element e in elements) {
+      if (!f(e.implementation)) return;
+    }
+  }
+
+  // TODO(johnniwinther): Make this private again.
+  GlobalTypeInferenceElementData dataOf(AstElement element) => inTreeData
+      .putIfAbsent(element, () => new GlobalTypeInferenceElementData());
+
+  /**
+   * Update [sideEffects] with the side effects of [callee] being
+   * called with [selector].
+   */
+  void updateSideEffects(
+      SideEffects sideEffects, Selector selector, Element callee) {
+    if (callee.isField) {
+      if (callee.isInstanceMember) {
+        if (selector.isSetter) {
+          sideEffects.setChangesInstanceProperty();
+        } else if (selector.isGetter) {
+          sideEffects.setDependsOnInstancePropertyStore();
+        } else {
+          sideEffects.setAllSideEffects();
+          sideEffects.setDependsOnSomething();
+        }
+      } else {
+        if (selector.isSetter) {
+          sideEffects.setChangesStaticProperty();
+        } else if (selector.isGetter) {
+          sideEffects.setDependsOnStaticPropertyStore();
+        } else {
+          sideEffects.setAllSideEffects();
+          sideEffects.setDependsOnSomething();
+        }
+      }
+    } else if (callee.isGetter && !selector.isGetter) {
+      sideEffects.setAllSideEffects();
+      sideEffects.setDependsOnSomething();
+    } else {
+      sideEffects.add(closedWorldRefiner.getCurrentlyKnownSideEffects(callee));
+    }
+  }
+
+  /**
+   * Returns the type for [nativeBehavior]. See documentation on
+   * [native.NativeBehavior].
+   */
+  TypeInformation typeOfNativeBehavior(native.NativeBehavior nativeBehavior) {
+    if (nativeBehavior == null) return types.dynamicType;
+    List typesReturned = nativeBehavior.typesReturned;
+    if (typesReturned.isEmpty) return types.dynamicType;
+    TypeInformation returnType;
+    for (var type in typesReturned) {
+      TypeInformation mappedType;
+      if (type == native.SpecialType.JsObject) {
+        mappedType = types.nonNullExact(commonElements.objectClass);
+      } else if (type == commonElements.stringType) {
+        mappedType = types.stringType;
+      } else if (type == commonElements.intType) {
+        mappedType = types.intType;
+      } else if (type == commonElements.numType ||
+          type == commonElements.doubleType) {
+        // Note: the backend double class is specifically for non-integer
+        // doubles, and a native behavior returning 'double' does not guarantee
+        // a non-integer return type, so we return the number type for those.
+        mappedType = types.numType;
+      } else if (type == commonElements.boolType) {
+        mappedType = types.boolType;
+      } else if (type == commonElements.nullType) {
+        mappedType = types.nullType;
+      } else if (type.isVoid) {
+        mappedType = types.nullType;
+      } else if (type.isDynamic) {
+        return types.dynamicType;
+      } else {
+        mappedType = types.nonNullSubtype(type.element);
+      }
+      returnType = types.computeLUB(returnType, mappedType);
+      if (returnType == types.dynamicType) {
+        break;
+      }
+    }
+    return returnType;
+  }
+
+  // TODO(johnniwinther): Pass the [ResolvedAst] instead of [owner].
+  void updateSelectorInTree(
+      AstElement owner, Spannable node, Selector selector, TypeMask mask) {
+    ast.Node astNode = node;
+    GlobalTypeInferenceElementData data = dataOf(owner);
+    if (astNode.asSendSet() != null) {
+      if (selector.isSetter || selector.isIndexSet) {
+        data.setTypeMask(node, mask);
+      } else if (selector.isGetter || selector.isIndex) {
+        data.setGetterTypeMaskInComplexSendSet(node, mask);
+      } else {
+        assert(selector.isOperator);
+        data.setOperatorTypeMaskInComplexSendSet(node, mask);
+      }
+    } else if (astNode.asSend() != null) {
+      data.setTypeMask(node, mask);
+    } else {
+      assert(astNode.asForIn() != null);
+      if (selector == Selectors.iterator) {
+        data.setIteratorTypeMask(node, mask);
+      } else if (selector == Selectors.current) {
+        data.setCurrentTypeMask(node, mask);
+      } else {
+        assert(selector == Selectors.moveNext);
+        data.setMoveNextTypeMask(node, mask);
+      }
+    }
+  }
+
+  bool isNativeElement(Element element) {
+    return compiler.backend.isNative(element);
+  }
+
+  bool checkIfExposesThis(Element element) {
+    element = element.implementation;
+    return generativeConstructorsExposingThis.contains(element);
+  }
+
+  void recordExposesThis(Element element, bool exposesThis) {
+    element = element.implementation;
+    if (exposesThis) {
+      generativeConstructorsExposingThis.add(element);
+    }
+  }
 
   JavaScriptBackend get backend => compiler.backend;
   Annotations get annotations => backend.annotations;
   DiagnosticReporter get reporter => compiler.reporter;
   CommonMasks get commonMasks => closedWorld.commonMasks;
 
   /**
    * A set of selector names that [List] implements, that we know return
    * their element type.
    */
@@ skipping 125 matching lines @@
             var info = types.getInferredTypeOf(parameter);
             info.maybeResume();
             workQueue.add(info);
           });
           if (tracer.tracedType.mightBePassedToFunctionApply) {
             closedWorldRefiner.registerMightBePassedToApply(e);
           }
           if (debug.VERBOSE) {
             print("traced closure $e as "
                 "${closedWorldRefiner
-                    .getCurrentlyKnownMightBePassedToApply(e)}");
+                .getCurrentlyKnownMightBePassedToApply(e)}");
           }
         });
       }
 
       if (info is ClosureTypeInformation) {
         Iterable<FunctionElement> elements = [info.element];
         trace(elements, new ClosureTracerVisitor(elements, info, this));
       } else if (info is CallSiteTypeInformation) {
         if (info is StaticCallSiteTypeInformation &&
             info.selector != null &&
@@ skipping 338 matching lines @@
    *            should be present and a default type for each parameter should
    *            exist.
    */
   TypeInformation getDefaultTypeOfParameter(Element parameter) {
     return defaultTypeOfParameter.putIfAbsent(parameter, () {
       return new PlaceholderTypeInformation(types.currentMember);
     });
   }
 
   /**
-   * Helper to inspect the [TypeGraphInferrer]'s state. To be removed by
-   * TODO(johnniwinther) once synthetic parameters get their own default
-   * values.
+   * This helper breaks abstractions but is currently required to work around
+   * the wrong modelling of default values of optional parameters of

[Siggi Cherem (dart-lang), 2017/01/06 18:59:56]

modelling => modeling

[Johnni Winther, 2017/01/09 09:01:49]

Done.

+   * synthetic constructors.
+   *
+   * TODO(johnniwinther): Remove once default values of synthetic parameters
+   * are fixed.
    */
   bool hasAlreadyComputedTypeOfParameterDefault(Element parameter) {
     TypeInformation seen = defaultTypeOfParameter[parameter];
     return (seen != null && seen is! PlaceholderTypeInformation);
   }
 
+  /**
+   * Returns the type of [element].
+   */
   TypeInformation typeOfElement(Element element) {
     if (element is FunctionElement) return types.functionType;
     return types.getInferredTypeOf(element);
   }
 
+  /**
+   * Returns the return type of [element].
+   */
   TypeInformation returnTypeOfElement(Element element) {
     if (element is! FunctionElement) return types.dynamicType;
     return types.getInferredTypeOf(element);
   }
 
+  /**
+   * Records that [node] sets final field [element] to be of type [type].
+   *
+   * [nodeHolder] is the element holder of [node].
+   */
   void recordTypeOfFinalField(
       Spannable node, Element analyzed, Element element, TypeInformation type) {
     types.getInferredTypeOf(element).addAssignment(type);
   }
 
+  /**
+   * Records that [node] sets non-final field [element] to be of type
+   * [type].
+   */
   void recordTypeOfNonFinalField(
       Spannable node, Element element, TypeInformation type) {
     types.getInferredTypeOf(element).addAssignment(type);
   }
 
+  /**
+   * Records that [element] is of type [type].
+   */
   void recordType(Element element, TypeInformation type) {
     types.getInferredTypeOf(element).addAssignment(type);
   }
 
+  /**
+   * Records that the return type [element] is of type [type].
+   */
   void recordReturnType(Element element, TypeInformation type) {
     TypeInformation info = types.getInferredTypeOf(element);
     if (element.name == '==') {
       // Even if x.== doesn't return a bool, 'x == null' evaluates to 'false'.
       info.addAssignment(types.boolType);
     }
     // TODO(ngeoffray): Clean up. We do these checks because
     // [SimpleTypesInferrer] deals with two different inferrers.
     if (type == null) return;
     if (info.assignments.isEmpty) info.addAssignment(type);
   }
 
+  /**
+   * Notifies to the inferrer that [analyzedElement] can have return
+   * type [newType]. [currentType] is the type the [InferrerVisitor]
+   * currently found.
+   *
+   * Returns the new type for [analyzedElement].
+   */
   TypeInformation addReturnTypeFor(
       Element element, TypeInformation unused, TypeInformation newType) {
     TypeInformation type = types.getInferredTypeOf(element);
     // TODO(ngeoffray): Clean up. We do this check because
     // [SimpleTypesInferrer] deals with two different inferrers.
     if (element.isGenerativeConstructor) return type;
     type.addAssignment(newType);
     return type;
   }
 
+  /**
+   * Registers that [caller] calls [callee] at location [node], with
+   * [selector], and [arguments]. Note that [selector] is null for
+   * forwarding constructors.
+   *
+   * [sideEffects] will be updated to incorporate [callee]'s side
+   * effects.
+   *
+   * [inLoop] tells whether the call happens in a loop.
+   */
   TypeInformation registerCalledElement(
       Spannable node,
       Selector selector,
       TypeMask mask,
       Element caller,
       Element callee,
       ArgumentsTypes arguments,
       SideEffects sideEffects,
       bool inLoop) {
     CallSiteTypeInformation info = new StaticCallSiteTypeInformation(
@@ skipping 12 matching lines @@
       if (cls.callType != null) {
         types.allocatedClosures.add(info);
       }
     }
     info.addToGraph(this);
     allocatedCalls.add(info);
     updateSideEffects(sideEffects, selector, callee);
     return info;
   }
 
+  /**
+   * Registers that [caller] calls [selector] with [receiverType] as
+   * receiver, and [arguments].
+   *
+   * [sideEffects] will be updated to incorporate the potential
+   * callees' side effects.
+   *
+   * [inLoop] tells whether the call happens in a loop.
+   */
   TypeInformation registerCalledSelector(
       ast.Node node,
       Selector selector,
       TypeMask mask,
       TypeInformation receiverType,
       Element caller,
       ArgumentsTypes arguments,
       SideEffects sideEffects,
       bool inLoop) {
     if (selector.isClosureCall) {
@@ skipping 13 matching lines @@
         mask,
         receiverType,
         arguments,
         inLoop);
 
     info.addToGraph(this);
     allocatedCalls.add(info);
     return info;
   }
 
+  /**
+   * Registers a call to await with an expression of type [argumentType] as
+   * argument.
+   */
   TypeInformation registerAwait(ast.Node node, TypeInformation argument) {
     AwaitTypeInformation info =
         new AwaitTypeInformation(types.currentMember, node);
     info.addAssignment(argument);
     types.allocatedTypes.add(info);
     return info;
   }
 
+  /**
+   * Registers that [caller] calls [closure] with [arguments].
+   *
+   * [sideEffects] will be updated to incorporate the potential
+   * callees' side effects.
+   *
+   * [inLoop] tells whether the call happens in a loop.
+   */
   TypeInformation registerCalledClosure(
       ast.Node node,
       Selector selector,
       TypeMask mask,
       TypeInformation closure,
       Element caller,
       ArgumentsTypes arguments,
       SideEffects sideEffects,
       bool inLoop) {
     sideEffects.setDependsOnSomething();
@@ skipping 112 matching lines @@
         return returnTypeOfElement(element);
       }
     } else if (element.isGetter || element.isField) {
       assert(selector.isCall || selector.isSetter);
       return types.dynamicType;
     } else {
       return returnTypeOfElement(element);
     }
   }
 
+  /**
+   * Records that the captured variable [local] is read.
+   */
   void recordCapturedLocalRead(Local local) {}
 
+  /**
+   * Records that the variable [local] is being updated.
+   */
   void recordLocalUpdate(Local local, TypeInformation type) {}
 }
-
-class TypeGraphInferrer implements TypesInferrer {
-  TypeGraphInferrerEngine inferrer;
-  final Compiler compiler;
-  final ClosedWorld closedWorld;
-  final ClosedWorldRefiner closedWorldRefiner;
-
-  TypeGraphInferrer(this.compiler, this.closedWorld, this.closedWorldRefiner);
-
-  String get name => 'Graph inferrer';
-
-  CommonMasks get commonMasks => closedWorld.commonMasks;
-
-  TypeMask get _dynamicType => commonMasks.dynamicType;
-
-  void analyzeMain(Element main) {
-    inferrer = new TypeGraphInferrerEngine(
-        compiler, closedWorld, closedWorldRefiner, main);
-    inferrer.runOverAllElements();
-  }
-
-  TypeMask getReturnTypeOfElement(Element element) {
-    if (compiler.disableTypeInference) return _dynamicType;
-    // Currently, closure calls return dynamic.
-    if (element is! FunctionElement) return _dynamicType;
-    return inferrer.types.getInferredTypeOf(element).type;
-  }
-
-  TypeMask getTypeOfElement(Element element) {
-    if (compiler.disableTypeInference) return _dynamicType;
-    // The inferrer stores the return type for a function, so we have to
-    // be careful to not return it here.
-    if (element is FunctionElement) return commonMasks.functionType;
-    return inferrer.types.getInferredTypeOf(element).type;
-  }
-
-  TypeMask getTypeForNewList(Element owner, ast.Node node) {
-    if (compiler.disableTypeInference) return _dynamicType;
-    return inferrer.types.allocatedLists[node].type;
-  }
-
-  bool isFixedArrayCheckedForGrowable(ast.Node node) {
-    if (compiler.disableTypeInference) return true;
-    ListTypeInformation info = inferrer.types.allocatedLists[node];
-    return info.checksGrowable;
-  }
-
-  TypeMask getTypeOfSelector(Selector selector, TypeMask mask) {
-    if (compiler.disableTypeInference) return _dynamicType;
-    // Bailout for closure calls. We're not tracking types of
-    // closures.
-    if (selector.isClosureCall) return _dynamicType;
-    if (selector.isSetter || selector.isIndexSet) {
-      return _dynamicType;
-    }
-    if (inferrer.returnsListElementType(selector, mask)) {
-      ContainerTypeMask containerTypeMask = mask;
-      TypeMask elementType = containerTypeMask.elementType;
-      return elementType == null ? _dynamicType : elementType;
-    }
-    if (inferrer.returnsMapValueType(selector, mask)) {
-      MapTypeMask mapTypeMask = mask;
-      TypeMask valueType = mapTypeMask.valueType;
-      return valueType == null ? _dynamicType : valueType;
-    }
-
-    TypeMask result = const TypeMask.nonNullEmpty();
-    Iterable<Element> elements =
-        inferrer.closedWorld.allFunctions.filter(selector, mask);
-    for (Element element in elements) {
-      TypeMask type =
-          inferrer.typeOfElementWithSelector(element, selector).type;
-      result = result.union(type, inferrer.closedWorld);
-    }
-    return result;
-  }
-
-  Iterable<Element> getCallersOf(Element element) {
-    if (compiler.disableTypeInference) {
-      throw new UnsupportedError(
-          "Cannot query the type inferrer when type inference is disabled.");
-    }
-    return inferrer.getCallersOf(element);
-  }
-
-  bool isCalledOnce(Element element) {
-    if (compiler.disableTypeInference) return false;
-    MemberTypeInformation info = inferrer.types.getInferredTypeOf(element);
-    return info.isCalledOnce();
-  }
-
-  void clear() {
-    inferrer.clear();
-  }
-}