| // Copyright (c) 2013, 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. |
| |
| part of type_graph_inferrer; |
| |
| /** |
| * Common class for all nodes in the graph. The current nodes are: |
| * |
| * - Concrete types |
| * - Elements |
| * - Call sites |
| * - Narrowing instructions |
| * - Phi instructions |
| * - Containers (for lists) |
| * - Type of the element in a container |
| * |
| * A node has a set of assignments and users. Assignments are used to |
| * compute the type of the node ([TypeInformation.refine]). Users are |
| * added to the inferrer's work queue when the type of the node |
| * changes. |
| */ |
| abstract class TypeInformation { |
| var /* List|Set */ users; |
| var /* List|ParameterAssignments */ assignments; |
| |
| /// The type the inferrer has found for this [TypeInformation]. |
| /// Initially empty. |
| TypeMask type = const TypeMask.nonNullEmpty(); |
| |
| /// We abandon inference in certain cases (complex cyclic flow, native |
| /// behaviours, etc.). In some case, we might resume inference in the |
| /// closure tracer, which is handled by checking whether [assignments] has |
| /// been set to [STOP_TRACKING_ASSIGNMENTS_MARKER]. |
| bool abandonInferencing = false; |
| bool get mightResume => |
| !identical(assignments, STOP_TRACKING_ASSIGNMENTS_MARKER); |
| |
| /// Number of times this [TypeInformation] has changed type. |
| int refineCount = 0; |
| |
| /// Whether this [TypeInformation] is currently in the inferrer's |
| /// work queue. |
| bool inQueue = false; |
| |
| /// Whether this [TypeInformation] has a stable [type] that will not |
| /// change. |
| bool isStable = false; |
| |
| // TypeInformations are unique. |
| static int staticHashCode = 0; |
| final int hashCode = staticHashCode++; |
| |
| bool get isConcrete => false; |
| |
| TypeInformation([users, assignments]) |
| : users = (users == null) ? new Setlet<TypeInformation>() : users, |
| assignments = (assignments == null) ? <TypeInformation>[] : assignments; |
| |
| |
| void addUser(TypeInformation user) { |
| assert(!user.isConcrete); |
| users.add(user); |
| } |
| |
| void removeUser(TypeInformation user) { |
| assert(!user.isConcrete); |
| users.remove(user); |
| } |
| |
| // The below is not a compile time constant to make it differentiable |
| // from other empty lists of [TypeInformation]. |
| static final STOP_TRACKING_ASSIGNMENTS_MARKER = new List<TypeInformation>(0); |
| |
| bool areAssignmentsTracked() { |
| return assignments != STOP_TRACKING_ASSIGNMENTS_MARKER; |
| } |
| |
| void addAssignment(TypeInformation assignment) { |
| // Cheap one-level cycle detection. |
| if (assignment == this) return; |
| if (areAssignmentsTracked()) { |
| assignments.add(assignment); |
| } |
| // Even if we abandon inferencing on this [TypeInformation] we |
| // need to collect the users, so that phases that track where |
| // elements flow in still work. |
| assignment.addUser(this); |
| } |
| |
| void removeAssignment(TypeInformation assignment) { |
| if (!abandonInferencing || mightResume) { |
| assignments.remove(assignment); |
| } |
| // We can have multiple assignments of the same [TypeInformation]. |
| if (!assignments.contains(assignment)) { |
| assignment.removeUser(this); |
| } |
| } |
| |
| TypeMask refine(TypeGraphInferrerEngine inferrer) { |
| return type; |
| } |
| |
| void giveUp(TypeGraphInferrerEngine inferrer, {bool clearAssignments: true}) { |
| abandonInferencing = true; |
| type = inferrer.types.dynamicType.type; |
| // Do not remove [this] as a user of nodes in [assignments], |
| // because our tracing analysis could be interested in tracing |
| // this node. |
| if (clearAssignments) assignments = STOP_TRACKING_ASSIGNMENTS_MARKER; |
| // Do not remove users because our tracing analysis could be |
| // interested in tracing the users of this node. |
| } |
| |
| void clear() { |
| assignments = STOP_TRACKING_ASSIGNMENTS_MARKER; |
| users = const <TypeInformation>[]; |
| } |
| |
| /// Reset the analysis of this node by making its type empty. |
| void reset(TypeGraphInferrerEngine inferrer) { |
| if (abandonInferencing) return; |
| type = const TypeMask.nonNullEmpty(); |
| refineCount = 0; |
| } |
| |
| accept(TypeInformationVisitor visitor); |
| |
| /// The [Element] where this [TypeInformation] was created. May be |
| /// for some [TypeInformation] nodes, where we do not need to store |
| /// the information. |
| Element get owner => null; |
| |
| /// Returns whether the type cannot change after it has been |
| /// inferred. |
| bool hasStableType(TypeGraphInferrerEngine inferrer) { |
| return !mightResume && assignments.every((e) => e.isStable); |
| } |
| |
| void removeAndClearReferences(TypeGraphInferrerEngine inferrer) { |
| assignments.forEach((info) { info.removeUser(this); }); |
| } |
| |
| void stabilize(TypeGraphInferrerEngine inferrer) { |
| removeAndClearReferences(inferrer); |
| // Do not remove users because the tracing analysis could be interested |
| // in tracing the users of this node. |
| assignments = STOP_TRACKING_ASSIGNMENTS_MARKER; |
| abandonInferencing = true; |
| isStable = true; |
| } |
| } |
| |
| abstract class ApplyableTypeInformation extends TypeInformation { |
| bool mightBePassedToFunctionApply = false; |
| |
| ApplyableTypeInformation([users, assignments]) : super(users, assignments); |
| } |
| |
| /** |
| * Parameters of instance functions behave differently than other |
| * elements because the inferrer may remove assignments. This happens |
| * when the receiver of a dynamic call site can be refined |
| * to a type where we know more about which instance method is being |
| * called. |
| */ |
| class ParameterAssignments extends IterableBase<TypeInformation> { |
| final Map<TypeInformation, int> assignments = |
| new Map<TypeInformation, int>(); |
| |
| void remove(TypeInformation info) { |
| int existing = assignments[info]; |
| if (existing == null) return; |
| if (existing == 1) { |
| assignments.remove(info); |
| } else { |
| assignments[info] = existing - 1; |
| } |
| } |
| |
| void add(TypeInformation info) { |
| int existing = assignments[info]; |
| if (existing == null) { |
| assignments[info] = 1; |
| } else { |
| assignments[info] = existing + 1; |
| } |
| } |
| |
| Iterator<TypeInformation> get iterator => assignments.keys.iterator; |
| Iterable<TypeInformation> where(Function f) => assignments.keys.where(f); |
| |
| bool contains(TypeInformation info) => assignments.containsKey(info); |
| |
| String toString() => assignments.keys.toList().toString(); |
| } |
| |
| /** |
| * A node representing a resolved element of the program. The kind of |
| * elements that need an [ElementTypeInformation] are: |
| * |
| * - Functions (including getters and setters) |
| * - Constructors (factory or generative) |
| * - Fields |
| * - Parameters |
| * - Local variables mutated in closures |
| * |
| * The [ElementTypeInformation] of a function and a constructor is its |
| * return type. |
| * |
| * Note that a few elements of these kinds must be treated specially, |
| * and they are dealt in [ElementTypeInformation.handleSpecialCases]: |
| * |
| * - Parameters of closures, [noSuchMethod] and [call] instance |
| * methods: we currently do not infer types for those. |
| * |
| * - Fields and parameters being assigned by synthesized calls done by |
| * the backend: we do not know what types the backend will use. |
| * |
| * - Native functions and fields: because native methods contain no Dart |
| * code, and native fields do not have Dart assignments, we just |
| * trust their type annotation. |
| * |
| */ |
| class ElementTypeInformation extends ApplyableTypeInformation { |
| final Element element; |
| |
| /// Marker to disable inference for closures in [handleSpecialCases]. |
| bool disableInferenceForClosures = true; |
| |
| /** |
| * If [element] is a function, [closurizedCount] is the number of |
| * times it is closurized. The value gets updated while infering. |
| */ |
| int closurizedCount = 0; |
| |
| /** |
| * This map contains the callers of [element]. It stores all unique call sites |
| * to enable counting the global number of call sites of [element]. |
| * |
| * A call site is either an AST [ast.Node], an [ir.Node] or in the case of |
| * synthesized calls, an [Element] (see uses of [synthesizeForwardingCall] |
| * in [SimpleTypeInferrerVisitor]). |
| */ |
| final Map<Element, Setlet<Spannable>> _callers = new Map<Element, Setlet>(); |
| |
| ElementTypeInformation.internal(this.element, assignments) |
| : super(null, assignments); |
| |
| factory ElementTypeInformation(Element element) { |
| var assignments = null; |
| if (element.enclosingElement.isInstanceMember && |
| (element.isParameter || element.isFieldParameter)) { |
| assignments = new ParameterAssignments(); |
| } |
| return new ElementTypeInformation.internal(element, assignments); |
| } |
| |
| void addCall(Element caller, Spannable node) { |
| assert(node is ast.Node || node is ir.Node || node is Element); |
| _callers.putIfAbsent(caller, () => new Setlet()).add(node); |
| } |
| |
| void removeCall(Element caller, node) { |
| Setlet calls = _callers[caller]; |
| if (calls == null) return; |
| calls.remove(node); |
| if (calls.isEmpty) { |
| _callers.remove(caller); |
| } |
| } |
| |
| Iterable<Element> get callers => _callers.keys; |
| |
| bool isCalledOnce() { |
| int count = 0; |
| for (var set in _callers.values) { |
| count += set.length; |
| if (count > 1) return false; |
| } |
| return count == 1; |
| } |
| |
| bool get isClosurized => closurizedCount > 0; |
| |
| // Closurized methods never become stable to ensure that the information in |
| // [users] is accurate. The inference stops tracking users for stable types. |
| // Note that we only override the getter, the setter will still modify the |
| // state of the [isStable] field inhertied from [TypeInformation]. |
| bool get isStable => super.isStable && !isClosurized; |
| |
| TypeMask handleSpecialCases(TypeGraphInferrerEngine inferrer) { |
| if (abandonInferencing) return type; |
| |
| if (element.isParameter) { |
| Element enclosing = element.enclosingElement; |
| if (Elements.isLocal(enclosing) && disableInferenceForClosures) { |
| // Do not infer types for parameters of closures. We do not |
| // clear the assignments in case the closure is successfully |
| // traced. |
| giveUp(inferrer, clearAssignments: false); |
| return type; |
| } else if (enclosing.isInstanceMember && |
| (enclosing.name == Compiler.NO_SUCH_METHOD || |
| (enclosing.name == Compiler.CALL_OPERATOR_NAME && |
| disableInferenceForClosures))) { |
| // Do not infer types for parameters of [noSuchMethod] and |
| // [call] instance methods. |
| giveUp(inferrer); |
| return type; |
| } else if (enclosing == inferrer.mainElement) { |
| // The implicit call to main is not seen by the inferrer, |
| // therefore we explicitly set the type of its parameters as |
| // dynamic. |
| // TODO(14566): synthesize a call instead to get the exact |
| // types. |
| giveUp(inferrer); |
| return type; |
| } |
| } |
| if (element.isField || |
| element.isParameter || |
| element.isFieldParameter) { |
| if (!inferrer.compiler.backend.canBeUsedForGlobalOptimizations(element)) { |
| // Do not infer types for fields and parameters being assigned |
| // by synthesized calls. |
| giveUp(inferrer); |
| return type; |
| } |
| } |
| if (inferrer.isNativeElement(element)) { |
| // Use the type annotation as the type for native elements. We |
| // also give up on inferring to make sure this element never |
| // goes in the work queue. |
| giveUp(inferrer); |
| if (element.isField) { |
| return inferrer.typeOfNativeBehavior( |
| native.NativeBehavior.ofFieldLoad(element, inferrer.compiler)).type; |
| } else { |
| assert(element.isFunction || |
| element.isGetter || |
| element.isSetter); |
| TypedElement typedElement = element; |
| var elementType = typedElement.type; |
| if (elementType.kind != TypeKind.FUNCTION) { |
| return type; |
| } else { |
| return inferrer.typeOfNativeBehavior( |
| native.NativeBehavior.ofMethod(element, inferrer.compiler)).type; |
| } |
| } |
| } |
| |
| Compiler compiler = inferrer.compiler; |
| if (element.declaration == compiler.intEnvironment) { |
| giveUp(inferrer); |
| return compiler.typesTask.intType.nullable(); |
| } else if (element.declaration == compiler.boolEnvironment) { |
| giveUp(inferrer); |
| return compiler.typesTask.boolType.nullable(); |
| } else if (element.declaration == compiler.stringEnvironment) { |
| giveUp(inferrer); |
| return compiler.typesTask.stringType.nullable(); |
| } |
| return null; |
| } |
| |
| TypeMask potentiallyNarrowType(TypeMask mask, |
| TypeGraphInferrerEngine inferrer) { |
| Compiler compiler = inferrer.compiler; |
| // Parameters are being explicitly checked in the method. |
| if (element.isParameter || element.isFieldParameter) return mask; |
| if (!compiler.trustTypeAnnotations && !compiler.enableTypeAssertions) { |
| return mask; |
| } |
| if (element.isGenerativeConstructor || element.isSetter) return mask; |
| var type = element.computeType(compiler); |
| if (element.isFunction || |
| element.isGetter || |
| element.isFactoryConstructor) { |
| type = type.returnType; |
| } |
| return new TypeMaskSystem(compiler).narrowType(mask, type); |
| } |
| |
| TypeMask refine(TypeGraphInferrerEngine inferrer) { |
| TypeMask special = handleSpecialCases(inferrer); |
| if (special != null) return potentiallyNarrowType(special, inferrer); |
| return potentiallyNarrowType( |
| inferrer.types.computeTypeMask(assignments), inferrer); |
| } |
| |
| String toString() => 'Element $element $type'; |
| |
| accept(TypeInformationVisitor visitor) { |
| return visitor.visitElementTypeInformation(this); |
| } |
| |
| Element get owner => element.outermostEnclosingMemberOrTopLevel; |
| |
| bool hasStableType(TypeGraphInferrerEngine inferrer) { |
| // The number of assignments of parameters of instance methods is |
| // not stable. Therefore such a parameter cannot be stable. |
| if (element.isParameter && element.enclosingElement.isInstanceMember) { |
| return false; |
| } |
| |
| // The number of assignments of non-final fields is |
| // not stable. Therefore such a field cannot be stable. |
| if (element.isField && !(element.isConst || element.isFinal)) { |
| return false; |
| } |
| |
| if (element.isFunction) return false; |
| |
| return super.hasStableType(inferrer); |
| } |
| } |
| |
| /** |
| * A [CallSiteTypeInformation] is a call found in the AST, or a |
| * synthesized call for implicit calls in Dart (such as forwarding |
| * factories). The [call] field is a [ast.Node] for the former, and an |
| * [Element] for the latter. |
| * |
| * In the inferrer graph, [CallSiteTypeInformation] nodes do not have |
| * any assignment. They rely on the [caller] field for static calls, |
| * and [selector] and [receiver] fields for dynamic calls. |
| */ |
| abstract class CallSiteTypeInformation extends ApplyableTypeInformation { |
| final Spannable call; |
| final Element caller; |
| final Selector selector; |
| final ArgumentsTypes arguments; |
| final bool inLoop; |
| |
| CallSiteTypeInformation( |
| this.call, |
| this.caller, |
| this.selector, |
| this.arguments, |
| this.inLoop) : super(null, const <TypeInformation>[]); |
| |
| String toString() => 'Call site $call $type'; |
| |
| /// Add [this] to the graph being computed by [engine]. |
| void addToGraph(TypeGraphInferrerEngine engine); |
| |
| /// Return an iterable over the targets of this call. |
| Iterable<Element> get callees; |
| |
| Element get owner => caller; |
| } |
| |
| class StaticCallSiteTypeInformation extends CallSiteTypeInformation { |
| final Element calledElement; |
| |
| StaticCallSiteTypeInformation( |
| Spannable call, |
| Element enclosing, |
| this.calledElement, |
| Selector selector, |
| ArgumentsTypes arguments, |
| bool inLoop) : super(call, enclosing, selector, arguments, inLoop); |
| |
| void addToGraph(TypeGraphInferrerEngine inferrer) { |
| ElementTypeInformation callee = |
| inferrer.types.getInferredTypeOf(calledElement); |
| callee.addCall(caller, call); |
| callee.addUser(this); |
| if (arguments != null) { |
| arguments.forEach((info) => info.addUser(this)); |
| } |
| inferrer.updateParameterAssignments( |
| this, calledElement, arguments, selector, remove: false, |
| addToQueue: false); |
| } |
| |
| bool get isSynthesized { |
| // Some calls do not have a corresponding node, for example |
| // fowarding factory constructors, or synthesized super |
| // constructor calls. We synthesize these calls but do |
| // not create a selector for them. |
| return selector == null; |
| } |
| |
| TypeMask refine(TypeGraphInferrerEngine inferrer) { |
| if (isSynthesized) { |
| assert(arguments != null); |
| return inferrer.types.getInferredTypeOf(calledElement).type; |
| } else { |
| return inferrer.typeOfElementWithSelector(calledElement, selector).type; |
| } |
| } |
| |
| Iterable<Element> get callees => [calledElement.implementation]; |
| |
| accept(TypeInformationVisitor visitor) { |
| return visitor.visitStaticCallSiteTypeInformation(this); |
| } |
| |
| bool hasStableType(TypeGraphInferrerEngine inferrer) { |
| return inferrer.types.getInferredTypeOf(calledElement).isStable && |
| (arguments == null || arguments.every((info) => info.isStable)) && |
| super.hasStableType(inferrer); |
| } |
| |
| void removeAndClearReferences(TypeGraphInferrerEngine inferrer) { |
| ElementTypeInformation callee = |
| inferrer.types.getInferredTypeOf(calledElement); |
| callee.removeUser(this); |
| if (arguments != null) { |
| arguments.forEach((info) => info.removeUser(this)); |
| } |
| super.removeAndClearReferences(inferrer); |
| } |
| } |
| |
| class DynamicCallSiteTypeInformation extends CallSiteTypeInformation { |
| final TypeInformation receiver; |
| /// Cached targets of this call. |
| Iterable<Element> targets; |
| |
| DynamicCallSiteTypeInformation( |
| Spannable call, |
| Element enclosing, |
| Selector selector, |
| this.receiver, |
| ArgumentsTypes arguments, |
| bool inLoop) : super(call, enclosing, selector, arguments, inLoop); |
| |
| void addToGraph(TypeGraphInferrerEngine inferrer) { |
| assert(receiver != null); |
| Selector typedSelector = computeTypedSelector(inferrer); |
| targets = inferrer.compiler.world.allFunctions.filter(typedSelector); |
| receiver.addUser(this); |
| if (arguments != null) { |
| arguments.forEach((info) => info.addUser(this)); |
| } |
| for (Element element in targets) { |
| ElementTypeInformation callee = inferrer.types.getInferredTypeOf(element); |
| callee.addCall(caller, call); |
| callee.addUser(this); |
| inferrer.updateParameterAssignments( |
| this, element, arguments, typedSelector, remove: false, |
| addToQueue: false); |
| } |
| } |
| |
| Iterable<Element> get callees => targets.map((e) => e.implementation); |
| |
| Selector computeTypedSelector(TypeGraphInferrerEngine inferrer) { |
| TypeMask receiverType = receiver.type; |
| |
| if (selector.mask != receiverType) { |
| return receiverType == inferrer.compiler.typesTask.dynamicType |
| ? selector.asUntyped |
| : new TypedSelector(receiverType, selector); |
| } else { |
| return selector; |
| } |
| } |
| |
| bool get targetsIncludeNoSuchMethod { |
| return targets.any((Element e) { |
| return e is FunctionElement && |
| e.isInstanceMember && |
| e.name == Compiler.NO_SUCH_METHOD; |
| }); |
| } |
| |
| /** |
| * We optimize certain operations on the [int] class because we know |
| * more about their return type than the actual Dart code. For |
| * example, we know int + int returns an int. The Dart code for |
| * [int.operator+] only says it returns a [num]. |
| */ |
| TypeInformation handleIntrisifiedSelector(Selector selector, |
| TypeGraphInferrerEngine inferrer) { |
| Compiler compiler = inferrer.compiler; |
| if (!compiler.backend.intImplementation.isResolved) return null; |
| TypeMask emptyType = const TypeMask.nonNullEmpty(); |
| if (selector.mask == null) return null; |
| if (!selector.mask.containsOnlyInt(compiler)) { |
| return null; |
| } |
| if (!selector.isCall && !selector.isOperator) return null; |
| if (!arguments.named.isEmpty) return null; |
| if (arguments.positional.length > 1) return null; |
| |
| ClassElement uint31Implementation = compiler.backend.uint31Implementation; |
| bool isInt(info) => info.type.containsOnlyInt(compiler); |
| bool isEmpty(info) => info.type == emptyType; |
| bool isUInt31(info) { |
| return info.type.satisfies(uint31Implementation, compiler); |
| } |
| bool isPositiveInt(info) { |
| return info.type.satisfies( |
| compiler.backend.positiveIntImplementation, compiler); |
| } |
| |
| String name = selector.name; |
| // We are optimizing for the cases that are not expressed in the |
| // Dart code, for example: |
| // int + int -> int |
| // uint31 | uint31 -> uint31 |
| if (name == '*' || name == '+' || name == '%' || name == 'remainder' || |
| name == '~/') { |
| if (isPositiveInt(receiver) && |
| arguments.hasOnePositionalArgumentThatMatches(isPositiveInt)) { |
| return inferrer.types.positiveIntType; |
| } else if (arguments.hasOnePositionalArgumentThatMatches(isInt)) { |
| return inferrer.types.intType; |
| } else if (arguments.hasOnePositionalArgumentThatMatches(isEmpty)) { |
| return inferrer.types.nonNullEmptyType; |
| } else { |
| return null; |
| } |
| } else if (name == '|' || name == '^') { |
| if (isUInt31(receiver) && |
| arguments.hasOnePositionalArgumentThatMatches(isUInt31)) { |
| return inferrer.types.uint31Type; |
| } |
| } else if (name == '>>') { |
| if (isUInt31(receiver)) { |
| return inferrer.types.uint31Type; |
| } |
| } else if (name == '&') { |
| if (isUInt31(receiver) || |
| arguments.hasOnePositionalArgumentThatMatches(isUInt31)) { |
| return inferrer.types.uint31Type; |
| } |
| } else if (name == 'unary-') { |
| // The receiver being an int, the return value will also be an |
| // int. |
| return inferrer.types.intType; |
| } else if (name == '-') { |
| if (arguments.hasOnePositionalArgumentThatMatches(isInt)) { |
| return inferrer.types.intType; |
| } else if (arguments.hasOnePositionalArgumentThatMatches(isEmpty)) { |
| return inferrer.types.nonNullEmptyType; |
| } |
| return null; |
| } else if (name == 'abs') { |
| return arguments.hasNoArguments() ? inferrer.types.positiveIntType : null; |
| } |
| return null; |
| } |
| |
| TypeMask refine(TypeGraphInferrerEngine inferrer) { |
| Iterable<Element> oldTargets = targets; |
| Selector typedSelector = computeTypedSelector(inferrer); |
| inferrer.updateSelectorInTree(caller, call, typedSelector); |
| |
| Compiler compiler = inferrer.compiler; |
| Selector selectorToUse = typedSelector.extendIfReachesAll(compiler); |
| |
| bool canReachAll = compiler.enabledInvokeOn && |
| (selectorToUse != typedSelector); |
| |
| // If this call could potentially reach all methods that satisfy |
| // the untyped selector (through noSuchMethod's `Invocation` |
| // and a call to `delegate`), we iterate over all these methods to |
| // update their parameter types. |
| targets = compiler.world.allFunctions.filter(selectorToUse); |
| Iterable<Element> typedTargets = canReachAll |
| ? compiler.world.allFunctions.filter(typedSelector) |
| : targets; |
| |
| // Walk over the found targets, and compute the joined union type mask |
| // for all these targets. |
| TypeMask newType = inferrer.types.joinTypeMasks(targets.map((element) { |
| if (!oldTargets.contains(element)) { |
| ElementTypeInformation callee = |
| inferrer.types.getInferredTypeOf(element); |
| callee.addCall(caller, call); |
| callee.addUser(this); |
| inferrer.updateParameterAssignments( |
| this, element, arguments, typedSelector, remove: false, |
| addToQueue: true); |
| } |
| |
| // If [canReachAll] is true, then we are iterating over all |
| // targets that satisfy the untyped selector. We skip the return |
| // type of the targets that can only be reached through |
| // `Invocation.delegate`. Note that the `noSuchMethod` targets |
| // are included in [typedTargets]. |
| if (canReachAll && !typedTargets.contains(element)) { |
| return const TypeMask.nonNullEmpty(); |
| } |
| |
| if (inferrer.returnsListElementType(typedSelector)) { |
| ContainerTypeMask mask = receiver.type; |
| return mask.elementType; |
| } else if (inferrer.returnsMapValueType(typedSelector)) { |
| if (typedSelector.mask.isDictionary && |
| arguments.positional[0].type.isValue) { |
| DictionaryTypeMask mask = typedSelector.mask; |
| ValueTypeMask arg = arguments.positional[0].type; |
| String key = arg.value; |
| if (mask.typeMap.containsKey(key)) { |
| if (_VERBOSE) { |
| print("Dictionary lookup for $key yields ${mask.typeMap[key]}."); |
| } |
| return mask.typeMap[key]; |
| } else { |
| // The typeMap is precise, so if we do not find the key, the lookup |
| // will be [null] at runtime. |
| if (_VERBOSE) { |
| print("Dictionary lookup for $key yields [null]."); |
| } |
| return inferrer.types.nullType.type; |
| } |
| } |
| MapTypeMask mask = typedSelector.mask; |
| if (_VERBOSE) { |
| print("Map lookup for $typedSelector yields ${mask.valueType}."); |
| } |
| return mask.valueType; |
| } else { |
| TypeInformation info = |
| handleIntrisifiedSelector(typedSelector, inferrer); |
| if (info != null) return info.type; |
| return inferrer.typeOfElementWithSelector(element, typedSelector).type; |
| } |
| })); |
| |
| // Walk over the old targets, and remove calls that cannot happen |
| // anymore. |
| oldTargets.forEach((element) { |
| if (!targets.contains(element)) { |
| ElementTypeInformation callee = |
| inferrer.types.getInferredTypeOf(element); |
| callee.removeCall(caller, call); |
| callee.removeUser(this); |
| inferrer.updateParameterAssignments( |
| this, element, arguments, typedSelector, remove: true, |
| addToQueue: true); |
| } |
| }); |
| |
| return newType; |
| } |
| |
| void giveUp(TypeGraphInferrerEngine inferrer, {bool clearAssignments: true}) { |
| inferrer.updateSelectorInTree(caller, call, selector); |
| Iterable<Element> oldTargets = targets; |
| targets = inferrer.compiler.world.allFunctions.filter(selector); |
| for (Element element in targets) { |
| if (!oldTargets.contains(element)) { |
| ElementTypeInformation callee = |
| inferrer.types.getInferredTypeOf(element); |
| callee.addCall(caller, call); |
| inferrer.updateParameterAssignments( |
| this, element, arguments, selector, remove: false, |
| addToQueue: true); |
| } |
| } |
| super.giveUp(inferrer, clearAssignments: clearAssignments); |
| } |
| |
| void removeAndClearReferences(TypeGraphInferrerEngine inferrer) { |
| for (Element element in targets) { |
| ElementTypeInformation callee = inferrer.types.getInferredTypeOf(element); |
| callee.removeUser(this); |
| } |
| if (arguments != null) { |
| arguments.forEach((info) => info.removeUser(this)); |
| } |
| super.removeAndClearReferences(inferrer); |
| } |
| |
| String toString() => 'Call site $call on ${receiver.type} $type'; |
| |
| accept(TypeInformationVisitor visitor) { |
| return visitor.visitDynamicCallSiteTypeInformation(this); |
| } |
| |
| bool hasStableType(TypeGraphInferrerEngine inferrer) { |
| return receiver.isStable && |
| targets.every( |
| (element) => inferrer.types.getInferredTypeOf(element).isStable) && |
| (arguments == null || arguments.every((info) => info.isStable)) && |
| super.hasStableType(inferrer); |
| } |
| } |
| |
| class ClosureCallSiteTypeInformation extends CallSiteTypeInformation { |
| final TypeInformation closure; |
| |
| ClosureCallSiteTypeInformation( |
| Spannable call, |
| Element enclosing, |
| Selector selector, |
| this.closure, |
| ArgumentsTypes arguments, |
| bool inLoop) : super(call, enclosing, selector, arguments, inLoop); |
| |
| void addToGraph(TypeGraphInferrerEngine inferrer) { |
| arguments.forEach((info) => info.addUser(this)); |
| closure.addUser(this); |
| } |
| |
| TypeMask refine(TypeGraphInferrerEngine inferrer) { |
| return inferrer.types.dynamicType.type; |
| } |
| |
| Iterable<Element> get callees { |
| throw new UnsupportedError("Cannot compute callees of a closure call."); |
| } |
| |
| String toString() => 'Closure call $call on $closure'; |
| |
| accept(TypeInformationVisitor visitor) { |
| return visitor.visitClosureCallSiteTypeInformation(this); |
| } |
| |
| void removeAndClearReferences(TypeGraphInferrerEngine inferrer) { |
| // This method is a placeholder for the following comment: |
| // We should maintain the information that the closure is a user |
| // of its arguments because we do not check that the arguments |
| // have a stable type for a closure call to be stable; our tracing |
| // analysis want to know whether an (non-stable) argument is |
| // passed to a closure. |
| return super.removeAndClearReferences(inferrer); |
| } |
| } |
| |
| /** |
| * A [ConcreteTypeInformation] represents a type that needed |
| * to be materialized during the creation of the graph. For example, |
| * literals, [:this:] or [:super:] need a [ConcreteTypeInformation]. |
| * |
| * [ConcreteTypeInformation] nodes have no assignment. Also, to save |
| * on memory, we do not add users to [ConcreteTypeInformation] nodes, |
| * because we know such node will never be refined to a different |
| * type. |
| */ |
| class ConcreteTypeInformation extends TypeInformation { |
| ConcreteTypeInformation(TypeMask type) |
| : super(const <TypeInformation>[], const <TypeInformation>[]) { |
| this.type = type; |
| this.isStable = true; |
| } |
| |
| bool get isConcrete => true; |
| |
| void addUser(TypeInformation user) { |
| // Nothing to do, a concrete type does not get updated so never |
| // needs to notify its users. |
| } |
| |
| void removeUser(TypeInformation user) { |
| } |
| |
| void addAssignment(TypeInformation assignment) { |
| } |
| |
| void removeAssignment(TypeInformation assignment) { |
| assert(false); |
| } |
| |
| void reset(TypeGraphInferrerEngine inferrer) { |
| assert(false); |
| } |
| |
| String toString() => 'Type $type'; |
| |
| accept(TypeInformationVisitor visitor) { |
| return visitor.visitConcreteTypeInformation(this); |
| } |
| |
| bool hasStableType(TypeGraphInferrerEngine inferrer) { |
| return true; |
| } |
| } |
| |
| class StringLiteralTypeInformation extends ConcreteTypeInformation { |
| final ast.DartString value; |
| |
| StringLiteralTypeInformation(value, TypeMask mask) |
| : super(new ValueTypeMask(mask, value.slowToString())), |
| this.value = value; |
| |
| String asString() => value.slowToString(); |
| String toString() => 'Type $type value ${value.slowToString()}'; |
| |
| accept(TypeInformationVisitor visitor) { |
| return visitor.visitStringLiteralTypeInformation(this); |
| } |
| } |
| |
| /** |
| * A [NarrowTypeInformation] narrows a [TypeInformation] to a type, |
| * represented in [typeAnnotation]. |
| * |
| * A [NarrowTypeInformation] node has only one assignment: the |
| * [TypeInformation] it narrows. |
| * |
| * [NarrowTypeInformation] nodes are created for: |
| * |
| * - Code after `is` and `as` checks, where we have more information |
| * on the type of the right hand side of the expression. |
| * |
| * - Code after a dynamic call, where we have more information on the |
| * type of the receiver: it can only be of a class that holds a |
| * potential target of this dynamic call. |
| * |
| * - In checked mode, after a type annotation, we have more |
| * information on the type of a local. |
| */ |
| class NarrowTypeInformation extends TypeInformation { |
| final TypeMask typeAnnotation; |
| |
| NarrowTypeInformation(narrowedType, this.typeAnnotation) { |
| addAssignment(narrowedType); |
| } |
| |
| TypeMask refine(TypeGraphInferrerEngine inferrer) { |
| return assignments[0].type.intersection(typeAnnotation, inferrer.compiler); |
| } |
| |
| String toString() { |
| return 'Narrow to $typeAnnotation $type'; |
| } |
| |
| accept(TypeInformationVisitor visitor) { |
| return visitor.visitNarrowTypeInformation(this); |
| } |
| } |
| |
| /** |
| * An [InferredTypeInformation] is a [TypeInformation] that |
| * defaults to the dynamic type until it is marked as beeing |
| * inferred, at which point it computes its type based on |
| * its assignments. |
| */ |
| abstract class InferredTypeInformation extends TypeInformation { |
| /** Whether the element type in that container has been inferred. */ |
| bool inferred = false; |
| |
| InferredTypeInformation(parentType) { |
| if (parentType != null) addAssignment(parentType); |
| } |
| |
| TypeMask refine(TypeGraphInferrerEngine inferrer) { |
| if (!inferred) { |
| return inferrer.types.dynamicType.type; |
| } |
| return inferrer.types.computeTypeMask(assignments); |
| } |
| |
| bool hasStableType(TypeGraphInferrerEngine inferrer) { |
| return inferred && super.hasStableType(inferrer); |
| } |
| } |
| |
| /** |
| * A [ListTypeInformation] is a [TypeInformation] created |
| * for each `List` instantiations. |
| */ |
| class ListTypeInformation extends TypeInformation { |
| final ElementInContainerTypeInformation elementType; |
| |
| /** The container type before it is inferred. */ |
| final ContainerTypeMask originalContainerType; |
| |
| /** The length at the allocation site. */ |
| final int originalLength; |
| |
| /** The length after the container has been traced. */ |
| int inferredLength; |
| |
| /** |
| * Whether this list goes through a growable check. |
| * We conservatively assume it does. |
| */ |
| bool checksGrowable = true; |
| |
| // The set of [TypeInformation] where the traced container could |
| // flow in. |
| final Setlet<TypeInformation> flowsInto = new Setlet<TypeInformation>(); |
| |
| bool bailedOut = true; |
| bool analyzed = false; |
| |
| ListTypeInformation(this.originalContainerType, |
| this.elementType, |
| this.originalLength) { |
| type = originalContainerType; |
| inferredLength = originalContainerType.length; |
| elementType.addUser(this); |
| } |
| |
| String toString() => 'List type $type'; |
| |
| accept(TypeInformationVisitor visitor) { |
| return visitor.visitListTypeInformation(this); |
| } |
| |
| bool hasStableType(TypeGraphInferrerEngine inferrer) { |
| return elementType.isStable && super.hasStableType(inferrer); |
| } |
| |
| TypeMask refine(TypeGraphInferrerEngine inferrer) { |
| var mask = type; |
| if (!mask.isContainer || |
| mask.elementType != elementType.type || |
| mask.length != inferredLength) { |
| return new ContainerTypeMask(originalContainerType.forwardTo, |
| originalContainerType.allocationNode, |
| originalContainerType.allocationElement, |
| elementType.type, |
| inferredLength); |
| } |
| return mask; |
| } |
| |
| void giveUp(TypeGraphInferrerEngine inferrer, {bool clearAssignments: true}) { |
| super.giveUp(inferrer, clearAssignments: clearAssignments); |
| // We still know that this node represents a container, so we explicitly |
| // preserve that information here. |
| type = new ContainerTypeMask(originalContainerType.forwardTo, |
| originalContainerType.allocationNode, |
| originalContainerType.allocationElement, |
| inferrer.types.dynamicType.type, |
| null); |
| } |
| } |
| |
| /** |
| * An [ElementInContainerTypeInformation] holds the common type of the |
| * elements in a [ListTypeInformation]. |
| */ |
| class ElementInContainerTypeInformation extends InferredTypeInformation { |
| ElementInContainerTypeInformation(elementType) : super(elementType); |
| |
| String toString() => 'Element in container $type'; |
| |
| accept(TypeInformationVisitor visitor) { |
| return visitor.visitElementInContainerTypeInformation(this); |
| } |
| } |
| |
| /** |
| * A [MapTypeInformation] is a [TypeInformation] created |
| * for maps. |
| */ |
| class MapTypeInformation extends TypeInformation { |
| // When in Dictionary mode, this map tracks the type of the values that |
| // have been assigned to a specific [String] key. |
| final Map<String, ValueInMapTypeInformation> typeInfoMap = {}; |
| // These fields track the overall type of the keys/values in the map. |
| final KeyInMapTypeInformation keyType; |
| final ValueInMapTypeInformation valueType; |
| final MapTypeMask initialType; |
| |
| // The set of [TypeInformation] where values from the traced map could |
| // flow in. |
| final Setlet<TypeInformation> flowsInto = new Setlet<TypeInformation>(); |
| |
| // Set to false once analysis has succeeded. |
| bool bailedOut = true; |
| bool analyzed = false; |
| |
| // Set to false if a statically unknown key flows into this map. |
| bool isDictionary = true; |
| |
| MapTypeInformation(this.initialType, this.keyType, this.valueType) { |
| keyType.addUser(this); |
| valueType.addUser(this); |
| type = initialType; |
| } |
| |
| TypeInformation addEntryAssignment(TypeInformation key, |
| TypeInformation value, |
| [bool nonNull = false]) { |
| TypeInformation newInfo = null; |
| if (isDictionary && key is StringLiteralTypeInformation) { |
| String keyString = key.asString(); |
| typeInfoMap.putIfAbsent(keyString, |
| () => newInfo = new ValueInMapTypeInformation(null, nonNull)); |
| typeInfoMap[keyString].addAssignment(value); |
| } else { |
| isDictionary = false; |
| typeInfoMap.clear(); |
| } |
| keyType.addAssignment(key); |
| valueType.addAssignment(value); |
| if (newInfo != null) newInfo.addUser(this); |
| |
| return newInfo; |
| } |
| |
| List<TypeInformation> addMapAssignment(MapTypeInformation map) { |
| List<TypeInformation> newInfos = <TypeInformation>[]; |
| if (map.isDictionary) { |
| map.typeInfoMap.forEach((keyString, value) { |
| typeInfoMap.putIfAbsent(keyString, () { |
| TypeInformation newInfo = new ValueInMapTypeInformation(null, false); |
| newInfos.add(newInfo); |
| return newInfo; |
| }); |
| typeInfoMap[keyString].addAssignment(value); |
| }); |
| } |
| keyType.addAssignment(map.keyType); |
| valueType.addAssignment(map.valueType); |
| |
| return newInfos; |
| } |
| |
| markAsInferred() { |
| keyType.inferred = valueType.inferred = true; |
| typeInfoMap.values.forEach((v) => v.inferred = true); |
| } |
| |
| addAssignment(TypeInformation other) { |
| throw "not supported"; |
| } |
| |
| accept(TypeInformationVisitor visitor) { |
| return visitor.visitMapTypeInformation(this); |
| } |
| |
| TypeMask toTypeMask(TypeGraphInferrerEngine inferrer) { |
| if (isDictionary) { |
| Map<String, TypeMask> mappings = new Map<String, TypeMask>(); |
| for (var key in typeInfoMap.keys) { |
| mappings[key] = typeInfoMap[key].type; |
| } |
| return new DictionaryTypeMask(initialType.forwardTo, |
| initialType.allocationNode, |
| initialType.allocationElement, |
| keyType.type, |
| valueType.type, |
| mappings); |
| } else { |
| return new MapTypeMask(initialType.forwardTo, |
| initialType.allocationNode, |
| initialType.allocationElement, |
| keyType.type, |
| valueType.type); |
| } |
| } |
| |
| TypeMask refine(TypeGraphInferrerEngine inferrer) { |
| if (!bailedOut && type.isDictionary != isDictionary) { |
| return toTypeMask(inferrer); |
| } else if (!bailedOut && type.isDictionary) { |
| DictionaryTypeMask mask = type; |
| for (var key in typeInfoMap.keys) { |
| TypeInformation value = typeInfoMap[key]; |
| if (!mask.typeMap.containsKey(key) && |
| !value.type.containsAll(inferrer.compiler) && |
| !value.type.isNullable) { |
| return toTypeMask(inferrer); |
| } |
| if (mask.typeMap[key] != typeInfoMap[key].type) { |
| return toTypeMask(inferrer); |
| } |
| } |
| } else if (type.isMap) { |
| MapTypeMask mask = type; |
| if (mask.keyType != keyType.type || |
| mask.valueType != valueType.type) { |
| return toTypeMask(inferrer); |
| } |
| } else { |
| return toTypeMask(inferrer); |
| } |
| |
| return type; |
| } |
| |
| bool hasStableType(TypeGraphInferrerEngine inferrer) { |
| return keyType.isStable && |
| valueType.isStable && |
| super.hasStableType(inferrer); |
| } |
| |
| String toString() { |
| return 'Map $type (K:$keyType, V:$valueType) contents $typeInfoMap'; |
| } |
| } |
| |
| /** |
| * A [KeyInMapTypeInformation] holds the common type |
| * for the keys in a [MapTypeInformation] |
| */ |
| class KeyInMapTypeInformation extends InferredTypeInformation { |
| KeyInMapTypeInformation(TypeInformation keyType) : super(keyType); |
| |
| accept(TypeInformationVisitor visitor) { |
| return visitor.visitKeyInMapTypeInformation(this); |
| } |
| |
| TypeMask refine(TypeGraphInferrerEngine inferrer) { |
| return super.refine(inferrer); |
| } |
| |
| String toString() => 'Key in Map $type'; |
| } |
| |
| /** |
| * A [ValueInMapTypeInformation] holds the common type |
| * for the values in a [MapTypeInformation] |
| */ |
| class ValueInMapTypeInformation extends InferredTypeInformation { |
| // [nonNull] is set to true if this value is known to be part of the map. |
| // Note that only values assigned to a specific key value in dictionary |
| // mode can ever be marked as [nonNull]. |
| final bool nonNull; |
| |
| ValueInMapTypeInformation(TypeInformation valueType, [this.nonNull = false]) |
| : super(valueType); |
| |
| accept(TypeInformationVisitor visitor) { |
| return visitor.visitValueInMapTypeInformation(this); |
| } |
| |
| TypeMask refine(TypeGraphInferrerEngine inferrer) { |
| return nonNull ? super.refine(inferrer) : super.refine(inferrer).nullable(); |
| } |
| |
| String toString() => 'Value in Map $type'; |
| } |
| |
| /** |
| * A [PhiElementTypeInformation] is an union of |
| * [ElementTypeInformation], that is local to a method. |
| */ |
| class PhiElementTypeInformation extends TypeInformation { |
| final ast.Node branchNode; |
| final bool isLoopPhi; |
| final Element element; |
| |
| PhiElementTypeInformation(this.branchNode, this.isLoopPhi, this.element); |
| |
| TypeMask refine(TypeGraphInferrerEngine inferrer) { |
| return inferrer.types.computeTypeMask(assignments); |
| } |
| |
| String toString() => 'Phi $element $type'; |
| |
| accept(TypeInformationVisitor visitor) { |
| return visitor.visitPhiElementTypeInformation(this); |
| } |
| } |
| |
| class ClosureTypeInformation extends ApplyableTypeInformation { |
| final ast.Node node; |
| final Element element; |
| |
| ClosureTypeInformation(this.node, this.element); |
| |
| TypeMask refine(TypeGraphInferrerEngine inferrer) { |
| return inferrer.types.functionType.type; |
| } |
| |
| String toString() => 'Closure $element'; |
| |
| accept(TypeInformationVisitor visitor) { |
| return visitor.visitClosureTypeInformation(this); |
| } |
| |
| bool hasStableType(TypeGraphInferrerEngine inferrer) { |
| return false; |
| } |
| } |
| |
| abstract class TypeInformationVisitor<T> { |
| T visitNarrowTypeInformation(NarrowTypeInformation info); |
| T visitPhiElementTypeInformation(PhiElementTypeInformation info); |
| T visitElementInContainerTypeInformation( |
| ElementInContainerTypeInformation info); |
| T visitKeyInMapTypeInformation(KeyInMapTypeInformation info); |
| T visitValueInMapTypeInformation(ValueInMapTypeInformation info); |
| T visitListTypeInformation(ListTypeInformation info); |
| T visitMapTypeInformation(MapTypeInformation info); |
| T visitConcreteTypeInformation(ConcreteTypeInformation info); |
| T visitStringLiteralTypeInformation(StringLiteralTypeInformation info); |
| T visitClosureCallSiteTypeInformation(ClosureCallSiteTypeInformation info); |
| T visitStaticCallSiteTypeInformation(StaticCallSiteTypeInformation info); |
| T visitDynamicCallSiteTypeInformation(DynamicCallSiteTypeInformation info); |
| T visitElementTypeInformation(ElementTypeInformation info); |
| T visitClosureTypeInformation(ClosureTypeInformation info); |
| } |
