in pkg/front_end/lib/src/fasta/type_inference/type_constraint_gatherer.dart [310:826]
bool _isNullabilityAwareSubtypeMatch(DartType p, DartType q,
{required bool constrainSupertype}) {
// ignore: unnecessary_null_comparison
assert(p != null);
// ignore: unnecessary_null_comparison
assert(q != null);
// ignore: unnecessary_null_comparison
assert(constrainSupertype != null);
// If the type parameters being constrained occur in the supertype (that is,
// [q]), the subtype (that is, [p]) is not allowed to contain them. To
// check that, the assert below uses the equivalence of the following: X ->
// Y <=> !X || Y.
assert(
!constrainSupertype ||
!containsTypeVariable(p, _parametersToConstrain.toSet(),
unhandledTypeHandler: (DartType type, ignored) =>
type is UnknownType
? false
: throw new UnsupportedError(
"Unsupported type '${type.runtimeType}'.")),
"Failed implication check: "
"constrainSupertype -> !containsTypeVariable(q)");
// If the type parameters being constrained occur in the supertype (that is,
// [q]), the supertype is not allowed to contain [UnknownType] as its part,
// that is, the supertype should be fully known. To check that, the assert
// below uses the equivalence of the following: X -> Y <=> !X || Y.
assert(
!constrainSupertype || isKnown(q),
"Failed implication check: "
"constrainSupertype -> isKnown(q)");
// If the type parameters being constrained occur in the subtype (that is,
// [p]), the subtype is not allowed to contain [UnknownType] as its part,
// that is, the subtype should be fully known. To check that, the assert
// below uses the equivalence of the following: X -> Y <=> !X || Y.
assert(
constrainSupertype || isKnown(p),
"Failed implication check: "
"!constrainSupertype -> isKnown(p)");
// If the type parameters being constrained occur in the subtype (that is,
// [p]), the supertype (that is, [q]) is not allowed to contain them. To
// check that, the assert below uses the equivalence of the following: X ->
// Y <=> !X || Y.
assert(
constrainSupertype ||
!containsTypeVariable(q, _parametersToConstrain.toSet(),
unhandledTypeHandler: (DartType type, ignored) =>
type is UnknownType
? false
: throw new UnsupportedError(
"Unsupported type '${type.runtimeType}'.")),
"Failed implication check: "
"!constrainSupertype -> !containsTypeVariable(q)");
if (p is InvalidType || q is InvalidType) return false;
// If P is _ then the match holds with no constraints.
if (p is UnknownType) return true;
// If Q is _ then the match holds with no constraints.
if (q is UnknownType) return true;
// If P is a type variable X in L, then the match holds:
//
// Under constraint _ <: X <: Q.
if (p is TypeParameterType &&
isTypeParameterTypeWithoutNullabilityMarker(p,
isNonNullableByDefault: _currentLibrary.isNonNullableByDefault) &&
_parametersToConstrain.contains(p.parameter)) {
_constrainParameterUpper(p.parameter, q);
return true;
}
// If Q is a type variable X in L, then the match holds:
//
// Under constraint P <: X <: _.
if (q is TypeParameterType &&
isTypeParameterTypeWithoutNullabilityMarker(q,
isNonNullableByDefault: _currentLibrary.isNonNullableByDefault) &&
_parametersToConstrain.contains(q.parameter)) {
_constrainParameterLower(q.parameter, p);
return true;
}
// If P and Q are identical types, then the subtype match holds under no
// constraints.
//
// We're only checking primitive types for equality, because the algorithm
// will recurse over non-primitive types anyway.
if (identical(p, q) ||
isPrimitiveDartType(p) && isPrimitiveDartType(q) && p == q) {
return true;
}
// If P is a legacy type P0* then the match holds under constraint set C:
//
// Only if P0 is a subtype match for Q under constraint set C.
if (isLegacyTypeConstructorApplication(p,
isNonNullableByDefault: _currentLibrary.isNonNullableByDefault)) {
return _isNullabilityAwareSubtypeMatch(
computeTypeWithoutNullabilityMarker(p,
isNonNullableByDefault: _currentLibrary.isNonNullableByDefault),
q,
constrainSupertype: constrainSupertype);
}
// If Q is a legacy type Q0* then the match holds under constraint set C:
//
// If P is dynamic or void and P is a subtype match for Q0 under constraint
// set C.
// Or if P is not dynamic or void and P is a subtype match for Q0? under
// constraint set C.
if (isLegacyTypeConstructorApplication(q,
isNonNullableByDefault: _currentLibrary.isNonNullableByDefault)) {
final int baseConstraintCount = _protoConstraints.length;
if ((p is DynamicType || p is VoidType) &&
_isNullabilityAwareSubtypeMatch(
p,
computeTypeWithoutNullabilityMarker(q,
isNonNullableByDefault:
_currentLibrary.isNonNullableByDefault),
constrainSupertype: constrainSupertype)) {
return true;
}
_protoConstraints.length = baseConstraintCount;
if (p is! DynamicType &&
p is! VoidType &&
_isNullabilityAwareSubtypeMatch(
p, q.withDeclaredNullability(Nullability.nullable),
constrainSupertype: constrainSupertype)) {
return true;
}
_protoConstraints.length = baseConstraintCount;
}
// If Q is FutureOr<Q0> the match holds under constraint set C:
//
// If P is FutureOr<P0> and P0 is a subtype match for Q0 under constraint
// set C. Or if P is a subtype match for Future<Q0> under non-empty
// constraint set C. Or if P is a subtype match for Q0 under constraint set
// C. Or if P is a subtype match for Future<Q0> under empty constraint set
// C.
if (q is FutureOrType) {
final int baseConstraintCount = _protoConstraints.length;
if (p is FutureOrType &&
_isNullabilityAwareSubtypeMatch(p.typeArgument, q.typeArgument,
constrainSupertype: constrainSupertype)) {
return true;
}
_protoConstraints.length = baseConstraintCount;
bool isMatchWithFuture = _isNullabilityAwareSubtypeMatch(
p, futureType(q.typeArgument, Nullability.nonNullable),
constrainSupertype: constrainSupertype);
bool matchWithFutureAddsConstraints =
_protoConstraints.length != baseConstraintCount;
if (isMatchWithFuture && matchWithFutureAddsConstraints) {
return true;
}
_protoConstraints.length = baseConstraintCount;
if (_isNullabilityAwareSubtypeMatch(p, q.typeArgument,
constrainSupertype: constrainSupertype)) {
return true;
}
_protoConstraints.length = baseConstraintCount;
if (isMatchWithFuture && !matchWithFutureAddsConstraints) {
return true;
}
_protoConstraints.length = baseConstraintCount;
}
// If Q is Q0? the match holds under constraint set C:
//
// If P is P0? and P0 is a subtype match for Q0 under constraint set C.
// Or if P is dynamic or void and Object is a subtype match for Q0 under
// constraint set C.
// Or if P is a subtype match for Q0 under non-empty constraint set C.
// Or if P is a subtype match for Null under constraint set C.
// Or if P is a subtype match for Q0 under empty constraint set C.
if (isNullableTypeConstructorApplication(q)) {
final int baseConstraintCount = _protoConstraints.length;
final DartType rawP = computeTypeWithoutNullabilityMarker(p,
isNonNullableByDefault: _currentLibrary.isNonNullableByDefault);
final DartType rawQ = computeTypeWithoutNullabilityMarker(q,
isNonNullableByDefault: _currentLibrary.isNonNullableByDefault);
if (isNullableTypeConstructorApplication(p) &&
_isNullabilityAwareSubtypeMatch(rawP, rawQ,
constrainSupertype: constrainSupertype)) {
return true;
}
_protoConstraints.length = baseConstraintCount;
if ((p is DynamicType || p is VoidType) &&
_isNullabilityAwareSubtypeMatch(
coreTypes.objectNonNullableRawType, rawQ,
constrainSupertype: constrainSupertype)) {
return true;
}
_protoConstraints.length = baseConstraintCount;
bool isMatchWithRawQ = _isNullabilityAwareSubtypeMatch(p, rawQ,
constrainSupertype: constrainSupertype);
bool matchWithRawQAddsConstraints =
_protoConstraints.length != baseConstraintCount;
if (isMatchWithRawQ && matchWithRawQAddsConstraints) {
return true;
}
_protoConstraints.length = baseConstraintCount;
if (_isNullabilityAwareSubtypeMatch(p, const NullType(),
constrainSupertype: constrainSupertype)) {
return true;
}
_protoConstraints.length = baseConstraintCount;
if (isMatchWithRawQ && !matchWithRawQAddsConstraints) {
return true;
}
_protoConstraints.length = baseConstraintCount;
}
// If P is FutureOr<P0> the match holds under constraint set C1 + C2:
//
// If Future<P0> is a subtype match for Q under constraint set C1.
// And if P0 is a subtype match for Q under constraint set C2.
if (p is FutureOrType) {
final int baseConstraintCount = _protoConstraints.length;
if (_isNullabilityAwareSubtypeMatch(
futureType(p.typeArgument, Nullability.nonNullable), q,
constrainSupertype: constrainSupertype) &&
_isNullabilityAwareSubtypeMatch(p.typeArgument, q,
constrainSupertype: constrainSupertype)) {
return true;
}
_protoConstraints.length = baseConstraintCount;
}
// If P is P0? the match holds under constraint set C1 + C2:
//
// If P0 is a subtype match for Q under constraint set C1.
// And if Null is a subtype match for Q under constraint set C2.
if (isNullableTypeConstructorApplication(p)) {
final int baseConstraintCount = _protoConstraints.length;
if (_isNullabilityAwareSubtypeMatch(
computeTypeWithoutNullabilityMarker(p,
isNonNullableByDefault:
_currentLibrary.isNonNullableByDefault),
q,
constrainSupertype: constrainSupertype) &&
_isNullabilityAwareSubtypeMatch(const NullType(), q,
constrainSupertype: constrainSupertype)) {
return true;
}
_protoConstraints.length = baseConstraintCount;
}
// If Q is dynamic, Object?, or void then the match holds under no
// constraints.
if (q is DynamicType ||
q is VoidType ||
q == coreTypes.objectNullableRawType) {
return true;
}
// If P is Never then the match holds under no constraints.
if (p is NeverType && p.declaredNullability == Nullability.nonNullable) {
return true;
}
// If Q is Object, then the match holds under no constraints:
//
// Only if P is non-nullable.
if (q == coreTypes.objectNonNullableRawType) {
return p.nullability == Nullability.nonNullable;
}
// If P is Null, then the match holds under no constraints:
//
// Only if Q is nullable.
if (p is NullType) {
return q.nullability == Nullability.nullable;
}
// If P is a type variable X with bound B (or a promoted type variable X &
// B), the match holds with constraint set C:
//
// If B is a subtype match for Q with constraint set C. Note that we have
// already eliminated the case that X is a variable in L.
if (p is TypeParameterType) {
final int baseConstraintCount = _protoConstraints.length;
if (_isNullabilityAwareSubtypeMatch(p.bound, q,
constrainSupertype: constrainSupertype)) {
return true;
}
_protoConstraints.length = baseConstraintCount;
}
// If P is C<M0, ..., Mk> and Q is C<N0, ..., Nk>, then the match holds
// under constraints C0 + ... + Ck:
//
// If Mi is a subtype match for Ni with respect to L under constraints Ci.
if (p is InterfaceType &&
q is InterfaceType &&
p.classNode == q.classNode) {
assert(p.typeArguments.length == q.typeArguments.length);
final int baseConstraintCount = _protoConstraints.length;
bool isMatch = true;
for (int i = 0; isMatch && i < p.typeArguments.length; ++i) {
isMatch = isMatch &&
_isNullabilityAwareSubtypeMatch(
p.typeArguments[i], q.typeArguments[i],
constrainSupertype: constrainSupertype);
}
if (isMatch) return true;
_protoConstraints.length = baseConstraintCount;
}
// If P is C0<M0, ..., Mk> and Q is C1<N0, ..., Nj> then the match holds
// with respect to L under constraints C:
//
// If C1<B0, ..., Bj> is a superinterface of C0<M0, ..., Mk> and C1<B0, ...,
// Bj> is a subtype match for C1<N0, ..., Nj> with respect to L under
// constraints C.
if (p is InterfaceType && q is InterfaceType) {
final List<DartType>? sArguments =
getTypeArgumentsAsInstanceOf(p, q.classNode);
if (sArguments != null) {
assert(sArguments.length == q.typeArguments.length);
final int baseConstraintCount = _protoConstraints.length;
bool isMatch = true;
for (int i = 0; isMatch && i < sArguments.length; ++i) {
isMatch = isMatch &&
_isNullabilityAwareSubtypeMatch(sArguments[i], q.typeArguments[i],
constrainSupertype: constrainSupertype);
}
if (isMatch) return true;
_protoConstraints.length = baseConstraintCount;
}
}
// If Q is Function then the match holds under no constraints:
//
// If P is a function type.
if (q == coreTypes.functionNonNullableRawType && p is FunctionType) {
return true;
}
// A function type (M0,..., Mn, [M{n+1}, ..., Mm]) -> R0 is a subtype match
// for a function type (N0,..., Nk, [N{k+1}, ..., Nr]) -> R1 with respect to
// L under constraints C0 + ... + Cr + C
//
// If R0 is a subtype match for a type R1 with respect to L under
// constraints C. If n <= k and r <= m. And for i in 0...r, Ni is a
// subtype match for Mi with respect to L under constraints Ci.
if (p is FunctionType &&
q is FunctionType &&
p.typeParameters.isEmpty &&
q.typeParameters.isEmpty &&
p.namedParameters.isEmpty &&
q.namedParameters.isEmpty &&
p.requiredParameterCount <= q.requiredParameterCount &&
p.positionalParameters.length >= q.positionalParameters.length) {
final int baseConstraintCount = _protoConstraints.length;
if (_isNullabilityAwareSubtypeMatch(p.returnType, q.returnType,
constrainSupertype: constrainSupertype)) {
bool isMatch = true;
for (int i = 0; isMatch && i < q.positionalParameters.length; ++i) {
isMatch = isMatch &&
_isNullabilityAwareSubtypeMatch(
q.positionalParameters[i], p.positionalParameters[i],
constrainSupertype: !constrainSupertype);
}
if (isMatch) return true;
}
_protoConstraints.length = baseConstraintCount;
}
// Function types with named parameters are treated analogously to the
// positional parameter case above.
if (p is FunctionType &&
q is FunctionType &&
p.typeParameters.isEmpty &&
q.typeParameters.isEmpty &&
p.positionalParameters.length == p.requiredParameterCount &&
q.positionalParameters.length == q.requiredParameterCount &&
p.requiredParameterCount == q.requiredParameterCount &&
(p.namedParameters.isNotEmpty || q.namedParameters.isNotEmpty)) {
final int baseConstraintCount = _protoConstraints.length;
if (_isNullabilityAwareSubtypeMatch(p.returnType, q.returnType,
constrainSupertype: constrainSupertype)) {
bool isMatch = true;
for (int i = 0; isMatch && i < p.positionalParameters.length; ++i) {
isMatch = isMatch &&
_isNullabilityAwareSubtypeMatch(
q.positionalParameters[i], p.positionalParameters[i],
constrainSupertype: !constrainSupertype);
}
Map<String, DartType> pNamedTypes = {};
for (int i = 0; isMatch && i < p.namedParameters.length; ++i) {
pNamedTypes[p.namedParameters[i].name] = p.namedParameters[i].type;
}
for (int i = 0; isMatch && i < q.namedParameters.length; ++i) {
isMatch =
isMatch && pNamedTypes.containsKey(q.namedParameters[i].name);
isMatch = isMatch &&
_isNullabilityAwareSubtypeMatch(q.namedParameters[i].type,
pNamedTypes[q.namedParameters[i].name]!,
constrainSupertype: !constrainSupertype);
}
if (isMatch) return true;
}
_protoConstraints.length = baseConstraintCount;
}
// A generic function type <T0 extends B00, ..., Tn extends B0n>F0 is a
// subtype match for a generic function type <S0 extends B10, ..., Sn
// extends B1n>F1 with respect to L under constraint set C2
//
// If B0i is a subtype match for B1i with constraint set Ci0. And B1i is a
// subtype match for B0i with constraint set Ci1. And Ci2 is Ci0 + Ci1.
//
// And Z0...Zn are fresh variables with bounds B20, ..., B2n, Where B2i is
// B0i[Z0/T0, ..., Zn/Tn] if P is a type schema. Or B2i is B1i[Z0/S0, ...,
// Zn/Sn] if Q is a type schema. In other words, we choose the bounds for
// the fresh variables from whichever of the two generic function types is a
// type schema and does not contain any variables from L.
//
// And F0[Z0/T0, ..., Zn/Tn] is a subtype match for F1[Z0/S0, ..., Zn/Sn]
// with respect to L under constraints C0. And C1 is C02 + ... + Cn2 + C0.
// And C2 is C1 with each constraint replaced with its closure with respect
// to [Z0, ..., Zn].
if (p is FunctionType &&
q is FunctionType &&
p.typeParameters.isNotEmpty &&
q.typeParameters.isNotEmpty &&
p.typeParameters.length == q.typeParameters.length) {
final int baseConstraintCount = _protoConstraints.length;
bool isMatch = true;
for (int i = 0; isMatch && i < p.typeParameters.length; ++i) {
isMatch = isMatch &&
_isNullabilityAwareSubtypeMatch(
p.typeParameters[i].bound, q.typeParameters[i].bound,
constrainSupertype: constrainSupertype) &&
_isNullabilityAwareSubtypeMatch(
q.typeParameters[i].bound, p.typeParameters[i].bound,
constrainSupertype: !constrainSupertype);
}
if (isMatch) {
FreshTypeParameters freshTypeParameters = getFreshTypeParameters(
constrainSupertype ? p.typeParameters : q.typeParameters);
Substitution substitutionForBound = freshTypeParameters.substitution;
FunctionType constrainedType = constrainSupertype ? q : p;
Map<TypeParameter, DartType> substitutionMapForConstrainedType = {};
for (int i = 0; i < constrainedType.typeParameters.length; ++i) {
substitutionMapForConstrainedType[constrainedType.typeParameters[i]] =
new TypeParameterType.forAlphaRenaming(
constrainedType.typeParameters[i],
freshTypeParameters.freshTypeParameters[i]);
}
Substitution substitutionForConstrainedType =
Substitution.fromMap(substitutionMapForConstrainedType);
Substitution substitutionForP = constrainSupertype
? substitutionForBound
: substitutionForConstrainedType;
Substitution substitutionForQ = constrainSupertype
? substitutionForConstrainedType
: substitutionForBound;
if (_isNullabilityAwareSubtypeMatch(
substitutionForP.substituteType(p.withoutTypeParameters),
substitutionForQ.substituteType(q.withoutTypeParameters),
constrainSupertype: constrainSupertype)) {
List<_ProtoConstraint> constraints =
_protoConstraints.sublist(baseConstraintCount);
_protoConstraints.length = baseConstraintCount;
NullabilityAwareTypeVariableEliminator eliminator =
new NullabilityAwareTypeVariableEliminator(
eliminationTargets:
freshTypeParameters.freshTypeParameters.toSet(),
bottomType: const NeverType.nonNullable(),
topType: coreTypes.objectNullableRawType,
topFunctionType: coreTypes.functionNonNullableRawType,
unhandledTypeHandler: (DartType type, ignored) =>
type is UnknownType
? false
: throw new UnsupportedError(
"Unsupported type '${type.runtimeType}'."));
for (_ProtoConstraint constraint in constraints) {
if (constraint.isUpper) {
_constrainParameterUpper(constraint.parameter,
eliminator.eliminateToLeast(constraint.bound));
} else {
_constrainParameterLower(constraint.parameter,
eliminator.eliminateToGreatest(constraint.bound));
}
}
return true;
}
}
_protoConstraints.length = baseConstraintCount;
}
return false;
}