Don't infer types when there's an irreconcilable type mismatch.
Also fix the type inference algorithm so that when it explores
multiple alternatives (as a result of the use of FutureOr<>), if one
alternative generated some constraints but failed to produce a match,
it rewinds those constraints and tries the other alternative.
(Previously, it erroneously assumed that if any constraints were
generated, the alternative matched successfully).
Also add unit tests to verify the proper operation of the subtype
match algorithm.
Fixes #32305.
Change-Id: I060b5d6d5247a68d2b27bba78819bae172e43d97
Reviewed-on: https://dart-review.googlesource.com/53685
Commit-Queue: Paul Berry <paulberry@google.com>
Reviewed-by: Jenny Messerly <jmesserly@google.com>
diff --git a/pkg/analyzer/lib/src/generated/type_system.dart b/pkg/analyzer/lib/src/generated/type_system.dart
index 7c76550..068294a 100644
--- a/pkg/analyzer/lib/src/generated/type_system.dart
+++ b/pkg/analyzer/lib/src/generated/type_system.dart
@@ -20,6 +20,7 @@
show AnalysisContext, AnalysisOptionsImpl;
import 'package:analyzer/src/generated/resolver.dart' show TypeProvider;
import 'package:analyzer/src/generated/utilities_dart.dart' show ParameterKind;
+import 'package:meta/meta.dart';
/**
* `void`, `dynamic`, and `Object` are all equivalent. However, this makes
@@ -233,7 +234,7 @@
// inferred. It will optimistically assume these type parameters can be
// subtypes (or supertypes) as necessary, and track the constraints that
// are implied by this.
- var inferrer = new _GenericInferrer(typeProvider, this, fnType.typeFormals);
+ var inferrer = new GenericInferrer(typeProvider, this, fnType.typeFormals);
inferrer.constrainGenericFunctionInContext(fnType, contextType);
// Infer and instantiate the resulting type.
@@ -280,7 +281,7 @@
// inferred. It will optimistically assume these type parameters can be
// subtypes (or supertypes) as necessary, and track the constraints that
// are implied by this.
- var inferrer = new _GenericInferrer(typeProvider, this, typeFormals);
+ var inferrer = new GenericInferrer(typeProvider, this, typeFormals);
DartType declaredReturnType =
genericType is FunctionType ? genericType.returnType : genericType;
@@ -1231,7 +1232,7 @@
InterfaceType matchSupertypeConstraints(
ClassElement mixinElement, List<DartType> srcs, List<DartType> dests) {
var typeParameters = mixinElement.typeParameters;
- var inferrer = new _GenericInferrer(typeProvider, this, typeParameters);
+ var inferrer = new GenericInferrer(typeProvider, this, typeParameters);
for (int i = 0; i < srcs.length; i++) {
inferrer.constrainReturnType(srcs[i], dests[i]);
inferrer.constrainReturnType(dests[i], srcs[i]);
@@ -1682,25 +1683,23 @@
///
/// As currently designed, an instance of this class should only be used to
/// infer a single call and discarded immediately afterwards.
-class _GenericInferrer {
+class GenericInferrer {
final StrongTypeSystemImpl _typeSystem;
final TypeProvider typeProvider;
- final Map<TypeParameterElement, List<_TypeConstraint>> _constraints;
+ final Map<TypeParameterElement, List<_TypeConstraint>> constraints;
- /// Counter internally by [_matchSubtypeOf] to see if a recursive call
- /// added anything to [_constraints].
- ///
- /// Essentially just an optimization for:
- /// `_constraints.values.expand((x) => x).length`
- int _constraintCount = 0;
+ /// Buffer recording constraints recorded while performing a recursive call to
+ /// [_matchSubtypeOf] that might fail, so that any constraints recorded during
+ /// the failed match can be rewound.
+ final _undoBuffer = <_TypeConstraint>[];
- _GenericInferrer(this.typeProvider, this._typeSystem,
+ GenericInferrer(this.typeProvider, this._typeSystem,
Iterable<TypeParameterElement> typeFormals)
- : _constraints = new HashMap(
+ : constraints = new HashMap(
equals: (x, y) => x.location == y.location,
hashCode: (x) => x.location.hashCode) {
for (var formal in typeFormals) {
- _constraints[formal] = [];
+ constraints[formal] = [];
}
}
@@ -1712,8 +1711,7 @@
var origin = new _TypeConstraintFromArgument(
argumentType, parameterType, parameterName,
genericType: genericType);
- _matchSubtypeOf(argumentType, parameterType, null, origin,
- covariant: false);
+ tryMatchSubtypeOf(argumentType, parameterType, origin, covariant: false);
}
/// Constrain a universal function type [fnType] used in a context
@@ -1726,14 +1724,14 @@
// formals as we check the parameters and return type.
var inferFnType =
fnType.instantiate(TypeParameterTypeImpl.getTypes(fnType.typeFormals));
- _matchSubtypeOf(inferFnType, contextType, null, origin, covariant: true);
+ tryMatchSubtypeOf(inferFnType, contextType, origin, covariant: true);
}
/// Apply a return type constraint, which asserts that the [declaredType]
/// is a subtype of the [contextType].
void constrainReturnType(DartType declaredType, DartType contextType) {
var origin = new _TypeConstraintFromReturnType(declaredType, contextType);
- _matchSubtypeOf(declaredType, contextType, null, origin, covariant: true);
+ tryMatchSubtypeOf(declaredType, contextType, origin, covariant: true);
}
/// Given the constraints that were given by calling [isSubtypeOf], find the
@@ -1772,8 +1770,8 @@
typeParam.bound.substitute2(inferredTypes, fnTypeParams));
}
- var constraints = _constraints[typeParam.element];
- inferredTypes[i] = _inferTypeParameter(constraints, extendsClause);
+ inferredTypes[i] =
+ _inferTypeParameter(constraints[typeParam.element], extendsClause);
}
// If the downwards infer phase has failed, we'll catch this in the upwards
@@ -1788,7 +1786,7 @@
hashCode: (x) => x.element.hashCode);
for (int i = 0; i < fnTypeParams.length; i++) {
TypeParameterType typeParam = fnTypeParams[i];
- var constraints = _constraints[typeParam.element];
+ var constraints = this.constraints[typeParam.element];
var typeParamBound =
typeParam.bound.substitute2(inferredTypes, fnTypeParams);
@@ -2019,11 +2017,16 @@
return t;
}
- void _matchInterfaceSubtypeOf(InterfaceType i1, InterfaceType i2,
+ /// Tries to make [i1] a subtype of [i2] and accumulate constraints as needed.
+ ///
+ /// The return value indicates whether the match was successful. If it was
+ /// unsuccessful, the caller is responsible for ignoring any constraints that
+ /// were accumulated (see [_rewindConstraints]).
+ bool _matchInterfaceSubtypeOf(InterfaceType i1, InterfaceType i2,
Set<Element> visited, _TypeConstraintOrigin origin,
{bool covariant}) {
if (identical(i1, i2)) {
- return;
+ return true;
}
if (i1.element == i2.element) {
@@ -2031,13 +2034,15 @@
List<DartType> tArgs2 = i2.typeArguments;
assert(tArgs1.length == tArgs2.length);
for (int i = 0; i < tArgs1.length; i++) {
- _matchSubtypeOf(tArgs1[i], tArgs2[i], visited, origin,
- covariant: covariant);
+ if (!_matchSubtypeOf(tArgs1[i], tArgs2[i], visited, origin,
+ covariant: covariant)) {
+ return false;
+ }
}
- return;
+ return true;
}
if (i1.isObject) {
- return;
+ return false;
}
// Guard against loops in the class hierarchy
@@ -2051,21 +2056,49 @@
// The fix is for type arguments (above) to not pass down `visited`, similar
// to how _isInterfaceSubtypeOf does not pass down `visited` for type
// arguments.
- void guardedInterfaceSubtype(InterfaceType t1) {
+ bool guardedInterfaceSubtype(InterfaceType t1) {
var visitedSet = visited ?? new HashSet<Element>();
if (visitedSet.add(t1.element)) {
- _matchInterfaceSubtypeOf(t1, i2, visited, origin, covariant: covariant);
+ bool matched = _matchInterfaceSubtypeOf(t1, i2, visited, origin,
+ covariant: covariant);
visitedSet.remove(t1.element);
+ return matched;
+ } else {
+ // In the case of a recursive type parameter, consider the subtype
+ // match to have failed.
+ return false;
}
}
- guardedInterfaceSubtype(i1.superclass);
+ // We don't need to search the entire class hierarchy, since a given
+ // subclass can't appear multiple times with different generic parameters.
+ // So shortcut to the first match found.
+ //
+ // We don't need undo logic here because if the classes don't match, nothing
+ // is added to the constraint set.
+ if (guardedInterfaceSubtype(i1.superclass)) return true;
for (final parent in i1.interfaces) {
- guardedInterfaceSubtype(parent);
+ if (guardedInterfaceSubtype(parent)) return true;
}
for (final parent in i1.mixins) {
- guardedInterfaceSubtype(parent);
+ if (guardedInterfaceSubtype(parent)) return true;
}
+ return false;
+ }
+
+ /// Tries to make [i1] a subtype of [i2] and accumulate constraints as needed.
+ ///
+ /// The return value indicates whether the match was successful. If it was
+ /// unsuccessful, any constraints that were accumulated during the match
+ /// attempt have been rewound (see [_rewindConstraints]).
+ bool tryMatchSubtypeOf(DartType t1, DartType t2, _TypeConstraintOrigin origin,
+ {bool covariant}) {
+ int previousRewindBufferLength = _undoBuffer.length;
+ bool success = _matchSubtypeOf(t1, t2, null, origin, covariant: covariant);
+ if (!success) {
+ _rewindConstraints(previousRewindBufferLength);
+ }
+ return success;
}
/// Assert that [t1] will be a subtype of [t2], and returns if the constraint
@@ -2080,37 +2113,39 @@
///
/// [origin] indicates where the constraint came from, for example an argument
/// or return type.
- void _matchSubtypeOf(DartType t1, DartType t2, Set<Element> visited,
+ bool _matchSubtypeOf(DartType t1, DartType t2, Set<Element> visited,
_TypeConstraintOrigin origin,
{bool covariant}) {
if (covariant && t1 is TypeParameterType) {
- var constraints = _constraints[t1.element];
+ var constraints = this.constraints[t1.element];
if (constraints != null) {
if (!identical(t2, UnknownInferredType.instance)) {
- constraints.add(new _TypeConstraint(origin, t1, upper: t2));
- _constraintCount++;
+ var constraint = new _TypeConstraint(origin, t1, upper: t2);
+ constraints.add(constraint);
+ _undoBuffer.add(constraint);
}
- return;
+ return true;
}
}
if (!covariant && t2 is TypeParameterType) {
- var constraints = _constraints[t2.element];
+ var constraints = this.constraints[t2.element];
if (constraints != null) {
if (!identical(t1, UnknownInferredType.instance)) {
- constraints.add(new _TypeConstraint(origin, t2, lower: t1));
- _constraintCount++;
+ var constraint = new _TypeConstraint(origin, t2, lower: t1);
+ constraints.add(constraint);
+ _undoBuffer.add(constraint);
}
- return;
+ return true;
}
}
if (identical(t1, t2)) {
- return;
+ return true;
}
// TODO(jmesserly): this logic is taken from subtype.
- void matchSubtype(DartType t1, DartType t2) {
- _matchSubtypeOf(t1, t2, null, origin, covariant: covariant);
+ bool matchSubtype(DartType t1, DartType t2) {
+ return _matchSubtypeOf(t1, t2, null, origin, covariant: covariant);
}
// Handle FutureOr<T> union type.
@@ -2119,16 +2154,13 @@
if (t2 is InterfaceType && t2.isDartAsyncFutureOr) {
var t2TypeArg = t2.typeArguments[0];
// FutureOr<A> <: FutureOr<B> iff A <: B
- matchSubtype(t1TypeArg, t2TypeArg);
- return;
+ return matchSubtype(t1TypeArg, t2TypeArg);
}
// given t1 is Future<A> | A, then:
// (Future<A> | A) <: t2 iff Future<A> <: t2 and A <: t2.
var t1Future = typeProvider.futureType.instantiate([t1TypeArg]);
- matchSubtype(t1Future, t2);
- matchSubtype(t1TypeArg, t2);
- return;
+ return matchSubtype(t1Future, t2) && matchSubtype(t1TypeArg, t2);
}
if (t2 is InterfaceType && t2.isDartAsyncFutureOr) {
@@ -2137,16 +2169,36 @@
var t2TypeArg = t2.typeArguments[0];
var t2Future = typeProvider.futureType.instantiate([t2TypeArg]);
- int constraintCount = _constraintCount;
- matchSubtype(t1, t2Future);
+ // First we try matching `t1 <: Future<A>`. If that succeeds *and*
+ // records at least one constraint, then we proceed using that constraint.
+ var previousRewindBufferLength = _undoBuffer.length;
+ var success =
+ tryMatchSubtypeOf(t1, t2Future, origin, covariant: covariant);
- // We only want to record these as "or" constraints, so if we matched
- // the `t1 <: Future<A>` constraint, don't add `t1 <: A` constraint, as
- // that would be interpreted incorrectly as `t1 <: Future<A> && t1 <: A`.
- if (constraintCount == _constraintCount) {
- matchSubtype(t1, t2TypeArg);
+ if (_undoBuffer.length != previousRewindBufferLength) {
+ // Trying to match `t1 <: Future<A>` succeeded and recorded constraints,
+ // so those are the constraints we want.
+ return true;
+ } else {
+ // Either `t1 <: Future<A>` failed to match, or it matched trivially
+ // without recording any constraints (e.g. because t1 is `Null`). We
+ // want constraints, because they let us do more precise inference, so
+ // go ahead and try matching `t1 <: A` to see if it records any
+ // constraints.
+ if (tryMatchSubtypeOf(t1, t2TypeArg, origin, covariant: covariant)) {
+ // Trying to match `t1 <: A` succeeded. If it recorded constraints,
+ // those are the constraints we want. If it didn't, then there's no
+ // way we're going to get any constraints. So either way, we want to
+ // return `true` since the match suceeded and the constraints we want
+ // (if any) have been recorded.
+ return true;
+ } else {
+ // Trying to match `t1 <: A` failed. So there's no way we are going
+ // to get any constraints. Just return `success` to indicate whether
+ // the match succeeded.
+ return success;
+ }
}
- return;
}
// S <: T where S is a type variable
@@ -2159,47 +2211,72 @@
//
// TODO(jmesserly): this function isn't guarding against anything (it's
// not passsing down `visitedSet`, so adding the element has no effect).
- void guardedSubtype(DartType t1, DartType t2) {
+ bool guardedSubtype(DartType t1, DartType t2) {
var visitedSet = visited ?? new HashSet<Element>();
if (visitedSet.add(t1.element)) {
- matchSubtype(t1, t2);
+ bool matched = matchSubtype(t1, t2);
visitedSet.remove(t1.element);
+ return matched;
+ } else {
+ // In the case of a recursive type parameter, consider the subtype
+ // match to have failed.
+ return false;
}
}
if (t2 is TypeParameterType && t1.definition == t2.definition) {
- guardedSubtype(t1.bound, t2.bound);
- return;
+ return guardedSubtype(t1.bound, t2.bound);
}
- guardedSubtype(t1.bound, t2);
- return;
+ return guardedSubtype(t1.bound, t2);
}
if (t2 is TypeParameterType) {
- return;
+ return false;
}
+ if (_isBottom(t1) || _isTop(t2)) return true;
+
if (t1 is InterfaceType && t2 is InterfaceType) {
- _matchInterfaceSubtypeOf(t1, t2, visited, origin, covariant: covariant);
- return;
+ return _matchInterfaceSubtypeOf(t1, t2, visited, origin,
+ covariant: covariant);
}
if (t1 is FunctionType && t2 is FunctionType) {
- FunctionTypeImpl.relate(
+ return FunctionTypeImpl.relate(
t1,
t2,
(t1, t2) {
// TODO(jmesserly): should we flip covariance when we're relating
// type formal bounds? They're more like parameters.
- matchSubtype(t1, t2);
- return true;
+ return matchSubtype(t1, t2);
},
_typeSystem.instantiateToBounds,
parameterRelation: (p1, p2) {
- _matchSubtypeOf(p2.type, p1.type, null, origin,
+ return _matchSubtypeOf(p2.type, p1.type, null, origin,
covariant: !covariant);
- return true;
});
}
+
+ if (t1 is FunctionType && t2 == typeProvider.functionType) {
+ return true;
+ }
+
+ return false;
+ }
+
+ /// Un-does constraints that were gathered by a failed match attempt, until
+ /// [_undoBuffer] has length [previousRewindBufferLength].
+ ///
+ /// The intended usage is that the caller should record the length of
+ /// [_undoBuffer] before attempting to make a match. Then, if the match
+ /// fails, pass the recorded length to this method to erase any constraints
+ /// that were recorded during the failed match.
+ void _rewindConstraints(int previousRewindBufferLength) {
+ while (_undoBuffer.length > previousRewindBufferLength) {
+ var constraint = _undoBuffer.removeLast();
+ var element = constraint.typeParameter.element;
+ assert(identical(constraints[element].last, constraint));
+ constraints[element].removeLast();
+ }
}
static String _formatConstraints(Iterable<_TypeConstraint> constraints) {
@@ -2393,4 +2470,22 @@
_TypeRange({DartType lower, DartType upper})
: lowerBound = lower ?? UnknownInferredType.instance,
upperBound = upper ?? UnknownInferredType.instance;
+
+ /// Formats the typeRange as a string suitable for unit testing.
+ ///
+ /// For example, if [typeName] is 'T' and the range has bounds int and Object
+ /// respectively, the returned string will be 'int <: T <: Object'.
+ @visibleForTesting
+ String format(String typeName) {
+ var lowerString = identical(lowerBound, UnknownInferredType.instance)
+ ? ''
+ : '$lowerBound <: ';
+ var upperString = identical(upperBound, UnknownInferredType.instance)
+ ? ''
+ : ' <: $upperBound';
+ return '$lowerString$typeName$upperString';
+ }
+
+ @override
+ String toString() => format('(type)');
}
diff --git a/pkg/analyzer/test/generated/type_system_test.dart b/pkg/analyzer/test/generated/type_system_test.dart
index da90947..fbc3eba 100644
--- a/pkg/analyzer/test/generated/type_system_test.dart
+++ b/pkg/analyzer/test/generated/type_system_test.dart
@@ -6,7 +6,8 @@
library analyzer.test.generated.type_system_test;
-import 'package:analyzer/analyzer.dart' show ErrorReporter, StrongModeCode;
+import 'package:analyzer/analyzer.dart'
+ show ErrorReporter, ParameterKind, StrongModeCode;
import 'package:analyzer/dart/ast/standard_ast_factory.dart' show astFactory;
import 'package:analyzer/dart/ast/token.dart' show Keyword;
import 'package:analyzer/dart/element/element.dart';
@@ -28,6 +29,7 @@
main() {
defineReflectiveSuite(() {
+ defineReflectiveTests(ConstraintMatchingTest);
defineReflectiveTests(StrongAssignabilityTest);
defineReflectiveTests(StrongSubtypingTest);
defineReflectiveTests(StrongGenericFunctionInferenceTest);
@@ -133,6 +135,354 @@
}
}
+@reflectiveTest
+class ConstraintMatchingTest {
+ TypeProvider typeProvider;
+ TypeSystem typeSystem;
+ TypeParameterType T;
+
+ DartType get dynamicType => DynamicTypeImpl.instance;
+
+ InterfaceType get functionType => typeProvider.functionType;
+
+ InterfaceType get intType => typeProvider.intType;
+
+ InterfaceType get nullType => typeProvider.nullType;
+
+ InterfaceType get objectType => typeProvider.objectType;
+
+ InterfaceType get stringType => typeProvider.stringType;
+
+ DartType get voidType => VoidTypeImpl.instance;
+
+ DartType fn(DartType paramType, DartType returnType) =>
+ new FunctionElementImpl.synthetic([
+ new ParameterElementImpl.synthetic(
+ 'value', paramType, ParameterKind.REQUIRED)
+ ], returnType)
+ .type;
+
+ DartType future(DartType T) => typeProvider.futureType.instantiate([T]);
+
+ DartType futureOr(DartType T) => typeProvider.futureOrType.instantiate([T]);
+
+ DartType iterable(DartType T) => typeProvider.iterableType.instantiate([T]);
+
+ DartType list(DartType T) => typeProvider.listType.instantiate([T]);
+
+ void setUp() {
+ typeProvider = AnalysisContextFactory.contextWithCore().typeProvider;
+ typeSystem = new StrongTypeSystemImpl(typeProvider);
+ T = _newTypeParameter('T');
+ }
+
+ void test_function_coreFunction() {
+ _checkOrdinarySubtypeMatch(fn(intType, stringType), functionType, [T],
+ covariant: true);
+ }
+
+ void test_function_parameter_types() {
+ _checkIsSubtypeMatchOf(
+ fn(T, intType), fn(stringType, intType), [T], ['String <: T'],
+ covariant: true);
+ }
+
+ void test_function_return_types() {
+ _checkIsSubtypeMatchOf(
+ fn(intType, T), fn(intType, stringType), [T], ['T <: String'],
+ covariant: true);
+ }
+
+ void test_futureOr_futureOr() {
+ _checkIsSubtypeMatchOf(
+ futureOr(T), futureOr(stringType), [T], ['T <: String'],
+ covariant: true);
+ }
+
+ void test_futureOr_x_fail_future_branch() {
+ // FutureOr<List<T>> <: List<String> can't be satisfied because
+ // Future<List<T>> <: List<String> can't be satisfied
+ _checkIsNotSubtypeMatchOf(futureOr(list(T)), list(stringType), [T],
+ covariant: true);
+ }
+
+ void test_futureOr_x_fail_nonFuture_branch() {
+ // FutureOr<List<T>> <: Future<List<String>> can't be satisfied because
+ // List<T> <: Future<List<String>> can't be satisfied
+ _checkIsNotSubtypeMatchOf(futureOr(list(T)), future(list(stringType)), [T],
+ covariant: true);
+ }
+
+ void test_futureOr_x_success() {
+ // FutureOr<T> <: Future<T> can be satisfied by T=Null. At this point in
+ // the type inference algorithm all we figure out is that T must be a
+ // subtype of both String and Future<String>.
+ _checkIsSubtypeMatchOf(futureOr(T), future(stringType), [T],
+ ['T <: String', 'T <: Future<String>'],
+ covariant: true);
+ }
+
+ void test_lhs_null() {
+ // Null <: T is trivially satisfied by the constraint Null <: T.
+ _checkIsSubtypeMatchOf(nullType, T, [T], ['Null <: T'], covariant: false);
+ // For any other type X, Null <: X is satisfied without the need for any
+ // constraints.
+ _checkOrdinarySubtypeMatch(nullType, list(T), [T], covariant: false);
+ _checkOrdinarySubtypeMatch(nullType, stringType, [T], covariant: false);
+ _checkOrdinarySubtypeMatch(nullType, voidType, [T], covariant: false);
+ _checkOrdinarySubtypeMatch(nullType, dynamicType, [T], covariant: false);
+ _checkOrdinarySubtypeMatch(nullType, objectType, [T], covariant: false);
+ _checkOrdinarySubtypeMatch(nullType, nullType, [T], covariant: false);
+ _checkOrdinarySubtypeMatch(nullType, fn(intType, stringType), [T],
+ covariant: false);
+ }
+
+ void test_param_on_lhs_contravariant_direct() {
+ // When doing a contravariant match, the type parameters we're trying to
+ // find types for are on the right hand side. Is a type parameter also
+ // appears on the left hand side, there is a condition in which the
+ // constraint can be satisfied without consulting the bound of the LHS type
+ // parameter: the condition where both parameters appear at corresponding
+ // locations in the type tree.
+ //
+ // In other words, List<S> <: List<T> is satisfied provided that
+ // S <: T.
+ var S = _newTypeParameter('S');
+ _checkIsSubtypeMatchOf(list(S), list(T), [T], ['S <: T'], covariant: false);
+ }
+
+ void test_param_on_lhs_contravariant_via_bound() {
+ // When doing a contravariant match, the type parameters we're trying to
+ // find types for are on the right hand side. Is a type parameter also
+ // appears on the left hand side, we may have to constrain the RHS type
+ // parameter using the bounds of the LHS type parameter.
+ //
+ // In other words, S <: List<T> is satisfied provided that
+ // bound(S) <: List<T>.
+ var S = _newTypeParameter('S', list(stringType));
+ _checkIsSubtypeMatchOf(S, list(T), [T], ['String <: T'], covariant: false);
+ }
+
+ void test_param_on_lhs_covariant() {
+ // When doing a covariant match, the type parameters we're trying to find
+ // types for are on the left hand side.
+ _checkIsSubtypeMatchOf(T, stringType, [T], ['T <: String'],
+ covariant: true);
+ }
+
+ void test_param_on_rhs_contravariant() {
+ // When doing a contravariant match, the type parameters we're trying to
+ // find types for are on the right hand side.
+ _checkIsSubtypeMatchOf(stringType, T, [T], ['String <: T'],
+ covariant: false);
+ }
+
+ void test_param_on_rhs_covariant_match() {
+ // When doing a covariant match, the type parameters we're trying to find
+ // types for are on the left hand side. If a type parameter appears on the
+ // right hand side, there is a condition in which the constraint can be
+ // satisfied: where both parameters appear at corresponding locations in the
+ // type tree.
+ //
+ // In other words, T <: S can be satisfied trivially by the constraint
+ // T <: S.
+ var S = _newTypeParameter('S');
+ _checkIsSubtypeMatchOf(T, S, [T], ['T <: S'], covariant: true);
+ }
+
+ void test_param_on_rhs_covariant_no_match() {
+ // When doing a covariant match, the type parameters we're trying to find
+ // types for are on the left hand side. If a type parameter appears on the
+ // right hand side, it's probable that the constraint can't be satisfied,
+ // because there is no possible type for the LHS (other than bottom)
+ // that's guaranteed to satisfy the relation for all possible assignments of
+ // the RHS type parameter.
+ //
+ // In other words, no match can be found for List<T> <: S because regardless
+ // of T, we can't guarantee that List<T> <: S for all S.
+ var S = _newTypeParameter('S');
+ _checkIsNotSubtypeMatchOf(list(T), S, [T], covariant: true);
+ }
+
+ void test_related_interface_types_failure() {
+ _checkIsNotSubtypeMatchOf(iterable(T), list(stringType), [T],
+ covariant: true);
+ }
+
+ void test_related_interface_types_success() {
+ _checkIsSubtypeMatchOf(list(T), iterable(stringType), [T], ['T <: String'],
+ covariant: true);
+ }
+
+ void test_rhs_dynamic() {
+ // T <: dynamic is trivially satisfied by the constraint T <: dynamic.
+ _checkIsSubtypeMatchOf(T, dynamicType, [T], ['T <: dynamic'],
+ covariant: true);
+ // For any other type X, X <: dynamic is satisfied without the need for any
+ // constraints.
+ _checkOrdinarySubtypeMatch(list(T), dynamicType, [T], covariant: true);
+ _checkOrdinarySubtypeMatch(stringType, dynamicType, [T], covariant: true);
+ _checkOrdinarySubtypeMatch(voidType, dynamicType, [T], covariant: true);
+ _checkOrdinarySubtypeMatch(dynamicType, dynamicType, [T], covariant: true);
+ _checkOrdinarySubtypeMatch(objectType, dynamicType, [T], covariant: true);
+ _checkOrdinarySubtypeMatch(nullType, dynamicType, [T], covariant: true);
+ _checkOrdinarySubtypeMatch(fn(intType, stringType), dynamicType, [T],
+ covariant: true);
+ }
+
+ void test_rhs_object() {
+ // T <: Object is trivially satisfied by the constraint T <: Object.
+ _checkIsSubtypeMatchOf(T, objectType, [T], ['T <: Object'],
+ covariant: true);
+ // For any other type X, X <: Object is satisfied without the need for any
+ // constraints.
+ _checkOrdinarySubtypeMatch(list(T), objectType, [T], covariant: true);
+ _checkOrdinarySubtypeMatch(stringType, objectType, [T], covariant: true);
+ _checkOrdinarySubtypeMatch(voidType, objectType, [T], covariant: true);
+ _checkOrdinarySubtypeMatch(dynamicType, objectType, [T], covariant: true);
+ _checkOrdinarySubtypeMatch(objectType, objectType, [T], covariant: true);
+ _checkOrdinarySubtypeMatch(nullType, objectType, [T], covariant: true);
+ _checkOrdinarySubtypeMatch(fn(intType, stringType), objectType, [T],
+ covariant: true);
+ }
+
+ void test_rhs_void() {
+ // T <: void is trivially satisfied by the constraint T <: void.
+ _checkIsSubtypeMatchOf(T, voidType, [T], ['T <: void'], covariant: true);
+ // For any other type X, X <: void is satisfied without the need for any
+ // constraints.
+ _checkOrdinarySubtypeMatch(list(T), voidType, [T], covariant: true);
+ _checkOrdinarySubtypeMatch(stringType, voidType, [T], covariant: true);
+ _checkOrdinarySubtypeMatch(voidType, voidType, [T], covariant: true);
+ _checkOrdinarySubtypeMatch(dynamicType, voidType, [T], covariant: true);
+ _checkOrdinarySubtypeMatch(objectType, voidType, [T], covariant: true);
+ _checkOrdinarySubtypeMatch(nullType, voidType, [T], covariant: true);
+ _checkOrdinarySubtypeMatch(fn(intType, stringType), voidType, [T],
+ covariant: true);
+ }
+
+ void test_same_interface_types() {
+ _checkIsSubtypeMatchOf(list(T), list(stringType), [T], ['T <: String'],
+ covariant: true);
+ }
+
+ void test_x_futureOr_fail_both_branches() {
+ // List<T> <: FutureOr<String> can't be satisfied because neither
+ // List<T> <: Future<String> nor List<T> <: int can be satisfied
+ _checkIsNotSubtypeMatchOf(list(T), futureOr(stringType), [T],
+ covariant: true);
+ }
+
+ void test_x_futureOr_pass_both_branches_constraints_from_both_branches() {
+ // Future<String> <: FutureOr<T> can be satisfied because both
+ // Future<String> <: Future<T> and Future<String> <: T can be satisfied.
+ // Trying to match Future<String> <: Future<T> generates the constraint
+ // String <: T, whereas trying to match Future<String> <: T generates the
+ // constraint Future<String> <: T. We keep the constraint based on trying
+ // to match Future<String> <: Future<T>, so String <: T.
+ _checkIsSubtypeMatchOf(
+ future(stringType), futureOr(T), [T], ['String <: T'],
+ covariant: false);
+ }
+
+ void test_x_futureOr_pass_both_branches_constraints_from_future_branch() {
+ // Future<T> <: FutureOr<Object> can be satisfied because both
+ // Future<T> <: Future<Object> and Future<T> <: Object can be satisfied.
+ // Trying to match Future<T> <: Future<Object> generates the constraint
+ // T <: Object, whereas trying to match Future<T> <: Object generates no
+ // constraints, so we keep the constraint T <: Object.
+ _checkIsSubtypeMatchOf(
+ future(T), futureOr(objectType), [T], ['T <: Object'],
+ covariant: true);
+ }
+
+ void test_x_futureOr_pass_both_branches_constraints_from_nonFuture_branch() {
+ // Null <: FutureOr<T> can be satisfied because both
+ // Null <: Future<T> and Null <: T can be satisfied.
+ // Trying to match Null <: FutureOr<T> generates no constraints, whereas
+ // trying to match Null <: T generates the constraint Null <: T,
+ // so we keep the constraint Null <: T.
+ _checkIsSubtypeMatchOf(nullType, futureOr(T), [T], ['Null <: T'],
+ covariant: false);
+ }
+
+ void test_x_futureOr_pass_both_branches_no_constraints() {
+ // Future<String> <: FutureOr<Object> is satisfied because both
+ // Future<String> <: Future<Object> and Future<String> <: Object.
+ // No constraints are recorded.
+ _checkIsSubtypeMatchOf(future(stringType), futureOr(objectType), [T], [],
+ covariant: true);
+ }
+
+ void test_x_futureOr_pass_future_branch() {
+ // Future<T> <: FutureOr<String> can be satisfied because
+ // Future<T> <: Future<String> can be satisfied
+ _checkIsSubtypeMatchOf(
+ future(T), futureOr(stringType), [T], ['T <: String'],
+ covariant: true);
+ }
+
+ void test_x_futureOr_pass_nonFuture_branch() {
+ // List<T> <: FutureOr<List<String>> can be satisfied because
+ // List<T> <: List<String> can be satisfied
+ _checkIsSubtypeMatchOf(
+ list(T), futureOr(list(stringType)), [T], ['T <: String'],
+ covariant: true);
+ }
+
+ void _checkIsNotSubtypeMatchOf(
+ DartType t1, DartType t2, Iterable<TypeParameterType> typeFormals,
+ {bool covariant}) {
+ var inferrer = new GenericInferrer(
+ typeProvider, typeSystem, typeFormals.map((t) => t.element));
+ var success =
+ inferrer.tryMatchSubtypeOf(t1, t2, null, covariant: covariant);
+ expect(success, isFalse);
+ inferrer.constraints.forEach((typeParameter, constraintsForTypeParameter) {
+ expect(constraintsForTypeParameter, isEmpty);
+ });
+ }
+
+ void _checkIsSubtypeMatchOf(
+ DartType t1,
+ DartType t2,
+ Iterable<TypeParameterType> typeFormals,
+ Iterable<String> expectedConstraints,
+ {bool covariant}) {
+ var inferrer = new GenericInferrer(
+ typeProvider, typeSystem, typeFormals.map((t) => t.element));
+ var success =
+ inferrer.tryMatchSubtypeOf(t1, t2, null, covariant: covariant);
+ expect(success, isTrue);
+ var formattedConstraints = <String>[];
+ inferrer.constraints.forEach((typeParameter, constraintsForTypeParameter) {
+ for (var constraint in constraintsForTypeParameter) {
+ formattedConstraints.add(constraint.format(typeParameter.toString()));
+ }
+ });
+ expect(formattedConstraints, unorderedEquals(expectedConstraints));
+ }
+
+ void _checkOrdinarySubtypeMatch(
+ DartType t1, DartType t2, Iterable<TypeParameterType> typeFormals,
+ {bool covariant}) {
+ bool expectSuccess = typeSystem.isSubtypeOf(t1, t2);
+ if (expectSuccess) {
+ _checkIsSubtypeMatchOf(t1, t2, typeFormals, [], covariant: covariant);
+ } else {
+ _checkIsNotSubtypeMatchOf(t1, t2, typeFormals);
+ }
+ }
+
+ TypeParameterType _newTypeParameter(String name, [DartType bound]) {
+ var element = new TypeParameterElementImpl(name, 0);
+ if (bound != null) {
+ element.bound = bound;
+ }
+ return new TypeParameterTypeImpl(element);
+ }
+}
+
/**
* Tests LUB in spec mode.
*
@@ -1044,13 +1394,13 @@
}
void test_returnFunctionWithGenericParameterAndContext() {
- // <T>(T -> T) -> (T -> void)
+ // <T>(T -> T) -> (T -> Null)
var t = TypeBuilder.variable('T');
var f = TypeBuilder.function(types: [
t
], required: [
TypeBuilder.function(required: [t], result: t)
- ], result: TypeBuilder.function(required: [t], result: voidType));
+ ], result: TypeBuilder.function(required: [t], result: nullType));
expect(
_inferCall(f, [],
returnType:
diff --git a/tests/language_2/bug32305_test.dart b/tests/language_2/bug32305_test.dart
new file mode 100644
index 0000000..5943764
--- /dev/null
+++ b/tests/language_2/bug32305_test.dart
@@ -0,0 +1,10 @@
+// Copyright (c) 2018, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+void main() {
+ int Function(int) f;
+
+ List<num> l = [];
+ /*@compile-error=unspecified*/ var a = l.map(f);
+}
diff --git a/tests/language_2/language_2_analyzer.status b/tests/language_2/language_2_analyzer.status
index 790afc0..748abd0 100644
--- a/tests/language_2/language_2_analyzer.status
+++ b/tests/language_2/language_2_analyzer.status
@@ -1203,6 +1203,7 @@
async_congruence_unnamed_test/01: MissingCompileTimeError
async_congruence_unnamed_test/02: MissingCompileTimeError
black_listed_test/none: Fail # Issue 14228
+bug32305_test: MissingCompileTimeError
built_in_identifier_type_annotation_test/35: MissingCompileTimeError # Issue 28813
built_in_identifier_type_annotation_test/36: MissingCompileTimeError # Issue 28813
built_in_identifier_type_annotation_test/37: MissingCompileTimeError # Issue 28813
diff --git a/tests/language_2/language_2_kernel.status b/tests/language_2/language_2_kernel.status
index 8c9665a..3c51ff8 100644
--- a/tests/language_2/language_2_kernel.status
+++ b/tests/language_2/language_2_kernel.status
@@ -1287,6 +1287,7 @@
abstract_factory_constructor_test/00: MissingCompileTimeError
abstract_getter_test/01: MissingCompileTimeError
abstract_syntax_test/00: MissingCompileTimeError
+bug32305_test: MissingCompileTimeError
call_method_implicit_invoke_local_test/05: MissingCompileTimeError
closure_invoked_through_interface_target_field_test: MissingCompileTimeError
closure_invoked_through_interface_target_getter_test: MissingCompileTimeError
diff --git a/tests/language_2/language_2_precompiled.status b/tests/language_2/language_2_precompiled.status
index a771e2d..1855bda 100644
--- a/tests/language_2/language_2_precompiled.status
+++ b/tests/language_2/language_2_precompiled.status
@@ -87,6 +87,7 @@
bool_check_test: RuntimeError
bool_condition_check_test: RuntimeError
bug31436_test: RuntimeError
+bug32305_test: MissingCompileTimeError
bug32372_test: RuntimeError
built_in_identifier_prefix_test: CompileTimeError
call_constructor_on_unresolvable_class_test/01: MissingCompileTimeError
diff --git a/tests/language_2/language_2_vm.status b/tests/language_2/language_2_vm.status
index b86d7b2..e71bf72 100644
--- a/tests/language_2/language_2_vm.status
+++ b/tests/language_2/language_2_vm.status
@@ -171,6 +171,7 @@
bad_override_test/02: MissingCompileTimeError
bad_override_test/06: MissingCompileTimeError
bug31436_test: RuntimeError
+bug32305_test: MissingCompileTimeError
bug32372_test: RuntimeError
built_in_identifier_prefix_test: CompileTimeError
call_constructor_on_unresolvable_class_test/01: MissingCompileTimeError
