| // Copyright (c) 2012, 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 concrete_types_inferrer; |
| |
| import 'dart:collection' show Queue, IterableBase; |
| import '../native_handler.dart' as native; |
| import '../dart2jslib.dart' hide Selector, TypedSelector; |
| import '../dart_types.dart' show DartType, TypeKind; |
| import '../elements/elements.dart'; |
| import '../tree/tree.dart'; |
| import '../universe/universe.dart'; |
| import '../util/util.dart'; |
| |
| import 'inferrer_visitor.dart'; |
| import '../types/types.dart' show TypeMask, FlatTypeMask, UnionTypeMask, |
| TypesInferrer; |
| import 'simple_types_inferrer.dart'; |
| |
| /** |
| * A singleton concrete type. More precisely, a [BaseType] is one of the |
| * following: |
| * |
| * - a non-asbtract class like [:int:] or [:Uri:] (but not [:List:]) |
| * - the null base type |
| * - the unknown base type |
| */ |
| abstract class BaseType { |
| bool isClass(); |
| bool isUnknown(); |
| bool isNull(); |
| } |
| |
| /** |
| * A non-asbtract class like [:int:] or [:Uri:] (but not [:List:]). |
| */ |
| class ClassBaseType implements BaseType { |
| final ClassElement element; |
| |
| ClassBaseType(this.element); |
| |
| bool operator ==(var other) { |
| if (identical(this, other)) return true; |
| if (other is! ClassBaseType) return false; |
| return element == other.element; |
| } |
| int get hashCode => element.hashCode; |
| String toString() { |
| return element == null ? 'toplevel' : element.name; |
| } |
| bool isClass() => true; |
| bool isUnknown() => false; |
| bool isNull() => false; |
| } |
| |
| /** |
| * The unknown base type. |
| */ |
| class UnknownBaseType implements BaseType { |
| const UnknownBaseType(); |
| bool operator ==(BaseType other) => other is UnknownBaseType; |
| int get hashCode => 0; |
| bool isClass() => false; |
| bool isUnknown() => true; |
| bool isNull() => false; |
| toString() => "unknown"; |
| } |
| |
| /** |
| * The null base type. |
| */ |
| class NullBaseType implements BaseType { |
| const NullBaseType(); |
| bool operator ==(BaseType other) => identical(other, this); |
| int get hashCode => 1; |
| bool isClass() => false; |
| bool isUnknown() => false; |
| bool isNull() => true; |
| toString() => "null"; |
| } |
| |
| /** |
| * An immutable set of base types like [:{int, bool}:], or the unknown concrete |
| * type. |
| */ |
| abstract class ConcreteType { |
| ConcreteType(); |
| |
| factory ConcreteType.empty(int maxConcreteTypeSize, |
| BaseTypes classBaseTypes) { |
| return new UnionType(maxConcreteTypeSize, classBaseTypes, |
| new Set<BaseType>()); |
| } |
| |
| /** |
| * The singleton constituted of the unknown base type is the unknown concrete |
| * type. |
| */ |
| factory ConcreteType.singleton(int maxConcreteTypeSize, |
| BaseTypes classBaseTypes, |
| BaseType baseType) { |
| if (baseType.isUnknown() || maxConcreteTypeSize < 1) { |
| return const UnknownConcreteType(); |
| } |
| Set<BaseType> singletonSet = new Set<BaseType>(); |
| singletonSet.add(baseType); |
| return new UnionType(maxConcreteTypeSize, classBaseTypes, singletonSet); |
| } |
| |
| factory ConcreteType.unknown() { |
| return const UnknownConcreteType(); |
| } |
| |
| ConcreteType union(ConcreteType other); |
| ConcreteType intersection(ConcreteType other); |
| ConcreteType refine(Selector selector, Compiler compiler); |
| bool isUnknown(); |
| bool isEmpty(); |
| Set<BaseType> get baseTypes; |
| |
| /** |
| * Returns the unique element of [:this:] if [:this:] is a singleton, null |
| * otherwise. |
| */ |
| ClassElement getUniqueType(); |
| } |
| |
| /** |
| * The unkown concrete type: it is absorbing for the union. |
| */ |
| class UnknownConcreteType implements ConcreteType { |
| const UnknownConcreteType(); |
| bool isUnknown() => true; |
| bool isEmpty() => false; |
| bool operator ==(ConcreteType other) => identical(this, other); |
| Set<BaseType> get baseTypes => |
| new Set<BaseType>.from([const UnknownBaseType()]); |
| int get hashCode => 0; |
| ConcreteType union(ConcreteType other) => this; |
| ConcreteType intersection(ConcreteType other) => other; |
| ConcreteType refine(Selector selector, Compiler compiler) => this; |
| ClassElement getUniqueType() => null; |
| toString() => "unknown"; |
| } |
| |
| /** |
| * An immutable set of base types, like [: {int, bool} :]. |
| */ |
| class UnionType implements ConcreteType { |
| final int maxConcreteTypeSize; |
| final BaseTypes classBaseTypes; |
| |
| final Set<BaseType> baseTypes; |
| |
| /** |
| * The argument should NOT be mutated later. Do not call directly, use |
| * ConcreteType.singleton instead. |
| */ |
| UnionType(this.maxConcreteTypeSize, this.classBaseTypes, this.baseTypes); |
| |
| bool isUnknown() => false; |
| bool isEmpty() => baseTypes.isEmpty; |
| |
| bool operator ==(ConcreteType other) { |
| if (other is! UnionType) return false; |
| if (baseTypes.length != other.baseTypes.length) return false; |
| return baseTypes.containsAll(other.baseTypes); |
| } |
| |
| int get hashCode { |
| int result = 1; |
| for (final baseType in baseTypes) { |
| result = 31 * result + baseType.hashCode; |
| } |
| return result; |
| } |
| |
| ConcreteType _simplify(Set<BaseType> baseTypes) { |
| // normalize all flavors of ints to int |
| // TODO(polux): handle different ints better |
| if (baseTypes.contains(classBaseTypes.uint31Type)) { |
| baseTypes.remove(classBaseTypes.uint31Type); |
| baseTypes.add(classBaseTypes.intBaseType); |
| } |
| if (baseTypes.contains(classBaseTypes.uint32Type)) { |
| baseTypes.remove(classBaseTypes.uint32Type); |
| baseTypes.add(classBaseTypes.intBaseType); |
| } |
| if (baseTypes.contains(classBaseTypes.positiveIntType)) { |
| baseTypes.remove(classBaseTypes.positiveIntType); |
| baseTypes.add(classBaseTypes.intBaseType); |
| } |
| // normalize {int, float}, {int, num} or {float, num} into num |
| // TODO(polux): generalize this to all types when we extend the concept of |
| // "concrete type" to other abstract classes than num |
| if (baseTypes.contains(classBaseTypes.numBaseType) || |
| (baseTypes.contains(classBaseTypes.intBaseType) |
| && baseTypes.contains(classBaseTypes.doubleBaseType))) { |
| baseTypes.remove(classBaseTypes.intBaseType); |
| baseTypes.remove(classBaseTypes.doubleBaseType); |
| baseTypes.add(classBaseTypes.numBaseType); |
| } |
| |
| // widen big types to dynamic |
| return baseTypes.length > maxConcreteTypeSize |
| ? const UnknownConcreteType() |
| : new UnionType(maxConcreteTypeSize, classBaseTypes, baseTypes); |
| } |
| |
| ConcreteType union(ConcreteType other) { |
| if (other.isUnknown()) { |
| return const UnknownConcreteType(); |
| } |
| UnionType otherUnion = other; // cast |
| Set<BaseType> newBaseTypes = new Set<BaseType>.from(baseTypes); |
| newBaseTypes.addAll(otherUnion.baseTypes); |
| return _simplify(newBaseTypes); |
| } |
| |
| ConcreteType intersection(ConcreteType other) { |
| if (other.isUnknown()) { |
| return this; |
| } |
| Set<BaseType> thisBaseTypes = new Set<BaseType>.from(baseTypes); |
| Set<BaseType> otherBaseTypes = new Set<BaseType>.from(other.baseTypes); |
| return _simplify(thisBaseTypes.intersection(otherBaseTypes)); |
| } |
| |
| ConcreteType refine(Selector selector, Compiler compiler) { |
| Set<BaseType> newBaseTypes = new Set<BaseType>(); |
| for (BaseType baseType in baseTypes) { |
| if (baseType.isClass()) { |
| ClassBaseType classBaseType = baseType; |
| if (classBaseType.element.lookupSelector(selector, compiler) != null) { |
| newBaseTypes.add(baseType); |
| } |
| } else { |
| newBaseTypes.add(baseType); |
| } |
| } |
| return _simplify(newBaseTypes); |
| } |
| |
| ClassElement getUniqueType() { |
| if (baseTypes.length == 1) { |
| var iterator = baseTypes.iterator; |
| iterator.moveNext(); |
| BaseType uniqueBaseType = iterator.current; |
| if (uniqueBaseType.isClass()) { |
| ClassBaseType uniqueClassType = uniqueBaseType; |
| return uniqueClassType.element; |
| } |
| } |
| return null; |
| } |
| |
| String toString() => baseTypes.toString(); |
| } |
| |
| class ConcreteTypeSystem extends TypeSystem<ConcreteType> { |
| final Compiler compiler; |
| final ConcreteTypesInferrer inferrer; |
| final BaseTypes baseTypes; |
| |
| final ConcreteType nullType; |
| final ConcreteType _intType; |
| final ConcreteType _uint31Type; |
| final ConcreteType _uint32Type; |
| final ConcreteType _positiveIntType; |
| final ConcreteType _doubleType; |
| final ConcreteType _numType; |
| final ConcreteType _boolType; |
| final ConcreteType _functionType; |
| final ConcreteType _listType; |
| final ConcreteType _constListType; |
| final ConcreteType _fixedListType; |
| final ConcreteType _growableListType; |
| final ConcreteType _mapType; |
| final ConcreteType _constMapType; |
| final ConcreteType _stringType; |
| |
| final ConcreteType dynamicType; |
| final ConcreteType typeType; |
| final ConcreteType nonNullEmptyType; |
| |
| ConcreteTypeSystem.internal(ConcreteTypesInferrer inferrer, |
| BaseTypes baseTypes, |
| ConcreteType singleton(BaseType baseType)) |
| : this.compiler = inferrer.compiler |
| , this.inferrer = inferrer |
| , this.baseTypes = baseTypes |
| , this._constListType = singleton(baseTypes.constMapBaseType) |
| , this._constMapType = singleton(baseTypes.constMapBaseType) |
| , this._doubleType = singleton(baseTypes.doubleBaseType) |
| , this._fixedListType = singleton(baseTypes.fixedListBaseType) |
| , this._functionType = singleton(baseTypes.functionBaseType) |
| , this._growableListType = singleton(baseTypes.growableListBaseType) |
| , this._intType = singleton(baseTypes.intBaseType) |
| , this._listType = singleton(baseTypes.listBaseType) |
| , this._mapType = singleton(baseTypes.mapBaseType) |
| , this._numType = singleton(baseTypes.numBaseType) |
| , this._boolType = singleton(baseTypes.boolBaseType) |
| , this._stringType = singleton(baseTypes.stringBaseType) |
| , this.typeType = singleton(baseTypes.typeBaseType) |
| , this.dynamicType = const UnknownConcreteType() |
| , this.nullType = singleton(const NullBaseType()) |
| , this.nonNullEmptyType = new ConcreteType.empty( |
| inferrer.compiler.maxConcreteTypeSize, baseTypes) |
| // TODO(polux): have better types here |
| , this._uint31Type = singleton(baseTypes.intBaseType) |
| , this._uint32Type = singleton(baseTypes.intBaseType) |
| , this._positiveIntType = singleton(baseTypes.intBaseType); |
| |
| factory ConcreteTypeSystem(ConcreteTypesInferrer inferrer) { |
| Compiler compiler = inferrer.compiler; |
| BaseTypes baseTypes = new BaseTypes(compiler); |
| return new ConcreteTypeSystem.internal( |
| inferrer, |
| baseTypes, |
| (BaseType baseType) => new ConcreteType.singleton( |
| compiler.maxConcreteTypeSize, baseTypes, baseType)); |
| } |
| |
| @override |
| ConcreteType get intType { |
| inferrer.augmentSeenClasses(compiler.backend.intImplementation); |
| return _intType; |
| } |
| |
| @override |
| ConcreteType get uint31Type { |
| inferrer.augmentSeenClasses(compiler.backend.uint31Implementation); |
| return _uint31Type; |
| } |
| |
| @override |
| ConcreteType get uint32Type { |
| inferrer.augmentSeenClasses(compiler.backend.uint32Implementation); |
| return _uint32Type; |
| } |
| |
| @override |
| ConcreteType get positiveIntType { |
| inferrer.augmentSeenClasses(compiler.backend.positiveIntImplementation); |
| return _positiveIntType; |
| } |
| |
| @override |
| ConcreteType get doubleType { |
| inferrer.augmentSeenClasses(compiler.backend.doubleImplementation); |
| return _doubleType; |
| } |
| |
| @override |
| ConcreteType get numType { |
| inferrer.augmentSeenClasses(compiler.backend.numImplementation); |
| return _numType; |
| } |
| |
| @override |
| ConcreteType get boolType { |
| inferrer.augmentSeenClasses(compiler.backend.boolImplementation); |
| return _boolType; |
| } |
| |
| @override |
| ConcreteType get functionType { |
| inferrer.augmentSeenClasses(compiler.backend.functionImplementation); |
| return _functionType; |
| } |
| |
| @override |
| ConcreteType get listType { |
| inferrer.augmentSeenClasses(compiler.backend.listImplementation); |
| return _listType; |
| } |
| |
| @override |
| ConcreteType get constListType { |
| inferrer.augmentSeenClasses(compiler.backend.constListImplementation); |
| return _constListType; |
| } |
| |
| @override |
| ConcreteType get fixedListType { |
| inferrer.augmentSeenClasses(compiler.backend.fixedListImplementation); |
| return _fixedListType; |
| } |
| |
| @override |
| ConcreteType get growableListType { |
| inferrer.augmentSeenClasses(compiler.backend.growableListImplementation); |
| return _growableListType; |
| } |
| |
| @override |
| ConcreteType get mapType { |
| inferrer.augmentSeenClasses(compiler.backend.mapImplementation); |
| return _mapType; |
| } |
| |
| @override |
| ConcreteType get constMapType { |
| inferrer.augmentSeenClasses(compiler.backend.constMapImplementation); |
| return _constMapType; |
| } |
| |
| @override |
| ConcreteType get stringType { |
| inferrer.augmentSeenClasses(compiler.backend.stringImplementation); |
| return _stringType; |
| } |
| |
| @override |
| ConcreteType stringLiteralType(_) { |
| inferrer.augmentSeenClasses(compiler.backend.stringImplementation); |
| return _stringType; |
| } |
| |
| /** |
| * Returns the [TypeMask] representation of [baseType]. |
| */ |
| TypeMask baseTypeToTypeMask(BaseType baseType) { |
| if (baseType.isUnknown()) { |
| return const DynamicTypeMask(); |
| } else if (baseType.isNull()) { |
| return new TypeMask.empty(); |
| } else { |
| ClassBaseType classBaseType = baseType; |
| final element = classBaseType.element; |
| assert(element != null); |
| if (element == compiler.backend.numImplementation) { |
| return new TypeMask.nonNullSubclass(compiler.backend.numImplementation); |
| } else if (element == compiler.backend.intImplementation) { |
| return new TypeMask.nonNullSubclass(compiler.backend.intImplementation); |
| } else { |
| return new TypeMask.nonNullExact(element.declaration); |
| } |
| } |
| } |
| |
| /** |
| * Returns the [TypeMask] representation of [concreteType]. |
| */ |
| TypeMask concreteTypeToTypeMask(ConcreteType concreteType) { |
| if (concreteType == null) return null; |
| TypeMask typeMask = new TypeMask.nonNullEmpty(); |
| for (BaseType baseType in concreteType.baseTypes) { |
| TypeMask baseMask = baseTypeToTypeMask(baseType); |
| if (baseMask == const DynamicTypeMask()) return baseMask; |
| typeMask = typeMask.union(baseMask, compiler); |
| } |
| return typeMask; |
| } |
| |
| @override |
| ConcreteType addPhiInput(Element element, |
| ConcreteType phiType, |
| ConcreteType newType) { |
| return computeLUB(phiType, newType); |
| } |
| |
| @override |
| ConcreteType allocateDiamondPhi(ConcreteType firstInput, |
| ConcreteType secondInput) { |
| return computeLUB(firstInput, secondInput); |
| } |
| |
| @override |
| ConcreteType allocatePhi(Node node, Element element, ConcreteType inputType) { |
| return inputType; |
| } |
| |
| @override |
| ConcreteType computeLUB(ConcreteType firstType, ConcreteType secondType) { |
| if (firstType == null) { |
| return secondType; |
| } else if (secondType == null) { |
| return firstType; |
| } else { |
| return firstType.union(secondType); |
| } |
| } |
| |
| // Implementation Inspired by |
| // type_graph_inferrer.TypeInformationSystem.narrowType |
| @override |
| ConcreteType narrowType(ConcreteType type, |
| DartType annotation, |
| {bool isNullable: true}) { |
| if (annotation.treatAsDynamic) return type; |
| if (annotation.isVoid) return nullType; |
| if (annotation.element == compiler.objectClass) return type; |
| ConcreteType otherType; |
| if (annotation.isTypedef || annotation.isFunctionType) { |
| otherType = functionType; |
| } else if (annotation.isTypeVariable) { |
| // TODO(polux): Narrow to bound. |
| return type; |
| } else { |
| assert(annotation.isInterfaceType); |
| otherType = nonNullSubtype(annotation.element); |
| } |
| if (isNullable) otherType = otherType.union(nullType); |
| if (type == null) return otherType; |
| return type.intersection(otherType); |
| } |
| |
| @override |
| Selector newTypedSelector(ConcreteType receiver, Selector selector) { |
| return new TypedSelector(concreteTypeToTypeMask(receiver), selector, |
| compiler); |
| } |
| |
| @override |
| ConcreteType nonNullEmpty() { |
| return nonNullEmptyType; |
| } |
| |
| @override |
| ConcreteType nonNullExact(ClassElement cls) { |
| return nonNullSubtype(cls); |
| } |
| |
| /** |
| * Helper method for [nonNullSubtype] and [nonNullSubclass]. |
| */ |
| ConcreteType nonNullSubX(ClassElement cls, |
| Set<ClassElement> extractor(ClassElement cls)) { |
| if (cls == compiler.objectClass) { |
| return dynamicType; |
| } |
| ConcreteType result = nonNullEmptyType; |
| void registerClass(ClassElement element) { |
| if (!element.isAbstract) { |
| result = result.union( |
| new ConcreteType.singleton(compiler.maxConcreteTypeSize, |
| baseTypes, |
| new ClassBaseType(element))); |
| inferrer.augmentSeenClasses(element); |
| } |
| } |
| registerClass(cls); |
| Set<ClassElement> subtypes = extractor(cls); |
| if (subtypes != null) { |
| subtypes.forEach(registerClass); |
| } |
| return result; |
| } |
| |
| @override |
| ConcreteType nonNullSubclass(ClassElement cls) { |
| return nonNullSubX(cls, compiler.world.subclassesOf); |
| } |
| |
| @override |
| ConcreteType nonNullSubtype(ClassElement cls) { |
| return nonNullSubX(cls, compiler.world.subtypesOf); |
| } |
| |
| @override |
| ConcreteType simplifyPhi(Node node, Element element, ConcreteType phiType) { |
| return phiType; |
| } |
| |
| @override |
| ConcreteType refineReceiver(Selector selector, ConcreteType receiverType) { |
| return receiverType.refine(selector, compiler); |
| } |
| |
| @override |
| bool isNull(ConcreteType type) { |
| return (type.baseTypes.length == 1) && (type.baseTypes.first.isNull()); |
| } |
| |
| @override |
| ConcreteType allocateClosure(Node node, Element element) { |
| // TODO(polux): register closure here instead of in visitor? |
| return functionType; |
| } |
| |
| @override |
| ConcreteType allocateList(ConcreteType type, |
| Node node, |
| Element enclosing, |
| [ConcreteType elementType, int length]) { |
| if (elementType != null) { |
| inferrer.augmentListElementType(elementType); |
| } |
| return type; |
| } |
| |
| @override |
| ConcreteType allocateMap(ConcreteType type, |
| Node node, |
| Element element, |
| [List<ConcreteType> keyTypes, |
| List<ConcreteType> valueTypes]) { |
| // TODO(polux): treat maps the same way we treat lists |
| return type; |
| } |
| |
| @override |
| ConcreteType getConcreteTypeFor(TypeMask mask) { |
| if (mask.isUnion) { |
| UnionTypeMask union = mask; |
| return union.disjointMasks.fold( |
| nonNullEmptyType, |
| (type1, type2) => type1.union(getConcreteTypeFor(type2))); |
| } else { |
| FlatTypeMask flat = mask; |
| ConcreteType result; |
| if (flat.isEmpty) { |
| result = nonNullEmptyType; |
| } else if (flat.isExact) { |
| result = nonNullExact(flat.base); |
| } else if (flat.isSubclass) { |
| result = nonNullSubclass(flat.base); |
| } else if (flat.isSubtype) { |
| result = nonNullSubtype(flat.base); |
| } else { |
| throw new ArgumentError("unexpected mask"); |
| } |
| return flat.isNullable ? result.union(nullType) : result; |
| } |
| } |
| } |
| |
| /** |
| * The cartesian product of concrete types: an iterable of |
| * [ConcreteTypesEnvironment]s. |
| */ |
| class ConcreteTypeCartesianProduct |
| extends IterableBase<ConcreteTypesEnvironment> { |
| final ConcreteTypesInferrer inferrer; |
| final ClassElement typeOfThis; |
| final Map<Element, ConcreteType> concreteTypes; |
| ConcreteTypeCartesianProduct(this.inferrer, this.typeOfThis, |
| this.concreteTypes); |
| Iterator get iterator => concreteTypes.isEmpty |
| ? [new ConcreteTypesEnvironment(typeOfThis)].iterator |
| : new ConcreteTypeCartesianProductIterator(inferrer, typeOfThis, |
| concreteTypes); |
| String toString() => this.toList().toString(); |
| } |
| |
| /** |
| * An helper class for [ConcreteTypeCartesianProduct]. |
| */ |
| class ConcreteTypeCartesianProductIterator |
| implements Iterator<ConcreteTypesEnvironment> { |
| final ConcreteTypesInferrer inferrer; |
| final ClassElement classOfThis; |
| final Map<Element, ConcreteType> concreteTypes; |
| final Map<Element, BaseType> nextValues; |
| final Map<Element, Iterator> state; |
| int size = 1; |
| int counter = 0; |
| ConcreteTypesEnvironment _current; |
| |
| ConcreteTypeCartesianProductIterator(this.inferrer, this.classOfThis, |
| Map<Element, ConcreteType> concreteTypes) |
| : this.concreteTypes = concreteTypes, |
| nextValues = new Map<Element, BaseType>(), |
| state = new Map<Element, Iterator>() { |
| if (concreteTypes.isEmpty) { |
| size = 0; |
| return; |
| } |
| for (final e in concreteTypes.keys) { |
| final baseTypes = concreteTypes[e].baseTypes; |
| size *= baseTypes.length; |
| } |
| } |
| |
| ConcreteTypesEnvironment get current => _current; |
| |
| ConcreteTypesEnvironment takeSnapshot() { |
| Map<Element, ConcreteType> result = new Map<Element, ConcreteType>(); |
| nextValues.forEach((k, v) { |
| result[k] = inferrer.singletonConcreteType(v); |
| }); |
| return new ConcreteTypesEnvironment.of(result, classOfThis); |
| } |
| |
| bool moveNext() { |
| if (counter >= size) { |
| _current = null; |
| return false; |
| } |
| Element keyToIncrement = null; |
| for (final key in concreteTypes.keys) { |
| final iterator = state[key]; |
| if (iterator != null && iterator.moveNext()) { |
| nextValues[key] = state[key].current; |
| break; |
| } |
| Iterator newIterator = concreteTypes[key].baseTypes.iterator; |
| state[key] = newIterator; |
| newIterator.moveNext(); |
| nextValues[key] = newIterator.current; |
| } |
| counter++; |
| _current = takeSnapshot(); |
| return true; |
| } |
| } |
| |
| /** |
| * [BaseType] Constants. |
| */ |
| class BaseTypes { |
| final ClassBaseType intBaseType; |
| final ClassBaseType doubleBaseType; |
| final ClassBaseType numBaseType; |
| final ClassBaseType boolBaseType; |
| final ClassBaseType stringBaseType; |
| final ClassBaseType listBaseType; |
| final ClassBaseType growableListBaseType; |
| final ClassBaseType fixedListBaseType; |
| final ClassBaseType constListBaseType; |
| final ClassBaseType mapBaseType; |
| final ClassBaseType constMapBaseType; |
| final ClassBaseType objectBaseType; |
| final ClassBaseType typeBaseType; |
| final ClassBaseType functionBaseType; |
| final ClassBaseType uint31Type; |
| final ClassBaseType uint32Type; |
| final ClassBaseType positiveIntType; |
| |
| BaseTypes(Compiler compiler) : |
| intBaseType = new ClassBaseType(compiler.backend.intImplementation), |
| doubleBaseType = new ClassBaseType(compiler.backend.doubleImplementation), |
| numBaseType = new ClassBaseType(compiler.backend.numImplementation), |
| boolBaseType = new ClassBaseType(compiler.backend.boolImplementation), |
| stringBaseType = new ClassBaseType(compiler.backend.stringImplementation), |
| listBaseType = new ClassBaseType(compiler.backend.listImplementation), |
| growableListBaseType = |
| new ClassBaseType(compiler.backend.growableListImplementation), |
| fixedListBaseType = |
| new ClassBaseType(compiler.backend.fixedListImplementation), |
| constListBaseType = |
| new ClassBaseType(compiler.backend.constListImplementation), |
| mapBaseType = new ClassBaseType(compiler.backend.mapImplementation), |
| constMapBaseType = |
| new ClassBaseType(compiler.backend.constMapImplementation), |
| objectBaseType = new ClassBaseType(compiler.objectClass), |
| typeBaseType = new ClassBaseType(compiler.backend.typeImplementation), |
| functionBaseType = |
| new ClassBaseType(compiler.backend.functionImplementation), |
| uint31Type = new ClassBaseType(compiler.backend.uint31Implementation), |
| uint32Type = new ClassBaseType(compiler.backend.uint32Implementation), |
| positiveIntType = |
| new ClassBaseType(compiler.backend.positiveIntImplementation); |
| } |
| |
| /** |
| * An immutable mapping from method arguments to [ConcreteTypes]. |
| */ |
| class ConcreteTypesEnvironment { |
| final Map<Element, ConcreteType> environment; |
| final ClassElement classOfThis; |
| |
| ConcreteTypesEnvironment([this.classOfThis]) : |
| environment = new Map<Element, ConcreteType>(); |
| ConcreteTypesEnvironment.of(this.environment, this.classOfThis); |
| |
| ConcreteType lookupType(Element element) => environment[element]; |
| |
| bool operator ==(ConcreteTypesEnvironment other) { |
| if (other is! ConcreteTypesEnvironment) return false; |
| if (classOfThis != other.classOfThis) return false; |
| if (environment.length != other.environment.length) return false; |
| for (Element key in environment.keys) { |
| if (!other.environment.containsKey(key) |
| || (environment[key] != other.environment[key])) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| int get hashCode { |
| int result = (classOfThis != null) ? classOfThis.hashCode : 1; |
| environment.forEach((element, concreteType) { |
| result = 31 * (31 * result + element.hashCode) + concreteType.hashCode; |
| }); |
| return result; |
| } |
| |
| String toString() => "{ this: $classOfThis, env: $environment }"; |
| } |
| |
| class ClosureEnvironment { |
| ConcreteType thisType; |
| final LocalsHandler locals; |
| |
| ClosureEnvironment(this.thisType, this.locals); |
| |
| bool mergeLocals(LocalsHandler newLocals) { |
| assert((locals == null) == (newLocals == null)); |
| return (locals != null) ? locals.mergeAll([newLocals]) : false; |
| } |
| |
| /// Returns true if changed. |
| bool merge(ConcreteType thisType, LocalsHandler locals) { |
| ConcreteType oldThisType = this.thisType; |
| if (this.thisType == null) { |
| this.thisType = thisType; |
| } else if (thisType != null) { |
| this.thisType = this.thisType.union(thisType); |
| } |
| return mergeLocals(locals) || (this.thisType != oldThisType); |
| } |
| |
| toString() => "ClosureEnvironment { thisType = $thisType, locals = ... }"; |
| } |
| |
| /** |
| * A set of encoutered closures. |
| */ |
| class Closures { |
| final Compiler compiler; |
| final Map<FunctionElement, ClosureEnvironment> closures = |
| new Map<FunctionElement, ClosureEnvironment>(); |
| |
| Closures(this.compiler); |
| |
| /// Returns true if the environment of the closure has changed. |
| bool put(FunctionElement closure, |
| ConcreteType typeOfThis, |
| LocalsHandler locals) { |
| ClosureEnvironment oldEnvironent = closures[closure]; |
| if (oldEnvironent == null) { |
| closures[closure] = new ClosureEnvironment(typeOfThis, locals); |
| return true; |
| } else { |
| return oldEnvironent.merge(typeOfThis, locals); |
| } |
| } |
| |
| ClosureEnvironment getEnvironmentOrNull(FunctionElement function) { |
| return closures[function]; |
| } |
| |
| Iterable<FunctionElement> get functionElements => closures.keys; |
| |
| bool contains(FunctionElement function) => closures.containsKey(function); |
| |
| String toString() => closures.toString(); |
| } |
| |
| /** |
| * A work item for the type inference queue. |
| */ |
| class InferenceWorkItem { |
| Element method; |
| ConcreteTypesEnvironment environment; |
| InferenceWorkItem(this.method, this.environment); |
| |
| toString() => "{ method = $method, environment = $environment }"; |
| |
| bool operator ==(other) { |
| return (other is InferenceWorkItem) |
| && method == other.method |
| && environment == other.environment; |
| } |
| |
| int get hashCode => 31 * method.hashCode + environment.hashCode; |
| } |
| |
| /** |
| * A sentinel type mask class representing the dynamicType. It is absorbing |
| * for [:ConcreteTypesEnvironment.typeMaskUnion:]. |
| */ |
| class DynamicTypeMask implements TypeMask { |
| const DynamicTypeMask(); |
| |
| String toString() => 'sentinel type mask'; |
| |
| TypeMask nullable() { |
| throw new UnsupportedError(""); |
| } |
| |
| TypeMask nonNullable() { |
| throw new UnsupportedError(""); |
| } |
| |
| bool get isEmpty { |
| throw new UnsupportedError(""); |
| } |
| |
| bool get isNullable { |
| throw new UnsupportedError(""); |
| } |
| |
| bool get isExact { |
| throw new UnsupportedError(""); |
| } |
| |
| bool get isUnion { |
| throw new UnsupportedError(""); |
| } |
| |
| bool get isContainer { |
| throw new UnsupportedError(""); |
| } |
| |
| bool get isMap { |
| throw new UnsupportedError(""); |
| } |
| |
| bool get isDictionary { |
| throw new UnsupportedError(""); |
| } |
| |
| bool get isForwarding { |
| throw new UnsupportedError(""); |
| } |
| |
| bool get isValue { |
| throw new UnsupportedError(""); |
| } |
| |
| bool containsOnlyInt(Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| bool containsOnlyDouble(Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| bool containsOnlyNum(Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| bool containsOnlyBool(Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| bool containsOnlyString(Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| bool containsOnly(ClassElement element) { |
| throw new UnsupportedError(""); |
| } |
| |
| bool satisfies(ClassElement cls, Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| bool contains(ClassElement type, Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| bool containsAll(Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| ClassElement singleClass(Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| TypeMask union(TypeMask other, Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| TypeMask intersection(TypeMask other, Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| bool canHit(Element element, Selector selector, Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| Element locateSingleElement(Selector selector, Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| bool needsNoSuchMethodHandling(Selector selector, Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| bool isInMask(TypeMask other, Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| bool containsMask(TypeMask other, Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| } |
| |
| class WorkQueue { |
| final Queue<InferenceWorkItem> queue = new Queue<InferenceWorkItem>(); |
| |
| void add(InferenceWorkItem workItem) { |
| if (!queue.contains(workItem)) { |
| queue.addLast(workItem); |
| } |
| } |
| |
| InferenceWorkItem remove() { |
| return queue.removeFirst(); |
| } |
| |
| bool get isEmpty => queue.isEmpty; |
| } |
| |
| /** |
| * A task which conservatively infers a [ConcreteType] for each sub expression |
| * of the program. The entry point is [analyzeMain]. |
| */ |
| class ConcreteTypesInferrer |
| extends InferrerEngine<ConcreteType, ConcreteTypeSystem> |
| implements TypesInferrer { |
| |
| final String name = "Type inferrer"; |
| |
| /** |
| * When true, the string literal [:"__dynamic_for_test":] is inferred to |
| * have the unknown type. |
| */ |
| // TODO(polux): get rid of this hack once we have a natural way of inferring |
| // the unknown type. |
| bool testMode = false; |
| |
| // --- constants --- |
| |
| /** |
| * Constants representing builtin base types. Initialized by [initialize] |
| * and not by the constructor because the compiler elements are not yet |
| * populated. |
| */ |
| BaseTypes baseTypes; |
| |
| /** The associated type system */ |
| ConcreteTypeSystem types; |
| |
| /** |
| * Constant representing [:ConcreteList#[]:] where [:ConcreteList:] is the |
| * concrete implementation of lists for the selected backend. |
| */ |
| FunctionElement listIndex; |
| |
| /** |
| * Constant representing [:ConcreteList#[]=:] where [:ConcreteList:] is the |
| * concrete implementation of lists for the selected backend. |
| */ |
| FunctionElement listIndexSet; |
| |
| /** |
| * Constant representing [:ConcreteList#add:] where [:ConcreteList:] is the |
| * concrete implementation of lists for the selected backend. |
| */ |
| FunctionElement listAdd; |
| |
| /** |
| * Constant representing [:ConcreteList#removeAt:] where [:ConcreteList:] is |
| * the concrete implementation of lists for the selected backend. |
| */ |
| FunctionElement listRemoveAt; |
| |
| /** |
| * Constant representing [:ConcreteList#insert:] where [:ConcreteList:] is |
| * the concrete implementation of lists for the selected backend. |
| */ |
| FunctionElement listInsert; |
| |
| /** |
| * Constant representing [:ConcreteList#removeLast:] where [:ConcreteList:] is |
| * the concrete implementation of lists for the selected backend. |
| */ |
| FunctionElement listRemoveLast; |
| |
| /** Constant representing [:List():]. */ |
| FunctionElement listConstructor; |
| |
| /** The unknown concrete type */ |
| final ConcreteType unknownConcreteType; |
| |
| /** The empty concrete type */ |
| ConcreteType emptyConcreteType; |
| |
| /** The null concrete type */ |
| ConcreteType nullConcreteType; |
| |
| // --- state updated by the inference --- |
| |
| /** |
| * A map from (function x argument base types) to their inferred concrete |
| * type. Another way of seeing [methodToTemplates] is as a map from |
| * [FunctionElement]s to "templates" in the sense of "The Cartesian Product |
| * Algorithm - Simple and Precise Type Inference of Parametric Polymorphism" |
| * by Ole Agesen. |
| */ |
| // TODO(polux): build a better abstraction, like Closures |
| final Map<FunctionElement, Map<ConcreteTypesEnvironment, ConcreteType>> |
| methodToTemplates; |
| |
| /** The set of encountered closures. */ |
| final Closures closures; |
| |
| /** A map from expressions to their inferred concrete types. */ |
| final Map<Node, ConcreteType> inferredTypes; |
| |
| /** A map from fields to their inferred concrete types. */ |
| final Map<Element, ConcreteType> inferredFieldTypes; |
| |
| /** |
| * [:callers[f]:] is the list of [:f:]'s possible callers or fields |
| * whose initialization is a call to [:f:]. |
| */ |
| final Map<FunctionElement, Set<Element>> callers; |
| |
| /** |
| * [:readers[field]:] is the list of [:field:]'s possible readers or fields |
| * whose initialization is a read of [:field:]. |
| */ |
| final Map<Element, Set<Element>> fieldReaders; |
| |
| /** |
| * [:readers[local]:] is the list of [:local:]'s possible readers. |
| */ |
| final Map<Element, Set<Element>> capuredLocalsReaders; |
| |
| /// The set of classes encountered so far. |
| final Set<ClassElement> seenClasses; |
| |
| /** |
| * A map from selector names to callers of methods with this name on objects |
| * of unknown inferred type. |
| */ |
| final Map<String, Set<FunctionElement>> dynamicCallers; |
| |
| /** 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. |
| */ |
| final Map<VariableElement, ConcreteType> inferredParameterTypes; |
| |
| /** |
| * A map from selectors to their inferred type masks, indexed by the mask |
| * of the receiver. It plays no role in the analysis, it is write only. |
| */ |
| final Map<Selector, Map<TypeMask, TypeMask>> inferredSelectorTypes; |
| |
| /** The work queue consumed by [analyzeMain]. */ |
| final WorkQueue workQueue; |
| |
| /** The item being worked on. */ |
| InferenceWorkItem currentWorkItem; |
| |
| ConcreteTypesInferrer(Compiler compiler) |
| : methodToTemplates = new Map<FunctionElement, |
| Map<ConcreteTypesEnvironment, ConcreteType>>(), |
| closures = new Closures(compiler), |
| inferredTypes = new Map<Node, ConcreteType>(), |
| inferredFieldTypes = new Map<Element, ConcreteType>(), |
| inferredParameterTypes = new Map<VariableElement, ConcreteType>(), |
| workQueue = new WorkQueue(), |
| callers = new Map<FunctionElement, Set<Element>>(), |
| fieldReaders = new Map<Element, Set<Element>>(), |
| capuredLocalsReaders = new Map<VariableElement, |
| Set<FunctionElement>>(), |
| seenClasses = new Set<ClassElement>(), |
| dynamicCallers = new Map<String, Set<FunctionElement>>(), |
| inferredSelectorTypes = new Map<Selector, Map<TypeMask, TypeMask>>(), |
| unknownConcreteType = new ConcreteType.unknown(), |
| super(compiler, null); |
| |
| /* 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); |
| types = new ConcreteTypeSystem(this); |
| ClassElement jsArrayClass = baseTypes.listBaseType.element; |
| listIndex = jsArrayClass.lookupMember('[]'); |
| listIndexSet = jsArrayClass.lookupMember('[]='); |
| listAdd = jsArrayClass.lookupMember('add'); |
| listRemoveAt = jsArrayClass.lookupMember('removeAt'); |
| listInsert = jsArrayClass.lookupMember('insert'); |
| listRemoveLast = |
| jsArrayClass.lookupMember('removeLast'); |
| List<String> typePreservingOps = const ['+', '-', '*']; |
| listConstructor = |
| compiler.listClass.lookupConstructor( |
| new Selector.callConstructor( |
| '', |
| compiler.listClass.library)).implementation; |
| emptyConcreteType = new ConcreteType.empty(compiler.maxConcreteTypeSize, |
| baseTypes); |
| nullConcreteType = singletonConcreteType(const NullBaseType()); |
| listElementType = emptyConcreteType; |
| } |
| |
| // --- utility methods --- |
| |
| /** Creates a singleton concrete type containing [baseType]. */ |
| ConcreteType singletonConcreteType(BaseType baseType) { |
| return new ConcreteType.singleton(compiler.maxConcreteTypeSize, baseTypes, |
| baseType); |
| } |
| |
| /** |
| * Computes the union of [mask1] and [mask2] where [mask1] and [mask2] are |
| * possibly equal to [: DynamicTypeMask.instance :]. |
| */ |
| TypeMask typeMaskUnion(TypeMask mask1, TypeMask mask2) { |
| if (mask1 == const DynamicTypeMask() || mask2 == const DynamicTypeMask()) { |
| return const DynamicTypeMask(); |
| } |
| return mask1.union(mask2, compiler); |
| } |
| |
| /** |
| * Returns all the members matching [selector]. |
| */ |
| Set<Element> getMembersBySelector(Selector selector) { |
| // TODO(polux): memoize? |
| Set<Element> result = new Set<Element>(); |
| for (ClassElement cls in seenClasses) { |
| Element elem = cls.lookupSelector(selector, compiler); |
| if (elem != null) { |
| result.add(elem.implementation); |
| } |
| } |
| return result; |
| } |
| |
| /** |
| * Returns all the subtypes of [cls], [cls] included. |
| */ |
| Set<ClassElement> getReflexiveSubtypesOf(ClassElement cls) { |
| // TODO(polux): memoize? |
| Set<ClassElement> result = new Set<ClassElement>()..add(cls); |
| for (ClassElement candidate in seenClasses) { |
| if (compiler.world.isSubtype(cls, candidate)) { |
| result.add(candidate); |
| } |
| } |
| return result; |
| } |
| |
| /** |
| * Sets the concrete type associated to [node] to the union of the inferred |
| * concrete type so far and of [type]. |
| */ |
| void augmentInferredType(Node node, ConcreteType type) { |
| ConcreteType currentType = inferredTypes[node]; |
| inferredTypes[node] = |
| (currentType == null) ? type : currentType.union(type); |
| } |
| |
| /** |
| * Sets the concrete type associated to [selector] to the union of the |
| * inferred concrete type so far and of [returnType]. |
| * |
| * Precondition: [:(typeOfThis != null) && (returnType != null):] |
| */ |
| void augmentInferredSelectorType(Selector selector, TypeMask typeOfThis, |
| TypeMask returnType) { |
| assert(returnType != null); |
| assert(typeOfThis != null); |
| |
| selector = selector.asUntyped; |
| Map<TypeMask, TypeMask> currentMap = inferredSelectorTypes.putIfAbsent( |
| selector, () => new Map<TypeMask, TypeMask>()); |
| TypeMask currentReturnType = currentMap[typeOfThis]; |
| currentMap[typeOfThis] = (currentReturnType == null) |
| ? returnType |
| : typeMaskUnion(currentReturnType, returnType); |
| } |
| |
| /** |
| * Returns the current inferred concrete type of [field]. |
| */ |
| ConcreteType getFieldType(Selector selector, Element field) { |
| ensureFieldInitialized(field); |
| ConcreteType result = inferredFieldTypes[field]; |
| result = (result == null) ? emptyConcreteType : result; |
| if (selector != null) { |
| Element enclosing = field.enclosingElement; |
| if (enclosing.isClass) { |
| ClassElement cls = enclosing; |
| TypeMask receiverMask = new TypeMask.exact(cls.declaration); |
| TypeMask resultMask = types.concreteTypeToTypeMask(result); |
| augmentInferredSelectorType(selector, receiverMask, resultMask); |
| } |
| } |
| return result; |
| } |
| |
| /** |
| * Sets the concrete type associated to [field] to the union of the inferred |
| * concrete type so far and of [type]. |
| */ |
| void augmentFieldType(Element field, ConcreteType type) { |
| ensureFieldInitialized(field); |
| ConcreteType oldType = inferredFieldTypes[field]; |
| ConcreteType newType = (oldType != null) ? oldType.union(type) : type; |
| if (oldType != newType) { |
| inferredFieldTypes[field] = newType; |
| invalidateReaders(field); |
| } |
| } |
| |
| /** Augment the inferred type of elements stored in Lists. */ |
| void augmentListElementType(ConcreteType type) { |
| ConcreteType newType = listElementType.union(type); |
| if (newType != listElementType) { |
| invalidateCallers(listIndex); |
| listElementType = newType; |
| } |
| } |
| |
| /** |
| * Sets the concrete type associated to [parameter] to the union of the |
| * inferred concrete type so far and of [type]. |
| */ |
| void augmentParameterType(VariableElement parameter, ConcreteType type) { |
| ConcreteType oldType = inferredParameterTypes[parameter]; |
| inferredParameterTypes[parameter] = |
| (oldType == null) ? type : oldType.union(type); |
| } |
| |
| /** Augments the set of classes encountered so far. */ |
| void augmentSeenClasses(ClassElement cls) { |
| if (!seenClasses.contains(cls)) { |
| seenClasses.add(cls); |
| cls.forEachMember((_, Element member) { |
| Set<FunctionElement> functions = dynamicCallers[member.name]; |
| if (functions != null) { |
| functions.forEach(invalidate); |
| } |
| }, includeSuperAndInjectedMembers: true); |
| } |
| } |
| |
| /** |
| * Add [caller] to the set of [callee]'s callers. |
| */ |
| void addCaller(FunctionElement callee, Element caller) { |
| callers.putIfAbsent(callee, () => new Set<Element>()) |
| .add(caller); |
| } |
| |
| /** |
| * Add [caller] to the set of [callee]'s dynamic callers. |
| */ |
| void addDynamicCaller(Selector callee, FunctionElement caller) { |
| dynamicCallers |
| .putIfAbsent(callee.name, () => new Set<FunctionElement>()) |
| .add(caller); |
| } |
| |
| /** |
| * Add [reader] to the set of [field]'s readers. |
| */ |
| void addFieldReader(Element field, Element reader) { |
| fieldReaders.putIfAbsent(field, () => new Set<Element>()) |
| .add(reader); |
| } |
| |
| /** |
| * Add [reader] to the set of [local]'s readers. |
| */ |
| void addCapturedLocalReader(VariableElement local, FunctionElement reader) { |
| capuredLocalsReaders.putIfAbsent(local, () => new Set<FunctionElement>()) |
| .add(reader); |
| } |
| |
| /** |
| * Add a closure to the set of seen closures. Invalidate callers if |
| * the set of locals has changed. |
| */ |
| void addClosure(FunctionElement closure, |
| ConcreteType typeOfThis, |
| LocalsHandler locals) { |
| if (closures.put(closure, typeOfThis, locals)) { |
| invalidateCallers(closure); |
| } |
| } |
| |
| /** |
| * Invalidate all callers of [function]. |
| */ |
| void invalidateCallers(FunctionElement function) { |
| Set<Element> methodCallers = callers[function]; |
| if (methodCallers != null) { |
| methodCallers.forEach(invalidate); |
| } |
| } |
| |
| /** |
| * Invalidate all reader of [field]. |
| */ |
| void invalidateReaders(Element field) { |
| Set<Element> readers = fieldReaders[field]; |
| if (readers != null) { |
| readers.forEach(invalidate); |
| } |
| } |
| |
| /** |
| * Add all templates of [methodOrField] to the workqueue. |
| */ |
| void invalidate(Element methodOrField) { |
| if (methodOrField.isField) { |
| workQueue.add(new InferenceWorkItem( |
| methodOrField, new ConcreteTypesEnvironment())); |
| } else { |
| Map<ConcreteTypesEnvironment, ConcreteType> templates = |
| methodToTemplates[methodOrField]; |
| if (templates != null) { |
| templates.forEach((environment, _) { |
| workQueue.add( |
| new InferenceWorkItem(methodOrField, environment)); |
| }); |
| } |
| } |
| } |
| |
| /** |
| * Returns the template associated to [function] or create an empty template |
| * for [function] return it. |
| */ |
| // TODO(polux): encapsulate this in an abstraction for templates |
| Map<ConcreteTypesEnvironment, ConcreteType> |
| getTemplatesOrEmpty(FunctionElement function) { |
| return methodToTemplates.putIfAbsent( |
| function, |
| () => new Map<ConcreteTypesEnvironment, ConcreteType>()); |
| } |
| |
| // -- methods of types.TypesInferrer (interface with the backend) -- |
| |
| /** Get the inferred concrete type of [node]. */ |
| @override |
| TypeMask getTypeOfNode(Element owner, Node node) { |
| TypeMask result = types.concreteTypeToTypeMask(inferredTypes[node]); |
| return (result == const DynamicTypeMask()) ? null : result; |
| } |
| |
| /** Get the inferred concrete type of [element]. */ |
| @override |
| TypeMask getTypeOfElement(Element element) { |
| final result = types.concreteTypeToTypeMask(typeOfElement(element)); |
| return (result == const DynamicTypeMask()) ? null : result; |
| } |
| |
| /** |
| * Get the inferred concrete return type of [element]. A null return value |
| * means "I don't know". |
| */ |
| @override |
| TypeMask getReturnTypeOfElement(Element element) { |
| assert(element is FunctionElement); |
| Map<ConcreteTypesEnvironment, ConcreteType> templates = |
| methodToTemplates[element]; |
| if (templates == null) return null; |
| ConcreteType returnType = emptyConcreteType; |
| templates.forEach((_, concreteType) { |
| returnType = returnType.union(concreteType); |
| }); |
| TypeMask result = types.concreteTypeToTypeMask(returnType); |
| return (result == const DynamicTypeMask()) ? null : result; |
| } |
| |
| /** |
| * Get the inferred concrete type of [selector]. A null return value means |
| * "I don't know". |
| */ |
| @override |
| TypeMask getTypeOfSelector(Selector selector) { |
| Map<TypeMask, TypeMask> candidates = |
| inferredSelectorTypes[selector.asUntyped]; |
| if (candidates == null) { |
| return null; |
| } |
| TypeMask result = new TypeMask.nonNullEmpty(); |
| if (selector.mask == null) { |
| candidates.forEach((TypeMask receiverType, TypeMask returnType) { |
| result = typeMaskUnion(result, returnType); |
| }); |
| } else { |
| candidates.forEach((TypeMask receiverType, TypeMask returnType) { |
| TypeMask intersection = |
| receiverType.intersection(selector.mask, compiler); |
| if (!intersection.isEmpty || intersection.isNullable) { |
| result = typeMaskUnion(result, returnType); |
| } |
| }); |
| } |
| return result == const DynamicTypeMask() ? null : result; |
| } |
| |
| @override |
| void clear() { |
| throw new UnsupportedError("clearing is not yet implemented"); |
| } |
| |
| @override |
| bool isCalledOnce(Element element) { |
| // Never called by SimpleTypeInferrer. |
| throw new UnsupportedError(""); |
| } |
| |
| @override |
| bool isFixedArrayCheckedForGrowable(Node node) { |
| // Never called by SimpleTypeInferrer. |
| throw new UnsupportedError(""); |
| } |
| |
| // --- analysis --- |
| |
| /** |
| * Returns the concrete type returned by [function] given arguments of |
| * concrete types [argumentsTypes]. If [function] is static then |
| * [receiverType] must be null, else [function] must be a member of |
| * [receiverType]. |
| */ |
| ConcreteType getSendReturnType(Selector selector, |
| FunctionElement function, |
| ClassElement receiverType, |
| ArgumentsTypes<ConcreteType> argumentsTypes) { |
| assert(function != null); |
| |
| ConcreteType result = emptyConcreteType; |
| Map<Element, ConcreteType> argumentMap = |
| associateArguments(function, argumentsTypes); |
| // if the association failed, this send will never occur or will fail |
| if (argumentMap == null) { |
| return emptyConcreteType; |
| } |
| |
| argumentMap.forEach(augmentParameterType); |
| ConcreteTypeCartesianProduct product = |
| new ConcreteTypeCartesianProduct(this, receiverType, argumentMap); |
| for (ConcreteTypesEnvironment environment in product) { |
| result = result.union( |
| getMonomorphicSendReturnType(function, environment)); |
| } |
| |
| if (selector != null && receiverType != null) { |
| // TODO(polux): generalize to any abstract class if we ever handle other |
| // abstract classes than num. |
| TypeMask receiverMask = |
| (receiverType == compiler.backend.numImplementation |
| || receiverType == compiler.backend.intImplementation) |
| ? new TypeMask.nonNullSubclass(receiverType.declaration) |
| : new TypeMask.nonNullExact(receiverType.declaration); |
| TypeMask resultMask = types.concreteTypeToTypeMask(result); |
| augmentInferredSelectorType(selector, receiverMask, resultMask); |
| } |
| |
| return result; |
| } |
| |
| /** |
| * Given a method signature and a list of concrete types, builds a map from |
| * formals to their corresponding concrete types. Returns null if the |
| * association is impossible (for instance: too many arguments). |
| */ |
| Map<Element, ConcreteType> associateArguments( |
| FunctionElement function, |
| ArgumentsTypes<ConcreteType> argumentsTypes) { |
| final Map<Element, ConcreteType> result = new Map<Element, ConcreteType>(); |
| final FunctionSignature signature = function.functionSignature; |
| |
| // guard 1: too many arguments |
| if (argumentsTypes.length > signature.parameterCount) { |
| return null; |
| } |
| // guard 2: not enough arguments |
| if (argumentsTypes.positional.length < signature.requiredParameterCount) { |
| return null; |
| } |
| // guard 3: too many positional arguments |
| if (signature.optionalParametersAreNamed && |
| argumentsTypes.positional.length > signature.requiredParameterCount) { |
| return null; |
| } |
| |
| handleLeftoverOptionalParameter(ParameterElement parameter) { |
| Expression initializer = parameter.initializer; |
| result[parameter] = (initializer == null) |
| ? nullConcreteType |
| : analyzeDefaultValue(function, initializer); |
| } |
| |
| final Iterator<ConcreteType> remainingPositionalArguments = |
| argumentsTypes.positional.iterator; |
| // we attach each positional parameter to its corresponding positional |
| // argument |
| for (Link<Element> requiredParameters = signature.requiredParameters; |
| !requiredParameters.isEmpty; |
| requiredParameters = requiredParameters.tail) { |
| final Element requiredParameter = requiredParameters.head; |
| // we know moveNext() succeeds because of guard 2 |
| remainingPositionalArguments.moveNext(); |
| result[requiredParameter] = remainingPositionalArguments.current; |
| } |
| if (signature.optionalParametersAreNamed) { |
| // we build a map out of the remaining named parameters |
| Link<Element> remainingOptionalParameters = signature.optionalParameters; |
| final Map<String, Element> leftOverNamedParameters = |
| new Map<String, Element>(); |
| for (; |
| !remainingOptionalParameters.isEmpty; |
| remainingOptionalParameters = remainingOptionalParameters.tail) { |
| final Element namedParameter = remainingOptionalParameters.head; |
| leftOverNamedParameters[namedParameter.name] = namedParameter; |
| } |
| // we attach the named arguments to their corresponding optional |
| // parameters |
| for (String source in argumentsTypes.named.keys) { |
| final ConcreteType concreteType = argumentsTypes.named[source]; |
| final Element namedParameter = leftOverNamedParameters[source]; |
| // unexisting or already used named parameter |
| if (namedParameter == null) return null; |
| result[namedParameter] = concreteType; |
| leftOverNamedParameters.remove(source); |
| } |
| leftOverNamedParameters.forEach((_, Element parameter) { |
| handleLeftoverOptionalParameter(parameter); |
| }); |
| } else { // optional parameters are positional |
| // we attach the remaining positional arguments to their corresponding |
| // optional parameters |
| Link<Element> remainingOptionalParameters = signature.optionalParameters; |
| while (remainingPositionalArguments.moveNext()) { |
| final Element optionalParameter = remainingOptionalParameters.head; |
| result[optionalParameter] = remainingPositionalArguments.current; |
| // we know tail is defined because of guard 1 |
| remainingOptionalParameters = remainingOptionalParameters.tail; |
| } |
| for (; |
| !remainingOptionalParameters.isEmpty; |
| remainingOptionalParameters = remainingOptionalParameters.tail) { |
| handleLeftoverOptionalParameter(remainingOptionalParameters.head); |
| } |
| } |
| return result; |
| } |
| |
| ConcreteType getMonomorphicSendReturnType( |
| FunctionElement function, |
| ConcreteTypesEnvironment environment) { |
| Map<ConcreteTypesEnvironment, ConcreteType> template = |
| getTemplatesOrEmpty(function); |
| ConcreteType type = template[environment]; |
| ConcreteType specialType = getSpecialCaseReturnType(function, environment); |
| if (type != null) { |
| return specialType != null ? specialType : type; |
| } else { |
| workQueue.add(new InferenceWorkItem(function, environment)); |
| return specialType != null ? specialType : emptyConcreteType; |
| } |
| } |
| |
| /** |
| * Handles external methods that cannot be cached because they depend on some |
| * 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) { |
| // Handles int + int, double + double, int - int, ... |
| // We cannot compare function to int#+, int#-, etc. because int and double |
| // don't override these methods. So for 1+2, getSpecialCaseReturnType will |
| // be invoked with function = num#+. We use environment.typeOfThis instead. |
| ClassElement cls = environment.classOfThis; |
| if (cls != null) { |
| String name = function.name; |
| if ((cls == baseTypes.intBaseType.element |
| || cls == baseTypes.doubleBaseType.element) |
| && (name == '+' || name == '-' || name == '*')) { |
| Link<Element> parameters = |
| function.functionSignature.requiredParameters; |
| ConcreteType argumentType = environment.lookupType(parameters.head); |
| if (argumentType.getUniqueType() == cls) { |
| return singletonConcreteType(new ClassBaseType(cls)); |
| } |
| } |
| } |
| |
| if (function == listIndex || function == listRemoveAt) { |
| Link<Element> parameters = function.functionSignature.requiredParameters; |
| ConcreteType indexType = environment.lookupType(parameters.head); |
| if (!indexType.baseTypes.contains(baseTypes.intBaseType)) { |
| return emptyConcreteType; |
| } |
| return listElementType; |
| } else if (function == listIndexSet || function == listInsert) { |
| Link<Element> parameters = function.functionSignature.requiredParameters; |
| ConcreteType indexType = environment.lookupType(parameters.head); |
| if (!indexType.baseTypes.contains(baseTypes.intBaseType)) { |
| return emptyConcreteType; |
| } |
| ConcreteType elementType = environment.lookupType(parameters.tail.head); |
| augmentListElementType(elementType); |
| return emptyConcreteType; |
| } else if (function == listAdd) { |
| Link<Element> parameters = function.functionSignature.requiredParameters; |
| ConcreteType elementType = environment.lookupType(parameters.head); |
| augmentListElementType(elementType); |
| return emptyConcreteType; |
| } else if (function == listRemoveLast) { |
| return listElementType; |
| } |
| return null; |
| } |
| |
| ConcreteType analyzeMethodOrClosure(Element element, |
| ConcreteTypesEnvironment environment) { |
| ConcreteType specialResult = handleSpecialMethod(element, environment); |
| if (specialResult != null) return specialResult; |
| ClosureEnvironment closureEnv = closures.getEnvironmentOrNull(element); |
| return (closureEnv == null) |
| ? analyzeMethod(element, environment) |
| : analyzeClosure(element, closureEnv, environment); |
| } |
| |
| ConcreteType analyzeMethod(Element element, |
| ConcreteTypesEnvironment environment) { |
| TypeInferrerVisitor visitor = new TypeInferrerVisitor( |
| element, |
| this, |
| singletonConcreteType(new ClassBaseType(environment.classOfThis)), |
| environment.environment); |
| visitor.run(); |
| return visitor.returnType; |
| } |
| |
| ConcreteType analyzeClosure(Element element, |
| ClosureEnvironment closureEnv, |
| ConcreteTypesEnvironment environment) { |
| assert(environment.classOfThis == null); |
| LocalsHandler locals = (closureEnv.locals != null) |
| ? new LocalsHandler.deepCopyOf(closureEnv.locals) |
| : null; |
| TypeInferrerVisitor visitor = new TypeInferrerVisitor(element, this, |
| closureEnv.thisType, environment.environment, locals); |
| visitor.run(); |
| return visitor.returnType; |
| } |
| |
| /** |
| * Analyze the initializer of a field if it has not yet been done and update |
| * [inferredFieldTypes] accordingly. Invalidate the readers of the field if |
| * needed. |
| */ |
| void ensureFieldInitialized(Element field) { |
| // This is test is needed for fitering out BoxFieldElements. |
| if (field is FieldElement && inferredFieldTypes[field] == null) { |
| analyzeFieldInitialization(field); |
| } |
| } |
| |
| /** |
| * Analyze the initializer of a field and update [inferredFieldTypes] |
| * accordingly. Invalidate the readers of the field if needed. |
| */ |
| ConcreteType analyzeFieldInitialization(VariableElement field) { |
| Visitor visitor = new TypeInferrerVisitor(field, this, null, new Map()); |
| ConcreteType type; |
| if (field.initializer != null) { |
| type = field.initializer.accept(visitor); |
| inferredFieldTypes[field] = type; |
| invalidateReaders(field); |
| } |
| return type; |
| } |
| |
| /** |
| * Analyze a default value. |
| */ |
| ConcreteType analyzeDefaultValue(Element function, Node expression) { |
| assert((function != null) && (expression != null)); |
| Visitor visitor = new TypeInferrerVisitor(function, this, null, {}); |
| return expression.accept(visitor); |
| } |
| |
| /** |
| * Hook that performs side effects on some special method calls (like |
| * [:List(length):]) and possibly returns a concrete type. |
| */ |
| ConcreteType handleSpecialMethod(FunctionElement element, |
| ConcreteTypesEnvironment environment) { |
| // We trust the return type of native elements |
| if (isNativeElement(element)) { |
| var elementType = element.type; |
| assert(elementType.isFunctionType); |
| return typeOfNativeBehavior( |
| native.NativeBehavior.ofMethod(element, compiler)); |
| } |
| // 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(nullConcreteType); |
| } |
| } |
| return null; |
| } |
| |
| /** |
| * Performs concrete type inference of the code reachable from [element]. |
| */ |
| @override |
| bool analyzeMain(Element element) { |
| initialize(); |
| workQueue.add( |
| new InferenceWorkItem(element, new ConcreteTypesEnvironment())); |
| while (!workQueue.isEmpty) { |
| currentWorkItem = workQueue.remove(); |
| if (currentWorkItem.method.isField) { |
| analyzeFieldInitialization(currentWorkItem.method); |
| } else { |
| Map<ConcreteTypesEnvironment, ConcreteType> template = |
| getTemplatesOrEmpty(currentWorkItem.method); |
| template.putIfAbsent( |
| currentWorkItem.environment, () => emptyConcreteType); |
| recordReturnType( |
| currentWorkItem.method, |
| analyzeMethodOrClosure(currentWorkItem.method, |
| currentWorkItem.environment)); |
| } |
| } |
| return true; |
| } |
| |
| /** |
| * Dumps debugging information on the standard output. |
| */ |
| void debug() { |
| print("queue:"); |
| for (InferenceWorkItem workItem in workQueue.queue) { |
| print(" $workItem"); |
| } |
| print("seen classes:"); |
| for (ClassElement cls in seenClasses) { |
| print(" ${cls.name}"); |
| } |
| print("callers:"); |
| callers.forEach((k,v) { |
| print(" $k: $v"); |
| }); |
| print("dynamic callers:"); |
| dynamicCallers.forEach((k,v) { |
| print(" $k: $v"); |
| }); |
| print("readers:"); |
| fieldReaders.forEach((k,v) { |
| print(" $k: $v"); |
| }); |
| print("readers of captured locals:"); |
| capuredLocalsReaders.forEach((k,v) { |
| print(" $k: $v"); |
| }); |
| print("inferredFieldTypes:"); |
| inferredFieldTypes.forEach((k,v) { |
| print(" $k: $v"); |
| }); |
| print("listElementType:"); |
| print(" $listElementType"); |
| print("inferredParameterTypes:"); |
| inferredParameterTypes.forEach((k,v) { |
| print(" $k: $v"); |
| }); |
| print("inferred selector types:"); |
| inferredSelectorTypes.forEach((selector, map) { |
| print(" $selector:"); |
| map.forEach((k, v) { |
| print(" $k: $v"); |
| }); |
| }); |
| print("cache:"); |
| methodToTemplates.forEach((k,v) { |
| print(" $k: $v"); |
| }); |
| print("closures:"); |
| closures.closures.forEach((k, ClosureEnvironment v) { |
| print(" $k"); |
| print(" this: ${v.thisType}"); |
| if (v.locals != null) { |
| v.locals.locals.forEachLocal((local, type) { |
| print(" $local: $type"); |
| }); |
| } |
| }); |
| print("inferred expression types:"); |
| inferredTypes.forEach((k,v) { |
| print(" $k: $v"); |
| }); |
| } |
| |
| @override |
| ConcreteType addReturnTypeFor(Element analyzedElement, |
| ConcreteType currentType, |
| ConcreteType newType) { |
| return (currentType == null) ? newType : currentType.union(newType); |
| } |
| |
| @override |
| void forEachElementMatching(Selector selector, bool f(Element element)) { |
| getMembersBySelector(selector).forEach(f); |
| } |
| |
| @override |
| void recordReturnType(Element element, ConcreteType type) { |
| assert((type != null) && (element == currentWorkItem.method)); |
| Map<ConcreteTypesEnvironment, ConcreteType> template = |
| getTemplatesOrEmpty(element); |
| if (template[currentWorkItem.environment] != type) { |
| template[currentWorkItem.environment] = type; |
| invalidateCallers(element); |
| } |
| } |
| |
| @override |
| void recordType(Element element, ConcreteType type) { |
| assert(element is FieldElement); |
| augmentFieldType(element, type); |
| } |
| |
| @override |
| void recordTypeOfFinalField(Node node, |
| Element nodeHolder, |
| Element field, |
| ConcreteType type) { |
| augmentFieldType(field, type); |
| } |
| |
| @override |
| void recordTypeOfNonFinalField(Spannable node, Element field, |
| ConcreteType type) { |
| augmentFieldType(field, type); |
| } |
| |
| @override |
| void recordCapturedLocalRead(Element local) { |
| addCapturedLocalReader(local, currentWorkItem.method); |
| } |
| |
| @override |
| void recordLocalUpdate(Element local, ConcreteType type) { |
| Set<Element> localReaders = capuredLocalsReaders[local]; |
| if (localReaders != null) { |
| localReaders.forEach(invalidate); |
| } |
| } |
| |
| /** |
| * Returns the caller of the current analyzed element, given the alleged |
| * caller provided by SimpleTypeInferrer. |
| * |
| * SimpleTypeInferrer lies about the caller when it's a closure. |
| * Unfortunately we cannot always trust currentWorkItem.method either because |
| * it is wrong for fields initializers. |
| */ |
| Element getRealCaller(Element allegedCaller) { |
| Element currentMethod = currentWorkItem.method; |
| if ((currentMethod != allegedCaller) |
| && currentMethod.isFunction |
| && closures.contains(currentMethod)) { |
| return currentMethod; |
| } else { |
| return allegedCaller; |
| } |
| } |
| |
| @override |
| ConcreteType registerCalledElement(Spannable node, |
| Selector selector, |
| Element caller, |
| Element callee, |
| ArgumentsTypes<ConcreteType> arguments, |
| SideEffects sideEffects, |
| bool inLoop) { |
| caller = getRealCaller(caller); |
| if ((selector == null) || (selector.kind == SelectorKind.CALL)) { |
| callee = callee.implementation; |
| if (selector != null && selector.name == 'JS') { |
| return null; |
| } |
| if (callee.isField) { // toplevel closure call |
| getFieldType(selector, callee); // trigger toplevel field analysis |
| addFieldReader(callee, caller); |
| ConcreteType result = emptyConcreteType; |
| for (FunctionElement function in closures.functionElements) { |
| addCaller(function, caller); |
| result = result.union( |
| getSendReturnType(selector, function, null, arguments)); |
| } |
| return result; |
| } else { // method or constructor call |
| addCaller(callee, caller); |
| ClassElement receiverClass = null; |
| if (callee.isGenerativeConstructor) { |
| receiverClass = callee.enclosingClass; |
| } else if (node is Send) { |
| Send send = node; |
| if (send.receiver != null) { |
| if (send.receiver.isSuper()) { |
| receiverClass = |
| currentWorkItem.environment.classOfThis.superclass; |
| } else { |
| receiverClass = currentWorkItem.environment.classOfThis; |
| } |
| } |
| } |
| return getSendReturnType(selector, callee, receiverClass, arguments); |
| } |
| } else if (selector.kind == SelectorKind.GETTER) { |
| if (callee.isField) { |
| addFieldReader(callee, caller); |
| return getFieldType(selector, callee); |
| } else if (callee.isGetter) { |
| Element enclosing = callee.enclosingElement.isCompilationUnit |
| ? null : callee.enclosingElement; |
| addCaller(callee, caller); |
| ArgumentsTypes noArguments = new ArgumentsTypes([], new Map()); |
| return getSendReturnType(selector, callee, enclosing, noArguments); |
| } else if (callee.isFunction) { |
| addClosure(callee, null, null); |
| return singletonConcreteType(baseTypes.functionBaseType); |
| } |
| } else if (selector.kind == SelectorKind.SETTER) { |
| ConcreteType argumentType = arguments.positional.first; |
| if (callee.isField) { |
| augmentFieldType(callee, argumentType); |
| } else if (callee.isSetter) { |
| FunctionElement setter = callee; |
| // TODO(polux): A setter always returns void so there's no need to |
| // invalidate its callers even if it is called with new arguments. |
| // However, if we start to record more than returned types, like |
| // exceptions for instance, we need to do it by uncommenting the |
| // following line. |
| // inferrer.addCaller(setter, currentMethod); |
| Element enclosing = callee.enclosingElement.isCompilationUnit |
| ? null : callee.enclosingElement; |
| return getSendReturnType(selector, setter, enclosing, |
| new ArgumentsTypes([argumentType], new Map())); |
| } |
| } else { |
| throw new ArgumentError("unexpected selector kind"); |
| } |
| return null; |
| } |
| |
| @override |
| ConcreteType registerCalledSelector(Node node, |
| Selector selector, |
| ConcreteType receiverType, |
| Element caller, |
| ArgumentsTypes<ConcreteType> arguments, |
| SideEffects sideEffects, |
| bool inLoop) { |
| caller = getRealCaller(caller); |
| switch (selector.kind) { |
| case SelectorKind.GETTER: |
| return registerDynamicGetterSend(selector, receiverType, caller); |
| case SelectorKind.SETTER: |
| return registerDynamicSetterSend( |
| selector, receiverType, caller, arguments); |
| default: |
| return registerDynamicSend(selector, receiverType, caller, arguments); |
| } |
| } |
| |
| ConcreteType registerDynamicGetterSend(Selector selector, |
| ConcreteType receiverType, |
| Element caller) { |
| caller = getRealCaller(caller); |
| ConcreteType result = emptyConcreteType; |
| |
| void augmentResult(ClassElement baseReceiverType, Element member) { |
| if (member.isField) { |
| addFieldReader(member, caller); |
| result = result.union(getFieldType(selector, member)); |
| } else if (member.isGetter) { |
| addCaller(member, caller); |
| ArgumentsTypes noArguments = new ArgumentsTypes([], new Map()); |
| result = result.union( |
| getSendReturnType(selector, member, baseReceiverType, noArguments)); |
| } else if (member.isFunction) { |
| addClosure(member, receiverType, null); |
| result = result.union( |
| singletonConcreteType(baseTypes.functionBaseType)); |
| } else { |
| throw new ArgumentError("unexpected element type"); |
| } |
| } |
| |
| if (receiverType.isUnknown()) { |
| addDynamicCaller(selector, caller); |
| Set<Element> members = getMembersBySelector(selector); |
| for (Element member in members) { |
| if (!(member.isField || member.isGetter)) continue; |
| for (ClassElement cls in |
| getReflexiveSubtypesOf(member.enclosingElement)) { |
| augmentResult(cls, member); |
| } |
| } |
| } else { |
| for (BaseType baseReceiverType in receiverType.baseTypes) { |
| if (!baseReceiverType.isNull()) { |
| ClassBaseType classBaseType = baseReceiverType; |
| ClassElement cls = classBaseType.element; |
| Element getterOrField = cls.lookupSelector(selector, compiler); |
| if (getterOrField != null) { |
| augmentResult(cls, getterOrField.implementation); |
| } |
| } |
| } |
| } |
| return result; |
| } |
| |
| ConcreteType registerDynamicSetterSend( |
| Selector selector, |
| ConcreteType receiverType, |
| Element caller, |
| ArgumentsTypes<ConcreteType> arguments) { |
| caller = getRealCaller(caller); |
| ConcreteType argumentType = arguments.positional.first; |
| |
| void augmentField(ClassElement receiverType, Element setterOrField) { |
| if (setterOrField.isField) { |
| augmentFieldType(setterOrField, argumentType); |
| } else if (setterOrField.isSetter) { |
| // A setter always returns void so there's no need to invalidate its |
| // callers even if it is called with new arguments. However, if we |
| // start to record more than returned types, like exceptions for |
| // instance, we need to do it by uncommenting the following line. |
| // inferrer.addCaller(setter, currentMethod); |
| getSendReturnType(selector, setterOrField, receiverType, |
| new ArgumentsTypes([argumentType], new Map())); |
| } else { |
| throw new ArgumentError("unexpected element type"); |
| } |
| } |
| |
| if (receiverType.isUnknown()) { |
| // Same remark as above |
| // addDynamicCaller(selector, caller); |
| for (Element member in getMembersBySelector(selector)) { |
| if (!(member.isField || member.isSetter)) continue; |
| Element cls = member.enclosingClass; |
| augmentField(cls, member); |
| } |
| } else { |
| for (BaseType baseReceiverType in receiverType.baseTypes) { |
| if (!baseReceiverType.isNull()) { |
| ClassBaseType classBaseType = baseReceiverType; |
| ClassElement cls = classBaseType.element; |
| Element setterOrField = cls.lookupSelector(selector, compiler); |
| if (setterOrField != null) { |
| augmentField(cls, setterOrField.implementation); |
| } |
| } |
| } |
| } |
| return argumentType; |
| } |
| |
| ConcreteType registerDynamicSend(Selector selector, |
| ConcreteType receiverType, |
| Element caller, |
| ArgumentsTypes<ConcreteType> arguments) { |
| caller = getRealCaller(caller); |
| ConcreteType result = emptyConcreteType; |
| if (receiverType.isUnknown()) { |
| addDynamicCaller(selector, caller); |
| Set<Element> elements = getMembersBySelector(selector); |
| for (Element element in elements) { |
| if (element.isFunction) { |
| FunctionElement method = element; |
| addCaller(method, caller); |
| for (ClassElement cls in |
| getReflexiveSubtypesOf(method.enclosingElement)) { |
| result = result.union( |
| getSendReturnType(selector, method, cls, arguments)); |
| } |
| } else { // closure call |
| assert(element.isField); |
| for (FunctionElement function in closures.functionElements) { |
| addCaller(function, caller); |
| result = result.union( |
| getSendReturnType(selector, function, null, arguments)); |
| } |
| } |
| } |
| } else { |
| for (BaseType baseReceiverType in receiverType.baseTypes) { |
| if (!baseReceiverType.isNull()) { |
| ClassBaseType classBaseReceiverType = baseReceiverType; |
| ClassElement cls = classBaseReceiverType.element; |
| Element method = cls.lookupSelector(selector, compiler); |
| if (method != null) { |
| if (method.isFunction) { |
| assert(method is FunctionElement); |
| method = method.implementation; |
| addCaller(method, caller); |
| result = result.union( |
| getSendReturnType(selector, method, cls, arguments)); |
| } else { // closure call |
| for (FunctionElement function in closures.functionElements) { |
| addCaller(function, caller); |
| result = result.union( |
| getSendReturnType(selector, function, null, arguments)); |
| } |
| } |
| } |
| } |
| } |
| } |
| return result; |
| } |
| |
| @override |
| void setDefaultTypeOfParameter(Element parameter, ConcreteType type) { |
| // We handle default parameters our own way in associateArguments |
| } |
| |
| @override |
| ConcreteType registerCalledClosure(Node node, |
| Selector selector, |
| ConcreteType closure, |
| Element caller, |
| ArgumentsTypes<ConcreteType> arguments, |
| SideEffects sideEffects, |
| bool inLoop) { |
| caller = getRealCaller(caller); |
| ConcreteType result = emptyConcreteType; |
| for (FunctionElement function in closures.functionElements) { |
| addCaller(function, caller); |
| result = result.union( |
| getSendReturnType(selector, function, null, arguments)); |
| } |
| return result; |
| } |
| |
| @override |
| ConcreteType returnTypeOfElement(Element element) { |
| // Never called by SimpleTypeInferrer. |
| throw new UnsupportedError(""); |
| } |
| |
| @override |
| ConcreteType typeOfElement(Element element) { |
| if (currentWorkItem != null) { |
| final result = currentWorkItem.environment.lookupType(element); |
| if (result != null) return result; |
| } |
| if (element.isParameter || element.isFieldParameter) { |
| return inferredParameterTypes[element]; |
| } else if (element.isField) { |
| return inferredFieldTypes[element]; |
| } |
| throw new ArgumentError("unexpected element type"); |
| } |
| |
| @override |
| void analyze(Element element, ArgumentsTypes arguments) { |
| FunctionElement function = element; |
| getSendReturnType( |
| null, function, currentWorkItem.environment.classOfThis, arguments); |
| } |
| } |
| |
| class TypeInferrerVisitor extends SimpleTypeInferrerVisitor<ConcreteType> { |
| final ConcreteType thisType; |
| ConcreteTypesInferrer get inferrer => super.inferrer; |
| |
| TypeInferrerVisitor(Element element, |
| ConcreteTypesInferrer inferrer, |
| this.thisType, |
| Map<Element, ConcreteType> environment, |
| [LocalsHandler<ConcreteType> handler]) |
| : super(element, inferrer.compiler, inferrer, handler); |
| |
| @override |
| ConcreteType visitFunctionExpression(FunctionExpression node) { |
| Element element = elements[node]; |
| // visitFunctionExpression should be only called for closures |
| assert(element != analyzedElement); |
| inferrer.addClosure( |
| element, thisType, new LocalsHandler.deepCopyOf(locals)); |
| return types.functionType; |
| } |
| |
| @override |
| ConcreteType visitLiteralString(LiteralString node) { |
| // TODO(polux): get rid of this hack once we have a natural way of inferring |
| // the unknown type. |
| if (inferrer.testMode |
| && (node.dartString.slowToString() == "__dynamic_for_test")) { |
| return inferrer.unknownConcreteType; |
| } |
| return super.visitLiteralString(node); |
| } |
| |
| /** |
| * Same as super.visitLiteralList except it doesn't cache anything. |
| */ |
| @override |
| ConcreteType visitLiteralList(LiteralList node) { |
| ConcreteType elementType; |
| int length = 0; |
| for (Node element in node.elements.nodes) { |
| ConcreteType type = visit(element); |
| elementType = elementType == null |
| ? types.allocatePhi(null, null, type) |
| : types.addPhiInput(null, elementType, type); |
| length++; |
| } |
| elementType = elementType == null |
| ? types.nonNullEmpty() |
| : types.simplifyPhi(null, null, elementType); |
| ConcreteType containerType = node.isConst |
| ? types.constListType |
| : types.growableListType; |
| return types.allocateList( |
| containerType, |
| node, |
| outermostElement, |
| elementType, |
| length); |
| } |
| |
| /** |
| * Same as super.visitGetterSend except it records the type of nodes in test |
| * mode. |
| */ |
| @override |
| ConcreteType visitGetterSend(Send node) { |
| if (inferrer.testMode) { |
| Element element = elements[node]; |
| ConcreteType type = locals.use(element); |
| if (type != null) { |
| inferrer.augmentInferredType(node, type); |
| } |
| } |
| return super.visitGetterSend(node); |
| } |
| } |