Flatten inferrer implementation

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

Index: pkg/compiler/lib/src/inferrer/type_system.dart
diff --git a/pkg/compiler/lib/src/inferrer/type_system.dart b/pkg/compiler/lib/src/inferrer/type_system.dart
new file mode 100644
index 0000000000000000000000000000000000000000..da755b91a93462bea061c6881e6cbf0a934525aa
--- /dev/null
+++ b/pkg/compiler/lib/src/inferrer/type_system.dart
@@ -0,0 +1,555 @@
+// 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.
+
+import '../common.dart';
+import '../elements/elements.dart';
+import '../elements/resolution_types.dart' show ResolutionDartType;
+import '../tree/dartstring.dart';
+import '../tree/nodes.dart' as ast;
+import '../types/masks.dart';
+import '../universe/selector.dart';
+import '../world.dart';
+import 'type_graph_nodes.dart';
+
+/**
+ * The class [SimpleInferrerVisitor] will use when working on types.
+ */
+class TypeSystem {
+  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);
+
+  TypeSystem(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;
+  // Subtype of Future returned by async methods.
+  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);
+  }
+
+  /**
+   * Returns the least upper bound between [firstType] and
+   * [secondType].
+   */
+  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));
+  }
+
+  /**
+   * Returns `true` if `selector` should be updated to reflect the new
+   * `receiverType`.
+   */
+  bool selectorNeedsUpdate(TypeInformation info, TypeMask mask) {
+    return info.type != mask;
+  }
+
+  /**
+   * Returns a new receiver type for this [selector] applied to
+   * [receiverType].
+   *
+   * The option [isConditional] is true when [selector] was seen in a
+   * conditional send (e.g.  `a?.selector`), in which case the returned type may
+   * be null.
+   */
+  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;
+  }
+
+  /**
+   * Returns the intersection between [type] and [annotation].
+   * [isNullable] indicates whether the annotation implies a null
+   * type.
+   */
+  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;
+    }
+  }
+
+  /**
+   * Returns the non-nullable type of [type].
+   */
+  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);
+    });
+  }
+
+  /**
+   * Returns the internal inferrer representation for [mask].
+   */
+  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;
+  }
+
+  /**
+   * Returns a new type that unions [firstInput] and [secondInput].
+   */
+  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;
+  }
+
+  /**
+   * Returns a new type for holding the potential types of [element].
+   * [inputType] is the first incoming type of the phi.
+   */
+  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);
+  }
+
+  /**
+   * Returns a new type for holding the potential types of [element].
+   * [inputType] is the first incoming type of the phi. [allocateLoopPhi]
+   * only differs from [allocatePhi] in that it allows the underlying
+   * implementation of [TypeSystem] to differentiate Phi nodes due to loops
+   * from other merging uses.
+   */
+  PhiElementTypeInformation allocateLoopPhi(
+      ast.Node node, Local variable, inputType) {
+    return _addPhi(node, variable, inputType, true);
+  }
+
+  /**
+   * Simplies the phi representing [element] and of the type
+   * [phiType]. For example, if this phi has one incoming input, an
+   * implementation of this method could just return that incoming
+   * input type.
+   */
+  TypeInformation simplifyPhi(
+      ast.Node node, Local variable, PhiElementTypeInformation phiType) {
+    assert(phiType.branchNode == node);
+    if (phiType.assignments.length == 1) return phiType.assignments.first;
+    return phiType;
+  }
+
+  /**
+   * Adds [newType] as an input of [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();
+  }
+}