OLD | NEW |
| (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 dart_types; | |
6 | |
7 import 'dart:math' show min; | |
8 | |
9 import 'dart2jslib.dart' show Compiler, invariant, Script, Message; | |
10 import 'elements/modelx.dart' | |
11 show VoidElementX, | |
12 LibraryElementX, | |
13 BaseClassElementX, | |
14 TypeDeclarationElementX, | |
15 TypedefElementX; | |
16 import 'elements/elements.dart'; | |
17 import 'helpers/helpers.dart'; // Included for debug helpers. | |
18 import 'ordered_typeset.dart' show OrderedTypeSet; | |
19 import 'util/util.dart' show CURRENT_ELEMENT_SPANNABLE, equalElements; | |
20 | |
21 class TypeKind { | |
22 final String id; | |
23 | |
24 const TypeKind(String this.id); | |
25 | |
26 static const TypeKind FUNCTION = const TypeKind('function'); | |
27 static const TypeKind INTERFACE = const TypeKind('interface'); | |
28 static const TypeKind STATEMENT = const TypeKind('statement'); | |
29 static const TypeKind TYPEDEF = const TypeKind('typedef'); | |
30 static const TypeKind TYPE_VARIABLE = const TypeKind('type variable'); | |
31 static const TypeKind MALFORMED_TYPE = const TypeKind('malformed'); | |
32 static const TypeKind DYNAMIC = const TypeKind('dynamic'); | |
33 static const TypeKind VOID = const TypeKind('void'); | |
34 | |
35 String toString() => id; | |
36 } | |
37 | |
38 abstract class DartType { | |
39 String get name; | |
40 | |
41 TypeKind get kind; | |
42 | |
43 const DartType(); | |
44 | |
45 /** | |
46 * Returns the [Element] which declared this type. | |
47 * | |
48 * This can be [ClassElement] for classes, [TypedefElement] for typedefs, | |
49 * [TypeVariableElement] for type variables and [FunctionElement] for | |
50 * function types. | |
51 * | |
52 * Invariant: [element] must be a declaration element. | |
53 */ | |
54 Element get element; | |
55 | |
56 /** | |
57 * Performs the substitution [: [arguments[i]/parameters[i]]this :]. | |
58 * | |
59 * The notation is known from this lambda calculus rule: | |
60 * | |
61 * (lambda x.e0)e1 -> [e1/x]e0. | |
62 * | |
63 * See [TypeVariableType] for a motivation for this method. | |
64 * | |
65 * Invariant: There must be the same number of [arguments] and [parameters]. | |
66 */ | |
67 DartType subst(List<DartType> arguments, List<DartType> parameters); | |
68 | |
69 /// Performs the substitution of the type arguments of [type] for their | |
70 /// corresponding type variables in this type. | |
71 DartType substByContext(GenericType type) { | |
72 return subst(type.typeArguments, type.element.typeVariables); | |
73 } | |
74 | |
75 /** | |
76 * Returns the unaliased type of this type. | |
77 * | |
78 * The unaliased type of a typedef'd type is the unaliased type to which its | |
79 * name is bound. The unaliased version of any other type is the type itself. | |
80 * | |
81 * For example, the unaliased type of [: typedef A Func<A,B>(B b) :] is the | |
82 * function type [: (B) -> A :] and the unaliased type of | |
83 * [: Func<int,String> :] is the function type [: (String) -> int :]. | |
84 */ | |
85 DartType unalias(Compiler compiler); | |
86 | |
87 /** | |
88 * If this type is malformed or a generic type created with the wrong number | |
89 * of type arguments then [userProvidedBadType] holds the bad type provided | |
90 * by the user. | |
91 */ | |
92 DartType get userProvidedBadType => null; | |
93 | |
94 /// Is [: true :] if this type has no explict type arguments. | |
95 bool get isRaw => true; | |
96 | |
97 /// Returns the raw version of this type. | |
98 DartType asRaw() => this; | |
99 | |
100 /// Is [: true :] if this type has no non-dynamic type arguments. | |
101 bool get treatAsRaw => isRaw; | |
102 | |
103 /// Is [: true :] if this type should be treated as the dynamic type. | |
104 bool get treatAsDynamic => false; | |
105 | |
106 /// Is [: true :] if this type is the dynamic type. | |
107 bool get isDynamic => kind == TypeKind.DYNAMIC; | |
108 | |
109 /// Is [: true :] if this type is the void type. | |
110 bool get isVoid => kind == TypeKind.VOID; | |
111 | |
112 /// Is [: true :] if this is the type of `Object` from dart:core. | |
113 bool get isObject => false; | |
114 | |
115 /// Is [: true :] if this type is an interface type. | |
116 bool get isInterfaceType => kind == TypeKind.INTERFACE; | |
117 | |
118 /// Is [: true :] if this type is a typedef. | |
119 bool get isTypedef => kind == TypeKind.TYPEDEF; | |
120 | |
121 /// Is [: true :] if this type is a function type. | |
122 bool get isFunctionType => kind == TypeKind.FUNCTION; | |
123 | |
124 /// Is [: true :] if this type is a type variable. | |
125 bool get isTypeVariable => kind == TypeKind.TYPE_VARIABLE; | |
126 | |
127 /// Is [: true :] if this type is a malformed type. | |
128 bool get isMalformed => kind == TypeKind.MALFORMED_TYPE; | |
129 | |
130 /// Returns an occurrence of a type variable within this type, if any. | |
131 TypeVariableType get typeVariableOccurrence => null; | |
132 | |
133 /// Applies [f] to each occurence of a [TypeVariableType] within this type. | |
134 void forEachTypeVariable(f(TypeVariableType variable)) {} | |
135 | |
136 TypeVariableType _findTypeVariableOccurrence(List<DartType> types) { | |
137 for (DartType type in types) { | |
138 TypeVariableType typeVariable = type.typeVariableOccurrence; | |
139 if (typeVariable != null) { | |
140 return typeVariable; | |
141 } | |
142 } | |
143 return null; | |
144 } | |
145 | |
146 /// Is [: true :] if this type contains any type variables. | |
147 bool get containsTypeVariables => typeVariableOccurrence != null; | |
148 | |
149 /// Returns a textual representation of this type as if it was the type | |
150 /// of a member named [name]. | |
151 String getStringAsDeclared(String name) { | |
152 return new TypeDeclarationFormatter().format(this, name); | |
153 } | |
154 | |
155 accept(DartTypeVisitor visitor, var argument); | |
156 | |
157 void visitChildren(DartTypeVisitor visitor, var argument) {} | |
158 | |
159 static void visitList(List<DartType> types, | |
160 DartTypeVisitor visitor, var argument) { | |
161 for (DartType type in types) { | |
162 type.accept(visitor, argument); | |
163 } | |
164 } | |
165 } | |
166 | |
167 /** | |
168 * Represents a type variable, that is the type parameters of a class type. | |
169 * | |
170 * For example, in [: class Array<E> { ... } :], E is a type variable. | |
171 * | |
172 * Each class should have its own unique type variables, one for each type | |
173 * parameter. A class with type parameters is said to be parameterized or | |
174 * generic. | |
175 * | |
176 * Non-static members, constructors, and factories of generic | |
177 * class/interface can refer to type variables of the current class | |
178 * (not of supertypes). | |
179 * | |
180 * When using a generic type, also known as an application or | |
181 * instantiation of the type, the actual type arguments should be | |
182 * substituted for the type variables in the class declaration. | |
183 * | |
184 * For example, given a box, [: class Box<T> { T value; } :], the | |
185 * type of the expression [: new Box<String>().value :] is | |
186 * [: String :] because we must substitute [: String :] for the | |
187 * the type variable [: T :]. | |
188 */ | |
189 class TypeVariableType extends DartType { | |
190 final TypeVariableElement element; | |
191 | |
192 TypeVariableType(this.element); | |
193 | |
194 TypeKind get kind => TypeKind.TYPE_VARIABLE; | |
195 | |
196 String get name => element.name; | |
197 | |
198 DartType subst(List<DartType> arguments, List<DartType> parameters) { | |
199 assert(arguments.length == parameters.length); | |
200 if (parameters.isEmpty) { | |
201 // Return fast on empty substitutions. | |
202 return this; | |
203 } | |
204 for (int index = 0; index < arguments.length; index++) { | |
205 TypeVariableType parameter = parameters[index]; | |
206 DartType argument = arguments[index]; | |
207 if (parameter == this) { | |
208 return argument; | |
209 } | |
210 } | |
211 // The type variable was not substituted. | |
212 return this; | |
213 } | |
214 | |
215 DartType unalias(Compiler compiler) => this; | |
216 | |
217 DartType get typeVariableOccurrence => this; | |
218 | |
219 void forEachTypeVariable(f(TypeVariableType variable)) { | |
220 f(this); | |
221 } | |
222 | |
223 accept(DartTypeVisitor visitor, var argument) { | |
224 return visitor.visitTypeVariableType(this, argument); | |
225 } | |
226 | |
227 int get hashCode => 17 * element.hashCode; | |
228 | |
229 bool operator ==(other) { | |
230 if (other is !TypeVariableType) return false; | |
231 return identical(other.element, element); | |
232 } | |
233 | |
234 String toString() => name; | |
235 } | |
236 | |
237 /// Internal type representing the result of analyzing a statement. | |
238 class StatementType extends DartType { | |
239 Element get element => null; | |
240 | |
241 TypeKind get kind => TypeKind.STATEMENT; | |
242 | |
243 String get name => 'statement'; | |
244 | |
245 const StatementType(); | |
246 | |
247 DartType subst(List<DartType> arguments, List<DartType> parameters) => this; | |
248 | |
249 DartType unalias(Compiler compiler) => this; | |
250 | |
251 accept(DartTypeVisitor visitor, var argument) { | |
252 return visitor.visitStatementType(this, argument); | |
253 } | |
254 } | |
255 | |
256 class VoidType extends DartType { | |
257 const VoidType(); | |
258 | |
259 TypeKind get kind => TypeKind.VOID; | |
260 | |
261 String get name => 'void'; | |
262 | |
263 Element get element => null; | |
264 | |
265 DartType subst(List<DartType> arguments, List<DartType> parameters) { | |
266 // Void cannot be substituted. | |
267 return this; | |
268 } | |
269 | |
270 DartType unalias(Compiler compiler) => this; | |
271 | |
272 accept(DartTypeVisitor visitor, var argument) { | |
273 return visitor.visitVoidType(this, argument); | |
274 } | |
275 | |
276 String toString() => name; | |
277 } | |
278 | |
279 class MalformedType extends DartType { | |
280 final ErroneousElement element; | |
281 | |
282 /** | |
283 * [declaredType] holds the type which the user wrote in code. | |
284 * | |
285 * For instance, for a resolved but malformed type like [: Map<String> :] the | |
286 * [declaredType] is [: Map<String> :] whereas for an unresolved type | |
287 * [userProvidedBadType] is [: null :]. | |
288 */ | |
289 final DartType userProvidedBadType; | |
290 | |
291 /** | |
292 * Type arguments for the malformed typed, if these cannot fit in the | |
293 * [declaredType]. | |
294 * | |
295 * This field is for instance used for [: dynamic<int> :] and [: T<int> :] | |
296 * where [: T :] is a type variable, in which case [declaredType] holds | |
297 * [: dynamic :] and [: T :], respectively, or for [: X<int> :] where [: X :] | |
298 * is not resolved or does not imply a type. | |
299 */ | |
300 final List<DartType> typeArguments; | |
301 | |
302 final int hashCode = (nextHash++) & 0x3fffffff; | |
303 static int nextHash = 43765; | |
304 | |
305 MalformedType(this.element, this.userProvidedBadType, | |
306 [this.typeArguments = null]); | |
307 | |
308 TypeKind get kind => TypeKind.MALFORMED_TYPE; | |
309 | |
310 String get name => element.name; | |
311 | |
312 DartType subst(List<DartType> arguments, List<DartType> parameters) { | |
313 // Malformed types are not substitutable. | |
314 return this; | |
315 } | |
316 | |
317 // Malformed types are treated as dynamic. | |
318 bool get treatAsDynamic => true; | |
319 | |
320 DartType unalias(Compiler compiler) => this; | |
321 | |
322 accept(DartTypeVisitor visitor, var argument) { | |
323 return visitor.visitMalformedType(this, argument); | |
324 } | |
325 | |
326 String toString() { | |
327 var sb = new StringBuffer(); | |
328 if (typeArguments != null) { | |
329 if (userProvidedBadType != null) { | |
330 sb.write(userProvidedBadType.name); | |
331 } else { | |
332 sb.write(element.name); | |
333 } | |
334 if (!typeArguments.isEmpty) { | |
335 sb.write('<'); | |
336 sb.write(typeArguments.join(', ')); | |
337 sb.write('>'); | |
338 } | |
339 } else { | |
340 sb.write(userProvidedBadType.toString()); | |
341 } | |
342 return sb.toString(); | |
343 } | |
344 } | |
345 | |
346 abstract class GenericType extends DartType { | |
347 final TypeDeclarationElement element; | |
348 final List<DartType> typeArguments; | |
349 | |
350 GenericType(TypeDeclarationElement element, | |
351 this.typeArguments, | |
352 {bool checkTypeArgumentCount: true}) | |
353 : this.element = element { | |
354 assert(invariant(element, () { | |
355 if (!checkTypeArgumentCount) return true; | |
356 if (element is TypeDeclarationElementX) { | |
357 return element.thisTypeCache == null || | |
358 typeArguments.length == element.typeVariables.length; | |
359 } | |
360 return true; | |
361 }, message: () => 'Invalid type argument count on ${element.thisType}. ' | |
362 'Provided type arguments: $typeArguments.')); | |
363 } | |
364 | |
365 /// Creates a new instance of this type using the provided type arguments. | |
366 GenericType createInstantiation(List<DartType> newTypeArguments); | |
367 | |
368 DartType subst(List<DartType> arguments, List<DartType> parameters) { | |
369 if (typeArguments.isEmpty) { | |
370 // Return fast on non-generic types. | |
371 return this; | |
372 } | |
373 if (parameters.isEmpty) { | |
374 assert(arguments.isEmpty); | |
375 // Return fast on empty substitutions. | |
376 return this; | |
377 } | |
378 List<DartType> newTypeArguments = | |
379 Types.substTypes(typeArguments, arguments, parameters); | |
380 if (!identical(typeArguments, newTypeArguments)) { | |
381 // Create a new type only if necessary. | |
382 return createInstantiation(newTypeArguments); | |
383 } | |
384 return this; | |
385 } | |
386 | |
387 TypeVariableType get typeVariableOccurrence { | |
388 return _findTypeVariableOccurrence(typeArguments); | |
389 } | |
390 | |
391 void forEachTypeVariable(f(TypeVariableType variable)) { | |
392 for (DartType type in typeArguments) { | |
393 type.forEachTypeVariable(f); | |
394 } | |
395 } | |
396 | |
397 void visitChildren(DartTypeVisitor visitor, var argument) { | |
398 DartType.visitList(typeArguments, visitor, argument); | |
399 } | |
400 | |
401 String toString() { | |
402 StringBuffer sb = new StringBuffer(); | |
403 sb.write(name); | |
404 if (!isRaw) { | |
405 sb.write('<'); | |
406 sb.write(typeArguments.join(', ')); | |
407 sb.write('>'); | |
408 } | |
409 return sb.toString(); | |
410 } | |
411 | |
412 int get hashCode { | |
413 int hash = element.hashCode; | |
414 for (DartType argument in typeArguments) { | |
415 int argumentHash = argument != null ? argument.hashCode : 0; | |
416 hash = 17 * hash + 3 * argumentHash; | |
417 } | |
418 return hash; | |
419 } | |
420 | |
421 bool operator ==(other) { | |
422 if (other is !GenericType) return false; | |
423 return kind == other.kind | |
424 && element == other.element | |
425 && equalElements(typeArguments, other.typeArguments); | |
426 } | |
427 | |
428 /// Returns `true` if the declaration of this type has type variables. | |
429 bool get isGeneric => !typeArguments.isEmpty; | |
430 | |
431 bool get isRaw => typeArguments.isEmpty || identical(this, element.rawType); | |
432 | |
433 GenericType asRaw() => element.rawType; | |
434 | |
435 bool get treatAsRaw { | |
436 if (isRaw) return true; | |
437 for (DartType type in typeArguments) { | |
438 if (!type.treatAsDynamic) return false; | |
439 } | |
440 return true; | |
441 } | |
442 } | |
443 | |
444 class InterfaceType extends GenericType { | |
445 InterfaceType(ClassElement element, | |
446 [List<DartType> typeArguments = const <DartType>[]]) | |
447 : super(element, typeArguments) { | |
448 assert(invariant(element, element.isDeclaration)); | |
449 } | |
450 | |
451 InterfaceType.forUserProvidedBadType(BaseClassElementX element, | |
452 [List<DartType> typeArguments = | |
453 const <DartType>[]]) | |
454 : super(element, typeArguments, checkTypeArgumentCount: false); | |
455 | |
456 ClassElement get element => super.element; | |
457 | |
458 TypeKind get kind => TypeKind.INTERFACE; | |
459 | |
460 String get name => element.name; | |
461 | |
462 bool get isObject => element.isObject; | |
463 | |
464 InterfaceType createInstantiation(List<DartType> newTypeArguments) { | |
465 return new InterfaceType(element, newTypeArguments); | |
466 } | |
467 | |
468 /** | |
469 * Returns the type as an instance of class [other], if possible, null | |
470 * otherwise. | |
471 */ | |
472 DartType asInstanceOf(ClassElement other) { | |
473 other = other.declaration; | |
474 if (element == other) return this; | |
475 InterfaceType supertype = element.asInstanceOf(other); | |
476 if (supertype != null) { | |
477 List<DartType> arguments = Types.substTypes(supertype.typeArguments, | |
478 typeArguments, | |
479 element.typeVariables); | |
480 return new InterfaceType(supertype.element, arguments); | |
481 } | |
482 return null; | |
483 } | |
484 | |
485 DartType unalias(Compiler compiler) => this; | |
486 | |
487 MemberSignature lookupInterfaceMember(Name name) { | |
488 MemberSignature member = element.lookupInterfaceMember(name); | |
489 if (member != null && isGeneric) { | |
490 return new InterfaceMember(this, member); | |
491 } | |
492 return member; | |
493 } | |
494 | |
495 MemberSignature lookupClassMember(Name name) { | |
496 MemberSignature member = element.lookupClassMember(name); | |
497 if (member != null && isGeneric) { | |
498 return new InterfaceMember(this, member); | |
499 } | |
500 return member; | |
501 } | |
502 | |
503 int get hashCode => super.hashCode; | |
504 | |
505 InterfaceType asRaw() => super.asRaw(); | |
506 | |
507 accept(DartTypeVisitor visitor, var argument) { | |
508 return visitor.visitInterfaceType(this, argument); | |
509 } | |
510 | |
511 /// Returns the type of the 'call' method in this interface type, or | |
512 /// `null` if the interface type has no 'call' method. | |
513 FunctionType get callType { | |
514 FunctionType type = element.callType; | |
515 return type != null && isGeneric ? type.substByContext(this) : type; | |
516 } | |
517 } | |
518 | |
519 /** | |
520 * Special subclass of [InterfaceType] used for generic interface types created | |
521 * with the wrong number of type arguments. | |
522 * | |
523 * The type uses [:dynamic:] for all it s type arguments. | |
524 */ | |
525 class BadInterfaceType extends InterfaceType { | |
526 final InterfaceType userProvidedBadType; | |
527 | |
528 BadInterfaceType(ClassElement element, | |
529 InterfaceType this.userProvidedBadType) | |
530 : super(element, element.rawType.typeArguments); | |
531 | |
532 String toString() { | |
533 return userProvidedBadType.toString(); | |
534 } | |
535 } | |
536 | |
537 | |
538 /** | |
539 * Special subclass of [TypedefType] used for generic typedef types created | |
540 * with the wrong number of type arguments. | |
541 * | |
542 * The type uses [:dynamic:] for all it s type arguments. | |
543 */ | |
544 class BadTypedefType extends TypedefType { | |
545 final TypedefType userProvidedBadType; | |
546 | |
547 BadTypedefType(TypedefElement element, | |
548 TypedefType this.userProvidedBadType) | |
549 : super(element, element.rawType.typeArguments); | |
550 | |
551 String toString() { | |
552 return userProvidedBadType.toString(); | |
553 } | |
554 } | |
555 | |
556 class FunctionType extends DartType { | |
557 final FunctionTypedElement element; | |
558 final DartType returnType; | |
559 final List<DartType> parameterTypes; | |
560 final List<DartType> optionalParameterTypes; | |
561 | |
562 /** | |
563 * The names of the named parameters ordered lexicographically. | |
564 */ | |
565 final List<String> namedParameters; | |
566 | |
567 /** | |
568 * The types of the named parameters in the order corresponding to the | |
569 * [namedParameters]. | |
570 */ | |
571 final List<DartType> namedParameterTypes; | |
572 | |
573 factory FunctionType( | |
574 FunctionTypedElement element, | |
575 [DartType returnType = const DynamicType(), | |
576 List<DartType> parameterTypes = const <DartType>[], | |
577 List<DartType> optionalParameterTypes = const <DartType>[], | |
578 List<String> namedParameters = const <String>[], | |
579 List<DartType> namedParameterTypes = const <DartType>[]]) { | |
580 assert(invariant(CURRENT_ELEMENT_SPANNABLE, element != null)); | |
581 assert(invariant(element, element.isDeclaration)); | |
582 return new FunctionType.internal(element, | |
583 returnType, parameterTypes, optionalParameterTypes, | |
584 namedParameters, namedParameterTypes); | |
585 } | |
586 | |
587 factory FunctionType.synthesized( | |
588 [DartType returnType = const DynamicType(), | |
589 List<DartType> parameterTypes = const <DartType>[], | |
590 List<DartType> optionalParameterTypes = const <DartType>[], | |
591 List<String> namedParameters = const <String>[], | |
592 List<DartType> namedParameterTypes = const <DartType>[]]) { | |
593 return new FunctionType.internal(null, | |
594 returnType, parameterTypes, optionalParameterTypes, | |
595 namedParameters, namedParameterTypes); | |
596 } | |
597 | |
598 FunctionType.internal(FunctionTypedElement this.element, | |
599 [DartType this.returnType = const DynamicType(), | |
600 this.parameterTypes = const <DartType>[], | |
601 this.optionalParameterTypes = const <DartType>[], | |
602 this.namedParameters = const <String>[], | |
603 this.namedParameterTypes = const <DartType>[]]) { | |
604 assert(invariant(CURRENT_ELEMENT_SPANNABLE, | |
605 element == null || element.isDeclaration)); | |
606 // Assert that optional and named parameters are not used at the same time. | |
607 assert(optionalParameterTypes.isEmpty || namedParameterTypes.isEmpty); | |
608 assert(namedParameters.length == namedParameterTypes.length); | |
609 } | |
610 | |
611 | |
612 | |
613 TypeKind get kind => TypeKind.FUNCTION; | |
614 | |
615 DartType getNamedParameterType(String name) { | |
616 for (int i = 0; i < namedParameters.length; i++) { | |
617 if (namedParameters[i] == name) { | |
618 return namedParameterTypes[i]; | |
619 } | |
620 } | |
621 return null; | |
622 } | |
623 | |
624 DartType subst(List<DartType> arguments, List<DartType> parameters) { | |
625 if (parameters.isEmpty) { | |
626 assert(arguments.isEmpty); | |
627 // Return fast on empty substitutions. | |
628 return this; | |
629 } | |
630 DartType newReturnType = returnType.subst(arguments, parameters); | |
631 bool changed = !identical(newReturnType, returnType); | |
632 List<DartType> newParameterTypes = | |
633 Types.substTypes(parameterTypes, arguments, parameters); | |
634 List<DartType> newOptionalParameterTypes = | |
635 Types.substTypes(optionalParameterTypes, arguments, parameters); | |
636 List<DartType> newNamedParameterTypes = | |
637 Types.substTypes(namedParameterTypes, arguments, parameters); | |
638 if (!changed && | |
639 (!identical(parameterTypes, newParameterTypes) || | |
640 !identical(optionalParameterTypes, newOptionalParameterTypes) || | |
641 !identical(namedParameterTypes, newNamedParameterTypes))) { | |
642 changed = true; | |
643 } | |
644 if (changed) { | |
645 // Create a new type only if necessary. | |
646 return new FunctionType.internal(element, | |
647 newReturnType, | |
648 newParameterTypes, | |
649 newOptionalParameterTypes, | |
650 namedParameters, | |
651 newNamedParameterTypes); | |
652 } | |
653 return this; | |
654 } | |
655 | |
656 DartType unalias(Compiler compiler) => this; | |
657 | |
658 DartType get typeVariableOccurrence { | |
659 TypeVariableType typeVariableType = returnType.typeVariableOccurrence; | |
660 if (typeVariableType != null) return typeVariableType; | |
661 | |
662 typeVariableType = _findTypeVariableOccurrence(parameterTypes); | |
663 if (typeVariableType != null) return typeVariableType; | |
664 | |
665 typeVariableType = _findTypeVariableOccurrence(optionalParameterTypes); | |
666 if (typeVariableType != null) return typeVariableType; | |
667 | |
668 return _findTypeVariableOccurrence(namedParameterTypes); | |
669 } | |
670 | |
671 void forEachTypeVariable(f(TypeVariableType variable)) { | |
672 returnType.forEachTypeVariable(f); | |
673 parameterTypes.forEach((DartType type) { | |
674 type.forEachTypeVariable(f); | |
675 }); | |
676 optionalParameterTypes.forEach((DartType type) { | |
677 type.forEachTypeVariable(f); | |
678 }); | |
679 namedParameterTypes.forEach((DartType type) { | |
680 type.forEachTypeVariable(f); | |
681 }); | |
682 } | |
683 | |
684 accept(DartTypeVisitor visitor, var argument) { | |
685 return visitor.visitFunctionType(this, argument); | |
686 } | |
687 | |
688 void visitChildren(DartTypeVisitor visitor, var argument) { | |
689 returnType.accept(visitor, argument); | |
690 DartType.visitList(parameterTypes, visitor, argument); | |
691 DartType.visitList(optionalParameterTypes, visitor, argument); | |
692 DartType.visitList(namedParameterTypes, visitor, argument); | |
693 } | |
694 | |
695 String toString() { | |
696 StringBuffer sb = new StringBuffer(); | |
697 sb.write('('); | |
698 sb.write(parameterTypes.join(', ')); | |
699 bool first = parameterTypes.isEmpty; | |
700 if (!optionalParameterTypes.isEmpty) { | |
701 if (!first) { | |
702 sb.write(', '); | |
703 } | |
704 sb.write('['); | |
705 sb.write(optionalParameterTypes.join(', ')); | |
706 sb.write(']'); | |
707 first = false; | |
708 } | |
709 if (!namedParameterTypes.isEmpty) { | |
710 if (!first) { | |
711 sb.write(', '); | |
712 } | |
713 sb.write('{'); | |
714 first = true; | |
715 for (int i = 0; i < namedParameters.length; i++) { | |
716 if (!first) { | |
717 sb.write(', '); | |
718 } | |
719 sb.write(namedParameterTypes[i]); | |
720 sb.write(' '); | |
721 sb.write(namedParameters[i]); | |
722 first = false; | |
723 } | |
724 sb.write('}'); | |
725 } | |
726 sb.write(') -> ${returnType}'); | |
727 return sb.toString(); | |
728 } | |
729 | |
730 String get name => 'Function'; | |
731 | |
732 int computeArity() { | |
733 int arity = 0; | |
734 parameterTypes.forEach((_) { arity++; }); | |
735 return arity; | |
736 } | |
737 | |
738 int get hashCode { | |
739 int hash = 3 * returnType.hashCode; | |
740 for (DartType parameter in parameterTypes) { | |
741 hash = 17 * hash + 5 * parameter.hashCode; | |
742 } | |
743 for (DartType parameter in optionalParameterTypes) { | |
744 hash = 19 * hash + 7 * parameter.hashCode; | |
745 } | |
746 for (String name in namedParameters) { | |
747 hash = 23 * hash + 11 * name.hashCode; | |
748 } | |
749 for (DartType parameter in namedParameterTypes) { | |
750 hash = 29 * hash + 13 * parameter.hashCode; | |
751 } | |
752 return hash; | |
753 } | |
754 | |
755 bool operator ==(other) { | |
756 if (other is !FunctionType) return false; | |
757 return returnType == other.returnType && | |
758 equalElements(parameterTypes, other.parameterTypes) && | |
759 equalElements(optionalParameterTypes, other.optionalParameterTypes) && | |
760 equalElements(namedParameters, other.namedParameters) && | |
761 equalElements(namedParameterTypes, other.namedParameterTypes); | |
762 } | |
763 } | |
764 | |
765 class TypedefType extends GenericType { | |
766 TypedefType(TypedefElement element, | |
767 [List<DartType> typeArguments = const <DartType>[]]) | |
768 : super(element, typeArguments); | |
769 | |
770 TypedefType.forUserProvidedBadType(TypedefElement element, | |
771 [List<DartType> typeArguments = | |
772 const <DartType>[]]) | |
773 : super(element, typeArguments, checkTypeArgumentCount: false); | |
774 | |
775 TypedefElement get element => super.element; | |
776 | |
777 TypeKind get kind => TypeKind.TYPEDEF; | |
778 | |
779 String get name => element.name; | |
780 | |
781 TypedefType createInstantiation(List<DartType> newTypeArguments) { | |
782 return new TypedefType(element, newTypeArguments); | |
783 } | |
784 | |
785 DartType unalias(Compiler compiler) { | |
786 element.ensureResolved(compiler); | |
787 element.checkCyclicReference(compiler); | |
788 DartType definition = element.alias.unalias(compiler); | |
789 return definition.substByContext(this); | |
790 } | |
791 | |
792 int get hashCode => super.hashCode; | |
793 | |
794 TypedefType asRaw() => super.asRaw(); | |
795 | |
796 accept(DartTypeVisitor visitor, var argument) { | |
797 return visitor.visitTypedefType(this, argument); | |
798 } | |
799 } | |
800 | |
801 /// A typedef which has already been resolved to its alias. | |
802 class ResolvedTypedefType extends TypedefType { | |
803 FunctionType alias; | |
804 | |
805 ResolvedTypedefType(TypedefElement element, | |
806 List<DartType> typeArguments, | |
807 this.alias) | |
808 : super(element, typeArguments) { | |
809 assert(invariant(element, alias != null, | |
810 message: 'Alias must be non-null on $element.')); | |
811 } | |
812 | |
813 FunctionType unalias(Compiler compiler) => alias; | |
814 } | |
815 | |
816 /** | |
817 * Special type for the `dynamic` type. | |
818 */ | |
819 class DynamicType extends DartType { | |
820 const DynamicType(); | |
821 | |
822 Element get element => null; | |
823 | |
824 String get name => 'dynamic'; | |
825 | |
826 bool get treatAsDynamic => true; | |
827 | |
828 TypeKind get kind => TypeKind.DYNAMIC; | |
829 | |
830 DartType unalias(Compiler compiler) => this; | |
831 | |
832 DartType subst(List<DartType> arguments, List<DartType> parameters) => this; | |
833 | |
834 accept(DartTypeVisitor visitor, var argument) { | |
835 return visitor.visitDynamicType(this, argument); | |
836 } | |
837 | |
838 String toString() => name; | |
839 } | |
840 | |
841 /** | |
842 * [InterfaceMember] encapsulates a member (method, field, property) with | |
843 * the types of the declarer and receiver in order to do substitution on the | |
844 * member type. | |
845 * | |
846 * Consider for instance these classes and the variable `B<String> b`: | |
847 * | |
848 * class A<E> { | |
849 * E field; | |
850 * } | |
851 * class B<F> extends A<F> {} | |
852 * | |
853 * In an [InterfaceMember] for `b.field` the [receiver] is the type | |
854 * `B<String>` and the declarer is the type `A<F>`, which is the supertype of | |
855 * `B<F>` from which `field` has been inherited. To compute the type of | |
856 * `b.field` we must first substitute `E` by `F` using the relation between | |
857 * `A<E>` and `A<F>`, and then `F` by `String` using the relation between | |
858 * `B<F>` and `B<String>`. | |
859 */ | |
860 class InterfaceMember implements MemberSignature { | |
861 final InterfaceType instance; | |
862 final MemberSignature member; | |
863 | |
864 InterfaceMember(this.instance, this.member); | |
865 | |
866 Name get name => member.name; | |
867 | |
868 DartType get type => member.type.substByContext(instance); | |
869 | |
870 FunctionType get functionType => member.functionType.substByContext(instance); | |
871 | |
872 bool get isGetter => member.isGetter; | |
873 | |
874 bool get isSetter => member.isSetter; | |
875 | |
876 bool get isMethod => member.isMethod; | |
877 | |
878 Iterable<Member> get declarations => member.declarations; | |
879 } | |
880 | |
881 abstract class DartTypeVisitor<R, A> { | |
882 const DartTypeVisitor(); | |
883 | |
884 R visitType(DartType type, A argument); | |
885 | |
886 R visitVoidType(VoidType type, A argument) => | |
887 visitType(type, argument); | |
888 | |
889 R visitTypeVariableType(TypeVariableType type, A argument) => | |
890 visitType(type, argument); | |
891 | |
892 R visitFunctionType(FunctionType type, A argument) => | |
893 visitType(type, argument); | |
894 | |
895 R visitMalformedType(MalformedType type, A argument) => | |
896 visitType(type, argument); | |
897 | |
898 R visitStatementType(StatementType type, A argument) => | |
899 visitType(type, argument); | |
900 | |
901 R visitGenericType(GenericType type, A argument) => | |
902 visitType(type, argument); | |
903 | |
904 R visitInterfaceType(InterfaceType type, A argument) => | |
905 visitGenericType(type, argument); | |
906 | |
907 R visitTypedefType(TypedefType type, A argument) => | |
908 visitGenericType(type, argument); | |
909 | |
910 R visitDynamicType(DynamicType type, A argument) => | |
911 visitType(type, argument); | |
912 } | |
913 | |
914 /** | |
915 * Abstract visitor for determining relations between types. | |
916 */ | |
917 abstract class AbstractTypeRelation extends DartTypeVisitor<bool, DartType> { | |
918 final Compiler compiler; | |
919 | |
920 AbstractTypeRelation(Compiler this.compiler); | |
921 | |
922 bool visitType(DartType t, DartType s) { | |
923 throw 'internal error: unknown type kind ${t.kind}'; | |
924 } | |
925 | |
926 bool visitVoidType(VoidType t, DartType s) { | |
927 assert(s is! VoidType); | |
928 return false; | |
929 } | |
930 | |
931 bool invalidTypeArguments(DartType t, DartType s); | |
932 | |
933 bool invalidFunctionReturnTypes(DartType t, DartType s); | |
934 | |
935 bool invalidFunctionParameterTypes(DartType t, DartType s); | |
936 | |
937 bool invalidTypeVariableBounds(DartType bound, DartType s); | |
938 | |
939 /// Handle as dynamic for both subtype and more specific relation to avoid | |
940 /// spurious errors from malformed types. | |
941 bool visitMalformedType(MalformedType t, DartType s) => true; | |
942 | |
943 bool visitInterfaceType(InterfaceType t, DartType s) { | |
944 | |
945 // TODO(johnniwinther): Currently needed since literal types like int, | |
946 // double, bool etc. might not have been resolved yet. | |
947 t.element.ensureResolved(compiler); | |
948 | |
949 bool checkTypeArguments(InterfaceType instance, InterfaceType other) { | |
950 List<DartType> tTypeArgs = instance.typeArguments; | |
951 List<DartType> sTypeArgs = other.typeArguments; | |
952 assert(tTypeArgs.length == sTypeArgs.length); | |
953 for (int i = 0; i < tTypeArgs.length; i++) { | |
954 if (invalidTypeArguments(tTypeArgs[i], sTypeArgs[i])) { | |
955 return false; | |
956 } | |
957 } | |
958 return true; | |
959 } | |
960 | |
961 if (s is InterfaceType) { | |
962 InterfaceType instance = t.asInstanceOf(s.element); | |
963 return instance != null && checkTypeArguments(instance, s); | |
964 } else { | |
965 return false; | |
966 } | |
967 } | |
968 | |
969 bool visitFunctionType(FunctionType t, DartType s) { | |
970 if (s is InterfaceType && identical(s.element, compiler.functionClass)) { | |
971 return true; | |
972 } | |
973 if (s is !FunctionType) return false; | |
974 FunctionType tf = t; | |
975 FunctionType sf = s; | |
976 if (invalidFunctionReturnTypes(tf.returnType, sf.returnType)) { | |
977 return false; | |
978 } | |
979 | |
980 // TODO(johnniwinther): Rewrite the function subtyping to be more readable | |
981 // but still as efficient. | |
982 | |
983 // For the comments we use the following abbreviations: | |
984 // x.p : parameterTypes on [:x:], | |
985 // x.o : optionalParameterTypes on [:x:], and | |
986 // len(xs) : length of list [:xs:]. | |
987 | |
988 Iterator<DartType> tps = tf.parameterTypes.iterator; | |
989 Iterator<DartType> sps = sf.parameterTypes.iterator; | |
990 bool sNotEmpty = sps.moveNext(); | |
991 bool tNotEmpty = tps.moveNext(); | |
992 tNext() => (tNotEmpty = tps.moveNext()); | |
993 sNext() => (sNotEmpty = sps.moveNext()); | |
994 | |
995 bool incompatibleParameters() { | |
996 while (tNotEmpty && sNotEmpty) { | |
997 if (invalidFunctionParameterTypes(tps.current, sps.current)) { | |
998 return true; | |
999 } | |
1000 tNext(); | |
1001 sNext(); | |
1002 } | |
1003 return false; | |
1004 } | |
1005 | |
1006 if (incompatibleParameters()) return false; | |
1007 if (tNotEmpty) { | |
1008 // We must have [: len(t.p) <= len(s.p) :]. | |
1009 return false; | |
1010 } | |
1011 if (!sf.namedParameters.isEmpty) { | |
1012 // We must have [: len(t.p) == len(s.p) :]. | |
1013 if (sNotEmpty) { | |
1014 return false; | |
1015 } | |
1016 // Since named parameters are globally ordered we can determine the | |
1017 // subset relation with a linear search for [:sf.namedParameters:] | |
1018 // within [:tf.namedParameters:]. | |
1019 List<String> tNames = tf.namedParameters; | |
1020 List<DartType> tTypes = tf.namedParameterTypes; | |
1021 List<String> sNames = sf.namedParameters; | |
1022 List<DartType> sTypes = sf.namedParameterTypes; | |
1023 int tIndex = 0; | |
1024 int sIndex = 0; | |
1025 while (tIndex < tNames.length && sIndex < sNames.length) { | |
1026 if (tNames[tIndex] == sNames[sIndex]) { | |
1027 if (invalidFunctionParameterTypes(tTypes[tIndex], sTypes[sIndex])) { | |
1028 return false; | |
1029 } | |
1030 sIndex++; | |
1031 } | |
1032 tIndex++; | |
1033 } | |
1034 if (sIndex < sNames.length) { | |
1035 // We didn't find all names. | |
1036 return false; | |
1037 } | |
1038 } else { | |
1039 // Check the remaining [: s.p :] against [: t.o :]. | |
1040 tps = tf.optionalParameterTypes.iterator; | |
1041 tNext(); | |
1042 if (incompatibleParameters()) return false; | |
1043 if (sNotEmpty) { | |
1044 // We must have [: len(t.p) + len(t.o) >= len(s.p) :]. | |
1045 return false; | |
1046 } | |
1047 if (!sf.optionalParameterTypes.isEmpty) { | |
1048 // Check the remaining [: s.o :] against the remaining [: t.o :]. | |
1049 sps = sf.optionalParameterTypes.iterator; | |
1050 sNext(); | |
1051 if (incompatibleParameters()) return false; | |
1052 if (sNotEmpty) { | |
1053 // We didn't find enough parameters: | |
1054 // We must have [: len(t.p) + len(t.o) <= len(s.p) + len(s.o) :]. | |
1055 return false; | |
1056 } | |
1057 } else { | |
1058 if (sNotEmpty) { | |
1059 // We must have [: len(t.p) + len(t.o) >= len(s.p) :]. | |
1060 return false; | |
1061 } | |
1062 } | |
1063 } | |
1064 return true; | |
1065 } | |
1066 | |
1067 bool visitTypeVariableType(TypeVariableType t, DartType s) { | |
1068 // Identity check is handled in [isSubtype]. | |
1069 DartType bound = t.element.bound; | |
1070 if (bound.isTypeVariable) { | |
1071 // The bound is potentially cyclic so we need to be extra careful. | |
1072 Set<TypeVariableElement> seenTypeVariables = | |
1073 new Set<TypeVariableElement>(); | |
1074 seenTypeVariables.add(t.element); | |
1075 while (bound.isTypeVariable) { | |
1076 TypeVariableElement element = bound.element; | |
1077 if (identical(bound.element, s.element)) { | |
1078 // [t] extends [s]. | |
1079 return true; | |
1080 } | |
1081 if (seenTypeVariables.contains(element)) { | |
1082 // We have a cycle and have already checked all bounds in the cycle | |
1083 // against [s] and can therefore conclude that [t] is not a subtype | |
1084 // of [s]. | |
1085 return false; | |
1086 } | |
1087 seenTypeVariables.add(element); | |
1088 bound = element.bound; | |
1089 } | |
1090 } | |
1091 if (invalidTypeVariableBounds(bound, s)) return false; | |
1092 return true; | |
1093 } | |
1094 } | |
1095 | |
1096 class MoreSpecificVisitor extends AbstractTypeRelation { | |
1097 MoreSpecificVisitor(Compiler compiler) : super(compiler); | |
1098 | |
1099 bool isMoreSpecific(DartType t, DartType s) { | |
1100 if (identical(t, s) || s.treatAsDynamic || | |
1101 identical(t.element, compiler.nullClass)) { | |
1102 return true; | |
1103 } | |
1104 if (t.isVoid || s.isVoid) { | |
1105 return false; | |
1106 } | |
1107 if (t.treatAsDynamic) { | |
1108 return false; | |
1109 } | |
1110 if (identical(s.element, compiler.objectClass)) { | |
1111 return true; | |
1112 } | |
1113 t = t.unalias(compiler); | |
1114 s = s.unalias(compiler); | |
1115 | |
1116 return t.accept(this, s); | |
1117 } | |
1118 | |
1119 bool invalidTypeArguments(DartType t, DartType s) { | |
1120 return !isMoreSpecific(t, s); | |
1121 } | |
1122 | |
1123 bool invalidFunctionReturnTypes(DartType t, DartType s) { | |
1124 if (s.treatAsDynamic && t.isVoid) return true; | |
1125 return !s.isVoid && !isMoreSpecific(t, s); | |
1126 } | |
1127 | |
1128 bool invalidFunctionParameterTypes(DartType t, DartType s) { | |
1129 return !isMoreSpecific(t, s); | |
1130 } | |
1131 | |
1132 bool invalidTypeVariableBounds(DartType bound, DartType s) { | |
1133 return !isMoreSpecific(bound, s); | |
1134 } | |
1135 } | |
1136 | |
1137 /** | |
1138 * Type visitor that determines the subtype relation two types. | |
1139 */ | |
1140 class SubtypeVisitor extends MoreSpecificVisitor { | |
1141 | |
1142 SubtypeVisitor(Compiler compiler) : super(compiler); | |
1143 | |
1144 bool isSubtype(DartType t, DartType s) { | |
1145 return t.treatAsDynamic || isMoreSpecific(t, s); | |
1146 } | |
1147 | |
1148 bool isAssignable(DartType t, DartType s) { | |
1149 return isSubtype(t, s) || isSubtype(s, t); | |
1150 } | |
1151 | |
1152 bool invalidTypeArguments(DartType t, DartType s) { | |
1153 return !isSubtype(t, s); | |
1154 } | |
1155 | |
1156 bool invalidFunctionReturnTypes(DartType t, DartType s) { | |
1157 return !s.isVoid && !isAssignable(t, s); | |
1158 } | |
1159 | |
1160 bool invalidFunctionParameterTypes(DartType t, DartType s) { | |
1161 return !isAssignable(t, s); | |
1162 } | |
1163 | |
1164 bool invalidTypeVariableBounds(DartType bound, DartType s) { | |
1165 return !isSubtype(bound, s); | |
1166 } | |
1167 | |
1168 bool visitInterfaceType(InterfaceType t, DartType s) { | |
1169 if (super.visitInterfaceType(t, s)) return true; | |
1170 | |
1171 if (s is InterfaceType && | |
1172 s.element == compiler.functionClass && | |
1173 t.element.callType != null) { | |
1174 return true; | |
1175 } else if (s is FunctionType) { | |
1176 FunctionType callType = t.callType; | |
1177 return callType != null && isSubtype(callType, s); | |
1178 } | |
1179 return false; | |
1180 } | |
1181 } | |
1182 | |
1183 /** | |
1184 * Callback used to check whether the [typeArgument] of [type] is a valid | |
1185 * substitute for the bound of [typeVariable]. [bound] holds the bound against | |
1186 * which [typeArgument] should be checked. | |
1187 */ | |
1188 typedef void CheckTypeVariableBound(GenericType type, | |
1189 DartType typeArgument, | |
1190 TypeVariableType typeVariable, | |
1191 DartType bound); | |
1192 | |
1193 class Types { | |
1194 final Compiler compiler; | |
1195 final MoreSpecificVisitor moreSpecificVisitor; | |
1196 final SubtypeVisitor subtypeVisitor; | |
1197 final PotentialSubtypeVisitor potentialSubtypeVisitor; | |
1198 | |
1199 Types(Compiler compiler) | |
1200 : this.compiler = compiler, | |
1201 this.moreSpecificVisitor = new MoreSpecificVisitor(compiler), | |
1202 this.subtypeVisitor = new SubtypeVisitor(compiler), | |
1203 this.potentialSubtypeVisitor = new PotentialSubtypeVisitor(compiler); | |
1204 | |
1205 Types copy(Compiler compiler) { | |
1206 return new Types(compiler); | |
1207 } | |
1208 | |
1209 /** Returns true if [t] is more specific than [s]. */ | |
1210 bool isMoreSpecific(DartType t, DartType s) { | |
1211 return moreSpecificVisitor.isMoreSpecific(t, s); | |
1212 } | |
1213 | |
1214 /** | |
1215 * Returns the most specific type of [t] and [s] or `null` if neither is more | |
1216 * specific than the other. | |
1217 */ | |
1218 DartType getMostSpecific(DartType t, DartType s) { | |
1219 if (isMoreSpecific(t, s)) { | |
1220 return t; | |
1221 } else if (isMoreSpecific(s, t)) { | |
1222 return s; | |
1223 } else { | |
1224 return null; | |
1225 } | |
1226 } | |
1227 | |
1228 /** Returns true if t is a subtype of s */ | |
1229 bool isSubtype(DartType t, DartType s) { | |
1230 return subtypeVisitor.isSubtype(t, s); | |
1231 } | |
1232 | |
1233 bool isAssignable(DartType r, DartType s) { | |
1234 return subtypeVisitor.isAssignable(r, s); | |
1235 } | |
1236 | |
1237 static const int IS_SUBTYPE = 1; | |
1238 static const int MAYBE_SUBTYPE = 0; | |
1239 static const int NOT_SUBTYPE = -1; | |
1240 | |
1241 int computeSubtypeRelation(DartType t, DartType s) { | |
1242 // TODO(johnniwinther): Compute this directly in [isPotentialSubtype]. | |
1243 if (isSubtype(t, s)) return IS_SUBTYPE; | |
1244 return isPotentialSubtype(t, s) ? MAYBE_SUBTYPE : NOT_SUBTYPE; | |
1245 } | |
1246 | |
1247 bool isPotentialSubtype(DartType t, DartType s) { | |
1248 // TODO(johnniwinther): Return a set of variable points in the positive | |
1249 // cases. | |
1250 return potentialSubtypeVisitor.isSubtype(t, s); | |
1251 } | |
1252 | |
1253 /** | |
1254 * Checks the type arguments of [type] against the type variable bounds | |
1255 * declared on [element]. Calls [checkTypeVariableBound] on each type | |
1256 * argument and bound. | |
1257 */ | |
1258 void checkTypeVariableBounds(GenericType type, | |
1259 CheckTypeVariableBound checkTypeVariableBound) { | |
1260 TypeDeclarationElement element = type.element; | |
1261 List<DartType> typeArguments = type.typeArguments; | |
1262 List<DartType> typeVariables = element.typeVariables; | |
1263 assert(typeVariables.length == typeArguments.length); | |
1264 for (int index = 0; index < typeArguments.length; index++) { | |
1265 TypeVariableType typeVariable = typeVariables[index]; | |
1266 DartType bound = typeVariable.element.bound.substByContext(type); | |
1267 DartType typeArgument = typeArguments[index]; | |
1268 checkTypeVariableBound(type, typeArgument, typeVariable, bound); | |
1269 } | |
1270 } | |
1271 | |
1272 /** | |
1273 * Helper method for performing substitution of a list of types. | |
1274 * | |
1275 * If no types are changed by the substitution, the [types] is returned | |
1276 * instead of a newly created list. | |
1277 */ | |
1278 static List<DartType> substTypes(List<DartType> types, | |
1279 List<DartType> arguments, | |
1280 List<DartType> parameters) { | |
1281 bool changed = false; | |
1282 List<DartType> result = new List<DartType>.generate(types.length, (index) { | |
1283 DartType type = types[index]; | |
1284 DartType argument = type.subst(arguments, parameters); | |
1285 if (!changed && !identical(argument, type)) { | |
1286 changed = true; | |
1287 } | |
1288 return argument; | |
1289 }); | |
1290 // Use the new List only if necessary. | |
1291 return changed ? result : types; | |
1292 } | |
1293 | |
1294 /** | |
1295 * Returns the [ClassElement] which declares the type variables occurring in | |
1296 * [type], or [:null:] if [type] does not contain type variables. | |
1297 */ | |
1298 static ClassElement getClassContext(DartType type) { | |
1299 TypeVariableType typeVariable = type.typeVariableOccurrence; | |
1300 if (typeVariable == null) return null; | |
1301 return typeVariable.element.typeDeclaration; | |
1302 } | |
1303 | |
1304 /** | |
1305 * A `compareTo` function that globally orders types using | |
1306 * [Elements.compareByPosition] to order types defined by a declaration. | |
1307 * | |
1308 * The order is: | |
1309 * * void | |
1310 * * dynamic | |
1311 * * interface, typedef, type variables ordered by element order | |
1312 * - interface and typedef of the same element are ordered by | |
1313 * the order of their type arguments | |
1314 * * function types, ordered by | |
1315 * - return type | |
1316 * - required parameter types | |
1317 * - optional parameter types | |
1318 * - named parameter names | |
1319 * - named parameter types | |
1320 * * malformed types | |
1321 * * statement types | |
1322 */ | |
1323 static int compare(DartType a, DartType b) { | |
1324 if (a == b) return 0; | |
1325 if (a.isVoid) { | |
1326 // [b] is not void => a < b. | |
1327 return -1; | |
1328 } else if (b.isVoid) { | |
1329 // [a] is not void => a > b. | |
1330 return 1; | |
1331 } | |
1332 if (a.isDynamic) { | |
1333 // [b] is not dynamic => a < b. | |
1334 return -1; | |
1335 } else if (b.isDynamic) { | |
1336 // [a] is not dynamic => a > b. | |
1337 return 1; | |
1338 } | |
1339 bool isDefinedByDeclaration(DartType type) { | |
1340 return type.isInterfaceType || | |
1341 type.isTypedef || | |
1342 type.isTypeVariable; | |
1343 } | |
1344 | |
1345 if (isDefinedByDeclaration(a)) { | |
1346 if (isDefinedByDeclaration(b)) { | |
1347 int result = Elements.compareByPosition(a.element, b.element); | |
1348 if (result != 0) return result; | |
1349 if (a.isTypeVariable) { | |
1350 return b.isTypeVariable | |
1351 ? 0 | |
1352 : 1; // [b] is not a type variable => a > b. | |
1353 } else { | |
1354 if (b.isTypeVariable) { | |
1355 // [a] is not a type variable => a < b. | |
1356 return -1; | |
1357 } else { | |
1358 return compareList((a as GenericType).typeArguments, | |
1359 (b as GenericType).typeArguments); | |
1360 } | |
1361 } | |
1362 } else { | |
1363 // [b] is neither an interface, typedef, type variable, dynamic, | |
1364 // nor void => a < b. | |
1365 return -1; | |
1366 } | |
1367 } else if (isDefinedByDeclaration(b)) { | |
1368 // [a] is neither an interface, typedef, type variable, dynamic, | |
1369 // nor void => a > b. | |
1370 return 1; | |
1371 } | |
1372 if (a.isFunctionType) { | |
1373 if (b.isFunctionType) { | |
1374 FunctionType aFunc = a; | |
1375 FunctionType bFunc = b; | |
1376 int result = compare(aFunc.returnType, bFunc.returnType); | |
1377 if (result != 0) return result; | |
1378 result = compareList(aFunc.parameterTypes, bFunc.parameterTypes); | |
1379 if (result != 0) return result; | |
1380 result = compareList(aFunc.optionalParameterTypes, | |
1381 bFunc.optionalParameterTypes); | |
1382 if (result != 0) return result; | |
1383 // TODO(karlklose): reuse [compareList]. | |
1384 Iterator<String> aNames = aFunc.namedParameters.iterator; | |
1385 Iterator<String> bNames = bFunc.namedParameters.iterator; | |
1386 while (aNames.moveNext() && bNames.moveNext()) { | |
1387 int result = aNames.current.compareTo(bNames.current); | |
1388 if (result != 0) return result; | |
1389 } | |
1390 if (aNames.moveNext()) { | |
1391 // [aNames] is longer that [bNames] => a > b. | |
1392 return 1; | |
1393 } else if (bNames.moveNext()) { | |
1394 // [bNames] is longer that [aNames] => a < b. | |
1395 return -1; | |
1396 } | |
1397 return compareList(aFunc.namedParameterTypes, | |
1398 bFunc.namedParameterTypes); | |
1399 } else { | |
1400 // [b] is a malformed or statement type => a < b. | |
1401 return -1; | |
1402 } | |
1403 } else if (b.isFunctionType) { | |
1404 // [b] is a malformed or statement type => a > b. | |
1405 return 1; | |
1406 } | |
1407 if (a.kind == TypeKind.STATEMENT) { | |
1408 if (b.kind == TypeKind.STATEMENT) { | |
1409 return 0; | |
1410 } else { | |
1411 // [b] is a malformed type => a > b. | |
1412 return 1; | |
1413 } | |
1414 } else if (b.kind == TypeKind.STATEMENT) { | |
1415 // [a] is a malformed type => a < b. | |
1416 return -1; | |
1417 } | |
1418 assert (a.isMalformed); | |
1419 assert (b.isMalformed); | |
1420 // TODO(johnniwinther): Can we do this better? | |
1421 return Elements.compareByPosition(a.element, b.element); | |
1422 } | |
1423 | |
1424 static int compareList(List<DartType> a, List<DartType> b) { | |
1425 for (int index = 0; index < min(a.length, b.length); index++) { | |
1426 int result = compare(a[index], b[index]); | |
1427 if (result != 0) return result; | |
1428 } | |
1429 if (a.length > b.length) { | |
1430 return 1; | |
1431 } else if (a.length < b.length) { | |
1432 return -1; | |
1433 } | |
1434 return 0; | |
1435 } | |
1436 | |
1437 static List<DartType> sorted(Iterable<DartType> types) { | |
1438 return types.toList()..sort(compare); | |
1439 } | |
1440 | |
1441 /// Computes the least upper bound of two interface types [a] and [b]. | |
1442 InterfaceType computeLeastUpperBoundInterfaces(InterfaceType a, | |
1443 InterfaceType b) { | |
1444 | |
1445 /// Returns the set of supertypes of [type] at depth [depth]. | |
1446 Set<DartType> getSupertypesAtDepth(InterfaceType type, int depth) { | |
1447 OrderedTypeSet types = type.element.allSupertypesAndSelf; | |
1448 Set<DartType> set = new Set<DartType>(); | |
1449 types.forEach(depth, (DartType supertype) { | |
1450 set.add(supertype.substByContext(type)); | |
1451 }); | |
1452 return set; | |
1453 } | |
1454 | |
1455 ClassElement aClass = a.element; | |
1456 ClassElement bClass = b.element; | |
1457 int maxCommonDepth = min(aClass.hierarchyDepth, bClass.hierarchyDepth); | |
1458 for (int depth = maxCommonDepth; depth >= 0; depth--) { | |
1459 Set<DartType> aTypeSet = getSupertypesAtDepth(a, depth); | |
1460 Set<DartType> bTypeSet = getSupertypesAtDepth(b, depth); | |
1461 Set<DartType> intersection = aTypeSet..retainAll(bTypeSet); | |
1462 if (intersection.length == 1) { | |
1463 return intersection.first; | |
1464 } | |
1465 } | |
1466 invariant(CURRENT_ELEMENT_SPANNABLE, false, | |
1467 message: 'No least upper bound computed for $a and $b.'); | |
1468 return null; | |
1469 } | |
1470 | |
1471 /// Computes the least upper bound of the types in the longest prefix of [a] | |
1472 /// and [b]. | |
1473 List<DartType> computeLeastUpperBoundsTypes(List<DartType> a, | |
1474 List<DartType> b) { | |
1475 if (a.isEmpty || b.isEmpty) return const <DartType>[]; | |
1476 int prefixLength = min(a.length, b.length); | |
1477 List<DartType> types = new List<DartType>(prefixLength); | |
1478 for (int index = 0; index < prefixLength; index++) { | |
1479 types[index] = computeLeastUpperBound(a[index], b[index]); | |
1480 } | |
1481 return types; | |
1482 } | |
1483 | |
1484 /// Computes the least upper bound of two function types [a] and [b]. | |
1485 /// | |
1486 /// If the required parameter count of [a] and [b] does not match, `Function` | |
1487 /// is returned. | |
1488 /// | |
1489 /// Otherwise, a function type is returned whose return type and | |
1490 /// parameter types are the least upper bound of those of [a] and [b], | |
1491 /// respectively. In addition, the optional parameters are the least upper | |
1492 /// bound of the longest common prefix of the optional parameters of [a] and | |
1493 /// [b], and the named parameters are the least upper bound of those common to | |
1494 /// [a] and [b]. | |
1495 DartType computeLeastUpperBoundFunctionTypes(FunctionType a, | |
1496 FunctionType b) { | |
1497 if (a.parameterTypes.length != b.parameterTypes.length) { | |
1498 return compiler.functionClass.rawType; | |
1499 } | |
1500 DartType returnType = computeLeastUpperBound(a.returnType, b.returnType); | |
1501 List<DartType> parameterTypes = | |
1502 computeLeastUpperBoundsTypes(a.parameterTypes, b.parameterTypes); | |
1503 List<DartType> optionalParameterTypes = | |
1504 computeLeastUpperBoundsTypes(a.optionalParameterTypes, | |
1505 b.optionalParameterTypes); | |
1506 List<String> namedParameters = <String>[]; | |
1507 List<String> aNamedParameters = a.namedParameters; | |
1508 List<String> bNamedParameters = b.namedParameters; | |
1509 List<DartType> namedParameterTypes = <DartType>[]; | |
1510 List<DartType> aNamedParameterTypes = a.namedParameterTypes; | |
1511 List<DartType> bNamedParameterTypes = b.namedParameterTypes; | |
1512 int aIndex = 0; | |
1513 int bIndex = 0; | |
1514 int prefixLength = | |
1515 min(aNamedParameterTypes.length, bNamedParameterTypes.length); | |
1516 while (aIndex < aNamedParameters.length && | |
1517 bIndex < bNamedParameters.length) { | |
1518 String aNamedParameter = aNamedParameters[aIndex]; | |
1519 String bNamedParameter = bNamedParameters[bIndex]; | |
1520 int result = aNamedParameter.compareTo(bNamedParameter); | |
1521 if (result == 0) { | |
1522 namedParameters.add(aNamedParameter); | |
1523 namedParameterTypes.add(computeLeastUpperBound( | |
1524 aNamedParameterTypes[aIndex], bNamedParameterTypes[bIndex])); | |
1525 } | |
1526 if (result <= 0) { | |
1527 aIndex++; | |
1528 } | |
1529 if (result >= 0) { | |
1530 bIndex++; | |
1531 } | |
1532 } | |
1533 return new FunctionType.synthesized( | |
1534 returnType, | |
1535 parameterTypes, optionalParameterTypes, | |
1536 namedParameters, namedParameterTypes); | |
1537 } | |
1538 | |
1539 /// Computes the least upper bound of two types of which at least one is a | |
1540 /// type variable. The least upper bound of a type variable is defined in | |
1541 /// terms of its bound, but to ensure reflexivity we need to check for common | |
1542 /// bounds transitively. | |
1543 DartType computeLeastUpperBoundTypeVariableTypes(DartType a, | |
1544 DartType b) { | |
1545 Set<DartType> typeVariableBounds = new Set<DartType>(); | |
1546 while (a.isTypeVariable) { | |
1547 if (a == b) return a; | |
1548 typeVariableBounds.add(a); | |
1549 TypeVariableElement element = a.element; | |
1550 a = element.bound; | |
1551 } | |
1552 while (b.isTypeVariable) { | |
1553 if (typeVariableBounds.contains(b)) return b; | |
1554 TypeVariableElement element = b.element; | |
1555 b = element.bound; | |
1556 } | |
1557 return computeLeastUpperBound(a, b); | |
1558 } | |
1559 | |
1560 /// Computes the least upper bound for [a] and [b]. | |
1561 DartType computeLeastUpperBound(DartType a, DartType b) { | |
1562 if (a == b) return a; | |
1563 | |
1564 if (a.isTypeVariable || | |
1565 b.isTypeVariable) { | |
1566 return computeLeastUpperBoundTypeVariableTypes(a, b); | |
1567 } | |
1568 | |
1569 a = a.unalias(compiler); | |
1570 b = b.unalias(compiler); | |
1571 | |
1572 if (a.treatAsDynamic || b.treatAsDynamic) return const DynamicType(); | |
1573 if (a.isVoid || b.isVoid) return const VoidType(); | |
1574 | |
1575 if (a.isFunctionType && b.isFunctionType) { | |
1576 return computeLeastUpperBoundFunctionTypes(a, b); | |
1577 } | |
1578 | |
1579 if (a.isFunctionType) { | |
1580 a = compiler.functionClass.rawType; | |
1581 } | |
1582 if (b.isFunctionType) { | |
1583 b = compiler.functionClass.rawType; | |
1584 } | |
1585 | |
1586 if (a.isInterfaceType && b.isInterfaceType) { | |
1587 return computeLeastUpperBoundInterfaces(a, b); | |
1588 } | |
1589 return const DynamicType(); | |
1590 } | |
1591 } | |
1592 | |
1593 /** | |
1594 * Type visitor that determines one type could a subtype of another given the | |
1595 * right type variable substitution. The computation is approximate and returns | |
1596 * [:false:] only if we are sure no such substitution exists. | |
1597 */ | |
1598 class PotentialSubtypeVisitor extends SubtypeVisitor { | |
1599 PotentialSubtypeVisitor(Compiler compiler) : super(compiler); | |
1600 | |
1601 bool isSubtype(DartType t, DartType s) { | |
1602 if (t is TypeVariableType || s is TypeVariableType) { | |
1603 return true; | |
1604 } | |
1605 return super.isSubtype(t, s); | |
1606 } | |
1607 } | |
1608 | |
1609 /// Visitor used to compute an instantiation of a generic type that is more | |
1610 /// specific than a given type. | |
1611 /// | |
1612 /// The visitor tries to compute constraints for all type variables in the | |
1613 /// visited type by structurally matching it with the argument type. If the | |
1614 /// constraints are too complex or the two types are too different, `false` | |
1615 /// is returned. Otherwise, the [constraintMap] holds the valid constraints. | |
1616 class MoreSpecificSubtypeVisitor extends DartTypeVisitor<bool, DartType> { | |
1617 final Compiler compiler; | |
1618 Map<TypeVariableType, DartType> constraintMap; | |
1619 | |
1620 MoreSpecificSubtypeVisitor(Compiler this.compiler); | |
1621 | |
1622 /// Compute an instance of [element] which is more specific than [supertype]. | |
1623 /// If no instance is found, `null` is returned. | |
1624 /// | |
1625 /// Note that this computation is a heuristic. It does not find a suggestion | |
1626 /// in all possible cases. | |
1627 InterfaceType computeMoreSpecific(ClassElement element, | |
1628 InterfaceType supertype) { | |
1629 InterfaceType supertypeInstance = | |
1630 element.thisType.asInstanceOf(supertype.element); | |
1631 if (supertypeInstance == null) return null; | |
1632 | |
1633 constraintMap = new Map<TypeVariableType, DartType>(); | |
1634 element.typeVariables.forEach((TypeVariableType typeVariable) { | |
1635 constraintMap[typeVariable] = const DynamicType(); | |
1636 }); | |
1637 if (supertypeInstance.accept(this, supertype)) { | |
1638 List<DartType> variables = element.typeVariables; | |
1639 List<DartType> typeArguments = new List<DartType>.generate( | |
1640 variables.length, (int index) => constraintMap[variables[index]]); | |
1641 return element.thisType.createInstantiation(typeArguments); | |
1642 } | |
1643 return null; | |
1644 } | |
1645 | |
1646 bool visitType(DartType type, DartType argument) { | |
1647 return compiler.types.isMoreSpecific(type, argument); | |
1648 } | |
1649 | |
1650 bool visitTypes(List<DartType> a, List<DartType> b) { | |
1651 int prefixLength = min(a.length, b.length); | |
1652 for (int index = 0; index < prefixLength; index++) { | |
1653 if (!a[index].accept(this, b[index])) return false; | |
1654 } | |
1655 return prefixLength == a.length && a.length == b.length; | |
1656 } | |
1657 | |
1658 bool visitTypeVariableType(TypeVariableType type, DartType argument) { | |
1659 DartType constraint = | |
1660 compiler.types.getMostSpecific(constraintMap[type], argument); | |
1661 constraintMap[type] = constraint; | |
1662 return constraint != null; | |
1663 } | |
1664 | |
1665 bool visitFunctionType(FunctionType type, DartType argument) { | |
1666 if (argument is FunctionType) { | |
1667 if (type.parameterTypes.length != | |
1668 argument.parameterTypes.length) { | |
1669 return false; | |
1670 } | |
1671 if (type.optionalParameterTypes.length != | |
1672 argument.optionalParameterTypes.length) { | |
1673 return false; | |
1674 } | |
1675 if (type.namedParameters != argument.namedParameters) { | |
1676 return false; | |
1677 } | |
1678 | |
1679 if (!type.returnType.accept(this, argument.returnType)) return false; | |
1680 if (visitTypes(type.parameterTypes, argument.parameterTypes)) { | |
1681 return false; | |
1682 } | |
1683 if (visitTypes(type.optionalParameterTypes, | |
1684 argument.optionalParameterTypes)) { | |
1685 return false; | |
1686 } | |
1687 return visitTypes(type.namedParameterTypes, argument.namedParameterTypes); | |
1688 } | |
1689 return false; | |
1690 } | |
1691 | |
1692 bool visitGenericType(GenericType type, DartType argument) { | |
1693 if (argument is GenericType) { | |
1694 if (type.element != argument.element) return false; | |
1695 return visitTypes(type.typeArguments, argument.typeArguments); | |
1696 } | |
1697 return false; | |
1698 } | |
1699 } | |
1700 | |
1701 /// Visitor used to print type annotation like they used in the source code. | |
1702 /// The visitor is especially for printing a function type like | |
1703 /// `(Foo,[Bar])->Baz` as `Baz m(Foo a1, [Bar a2])`. | |
1704 class TypeDeclarationFormatter extends DartTypeVisitor<dynamic, String> { | |
1705 Set<String> usedNames; | |
1706 StringBuffer sb; | |
1707 | |
1708 /// Creates textual representation of [type] as if a member by the [name] were | |
1709 /// declared. For instance 'String foo' for `format(String, 'foo')`. | |
1710 String format(DartType type, String name) { | |
1711 sb = new StringBuffer(); | |
1712 usedNames = new Set<String>(); | |
1713 type.accept(this, name); | |
1714 usedNames = null; | |
1715 return sb.toString(); | |
1716 } | |
1717 | |
1718 String createName(String name) { | |
1719 if (name != null && !usedNames.contains(name)) { | |
1720 usedNames.add(name); | |
1721 return name; | |
1722 } | |
1723 int index = usedNames.length; | |
1724 String proposal; | |
1725 do { | |
1726 proposal = '${name}${index++}'; | |
1727 } while (usedNames.contains(proposal)); | |
1728 usedNames.add(proposal); | |
1729 return proposal; | |
1730 } | |
1731 | |
1732 void visit(DartType type) { | |
1733 type.accept(this, null); | |
1734 } | |
1735 | |
1736 void visitTypes(List<DartType> types, String prefix) { | |
1737 bool needsComma = false; | |
1738 for (DartType type in types) { | |
1739 if (needsComma) { | |
1740 sb.write(', '); | |
1741 } | |
1742 type.accept(this, prefix); | |
1743 needsComma = true; | |
1744 } | |
1745 } | |
1746 | |
1747 void visitType(DartType type, String name) { | |
1748 if (name == null) { | |
1749 sb.write(type); | |
1750 } else { | |
1751 sb.write('$type ${createName(name)}'); | |
1752 } | |
1753 } | |
1754 | |
1755 void visitGenericType(GenericType type, String name) { | |
1756 sb.write(type.name); | |
1757 if (!type.treatAsRaw) { | |
1758 sb.write('<'); | |
1759 visitTypes(type.typeArguments, null); | |
1760 sb.write('>'); | |
1761 } | |
1762 if (name != null) { | |
1763 sb.write(' '); | |
1764 sb.write(createName(name)); | |
1765 } | |
1766 } | |
1767 | |
1768 void visitFunctionType(FunctionType type, String name) { | |
1769 visit(type.returnType); | |
1770 sb.write(' '); | |
1771 if (name != null) { | |
1772 sb.write(name); | |
1773 } else { | |
1774 sb.write(createName('f')); | |
1775 } | |
1776 sb.write('('); | |
1777 visitTypes(type.parameterTypes, 'a'); | |
1778 bool needsComma = !type.parameterTypes.isEmpty; | |
1779 if (!type.optionalParameterTypes.isEmpty) { | |
1780 if (needsComma) { | |
1781 sb.write(', '); | |
1782 } | |
1783 sb.write('['); | |
1784 visitTypes(type.optionalParameterTypes, 'a'); | |
1785 sb.write(']'); | |
1786 needsComma = true; | |
1787 } | |
1788 if (!type.namedParameterTypes.isEmpty) { | |
1789 if (needsComma) { | |
1790 sb.write(', '); | |
1791 } | |
1792 sb.write('{'); | |
1793 List<String> namedParameters = type.namedParameters; | |
1794 List<DartType> namedParameterTypes = type.namedParameterTypes; | |
1795 needsComma = false; | |
1796 for (int index = 0; index < namedParameters.length; index++) { | |
1797 if (needsComma) { | |
1798 sb.write(', '); | |
1799 } | |
1800 namedParameterTypes[index].accept(this, namedParameters[index]); | |
1801 needsComma = true; | |
1802 } | |
1803 sb.write('}'); | |
1804 } | |
1805 sb.write(')'); | |
1806 } | |
1807 } | |
1808 | |
OLD | NEW |