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

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: pkg/analyzer/lib/src/generated/type_system.dart

Issue 2837963003: Fix stack overflow (issue 29406) (Closed)
Patch Set: Created 3 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « no previous file | no next file » | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: pkg/analyzer/lib/src/generated/type_system.dart
diff --git a/pkg/analyzer/lib/src/generated/type_system.dart b/pkg/analyzer/lib/src/generated/type_system.dart
index 1259237e82815d024e0e7b05eb0441004219bff0..991475396708a5602320efbce33741e8b51604c7 100644
--- a/pkg/analyzer/lib/src/generated/type_system.dart
+++ b/pkg/analyzer/lib/src/generated/type_system.dart
@@ -38,13 +38,15 @@ bool _isTop(DartType t, {bool dynamicIsBottom: false}) {
identical(t, UnknownInferredType.instance);
}
-typedef bool _GuardedSubtypeChecker<T>(T t1, T t2, Set<Element> visited);
+typedef bool _GuardedSubtypeChecker<T>(T t1, T t2, Set<TypeImpl> visitedTypes);
/**
* Implementation of [TypeSystem] using the strong mode rules.
* https://github.com/dart-lang/dev_compiler/blob/master/STRONG_MODE.md
*/
class StrongTypeSystemImpl extends TypeSystem {
+ static bool _comparingTypeParameterBounds = false;
+
/**
* True if implicit casts should be allowed, otherwise false.
*
@@ -515,6 +517,15 @@ class StrongTypeSystemImpl extends TypeSystem {
return _isSubtypeOf(leftType, rightType, null);
}
+ /// Given a [type] T that may have an unknown type `?`, returns a type
+ /// R such that R <: T for any type substituted for `?`.
+ ///
+ /// In practice this will always replace `?` with either bottom or top
+ /// (dynamic), depending on the position of `?`.
+ DartType lowerBoundForType(DartType type) {
+ return _substituteForUnknownType(type, lowerBound: true);
+ }
+
@override
DartType refineBinaryExpressionType(DartType leftType, TokenType operator,
DartType rightType, DartType currentType) {
@@ -578,85 +589,15 @@ class StrongTypeSystemImpl extends TypeSystem {
return t;
}
- // Given a [type] T that may have an unknown type `?`, returns a type
- // R such that T <: R for any type substituted for `?`.
- //
- // In practice this will always replace `?` with either bottom or top
- // (dynamic), depending on the position of `?`.
+ /// Given a [type] T that may have an unknown type `?`, returns a type
+ /// R such that T <: R for any type substituted for `?`.
+ ///
+ /// In practice this will always replace `?` with either bottom or top
+ /// (dynamic), depending on the position of `?`.
DartType upperBoundForType(DartType type) {
return _substituteForUnknownType(type);
}
- // Given a [type] T that may have an unknown type `?`, returns a type
- // R such that R <: T for any type substituted for `?`.
- //
- // In practice this will always replace `?` with either bottom or top
- // (dynamic), depending on the position of `?`.
- DartType lowerBoundForType(DartType type) {
- return _substituteForUnknownType(type, lowerBound: true);
- }
-
- DartType _substituteForUnknownType(DartType type,
- {bool lowerBound: false, dynamicIsBottom: false}) {
- if (identical(type, UnknownInferredType.instance)) {
- if (lowerBound && !dynamicIsBottom) {
- // TODO(jmesserly): this should be the bottom type, once i can be
- // reified.
- return typeProvider.nullType;
- }
- return typeProvider.dynamicType;
- }
- if (type is InterfaceTypeImpl) {
- // Generic types are covariant, so keep the constraint direction.
- var newTypeArgs = _transformList(type.typeArguments,
- (t) => _substituteForUnknownType(t, lowerBound: lowerBound));
- if (identical(type.typeArguments, newTypeArgs)) return type;
- return new InterfaceTypeImpl(type.element, type.prunedTypedefs)
- ..typeArguments = newTypeArgs;
- }
- if (type is FunctionType) {
- var parameters = type.parameters;
- var returnType = type.returnType;
- var newParameters = _transformList(parameters, (ParameterElement p) {
- // Parameters are contravariant, so flip the constraint direction.
- // Also pass dynamicIsBottom, because this is a fuzzy arrow.
- var newType = _substituteForUnknownType(p.type,
- lowerBound: !lowerBound, dynamicIsBottom: true);
- return new ParameterElementImpl.synthetic(
- p.name, newType, p.parameterKind);
- });
- // Return type is covariant.
- var newReturnType =
- _substituteForUnknownType(returnType, lowerBound: lowerBound);
- if (identical(parameters, newParameters) &&
- identical(returnType, newReturnType)) {
- return type;
- }
-
- var function = new FunctionElementImpl(type.name, -1)
- ..isSynthetic = true
- ..returnType = newReturnType
- ..shareTypeParameters(type.typeFormals)
- ..parameters = newParameters;
- return function.type = new FunctionTypeImpl(function);
- }
- return type;
- }
-
- static List/*<T>*/ _transformList/*<T>*/(
- List/*<T>*/ list, /*=T*/ f(/*=T*/ t)) {
- List/*<T>*/ newList = null;
- for (var i = 0; i < list.length; i++) {
- var item = list[i];
- var newItem = f(item);
- if (!identical(item, newItem)) {
- newList ??= new List.from(list);
- newList[i] = newItem;
- }
- }
- return newList ?? list;
- }
-
/**
* Compute the greatest lower bound of function types [f] and [g].
*
@@ -780,18 +721,17 @@ class StrongTypeSystemImpl extends TypeSystem {
*/
_GuardedSubtypeChecker<DartType> _guard(
_GuardedSubtypeChecker<DartType> check) {
- return (DartType t1, DartType t2, Set<Element> visited) {
- Element element = t1.element;
- if (visited == null) {
- visited = new HashSet<Element>();
+ return (DartType t1, DartType t2, Set<TypeImpl> visitedTypes) {
+ if (visitedTypes == null) {
+ visitedTypes = new HashSet<TypeImpl>();
}
- if (element == null || !visited.add(element)) {
+ if (t1 == null || !visitedTypes.add(t1)) {
return false;
}
try {
- return check(t1, t2, visited);
+ return check(t1, t2, visitedTypes);
} finally {
- visited.remove(element);
+ visitedTypes.remove(t1);
}
};
}
@@ -847,25 +787,27 @@ class StrongTypeSystemImpl extends TypeSystem {
///
/// This will always assume function types use fuzzy arrows, in other words
/// that dynamic parameters of f1 and f2 are treated as bottom.
- bool _isFunctionSubtypeOf(FunctionType f1, FunctionType f2) {
+ bool _isFunctionSubtypeOf(
+ FunctionType f1, FunctionType f2, Set<TypeImpl> visitedTypes) {
return FunctionTypeImpl.relate(
f1,
f2,
- (t1, t2, _, __) => _isSubtypeOf(t2, t1, null, dynamicIsBottom: true),
+ (t1, t2, _, __) =>
+ _isSubtypeOf(t2, t1, visitedTypes, dynamicIsBottom: true),
instantiateToBounds,
returnRelation: isSubtypeOf);
}
bool _isInterfaceSubtypeOf(
- InterfaceType i1, InterfaceType i2, Set<Element> visited) {
+ InterfaceType i1, InterfaceType i2, Set<TypeImpl> visitedTypes) {
if (identical(i1, i2)) {
return true;
}
// Guard recursive calls
_GuardedSubtypeChecker<InterfaceType> guardedInterfaceSubtype = _guard(
- (DartType i1, DartType i2, Set<Element> visited) =>
- _isInterfaceSubtypeOf(i1, i2, visited));
+ (DartType i1, DartType i2, Set<TypeImpl> visitedTypes) =>
+ _isInterfaceSubtypeOf(i1, i2, visitedTypes));
if (i1.element == i2.element) {
List<DartType> tArgs1 = i1.typeArguments;
@@ -891,18 +833,18 @@ class StrongTypeSystemImpl extends TypeSystem {
return false;
}
- if (guardedInterfaceSubtype(i1.superclass, i2, visited)) {
+ if (guardedInterfaceSubtype(i1.superclass, i2, visitedTypes)) {
return true;
}
for (final parent in i1.interfaces) {
- if (guardedInterfaceSubtype(parent, i2, visited)) {
+ if (guardedInterfaceSubtype(parent, i2, visitedTypes)) {
return true;
}
}
for (final parent in i1.mixins) {
- if (guardedInterfaceSubtype(parent, i2, visited)) {
+ if (guardedInterfaceSubtype(parent, i2, visitedTypes)) {
return true;
}
}
@@ -910,7 +852,7 @@ class StrongTypeSystemImpl extends TypeSystem {
return false;
}
- bool _isSubtypeOf(DartType t1, DartType t2, Set<Element> visited,
+ bool _isSubtypeOf(DartType t1, DartType t2, Set<TypeImpl> visitedTypes,
{bool dynamicIsBottom: false}) {
if (identical(t1, t2)) {
return true;
@@ -997,20 +939,87 @@ class StrongTypeSystemImpl extends TypeSystem {
return t2.isDartCoreFunction;
}
+ // Guard recursive calls
+ _GuardedSubtypeChecker<FunctionType> guardedIsFunctionSubtype = _guard(
+ (DartType t1, DartType t2, Set<TypeImpl> visitedTypes) =>
+ _isFunctionSubtypeOf(
+ t1 as FunctionType, t2 as FunctionType, visitedTypes));
+
// An interface type can only subtype a function type if
// the interface type declares a call method with a type
// which is a super type of the function type.
if (t1 is InterfaceType && t2 is FunctionType) {
var callType = getCallMethodDefiniteType(t1);
- return (callType != null) && _isFunctionSubtypeOf(callType, t2);
+ return callType != null &&
+ guardedIsFunctionSubtype(callType, t2, visitedTypes);
}
// Two interface types
if (t1 is InterfaceType && t2 is InterfaceType) {
- return _isInterfaceSubtypeOf(t1, t2, visited);
+ return _isInterfaceSubtypeOf(t1, t2, visitedTypes);
+ }
+
+ return guardedIsFunctionSubtype(t1, t2, visitedTypes);
+ }
+
+ DartType _substituteForUnknownType(DartType type,
+ {bool lowerBound: false, dynamicIsBottom: false}) {
+ if (identical(type, UnknownInferredType.instance)) {
+ if (lowerBound && !dynamicIsBottom) {
+ // TODO(jmesserly): this should be the bottom type, once i can be
+ // reified.
+ return typeProvider.nullType;
+ }
+ return typeProvider.dynamicType;
+ }
+ if (type is InterfaceTypeImpl) {
+ // Generic types are covariant, so keep the constraint direction.
+ var newTypeArgs = _transformList(type.typeArguments,
+ (t) => _substituteForUnknownType(t, lowerBound: lowerBound));
+ if (identical(type.typeArguments, newTypeArgs)) return type;
+ return new InterfaceTypeImpl(type.element, type.prunedTypedefs)
+ ..typeArguments = newTypeArgs;
}
+ if (type is FunctionType) {
+ var parameters = type.parameters;
+ var returnType = type.returnType;
+ var newParameters = _transformList(parameters, (ParameterElement p) {
+ // Parameters are contravariant, so flip the constraint direction.
+ // Also pass dynamicIsBottom, because this is a fuzzy arrow.
+ var newType = _substituteForUnknownType(p.type,
+ lowerBound: !lowerBound, dynamicIsBottom: true);
+ return new ParameterElementImpl.synthetic(
+ p.name, newType, p.parameterKind);
+ });
+ // Return type is covariant.
+ var newReturnType =
+ _substituteForUnknownType(returnType, lowerBound: lowerBound);
+ if (identical(parameters, newParameters) &&
+ identical(returnType, newReturnType)) {
+ return type;
+ }
+
+ var function = new FunctionElementImpl(type.name, -1)
+ ..isSynthetic = true
+ ..returnType = newReturnType
+ ..shareTypeParameters(type.typeFormals)
+ ..parameters = newParameters;
+ return function.type = new FunctionTypeImpl(function);
+ }
+ return type;
+ }
- return _isFunctionSubtypeOf(t1 as FunctionType, t2 as FunctionType);
+ bool _typeParameterBoundsSubtype(
+ DartType t1, DartType t2, bool recursionValue) {
+ if (_comparingTypeParameterBounds) {
+ return recursionValue;
+ }
+ _comparingTypeParameterBounds = true;
+ try {
+ return isSubtypeOf(t1, t2);
+ } finally {
+ _comparingTypeParameterBounds = false;
+ }
}
/**
@@ -1069,20 +1078,19 @@ class StrongTypeSystemImpl extends TypeSystem {
return getLeastUpperBound(type1, type2);
}
- bool _typeParameterBoundsSubtype(
- DartType t1, DartType t2, bool recursionValue) {
- if (_comparingTypeParameterBounds) {
- return recursionValue;
- }
- _comparingTypeParameterBounds = true;
- try {
- return isSubtypeOf(t1, t2);
- } finally {
- _comparingTypeParameterBounds = false;
+ static List/*<T>*/ _transformList/*<T>*/(
+ List/*<T>*/ list, /*=T*/ f(/*=T*/ t)) {
+ List/*<T>*/ newList = null;
+ for (var i = 0; i < list.length; i++) {
+ var item = list[i];
+ var newItem = f(item);
+ if (!identical(item, newItem)) {
+ newList ??= new List.from(list);
+ newList[i] = newItem;
+ }
}
+ return newList ?? list;
}
-
- static bool _comparingTypeParameterBounds = false;
}
/**
@@ -1544,6 +1552,104 @@ class TypeSystemImpl extends TypeSystem {
}
}
+/// A type that is being inferred but is not currently known.
+///
+/// This type will only appear in a downward inference context for type
+/// parameters that we do not know yet. Notationally it is written `?`, for
+/// example `List<?>`. This is distinct from `List<dynamic>`. These types will
+/// never appear in the final resolved AST.
+class UnknownInferredType extends TypeImpl {
+ static final UnknownInferredType instance = new UnknownInferredType._();
+
+ UnknownInferredType._()
+ : super(UnknownInferredTypeElement.instance, Keyword.DYNAMIC.syntax);
+
+ @override
+ int get hashCode => 1;
+
+ @override
+ bool get isDynamic => true;
+
+ @override
+ bool operator ==(Object object) => identical(object, this);
+
+ @override
+ void appendTo(StringBuffer buffer, Set<TypeImpl> types) {
+ buffer.write('?');
+ }
+
+ @override
+ bool isMoreSpecificThan(DartType type,
+ [bool withDynamic = false, Set<Element> visitedElements]) {
+ // T is S
+ if (identical(this, type)) {
+ return true;
+ }
+ // else
+ return withDynamic;
+ }
+
+ @override
+ bool isSubtypeOf(DartType type) => true;
+
+ @override
+ bool isSupertypeOf(DartType type) => true;
+
+ @override
+ TypeImpl pruned(List<FunctionTypeAliasElement> prune) => this;
+
+ @override
+ DartType substitute2(
+ List<DartType> argumentTypes, List<DartType> parameterTypes,
+ [List<FunctionTypeAliasElement> prune]) {
+ int length = parameterTypes.length;
+ for (int i = 0; i < length; i++) {
+ if (parameterTypes[i] == this) {
+ return argumentTypes[i];
+ }
+ }
+ return this;
+ }
+
+ /// Given a [type] T, return true if it does not have an unknown type `?`.
+ static bool isKnown(DartType type) => !isUnknown(type);
+
+ /// Given a [type] T, return true if it has an unknown type `?`.
+ static bool isUnknown(DartType type) {
+ if (identical(type, UnknownInferredType.instance)) {
+ return true;
+ }
+ if (type is InterfaceTypeImpl) {
+ return type.typeArguments.any(isUnknown);
+ }
+ if (type is FunctionType) {
+ return isUnknown(type.returnType) ||
+ type.parameters.any((p) => isUnknown(p.type));
+ }
+ return false;
+ }
+}
+
+/// The synthetic element for [UnknownInferredType].
+class UnknownInferredTypeElement extends ElementImpl
+ implements TypeDefiningElement {
+ static final UnknownInferredTypeElement instance =
+ new UnknownInferredTypeElement._();
+
+ UnknownInferredTypeElement._() : super(Keyword.DYNAMIC.syntax, -1) {
+ setModifier(Modifier.SYNTHETIC, true);
+ }
+
+ @override
+ ElementKind get kind => ElementKind.DYNAMIC;
+
+ @override
+ UnknownInferredType get type => UnknownInferredType.instance;
+
+ @override
+ /*=T*/ accept/*<T>*/(ElementVisitor visitor) => null;
+}
+
/// Tracks upper and lower type bounds for a set of type parameters.
///
/// This class is used by calling [isSubtypeOf]. When it encounters one of
@@ -1589,26 +1695,6 @@ class _GenericInferrer {
}
}
- /// 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);
- }
-
- /// Constrain a universal function type [fnType] used in a context
- /// [contextType].
- void constrainGenericFunctionInContext(
- FunctionType fnType, DartType contextType) {
- var origin = new _TypeConstraintFromFunctionContext(fnType, contextType);
-
- // Since we're trying to infer the instantiation, we want to ignore type
- // formals as we check the parameters and return type.
- var inferFnType =
- fnType.instantiate(TypeParameterTypeImpl.getTypes(fnType.typeFormals));
- _matchSubtypeOf(inferFnType, contextType, null, origin, covariant: true);
- }
-
/// Apply an argument constraint, which asserts that the [argument] staticType
/// is a subtype of the [parameterType].
void constrainArgument(
@@ -1621,185 +1707,24 @@ class _GenericInferrer {
covariant: false);
}
- /// Assert that [t1] will be a subtype of [t2], and returns if the constraint
- /// can be satisfied.
- ///
- /// [covariant] must be true if [t1] is a declared type of the generic
- /// function and [t2] is the context type, or false if the reverse. For
- /// example [covariant] is used when [t1] is the declared return type
- /// and [t2] is the context type. Contravariant would be used if [t1] is the
- /// argument type (i.e. passed in to the generic function) and [t2] is the
- /// declared parameter type.
- ///
- /// [origin] indicates where the constraint came from, for example an argument
- /// or return type.
- void _matchSubtypeOf(DartType t1, DartType t2, Set<Element> visited,
- _TypeConstraintOrigin origin,
- {bool covariant, bool dynamicIsBottom: false}) {
- // TODO(jmesserly): I think we should handle `dynamicIsBottom`
- // https://github.com/dart-lang/sdk/issues/29041
- if (covariant && t1 is TypeParameterType) {
- var constraints = _constraints[t1.element];
- if (constraints != null) {
- if (!identical(t2, UnknownInferredType.instance)) {
- constraints.add(new _TypeConstraint(origin, t1, upper: t2));
- _constraintCount++;
- }
- return;
- }
- }
- if (!covariant && t2 is TypeParameterType) {
- var constraints = _constraints[t2.element];
- if (constraints != null) {
- if (!identical(t1, UnknownInferredType.instance)) {
- constraints.add(new _TypeConstraint(origin, t2, lower: t1));
- _constraintCount++;
- }
- return;
- }
- }
-
- if (identical(t1, t2)) {
- return;
- }
-
- // TODO(jmesserly): this logic is taken from subtype.
- void matchSubtype(DartType t1, DartType t2) {
- _matchSubtypeOf(t1, t2, null, origin, covariant: covariant);
- }
-
- // Handle FutureOr<T> union type.
- if (t1 is InterfaceType && t1.isDartAsyncFutureOr) {
- var t1TypeArg = t1.typeArguments[0];
- if (t2 is InterfaceType && t2.isDartAsyncFutureOr) {
- var t2TypeArg = t2.typeArguments[0];
- // FutureOr<A> <: FutureOr<B> iff A <: B
- matchSubtype(t1TypeArg, t2TypeArg);
- return;
- }
-
- // 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;
- }
-
- if (t2 is InterfaceType && t2.isDartAsyncFutureOr) {
- // given t2 is Future<A> | A, then:
- // t1 <: (Future<A> | A) iff t1 <: Future<A> or t1 <: A
- var t2TypeArg = t2.typeArguments[0];
- var t2Future = typeProvider.futureType.instantiate([t2TypeArg]);
-
- int constraintCount = _constraintCount;
- matchSubtype(t1, t2Future);
-
- // 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);
- }
- return;
- }
-
- // S <: T where S is a type variable
- // T is not dynamic or object (handled above)
- // True if T == S
- // Or true if bound of S is S' and S' <: T
-
- if (t1 is TypeParameterType) {
- // Guard against recursive type parameters
- void guardedSubtype(DartType t1, DartType t2) {
- var visitedSet = visited ?? new HashSet<Element>();
- if (visitedSet.add(t1.element)) {
- matchSubtype(t1, t2);
- visitedSet.remove(t1.element);
- }
- }
-
- if (t2 is TypeParameterType && t1.definition == t2.definition) {
- guardedSubtype(t1.bound, t2.bound);
- return;
- }
- guardedSubtype(t1.bound, t2);
- return;
- }
- if (t2 is TypeParameterType) {
- return;
- }
-
- if (t1 is InterfaceType && t2 is InterfaceType) {
- _matchInterfaceSubtypeOf(t1, t2, visited, origin, covariant: covariant);
- return;
- }
-
- // An interface type can only subtype a function type if
- // the interface type declares a call method with a type
- // which is a super type of the function type.
- if (t1 is InterfaceType) {
- t1 = _typeSystem.getCallMethodDefiniteType(t1);
- if (t1 == null) return;
- }
+ /// Constrain a universal function type [fnType] used in a context
+ /// [contextType].
+ void constrainGenericFunctionInContext(
+ FunctionType fnType, DartType contextType) {
+ var origin = new _TypeConstraintFromFunctionContext(fnType, contextType);
- if (t1 is FunctionType && t2 is FunctionType) {
- FunctionTypeImpl.relate(
- t1,
- t2,
- (t1, t2, _, __) {
- _matchSubtypeOf(t2, t1, null, origin,
- covariant: !covariant, dynamicIsBottom: true);
- return true;
- },
- _typeSystem.instantiateToBounds,
- returnRelation: (t1, t2) {
- matchSubtype(t1, t2);
- return true;
- });
- }
+ // Since we're trying to infer the instantiation, we want to ignore type
+ // formals as we check the parameters and return type.
+ var inferFnType =
+ fnType.instantiate(TypeParameterTypeImpl.getTypes(fnType.typeFormals));
+ _matchSubtypeOf(inferFnType, contextType, null, origin, covariant: true);
}
- void _matchInterfaceSubtypeOf(InterfaceType i1, InterfaceType i2,
- Set<Element> visited, _TypeConstraintOrigin origin,
- {bool covariant}) {
- if (identical(i1, i2)) {
- return;
- }
-
- if (i1.element == i2.element) {
- List<DartType> tArgs1 = i1.typeArguments;
- 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);
- }
- return;
- }
- if (i2.isDartCoreFunction && i1.element.getMethod("call") != null) {
- return;
- }
- if (i1.isObject) {
- return;
- }
-
- // Guard against loops in the class hierarchy
- void guardedInterfaceSubtype(InterfaceType t1) {
- var visitedSet = visited ?? new HashSet<Element>();
- if (visitedSet.add(t1.element)) {
- _matchInterfaceSubtypeOf(t1, i2, visited, origin, covariant: covariant);
- visitedSet.remove(t1.element);
- }
- }
-
- guardedInterfaceSubtype(i1.superclass);
- for (final parent in i1.interfaces) {
- guardedInterfaceSubtype(parent);
- }
- for (final parent in i1.mixins) {
- guardedInterfaceSubtype(parent);
- }
+ /// 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);
}
/// Given the constraints that were given by calling [isSubtypeOf], find the
@@ -1910,48 +1835,6 @@ class _GenericInferrer {
return result;
}
- DartType _inferTypeParameterFromContext(
- Iterable<_TypeConstraint> constraints, _TypeConstraint extendsClause) {
- DartType t = _chooseTypeFromConstraints(constraints);
- if (UnknownInferredType.isUnknown(t)) {
- return t;
- }
-
- // If we're about to make our final choice, apply the extends clause.
- // This gives us a chance to refine the choice, in case it would violate
- // the `extends` clause. For example:
- //
- // Object obj = math.min/*<infer Object, error>*/(1, 2);
- //
- // If we consider the `T extends num` we conclude `<num>`, which works.
- if (extendsClause != null) {
- constraints = constraints.toList()..add(extendsClause);
- return _chooseTypeFromConstraints(constraints);
- }
- return t;
- }
-
- DartType _inferTypeParameterFromAll(
- List<_TypeConstraint> constraints, _TypeConstraint extendsClause) {
- // See if we already fixed this type from downwards inference.
- // If so, then we aren't allowed to change it based on argument types.
- DartType t = _inferTypeParameterFromContext(
- constraints.where((c) => c.isDownwards), extendsClause);
- if (UnknownInferredType.isKnown(t)) {
- // Remove constraints that aren't downward ones; we'll ignore these for
- // error reporting, because inference already succeeded.
- constraints.removeWhere((c) => !c.isDownwards);
- return t;
- }
-
- if (extendsClause != null) {
- constraints = constraints.toList()..add(extendsClause);
- }
-
- var choice = _chooseTypeFromConstraints(constraints, toKnownType: true);
- return choice;
- }
-
/// Choose the bound that was implied by the return type, if any.
///
/// Which bound this is depends on what positions the type parameter
@@ -2014,9 +1897,38 @@ class _GenericInferrer {
return lower;
}
- /// This is first calls strong mode's GLB, but if it fails to find anything
- /// (i.e. returns the bottom type), we kick in a few additional rules:
- ///
+ String _formatError(TypeParameterType typeParam, DartType inferred,
+ Iterable<_TypeConstraint> constraints) {
+ var intro = "Tried to infer '$inferred' for '$typeParam'"
+ " which doesn't work:";
+
+ var constraintsByOrigin = <_TypeConstraintOrigin, List<_TypeConstraint>>{};
+ for (var c in constraints) {
+ constraintsByOrigin.putIfAbsent(c.origin, () => []).add(c);
+ }
+
+ // Only report unique constraint origins.
+ Iterable<_TypeConstraint> isSatisified(bool expected) => constraintsByOrigin
+ .values
+ .where((l) =>
+ l.every((c) => c.isSatisifedBy(_typeSystem, inferred)) == expected)
+ .expand((i) => i);
+
+ String unsatisified = _formatConstraints(isSatisified(false));
+ String satisified = _formatConstraints(isSatisified(true));
+
+ assert(unsatisified.isNotEmpty);
+ if (satisified.isNotEmpty) {
+ satisified = "\nThe type '$inferred' was inferred from:\n$satisified";
+ }
+
+ return '\n\n$intro\n$unsatisified$satisified\n\n'
+ 'Consider passing explicit type argument(s) to the generic.\n\n';
+ }
+
+ /// This is first calls strong mode's GLB, but if it fails to find anything
+ /// (i.e. returns the bottom type), we kick in a few additional rules:
+ ///
/// - `GLB(FutureOr<A>, B)` is defined as:
/// - `GLB(FutureOr<A>, FutureOr<B>) == FutureOr<GLB(A, B)>`
/// - `GLB(FutureOr<A>, Future<B>) == Future<GLB(A, B)>`
@@ -2056,33 +1968,227 @@ class _GenericInferrer {
return result;
}
- String _formatError(TypeParameterType typeParam, DartType inferred,
- Iterable<_TypeConstraint> constraints) {
- var intro = "Tried to infer '$inferred' for '$typeParam'"
- " which doesn't work:";
+ DartType _inferTypeParameterFromAll(
+ List<_TypeConstraint> constraints, _TypeConstraint extendsClause) {
+ // See if we already fixed this type from downwards inference.
+ // If so, then we aren't allowed to change it based on argument types.
+ DartType t = _inferTypeParameterFromContext(
+ constraints.where((c) => c.isDownwards), extendsClause);
+ if (UnknownInferredType.isKnown(t)) {
+ // Remove constraints that aren't downward ones; we'll ignore these for
+ // error reporting, because inference already succeeded.
+ constraints.removeWhere((c) => !c.isDownwards);
+ return t;
+ }
- var constraintsByOrigin = <_TypeConstraintOrigin, List<_TypeConstraint>>{};
- for (var c in constraints) {
- constraintsByOrigin.putIfAbsent(c.origin, () => []).add(c);
+ if (extendsClause != null) {
+ constraints = constraints.toList()..add(extendsClause);
}
- // Only report unique constraint origins.
- Iterable<_TypeConstraint> isSatisified(bool expected) => constraintsByOrigin
- .values
- .where((l) =>
- l.every((c) => c.isSatisifedBy(_typeSystem, inferred)) == expected)
- .expand((i) => i);
+ var choice = _chooseTypeFromConstraints(constraints, toKnownType: true);
+ return choice;
+ }
- String unsatisified = _formatConstraints(isSatisified(false));
- String satisified = _formatConstraints(isSatisified(true));
+ DartType _inferTypeParameterFromContext(
+ Iterable<_TypeConstraint> constraints, _TypeConstraint extendsClause) {
+ DartType t = _chooseTypeFromConstraints(constraints);
+ if (UnknownInferredType.isUnknown(t)) {
+ return t;
+ }
- assert(unsatisified.isNotEmpty);
- if (satisified.isNotEmpty) {
- satisified = "\nThe type '$inferred' was inferred from:\n$satisified";
+ // If we're about to make our final choice, apply the extends clause.
+ // This gives us a chance to refine the choice, in case it would violate
+ // the `extends` clause. For example:
+ //
+ // Object obj = math.min/*<infer Object, error>*/(1, 2);
+ //
+ // If we consider the `T extends num` we conclude `<num>`, which works.
+ if (extendsClause != null) {
+ constraints = constraints.toList()..add(extendsClause);
+ return _chooseTypeFromConstraints(constraints);
}
+ return t;
+ }
- return '\n\n$intro\n$unsatisified$satisified\n\n'
- 'Consider passing explicit type argument(s) to the generic.\n\n';
+ void _matchInterfaceSubtypeOf(InterfaceType i1, InterfaceType i2,
+ Set<Element> visited, _TypeConstraintOrigin origin,
+ {bool covariant}) {
+ if (identical(i1, i2)) {
+ return;
+ }
+
+ if (i1.element == i2.element) {
+ List<DartType> tArgs1 = i1.typeArguments;
+ 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);
+ }
+ return;
+ }
+ if (i2.isDartCoreFunction && i1.element.getMethod("call") != null) {
+ return;
+ }
+ if (i1.isObject) {
+ return;
+ }
+
+ // Guard against loops in the class hierarchy
+ void guardedInterfaceSubtype(InterfaceType t1) {
+ var visitedSet = visited ?? new HashSet<Element>();
+ if (visitedSet.add(t1.element)) {
+ _matchInterfaceSubtypeOf(t1, i2, visited, origin, covariant: covariant);
+ visitedSet.remove(t1.element);
+ }
+ }
+
+ guardedInterfaceSubtype(i1.superclass);
+ for (final parent in i1.interfaces) {
+ guardedInterfaceSubtype(parent);
+ }
+ for (final parent in i1.mixins) {
+ guardedInterfaceSubtype(parent);
+ }
+ }
+
+ /// Assert that [t1] will be a subtype of [t2], and returns if the constraint
+ /// can be satisfied.
+ ///
+ /// [covariant] must be true if [t1] is a declared type of the generic
+ /// function and [t2] is the context type, or false if the reverse. For
+ /// example [covariant] is used when [t1] is the declared return type
+ /// and [t2] is the context type. Contravariant would be used if [t1] is the
+ /// argument type (i.e. passed in to the generic function) and [t2] is the
+ /// declared parameter type.
+ ///
+ /// [origin] indicates where the constraint came from, for example an argument
+ /// or return type.
+ void _matchSubtypeOf(DartType t1, DartType t2, Set<Element> visited,
+ _TypeConstraintOrigin origin,
+ {bool covariant, bool dynamicIsBottom: false}) {
+ // TODO(jmesserly): I think we should handle `dynamicIsBottom`
+ // https://github.com/dart-lang/sdk/issues/29041
+ if (covariant && t1 is TypeParameterType) {
+ var constraints = _constraints[t1.element];
+ if (constraints != null) {
+ if (!identical(t2, UnknownInferredType.instance)) {
+ constraints.add(new _TypeConstraint(origin, t1, upper: t2));
+ _constraintCount++;
+ }
+ return;
+ }
+ }
+ if (!covariant && t2 is TypeParameterType) {
+ var constraints = _constraints[t2.element];
+ if (constraints != null) {
+ if (!identical(t1, UnknownInferredType.instance)) {
+ constraints.add(new _TypeConstraint(origin, t2, lower: t1));
+ _constraintCount++;
+ }
+ return;
+ }
+ }
+
+ if (identical(t1, t2)) {
+ return;
+ }
+
+ // TODO(jmesserly): this logic is taken from subtype.
+ void matchSubtype(DartType t1, DartType t2) {
+ _matchSubtypeOf(t1, t2, null, origin, covariant: covariant);
+ }
+
+ // Handle FutureOr<T> union type.
+ if (t1 is InterfaceType && t1.isDartAsyncFutureOr) {
+ var t1TypeArg = t1.typeArguments[0];
+ if (t2 is InterfaceType && t2.isDartAsyncFutureOr) {
+ var t2TypeArg = t2.typeArguments[0];
+ // FutureOr<A> <: FutureOr<B> iff A <: B
+ matchSubtype(t1TypeArg, t2TypeArg);
+ return;
+ }
+
+ // 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;
+ }
+
+ if (t2 is InterfaceType && t2.isDartAsyncFutureOr) {
+ // given t2 is Future<A> | A, then:
+ // t1 <: (Future<A> | A) iff t1 <: Future<A> or t1 <: A
+ var t2TypeArg = t2.typeArguments[0];
+ var t2Future = typeProvider.futureType.instantiate([t2TypeArg]);
+
+ int constraintCount = _constraintCount;
+ matchSubtype(t1, t2Future);
+
+ // 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);
+ }
+ return;
+ }
+
+ // S <: T where S is a type variable
+ // T is not dynamic or object (handled above)
+ // True if T == S
+ // Or true if bound of S is S' and S' <: T
+
+ if (t1 is TypeParameterType) {
+ // Guard against recursive type parameters
+ void guardedSubtype(DartType t1, DartType t2) {
+ var visitedSet = visited ?? new HashSet<Element>();
+ if (visitedSet.add(t1.element)) {
+ matchSubtype(t1, t2);
+ visitedSet.remove(t1.element);
+ }
+ }
+
+ if (t2 is TypeParameterType && t1.definition == t2.definition) {
+ guardedSubtype(t1.bound, t2.bound);
+ return;
+ }
+ guardedSubtype(t1.bound, t2);
+ return;
+ }
+ if (t2 is TypeParameterType) {
+ return;
+ }
+
+ if (t1 is InterfaceType && t2 is InterfaceType) {
+ _matchInterfaceSubtypeOf(t1, t2, visited, origin, covariant: covariant);
+ return;
+ }
+
+ // An interface type can only subtype a function type if
+ // the interface type declares a call method with a type
+ // which is a super type of the function type.
+ if (t1 is InterfaceType) {
+ t1 = _typeSystem.getCallMethodDefiniteType(t1);
+ if (t1 == null) return;
+ }
+
+ if (t1 is FunctionType && t2 is FunctionType) {
+ FunctionTypeImpl.relate(
+ t1,
+ t2,
+ (t1, t2, _, __) {
+ _matchSubtypeOf(t2, t1, null, origin,
+ covariant: !covariant, dynamicIsBottom: true);
+ return true;
+ },
+ _typeSystem.instantiateToBounds,
+ returnRelation: (t1, t2) {
+ matchSubtype(t1, t2);
+ return true;
+ });
+ }
}
static String _formatConstraints(Iterable<_TypeConstraint> constraints) {
@@ -2111,11 +2217,34 @@ class _GenericInferrer {
}
}
-/// The origin of a type constraint, for the purposes of producing a human
-/// readable error message during type inference as well as determining whether
-/// the constraint was used to fix the type parameter or not.
-abstract class _TypeConstraintOrigin {
- List<String> formatError();
+/// A constraint on a type parameter that we're inferring.
+class _TypeConstraint extends _TypeRange {
+ /// The type parameter that is constrained by [lowerBound] or [upperBound].
+ final TypeParameterType typeParameter;
+
+ /// Where this constraint comes from, used for error messages.
+ ///
+ /// See [toString].
+ final _TypeConstraintOrigin origin;
+
+ _TypeConstraint(this.origin, this.typeParameter,
+ {DartType upper, DartType lower})
+ : super(upper: upper, lower: lower);
+
+ _TypeConstraint.fromExtends(TypeParameterType type, DartType extendsType)
+ : this(new _TypeConstraintFromExtendsClause(type, extendsType), type,
+ upper: extendsType);
+
+ bool get isDownwards => origin is! _TypeConstraintFromArgument;
+
+ bool isSatisifedBy(TypeSystem ts, DartType type) =>
+ ts.isSubtypeOf(lowerBound, type) && ts.isSubtypeOf(type, upperBound);
+
+ /// Converts this constraint to a message suitable for a type inference error.
+ @override
+ String toString() => !identical(upperBound, UnknownInferredType.instance)
+ ? "'$typeParameter' must extend '$upperBound'"
+ : "'$lowerBound' must extend '$typeParameter'";
}
class _TypeConstraintFromArgument extends _TypeConstraintOrigin {
@@ -2153,18 +2282,17 @@ class _TypeConstraintFromArgument extends _TypeConstraintOrigin {
}
}
-class _TypeConstraintFromReturnType extends _TypeConstraintOrigin {
- final DartType contextType;
- final DartType declaredType;
+class _TypeConstraintFromExtendsClause extends _TypeConstraintOrigin {
+ final TypeParameterType typeParam;
+ final DartType extendsType;
- _TypeConstraintFromReturnType(this.declaredType, this.contextType);
+ _TypeConstraintFromExtendsClause(this.typeParam, this.extendsType);
@override
formatError() {
return [
- "Return type",
- "declared as '$declaredType'",
- "used where '$contextType' is required."
+ "Type parameter '$typeParam'",
+ "declared to extend '$extendsType'."
];
}
}
@@ -2185,21 +2313,29 @@ class _TypeConstraintFromFunctionContext extends _TypeConstraintOrigin {
}
}
-class _TypeConstraintFromExtendsClause extends _TypeConstraintOrigin {
- final TypeParameterType typeParam;
- final DartType extendsType;
+class _TypeConstraintFromReturnType extends _TypeConstraintOrigin {
+ final DartType contextType;
+ final DartType declaredType;
- _TypeConstraintFromExtendsClause(this.typeParam, this.extendsType);
+ _TypeConstraintFromReturnType(this.declaredType, this.contextType);
@override
formatError() {
return [
- "Type parameter '$typeParam'",
- "declared to extend '$extendsType'."
+ "Return type",
+ "declared as '$declaredType'",
+ "used where '$contextType' is required."
];
}
}
+/// The origin of a type constraint, for the purposes of producing a human
+/// readable error message during type inference as well as determining whether
+/// the constraint was used to fix the type parameter or not.
+abstract class _TypeConstraintOrigin {
+ List<String> formatError();
+}
+
class _TypeRange {
/// The upper bound of the type parameter. In other words, T <: upperBound.
///
@@ -2247,131 +2383,3 @@ class _TypeRange {
: lowerBound = lower ?? UnknownInferredType.instance,
upperBound = upper ?? UnknownInferredType.instance;
}
-
-/// A constraint on a type parameter that we're inferring.
-class _TypeConstraint extends _TypeRange {
- /// The type parameter that is constrained by [lowerBound] or [upperBound].
- final TypeParameterType typeParameter;
-
- /// Where this constraint comes from, used for error messages.
- ///
- /// See [toString].
- final _TypeConstraintOrigin origin;
-
- _TypeConstraint(this.origin, this.typeParameter,
- {DartType upper, DartType lower})
- : super(upper: upper, lower: lower);
-
- _TypeConstraint.fromExtends(TypeParameterType type, DartType extendsType)
- : this(new _TypeConstraintFromExtendsClause(type, extendsType), type,
- upper: extendsType);
-
- bool get isDownwards => origin is! _TypeConstraintFromArgument;
-
- bool isSatisifedBy(TypeSystem ts, DartType type) =>
- ts.isSubtypeOf(lowerBound, type) && ts.isSubtypeOf(type, upperBound);
-
- /// Converts this constraint to a message suitable for a type inference error.
- @override
- String toString() => !identical(upperBound, UnknownInferredType.instance)
- ? "'$typeParameter' must extend '$upperBound'"
- : "'$lowerBound' must extend '$typeParameter'";
-}
-
-/// The synthetic element for [UnknownInferredType].
-class UnknownInferredTypeElement extends ElementImpl
- implements TypeDefiningElement {
- static final UnknownInferredTypeElement instance =
- new UnknownInferredTypeElement._();
-
- @override
- UnknownInferredType get type => UnknownInferredType.instance;
-
- UnknownInferredTypeElement._() : super(Keyword.DYNAMIC.syntax, -1) {
- setModifier(Modifier.SYNTHETIC, true);
- }
-
- @override
- ElementKind get kind => ElementKind.DYNAMIC;
-
- @override
- /*=T*/ accept/*<T>*/(ElementVisitor visitor) => null;
-}
-
-/// A type that is being inferred but is not currently known.
-///
-/// This type will only appear in a downward inference context for type
-/// parameters that we do not know yet. Notationally it is written `?`, for
-/// example `List<?>`. This is distinct from `List<dynamic>`. These types will
-/// never appear in the final resolved AST.
-class UnknownInferredType extends TypeImpl {
- static final UnknownInferredType instance = new UnknownInferredType._();
-
- UnknownInferredType._()
- : super(UnknownInferredTypeElement.instance, Keyword.DYNAMIC.syntax);
-
- @override
- int get hashCode => 1;
-
- @override
- bool get isDynamic => true;
-
- @override
- bool operator ==(Object object) => identical(object, this);
-
- @override
- bool isMoreSpecificThan(DartType type,
- [bool withDynamic = false, Set<Element> visitedElements]) {
- // T is S
- if (identical(this, type)) {
- return true;
- }
- // else
- return withDynamic;
- }
-
- @override
- bool isSubtypeOf(DartType type) => true;
-
- @override
- bool isSupertypeOf(DartType type) => true;
-
- @override
- TypeImpl pruned(List<FunctionTypeAliasElement> prune) => this;
-
- @override
- DartType substitute2(
- List<DartType> argumentTypes, List<DartType> parameterTypes,
- [List<FunctionTypeAliasElement> prune]) {
- int length = parameterTypes.length;
- for (int i = 0; i < length; i++) {
- if (parameterTypes[i] == this) {
- return argumentTypes[i];
- }
- }
- return this;
- }
-
- @override
- void appendTo(StringBuffer buffer, Set<TypeImpl> types) {
- buffer.write('?');
- }
-
- /// Given a [type] T, return true if it does not have an unknown type `?`.
- static bool isKnown(DartType type) => !isUnknown(type);
-
- /// Given a [type] T, return true if it has an unknown type `?`.
- static bool isUnknown(DartType type) {
- if (identical(type, UnknownInferredType.instance)) {
- return true;
- }
- if (type is InterfaceTypeImpl) {
- return type.typeArguments.any(isUnknown);
- }
- if (type is FunctionType) {
- return isUnknown(type.returnType) ||
- type.parameters.any((p) => isUnknown(p.type));
- }
- return false;
- }
-}
« no previous file with comments | « no previous file | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698