OLD | NEW |
1 // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2015, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 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. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 library analyzer.src.generated.type_system; | 5 library analyzer.src.generated.type_system; |
6 | 6 |
7 import 'dart:collection'; | 7 import 'dart:collection'; |
8 import 'dart:math' as math; | 8 import 'dart:math' as math; |
9 | 9 |
10 import 'package:analyzer/dart/ast/token.dart' show TokenType; | 10 import 'package:analyzer/dart/ast/token.dart' show TokenType; |
11 import 'package:analyzer/dart/element/element.dart'; | 11 import 'package:analyzer/dart/element/element.dart'; |
12 import 'package:analyzer/dart/element/type.dart'; | 12 import 'package:analyzer/dart/element/type.dart'; |
13 import 'package:analyzer/src/dart/element/element.dart'; | 13 import 'package:analyzer/src/dart/element/element.dart'; |
14 import 'package:analyzer/src/dart/element/type.dart'; | 14 import 'package:analyzer/src/dart/element/type.dart'; |
15 import 'package:analyzer/src/generated/engine.dart' | 15 import 'package:analyzer/src/generated/engine.dart' |
16 show AnalysisContext, AnalysisOptionsImpl; | 16 show AnalysisContext, AnalysisOptionsImpl; |
17 import 'package:analyzer/src/generated/resolver.dart' show TypeProvider; | 17 import 'package:analyzer/src/generated/resolver.dart' show TypeProvider; |
18 import 'package:analyzer/src/generated/utilities_dart.dart'; | 18 import 'package:analyzer/src/generated/utilities_dart.dart' show ParameterKind; |
| 19 import 'package:analyzer/src/generated/utilities_general.dart' |
| 20 show JenkinsSmiHash; |
19 | 21 |
20 typedef bool _GuardedSubtypeChecker<T>(T t1, T t2, Set<Element> visited); | 22 typedef bool _GuardedSubtypeChecker<T>(T t1, T t2, Set<Element> visited); |
21 | 23 |
22 /** | 24 /** |
23 * Implementation of [TypeSystem] using the strong mode rules. | 25 * Implementation of [TypeSystem] using the strong mode rules. |
24 * https://github.com/dart-lang/dev_compiler/blob/master/STRONG_MODE.md | 26 * https://github.com/dart-lang/dev_compiler/blob/master/STRONG_MODE.md |
25 */ | 27 */ |
26 class StrongTypeSystemImpl extends TypeSystem { | 28 class StrongTypeSystemImpl extends TypeSystem { |
27 /** | 29 /** |
28 * True if implicit casts should be allowed, otherwise false. | 30 * True if implicit casts should be allowed, otherwise false. |
(...skipping 246 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
275 return fnType; | 277 return fnType; |
276 } | 278 } |
277 | 279 |
278 // Create a TypeSystem that will allow certain type parameters to be | 280 // Create a TypeSystem that will allow certain type parameters to be |
279 // inferred. It will optimistically assume these type parameters can be | 281 // inferred. It will optimistically assume these type parameters can be |
280 // subtypes (or supertypes) as necessary, and track the constraints that | 282 // subtypes (or supertypes) as necessary, and track the constraints that |
281 // are implied by this. | 283 // are implied by this. |
282 var inferringTypeSystem = | 284 var inferringTypeSystem = |
283 new _StrongInferenceTypeSystem(typeProvider, this, fnType.typeFormals); | 285 new _StrongInferenceTypeSystem(typeProvider, this, fnType.typeFormals); |
284 | 286 |
285 // Special case inference for Future.then. | |
286 // | |
287 // We don't have union types, so Future<T>.then<S> is typed to take a | |
288 // callback `T -> S`. However, the lambda might actually return a | |
289 // Future<S>. So we handle that special case here. | |
290 if (argumentTypes.isNotEmpty && argumentTypes[0] is FunctionType) { | |
291 Element element = fnType?.element; | |
292 bool isFutureThen = element is MethodElement && | |
293 element.name == 'then' && | |
294 element.enclosingElement.type.isDartAsyncFuture; | |
295 if (isFutureThen) { | |
296 // Ignore return context. We'll let the onValue function's return type | |
297 // drive inference. | |
298 returnContextType = null; | |
299 } | |
300 } | |
301 | |
302 if (returnContextType != null) { | 287 if (returnContextType != null) { |
303 inferringTypeSystem.isSubtypeOf(fnType.returnType, returnContextType); | 288 inferringTypeSystem.isSubtypeOf(fnType.returnType, returnContextType); |
304 } | 289 } |
305 | 290 |
306 for (int i = 0; i < argumentTypes.length; i++) { | 291 for (int i = 0; i < argumentTypes.length; i++) { |
307 // Try to pass each argument to each parameter, recording any type | 292 // Try to pass each argument to each parameter, recording any type |
308 // parameter bounds that were implied by this assignment. | 293 // parameter bounds that were implied by this assignment. |
309 inferringTypeSystem.isSubtypeOf( | 294 inferringTypeSystem.isSubtypeOf( |
310 argumentTypes[i], correspondingParameterTypes[i]); | 295 argumentTypes[i], correspondingParameterTypes[i]); |
311 } | 296 } |
(...skipping 432 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
744 bool _isSubtypeOf(DartType t1, DartType t2, Set<Element> visited, | 729 bool _isSubtypeOf(DartType t1, DartType t2, Set<Element> visited, |
745 {bool dynamicIsBottom: false}) { | 730 {bool dynamicIsBottom: false}) { |
746 // Guard recursive calls | 731 // Guard recursive calls |
747 _GuardedSubtypeChecker<DartType> guardedSubtype = _guard(_isSubtypeOf); | 732 _GuardedSubtypeChecker<DartType> guardedSubtype = _guard(_isSubtypeOf); |
748 _GuardedSubtypeChecker<DartType> guardedInferTypeParameter = | 733 _GuardedSubtypeChecker<DartType> guardedInferTypeParameter = |
749 _guard(_inferTypeParameterSubtypeOf); | 734 _guard(_inferTypeParameterSubtypeOf); |
750 if (t1 == t2) { | 735 if (t1 == t2) { |
751 return true; | 736 return true; |
752 } | 737 } |
753 | 738 |
754 // The types are void, dynamic, bottom, interface types, function types | 739 // The types are void, dynamic, bottom, interface types, function types, |
755 // and type parameters. We proceed by eliminating these different classes | 740 // and type parameters. We proceed by eliminating these different classes |
756 // from consideration. | 741 // from consideration. |
757 | 742 |
758 // Trivially true. | 743 // Trivially true. |
759 if (_isTop(t2, dynamicIsBottom: dynamicIsBottom) || | 744 if (_isTop(t2, dynamicIsBottom: dynamicIsBottom) || |
760 _isBottom(t1, dynamicIsBottom: dynamicIsBottom)) { | 745 _isBottom(t1, dynamicIsBottom: dynamicIsBottom)) { |
761 return true; | 746 return true; |
762 } | 747 } |
763 | 748 |
764 // Trivially false. | 749 // Trivially false. |
765 if (_isTop(t1, dynamicIsBottom: dynamicIsBottom) || | 750 if (_isTop(t1, dynamicIsBottom: dynamicIsBottom) || |
(...skipping 567 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1333 @override | 1318 @override |
1334 DartType _typeParameterLeastUpperBound( | 1319 DartType _typeParameterLeastUpperBound( |
1335 TypeProvider provider, DartType type1, DartType type2) { | 1320 TypeProvider provider, DartType type1, DartType type2) { |
1336 type1 = type1.resolveToBound(provider.objectType); | 1321 type1 = type1.resolveToBound(provider.objectType); |
1337 type2 = type2.resolveToBound(provider.objectType); | 1322 type2 = type2.resolveToBound(provider.objectType); |
1338 return getLeastUpperBound(provider, type1, type2); | 1323 return getLeastUpperBound(provider, type1, type2); |
1339 } | 1324 } |
1340 } | 1325 } |
1341 | 1326 |
1342 /// Tracks upper and lower type bounds for a set of type parameters. | 1327 /// Tracks upper and lower type bounds for a set of type parameters. |
| 1328 /// |
| 1329 /// This class is used by calling [isSubtypeOf]. When it encounters one of |
| 1330 /// the type parameters it is inferring, it will record the constraint, and |
| 1331 /// optimistically assume the constraint will be satisfied. |
| 1332 /// |
| 1333 /// For example if we are inferring type parameter A, and we ask if |
| 1334 /// `A <: num`, this will record that A must be a subytpe of `num`. It also |
| 1335 /// handles cases when A appears as part of the structure of another type, for |
| 1336 /// example `Iterable<A> <: Iterable<num>` would infer the same constraint |
| 1337 /// (due to covariant generic types) as would `() -> A <: () -> num`. In |
| 1338 /// contrast `(A) -> void <: (num) -> void`. |
| 1339 /// |
| 1340 /// Once the lower/upper bounds are determined, [_infer] should be called to |
| 1341 /// finish the inference. It will instantiate a generic function type with the |
| 1342 /// inferred types for each type parameter. |
| 1343 /// |
| 1344 /// It can also optionally compute a partial solution, in case some of the type |
| 1345 /// parameters could not be inferred (because the constraints cannot be |
| 1346 /// satisfied), or bail on the inference when this happens. |
| 1347 /// |
| 1348 /// As currently designed, an instance of this class should only be used to |
| 1349 /// infer a single call and discarded immediately afterwards. |
1343 class _StrongInferenceTypeSystem extends StrongTypeSystemImpl { | 1350 class _StrongInferenceTypeSystem extends StrongTypeSystemImpl { |
1344 final TypeProvider _typeProvider; | 1351 final TypeProvider _typeProvider; |
1345 | 1352 |
1346 /// The outer strong mode type system, used for GLB and LUB, so we don't | 1353 /// The outer strong mode type system, used for GLB and LUB, so we don't |
1347 /// recurse into our constraint solving code. | 1354 /// recurse into our constraint solving code. |
1348 final StrongTypeSystemImpl _typeSystem; | 1355 final StrongTypeSystemImpl _typeSystem; |
1349 final Map<TypeParameterType, _TypeParameterBound> _bounds; | 1356 final Map<TypeParameterType, _TypeParameterBound> _bounds; |
1350 | 1357 |
1351 _StrongInferenceTypeSystem(this._typeProvider, this._typeSystem, | 1358 _StrongInferenceTypeSystem(this._typeProvider, this._typeSystem, |
1352 Iterable<TypeParameterElement> typeFormals) | 1359 Iterable<TypeParameterElement> typeFormals) |
(...skipping 218 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1571 passedOut = true; | 1578 passedOut = true; |
1572 } | 1579 } |
1573 } else if (type is FunctionType) { | 1580 } else if (type is FunctionType) { |
1574 _visitFunctionType(typeParam, type, paramIn); | 1581 _visitFunctionType(typeParam, type, paramIn); |
1575 } else if (type is InterfaceType) { | 1582 } else if (type is InterfaceType) { |
1576 _visitInterfaceType(typeParam, type, paramIn); | 1583 _visitInterfaceType(typeParam, type, paramIn); |
1577 } | 1584 } |
1578 } | 1585 } |
1579 } | 1586 } |
1580 | 1587 |
| 1588 /** |
| 1589 * A special union type of `Future<T> | T` used for Strong Mode inference. |
| 1590 */ |
| 1591 class FutureUnionType extends TypeImpl { |
| 1592 // TODO(jmesserly): a Set would be better. |
| 1593 // |
| 1594 // For now we know `Future<T> | T` is the only valid use, so we can rely on |
| 1595 // the order, which simplifies some things. |
| 1596 // |
| 1597 // This will need clean up before this can function as a real union type. |
| 1598 final List<DartType> _types; |
| 1599 |
| 1600 /** |
| 1601 * Creates a union of `Future< flatten(T) > | flatten(T)`. |
| 1602 */ |
| 1603 factory FutureUnionType( |
| 1604 DartType type, TypeProvider provider, TypeSystem system) { |
| 1605 type = type.flattenFutures(system); |
| 1606 |
| 1607 // The order of these types is important: T could be a type variable, so |
| 1608 // we want to try and match `Future<T>` before we try and match `T`. |
| 1609 return new FutureUnionType._([ |
| 1610 provider.futureType.instantiate([type]), |
| 1611 type |
| 1612 ]); |
| 1613 } |
| 1614 |
| 1615 FutureUnionType._(this._types) : super(null, null); |
| 1616 |
| 1617 DartType get futureOfType => _types[0]; |
| 1618 |
| 1619 DartType get type => _types[1]; |
| 1620 |
| 1621 Iterable<DartType> get types => _types; |
| 1622 |
| 1623 @override |
| 1624 void appendTo(StringBuffer buffer) { |
| 1625 buffer.write('('); |
| 1626 for (int i = 0; i < _types.length; i++) { |
| 1627 if (i != 0) { |
| 1628 buffer.write(' | '); |
| 1629 } |
| 1630 (_types[i] as TypeImpl).appendTo(buffer); |
| 1631 } |
| 1632 buffer.write(')'); |
| 1633 } |
| 1634 |
| 1635 @override |
| 1636 int get hashCode { |
| 1637 int hash = 0; |
| 1638 for (var t in types) { |
| 1639 hash = JenkinsSmiHash.combine(hash, t.hashCode); |
| 1640 } |
| 1641 return JenkinsSmiHash.finish(hash); |
| 1642 } |
| 1643 |
| 1644 @override |
| 1645 bool operator ==(Object obj) { |
| 1646 if (obj is FutureUnionType) { |
| 1647 if (identical(obj, this)) return true; |
| 1648 return types.length == obj.types.length && |
| 1649 types.toSet().containsAll(obj.types); |
| 1650 } |
| 1651 return false; |
| 1652 } |
| 1653 |
| 1654 @override |
| 1655 bool isMoreSpecificThan(DartType type, |
| 1656 [bool withDynamic = false, Set<Element> visitedElements]) => |
| 1657 throw new UnsupportedError( |
| 1658 'Future unions are not part of the Dart 1 type system'); |
| 1659 |
| 1660 @override |
| 1661 TypeImpl pruned(List<FunctionTypeAliasElement> prune) => |
| 1662 throw new UnsupportedError('Future unions are not substituted'); |
| 1663 |
| 1664 @override |
| 1665 DartType substitute2(List<DartType> args, List<DartType> params, |
| 1666 [List<FunctionTypeAliasElement> prune]) => |
| 1667 throw new UnsupportedError('Future unions are not used in typedefs'); |
| 1668 |
| 1669 /** |
| 1670 * Creates a union of `T | Future<T>`, unless `T` is already a future-union, |
| 1671 * in which case it simply returns `T` |
| 1672 */ |
| 1673 static DartType from( |
| 1674 DartType type, TypeProvider provider, TypeSystem system) { |
| 1675 if (type is FutureUnionType) { |
| 1676 return type; |
| 1677 } |
| 1678 return new FutureUnionType(type, provider, system); |
| 1679 } |
| 1680 } |
| 1681 |
1581 bool _isBottom(DartType t, {bool dynamicIsBottom: false}) { | 1682 bool _isBottom(DartType t, {bool dynamicIsBottom: false}) { |
1582 return (t.isDynamic && dynamicIsBottom) || t.isBottom; | 1683 return (t.isDynamic && dynamicIsBottom) || t.isBottom; |
1583 } | 1684 } |
1584 | 1685 |
1585 bool _isTop(DartType t, {bool dynamicIsBottom: false}) { | 1686 bool _isTop(DartType t, {bool dynamicIsBottom: false}) { |
1586 // TODO(leafp): Document the rules in play here | 1687 // TODO(leafp): Document the rules in play here |
1587 return (t.isDynamic && !dynamicIsBottom) || t.isObject; | 1688 return (t.isDynamic && !dynamicIsBottom) || t.isObject; |
1588 } | 1689 } |
OLD | NEW |