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/ast.dart' show AstNode; | 10 import 'package:analyzer/dart/ast/ast.dart' show AstNode; |
(...skipping 678 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
689 return false; | 689 return false; |
690 } | 690 } |
691 try { | 691 try { |
692 return check(t1, t2, visited); | 692 return check(t1, t2, visited); |
693 } finally { | 693 } finally { |
694 visited.remove(element); | 694 visited.remove(element); |
695 } | 695 } |
696 }; | 696 }; |
697 } | 697 } |
698 | 698 |
699 /// If [t1] or [t2] is a type parameter we are inferring, update its bound. | |
700 /// Returns `true` if we could possibly find a compatible type, | |
701 /// otherwise `false`. | |
702 bool _inferTypeParameterSubtypeOf(DartType t1, DartType t2) { | |
703 return false; | |
704 } | |
705 | |
706 /** | 699 /** |
707 * This currently does not implement a very complete least upper bound | 700 * This currently does not implement a very complete least upper bound |
708 * algorithm, but handles a couple of the very common cases that are | 701 * algorithm, but handles a couple of the very common cases that are |
709 * causing pain in real code. The current algorithm is: | 702 * causing pain in real code. The current algorithm is: |
710 * 1. If either of the types is a supertype of the other, return it. | 703 * 1. If either of the types is a supertype of the other, return it. |
711 * This is in fact the best result in this case. | 704 * This is in fact the best result in this case. |
712 * 2. If the two types have the same class element, then take the | 705 * 2. If the two types have the same class element, then take the |
713 * pointwise least upper bound of the type arguments. This is again | 706 * pointwise least upper bound of the type arguments. This is again |
714 * the best result, except that the recursive calls may not return | 707 * the best result, except that the recursive calls may not return |
715 * the true least uppper bounds. The result is guaranteed to be a | 708 * the true least uppper bounds. The result is guaranteed to be a |
(...skipping 117 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
833 | 826 |
834 // Trivially true. | 827 // Trivially true. |
835 if (_isTop(t2, dynamicIsBottom: dynamicIsBottom) || | 828 if (_isTop(t2, dynamicIsBottom: dynamicIsBottom) || |
836 _isBottom(t1, dynamicIsBottom: dynamicIsBottom)) { | 829 _isBottom(t1, dynamicIsBottom: dynamicIsBottom)) { |
837 return true; | 830 return true; |
838 } | 831 } |
839 | 832 |
840 // Trivially false. | 833 // Trivially false. |
841 if (_isTop(t1, dynamicIsBottom: dynamicIsBottom) || | 834 if (_isTop(t1, dynamicIsBottom: dynamicIsBottom) || |
842 _isBottom(t2, dynamicIsBottom: dynamicIsBottom)) { | 835 _isBottom(t2, dynamicIsBottom: dynamicIsBottom)) { |
843 return _inferTypeParameterSubtypeOf(t1, t2); | 836 return false; |
844 } | |
845 | |
846 // S <: T where S is a type variable | |
847 // T is not dynamic or object (handled above) | |
848 // True if T == S | |
849 // Or true if bound of S is S' and S' <: T | |
850 if (t1 is TypeParameterType) { | |
851 if (t2 is TypeParameterType && | |
852 t1.definition == t2.definition && | |
853 guardedSubtype(t1.bound, t2.bound, visited)) { | |
854 return true; | |
855 } | |
856 if (_inferTypeParameterSubtypeOf(t1, t2)) { | |
857 return true; | |
858 } | |
859 DartType bound = t1.element.bound; | |
860 return bound == null ? false : guardedSubtype(bound, t2, visited); | |
861 } | |
862 | |
863 if (t2 is TypeParameterType) { | |
864 return _inferTypeParameterSubtypeOf(t1, t2); | |
865 } | 837 } |
866 | 838 |
867 // Handle FutureOr<T> union type. | 839 // Handle FutureOr<T> union type. |
868 if (t1 is InterfaceType && t1.isDartAsyncFutureOr) { | 840 if (t1 is InterfaceType && t1.isDartAsyncFutureOr) { |
869 var t1TypeArg = t1.typeArguments[0]; | 841 var t1TypeArg = t1.typeArguments[0]; |
870 if (t2 is InterfaceType && t2.isDartAsyncFutureOr) { | 842 if (t2 is InterfaceType && t2.isDartAsyncFutureOr) { |
871 var t2TypeArg = t2.typeArguments[0]; | 843 var t2TypeArg = t2.typeArguments[0]; |
872 // FutureOr<A> <: FutureOr<B> iff A <: B | 844 // FutureOr<A> <: FutureOr<B> iff A <: B |
873 return isSubtypeOf(t1TypeArg, t2TypeArg); | 845 return isSubtypeOf(t1TypeArg, t2TypeArg); |
874 } | 846 } |
875 | 847 |
876 // given t1 is Future<A> | A, then: | 848 // given t1 is Future<A> | A, then: |
877 // (Future<A> | A) <: t2 iff Future<A> <: t2 and A <: t2. | 849 // (Future<A> | A) <: t2 iff Future<A> <: t2 and A <: t2. |
878 var t1Future = typeProvider.futureType.instantiate([t1TypeArg]); | 850 var t1Future = typeProvider.futureType.instantiate([t1TypeArg]); |
879 return isSubtypeOf(t1Future, t2) && isSubtypeOf(t1TypeArg, t2); | 851 return isSubtypeOf(t1Future, t2) && isSubtypeOf(t1TypeArg, t2); |
880 } | 852 } |
881 | 853 |
882 if (t2 is InterfaceType && t2.isDartAsyncFutureOr) { | 854 if (t2 is InterfaceType && t2.isDartAsyncFutureOr) { |
883 // given t2 is Future<A> | A, then: | 855 // given t2 is Future<A> | A, then: |
884 // t1 <: (Future<A> | A) iff t1 <: Future<A> or t1 <: A | 856 // t1 <: (Future<A> | A) iff t1 <: Future<A> or t1 <: A |
885 var t2TypeArg = t2.typeArguments[0]; | 857 var t2TypeArg = t2.typeArguments[0]; |
886 var t2Future = typeProvider.futureType.instantiate([t2TypeArg]); | 858 var t2Future = typeProvider.futureType.instantiate([t2TypeArg]); |
887 return isSubtypeOf(t1, t2Future) || isSubtypeOf(t1, t2TypeArg); | 859 return isSubtypeOf(t1, t2Future) || isSubtypeOf(t1, t2TypeArg); |
888 } | 860 } |
889 | 861 |
862 // S <: T where S is a type variable | |
863 // T is not dynamic or object (handled above) | |
864 // True if T == S | |
865 // Or true if bound of S is S' and S' <: T | |
866 if (t1 is TypeParameterType) { | |
867 if (t2 is TypeParameterType && | |
868 t1.definition == t2.definition && | |
869 guardedSubtype(t1.bound, t2.bound, visited)) { | |
870 return true; | |
871 } | |
872 DartType bound = t1.element.bound; | |
873 return bound == null ? false : guardedSubtype(bound, t2, visited); | |
874 } | |
875 if (t2 is TypeParameterType) { | |
876 return false; | |
877 } | |
878 | |
890 // Void only appears as the return type of a function, and we handle it | 879 // Void only appears as the return type of a function, and we handle it |
891 // directly in the function subtype rules. We should not get to a point | 880 // directly in the function subtype rules. We should not get to a point |
892 // where we're doing a subtype test on a "bare" void, but just in case we | 881 // where we're doing a subtype test on a "bare" void, but just in case we |
893 // do, handle it safely. | 882 // do, handle it safely. |
894 // TODO(rnystrom): Determine how this can ever be reached. If it can't, | 883 // TODO(rnystrom): Determine how this can ever be reached. If it can't, |
895 // remove it. | 884 // remove it. |
896 if (t1.isVoid || t2.isVoid) { | 885 if (t1.isVoid || t2.isVoid) { |
897 return t1.isVoid && t2.isVoid; | 886 return t1.isVoid && t2.isVoid; |
898 } | 887 } |
899 | 888 |
(...skipping 596 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1496 // complex cases such as: | 1485 // complex cases such as: |
1497 // | 1486 // |
1498 // <TFrom, TTo extends Iterable<TFrom>> | 1487 // <TFrom, TTo extends Iterable<TFrom>> |
1499 // | 1488 // |
1500 // Or if the type parameter's bound depends on itself such as: | 1489 // Or if the type parameter's bound depends on itself such as: |
1501 // | 1490 // |
1502 // <T extends Clonable<T>> | 1491 // <T extends Clonable<T>> |
1503 DartType declaredUpperBound = typeParam.element.bound; | 1492 DartType declaredUpperBound = typeParam.element.bound; |
1504 if (declaredUpperBound != null) { | 1493 if (declaredUpperBound != null) { |
1505 // Assert that the type parameter is a subtype of its bound. | 1494 // Assert that the type parameter is a subtype of its bound. |
1506 _inferTypeParameterSubtypeOf(typeParam, | 1495 _isSubtypeOf(typeParam, |
1507 declaredUpperBound.substitute2(inferredTypes, fnTypeParams)); | 1496 declaredUpperBound.substitute2(inferredTypes, fnTypeParams), null); |
1508 } | 1497 } |
1509 | 1498 |
1510 // Now we've computed lower and upper bounds for each type parameter. | 1499 // Now we've computed lower and upper bounds for each type parameter. |
1511 // | 1500 // |
1512 // To decide on which type to assign, we look at the return type and see | 1501 // To decide on which type to assign, we look at the return type and see |
1513 // if the type parameter occurs in covariant or contravariant positions. | 1502 // if the type parameter occurs in covariant or contravariant positions. |
1514 // | 1503 // |
1515 // If the type is "passed in" at all, or if our lower bound was bottom, | 1504 // If the type is "passed in" at all, or if our lower bound was bottom, |
1516 // we choose the upper bound as being the most useful. | 1505 // we choose the upper bound as being the most useful. |
1517 // | 1506 // |
(...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1555 variance.passedIn && !upperBound.isDynamic || lowerBound.isBottom | 1544 variance.passedIn && !upperBound.isDynamic || lowerBound.isBottom |
1556 ? upperBound | 1545 ? upperBound |
1557 : lowerBound; | 1546 : lowerBound; |
1558 } | 1547 } |
1559 | 1548 |
1560 // Return the instantiated type. | 1549 // Return the instantiated type. |
1561 return genericType.instantiate(inferredTypes) as dynamic/*=T*/; | 1550 return genericType.instantiate(inferredTypes) as dynamic/*=T*/; |
1562 } | 1551 } |
1563 | 1552 |
1564 @override | 1553 @override |
1565 bool _inferTypeParameterSubtypeOf(DartType t1, DartType t2) { | 1554 bool _isSubtypeOf(DartType t1, DartType t2, Set<Element> visited, |
1555 {bool dynamicIsBottom: false}) { | |
1556 // TODO(jmesserly): to match old behavior, the trivial constraints are | |
Leaf
2017/01/27 21:34:54
What's the thing to be done in in this TODO?
Jennifer Messerly
2017/01/27 22:39:19
it's not right once we pin based on downward const
| |
1557 // not treated as adding to the constraint set. | |
1558 if (identical(t1, t2) || | |
1559 _isTop(t2, dynamicIsBottom: dynamicIsBottom) || | |
1560 _isBottom(t1, dynamicIsBottom: dynamicIsBottom)) { | |
1561 return true; | |
1562 } | |
1563 | |
1566 if (t1 is TypeParameterType) { | 1564 if (t1 is TypeParameterType) { |
1565 // TODO(jmesserly): we ignore `dynamicIsBottom` here, is that correct? | |
1567 _TypeParameterBound bound = _bounds[t1]; | 1566 _TypeParameterBound bound = _bounds[t1]; |
1568 if (bound != null) { | 1567 if (bound != null) { |
1569 // Ensure T1 <: T2, where T1 is a type parameter we are inferring. | 1568 // Ensure T1 <: T2, where T1 is a type parameter we are inferring. |
1570 // T2 is an upper bound, so merge it with our existing upper bound. | 1569 // T2 is an upper bound, so merge it with our existing upper bound. |
1571 // | 1570 // |
1572 // We already know T1 <: U, for some U. | 1571 // We already know T1 <: U, for some U. |
1573 // So update U to reflect the new constraint T1 <: GLB(U, T2) | 1572 // So update U to reflect the new constraint T1 <: GLB(U, T2) |
1574 // | 1573 // |
1575 bound.upper = _typeSystem.getGreatestLowerBound(bound.upper, t2); | 1574 bound.upper = _typeSystem.getGreatestLowerBound(bound.upper, t2); |
1576 // Optimistically assume we will be able to satisfy the constraint. | 1575 // Optimistically assume we will be able to satisfy the constraint. |
1577 return true; | 1576 return true; |
1578 } | 1577 } |
1579 } | 1578 } |
1580 if (t2 is TypeParameterType) { | 1579 if (t2 is TypeParameterType) { |
1581 _TypeParameterBound bound = _bounds[t2]; | 1580 _TypeParameterBound bound = _bounds[t2]; |
1582 if (bound != null) { | 1581 if (bound != null) { |
1583 // Ensure T1 <: T2, where T2 is a type parameter we are inferring. | 1582 // Ensure T1 <: T2, where T2 is a type parameter we are inferring. |
1584 // T1 is a lower bound, so merge it with our existing lower bound. | 1583 // T1 is a lower bound, so merge it with our existing lower bound. |
1585 // | 1584 // |
1586 // We already know L <: T2, for some L. | 1585 // We already know L <: T2, for some L. |
1587 // So update L to reflect the new constraint LUB(L, T1) <: T2 | 1586 // So update L to reflect the new constraint LUB(L, T1) <: T2 |
1588 // | 1587 // |
1589 bound.lower = _typeSystem.getLeastUpperBound(bound.lower, t1); | 1588 bound.lower = _typeSystem.getLeastUpperBound(bound.lower, t1); |
1590 // Optimistically assume we will be able to satisfy the constraint. | 1589 // Optimistically assume we will be able to satisfy the constraint. |
1591 return true; | 1590 return true; |
1592 } | 1591 } |
1593 } | 1592 } |
1594 return false; | 1593 return super |
1594 ._isSubtypeOf(t1, t2, visited, dynamicIsBottom: dynamicIsBottom); | |
1595 } | 1595 } |
1596 } | 1596 } |
1597 | 1597 |
1598 /// An [upper] and [lower] bound for a type variable. | 1598 /// An [upper] and [lower] bound for a type variable. |
1599 class _TypeParameterBound { | 1599 class _TypeParameterBound { |
1600 /// The upper bound of the type parameter. In other words, T <: upperBound. | 1600 /// The upper bound of the type parameter. In other words, T <: upperBound. |
1601 /// | 1601 /// |
1602 /// In Dart this can be written as `<T extends UpperBoundType>`. | 1602 /// In Dart this can be written as `<T extends UpperBoundType>`. |
1603 /// | 1603 /// |
1604 /// In inference, this can happen as a result of parameters of function type. | 1604 /// In inference, this can happen as a result of parameters of function type. |
(...skipping 93 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1698 } else { | 1698 } else { |
1699 passedOut = true; | 1699 passedOut = true; |
1700 } | 1700 } |
1701 } else if (type is FunctionType) { | 1701 } else if (type is FunctionType) { |
1702 _visitFunctionType(typeParam, type, paramIn); | 1702 _visitFunctionType(typeParam, type, paramIn); |
1703 } else if (type is InterfaceType) { | 1703 } else if (type is InterfaceType) { |
1704 _visitInterfaceType(typeParam, type, paramIn); | 1704 _visitInterfaceType(typeParam, type, paramIn); |
1705 } | 1705 } |
1706 } | 1706 } |
1707 } | 1707 } |
OLD | NEW |