| // 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 '../dart2jslib.dart' hide Selector, TypedSelector; |
| import '../dart_types.dart'; |
| import '../elements/elements.dart'; |
| import '../native_handler.dart' as native; |
| import '../tree/tree.dart'; |
| import '../universe/universe.dart'; |
| import '../util/util.dart'; |
| |
| import 'types.dart' show TypeMask, TypesInferrer; |
| |
| class CancelTypeInferenceException { |
| final Node node; |
| final String reason; |
| |
| CancelTypeInferenceException(this.node, this.reason); |
| } |
| |
| /** |
| * 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.slowToString(); |
| } |
| 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); |
| 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; |
| 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 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); |
| |
| // 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 (newBaseTypes.contains(classBaseTypes.numBaseType) || |
| (newBaseTypes.contains(classBaseTypes.intBaseType) |
| && newBaseTypes.contains(classBaseTypes.doubleBaseType))) { |
| newBaseTypes.remove(classBaseTypes.intBaseType); |
| newBaseTypes.remove(classBaseTypes.doubleBaseType); |
| newBaseTypes.add(classBaseTypes.numBaseType); |
| } |
| |
| // widen big types to dynamic |
| return newBaseTypes.length > maxConcreteTypeSize |
| ? const UnknownConcreteType() |
| : new UnionType(maxConcreteTypeSize, classBaseTypes, 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(); |
| } |
| |
| /** |
| * The cartesian product of concrete types: an iterable of [BaseTypeTuple]s. For |
| * instance, the cartesian product of the concrete types [: {A, B} :] and |
| * [: {C, D} :] is an itearble whose iterators will yield [: (A, C) :], |
| * [: (A, D) :], [: (B, C) :] and finally [: (B, D) :]. |
| */ |
| 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(inferrer, new ClassBaseType(typeOfThis))] |
| .iterator |
| : new ConcreteTypeCartesianProductIterator(inferrer, |
| new ClassBaseType(typeOfThis), concreteTypes); |
| String toString() { |
| List<ConcreteTypesEnvironment> cartesianProduct = |
| new List<ConcreteTypesEnvironment>.from(this); |
| return cartesianProduct.toString(); |
| } |
| } |
| |
| /** |
| * An helper class for [ConcreteTypeCartesianProduct]. |
| */ |
| class ConcreteTypeCartesianProductIterator |
| implements Iterator<ConcreteTypesEnvironment> { |
| final ConcreteTypesInferrer inferrer; |
| final BaseType baseTypeOfThis; |
| 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.baseTypeOfThis, |
| 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(inferrer, result, baseTypeOfThis); |
| } |
| |
| 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 objectBaseType; |
| final ClassBaseType typeBaseType; |
| final ClassBaseType functionBaseType; |
| |
| 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), |
| objectBaseType = new ClassBaseType(compiler.objectClass), |
| typeBaseType = new ClassBaseType(compiler.backend.typeImplementation), |
| functionBaseType |
| = new ClassBaseType(compiler.backend.functionImplementation); |
| } |
| |
| /** |
| * A method-local immutable mapping from variables to their inferred |
| * [ConcreteTypes]. Each visitor owns one. |
| */ |
| class ConcreteTypesEnvironment { |
| final ConcreteTypesInferrer inferrer; |
| final Map<Element, ConcreteType> environment; |
| final BaseType typeOfThis; |
| |
| ConcreteTypesEnvironment(this.inferrer, [this.typeOfThis]) : |
| environment = new Map<Element, ConcreteType>(); |
| ConcreteTypesEnvironment.of(this.inferrer, this.environment, this.typeOfThis); |
| |
| ConcreteType lookupType(Element element) => environment[element]; |
| ConcreteType lookupTypeOfThis() { |
| return (typeOfThis == null) |
| ? null |
| : inferrer.singletonConcreteType(typeOfThis); |
| } |
| |
| ConcreteTypesEnvironment put(Element element, ConcreteType type) { |
| Map<Element, ConcreteType> newMap = |
| new Map<Element, ConcreteType>.from(environment); |
| newMap[element] = type; |
| return new ConcreteTypesEnvironment.of(inferrer, newMap, typeOfThis); |
| } |
| |
| ConcreteTypesEnvironment join(ConcreteTypesEnvironment other) { |
| if (typeOfThis != other.typeOfThis) { |
| throw "trying to join incompatible environments"; |
| } |
| Map<Element, ConcreteType> newMap = |
| new Map<Element, ConcreteType>.from(environment); |
| other.environment.forEach((element, type) { |
| ConcreteType currentType = newMap[element]; |
| if (currentType == null) { |
| newMap[element] = type; |
| } else { |
| newMap[element] = currentType.union(type); |
| } |
| }); |
| return new ConcreteTypesEnvironment.of(inferrer, newMap, typeOfThis); |
| } |
| |
| bool operator ==(ConcreteTypesEnvironment other) { |
| if (other is! ConcreteTypesEnvironment) return false; |
| if (typeOfThis != other.typeOfThis) 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 = (typeOfThis != null) ? typeOfThis.hashCode : 1; |
| environment.forEach((element, concreteType) { |
| result = 31 * (31 * result + element.hashCode) + |
| concreteType.hashCode; |
| }); |
| return result; |
| } |
| |
| /** |
| * Returns true if and only if the environment is compatible with [signature]. |
| */ |
| bool matches(FunctionSignature signature) { |
| Types types = inferrer.compiler.types; |
| bool paramMatches(ConcreteType concrete, VariableElement parameter) { |
| DartType parameterType = parameter.variables.type; |
| if (parameterType.treatAsDynamic || parameterType.isRaw) { |
| return true; |
| } |
| for (BaseType baseType in concrete.baseTypes) { |
| if (baseType.isUnknown()) return false; |
| if (baseType.isNull()) continue; |
| ClassBaseType classType = baseType; |
| if (!types.isSubtype(classType.element.rawType, |
| parameterType)) return false; |
| } |
| return true; |
| } |
| for (VariableElement param in signature.requiredParameters) { |
| ConcreteType concrete = environment[param]; |
| if (concrete == null || !paramMatches(concrete, param)) return false; |
| } |
| for (VariableElement param in signature.optionalParameters) { |
| ConcreteType concrete = environment[param]; |
| if (concrete != null && !paramMatches(concrete, param)) return false; |
| } |
| return true; |
| } |
| |
| String toString() => "{ this: $typeOfThis, env: $environment }"; |
| } |
| |
| /** |
| * A work item for the type inference queue. |
| */ |
| class InferenceWorkItem { |
| Element methodOrField; |
| ConcreteTypesEnvironment environment; |
| InferenceWorkItem(this.methodOrField, this.environment); |
| |
| toString() { |
| final elementType = methodOrField.isField() ? "field" : "method"; |
| final elementRepresentation = methodOrField.name.slowToString(); |
| return "{ $elementType = $elementRepresentation" |
| ", environment = $environment }"; |
| } |
| } |
| |
| /** |
| * 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(""); |
| } |
| |
| TypeMask simplify(Compiler compiler) { |
| 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 isForwarding { |
| throw new UnsupportedError(""); |
| } |
| |
| bool get isElement { |
| 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 containsOnlyNull(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(DartType type, Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| bool containsAll(Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| ClassElement singleClass(Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| Iterable<ClassElement> containedClasses(Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| TypeMask union(TypeMask other, Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| TypeMask intersection(TypeMask other, Compiler compiler) { |
| throw new UnsupportedError(""); |
| } |
| |
| bool willHit(Selector selector, 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(""); |
| } |
| } |
| |
| /** |
| * A task which conservatively infers a [ConcreteType] for each sub expression |
| * of the program. The entry point is [analyzeMain]. |
| */ |
| class ConcreteTypesInferrer extends TypesInferrer { |
| static final bool LOG_FAILURES = true; |
| |
| final String name = "Type inferrer"; |
| |
| final Compiler compiler; |
| |
| /** |
| * 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 representing builtin base types. Initialized in [initialize] |
| * and not in the constructor because the compiler elements are not yet |
| * populated. |
| */ |
| BaseTypes baseTypes; |
| |
| /** |
| * 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; |
| |
| /** |
| * Constant mapping between types returned by native calls and concrete types. |
| */ |
| Map<ClassElement, ConcreteType> nativeTypesToConcreteTypes; |
| |
| /** |
| * Constant mapping between types returned by native calls and the set of |
| * classes that should augment [seenClasses] when encountered. |
| */ |
| Map<ClassElement, List<ClassElement>> nativeTypesToSeenClasses; |
| |
| /** |
| * Constant list of concrete classes seen by the resolver. |
| */ |
| List<ClassElement> concreteSeenClasses; |
| |
| /** |
| * A cache from (function x argument base types) to concrete types, |
| * used to memoize [analyzeMonoSend]. Another way of seeing [cache] 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): rename and build a better abstraction. |
| final Map<FunctionElement, Map<ConcreteTypesEnvironment, ConcreteType>> cache; |
| |
| /** 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; |
| |
| /** The work queue consumed by [analyzeMain]. */ |
| final Queue<InferenceWorkItem> workQueue; |
| |
| /** |
| * [: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>> readers; |
| |
| /// The set of classes encountered so far. |
| final Set<ClassElement> seenClasses; |
| |
| /** |
| * A map from method names to callers of methods with this name on objects |
| * of unknown inferred type. |
| */ |
| final Map<SourceString, 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; |
| |
| ConcreteTypesInferrer(Compiler compiler) |
| : this.compiler = compiler, |
| cache = new Map<FunctionElement, |
| Map<ConcreteTypesEnvironment, ConcreteType>>(), |
| inferredTypes = new Map<Node, ConcreteType>(), |
| inferredFieldTypes = new Map<Element, ConcreteType>(), |
| inferredParameterTypes = new Map<VariableElement, ConcreteType>(), |
| workQueue = new Queue<InferenceWorkItem>(), |
| callers = new Map<FunctionElement, Set<Element>>(), |
| readers = new Map<Element, Set<Element>>(), |
| seenClasses = new Set<ClassElement>(), |
| dynamicCallers = new Map<SourceString, Set<FunctionElement>>(), |
| inferredSelectorTypes = new Map<Selector, Map<TypeMask, TypeMask>>() { |
| unknownConcreteType = new ConcreteType.unknown(); |
| } |
| |
| // --- utility methods --- |
| |
| /** The unknown concrete type */ |
| ConcreteType unknownConcreteType; |
| |
| /** The empty concrete type */ |
| ConcreteType emptyConcreteType; |
| |
| /** The null concrete type */ |
| ConcreteType nullConcreteType; |
| |
| /** 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 with name [methodName]. |
| */ |
| List<Element> getMembersByName(SourceString methodName) { |
| // TODO(polux): memoize? |
| var result = new List<Element>(); |
| for (ClassElement cls in seenClasses) { |
| Element elem = cls.lookupMember(methodName); |
| if (elem != null) { |
| result.add(elem.implementation); |
| } |
| } |
| return result; |
| } |
| |
| /** |
| * Sets the concrete type associated to [node] to the union of the inferred |
| * concrete type so far and [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 [type]. |
| * Precondition: [:typeOfThis != 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) { |
| ConcreteType result = inferredFieldTypes[field]; |
| if (result == null) { |
| // field is a toplevel variable, we trigger its analysis because no object |
| // creation is ever going to trigger it |
| result = analyzeFieldInitialization(field); |
| return (result == null) ? emptyConcreteType : result; |
| } |
| if (selector != null) { |
| Element enclosing = field.enclosingElement; |
| if (enclosing.isClass()) { |
| ClassElement cls = enclosing; |
| TypeMask receiverMask = new TypeMask.exact(cls.rawType); |
| TypeMask resultMask = 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 [type]. |
| */ |
| void augmentFieldType(Element field, ConcreteType type) { |
| ConcreteType oldType = inferredFieldTypes[field]; |
| ConcreteType newType = (oldType != null) |
| ? oldType.union(type) |
| : type; |
| if (oldType != newType) { |
| inferredFieldTypes[field] = newType; |
| final fieldReaders = readers[field]; |
| if (fieldReaders != null) { |
| fieldReaders.forEach(invalidate); |
| } |
| } |
| } |
| |
| /// 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 [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) return; |
| for (FunctionElement function in functions) { |
| invalidate(function); |
| } |
| }, includeSuperAndInjectedMembers: true); |
| } |
| } |
| |
| /** |
| * Add [caller] to the set of [callee]'s callers. |
| */ |
| void addCaller(FunctionElement callee, Element caller) { |
| Set<Element> current = callers[callee]; |
| if (current != null) { |
| current.add(caller); |
| } else { |
| Set<Element> newSet = new Set<Element>(); |
| newSet.add(caller); |
| callers[callee] = newSet; |
| } |
| } |
| |
| /** |
| * Add [caller] to the set of [callee]'s dynamic callers. |
| */ |
| void addDynamicCaller(SourceString callee, FunctionElement caller) { |
| Set<FunctionElement> current = dynamicCallers[callee]; |
| if (current != null) { |
| current.add(caller); |
| } else { |
| Set<FunctionElement> newSet = new Set<FunctionElement>(); |
| newSet.add(caller); |
| dynamicCallers[callee] = newSet; |
| } |
| } |
| |
| /** |
| * Add [reader] to the set of [field]'s readers. |
| */ |
| void addReader(Element field, Element reader) { |
| Set<Element> current = readers[field]; |
| if (current != null) { |
| current.add(reader); |
| } else { |
| Set<Element> newSet = new Set<Element>(); |
| newSet.add(reader); |
| readers[field] = newSet; |
| } |
| } |
| |
| /** |
| * Add callers of [function] to the workqueue. |
| */ |
| void invalidateCallers(FunctionElement function) { |
| Set<Element> methodCallers = callers[function]; |
| if (methodCallers == null) return; |
| for (Element caller in methodCallers) { |
| invalidate(caller); |
| } |
| } |
| |
| /** |
| * Add all instances of [methodOrField] to the workqueue. |
| */ |
| void invalidate(Element methodOrField) { |
| if (methodOrField.isField()) { |
| workQueue.addLast(new InferenceWorkItem( |
| methodOrField, new ConcreteTypesEnvironment(this))); |
| } else { |
| Map<ConcreteTypesEnvironment, ConcreteType> instances = |
| cache[methodOrField]; |
| if (instances != null) { |
| instances.forEach((environment, _) { |
| workQueue.addLast( |
| new InferenceWorkItem(methodOrField, environment)); |
| }); |
| } |
| } |
| } |
| |
| /** |
| * Returns the template associated to [function] in cache or create an |
| * empty template for [function] in cache and returns it. |
| */ |
| Map<ConcreteTypesEnvironment, ConcreteType> |
| getTemplatesOrEmpty(FunctionElement function) { |
| return cache.putIfAbsent( |
| function, |
| () => new Map<ConcreteTypesEnvironment, ConcreteType>()); |
| } |
| |
| // -- query -- |
| |
| /** |
| * 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.rawType); |
| } else if (element == compiler.dynamicClass) { |
| return new TypeMask.nonNullSubclass(compiler.objectClass.rawType); |
| } else { |
| return new TypeMask.nonNullExact(element.rawType); |
| } |
| } |
| } |
| |
| /** |
| * 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; |
| } |
| |
| /** |
| * Get the inferred concrete type of [node]. |
| */ |
| TypeMask getTypeOfNode(Element owner, Node node) { |
| TypeMask result = concreteTypeToTypeMask(inferredTypes[node]); |
| return result == const DynamicTypeMask() ? null : result; |
| } |
| |
| /** |
| * Get the inferred concrete type of [element]. |
| */ |
| TypeMask getTypeOfElement(Element element) { |
| TypeMask result = null; |
| if (element.isParameter()) { |
| result = concreteTypeToTypeMask(inferredParameterTypes[element]); |
| } else if (element.isField()) { |
| result = concreteTypeToTypeMask(inferredFieldTypes[element]); |
| } |
| // TODO(polux): handle field parameters |
| return result == const DynamicTypeMask() ? null : result; |
| } |
| |
| /** |
| * Get the inferred concrete return type of [element]. |
| */ |
| TypeMask getReturnTypeOfElement(Element element) { |
| if (!element.isFunction()) return null; |
| Map<ConcreteTypesEnvironment, ConcreteType> templates = cache[element]; |
| if (templates == null) return null; |
| ConcreteType returnType = emptyConcreteType; |
| templates.forEach((_, concreteType) { |
| returnType = returnType.union(concreteType); |
| }); |
| TypeMask result = concreteTypeToTypeMask(returnType); |
| return result == const DynamicTypeMask() ? null : result; |
| } |
| |
| /** |
| * Get the inferred concrete type of [selector]. A null return value means |
| * "I don't know". |
| */ |
| 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; |
| } |
| |
| // --- 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 the class |
| * of [receiverType]. |
| */ |
| ConcreteType getSendReturnType(Selector selector, |
| FunctionElement function, |
| ClassElement receiverType, |
| ArgumentsTypes argumentsTypes) { |
| 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) |
| ? new TypeMask.nonNullSubclass(receiverType.rawType) |
| : new TypeMask.nonNullExact(receiverType.rawType); |
| TypeMask resultMask = 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 argumentsTypes) { |
| final Map<Element, ConcreteType> result = new Map<Element, ConcreteType>(); |
| final FunctionSignature signature = function.computeSignature(compiler); |
| |
| // 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(Element parameter) { |
| // TODO(polux): use default value whenever available |
| // TODO(polux): add a marker to indicate whether an argument was provided |
| // in order to handle "?parameter" tests |
| result[parameter] = nullConcreteType; |
| } |
| |
| 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<SourceString, Element> leftOverNamedParameters = |
| new Map<SourceString, 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 (Identifier identifier in argumentsTypes.named.keys) { |
| final ConcreteType concreteType = argumentsTypes.named[identifier]; |
| SourceString source = identifier.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.addLast(new InferenceWorkItem(function, environment)); |
| // in case of a constructor, optimize by returning the class |
| return specialType != null ? specialType : emptyConcreteType; |
| } |
| } |
| |
| /** |
| * Computes the type of a call to the magic 'JS' function. |
| */ |
| ConcreteType getNativeCallReturnType(Send node) { |
| native.NativeBehavior nativeBehavior = |
| compiler.enqueuer.resolution.nativeEnqueuer.getNativeBehaviorOf(node); |
| assert(nativeBehavior != null); |
| List typesReturned = nativeBehavior.typesReturned; |
| if (typesReturned.isEmpty) return unknownConcreteType; |
| |
| ConcreteType result = emptyConcreteType; |
| void registerClass(ClassElement element) { |
| if (!element.isAbstract(compiler)) { |
| result = |
| result.union(singletonConcreteType(new ClassBaseType(element))); |
| augmentSeenClasses(element); |
| } |
| } |
| void registerDynamic() { |
| result = unknownConcreteType; |
| concreteSeenClasses.forEach(augmentSeenClasses); |
| } |
| |
| for (final type in typesReturned) { |
| if (type == native.SpecialType.JsObject) { |
| registerDynamic(); |
| } else if (type.treatAsDynamic) { |
| registerDynamic(); |
| } else { |
| ClassElement element = type.element; |
| ConcreteType concreteType = nativeTypesToConcreteTypes[element]; |
| if (concreteType != null) { |
| result = result.union(concreteType); |
| nativeTypesToSeenClasses[element].forEach(augmentSeenClasses); |
| } else { |
| if (compiler.enqueuer.resolution.seenClasses.contains(element)) { |
| registerClass(element); |
| } |
| Set<ClassElement> subtypes = compiler.world.subtypesOf(element); |
| if (subtypes != null) { |
| subtypes.forEach(registerClass); |
| } |
| } |
| } |
| } |
| return result; |
| } |
| |
| /// Replaces native types by their backend implementation. |
| Element normalize(Element cls) { |
| if (cls == compiler.boolClass) { |
| return compiler.backend.boolImplementation; |
| } |
| if (cls == compiler.intClass) { |
| return compiler.backend.intImplementation; |
| } |
| if (cls == compiler.doubleClass) { |
| return compiler.backend.doubleImplementation; |
| } |
| if (cls == compiler.numClass) { |
| return compiler.backend.numImplementation; |
| } |
| if (cls == compiler.stringClass) { |
| return compiler.backend.stringImplementation; |
| } |
| if (cls == compiler.listClass) { |
| return compiler.backend.listImplementation; |
| } |
| return cls; |
| } |
| |
| /** |
| * 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. |
| BaseType baseType = environment.typeOfThis; |
| if (baseType != null && baseType.isClass()) { |
| ClassBaseType classBaseType = baseType; |
| ClassElement cls = classBaseType.element; |
| SourceString name = function.name; |
| if ((cls == baseTypes.intBaseType.element |
| || cls == baseTypes.doubleBaseType.element) |
| && (name == const SourceString('+') |
| || name == const SourceString('-') |
| || name == const SourceString('*'))) { |
| 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; |
| } |
| |
| /** |
| * [element] must be either a field with an initializing expression, |
| * a generative constructor or a function. |
| */ |
| ConcreteType analyze(Selector selector, |
| Element element, |
| ConcreteTypesEnvironment environment) { |
| if (element.isGenerativeConstructor()) { |
| return analyzeConstructor(selector, element, environment); |
| } else if (element.isField()) { |
| analyzeFieldInitialization(element); |
| return emptyConcreteType; |
| } else { |
| assert(element is FunctionElement); |
| return analyzeMethod(element, environment); |
| } |
| } |
| |
| ConcreteType analyzeMethod(FunctionElement element, |
| ConcreteTypesEnvironment environment) { |
| TreeElements elements = |
| compiler.enqueuer.resolution.resolvedElements[element.declaration]; |
| assert(elements != null); |
| ConcreteType specialResult = handleSpecialMethod(element, environment); |
| if (specialResult != null) return specialResult; |
| FunctionExpression tree = element.parseNode(compiler); |
| if (tree.hasBody()) { |
| Visitor visitor = |
| new TypeInferrerVisitor(elements, element, this, environment); |
| return tree.accept(visitor); |
| } else { |
| // TODO(polux): handle num#<, num#>, etc. in order to get rid of this |
| // else branch |
| return new ConcreteType.unknown(); |
| } |
| } |
| |
| /** |
| * Analyzes the initialization of a field. Returns [:null:] if and only if |
| * [element] has no initialization expression. |
| */ |
| ConcreteType analyzeFieldInitialization(VariableElement element) { |
| TreeElements elements = |
| compiler.enqueuer.resolution.resolvedElements[element]; |
| assert(elements != null); |
| Visitor visitor = new TypeInferrerVisitor(elements, element, this, |
| new ConcreteTypesEnvironment(this)); |
| Node tree = element.parseNode(compiler); |
| ConcreteType type = initializerDo(tree, (node) => node.accept(visitor)); |
| if (type != null) { |
| augmentFieldType(element, type); |
| } |
| return type; |
| } |
| |
| ConcreteType analyzeConstructor(Selector selector, |
| FunctionElement element, |
| ConcreteTypesEnvironment environment) { |
| Set<Element> uninitializedFields = new Set<Element>(); |
| |
| // initialize fields |
| ClassElement enclosingClass = element.enclosingElement; |
| augmentSeenClasses(enclosingClass); |
| enclosingClass.forEachInstanceField((_, VariableElement field) { |
| ConcreteType type = analyzeFieldInitialization(field); |
| if (type == null) { |
| uninitializedFields.add(field); |
| } |
| }); |
| |
| // handle initializing formals |
| element.computeSignature(compiler).forEachParameter((param) { |
| if (param.kind == ElementKind.FIELD_PARAMETER) { |
| FieldParameterElement fieldParam = param; |
| augmentFieldType(fieldParam.fieldElement, |
| environment.lookupType(param)); |
| uninitializedFields.remove(fieldParam.fieldElement); |
| } |
| }); |
| |
| // analyze initializers, including a possible call to super or a redirect |
| FunctionExpression tree = compiler.parser.parse(element); |
| TreeElements elements = |
| compiler.enqueuer.resolution.resolvedElements[element.declaration]; |
| assert(elements != null); |
| Visitor visitor = |
| new TypeInferrerVisitor(elements, element, this, environment); |
| |
| bool foundSuperOrRedirect = false; |
| if (tree != null && tree.initializers != null) { |
| // we look for a possible call to super in the initializer list |
| for (final init in tree.initializers) { |
| init.accept(visitor); |
| SendSet sendSet = init.asSendSet(); |
| if (init.asSendSet() == null) { |
| foundSuperOrRedirect = true; |
| } else { |
| uninitializedFields.remove(elements[init]); |
| } |
| } |
| } |
| |
| // set uninitialized fields to null |
| for (VariableElement field in uninitializedFields) { |
| augmentFieldType(field, nullConcreteType); |
| } |
| |
| // if no call to super or redirect has been found, call the default |
| // constructor (if the current class is not Object). |
| if (!foundSuperOrRedirect) { |
| ClassElement superClass = enclosingClass.superclass; |
| if (enclosingClass != compiler.objectClass) { |
| FunctionElement target = superClass.lookupConstructor( |
| new Selector.callDefaultConstructor(enclosingClass.getLibrary())) |
| .implementation; |
| final superClassConcreteType = singletonConcreteType( |
| new ClassBaseType(enclosingClass)); |
| getSendReturnType(selector, target, enclosingClass, |
| new ArgumentsTypes(new List(), new Map())); |
| } |
| } |
| |
| if (tree != null) tree.accept(visitor); |
| return singletonConcreteType(new ClassBaseType(enclosingClass)); |
| } |
| |
| /** |
| * 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) { |
| // 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); |
| } |
| } |
| } |
| |
| /* 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); |
| ClassElement jsArrayClass = baseTypes.listBaseType.element; |
| listIndex = jsArrayClass.lookupMember(const SourceString('[]')); |
| listIndexSet = jsArrayClass.lookupMember(const SourceString('[]=')); |
| listAdd = jsArrayClass.lookupMember(const SourceString('add')); |
| listRemoveAt = jsArrayClass.lookupMember(const SourceString('removeAt')); |
| listInsert = jsArrayClass.lookupMember(const SourceString('insert')); |
| listRemoveLast = |
| jsArrayClass.lookupMember(const SourceString('removeLast')); |
| List<SourceString> typePreservingOps = const [const SourceString('+'), |
| const SourceString('-'), |
| const SourceString('*')]; |
| listConstructor = |
| compiler.listClass.lookupConstructor( |
| new Selector.callConstructor( |
| const SourceString(''), |
| compiler.listClass.getLibrary())).implementation; |
| emptyConcreteType = new ConcreteType.empty(compiler.maxConcreteTypeSize, |
| baseTypes); |
| nullConcreteType = singletonConcreteType(const NullBaseType()); |
| listElementType = emptyConcreteType; |
| concreteSeenClasses = compiler.enqueuer.resolution |
| .seenClasses |
| .where((cls) => !cls.isAbstract(compiler)) |
| .toList() |
| ..add(baseTypes.numBaseType.element); |
| nativeTypesToConcreteTypes = new Map<ClassElement, ConcreteType>() |
| ..[compiler.nullClass] = nullConcreteType |
| ..[compiler.objectClass] = unknownConcreteType |
| ..[compiler.stringClass] = |
| singletonConcreteType(baseTypes.stringBaseType) |
| ..[compiler.intClass] = singletonConcreteType(baseTypes.intBaseType) |
| ..[compiler.doubleClass] = |
| singletonConcreteType(baseTypes.doubleBaseType) |
| ..[compiler.numClass] = singletonConcreteType(baseTypes.numBaseType) |
| ..[compiler.boolClass] = singletonConcreteType(baseTypes.boolBaseType); |
| nativeTypesToSeenClasses = new Map<dynamic, List<ClassElement>>() |
| ..[compiler.nullClass] = [] |
| ..[compiler.objectClass] = concreteSeenClasses |
| ..[compiler.stringClass] = [baseTypes.stringBaseType.element] |
| ..[compiler.intClass] = [baseTypes.intBaseType.element] |
| ..[compiler.doubleClass] = [baseTypes.doubleBaseType.element] |
| ..[compiler.numClass] = [baseTypes.numBaseType.element, |
| baseTypes.intBaseType.element, |
| baseTypes.doubleBaseType.element] |
| ..[compiler.boolClass] = [baseTypes.boolBaseType.element]; |
| } |
| |
| /** |
| * Performs concrete type inference of the code reachable from [element]. |
| * Returns [:true:] if and only if analysis succeeded. |
| */ |
| bool analyzeMain(Element element) { |
| initialize(); |
| try { |
| workQueue.addLast( |
| new InferenceWorkItem(element, new ConcreteTypesEnvironment(this))); |
| while (!workQueue.isEmpty) { |
| InferenceWorkItem item = workQueue.removeFirst(); |
| if (item.methodOrField.isField()) { |
| analyze(null, item.methodOrField, item.environment); |
| } else { |
| Map<ConcreteTypesEnvironment, ConcreteType> template = |
| getTemplatesOrEmpty(item.methodOrField); |
| template.putIfAbsent(item.environment, () => emptyConcreteType); |
| ConcreteType concreteType = |
| analyze(null, item.methodOrField, item.environment); |
| if (template[item.environment] != concreteType) { |
| template[item.environment] = concreteType; |
| invalidateCallers(item.methodOrField); |
| } |
| } |
| } |
| return true; |
| } on CancelTypeInferenceException catch(e) { |
| if (LOG_FAILURES) { |
| compiler.log(e.reason); |
| } |
| return false; |
| } |
| } |
| |
| /** |
| * Dumps debugging information on the standard output. |
| */ |
| void debug() { |
| print("seen classes:"); |
| for (ClassElement cls in seenClasses) { |
| print(" ${cls.name.slowToString()}"); |
| } |
| print("callers:"); |
| callers.forEach((k,v) { |
| print(" $k: $v"); |
| }); |
| print("dynamic callers:"); |
| dynamicCallers.forEach((k,v) { |
| print(" $k: $v"); |
| }); |
| print("readers:"); |
| readers.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:"); |
| cache.forEach((k,v) { |
| print(" $k: $v"); |
| }); |
| print("inferred expression types:"); |
| inferredTypes.forEach((k,v) { |
| print(" $k: $v"); |
| }); |
| } |
| |
| /** |
| * Fail with a message and abort. |
| */ |
| void fail(node, [reason]) { |
| String message = 'cannot infer types'; |
| if (reason != null) { |
| message = '$message: $reason'; |
| } |
| throw new CancelTypeInferenceException(node, message); |
| } |
| } |
| |
| /** |
| * Represents the concrete types of the arguments of a send, indexed by |
| * position or name. |
| */ |
| class ArgumentsTypes { |
| final List<ConcreteType> positional; |
| final Map<Identifier, ConcreteType> named; |
| ArgumentsTypes(this.positional, this.named); |
| int get length => positional.length + named.length; |
| toString() => "{ positional = $positional, named = $named }"; |
| } |
| |
| /** |
| * The core logic of the type inference algorithm. |
| */ |
| class TypeInferrerVisitor extends ResolvedVisitor<ConcreteType> { |
| final ConcreteTypesInferrer inferrer; |
| /// Invariant: backend = inferrer.compiler.backend |
| final Backend backend; |
| |
| final Element currentMethodOrField; |
| ConcreteTypesEnvironment environment; |
| Node lastSeenNode; |
| |
| TypeInferrerVisitor(TreeElements elements, this.currentMethodOrField, |
| ConcreteTypesInferrer inferrer, this.environment) |
| : this.inferrer = inferrer |
| , this.backend = inferrer.compiler.backend |
| , super(elements) { |
| for (Element element in elements.otherDependencies) { |
| if (element.isClass()) { |
| inferrer.augmentSeenClasses(inferrer.normalize(element)); |
| } else { |
| FunctionElement functionElement = element; |
| List<ConcreteType> unknowns = new List.filled( |
| functionElement.computeSignature(inferrer.compiler) |
| .requiredParameterCount, |
| inferrer.unknownConcreteType); |
| inferrer.getSendReturnType( |
| null, |
| functionElement, |
| functionElement.getEnclosingClass(), |
| new ArgumentsTypes(unknowns, new Map())); |
| } |
| } |
| } |
| |
| ArgumentsTypes analyzeArguments(Link<Node> arguments) { |
| final positional = new List<ConcreteType>(); |
| final named = new Map<Identifier, ConcreteType>(); |
| for(Link<Node> iterator = arguments; |
| !iterator.isEmpty; |
| iterator = iterator.tail) { |
| Node node = iterator.head; |
| NamedArgument namedArgument = node.asNamedArgument(); |
| if (namedArgument != null) { |
| named[namedArgument.name] = analyze(namedArgument.expression); |
| } else { |
| positional.add(analyze(node)); |
| } |
| } |
| return new ArgumentsTypes(positional, named); |
| } |
| |
| /** |
| * A proxy to accept which does book keeping and error reporting. Returns null |
| * if [node] is a non-returning statement, its inferred concrete type |
| * otherwise. |
| */ |
| ConcreteType analyze(Node node) { |
| if (node == null) { |
| final String error = 'internal error: unexpected node: null'; |
| inferrer.fail(lastSeenNode, error); |
| } else { |
| lastSeenNode = node; |
| } |
| ConcreteType result = node.accept(this); |
| if (result == null) { |
| inferrer.fail(node, 'internal error: inferred type is null'); |
| } |
| inferrer.augmentInferredType(node, result); |
| return result; |
| } |
| |
| ConcreteType visitBlock(Block node) { |
| return analyze(node.statements); |
| } |
| |
| ConcreteType visitCascade(Cascade node) { |
| inferrer.fail(node, 'not yet implemented'); |
| } |
| |
| ConcreteType visitCascadeReceiver(CascadeReceiver node) { |
| inferrer.fail(node, 'not yet implemented'); |
| } |
| |
| ConcreteType visitClassNode(ClassNode node) { |
| inferrer.fail(node, 'not implemented'); |
| } |
| |
| ConcreteType visitDoWhile(DoWhile node) { |
| analyze(node.body); |
| analyze(node.condition); |
| ConcreteTypesEnvironment oldEnvironment; |
| do { |
| oldEnvironment = environment; |
| analyze(node.body); |
| analyze(node.condition); |
| environment = oldEnvironment.join(environment); |
| } while (oldEnvironment != environment); |
| return inferrer.emptyConcreteType; |
| } |
| |
| ConcreteType visitExpressionStatement(ExpressionStatement node) { |
| analyze(node.expression); |
| return inferrer.emptyConcreteType; |
| } |
| |
| ConcreteType visitFor(For node) { |
| if (node.initializer != null) { |
| analyze(node.initializer); |
| } |
| analyze(node.conditionStatement); |
| ConcreteTypesEnvironment oldEnvironment; |
| do { |
| oldEnvironment = environment; |
| analyze(node.conditionStatement); |
| analyze(node.body); |
| analyze(node.update); |
| environment = oldEnvironment.join(environment); |
| // TODO(polux): Maybe have a destructive join-method that returns a boolean |
| // value indicating whether something changed to avoid performing this |
| // comparison twice. |
| } while (oldEnvironment != environment); |
| return inferrer.emptyConcreteType; |
| } |
| |
| void analyzeClosure(FunctionExpression node) { |
| for (VariableDefinitions definitions in node.parameters) { |
| for (Node parameter in definitions.definitions) { |
| environment = environment.put(elements[parameter], |
| inferrer.unknownConcreteType); |
| } |
| } |
| analyze(node.body); |
| } |
| |
| ConcreteType visitFunctionDeclaration(FunctionDeclaration node) { |
| analyzeClosure(node.function); |
| environment = environment.put(elements[node], |
| inferrer.singletonConcreteType(inferrer.baseTypes.functionBaseType)); |
| return inferrer.emptyConcreteType; |
| } |
| |
| ConcreteType visitFunctionExpression(FunctionExpression node) { |
| // Naive handling of closures: we assume their body is always executed, |
| // and that each of their arguments has type dynamic. |
| // TODO(polux): treat closures as classes |
| if (node.name == null) { |
| analyzeClosure(node); |
| return inferrer.singletonConcreteType( |
| inferrer.baseTypes.functionBaseType); |
| } else { |
| return analyze(node.body); |
| } |
| } |
| |
| ConcreteType visitIdentifier(Identifier node) { |
| if (node.isThis()) { |
| ConcreteType result = environment.lookupTypeOfThis(); |
| if (result == null) { |
| inferrer.fail(node, '"this" has no type'); |
| } |
| return result; |
| } |
| Element element = elements[node]; |
| assert(element != null); |
| ConcreteType result = environment.lookupType(element); |
| if (result != null) { |
| assert(element.isParameter()); |
| return result; |
| } else { |
| environment = environment.put(element, inferrer.nullConcreteType); |
| return inferrer.nullConcreteType; |
| } |
| } |
| |
| ConcreteType visitIf(If node) { |
| analyze(node.condition); |
| ConcreteType thenType = analyze(node.thenPart); |
| ConcreteTypesEnvironment snapshot = environment; |
| ConcreteType elseType = node.hasElsePart ? analyze(node.elsePart) |
| : inferrer.emptyConcreteType; |
| environment = environment.join(snapshot); |
| return thenType.union(elseType); |
| } |
| |
| ConcreteType visitLoop(Loop node) { |
| inferrer.fail(node, 'not yet implemented'); |
| } |
| |
| ConcreteType analyzeSetElement(Selector selector, |
| Element receiver, ConcreteType argumentType) { |
| environment = environment.put(receiver, argumentType); |
| if (receiver.isField()) { |
| inferrer.augmentFieldType(receiver, argumentType); |
| } else if (receiver.isSetter()){ |
| FunctionElement setter = receiver; |
| // 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); |
| inferrer.getSendReturnType(selector, setter, receiver.enclosingElement, |
| new ArgumentsTypes([argumentType], new Map())); |
| } |
| return argumentType; |
| } |
| |
| ConcreteType analyzeSetNode(Selector selector, |
| Node receiver, ConcreteType argumentType, |
| SourceString name) { |
| ConcreteType receiverType = analyze(receiver); |
| |
| void augmentField(ClassElement receiverType, Element member) { |
| if (member.isField()) { |
| inferrer.augmentFieldType(member, argumentType); |
| } else if (member.isAbstractField()){ |
| AbstractFieldElement abstractField = member; |
| FunctionElement setter = abstractField.setter; |
| // 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); |
| inferrer.getSendReturnType(selector, setter, receiverType, |
| new ArgumentsTypes([argumentType], new Map())); |
| } |
| // since this is a sendSet we ignore non-fields |
| } |
| |
| if (receiverType.isUnknown()) { |
| inferrer.addDynamicCaller(name, currentMethodOrField); |
| for (Element member in inferrer.getMembersByName(name)) { |
| if (!(member.isField() || member.isAbstractField())) continue; |
| Element cls = member.getEnclosingClass(); |
| augmentField(cls, member); |
| } |
| } else { |
| for (BaseType baseReceiverType in receiverType.baseTypes) { |
| if (!baseReceiverType.isClass()) continue; |
| ClassBaseType baseReceiverClassType = baseReceiverType; |
| Element member = baseReceiverClassType.element.lookupMember(name); |
| if (member != null) { |
| augmentField(baseReceiverClassType.element, member); |
| } |
| } |
| } |
| return argumentType; |
| } |
| |
| SourceString canonicalizeCompoundOperator(SourceString op) { |
| // TODO(ahe): This class should work on elements or selectors, not |
| // names. Otherwise, it is repeating work the resolver has |
| // already done (or should have done). In this case, the problem |
| // is that the resolver is not recording the selectors it is |
| // registering in registerBinaryOperator in |
| // ResolverVisitor.visitSendSet. |
| String stringValue = op.stringValue; |
| if (stringValue == '++') return const SourceString(r'+'); |
| else if (stringValue == '--') return const SourceString(r'-'); |
| else return Elements.mapToUserOperatorOrNull(op); |
| } |
| |
| ConcreteType visitSendSet(SendSet node) { |
| // Operator []= has a different behaviour than other send sets: it is |
| // actually a send whose return type is that of its second argument. |
| if (node.selector.asIdentifier().source.stringValue == '[]') { |
| ConcreteType receiverType = analyze(node.receiver); |
| ArgumentsTypes argumentsTypes = analyzeArguments(node.arguments); |
| analyzeDynamicSend(elements.getSelector(node), receiverType, |
| const SourceString('[]='), argumentsTypes); |
| return argumentsTypes.positional[1]; |
| } |
| |
| // All other operators have a single argument (++ and -- have an implicit |
| // argument: 1). We will store its type in argumentType. |
| ConcreteType argumentType; |
| SourceString operatorName = node.assignmentOperator.source; |
| SourceString compoundOperatorName = |
| canonicalizeCompoundOperator(node.assignmentOperator.source); |
| // ++, --, +=, -=, ... |
| if (compoundOperatorName != null) { |
| ConcreteType receiverType = visitGetterSendForSelector(node, |
| elements.getGetterSelectorInComplexSendSet(node)); |
| // argumentsTypes is either computed from the actual arguments or [{int}] |
| // in case of ++ or --. |
| ArgumentsTypes argumentsTypes; |
| if (operatorName.stringValue == '++' |
| || operatorName.stringValue == '--') { |
| List<ConcreteType> positionalArguments = <ConcreteType>[ |
| inferrer.singletonConcreteType(inferrer.baseTypes.intBaseType)]; |
| argumentsTypes = new ArgumentsTypes(positionalArguments, new Map()); |
| } else { |
| argumentsTypes = analyzeArguments(node.arguments); |
| } |
| argumentType = analyzeDynamicSend( |
| elements.getOperatorSelectorInComplexSendSet(node), |
| receiverType, |
| compoundOperatorName, |
| argumentsTypes); |
| // The simple assignment case: receiver = argument. |
| } else { |
| argumentType = analyze(node.argumentsNode); |
| } |
| |
| Element element = elements[node]; |
| if (element != null) { |
| return analyzeSetElement(elements.getSelector(node), |
| element, argumentType); |
| } else { |
| return analyzeSetNode(elements.getSelector(node), |
| node.receiver, argumentType, |
| node.selector.asIdentifier().source); |
| } |
| } |
| |
| ConcreteType visitLiteralInt(LiteralInt node) { |
| inferrer.augmentSeenClasses(backend.intImplementation); |
| inferrer.augmentSeenClasses(backend.numImplementation); |
| return inferrer.singletonConcreteType(inferrer.baseTypes.intBaseType); |
| } |
| |
| ConcreteType visitLiteralDouble(LiteralDouble node) { |
| inferrer.augmentSeenClasses(backend.doubleImplementation); |
| inferrer.augmentSeenClasses(backend.numImplementation); |
| return inferrer.singletonConcreteType(inferrer.baseTypes.doubleBaseType); |
| } |
| |
| ConcreteType visitLiteralBool(LiteralBool node) { |
| inferrer.augmentSeenClasses(backend.boolImplementation); |
| return inferrer.singletonConcreteType(inferrer.baseTypes.boolBaseType); |
| } |
| |
| 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; |
| } |
| inferrer.augmentSeenClasses(inferrer.compiler.stringClass); |
| return inferrer.singletonConcreteType(inferrer.baseTypes.stringBaseType); |
| } |
| |
| ConcreteType visitStringJuxtaposition(StringJuxtaposition node) { |
| analyze(node.first); |
| analyze(node.second); |
| return inferrer.singletonConcreteType(inferrer.baseTypes.stringBaseType); |
| } |
| |
| ConcreteType visitLiteralNull(LiteralNull node) { |
| return inferrer.nullConcreteType; |
| } |
| |
| ConcreteType visitNewExpression(NewExpression node) { |
| Element constructor = elements[node.send].implementation; |
| inferrer.addCaller(constructor, currentMethodOrField); |
| ClassElement cls = constructor.enclosingElement; |
| return inferrer.getSendReturnType(null, constructor, cls, |
| analyzeArguments(node.send.arguments)); |
| } |
| |
| ConcreteType visitLiteralList(LiteralList node) { |
| ConcreteType elementsType = inferrer.emptyConcreteType; |
| // We compute the union of the types of the list literal's elements. |
| for (Link<Node> link = node.elements.nodes; |
| !link.isEmpty; |
| link = link.tail) { |
| elementsType = elementsType.union(analyze(link.head)); |
| } |
| inferrer.augmentListElementType(elementsType); |
| inferrer.augmentSeenClasses(backend.listImplementation); |
| return inferrer.singletonConcreteType( |
| inferrer.baseTypes.growableListBaseType); |
| } |
| |
| ConcreteType visitNodeList(NodeList node) { |
| ConcreteType type = inferrer.emptyConcreteType; |
| // The concrete type of a sequence of statements is the union of the |
| // statement's types. |
| for (Link<Node> link = node.nodes; !link.isEmpty; link = link.tail) { |
| type = type.union(analyze(link.head)); |
| } |
| return type; |
| } |
| |
| ConcreteType visitOperator(Operator node) { |
| inferrer.fail(node, 'not yet implemented'); |
| } |
| |
| ConcreteType visitReturn(Return node) { |
| final expression = node.expression; |
| return (expression == null) |
| ? inferrer.nullConcreteType |
| : analyze(expression); |
| } |
| |
| ConcreteType visitThrow(Throw node) { |
| if (node.expression != null) analyze(node.expression); |
| return inferrer.emptyConcreteType; |
| } |
| |
| ConcreteType visitTypeAnnotation(TypeAnnotation node) { |
| inferrer.fail(node, 'not yet implemented'); |
| } |
| |
| ConcreteType visitTypeVariable(TypeVariable node) { |
| inferrer.fail(node, 'not yet implemented'); |
| } |
| |
| ConcreteType visitVariableDefinitions(VariableDefinitions node) { |
| for (Link<Node> link = node.definitions.nodes; !link.isEmpty; |
| link = link.tail) { |
| analyze(link.head); |
| } |
| return inferrer.emptyConcreteType; |
| } |
| |
| ConcreteType visitWhile(While node) { |
| analyze(node.condition); |
| ConcreteTypesEnvironment oldEnvironment; |
| do { |
| oldEnvironment = environment; |
| analyze(node.condition); |
| analyze(node.body); |
| environment = oldEnvironment.join(environment); |
| } while (oldEnvironment != environment); |
| return inferrer.emptyConcreteType; |
| } |
| |
| ConcreteType visitParenthesizedExpression(ParenthesizedExpression node) { |
| return analyze(node.expression); |
| } |
| |
| ConcreteType visitConditional(Conditional node) { |
| analyze(node.condition); |
| ConcreteType thenType = analyze(node.thenExpression); |
| ConcreteType elseType = analyze(node.elseExpression); |
| return thenType.union(elseType); |
| } |
| |
| ConcreteType visitModifiers(Modifiers node) { |
| inferrer.fail(node, 'not yet implemented'); |
| } |
| |
| ConcreteType visitStringInterpolation(StringInterpolation node) { |
| node.visitChildren(this); |
| inferrer.augmentSeenClasses(inferrer.compiler.stringClass); |
| return inferrer.singletonConcreteType(inferrer.baseTypes.stringBaseType); |
| } |
| |
| ConcreteType visitStringInterpolationPart(StringInterpolationPart node) { |
| node.visitChildren(this); |
| inferrer.augmentSeenClasses(inferrer.compiler.stringClass); |
| return inferrer.singletonConcreteType(inferrer.baseTypes.stringBaseType); |
| } |
| |
| ConcreteType visitEmptyStatement(EmptyStatement node) { |
| return inferrer.emptyConcreteType; |
| } |
| |
| ConcreteType visitBreakStatement(BreakStatement node) { |
| return inferrer.emptyConcreteType; |
| } |
| |
| ConcreteType visitContinueStatement(ContinueStatement node) { |
| // TODO(polux): we can be more precise |
| return inferrer.emptyConcreteType; |
| } |
| |
| ConcreteType visitForIn(ForIn node) { |
| Element declaredIdentifier = elements[node.declaredIdentifier]; |
| assert(declaredIdentifier != null); |
| ConcreteType iterableType = analyze(node.expression); |
| |
| // var n0 = e.iterator |
| ConcreteType iteratorType = analyzeDynamicGetterSend( |
| elements.getIteratorSelector(node), |
| iterableType); |
| ConcreteType result = inferrer.emptyConcreteType; |
| ConcreteTypesEnvironment oldEnvironment; |
| do { |
| oldEnvironment = environment; |
| // n0.moveNext(); |
| analyzeDynamicSend( |
| elements.getMoveNextSelector(node), |
| iteratorType, |
| const SourceString("moveNext"), |
| new ArgumentsTypes(const [], const {})); |
| // id = n0.current |
| ConcreteType currentType = analyzeDynamicGetterSend( |
| elements.getCurrentSelector(node), |
| iteratorType); |
| environment = environment.put(declaredIdentifier, currentType); |
| result = result.union(analyze(node.body)); |
| environment = oldEnvironment.join(environment); |
| } while (oldEnvironment != environment); |
| return result; |
| } |
| |
| ConcreteType visitLabel(Label node) { |
| inferrer.fail(node, 'not yet implemented'); |
| } |
| |
| ConcreteType visitLabeledStatement(LabeledStatement node) { |
| return analyze(node.statement); |
| } |
| |
| ConcreteType visitLiteralMap(LiteralMap node) { |
| visitNodeList(node.entries); |
| inferrer.augmentSeenClasses(inferrer.compiler.mapClass); |
| return inferrer.singletonConcreteType(inferrer.baseTypes.mapBaseType); |
| } |
| |
| ConcreteType visitLiteralMapEntry(LiteralMapEntry node) { |
| // We don't need to visit the key, it's always a string. |
| return analyze(node.value); |
| } |
| |
| ConcreteType visitNamedArgument(NamedArgument node) { |
| inferrer.fail(node, 'not yet implemented'); |
| } |
| |
| ConcreteType visitSwitchStatement(SwitchStatement node) { |
| inferrer.fail(node, 'not yet implemented'); |
| } |
| |
| ConcreteType visitSwitchCase(SwitchCase node) { |
| inferrer.fail(node, 'not yet implemented'); |
| } |
| |
| ConcreteType visitCaseMatch(CaseMatch node) { |
| inferrer.fail(node, 'not yet implemented'); |
| } |
| |
| ConcreteType visitTryStatement(TryStatement node) { |
| inferrer.fail(node, 'not yet implemented'); |
| } |
| |
| ConcreteType visitCatchBlock(CatchBlock node) { |
| inferrer.fail(node, 'not yet implemented'); |
| } |
| |
| ConcreteType visitTypedef(Typedef node) { |
| inferrer.fail(node, 'not implemented'); |
| } |
| |
| ConcreteType visitSuperSend(Send node) { |
| inferrer.fail(node, 'not implemented'); |
| } |
| |
| ConcreteType visitOperatorSend(Send node) { |
| SourceString name = |
| canonicalizeMethodName(node.selector.asIdentifier().source); |
| if (name == const SourceString('is')) { |
| return inferrer.singletonConcreteType(inferrer.baseTypes.boolBaseType); |
| } |
| return visitDynamicSend(node); |
| } |
| |
| ConcreteType analyzeFieldRead(Selector selector, Element field) { |
| inferrer.addReader(field, currentMethodOrField); |
| return inferrer.getFieldType(selector, field); |
| } |
| |
| ConcreteType analyzeGetterSend(Selector selector, |
| ClassElement receiverType, |
| FunctionElement getter) { |
| inferrer.addCaller(getter, currentMethodOrField); |
| return inferrer.getSendReturnType(selector, getter, receiverType, |
| new ArgumentsTypes([], new Map())); |
| } |
| |
| ConcreteType visitGetterSend(Send node) { |
| Selector selector = elements.getSelector(node); |
| return visitGetterSendForSelector(node, selector); |
| } |
| |
| ConcreteType analyzeDynamicGetterSend(Selector selector, |
| ConcreteType receiverType) { |
| ConcreteType result = inferrer.emptyConcreteType; |
| void augmentResult(ClassElement baseReceiverType, Element member) { |
| if (member.isField()) { |
| result = result.union(analyzeFieldRead(selector, member)); |
| } else if (member.isAbstractField()){ |
| // call to a getter |
| AbstractFieldElement abstractField = member; |
| ConcreteType getterReturnType = analyzeGetterSend( |
| selector, baseReceiverType, abstractField.getter); |
| result = result.union(getterReturnType); |
| } |
| // since this is a get we ignore non-fields |
| } |
| |
| if (receiverType.isUnknown()) { |
| inferrer.addDynamicCaller(selector.name, currentMethodOrField); |
| List<Element> members = inferrer.getMembersByName(selector.name); |
| for (Element member in members) { |
| Element cls = member.getEnclosingClass(); |
| augmentResult(cls, member); |
| } |
| } else { |
| for (BaseType baseReceiverType in receiverType.baseTypes) { |
| if (!baseReceiverType.isNull()) { |
| ClassBaseType classBaseType = baseReceiverType; |
| ClassElement cls = classBaseType.element; |
| Element getterOrField = cls.lookupMember(selector.name); |
| if (getterOrField != null) { |
| augmentResult(cls, getterOrField.implementation); |
| } |
| } |
| } |
| } |
| return result; |
| } |
| |
| ConcreteType visitGetterSendForSelector(Send node, Selector selector) { |
| Element element = elements[node]; |
| if (element != null) { |
| // node is a local variable or a field of this |
| ConcreteType result = environment.lookupType(element); |
| if (result != null) { |
| // node is a local variable |
| return result; |
| } else { |
| // node is a field or a getter of this |
| if (element.isField()) { |
| return analyzeFieldRead(selector, element); |
| } else { |
| assert(element.isGetter()); |
| ClassElement receiverType = element.enclosingElement; |
| return analyzeGetterSend(selector, receiverType, element); |
| } |
| } |
| } else { |
| // node is a field/getter which doesn't belong to the current class or |
| // the field/getter of a mixed-in class |
| ConcreteType receiverType = node.receiver != null |
| ? analyze(node.receiver) |
| : environment.lookupTypeOfThis(); |
| return analyzeDynamicGetterSend(selector, receiverType); |
| } |
| } |
| |
| ConcreteType visitClosureSend(Send node) { |
| return inferrer.unknownConcreteType; |
| } |
| |
| ConcreteType analyzeDynamicSend(Selector selector, |
| ConcreteType receiverType, |
| SourceString canonicalizedMethodName, |
| ArgumentsTypes argumentsTypes) { |
| ConcreteType result = inferrer.emptyConcreteType; |
| |
| if (receiverType.isUnknown()) { |
| inferrer.addDynamicCaller(canonicalizedMethodName, currentMethodOrField); |
| List<Element> methods = |
| inferrer.getMembersByName(canonicalizedMethodName); |
| for (Element element in methods) { |
| // TODO(polux): when we handle closures, we must handle sends to fields |
| // that are closures. |
| if (!element.isFunction()) continue; |
| FunctionElement method = element; |
| inferrer.addCaller(method, currentMethodOrField); |
| Element cls = method.enclosingElement; |
| result = result.union( |
| inferrer.getSendReturnType(selector, method, cls, argumentsTypes)); |
| } |
| |
| } else { |
| for (BaseType baseReceiverType in receiverType.baseTypes) { |
| if (!baseReceiverType.isNull()) { |
| ClassBaseType classBaseReceiverType = baseReceiverType; |
| ClassElement cls = classBaseReceiverType.element; |
| FunctionElement method = cls.lookupMember(canonicalizedMethodName); |
| if (method != null) { |
| method = method.implementation; |
| inferrer.addCaller(method, currentMethodOrField); |
| result = result.union( |
| inferrer.getSendReturnType(selector, method, cls, |
| argumentsTypes)); |
| } |
| } |
| } |
| } |
| return result; |
| } |
| |
| SourceString canonicalizeMethodName(SourceString name) { |
| // TODO(polux): handle unary- |
| SourceString operatorName = |
| Elements.constructOperatorNameOrNull(name, false); |
| if (operatorName != null) return operatorName; |
| return name; |
| } |
| |
| ConcreteType visitDynamicSend(Send node) { |
| ConcreteType receiverType = (node.receiver != null) |
| ? analyze(node.receiver) |
| : environment.lookupTypeOfThis(); |
| SourceString name = |
| canonicalizeMethodName(node.selector.asIdentifier().source); |
| if (name.stringValue == '!=') { |
| ArgumentsTypes argumentsTypes = analyzeArguments(node.arguments); |
| ConcreteType returnType = analyzeDynamicSend(elements.getSelector(node), |
| receiverType, |
| const SourceString('=='), |
| argumentsTypes); |
| return returnType.isEmpty() |
| ? returnType |
| : inferrer.singletonConcreteType(inferrer.baseTypes.boolBaseType); |
| } else if (name.stringValue == '&&' || name.stringValue == '||'){ |
| ConcreteTypesEnvironment oldEnvironment = environment; |
| analyze(node.arguments.head); |
| environment = oldEnvironment.join(environment); |
| return inferrer.singletonConcreteType(inferrer.baseTypes.boolBaseType); |
| } else { |
| ArgumentsTypes argumentsTypes = analyzeArguments(node.arguments); |
| return analyzeDynamicSend(elements.getSelector(node), |
| receiverType, name, argumentsTypes); |
| } |
| } |
| |
| ConcreteType visitForeignSend(Send node) { |
| return inferrer.unknownConcreteType; |
| } |
| |
| ConcreteType visitStaticSend(Send node) { |
| if (elements.getSelector(node).name == const SourceString('JS')) { |
| return inferrer.getNativeCallReturnType(node); |
| } |
| Element element = elements[node].implementation; |
| inferrer.addCaller(element, currentMethodOrField); |
| return inferrer.getSendReturnType(elements.getSelector(node), |
| element, null, |
| analyzeArguments(node.arguments)); |
| } |
| |
| void internalError(String reason, {Node node}) { |
| inferrer.fail(node, reason); |
| } |
| |
| ConcreteType visitTypeReferenceSend(Send) { |
| return inferrer.singletonConcreteType(inferrer.baseTypes.typeBaseType); |
| } |
| } |