Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(473)

Issues Search
    My Issues | Starred     Open | Closed | All

Side by Side Diff: sdk/lib/_internal/compiler/implementation/inferrer/concrete_types_inferrer.dart

Issue 694353007: Move dart2js from sdk/lib/_internal/compiler to pkg/compiler (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 6 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « sdk/lib/_internal/compiler/implementation/inferrer/closure_tracer.dart ('k') | sdk/lib/_internal/compiler/implementation/inferrer/inferrer_visitor.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
2 // for details. All rights reserved. Use of this source code is governed by a
3 // BSD-style license that can be found in the LICENSE file.
4
5 library concrete_types_inferrer;
6
7 import 'dart:collection' show Queue, IterableBase;
8 import '../native/native.dart' as native;
9 import '../dart2jslib.dart' hide Selector, TypedSelector;
10 import '../dart_types.dart' show DartType, TypeKind;
11 import '../elements/elements.dart';
12 import '../tree/tree.dart';
13 import '../universe/universe.dart';
14 import '../util/util.dart';
15
16 import 'inferrer_visitor.dart';
17 import '../types/types.dart' show TypeMask, FlatTypeMask, UnionTypeMask,
18 TypesInferrer;
19 import 'simple_types_inferrer.dart';
20
21 /**
22 * A singleton concrete type. More precisely, a [BaseType] is one of the
23 * following:
24 *
25 * - a non-asbtract class like [:int:] or [:Uri:] (but not [:List:])
26 * - the null base type
27 * - the unknown base type
28 */
29 abstract class BaseType {
30 bool isClass();
31 bool isUnknown();
32 bool isNull();
33 }
34
35 /**
36 * A non-asbtract class like [:int:] or [:Uri:] (but not [:List:]).
37 */
38 class ClassBaseType implements BaseType {
39 final ClassElement element;
40
41 ClassBaseType(this.element);
42
43 bool operator ==(var other) {
44 if (identical(this, other)) return true;
45 if (other is! ClassBaseType) return false;
46 return element == other.element;
47 }
48 int get hashCode => element.hashCode;
49 String toString() {
50 return element == null ? 'toplevel' : element.name;
51 }
52 bool isClass() => true;
53 bool isUnknown() => false;
54 bool isNull() => false;
55 }
56
57 /**
58 * The unknown base type.
59 */
60 class UnknownBaseType implements BaseType {
61 const UnknownBaseType();
62 bool operator ==(BaseType other) => other is UnknownBaseType;
63 int get hashCode => 0;
64 bool isClass() => false;
65 bool isUnknown() => true;
66 bool isNull() => false;
67 toString() => "unknown";
68 }
69
70 /**
71 * The null base type.
72 */
73 class NullBaseType implements BaseType {
74 const NullBaseType();
75 bool operator ==(BaseType other) => identical(other, this);
76 int get hashCode => 1;
77 bool isClass() => false;
78 bool isUnknown() => false;
79 bool isNull() => true;
80 toString() => "null";
81 }
82
83 /**
84 * An immutable set of base types like [:{int, bool}:], or the unknown concrete
85 * type.
86 */
87 abstract class ConcreteType {
88 ConcreteType();
89
90 factory ConcreteType.empty(int maxConcreteTypeSize,
91 BaseTypes classBaseTypes) {
92 return new UnionType(maxConcreteTypeSize, classBaseTypes,
93 new Set<BaseType>());
94 }
95
96 /**
97 * The singleton constituted of the unknown base type is the unknown concrete
98 * type.
99 */
100 factory ConcreteType.singleton(int maxConcreteTypeSize,
101 BaseTypes classBaseTypes,
102 BaseType baseType) {
103 if (baseType.isUnknown() || maxConcreteTypeSize < 1) {
104 return const UnknownConcreteType();
105 }
106 Set<BaseType> singletonSet = new Set<BaseType>();
107 singletonSet.add(baseType);
108 return new UnionType(maxConcreteTypeSize, classBaseTypes, singletonSet);
109 }
110
111 factory ConcreteType.unknown() {
112 return const UnknownConcreteType();
113 }
114
115 ConcreteType union(ConcreteType other);
116 ConcreteType intersection(ConcreteType other);
117 ConcreteType refine(Selector selector, Compiler compiler);
118 bool isUnknown();
119 bool isEmpty();
120 Set<BaseType> get baseTypes;
121
122 /**
123 * Returns the unique element of [:this:] if [:this:] is a singleton, null
124 * otherwise.
125 */
126 ClassElement getUniqueType();
127 }
128
129 /**
130 * The unkown concrete type: it is absorbing for the union.
131 */
132 class UnknownConcreteType implements ConcreteType {
133 const UnknownConcreteType();
134 bool isUnknown() => true;
135 bool isEmpty() => false;
136 bool operator ==(ConcreteType other) => identical(this, other);
137 Set<BaseType> get baseTypes =>
138 new Set<BaseType>.from([const UnknownBaseType()]);
139 int get hashCode => 0;
140 ConcreteType union(ConcreteType other) => this;
141 ConcreteType intersection(ConcreteType other) => other;
142 ConcreteType refine(Selector selector, Compiler compiler) => this;
143 ClassElement getUniqueType() => null;
144 toString() => "unknown";
145 }
146
147 /**
148 * An immutable set of base types, like [: {int, bool} :].
149 */
150 class UnionType implements ConcreteType {
151 final int maxConcreteTypeSize;
152 final BaseTypes classBaseTypes;
153
154 final Set<BaseType> baseTypes;
155
156 /**
157 * The argument should NOT be mutated later. Do not call directly, use
158 * ConcreteType.singleton instead.
159 */
160 UnionType(this.maxConcreteTypeSize, this.classBaseTypes, this.baseTypes);
161
162 bool isUnknown() => false;
163 bool isEmpty() => baseTypes.isEmpty;
164
165 bool operator ==(ConcreteType other) {
166 if (other is! UnionType) return false;
167 if (baseTypes.length != other.baseTypes.length) return false;
168 return baseTypes.containsAll(other.baseTypes);
169 }
170
171 int get hashCode {
172 int result = 1;
173 for (final baseType in baseTypes) {
174 result = 31 * result + baseType.hashCode;
175 }
176 return result;
177 }
178
179 ConcreteType _simplify(Set<BaseType> baseTypes) {
180 // normalize all flavors of ints to int
181 // TODO(polux): handle different ints better
182 if (baseTypes.contains(classBaseTypes.uint31Type)) {
183 baseTypes.remove(classBaseTypes.uint31Type);
184 baseTypes.add(classBaseTypes.intBaseType);
185 }
186 if (baseTypes.contains(classBaseTypes.uint32Type)) {
187 baseTypes.remove(classBaseTypes.uint32Type);
188 baseTypes.add(classBaseTypes.intBaseType);
189 }
190 if (baseTypes.contains(classBaseTypes.positiveIntType)) {
191 baseTypes.remove(classBaseTypes.positiveIntType);
192 baseTypes.add(classBaseTypes.intBaseType);
193 }
194 // normalize {int, float}, {int, num} or {float, num} into num
195 // TODO(polux): generalize this to all types when we extend the concept of
196 // "concrete type" to other abstract classes than num
197 if (baseTypes.contains(classBaseTypes.numBaseType) ||
198 (baseTypes.contains(classBaseTypes.intBaseType)
199 && baseTypes.contains(classBaseTypes.doubleBaseType))) {
200 baseTypes.remove(classBaseTypes.intBaseType);
201 baseTypes.remove(classBaseTypes.doubleBaseType);
202 baseTypes.add(classBaseTypes.numBaseType);
203 }
204
205 // widen big types to dynamic
206 return baseTypes.length > maxConcreteTypeSize
207 ? const UnknownConcreteType()
208 : new UnionType(maxConcreteTypeSize, classBaseTypes, baseTypes);
209 }
210
211 ConcreteType union(ConcreteType other) {
212 if (other.isUnknown()) {
213 return const UnknownConcreteType();
214 }
215 UnionType otherUnion = other; // cast
216 Set<BaseType> newBaseTypes = new Set<BaseType>.from(baseTypes);
217 newBaseTypes.addAll(otherUnion.baseTypes);
218 return _simplify(newBaseTypes);
219 }
220
221 ConcreteType intersection(ConcreteType other) {
222 if (other.isUnknown()) {
223 return this;
224 }
225 Set<BaseType> thisBaseTypes = new Set<BaseType>.from(baseTypes);
226 Set<BaseType> otherBaseTypes = new Set<BaseType>.from(other.baseTypes);
227 return _simplify(thisBaseTypes.intersection(otherBaseTypes));
228 }
229
230 ConcreteType refine(Selector selector, Compiler compiler) {
231 Set<BaseType> newBaseTypes = new Set<BaseType>();
232 for (BaseType baseType in baseTypes) {
233 if (baseType.isClass()) {
234 ClassBaseType classBaseType = baseType;
235 if (classBaseType.element.lookupSelector(selector) != null) {
236 newBaseTypes.add(baseType);
237 }
238 } else {
239 newBaseTypes.add(baseType);
240 }
241 }
242 return _simplify(newBaseTypes);
243 }
244
245 ClassElement getUniqueType() {
246 if (baseTypes.length == 1) {
247 var iterator = baseTypes.iterator;
248 iterator.moveNext();
249 BaseType uniqueBaseType = iterator.current;
250 if (uniqueBaseType.isClass()) {
251 ClassBaseType uniqueClassType = uniqueBaseType;
252 return uniqueClassType.element;
253 }
254 }
255 return null;
256 }
257
258 String toString() => baseTypes.toString();
259 }
260
261 class ConcreteTypeSystem extends TypeSystem<ConcreteType> {
262 final Compiler compiler;
263 final ConcreteTypesInferrer inferrer;
264 final BaseTypes baseTypes;
265
266 final ConcreteType nullType;
267 final ConcreteType _intType;
268 final ConcreteType _uint31Type;
269 final ConcreteType _uint32Type;
270 final ConcreteType _positiveIntType;
271 final ConcreteType _doubleType;
272 final ConcreteType _numType;
273 final ConcreteType _boolType;
274 final ConcreteType _functionType;
275 final ConcreteType _listType;
276 final ConcreteType _constListType;
277 final ConcreteType _fixedListType;
278 final ConcreteType _growableListType;
279 final ConcreteType _mapType;
280 final ConcreteType _constMapType;
281 final ConcreteType _stringType;
282
283 final ConcreteType dynamicType;
284 final ConcreteType typeType;
285 final ConcreteType nonNullEmptyType;
286
287 ConcreteTypeSystem.internal(ConcreteTypesInferrer inferrer,
288 BaseTypes baseTypes,
289 ConcreteType singleton(BaseType baseType))
290 : this.compiler = inferrer.compiler
291 , this.inferrer = inferrer
292 , this.baseTypes = baseTypes
293 , this._constListType = singleton(baseTypes.constMapBaseType)
294 , this._constMapType = singleton(baseTypes.constMapBaseType)
295 , this._doubleType = singleton(baseTypes.doubleBaseType)
296 , this._fixedListType = singleton(baseTypes.fixedListBaseType)
297 , this._functionType = singleton(baseTypes.functionBaseType)
298 , this._growableListType = singleton(baseTypes.growableListBaseType)
299 , this._intType = singleton(baseTypes.intBaseType)
300 , this._listType = singleton(baseTypes.listBaseType)
301 , this._mapType = singleton(baseTypes.mapBaseType)
302 , this._numType = singleton(baseTypes.numBaseType)
303 , this._boolType = singleton(baseTypes.boolBaseType)
304 , this._stringType = singleton(baseTypes.stringBaseType)
305 , this.typeType = singleton(baseTypes.typeBaseType)
306 , this.dynamicType = const UnknownConcreteType()
307 , this.nullType = singleton(const NullBaseType())
308 , this.nonNullEmptyType = new ConcreteType.empty(
309 inferrer.compiler.maxConcreteTypeSize, baseTypes)
310 // TODO(polux): have better types here
311 , this._uint31Type = singleton(baseTypes.intBaseType)
312 , this._uint32Type = singleton(baseTypes.intBaseType)
313 , this._positiveIntType = singleton(baseTypes.intBaseType);
314
315 factory ConcreteTypeSystem(ConcreteTypesInferrer inferrer) {
316 Compiler compiler = inferrer.compiler;
317 BaseTypes baseTypes = new BaseTypes(compiler);
318 return new ConcreteTypeSystem.internal(
319 inferrer,
320 baseTypes,
321 (BaseType baseType) => new ConcreteType.singleton(
322 compiler.maxConcreteTypeSize, baseTypes, baseType));
323 }
324
325 @override
326 ConcreteType get intType {
327 inferrer.augmentSeenClasses(compiler.backend.intImplementation);
328 return _intType;
329 }
330
331 @override
332 ConcreteType get uint31Type {
333 inferrer.augmentSeenClasses(compiler.backend.uint31Implementation);
334 return _uint31Type;
335 }
336
337 @override
338 ConcreteType get uint32Type {
339 inferrer.augmentSeenClasses(compiler.backend.uint32Implementation);
340 return _uint32Type;
341 }
342
343 @override
344 ConcreteType get positiveIntType {
345 inferrer.augmentSeenClasses(compiler.backend.positiveIntImplementation);
346 return _positiveIntType;
347 }
348
349 @override
350 ConcreteType get doubleType {
351 inferrer.augmentSeenClasses(compiler.backend.doubleImplementation);
352 return _doubleType;
353 }
354
355 @override
356 ConcreteType get numType {
357 inferrer.augmentSeenClasses(compiler.backend.numImplementation);
358 return _numType;
359 }
360
361 @override
362 ConcreteType get boolType {
363 inferrer.augmentSeenClasses(compiler.backend.boolImplementation);
364 return _boolType;
365 }
366
367 @override
368 ConcreteType get functionType {
369 inferrer.augmentSeenClasses(compiler.backend.functionImplementation);
370 return _functionType;
371 }
372
373 @override
374 ConcreteType get listType {
375 inferrer.augmentSeenClasses(compiler.backend.listImplementation);
376 return _listType;
377 }
378
379 @override
380 ConcreteType get constListType {
381 inferrer.augmentSeenClasses(compiler.backend.constListImplementation);
382 return _constListType;
383 }
384
385 @override
386 ConcreteType get fixedListType {
387 inferrer.augmentSeenClasses(compiler.backend.fixedListImplementation);
388 return _fixedListType;
389 }
390
391 @override
392 ConcreteType get growableListType {
393 inferrer.augmentSeenClasses(compiler.backend.growableListImplementation);
394 return _growableListType;
395 }
396
397 @override
398 ConcreteType get mapType {
399 inferrer.augmentSeenClasses(compiler.backend.mapImplementation);
400 return _mapType;
401 }
402
403 @override
404 ConcreteType get constMapType {
405 inferrer.augmentSeenClasses(compiler.backend.constMapImplementation);
406 return _constMapType;
407 }
408
409 @override
410 ConcreteType get stringType {
411 inferrer.augmentSeenClasses(compiler.backend.stringImplementation);
412 return _stringType;
413 }
414
415 @override
416 ConcreteType stringLiteralType(_) {
417 inferrer.augmentSeenClasses(compiler.backend.stringImplementation);
418 return _stringType;
419 }
420
421 /**
422 * Returns the [TypeMask] representation of [baseType].
423 */
424 TypeMask baseTypeToTypeMask(BaseType baseType) {
425 if (baseType.isUnknown()) {
426 return const DynamicTypeMask();
427 } else if (baseType.isNull()) {
428 return new TypeMask.empty();
429 } else {
430 ClassBaseType classBaseType = baseType;
431 final element = classBaseType.element;
432 assert(element != null);
433 if (element == compiler.backend.numImplementation) {
434 return new TypeMask.nonNullSubclass(compiler.backend.numImplementation,
435 compiler.world);
436 } else if (element == compiler.backend.intImplementation) {
437 return new TypeMask.nonNullSubclass(compiler.backend.intImplementation,
438 compiler.world);
439 } else {
440 return new TypeMask.nonNullExact(element.declaration, compiler.world);
441 }
442 }
443 }
444
445 /**
446 * Returns the [TypeMask] representation of [concreteType].
447 */
448 TypeMask concreteTypeToTypeMask(ConcreteType concreteType) {
449 if (concreteType == null) return null;
450 TypeMask typeMask = new TypeMask.nonNullEmpty();
451 for (BaseType baseType in concreteType.baseTypes) {
452 TypeMask baseMask = baseTypeToTypeMask(baseType);
453 if (baseMask == const DynamicTypeMask()) return baseMask;
454 typeMask = typeMask.union(baseMask, compiler.world);
455 }
456 return typeMask;
457 }
458
459 @override
460 ConcreteType addPhiInput(Local variable,
461 ConcreteType phiType,
462 ConcreteType newType) {
463 return computeLUB(phiType, newType);
464 }
465
466 @override
467 ConcreteType allocateDiamondPhi(ConcreteType firstInput,
468 ConcreteType secondInput) {
469 return computeLUB(firstInput, secondInput);
470 }
471
472 @override
473 ConcreteType allocatePhi(Node node, Local variable, ConcreteType inputType) {
474 return inputType;
475 }
476
477 @override
478 ConcreteType allocateLoopPhi(Node node, Local variable,
479 ConcreteType inputType) {
480 return inputType;
481 }
482
483 @override
484 ConcreteType computeLUB(ConcreteType firstType, ConcreteType secondType) {
485 if (firstType == null) {
486 return secondType;
487 } else if (secondType == null) {
488 return firstType;
489 } else {
490 return firstType.union(secondType);
491 }
492 }
493
494 // Implementation Inspired by
495 // type_graph_inferrer.TypeInformationSystem.narrowType
496 @override
497 ConcreteType narrowType(ConcreteType type,
498 DartType annotation,
499 {bool isNullable: true}) {
500 if (annotation.treatAsDynamic) return type;
501 if (annotation.isVoid) return nullType;
502 if (annotation.element == compiler.objectClass) return type;
503 ConcreteType otherType;
504 if (annotation.isTypedef || annotation.isFunctionType) {
505 otherType = functionType;
506 } else if (annotation.isTypeVariable) {
507 // TODO(polux): Narrow to bound.
508 return type;
509 } else {
510 assert(annotation.isInterfaceType);
511 otherType = nonNullSubtype(annotation.element);
512 }
513 if (isNullable) otherType = otherType.union(nullType);
514 if (type == null) return otherType;
515 return type.intersection(otherType);
516 }
517
518 @override
519 Selector newTypedSelector(ConcreteType receiver, Selector selector) {
520 return new TypedSelector(concreteTypeToTypeMask(receiver), selector,
521 compiler.world);
522 }
523
524 @override
525 ConcreteType nonNullEmpty() {
526 return nonNullEmptyType;
527 }
528
529 @override
530 ConcreteType nonNullExact(ClassElement cls) {
531 return nonNullSubtype(cls);
532 }
533
534 /**
535 * Helper method for [nonNullSubtype] and [nonNullSubclass].
536 */
537 ConcreteType nonNullSubX(ClassElement cls,
538 Iterable<ClassElement> extractor(ClassElement cls)) {
539 if (cls == compiler.objectClass) {
540 return dynamicType;
541 }
542 ConcreteType result = nonNullEmptyType;
543 void registerClass(ClassElement element) {
544 if (!element.isAbstract) {
545 result = result.union(
546 new ConcreteType.singleton(compiler.maxConcreteTypeSize,
547 baseTypes,
548 new ClassBaseType(element)));
549 inferrer.augmentSeenClasses(element);
550 }
551 }
552 registerClass(cls);
553 Iterable<ClassElement> subtypes = extractor(cls);
554 subtypes.forEach(registerClass);
555 return result;
556 }
557
558 @override
559 ConcreteType nonNullSubclass(ClassElement cls) {
560 return nonNullSubX(cls, compiler.world.subclassesOf);
561 }
562
563 @override
564 ConcreteType nonNullSubtype(ClassElement cls) {
565 return nonNullSubX(cls, compiler.world.subtypesOf);
566 }
567
568 @override
569 ConcreteType simplifyPhi(Node node,
570 Local variable,
571 ConcreteType phiType) {
572 return phiType;
573 }
574
575 @override
576 bool selectorNeedsUpdate(ConcreteType type, Selector selector) {
577 return concreteTypeToTypeMask(type) != selector.mask;
578 }
579
580 @override
581 ConcreteType refineReceiver(Selector selector, ConcreteType receiverType) {
582 return receiverType.refine(selector, compiler);
583 }
584
585 @override
586 bool isNull(ConcreteType type) {
587 return (type.baseTypes.length == 1) && (type.baseTypes.first.isNull());
588 }
589
590 @override
591 ConcreteType allocateClosure(Node node, Element element) {
592 // TODO(polux): register closure here instead of in visitor?
593 return functionType;
594 }
595
596 @override
597 ConcreteType allocateList(ConcreteType type,
598 Node node,
599 Element enclosing,
600 [ConcreteType elementType, int length]) {
601 if (elementType != null) {
602 inferrer.augmentListElementType(elementType);
603 }
604 return type;
605 }
606
607 @override
608 ConcreteType allocateMap(ConcreteType type,
609 Node node,
610 Element element,
611 [List<ConcreteType> keyTypes,
612 List<ConcreteType> valueTypes]) {
613 // TODO(polux): treat maps the same way we treat lists
614 return type;
615 }
616
617 @override
618 ConcreteType getConcreteTypeFor(TypeMask mask) {
619 if (mask.isUnion) {
620 UnionTypeMask union = mask;
621 return union.disjointMasks.fold(
622 nonNullEmptyType,
623 (type1, type2) => type1.union(getConcreteTypeFor(type2)));
624 } else {
625 FlatTypeMask flat = mask;
626 ConcreteType result;
627 if (flat.isEmpty) {
628 result = nonNullEmptyType;
629 } else if (flat.isExact) {
630 result = nonNullExact(flat.base);
631 } else if (flat.isSubclass) {
632 result = nonNullSubclass(flat.base);
633 } else if (flat.isSubtype) {
634 result = nonNullSubtype(flat.base);
635 } else {
636 throw new ArgumentError("unexpected mask");
637 }
638 return flat.isNullable ? result.union(nullType) : result;
639 }
640 }
641 }
642
643 /**
644 * The cartesian product of concrete types: an iterable of
645 * [ConcreteTypesEnvironment]s.
646 */
647 class ConcreteTypeCartesianProduct
648 extends IterableBase<ConcreteTypesEnvironment> {
649 final ConcreteTypesInferrer inferrer;
650 final ClassElement typeOfThis;
651 final Map<Element, ConcreteType> concreteTypes;
652 ConcreteTypeCartesianProduct(this.inferrer, this.typeOfThis,
653 this.concreteTypes);
654 Iterator get iterator => concreteTypes.isEmpty
655 ? [new ConcreteTypesEnvironment(typeOfThis)].iterator
656 : new ConcreteTypeCartesianProductIterator(inferrer, typeOfThis,
657 concreteTypes);
658 String toString() => this.toList().toString();
659 }
660
661 /**
662 * An helper class for [ConcreteTypeCartesianProduct].
663 */
664 class ConcreteTypeCartesianProductIterator
665 implements Iterator<ConcreteTypesEnvironment> {
666 final ConcreteTypesInferrer inferrer;
667 final ClassElement classOfThis;
668 final Map<Element, ConcreteType> concreteTypes;
669 final Map<Element, BaseType> nextValues;
670 final Map<Element, Iterator> state;
671 int size = 1;
672 int counter = 0;
673 ConcreteTypesEnvironment _current;
674
675 ConcreteTypeCartesianProductIterator(this.inferrer, this.classOfThis,
676 Map<Element, ConcreteType> concreteTypes)
677 : this.concreteTypes = concreteTypes,
678 nextValues = new Map<Element, BaseType>(),
679 state = new Map<Element, Iterator>() {
680 if (concreteTypes.isEmpty) {
681 size = 0;
682 return;
683 }
684 for (final e in concreteTypes.keys) {
685 final baseTypes = concreteTypes[e].baseTypes;
686 size *= baseTypes.length;
687 }
688 }
689
690 ConcreteTypesEnvironment get current => _current;
691
692 ConcreteTypesEnvironment takeSnapshot() {
693 Map<Element, ConcreteType> result = new Map<Element, ConcreteType>();
694 nextValues.forEach((k, v) {
695 result[k] = inferrer.singletonConcreteType(v);
696 });
697 return new ConcreteTypesEnvironment.of(result, classOfThis);
698 }
699
700 bool moveNext() {
701 if (counter >= size) {
702 _current = null;
703 return false;
704 }
705 Element keyToIncrement = null;
706 for (final key in concreteTypes.keys) {
707 final iterator = state[key];
708 if (iterator != null && iterator.moveNext()) {
709 nextValues[key] = state[key].current;
710 break;
711 }
712 Iterator newIterator = concreteTypes[key].baseTypes.iterator;
713 state[key] = newIterator;
714 newIterator.moveNext();
715 nextValues[key] = newIterator.current;
716 }
717 counter++;
718 _current = takeSnapshot();
719 return true;
720 }
721 }
722
723 /**
724 * [BaseType] Constants.
725 */
726 class BaseTypes {
727 final ClassBaseType intBaseType;
728 final ClassBaseType doubleBaseType;
729 final ClassBaseType numBaseType;
730 final ClassBaseType boolBaseType;
731 final ClassBaseType stringBaseType;
732 final ClassBaseType listBaseType;
733 final ClassBaseType growableListBaseType;
734 final ClassBaseType fixedListBaseType;
735 final ClassBaseType constListBaseType;
736 final ClassBaseType mapBaseType;
737 final ClassBaseType constMapBaseType;
738 final ClassBaseType objectBaseType;
739 final ClassBaseType typeBaseType;
740 final ClassBaseType functionBaseType;
741 final ClassBaseType uint31Type;
742 final ClassBaseType uint32Type;
743 final ClassBaseType positiveIntType;
744
745 BaseTypes(Compiler compiler) :
746 intBaseType = new ClassBaseType(compiler.backend.intImplementation),
747 doubleBaseType = new ClassBaseType(compiler.backend.doubleImplementation),
748 numBaseType = new ClassBaseType(compiler.backend.numImplementation),
749 boolBaseType = new ClassBaseType(compiler.backend.boolImplementation),
750 stringBaseType = new ClassBaseType(compiler.backend.stringImplementation),
751 listBaseType = new ClassBaseType(compiler.backend.listImplementation),
752 growableListBaseType =
753 new ClassBaseType(compiler.backend.growableListImplementation),
754 fixedListBaseType =
755 new ClassBaseType(compiler.backend.fixedListImplementation),
756 constListBaseType =
757 new ClassBaseType(compiler.backend.constListImplementation),
758 mapBaseType = new ClassBaseType(compiler.backend.mapImplementation),
759 constMapBaseType =
760 new ClassBaseType(compiler.backend.constMapImplementation),
761 objectBaseType = new ClassBaseType(compiler.objectClass),
762 typeBaseType = new ClassBaseType(compiler.backend.typeImplementation),
763 functionBaseType =
764 new ClassBaseType(compiler.backend.functionImplementation),
765 uint31Type = new ClassBaseType(compiler.backend.uint31Implementation),
766 uint32Type = new ClassBaseType(compiler.backend.uint32Implementation),
767 positiveIntType =
768 new ClassBaseType(compiler.backend.positiveIntImplementation);
769 }
770
771 /**
772 * An immutable mapping from method arguments to [ConcreteTypes].
773 */
774 class ConcreteTypesEnvironment {
775 final Map<Element, ConcreteType> environment;
776 final ClassElement classOfThis;
777
778 ConcreteTypesEnvironment([this.classOfThis]) :
779 environment = new Map<Element, ConcreteType>();
780 ConcreteTypesEnvironment.of(this.environment, this.classOfThis);
781
782 ConcreteType lookupType(Element element) => environment[element];
783
784 bool operator ==(ConcreteTypesEnvironment other) {
785 if (other is! ConcreteTypesEnvironment) return false;
786 if (classOfThis != other.classOfThis) return false;
787 if (environment.length != other.environment.length) return false;
788 for (Element key in environment.keys) {
789 if (!other.environment.containsKey(key)
790 || (environment[key] != other.environment[key])) {
791 return false;
792 }
793 }
794 return true;
795 }
796
797 int get hashCode {
798 int result = (classOfThis != null) ? classOfThis.hashCode : 1;
799 environment.forEach((element, concreteType) {
800 result = 31 * (31 * result + element.hashCode) + concreteType.hashCode;
801 });
802 return result;
803 }
804
805 String toString() => "{ this: $classOfThis, env: $environment }";
806 }
807
808 class ClosureEnvironment {
809 ConcreteType thisType;
810 final LocalsHandler locals;
811
812 ClosureEnvironment(this.thisType, this.locals);
813
814 bool mergeLocals(LocalsHandler newLocals) {
815 assert((locals == null) == (newLocals == null));
816 return (locals != null) ? locals.mergeAll([newLocals]) : false;
817 }
818
819 /// Returns true if changed.
820 bool merge(ConcreteType thisType, LocalsHandler locals) {
821 ConcreteType oldThisType = this.thisType;
822 if (this.thisType == null) {
823 this.thisType = thisType;
824 } else if (thisType != null) {
825 this.thisType = this.thisType.union(thisType);
826 }
827 return mergeLocals(locals) || (this.thisType != oldThisType);
828 }
829
830 toString() => "ClosureEnvironment { thisType = $thisType, locals = ... }";
831 }
832
833 /**
834 * A set of encoutered closures.
835 */
836 class Closures {
837 final Compiler compiler;
838 final Map<FunctionElement, ClosureEnvironment> closures =
839 new Map<FunctionElement, ClosureEnvironment>();
840
841 Closures(this.compiler);
842
843 /// Returns true if the environment of the closure has changed.
844 bool put(FunctionElement closure,
845 ConcreteType typeOfThis,
846 LocalsHandler locals) {
847 ClosureEnvironment oldEnvironent = closures[closure];
848 if (oldEnvironent == null) {
849 closures[closure] = new ClosureEnvironment(typeOfThis, locals);
850 return true;
851 } else {
852 return oldEnvironent.merge(typeOfThis, locals);
853 }
854 }
855
856 ClosureEnvironment getEnvironmentOrNull(FunctionElement function) {
857 return closures[function];
858 }
859
860 Iterable<FunctionElement> get functionElements => closures.keys;
861
862 bool contains(FunctionElement function) => closures.containsKey(function);
863
864 String toString() => closures.toString();
865 }
866
867 /**
868 * A work item for the type inference queue.
869 */
870 class InferenceWorkItem {
871 Element method;
872 ConcreteTypesEnvironment environment;
873 InferenceWorkItem(this.method, this.environment);
874
875 toString() => "{ method = $method, environment = $environment }";
876
877 bool operator ==(other) {
878 return (other is InferenceWorkItem)
879 && method == other.method
880 && environment == other.environment;
881 }
882
883 int get hashCode => 31 * method.hashCode + environment.hashCode;
884 }
885
886 /**
887 * A sentinel type mask class representing the dynamicType. It is absorbing
888 * for [:ConcreteTypesEnvironment.typeMaskUnion:].
889 */
890 class DynamicTypeMask implements TypeMask {
891 const DynamicTypeMask();
892
893 String toString() => 'sentinel type mask';
894
895 TypeMask nullable() {
896 throw new UnsupportedError("");
897 }
898
899 TypeMask nonNullable() {
900 throw new UnsupportedError("");
901 }
902
903 bool get isEmpty {
904 throw new UnsupportedError("");
905 }
906
907 bool get isNullable {
908 throw new UnsupportedError("");
909 }
910
911 bool get isExact {
912 throw new UnsupportedError("");
913 }
914
915 bool get isUnion {
916 throw new UnsupportedError("");
917 }
918
919 bool get isContainer {
920 throw new UnsupportedError("");
921 }
922
923 bool get isMap {
924 throw new UnsupportedError("");
925 }
926
927 bool get isDictionary {
928 throw new UnsupportedError("");
929 }
930
931 bool get isForwarding {
932 throw new UnsupportedError("");
933 }
934
935 bool get isValue {
936 throw new UnsupportedError("");
937 }
938
939 bool containsOnlyInt(ClassWorld classWorld) {
940 throw new UnsupportedError("");
941 }
942
943 bool containsOnlyDouble(ClassWorld classWorld) {
944 throw new UnsupportedError("");
945 }
946
947 bool containsOnlyNum(ClassWorld classWorld) {
948 throw new UnsupportedError("");
949 }
950
951 bool containsOnlyBool(ClassWorld classWorld) {
952 throw new UnsupportedError("");
953 }
954
955 bool containsOnlyString(ClassWorld classWorld) {
956 throw new UnsupportedError("");
957 }
958
959 bool containsOnly(ClassElement element) {
960 throw new UnsupportedError("");
961 }
962
963 bool satisfies(ClassElement cls, ClassWorld classWorld) {
964 throw new UnsupportedError("");
965 }
966
967 bool contains(ClassElement type, ClassWorld classWorld) {
968 throw new UnsupportedError("");
969 }
970
971 bool containsAll(ClassWorld classWorld) {
972 throw new UnsupportedError("");
973 }
974
975 ClassElement singleClass(ClassWorld classWorld) {
976 throw new UnsupportedError("");
977 }
978
979 TypeMask union(TypeMask other, ClassWorld classWorld) {
980 throw new UnsupportedError("");
981 }
982
983 TypeMask intersection(TypeMask other, ClassWorld classWorld) {
984 throw new UnsupportedError("");
985 }
986
987 bool canHit(Element element, Selector selector, ClassWorld classWorld) {
988 throw new UnsupportedError("");
989 }
990
991 Element locateSingleElement(Selector selector, Compiler compiler) {
992 throw new UnsupportedError("");
993 }
994
995 bool needsNoSuchMethodHandling(Selector selector, ClassWorld classWorld) {
996 throw new UnsupportedError("");
997 }
998
999 bool isInMask(TypeMask other, ClassWorld classWorld) {
1000 throw new UnsupportedError("");
1001 }
1002
1003 bool containsMask(TypeMask other, ClassWorld classWorld) {
1004 throw new UnsupportedError("");
1005 }
1006 }
1007
1008 class WorkQueue {
1009 final Queue<InferenceWorkItem> queue = new Queue<InferenceWorkItem>();
1010
1011 void add(InferenceWorkItem workItem) {
1012 if (!queue.contains(workItem)) {
1013 queue.addLast(workItem);
1014 }
1015 }
1016
1017 InferenceWorkItem remove() {
1018 return queue.removeFirst();
1019 }
1020
1021 bool get isEmpty => queue.isEmpty;
1022 }
1023
1024 /**
1025 * A task which conservatively infers a [ConcreteType] for each sub expression
1026 * of the program. The entry point is [analyzeMain].
1027 */
1028 class ConcreteTypesInferrer
1029 extends InferrerEngine<ConcreteType, ConcreteTypeSystem>
1030 implements TypesInferrer {
1031
1032 final String name = "Type inferrer";
1033
1034 /**
1035 * When true, the string literal [:"__dynamic_for_test":] is inferred to
1036 * have the unknown type.
1037 */
1038 // TODO(polux): get rid of this hack once we have a natural way of inferring
1039 // the unknown type.
1040 bool testMode = false;
1041
1042 // --- constants ---
1043
1044 /**
1045 * Constants representing builtin base types. Initialized by [initialize]
1046 * and not by the constructor because the compiler elements are not yet
1047 * populated.
1048 */
1049 BaseTypes baseTypes;
1050
1051 /** The associated type system */
1052 ConcreteTypeSystem types;
1053
1054 /**
1055 * Constant representing [:ConcreteList#[]:] where [:ConcreteList:] is the
1056 * concrete implementation of lists for the selected backend.
1057 */
1058 FunctionElement listIndex;
1059
1060 /**
1061 * Constant representing [:ConcreteList#[]=:] where [:ConcreteList:] is the
1062 * concrete implementation of lists for the selected backend.
1063 */
1064 FunctionElement listIndexSet;
1065
1066 /**
1067 * Constant representing [:ConcreteList#add:] where [:ConcreteList:] is the
1068 * concrete implementation of lists for the selected backend.
1069 */
1070 FunctionElement listAdd;
1071
1072 /**
1073 * Constant representing [:ConcreteList#removeAt:] where [:ConcreteList:] is
1074 * the concrete implementation of lists for the selected backend.
1075 */
1076 FunctionElement listRemoveAt;
1077
1078 /**
1079 * Constant representing [:ConcreteList#insert:] where [:ConcreteList:] is
1080 * the concrete implementation of lists for the selected backend.
1081 */
1082 FunctionElement listInsert;
1083
1084 /**
1085 * Constant representing [:ConcreteList#removeLast:] where [:ConcreteList:] is
1086 * the concrete implementation of lists for the selected backend.
1087 */
1088 FunctionElement listRemoveLast;
1089
1090 /** Constant representing [:List():]. */
1091 FunctionElement listConstructor;
1092
1093 /** The unknown concrete type */
1094 final ConcreteType unknownConcreteType;
1095
1096 /** The empty concrete type */
1097 ConcreteType emptyConcreteType;
1098
1099 /** The null concrete type */
1100 ConcreteType nullConcreteType;
1101
1102 // --- state updated by the inference ---
1103
1104 /**
1105 * A map from (function x argument base types) to their inferred concrete
1106 * type. Another way of seeing [methodToTemplates] is as a map from
1107 * [FunctionElement]s to "templates" in the sense of "The Cartesian Product
1108 * Algorithm - Simple and Precise Type Inference of Parametric Polymorphism"
1109 * by Ole Agesen.
1110 */
1111 // TODO(polux): build a better abstraction, like Closures
1112 final Map<FunctionElement, Map<ConcreteTypesEnvironment, ConcreteType>>
1113 methodToTemplates;
1114
1115 /** The set of encountered closures. */
1116 final Closures closures;
1117
1118 /** A map from expressions to their inferred concrete types. */
1119 final Map<Node, ConcreteType> inferredTypes;
1120
1121 /** A map from fields to their inferred concrete types. */
1122 final Map<Element, ConcreteType> inferredFieldTypes;
1123
1124 /**
1125 * [:callers[f]:] is the list of [:f:]'s possible callers or fields
1126 * whose initialization is a call to [:f:].
1127 */
1128 final Map<FunctionElement, Set<Element>> callers;
1129
1130 /**
1131 * [:readers[field]:] is the list of [:field:]'s possible readers or fields
1132 * whose initialization is a read of [:field:].
1133 */
1134 final Map<Element, Set<Element>> fieldReaders;
1135
1136 /**
1137 * [:readers[local]:] is the list of [:local:]'s possible readers.
1138 */
1139 final Map<Local, Set<FunctionElement>> capturedLocalsReaders;
1140
1141 /// The set of classes encountered so far.
1142 final Set<ClassElement> seenClasses;
1143
1144 /**
1145 * A map from selector names to callers of methods with this name on objects
1146 * of unknown inferred type.
1147 */
1148 final Map<String, Set<FunctionElement>> dynamicCallers;
1149
1150 /** The inferred type of elements stored in Lists. */
1151 ConcreteType listElementType;
1152
1153 /**
1154 * A map from parameters to their inferred concrete types. It plays no role
1155 * in the analysis, it is write only.
1156 */
1157 final Map<VariableElement, ConcreteType> inferredParameterTypes;
1158
1159 /**
1160 * A map from selectors to their inferred type masks, indexed by the mask
1161 * of the receiver. It plays no role in the analysis, it is write only.
1162 */
1163 final Map<Selector, Map<TypeMask, TypeMask>> inferredSelectorTypes;
1164
1165 /** The work queue consumed by [analyzeMain]. */
1166 final WorkQueue workQueue;
1167
1168 /** The item being worked on. */
1169 InferenceWorkItem currentWorkItem;
1170
1171 ConcreteTypesInferrer(Compiler compiler)
1172 : methodToTemplates = new Map<FunctionElement,
1173 Map<ConcreteTypesEnvironment, ConcreteType>>(),
1174 closures = new Closures(compiler),
1175 inferredTypes = new Map<Node, ConcreteType>(),
1176 inferredFieldTypes = new Map<Element, ConcreteType>(),
1177 inferredParameterTypes = new Map<VariableElement, ConcreteType>(),
1178 workQueue = new WorkQueue(),
1179 callers = new Map<FunctionElement, Set<Element>>(),
1180 fieldReaders = new Map<Element, Set<Element>>(),
1181 capturedLocalsReaders = new Map<Local, Set<FunctionElement>>(),
1182 seenClasses = new Set<ClassElement>(),
1183 dynamicCallers = new Map<String, Set<FunctionElement>>(),
1184 inferredSelectorTypes = new Map<Selector, Map<TypeMask, TypeMask>>(),
1185 unknownConcreteType = new ConcreteType.unknown(),
1186 super(compiler, null);
1187
1188 /* Initialization code that cannot be run in the constructor because it
1189 * requires the compiler's elements to be populated.
1190 */
1191 void initialize() {
1192 baseTypes = new BaseTypes(compiler);
1193 types = new ConcreteTypeSystem(this);
1194 ClassElement jsArrayClass = baseTypes.listBaseType.element;
1195 listIndex = jsArrayClass.lookupMember('[]');
1196 listIndexSet = jsArrayClass.lookupMember('[]=');
1197 listAdd = jsArrayClass.lookupMember('add');
1198 listRemoveAt = jsArrayClass.lookupMember('removeAt');
1199 listInsert = jsArrayClass.lookupMember('insert');
1200 listRemoveLast =
1201 jsArrayClass.lookupMember('removeLast');
1202 List<String> typePreservingOps = const ['+', '-', '*'];
1203 listConstructor =
1204 compiler.listClass.lookupConstructor(
1205 new Selector.callConstructor(
1206 '',
1207 compiler.listClass.library)).implementation;
1208 emptyConcreteType = new ConcreteType.empty(compiler.maxConcreteTypeSize,
1209 baseTypes);
1210 nullConcreteType = singletonConcreteType(const NullBaseType());
1211 listElementType = emptyConcreteType;
1212 }
1213
1214 // --- utility methods ---
1215
1216 /** Creates a singleton concrete type containing [baseType]. */
1217 ConcreteType singletonConcreteType(BaseType baseType) {
1218 return new ConcreteType.singleton(compiler.maxConcreteTypeSize, baseTypes,
1219 baseType);
1220 }
1221
1222 /**
1223 * Computes the union of [mask1] and [mask2] where [mask1] and [mask2] are
1224 * possibly equal to [: DynamicTypeMask.instance :].
1225 */
1226 TypeMask typeMaskUnion(TypeMask mask1, TypeMask mask2) {
1227 if (mask1 == const DynamicTypeMask() || mask2 == const DynamicTypeMask()) {
1228 return const DynamicTypeMask();
1229 }
1230 return mask1.union(mask2, compiler.world);
1231 }
1232
1233 /**
1234 * Returns all the members matching [selector].
1235 */
1236 Set<Element> getMembersBySelector(Selector selector) {
1237 // TODO(polux): memoize?
1238 Set<Element> result = new Set<Element>();
1239 for (ClassElement cls in seenClasses) {
1240 Element elem = cls.lookupSelector(selector);
1241 if (elem != null) {
1242 result.add(elem.implementation);
1243 }
1244 }
1245 return result;
1246 }
1247
1248 /**
1249 * Returns all the subtypes of [cls], [cls] included.
1250 */
1251 Set<ClassElement> getReflexiveSubtypesOf(ClassElement cls) {
1252 // TODO(polux): memoize?
1253 Set<ClassElement> result = new Set<ClassElement>()..add(cls);
1254 for (ClassElement candidate in seenClasses) {
1255 if (compiler.world.isSubtypeOf(candidate, cls)) {
1256 result.add(candidate);
1257 }
1258 }
1259 return result;
1260 }
1261
1262 /**
1263 * Sets the concrete type associated to [node] to the union of the inferred
1264 * concrete type so far and of [type].
1265 */
1266 void augmentInferredType(Node node, ConcreteType type) {
1267 ConcreteType currentType = inferredTypes[node];
1268 inferredTypes[node] =
1269 (currentType == null) ? type : currentType.union(type);
1270 }
1271
1272 /**
1273 * Sets the concrete type associated to [selector] to the union of the
1274 * inferred concrete type so far and of [returnType].
1275 *
1276 * Precondition: [:(typeOfThis != null) && (returnType != null):]
1277 */
1278 void augmentInferredSelectorType(Selector selector, TypeMask typeOfThis,
1279 TypeMask returnType) {
1280 assert(returnType != null);
1281 assert(typeOfThis != null);
1282
1283 selector = selector.asUntyped;
1284 Map<TypeMask, TypeMask> currentMap = inferredSelectorTypes.putIfAbsent(
1285 selector, () => new Map<TypeMask, TypeMask>());
1286 TypeMask currentReturnType = currentMap[typeOfThis];
1287 currentMap[typeOfThis] = (currentReturnType == null)
1288 ? returnType
1289 : typeMaskUnion(currentReturnType, returnType);
1290 }
1291
1292 /**
1293 * Returns the current inferred concrete type of [field].
1294 */
1295 ConcreteType getFieldType(Selector selector, Element field) {
1296 ensureFieldInitialized(field);
1297 ConcreteType result = inferredFieldTypes[field];
1298 result = (result == null) ? emptyConcreteType : result;
1299 if (selector != null) {
1300 Element enclosing = field.enclosingElement;
1301 if (enclosing.isClass) {
1302 ClassElement cls = enclosing;
1303 TypeMask receiverMask = new TypeMask.exact(cls.declaration, classWorld);
1304 TypeMask resultMask = types.concreteTypeToTypeMask(result);
1305 augmentInferredSelectorType(selector, receiverMask, resultMask);
1306 }
1307 }
1308 return result;
1309 }
1310
1311 /**
1312 * Sets the concrete type associated to [field] to the union of the inferred
1313 * concrete type so far and of [type].
1314 */
1315 void augmentFieldType(Element field, ConcreteType type) {
1316 ensureFieldInitialized(field);
1317 ConcreteType oldType = inferredFieldTypes[field];
1318 ConcreteType newType = (oldType != null) ? oldType.union(type) : type;
1319 if (oldType != newType) {
1320 inferredFieldTypes[field] = newType;
1321 invalidateReaders(field);
1322 }
1323 }
1324
1325 /** Augment the inferred type of elements stored in Lists. */
1326 void augmentListElementType(ConcreteType type) {
1327 ConcreteType newType = listElementType.union(type);
1328 if (newType != listElementType) {
1329 invalidateCallers(listIndex);
1330 listElementType = newType;
1331 }
1332 }
1333
1334 /**
1335 * Sets the concrete type associated to [parameter] to the union of the
1336 * inferred concrete type so far and of [type].
1337 */
1338 void augmentParameterType(VariableElement parameter, ConcreteType type) {
1339 ConcreteType oldType = inferredParameterTypes[parameter];
1340 inferredParameterTypes[parameter] =
1341 (oldType == null) ? type : oldType.union(type);
1342 }
1343
1344 /** Augments the set of classes encountered so far. */
1345 void augmentSeenClasses(ClassElement cls) {
1346 if (!seenClasses.contains(cls)) {
1347 seenClasses.add(cls);
1348 cls.forEachMember((_, Element member) {
1349 Set<FunctionElement> functions = dynamicCallers[member.name];
1350 if (functions != null) {
1351 functions.forEach(invalidate);
1352 }
1353 }, includeSuperAndInjectedMembers: true);
1354 }
1355 }
1356
1357 /**
1358 * Add [caller] to the set of [callee]'s callers.
1359 */
1360 void addCaller(FunctionElement callee, Element caller) {
1361 callers.putIfAbsent(callee, () => new Set<Element>())
1362 .add(caller);
1363 }
1364
1365 /**
1366 * Add [caller] to the set of [callee]'s dynamic callers.
1367 */
1368 void addDynamicCaller(Selector callee, FunctionElement caller) {
1369 dynamicCallers
1370 .putIfAbsent(callee.name, () => new Set<FunctionElement>())
1371 .add(caller);
1372 }
1373
1374 /**
1375 * Add [reader] to the set of [field]'s readers.
1376 */
1377 void addFieldReader(Element field, Element reader) {
1378 fieldReaders.putIfAbsent(field, () => new Set<Element>())
1379 .add(reader);
1380 }
1381
1382 /**
1383 * Add [reader] to the set of [local]'s readers.
1384 */
1385 void addCapturedLocalReader(Local local, FunctionElement reader) {
1386 capturedLocalsReaders.putIfAbsent(local, () => new Set<FunctionElement>())
1387 .add(reader);
1388 }
1389
1390 /**
1391 * Add a closure to the set of seen closures. Invalidate callers if
1392 * the set of locals has changed.
1393 */
1394 void addClosure(FunctionElement closure,
1395 ConcreteType typeOfThis,
1396 LocalsHandler locals) {
1397 if (closures.put(closure, typeOfThis, locals)) {
1398 invalidateCallers(closure);
1399 }
1400 }
1401
1402 /**
1403 * Invalidate all callers of [function].
1404 */
1405 void invalidateCallers(FunctionElement function) {
1406 Set<Element> methodCallers = callers[function];
1407 if (methodCallers != null) {
1408 methodCallers.forEach(invalidate);
1409 }
1410 }
1411
1412 /**
1413 * Invalidate all reader of [field].
1414 */
1415 void invalidateReaders(Element field) {
1416 Set<Element> readers = fieldReaders[field];
1417 if (readers != null) {
1418 readers.forEach(invalidate);
1419 }
1420 }
1421
1422 /**
1423 * Add all templates of [methodOrField] to the workqueue.
1424 */
1425 void invalidate(Element methodOrField) {
1426 if (methodOrField.isField) {
1427 workQueue.add(new InferenceWorkItem(
1428 methodOrField, new ConcreteTypesEnvironment()));
1429 } else {
1430 Map<ConcreteTypesEnvironment, ConcreteType> templates =
1431 methodToTemplates[methodOrField];
1432 if (templates != null) {
1433 templates.forEach((environment, _) {
1434 workQueue.add(
1435 new InferenceWorkItem(methodOrField, environment));
1436 });
1437 }
1438 }
1439 }
1440
1441 /**
1442 * Returns the template associated to [function] or create an empty template
1443 * for [function] return it.
1444 */
1445 // TODO(polux): encapsulate this in an abstraction for templates
1446 Map<ConcreteTypesEnvironment, ConcreteType>
1447 getTemplatesOrEmpty(FunctionElement function) {
1448 return methodToTemplates.putIfAbsent(
1449 function,
1450 () => new Map<ConcreteTypesEnvironment, ConcreteType>());
1451 }
1452
1453 // -- methods of types.TypesInferrer (interface with the backend) --
1454
1455 /** Get the inferred concrete type of [node]. */
1456 @override
1457 TypeMask getTypeOfNode(Element owner, Node node) {
1458 TypeMask result = types.concreteTypeToTypeMask(inferredTypes[node]);
1459 return (result == const DynamicTypeMask()) ? null : result;
1460 }
1461
1462 /** Get the inferred concrete type of [element]. */
1463 @override
1464 TypeMask getTypeOfElement(Element element) {
1465 final result = types.concreteTypeToTypeMask(typeOfElement(element));
1466 return (result == const DynamicTypeMask()) ? null : result;
1467 }
1468
1469 /**
1470 * Get the inferred concrete return type of [element]. A null return value
1471 * means "I don't know".
1472 */
1473 @override
1474 TypeMask getReturnTypeOfElement(Element element) {
1475 assert(element is FunctionElement);
1476 Map<ConcreteTypesEnvironment, ConcreteType> templates =
1477 methodToTemplates[element];
1478 if (templates == null) return null;
1479 ConcreteType returnType = emptyConcreteType;
1480 templates.forEach((_, concreteType) {
1481 returnType = returnType.union(concreteType);
1482 });
1483 TypeMask result = types.concreteTypeToTypeMask(returnType);
1484 return (result == const DynamicTypeMask()) ? null : result;
1485 }
1486
1487 /**
1488 * Get the inferred concrete type of [selector]. A null return value means
1489 * "I don't know".
1490 */
1491 @override
1492 TypeMask getTypeOfSelector(Selector selector) {
1493 Map<TypeMask, TypeMask> candidates =
1494 inferredSelectorTypes[selector.asUntyped];
1495 if (candidates == null) {
1496 return null;
1497 }
1498 TypeMask result = new TypeMask.nonNullEmpty();
1499 if (selector.mask == null) {
1500 candidates.forEach((TypeMask receiverType, TypeMask returnType) {
1501 result = typeMaskUnion(result, returnType);
1502 });
1503 } else {
1504 candidates.forEach((TypeMask receiverType, TypeMask returnType) {
1505 TypeMask intersection =
1506 receiverType.intersection(selector.mask, compiler.world);
1507 if (!intersection.isEmpty || intersection.isNullable) {
1508 result = typeMaskUnion(result, returnType);
1509 }
1510 });
1511 }
1512 return result == const DynamicTypeMask() ? null : result;
1513 }
1514
1515 @override
1516 void clear() {
1517 throw new UnsupportedError("clearing is not yet implemented");
1518 }
1519
1520 @override
1521 bool isCalledOnce(Element element) {
1522 // Never called by SimpleTypeInferrer.
1523 throw new UnsupportedError("");
1524 }
1525
1526 @override
1527 bool isFixedArrayCheckedForGrowable(Node node) {
1528 // Never called by SimpleTypeInferrer.
1529 throw new UnsupportedError("");
1530 }
1531
1532 // --- analysis ---
1533
1534 /**
1535 * Returns the concrete type returned by [function] given arguments of
1536 * concrete types [argumentsTypes]. If [function] is static then
1537 * [receiverType] must be null, else [function] must be a member of
1538 * [receiverType].
1539 */
1540 ConcreteType getSendReturnType(Selector selector,
1541 FunctionElement function,
1542 ClassElement receiverType,
1543 ArgumentsTypes<ConcreteType> argumentsTypes) {
1544 assert(function != null);
1545
1546 ConcreteType result = emptyConcreteType;
1547 Map<Element, ConcreteType> argumentMap =
1548 associateArguments(function, argumentsTypes);
1549 // if the association failed, this send will never occur or will fail
1550 if (argumentMap == null) {
1551 return emptyConcreteType;
1552 }
1553
1554 argumentMap.forEach(augmentParameterType);
1555 ConcreteTypeCartesianProduct product =
1556 new ConcreteTypeCartesianProduct(this, receiverType, argumentMap);
1557 for (ConcreteTypesEnvironment environment in product) {
1558 result = result.union(
1559 getMonomorphicSendReturnType(function, environment));
1560 }
1561
1562 if (selector != null && receiverType != null) {
1563 // TODO(polux): generalize to any abstract class if we ever handle other
1564 // abstract classes than num.
1565 TypeMask receiverMask =
1566 (receiverType == compiler.backend.numImplementation
1567 || receiverType == compiler.backend.intImplementation)
1568 ? new TypeMask.nonNullSubclass(receiverType.declaration,
1569 compiler.world)
1570 : new TypeMask.nonNullExact(receiverType.declaration,
1571 compiler.world);
1572 TypeMask resultMask = types.concreteTypeToTypeMask(result);
1573 augmentInferredSelectorType(selector, receiverMask, resultMask);
1574 }
1575
1576 return result;
1577 }
1578
1579 /**
1580 * Given a method signature and a list of concrete types, builds a map from
1581 * formals to their corresponding concrete types. Returns null if the
1582 * association is impossible (for instance: too many arguments).
1583 */
1584 Map<Element, ConcreteType> associateArguments(
1585 FunctionElement function,
1586 ArgumentsTypes<ConcreteType> argumentsTypes) {
1587 final Map<Element, ConcreteType> result = new Map<Element, ConcreteType>();
1588 final FunctionSignature signature = function.functionSignature;
1589
1590 // guard 1: too many arguments
1591 if (argumentsTypes.length > signature.parameterCount) {
1592 return null;
1593 }
1594 // guard 2: not enough arguments
1595 if (argumentsTypes.positional.length < signature.requiredParameterCount) {
1596 return null;
1597 }
1598 // guard 3: too many positional arguments
1599 if (signature.optionalParametersAreNamed &&
1600 argumentsTypes.positional.length > signature.requiredParameterCount) {
1601 return null;
1602 }
1603
1604 handleLeftoverOptionalParameter(ParameterElement parameter) {
1605 Expression initializer = parameter.initializer;
1606 result[parameter] = (initializer == null)
1607 ? nullConcreteType
1608 : analyzeDefaultValue(function, initializer);
1609 }
1610
1611 final Iterator<ConcreteType> remainingPositionalArguments =
1612 argumentsTypes.positional.iterator;
1613 // we attach each positional parameter to its corresponding positional
1614 // argument
1615 for (Link<Element> requiredParameters = signature.requiredParameters;
1616 !requiredParameters.isEmpty;
1617 requiredParameters = requiredParameters.tail) {
1618 final Element requiredParameter = requiredParameters.head;
1619 // we know moveNext() succeeds because of guard 2
1620 remainingPositionalArguments.moveNext();
1621 result[requiredParameter] = remainingPositionalArguments.current;
1622 }
1623 if (signature.optionalParametersAreNamed) {
1624 // we build a map out of the remaining named parameters
1625 Link<Element> remainingOptionalParameters = signature.optionalParameters;
1626 final Map<String, Element> leftOverNamedParameters =
1627 new Map<String, Element>();
1628 for (;
1629 !remainingOptionalParameters.isEmpty;
1630 remainingOptionalParameters = remainingOptionalParameters.tail) {
1631 final Element namedParameter = remainingOptionalParameters.head;
1632 leftOverNamedParameters[namedParameter.name] = namedParameter;
1633 }
1634 // we attach the named arguments to their corresponding optional
1635 // parameters
1636 for (String source in argumentsTypes.named.keys) {
1637 final ConcreteType concreteType = argumentsTypes.named[source];
1638 final Element namedParameter = leftOverNamedParameters[source];
1639 // unexisting or already used named parameter
1640 if (namedParameter == null) return null;
1641 result[namedParameter] = concreteType;
1642 leftOverNamedParameters.remove(source);
1643 }
1644 leftOverNamedParameters.forEach((_, Element parameter) {
1645 handleLeftoverOptionalParameter(parameter);
1646 });
1647 } else { // optional parameters are positional
1648 // we attach the remaining positional arguments to their corresponding
1649 // optional parameters
1650 Link<Element> remainingOptionalParameters = signature.optionalParameters;
1651 while (remainingPositionalArguments.moveNext()) {
1652 final Element optionalParameter = remainingOptionalParameters.head;
1653 result[optionalParameter] = remainingPositionalArguments.current;
1654 // we know tail is defined because of guard 1
1655 remainingOptionalParameters = remainingOptionalParameters.tail;
1656 }
1657 for (;
1658 !remainingOptionalParameters.isEmpty;
1659 remainingOptionalParameters = remainingOptionalParameters.tail) {
1660 handleLeftoverOptionalParameter(remainingOptionalParameters.head);
1661 }
1662 }
1663 return result;
1664 }
1665
1666 ConcreteType getMonomorphicSendReturnType(
1667 FunctionElement function,
1668 ConcreteTypesEnvironment environment) {
1669 Map<ConcreteTypesEnvironment, ConcreteType> template =
1670 getTemplatesOrEmpty(function);
1671 ConcreteType type = template[environment];
1672 ConcreteType specialType = getSpecialCaseReturnType(function, environment);
1673 if (type != null) {
1674 return specialType != null ? specialType : type;
1675 } else {
1676 workQueue.add(new InferenceWorkItem(function, environment));
1677 return specialType != null ? specialType : emptyConcreteType;
1678 }
1679 }
1680
1681 /**
1682 * Handles external methods that cannot be cached because they depend on some
1683 * other state of [ConcreteTypesInferrer] like [:List#[]:] and
1684 * [:List#[]=:]. Returns null if [function] and [environment] don't form a
1685 * special case
1686 */
1687 ConcreteType getSpecialCaseReturnType(FunctionElement function,
1688 ConcreteTypesEnvironment environment) {
1689 // Handles int + int, double + double, int - int, ...
1690 // We cannot compare function to int#+, int#-, etc. because int and double
1691 // don't override these methods. So for 1+2, getSpecialCaseReturnType will
1692 // be invoked with function = num#+. We use environment.typeOfThis instead.
1693 ClassElement cls = environment.classOfThis;
1694 if (cls != null) {
1695 String name = function.name;
1696 if ((cls == baseTypes.intBaseType.element
1697 || cls == baseTypes.doubleBaseType.element)
1698 && (name == '+' || name == '-' || name == '*')) {
1699 Link<Element> parameters =
1700 function.functionSignature.requiredParameters;
1701 ConcreteType argumentType = environment.lookupType(parameters.head);
1702 if (argumentType.getUniqueType() == cls) {
1703 return singletonConcreteType(new ClassBaseType(cls));
1704 }
1705 }
1706 }
1707
1708 if (function == listIndex || function == listRemoveAt) {
1709 Link<Element> parameters = function.functionSignature.requiredParameters;
1710 ConcreteType indexType = environment.lookupType(parameters.head);
1711 if (!indexType.baseTypes.contains(baseTypes.intBaseType)) {
1712 return emptyConcreteType;
1713 }
1714 return listElementType;
1715 } else if (function == listIndexSet || function == listInsert) {
1716 Link<Element> parameters = function.functionSignature.requiredParameters;
1717 ConcreteType indexType = environment.lookupType(parameters.head);
1718 if (!indexType.baseTypes.contains(baseTypes.intBaseType)) {
1719 return emptyConcreteType;
1720 }
1721 ConcreteType elementType = environment.lookupType(parameters.tail.head);
1722 augmentListElementType(elementType);
1723 return emptyConcreteType;
1724 } else if (function == listAdd) {
1725 Link<Element> parameters = function.functionSignature.requiredParameters;
1726 ConcreteType elementType = environment.lookupType(parameters.head);
1727 augmentListElementType(elementType);
1728 return emptyConcreteType;
1729 } else if (function == listRemoveLast) {
1730 return listElementType;
1731 }
1732 return null;
1733 }
1734
1735 ConcreteType analyzeMethodOrClosure(Element element,
1736 ConcreteTypesEnvironment environment) {
1737 ConcreteType specialResult = handleSpecialMethod(element, environment);
1738 if (specialResult != null) return specialResult;
1739 ClosureEnvironment closureEnv = closures.getEnvironmentOrNull(element);
1740 return (closureEnv == null)
1741 ? analyzeMethod(element, environment)
1742 : analyzeClosure(element, closureEnv, environment);
1743 }
1744
1745 ConcreteType analyzeMethod(Element element,
1746 ConcreteTypesEnvironment environment) {
1747 TypeInferrerVisitor visitor = new TypeInferrerVisitor(
1748 element,
1749 this,
1750 singletonConcreteType(new ClassBaseType(environment.classOfThis)),
1751 environment.environment);
1752 visitor.run();
1753 return visitor.returnType;
1754 }
1755
1756 ConcreteType analyzeClosure(Element element,
1757 ClosureEnvironment closureEnv,
1758 ConcreteTypesEnvironment environment) {
1759 assert(environment.classOfThis == null);
1760 LocalsHandler locals = (closureEnv.locals != null)
1761 ? new LocalsHandler.deepCopyOf(closureEnv.locals)
1762 : null;
1763 TypeInferrerVisitor visitor = new TypeInferrerVisitor(element, this,
1764 closureEnv.thisType, environment.environment, locals);
1765 visitor.run();
1766 return visitor.returnType;
1767 }
1768
1769 /**
1770 * Analyze the initializer of a field if it has not yet been done and update
1771 * [inferredFieldTypes] accordingly. Invalidate the readers of the field if
1772 * needed.
1773 */
1774 void ensureFieldInitialized(Element field) {
1775 // This is test is needed for fitering out BoxFieldElements.
1776 if (field is FieldElement && inferredFieldTypes[field] == null) {
1777 analyzeFieldInitialization(field);
1778 }
1779 }
1780
1781 /**
1782 * Analyze the initializer of a field and update [inferredFieldTypes]
1783 * accordingly. Invalidate the readers of the field if needed.
1784 */
1785 ConcreteType analyzeFieldInitialization(VariableElement field) {
1786 Visitor visitor = new TypeInferrerVisitor(field, this, null, new Map());
1787 ConcreteType type;
1788 if (field.initializer != null) {
1789 type = field.initializer.accept(visitor);
1790 inferredFieldTypes[field] = type;
1791 invalidateReaders(field);
1792 }
1793 return type;
1794 }
1795
1796 /**
1797 * Analyze a default value.
1798 */
1799 ConcreteType analyzeDefaultValue(Element function, Node expression) {
1800 assert((function != null) && (expression != null));
1801 Visitor visitor = new TypeInferrerVisitor(function, this, null, {});
1802 return expression.accept(visitor);
1803 }
1804
1805 /**
1806 * Hook that performs side effects on some special method calls (like
1807 * [:List(length):]) and possibly returns a concrete type.
1808 */
1809 ConcreteType handleSpecialMethod(FunctionElement element,
1810 ConcreteTypesEnvironment environment) {
1811 // We trust the return type of native elements
1812 if (isNativeElement(element)) {
1813 var elementType = element.type;
1814 assert(elementType.isFunctionType);
1815 return typeOfNativeBehavior(
1816 native.NativeBehavior.ofMethod(element, compiler));
1817 }
1818 // When List([length]) is called with some length, we must augment
1819 // listElementType with {null}.
1820 if (element == listConstructor) {
1821 Link<Element> parameters =
1822 listConstructor.functionSignature.optionalParameters;
1823 ConcreteType lengthType = environment.lookupType(parameters.head);
1824 if (lengthType.baseTypes.contains(baseTypes.intBaseType)) {
1825 augmentListElementType(nullConcreteType);
1826 }
1827 }
1828 return null;
1829 }
1830
1831 /**
1832 * Performs concrete type inference of the code reachable from [element].
1833 */
1834 @override
1835 bool analyzeMain(Element element) {
1836 initialize();
1837 workQueue.add(
1838 new InferenceWorkItem(element, new ConcreteTypesEnvironment()));
1839 while (!workQueue.isEmpty) {
1840 currentWorkItem = workQueue.remove();
1841 if (currentWorkItem.method.isField) {
1842 analyzeFieldInitialization(currentWorkItem.method);
1843 } else {
1844 Map<ConcreteTypesEnvironment, ConcreteType> template =
1845 getTemplatesOrEmpty(currentWorkItem.method);
1846 template.putIfAbsent(
1847 currentWorkItem.environment, () => emptyConcreteType);
1848 recordReturnType(
1849 currentWorkItem.method,
1850 analyzeMethodOrClosure(currentWorkItem.method,
1851 currentWorkItem.environment));
1852 }
1853 }
1854 return true;
1855 }
1856
1857 /**
1858 * Dumps debugging information on the standard output.
1859 */
1860 void debug() {
1861 print("queue:");
1862 for (InferenceWorkItem workItem in workQueue.queue) {
1863 print(" $workItem");
1864 }
1865 print("seen classes:");
1866 for (ClassElement cls in seenClasses) {
1867 print(" ${cls.name}");
1868 }
1869 print("callers:");
1870 callers.forEach((k,v) {
1871 print(" $k: $v");
1872 });
1873 print("dynamic callers:");
1874 dynamicCallers.forEach((k,v) {
1875 print(" $k: $v");
1876 });
1877 print("readers:");
1878 fieldReaders.forEach((k,v) {
1879 print(" $k: $v");
1880 });
1881 print("readers of captured locals:");
1882 capturedLocalsReaders.forEach((k,v) {
1883 print(" $k: $v");
1884 });
1885 print("inferredFieldTypes:");
1886 inferredFieldTypes.forEach((k,v) {
1887 print(" $k: $v");
1888 });
1889 print("listElementType:");
1890 print(" $listElementType");
1891 print("inferredParameterTypes:");
1892 inferredParameterTypes.forEach((k,v) {
1893 print(" $k: $v");
1894 });
1895 print("inferred selector types:");
1896 inferredSelectorTypes.forEach((selector, map) {
1897 print(" $selector:");
1898 map.forEach((k, v) {
1899 print(" $k: $v");
1900 });
1901 });
1902 print("cache:");
1903 methodToTemplates.forEach((k,v) {
1904 print(" $k: $v");
1905 });
1906 print("closures:");
1907 closures.closures.forEach((k, ClosureEnvironment v) {
1908 print(" $k");
1909 print(" this: ${v.thisType}");
1910 if (v.locals != null) {
1911 v.locals.locals.forEachLocal((local, type) {
1912 print(" $local: $type");
1913 });
1914 }
1915 });
1916 print("inferred expression types:");
1917 inferredTypes.forEach((k,v) {
1918 print(" $k: $v");
1919 });
1920 }
1921
1922 @override
1923 ConcreteType addReturnTypeFor(Element analyzedElement,
1924 ConcreteType currentType,
1925 ConcreteType newType) {
1926 return (currentType == null) ? newType : currentType.union(newType);
1927 }
1928
1929 @override
1930 void forEachElementMatching(Selector selector, bool f(Element element)) {
1931 getMembersBySelector(selector).forEach(f);
1932 }
1933
1934 @override
1935 void recordReturnType(Element element, ConcreteType type) {
1936 assert((type != null) && (element == currentWorkItem.method));
1937 Map<ConcreteTypesEnvironment, ConcreteType> template =
1938 getTemplatesOrEmpty(element);
1939 if (template[currentWorkItem.environment] != type) {
1940 template[currentWorkItem.environment] = type;
1941 invalidateCallers(element);
1942 }
1943 }
1944
1945 @override
1946 void recordType(Element element, ConcreteType type) {
1947 assert(element is FieldElement);
1948 augmentFieldType(element, type);
1949 }
1950
1951 @override
1952 void recordTypeOfFinalField(Node node,
1953 Element nodeHolder,
1954 Element field,
1955 ConcreteType type) {
1956 augmentFieldType(field, type);
1957 }
1958
1959 @override
1960 void recordTypeOfNonFinalField(Spannable node, Element field,
1961 ConcreteType type) {
1962 augmentFieldType(field, type);
1963 }
1964
1965 @override
1966 void recordCapturedLocalRead(Local local) {
1967 addCapturedLocalReader(local, currentWorkItem.method);
1968 }
1969
1970 @override
1971 void recordLocalUpdate(Local local, ConcreteType type) {
1972 Set<FunctionElement> localReaders = capturedLocalsReaders[local];
1973 if (localReaders != null) {
1974 localReaders.forEach(invalidate);
1975 }
1976 }
1977
1978 /**
1979 * Returns the caller of the current analyzed element, given the alleged
1980 * caller provided by SimpleTypeInferrer.
1981 *
1982 * SimpleTypeInferrer lies about the caller when it's a closure.
1983 * Unfortunately we cannot always trust currentWorkItem.method either because
1984 * it is wrong for fields initializers.
1985 */
1986 Element getRealCaller(Element allegedCaller) {
1987 Element currentMethod = currentWorkItem.method;
1988 if ((currentMethod != allegedCaller)
1989 && currentMethod.isFunction
1990 && closures.contains(currentMethod)) {
1991 return currentMethod;
1992 } else {
1993 return allegedCaller;
1994 }
1995 }
1996
1997 @override
1998 ConcreteType registerCalledElement(Spannable node,
1999 Selector selector,
2000 Element caller,
2001 Element callee,
2002 ArgumentsTypes<ConcreteType> arguments,
2003 SideEffects sideEffects,
2004 bool inLoop) {
2005 caller = getRealCaller(caller);
2006 if ((selector == null) || (selector.kind == SelectorKind.CALL)) {
2007 callee = callee.implementation;
2008 if (selector != null && selector.name == 'JS') {
2009 return null;
2010 }
2011 if (callee.isField) { // toplevel closure call
2012 getFieldType(selector, callee); // trigger toplevel field analysis
2013 addFieldReader(callee, caller);
2014 ConcreteType result = emptyConcreteType;
2015 for (FunctionElement function in closures.functionElements) {
2016 addCaller(function, caller);
2017 result = result.union(
2018 getSendReturnType(selector, function, null, arguments));
2019 }
2020 return result;
2021 } else { // method or constructor call
2022 addCaller(callee, caller);
2023 ClassElement receiverClass = null;
2024 if (callee.isGenerativeConstructor) {
2025 receiverClass = callee.enclosingClass;
2026 } else if (node is Send) {
2027 Send send = node;
2028 if (send.receiver != null) {
2029 if (send.receiver.isSuper()) {
2030 receiverClass =
2031 currentWorkItem.environment.classOfThis.superclass;
2032 } else {
2033 receiverClass = currentWorkItem.environment.classOfThis;
2034 }
2035 }
2036 }
2037 return getSendReturnType(selector, callee, receiverClass, arguments);
2038 }
2039 } else if (selector.kind == SelectorKind.GETTER) {
2040 if (callee.isField) {
2041 addFieldReader(callee, caller);
2042 return getFieldType(selector, callee);
2043 } else if (callee.isGetter) {
2044 Element enclosing = callee.enclosingElement.isCompilationUnit
2045 ? null : callee.enclosingElement;
2046 addCaller(callee, caller);
2047 ArgumentsTypes noArguments = new ArgumentsTypes([], new Map());
2048 return getSendReturnType(selector, callee, enclosing, noArguments);
2049 } else if (callee.isFunction) {
2050 addClosure(callee, null, null);
2051 return singletonConcreteType(baseTypes.functionBaseType);
2052 }
2053 } else if (selector.kind == SelectorKind.SETTER) {
2054 ConcreteType argumentType = arguments.positional.first;
2055 if (callee.isField) {
2056 augmentFieldType(callee, argumentType);
2057 } else if (callee.isSetter) {
2058 FunctionElement setter = callee;
2059 // TODO(polux): A setter always returns void so there's no need to
2060 // invalidate its callers even if it is called with new arguments.
2061 // However, if we start to record more than returned types, like
2062 // exceptions for instance, we need to do it by uncommenting the
2063 // following line.
2064 // inferrer.addCaller(setter, currentMethod);
2065 Element enclosing = callee.enclosingElement.isCompilationUnit
2066 ? null : callee.enclosingElement;
2067 return getSendReturnType(selector, setter, enclosing,
2068 new ArgumentsTypes([argumentType], new Map()));
2069 }
2070 } else {
2071 throw new ArgumentError("unexpected selector kind");
2072 }
2073 return null;
2074 }
2075
2076 @override
2077 ConcreteType registerCalledSelector(Node node,
2078 Selector selector,
2079 ConcreteType receiverType,
2080 Element caller,
2081 ArgumentsTypes<ConcreteType> arguments,
2082 SideEffects sideEffects,
2083 bool inLoop) {
2084 caller = getRealCaller(caller);
2085 switch (selector.kind) {
2086 case SelectorKind.GETTER:
2087 return registerDynamicGetterSend(selector, receiverType, caller);
2088 case SelectorKind.SETTER:
2089 return registerDynamicSetterSend(
2090 selector, receiverType, caller, arguments);
2091 default:
2092 return registerDynamicSend(selector, receiverType, caller, arguments);
2093 }
2094 }
2095
2096 ConcreteType registerDynamicGetterSend(Selector selector,
2097 ConcreteType receiverType,
2098 Element caller) {
2099 caller = getRealCaller(caller);
2100 ConcreteType result = emptyConcreteType;
2101
2102 void augmentResult(ClassElement baseReceiverType, Element member) {
2103 if (member.isField) {
2104 addFieldReader(member, caller);
2105 result = result.union(getFieldType(selector, member));
2106 } else if (member.isGetter) {
2107 addCaller(member, caller);
2108 ArgumentsTypes noArguments = new ArgumentsTypes([], new Map());
2109 result = result.union(
2110 getSendReturnType(selector, member, baseReceiverType, noArguments));
2111 } else if (member.isFunction) {
2112 addClosure(member, receiverType, null);
2113 result = result.union(
2114 singletonConcreteType(baseTypes.functionBaseType));
2115 } else {
2116 throw new ArgumentError("unexpected element type");
2117 }
2118 }
2119
2120 if (receiverType.isUnknown()) {
2121 addDynamicCaller(selector, caller);
2122 Set<Element> members = getMembersBySelector(selector);
2123 for (Element member in members) {
2124 if (!(member.isField || member.isGetter)) continue;
2125 for (ClassElement cls in
2126 getReflexiveSubtypesOf(member.enclosingElement)) {
2127 augmentResult(cls, member);
2128 }
2129 }
2130 } else {
2131 for (BaseType baseReceiverType in receiverType.baseTypes) {
2132 if (!baseReceiverType.isNull()) {
2133 ClassBaseType classBaseType = baseReceiverType;
2134 ClassElement cls = classBaseType.element;
2135 Element getterOrField = cls.lookupSelector(selector);
2136 if (getterOrField != null) {
2137 augmentResult(cls, getterOrField.implementation);
2138 }
2139 }
2140 }
2141 }
2142 return result;
2143 }
2144
2145 ConcreteType registerDynamicSetterSend(
2146 Selector selector,
2147 ConcreteType receiverType,
2148 Element caller,
2149 ArgumentsTypes<ConcreteType> arguments) {
2150 caller = getRealCaller(caller);
2151 ConcreteType argumentType = arguments.positional.first;
2152
2153 void augmentField(ClassElement receiverType, Element setterOrField) {
2154 if (setterOrField.isField) {
2155 augmentFieldType(setterOrField, argumentType);
2156 } else if (setterOrField.isSetter) {
2157 // A setter always returns void so there's no need to invalidate its
2158 // callers even if it is called with new arguments. However, if we
2159 // start to record more than returned types, like exceptions for
2160 // instance, we need to do it by uncommenting the following line.
2161 // inferrer.addCaller(setter, currentMethod);
2162 getSendReturnType(selector, setterOrField, receiverType,
2163 new ArgumentsTypes([argumentType], new Map()));
2164 } else {
2165 throw new ArgumentError("unexpected element type");
2166 }
2167 }
2168
2169 if (receiverType.isUnknown()) {
2170 // Same remark as above
2171 // addDynamicCaller(selector, caller);
2172 for (Element member in getMembersBySelector(selector)) {
2173 if (!(member.isField || member.isSetter)) continue;
2174 Element cls = member.enclosingClass;
2175 augmentField(cls, member);
2176 }
2177 } else {
2178 for (BaseType baseReceiverType in receiverType.baseTypes) {
2179 if (!baseReceiverType.isNull()) {
2180 ClassBaseType classBaseType = baseReceiverType;
2181 ClassElement cls = classBaseType.element;
2182 Element setterOrField = cls.lookupSelector(selector);
2183 if (setterOrField != null) {
2184 augmentField(cls, setterOrField.implementation);
2185 }
2186 }
2187 }
2188 }
2189 return argumentType;
2190 }
2191
2192 ConcreteType registerDynamicSend(Selector selector,
2193 ConcreteType receiverType,
2194 Element caller,
2195 ArgumentsTypes<ConcreteType> arguments) {
2196 caller = getRealCaller(caller);
2197 ConcreteType result = emptyConcreteType;
2198 if (receiverType.isUnknown()) {
2199 addDynamicCaller(selector, caller);
2200 Set<Element> elements = getMembersBySelector(selector);
2201 for (Element element in elements) {
2202 if (element.isFunction) {
2203 FunctionElement method = element;
2204 addCaller(method, caller);
2205 for (ClassElement cls in
2206 getReflexiveSubtypesOf(method.enclosingElement)) {
2207 result = result.union(
2208 getSendReturnType(selector, method, cls, arguments));
2209 }
2210 } else { // closure call
2211 assert(element.isField);
2212 for (FunctionElement function in closures.functionElements) {
2213 addCaller(function, caller);
2214 result = result.union(
2215 getSendReturnType(selector, function, null, arguments));
2216 }
2217 }
2218 }
2219 } else {
2220 for (BaseType baseReceiverType in receiverType.baseTypes) {
2221 if (!baseReceiverType.isNull()) {
2222 ClassBaseType classBaseReceiverType = baseReceiverType;
2223 ClassElement cls = classBaseReceiverType.element;
2224 Element method = cls.lookupSelector(selector);
2225 if (method != null) {
2226 if (method.isFunction) {
2227 assert(method is FunctionElement);
2228 method = method.implementation;
2229 addCaller(method, caller);
2230 result = result.union(
2231 getSendReturnType(selector, method, cls, arguments));
2232 } else { // closure call
2233 for (FunctionElement function in closures.functionElements) {
2234 addCaller(function, caller);
2235 result = result.union(
2236 getSendReturnType(selector, function, null, arguments));
2237 }
2238 }
2239 }
2240 }
2241 }
2242 }
2243 return result;
2244 }
2245
2246 @override
2247 void setDefaultTypeOfParameter(ParameterElement parameter,
2248 ConcreteType type) {
2249 // We handle default parameters our own way in associateArguments
2250 }
2251
2252 /**
2253 * TODO(johnniwinther): Remove once synthetic parameters get their own default
2254 * values.
2255 */
2256 bool hasAlreadyComputedTypeOfParameterDefault(Element parameter) => false;
2257
2258 @override
2259 ConcreteType registerCalledClosure(Node node,
2260 Selector selector,
2261 ConcreteType closure,
2262 Element caller,
2263 ArgumentsTypes<ConcreteType> arguments,
2264 SideEffects sideEffects,
2265 bool inLoop) {
2266 caller = getRealCaller(caller);
2267 ConcreteType result = emptyConcreteType;
2268 for (FunctionElement function in closures.functionElements) {
2269 addCaller(function, caller);
2270 result = result.union(
2271 getSendReturnType(selector, function, null, arguments));
2272 }
2273 return result;
2274 }
2275
2276 @override
2277 ConcreteType returnTypeOfElement(Element element) {
2278 // Never called by SimpleTypeInferrer.
2279 throw new UnsupportedError("");
2280 }
2281
2282 @override
2283 ConcreteType typeOfElement(Element element) {
2284 if (currentWorkItem != null) {
2285 final result = currentWorkItem.environment.lookupType(element);
2286 if (result != null) return result;
2287 }
2288 if (element.isParameter || element.isInitializingFormal) {
2289 return inferredParameterTypes[element];
2290 } else if (element.isField) {
2291 return inferredFieldTypes[element];
2292 }
2293 throw new ArgumentError("unexpected element type");
2294 }
2295
2296 @override
2297 void analyze(Element element, ArgumentsTypes arguments) {
2298 FunctionElement function = element;
2299 getSendReturnType(
2300 null, function, currentWorkItem.environment.classOfThis, arguments);
2301 }
2302 }
2303
2304 class TypeInferrerVisitor extends SimpleTypeInferrerVisitor<ConcreteType> {
2305 final ConcreteType thisType;
2306 ConcreteTypesInferrer get inferrer => super.inferrer;
2307
2308 TypeInferrerVisitor(Element element,
2309 ConcreteTypesInferrer inferrer,
2310 this.thisType,
2311 Map<Element, ConcreteType> environment,
2312 [LocalsHandler<ConcreteType> handler])
2313 : super(element, inferrer.compiler, inferrer, handler);
2314
2315 @override
2316 ConcreteType visitFunctionExpression(FunctionExpression node) {
2317 Element element = elements[node];
2318 // visitFunctionExpression should be only called for closures
2319 assert(element != analyzedElement);
2320 inferrer.addClosure(
2321 element, thisType, new LocalsHandler.deepCopyOf(locals));
2322 return types.functionType;
2323 }
2324
2325 @override
2326 ConcreteType visitLiteralString(LiteralString node) {
2327 // TODO(polux): get rid of this hack once we have a natural way of inferring
2328 // the unknown type.
2329 if (inferrer.testMode
2330 && (node.dartString.slowToString() == "__dynamic_for_test")) {
2331 return inferrer.unknownConcreteType;
2332 }
2333 return super.visitLiteralString(node);
2334 }
2335
2336 /**
2337 * Same as super.visitLiteralList except it doesn't cache anything.
2338 */
2339 @override
2340 ConcreteType visitLiteralList(LiteralList node) {
2341 ConcreteType elementType;
2342 int length = 0;
2343 for (Node element in node.elements.nodes) {
2344 ConcreteType type = visit(element);
2345 elementType = elementType == null
2346 ? types.allocatePhi(null, null, type)
2347 : types.addPhiInput(null, elementType, type);
2348 length++;
2349 }
2350 elementType = elementType == null
2351 ? types.nonNullEmpty()
2352 : types.simplifyPhi(null, null, elementType);
2353 ConcreteType containerType = node.isConst
2354 ? types.constListType
2355 : types.growableListType;
2356 return types.allocateList(
2357 containerType,
2358 node,
2359 outermostElement,
2360 elementType,
2361 length);
2362 }
2363
2364 /**
2365 * Same as super.visitGetterSend except it records the type of nodes in test
2366 * mode.
2367 */
2368 @override
2369 ConcreteType visitGetterSend(Send node) {
2370 if (inferrer.testMode) {
2371 var element = elements[node];
2372 if (element is Local) {
2373 ConcreteType type = locals.use(element);
2374 if (type != null) {
2375 inferrer.augmentInferredType(node, type);
2376 }
2377 }
2378 }
2379 return super.visitGetterSend(node);
2380 }
2381 }
OLDNEW
« no previous file with comments | « sdk/lib/_internal/compiler/implementation/inferrer/closure_tracer.dart ('k') | sdk/lib/_internal/compiler/implementation/inferrer/inferrer_visitor.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698