[analyzer][cfe] Share constraint generation for generic functions
Part of https://github.com/dart-lang/sdk/issues/54902
Change-Id: Ic025cdc36a266d35094626df175346ccac6f99fe
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/393860
Reviewed-by: Paul Berry <paulberry@google.com>
Commit-Queue: Chloe Stefantsova <cstefantsova@google.com>
diff --git a/pkg/_fe_analyzer_shared/lib/src/type_inference/type_analyzer_operations.dart b/pkg/_fe_analyzer_shared/lib/src/type_inference/type_analyzer_operations.dart
index d47f831..3f26fce 100644
--- a/pkg/_fe_analyzer_shared/lib/src/type_inference/type_analyzer_operations.dart
+++ b/pkg/_fe_analyzer_shared/lib/src/type_inference/type_analyzer_operations.dart
@@ -667,6 +667,15 @@
List<SharedTypeParameterStructure<TypeStructure>>
typeParametersToEliminate);
+ /// Computes the least closure of a type.
+ ///
+ /// Computing the greatest closure of a type is described here:
+ /// https://github.com/dart-lang/language/blob/main/resources/type-system/inference.md#type-variable-elimination-least-and-greatest-closure-of-a-type
+ TypeStructure leastClosureOfTypeInternal(
+ TypeStructure type,
+ List<SharedTypeParameterStructure<TypeStructure>>
+ typeParametersToEliminate);
+
/// Converts a type into a corresponding type schema.
SharedTypeSchemaView<TypeStructure> typeToSchema(
SharedTypeView<TypeStructure> type);
@@ -924,16 +933,15 @@
/// Matches [p] against [q].
///
- /// If [p] and [q] are both non-generic function types, and [p] is a subtype
- /// of [q] under some constraints, the constraints making the relation
- /// possible are recorded, and `true` is returned. Otherwise, the constraint
- /// state is unchanged (or rolled back using [restoreState]), and `false` is
- /// returned.
+ /// If [p] and [q] are both function types, and [p] is a subtype of [q] under
+ /// some constraints, the constraints making the relation possible are
+ /// recorded, and `true` is returned. Otherwise, the constraint state is
+ /// unchanged (or rolled back using [restoreState]), and `false` is returned.
///
/// An invariant of the type inference is that only [p] or [q] may be a
/// schema (in other words, may contain the unknown type `_`); the other must
- /// be simply a type. If [leftSchema] is `true`, [p] may contain `_`; if it is
- /// `false`, [q] may contain `_`.
+ /// be simply a type. If [leftSchema] is `true`, [p] may contain `_`; if it
+ /// is `false`, [q] may contain `_`.
bool performSubtypeConstraintGenerationForFunctionTypes(
TypeStructure p, TypeStructure q,
{required bool leftSchema, required AstNode? astNodeForTesting}) {
@@ -941,125 +949,221 @@
FunctionParameterStructure> &&
q is SharedFunctionTypeStructure<TypeStructure, TypeParameterStructure,
FunctionParameterStructure>) {
- // 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.typeFormals.isEmpty && q.typeFormals.isEmpty) {
+ return _handleNonGenericFunctionTypes(p, q,
+ leftSchema: leftSchema, astNodeForTesting: astNodeForTesting);
+ } else {
+ return _handleGenericFunctionTypes(p, q,
+ leftSchema: leftSchema, astNodeForTesting: astNodeForTesting);
+ }
+ }
- if (p.typeFormals.isEmpty &&
- q.typeFormals.isEmpty &&
- p.sortedNamedParameters.isEmpty &&
- q.sortedNamedParameters.isEmpty &&
- p.requiredPositionalParameterCount <=
- q.requiredPositionalParameterCount &&
- p.positionalParameterTypes.length >=
- q.positionalParameterTypes.length) {
- final TypeConstraintGeneratorState state = currentState;
+ return false;
+ }
+ /// Matches non-generic function type [p] against non-generic function type
+ /// [q].
+ ///
+ /// See the documentation on
+ /// [performSubtypeConstraintGenerationForFunctionTypes] for details.
+ bool _handleNonGenericFunctionTypes(
+ SharedFunctionTypeStructure<TypeStructure, TypeParameterStructure,
+ FunctionParameterStructure>
+ p,
+ SharedFunctionTypeStructure<TypeStructure, TypeParameterStructure,
+ FunctionParameterStructure>
+ q,
+ {required bool leftSchema,
+ required AstNode? astNodeForTesting}) {
+ assert(p.typeFormals.isEmpty && q.typeFormals.isEmpty);
+ // 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.sortedNamedParameters.isEmpty &&
+ q.sortedNamedParameters.isEmpty &&
+ p.requiredPositionalParameterCount <=
+ q.requiredPositionalParameterCount &&
+ p.positionalParameterTypes.length >=
+ q.positionalParameterTypes.length) {
+ final TypeConstraintGeneratorState state = currentState;
+
+ if (!performSubtypeConstraintGenerationInternal(
+ p.returnType, q.returnType,
+ leftSchema: leftSchema, astNodeForTesting: astNodeForTesting)) {
+ return false;
+ }
+ for (int i = 0; i < q.positionalParameterTypes.length; ++i) {
if (!performSubtypeConstraintGenerationInternal(
- p.returnType, q.returnType,
- leftSchema: leftSchema, astNodeForTesting: astNodeForTesting)) {
+ q.positionalParameterTypes[i], p.positionalParameterTypes[i],
+ leftSchema: !leftSchema, astNodeForTesting: astNodeForTesting)) {
+ restoreState(state);
return false;
}
- for (int i = 0; i < q.positionalParameterTypes.length; ++i) {
- if (!performSubtypeConstraintGenerationInternal(
- q.positionalParameterTypes[i], p.positionalParameterTypes[i],
- leftSchema: !leftSchema, astNodeForTesting: astNodeForTesting)) {
- restoreState(state);
- return false;
- }
- }
- return true;
- } else if (p.typeFormals.isEmpty &&
- q.typeFormals.isEmpty &&
- p.positionalParameterTypes.length ==
- p.requiredPositionalParameterCount &&
- q.positionalParameterTypes.length ==
- q.requiredPositionalParameterCount &&
- p.requiredPositionalParameterCount ==
- q.requiredPositionalParameterCount &&
- p.sortedNamedParameters.isNotEmpty &&
- q.sortedNamedParameters.length <= p.sortedNamedParameters.length) {
- // Function types with named parameters are treated analogously to the
- // positional parameter case above.
-
- final TypeConstraintGeneratorState state = currentState;
-
- if (!performSubtypeConstraintGenerationInternal(
- p.returnType, q.returnType,
- leftSchema: leftSchema, astNodeForTesting: astNodeForTesting)) {
- return false;
- }
- for (int i = 0; i < p.positionalParameterTypes.length; ++i) {
- if (!performSubtypeConstraintGenerationInternal(
- q.positionalParameterTypes[i], p.positionalParameterTypes[i],
- leftSchema: !leftSchema, astNodeForTesting: astNodeForTesting)) {
- restoreState(state);
- return false;
- }
- }
- // Consume parameter names from p and q in order. Since the named
- // parameters in p and q are already sorted by name, we can do this by
- // iterating through both lists in tandem.
- int i = 0;
- int j = 0;
- while (true) {
- // Determine whether the next parameter should be consumed from p,
- // q, or both (because the next set of names matches). If the next
- // parameter should be consumed from p, comparisonResult will be set
- // to a value < 0. If the next parameter should be consumed from q,
- // comparisonResult will be set to a value > 0. If the next
- // parameter should be consumed from both, comparisonResult will be
- // set to 0.
- int comparisonResult;
- if (i >= p.sortedNamedParameters.length) {
- if (j >= q.sortedNamedParameters.length) {
- // No parameters left.
- return true;
- } else {
- // No more parameters in p, so the next parameter must come from
- // q.
- comparisonResult = 1;
- }
- } else if (j >= q.sortedNamedParameters.length) {
- // No more parameters in q, so the next parameter must come from
- // p.
- comparisonResult = -1;
- } else {
- comparisonResult = p.sortedNamedParameters[i].name
- .compareTo(q.sortedNamedParameters[j].name);
- }
- if (comparisonResult > 0) {
- // Extra parameter in q that q that doesn't exist in p. No match.
- restoreState(state);
- return false;
- } else if (comparisonResult < 0) {
- // Extra parameter in p that doesn't exist in q. Ok if not
- // required.
- if (p.sortedNamedParameters[i].isRequired) {
- restoreState(state);
- return false;
- } else {
- i++;
- }
- } else {
- // The next parameter in p and q matches, so match their types.
- if (!performSubtypeConstraintGenerationInternal(
- q.sortedNamedParameters[j].type,
- p.sortedNamedParameters[i].type,
- leftSchema: !leftSchema,
- astNodeForTesting: astNodeForTesting)) {
- restoreState(state);
- return false;
- }
- i++;
- j++;
- }
- }
}
+ return true;
+ } else if (p.positionalParameterTypes.length ==
+ p.requiredPositionalParameterCount &&
+ q.positionalParameterTypes.length ==
+ q.requiredPositionalParameterCount &&
+ p.requiredPositionalParameterCount ==
+ q.requiredPositionalParameterCount &&
+ p.sortedNamedParameters.isNotEmpty &&
+ q.sortedNamedParameters.length <= p.sortedNamedParameters.length) {
+ // Function types with named parameters are treated analogously to the
+ // positional parameter case above.
+
+ final TypeConstraintGeneratorState state = currentState;
+
+ if (!performSubtypeConstraintGenerationInternal(
+ p.returnType, q.returnType,
+ leftSchema: leftSchema, astNodeForTesting: astNodeForTesting)) {
+ return false;
+ }
+ for (int i = 0; i < p.positionalParameterTypes.length; ++i) {
+ if (!performSubtypeConstraintGenerationInternal(
+ q.positionalParameterTypes[i], p.positionalParameterTypes[i],
+ leftSchema: !leftSchema, astNodeForTesting: astNodeForTesting)) {
+ restoreState(state);
+ return false;
+ }
+ }
+ // Consume parameter names from p and q in order. Since the named
+ // parameters in p and q are already sorted by name, we can do this by
+ // iterating through both lists in tandem.
+ int i = 0;
+ int j = 0;
+ while (true) {
+ // Determine whether the next parameter should be consumed from p,
+ // q, or both (because the next set of names matches). If the next
+ // parameter should be consumed from p, comparisonResult will be set
+ // to a value < 0. If the next parameter should be consumed from q,
+ // comparisonResult will be set to a value > 0. If the next
+ // parameter should be consumed from both, comparisonResult will be
+ // set to 0.
+ int comparisonResult;
+ if (i >= p.sortedNamedParameters.length) {
+ if (j >= q.sortedNamedParameters.length) {
+ // No parameters left.
+ return true;
+ } else {
+ // No more parameters in p, so the next parameter must come from
+ // q.
+ comparisonResult = 1;
+ }
+ } else if (j >= q.sortedNamedParameters.length) {
+ // No more parameters in q, so the next parameter must come from
+ // p.
+ comparisonResult = -1;
+ } else {
+ comparisonResult = p.sortedNamedParameters[i].name
+ .compareTo(q.sortedNamedParameters[j].name);
+ }
+ if (comparisonResult > 0) {
+ // Extra parameter in q that q that doesn't exist in p. No match.
+ restoreState(state);
+ return false;
+ } else if (comparisonResult < 0) {
+ // Extra parameter in p that doesn't exist in q. Ok if not
+ // required.
+ if (p.sortedNamedParameters[i].isRequired) {
+ restoreState(state);
+ return false;
+ } else {
+ i++;
+ }
+ } else {
+ // The next parameter in p and q matches, so match their types.
+ if (!performSubtypeConstraintGenerationInternal(
+ q.sortedNamedParameters[j].type, p.sortedNamedParameters[i].type,
+ leftSchema: !leftSchema, astNodeForTesting: astNodeForTesting)) {
+ restoreState(state);
+ return false;
+ }
+ i++;
+ j++;
+ }
+ }
+ }
+
+ return false;
+ }
+
+ /// Matches generic function type [p] against generic function type [q].
+ ///
+ /// See the documentation on
+ /// [performSubtypeConstraintGenerationForFunctionTypes] for details.
+ bool _handleGenericFunctionTypes(
+ SharedFunctionTypeStructure<TypeStructure, TypeParameterStructure,
+ FunctionParameterStructure>
+ p,
+ SharedFunctionTypeStructure<TypeStructure, TypeParameterStructure,
+ FunctionParameterStructure>
+ q,
+ {required bool leftSchema,
+ required AstNode? astNodeForTesting}) {
+ assert(p.typeFormals.isNotEmpty || q.typeFormals.isNotEmpty);
+ // 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.typeFormals.length == q.typeFormals.length) {
+ final TypeConstraintGeneratorState state = currentState;
+
+ bool isMatch = true;
+ for (int i = 0; isMatch && i < p.typeFormals.length; ++i) {
+ isMatch = isMatch &&
+ performSubtypeConstraintGenerationInternal(
+ p.typeFormals[i].bound ??
+ typeAnalyzerOperations.objectQuestionType.unwrapTypeView(),
+ q.typeFormals[i].bound ??
+ typeAnalyzerOperations.objectQuestionType.unwrapTypeView(),
+ leftSchema: leftSchema,
+ astNodeForTesting: astNodeForTesting) &&
+ performSubtypeConstraintGenerationInternal(
+ q.typeFormals[i].bound ??
+ typeAnalyzerOperations.objectQuestionType.unwrapTypeView(),
+ p.typeFormals[i].bound ??
+ typeAnalyzerOperations.objectQuestionType.unwrapTypeView(),
+ leftSchema: !leftSchema,
+ astNodeForTesting: astNodeForTesting);
+ }
+ if (isMatch) {
+ var (
+ instantiatedP,
+ instantiatedQ,
+ typeParametersToEliminate: typeParametersToEliminate
+ ) = instantiateFunctionTypesAndProvideFreshTypeParameters(p, q,
+ leftSchema: leftSchema);
+
+ if (performSubtypeConstraintGenerationInternal(
+ instantiatedP, instantiatedQ,
+ leftSchema: leftSchema, astNodeForTesting: astNodeForTesting)) {
+ eliminateTypeParametersInGeneratedConstraints(
+ typeParametersToEliminate, state,
+ astNodeForTesting: astNodeForTesting);
+ return true;
+ }
+ }
+ restoreState(state);
}
return false;
@@ -1117,6 +1221,39 @@
return true;
}
+ /// Creates fresh type parameters, instantiates the non-generic parts of [p]
+ /// and [q] with the new parameters as type arguments, and returns the
+ /// instantiated non-generic function types and the eliminator that
+ /// eliminates the new type parameters.
+ ///
+ /// This operation is required as a part of the subtype constraint generation
+ /// algorithm, in the step for the generic function types. See
+ /// https://github.com/dart-lang/language/blob/main/resources/type-system/inference.md#subtype-constraint-generation.
+ (
+ TypeStructure,
+ TypeStructure, {
+ List<TypeParameterStructure> typeParametersToEliminate
+ }) instantiateFunctionTypesAndProvideFreshTypeParameters(
+ SharedFunctionTypeStructure<TypeStructure, TypeParameterStructure,
+ FunctionParameterStructure>
+ p,
+ SharedFunctionTypeStructure<TypeStructure, TypeParameterStructure,
+ FunctionParameterStructure>
+ q,
+ {required bool leftSchema});
+
+ /// Iterates over all of the type constraints generated since
+ /// [eliminationStartState] and eliminates the type variables in them using
+ /// [typeParametersToEliminate].
+ ///
+ /// This step is required as a part of the subtype constraint generation
+ /// algorithm, in the step for generic function types. See
+ /// https://github.com/dart-lang/language/blob/main/resources/type-system/inference.md#subtype-constraint-generation.
+ void eliminateTypeParametersInGeneratedConstraints(
+ List<TypeParameterStructure> typeParametersToEliminate,
+ TypeConstraintGeneratorState eliminationStartState,
+ {required AstNode? astNodeForTesting});
+
/// Matches [p] against [q].
///
/// If [q] is of the form `FutureOr<q0>` for some `q0`, and [p] is a subtype
diff --git a/pkg/_fe_analyzer_shared/lib/src/types/shared_type.dart b/pkg/_fe_analyzer_shared/lib/src/types/shared_type.dart
index 1bd0d4e..df4d48f 100644
--- a/pkg/_fe_analyzer_shared/lib/src/types/shared_type.dart
+++ b/pkg/_fe_analyzer_shared/lib/src/types/shared_type.dart
@@ -83,6 +83,9 @@
TypeStructure extends SharedTypeStructure<TypeStructure>> {
/// The name of the type parameter, for display to the user.
String get displayName;
+
+ /// The bound of the type parameter.
+ TypeStructure? get bound;
}
/// Common interface for data structures used by the implementations to
diff --git a/pkg/_fe_analyzer_shared/test/mini_ast.dart b/pkg/_fe_analyzer_shared/test/mini_ast.dart
index d911205..1aa1f53 100644
--- a/pkg/_fe_analyzer_shared/test/mini_ast.dart
+++ b/pkg/_fe_analyzer_shared/test/mini_ast.dart
@@ -3281,6 +3281,13 @@
// TODO(paulberry): Implement greatest closure of types in mini ast.
throw UnimplementedError();
}
+
+ @override
+ Type leastClosureOfTypeInternal(Type type,
+ List<SharedTypeParameterStructure<Type>> typeParametersToEliminate) {
+ // TODO(paulberry): Implement greatest closure of types in mini ast.
+ throw UnimplementedError();
+ }
}
/// Representation of an expression or statement in the pseudo-Dart language
diff --git a/pkg/_fe_analyzer_shared/test/mini_types.dart b/pkg/_fe_analyzer_shared/test/mini_types.dart
index d0ce5ea..e431ec1 100644
--- a/pkg/_fe_analyzer_shared/test/mini_types.dart
+++ b/pkg/_fe_analyzer_shared/test/mini_types.dart
@@ -513,6 +513,7 @@
class TypeParameter extends TypeNameInfo
implements SharedTypeParameterStructure<Type> {
/// The type variable's bound. Defaults to `Object?`.
+ @override
Type bound;
TypeParameter._(super.name) : bound = Type('Object?');
diff --git a/pkg/_fe_analyzer_shared/test/type_inference/type_constraint_gatherer_test.dart b/pkg/_fe_analyzer_shared/test/type_inference/type_constraint_gatherer_test.dart
index 856f02b..ca7620d 100644
--- a/pkg/_fe_analyzer_shared/test/type_inference/type_constraint_gatherer_test.dart
+++ b/pkg/_fe_analyzer_shared/test/type_inference/type_constraint_gatherer_test.dart
@@ -879,4 +879,26 @@
{required Node? nodeForTesting}) {
_constraints.add('$lower <: $typeParameter');
}
+
+ @override
+ void eliminateTypeParametersInGeneratedConstraints(
+ Object eliminator, TypeConstraintGeneratorState eliminationStartState,
+ {required Node? astNodeForTesting}) {
+ // TODO(paulberry): implement eliminateTypeParametersInGeneratedConstraints
+ }
+
+ @override
+ (
+ Type,
+ Type, {
+ List<TypeParameter> typeParametersToEliminate
+ }) instantiateFunctionTypesAndProvideFreshTypeParameters(
+ SharedFunctionTypeStructure<Type, TypeParameter, NamedFunctionParameter>
+ p,
+ SharedFunctionTypeStructure<Type, TypeParameter, NamedFunctionParameter>
+ q,
+ {required bool leftSchema}) {
+ // TODO(paulberry): implement instantiateFunctionTypesAndProvideEliminator
+ throw UnimplementedError();
+ }
}
diff --git a/pkg/analyzer/lib/dart/element/element.dart b/pkg/analyzer/lib/dart/element/element.dart
index 91c70e2..589d6eb 100644
--- a/pkg/analyzer/lib/dart/element/element.dart
+++ b/pkg/analyzer/lib/dart/element/element.dart
@@ -2517,6 +2517,7 @@
/// if this parameter does not have an explicit bound. Being able to
/// distinguish between an implicit and explicit bound is needed by the
/// instantiate to bounds algorithm.
+ @override
DartType? get bound;
@override
diff --git a/pkg/analyzer/lib/src/dart/element/type_constraint_gatherer.dart b/pkg/analyzer/lib/src/dart/element/type_constraint_gatherer.dart
index 03ba563..4870ac3 100644
--- a/pkg/analyzer/lib/src/dart/element/type_constraint_gatherer.dart
+++ b/pkg/analyzer/lib/src/dart/element/type_constraint_gatherer.dart
@@ -131,6 +131,30 @@
}
@override
+ void eliminateTypeParametersInGeneratedConstraints(
+ covariant List<TypeParameterElement> eliminator,
+ shared.TypeConstraintGeneratorState eliminationStartState,
+ {required AstNode? astNodeForTesting}) {
+ var constraints = _constraints.sublist(eliminationStartState.count);
+ _constraints.length = eliminationStartState.count;
+ for (var constraint in constraints) {
+ if (constraint.isUpper) {
+ addUpperConstraintForParameter(
+ constraint.typeParameter,
+ typeAnalyzerOperations.leastClosureOfTypeInternal(
+ constraint.constraint.unwrapTypeSchemaView(), eliminator),
+ nodeForTesting: astNodeForTesting);
+ } else {
+ addLowerConstraintForParameter(
+ constraint.typeParameter,
+ typeAnalyzerOperations.greatestClosureOfTypeInternal(
+ constraint.constraint.unwrapTypeSchemaView(), eliminator),
+ nodeForTesting: astNodeForTesting);
+ }
+ }
+ }
+
+ @override
List<DartType>? getTypeArgumentsAsInstanceOf(
InterfaceType type, InterfaceElement typeDeclaration) {
for (var interface in type.element.allSupertypes) {
@@ -145,6 +169,43 @@
}
@override
+ (DartType, DartType, {List<TypeParameterElement> typeParametersToEliminate})
+ instantiateFunctionTypesAndProvideFreshTypeParameters(
+ covariant FunctionType P, covariant FunctionType Q,
+ {required bool leftSchema}) {
+ // 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`.
+ var newTypeParameters = <TypeParameterElement>[];
+ for (var i = 0; i < P.typeFormals.length; i++) {
+ var Z = TypeParameterElementImpl('Z$i', -1);
+ if (leftSchema) {
+ Z.bound = P.typeFormals[i].bound;
+ } else {
+ Z.bound = Q.typeFormals[i].bound;
+ }
+ newTypeParameters.add(Z);
+ }
+
+ // And `F0[Z0/T0, ..., Zn/Tn]` is a subtype match for
+ // `F1[Z0/S0, ..., Zn/Sn]` with respect to `L` under constraints `C0`.
+ var typeArguments = newTypeParameters
+ .map((e) => e.instantiate(nullabilitySuffix: NullabilitySuffix.none))
+ .toList();
+ var P_instantiated = P.instantiate(typeArguments);
+ var Q_instantiated = Q.instantiate(typeArguments);
+
+ return (
+ P_instantiated,
+ Q_instantiated,
+ typeParametersToEliminate: newTypeParameters
+ );
+ }
+
+ @override
bool performSubtypeConstraintGenerationInternal(DartType p, DartType q,
{required bool leftSchema, required AstNode? astNodeForTesting}) {
return trySubtypeMatch(p, q, leftSchema, nodeForTesting: astNodeForTesting);
@@ -299,8 +360,9 @@
}
}
- if (P is FunctionType && Q is FunctionType) {
- return _functionType(P, Q, leftSchema, nodeForTesting: nodeForTesting);
+ if (performSubtypeConstraintGenerationForFunctionTypes(P, Q,
+ leftSchema: leftSchema, astNodeForTesting: nodeForTesting)) {
+ return true;
}
// A type `P` is a subtype match for `Record` with respect to `L` under no
@@ -319,96 +381,6 @@
return false;
}
-
- /// Matches [P] against [Q], where [P] and [Q] are both function types.
- ///
- /// If [P] is a subtype of [Q] under some constraints, the constraints making
- /// the relation possible are recorded to [_constraints], and `true` is
- /// returned. Otherwise, [_constraints] is left unchanged (or rolled back),
- /// and `false` is returned.
- bool _functionType(FunctionType P, FunctionType Q, bool leftSchema,
- {required AstNode? nodeForTesting}) {
- if (P.nullabilitySuffix != NullabilitySuffix.none) {
- return false;
- }
-
- if (Q.nullabilitySuffix != NullabilitySuffix.none) {
- return false;
- }
-
- var P_typeFormals = P.typeFormals;
- var Q_typeFormals = Q.typeFormals;
- if (P_typeFormals.length != Q_typeFormals.length) {
- return false;
- }
-
- if (P_typeFormals.isEmpty && Q_typeFormals.isEmpty) {
- return performSubtypeConstraintGenerationForFunctionTypes(P, Q,
- leftSchema: leftSchema, astNodeForTesting: nodeForTesting);
- }
-
- // We match two generic function types:
- // `<T0 extends B00, ..., Tn extends B0n>F0`
- // `<S0 extends B10, ..., Sn extends B1n>F1`
- // with respect to `L` under constraint set `C2`:
- var rewind = _constraints.length;
-
- // If `B0i` is a subtype match for `B1i` with constraint set `Ci0`.
- // If `B1i` is a subtype match for `B0i` with constraint set `Ci1`.
- // And `Ci2` is `Ci0 + Ci1`.
- for (var i = 0; i < P_typeFormals.length; i++) {
- var B0 = P_typeFormals[i].bound ?? _typeSystem.objectQuestion;
- var B1 = Q_typeFormals[i].bound ?? _typeSystem.objectQuestion;
- if (!trySubtypeMatch(B0, B1, leftSchema,
- nodeForTesting: nodeForTesting)) {
- _constraints.length = rewind;
- return false;
- }
- if (!trySubtypeMatch(B1, B0, !leftSchema,
- nodeForTesting: nodeForTesting)) {
- _constraints.length = rewind;
- return false;
- }
- }
-
- // 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`.
- var newTypeParameters = <TypeParameterElement>[];
- for (var i = 0; i < P_typeFormals.length; i++) {
- var Z = TypeParameterElementImpl('Z$i', -1);
- if (leftSchema) {
- Z.bound = P_typeFormals[i].bound;
- } else {
- Z.bound = Q_typeFormals[i].bound;
- }
- newTypeParameters.add(Z);
- }
-
- // And `F0[Z0/T0, ..., Zn/Tn]` is a subtype match for
- // `F1[Z0/S0, ..., Zn/Sn]` with respect to `L` under constraints `C0`.
- var typeArguments = newTypeParameters
- .map((e) => e.instantiate(nullabilitySuffix: NullabilitySuffix.none))
- .toList();
- var P_instantiated = P.instantiate(typeArguments);
- var Q_instantiated = Q.instantiate(typeArguments);
- if (!performSubtypeConstraintGenerationForFunctionTypes(
- P_instantiated, Q_instantiated,
- leftSchema: leftSchema, astNodeForTesting: nodeForTesting)) {
- _constraints.length = rewind;
- return false;
- }
-
- // And `C1` is `C02 + ... + Cn2 + C0`.
- // And `C2` is `C1` with each constraint replaced with its closure
- // with respect to `[Z0, ..., Zn]`.
- // TODO(scheglov): do closure
-
- return true;
- }
}
/// Data structure maintaining intermediate type inference results, such as
diff --git a/pkg/analyzer/lib/src/dart/resolver/flow_analysis_visitor.dart b/pkg/analyzer/lib/src/dart/resolver/flow_analysis_visitor.dart
index ce05521..5ab3ade 100644
--- a/pkg/analyzer/lib/src/dart/resolver/flow_analysis_visitor.dart
+++ b/pkg/analyzer/lib/src/dart/resolver/flow_analysis_visitor.dart
@@ -520,7 +520,6 @@
@override
DartType greatestClosureOfTypeInternal(DartType type,
List<SharedTypeParameterStructure<DartType>> typeParametersToEliminate) {
- typeParametersToEliminate.first;
return typeSystem.greatestClosure(
type, typeParametersToEliminate.cast<TypeParameterElement>());
}
@@ -625,6 +624,13 @@
}
@override
+ DartType leastClosureOfTypeInternal(DartType type,
+ List<SharedTypeParameterStructure<DartType>> typeParametersToEliminate) {
+ return typeSystem.leastClosure(
+ type, typeParametersToEliminate.cast<TypeParameterElement>());
+ }
+
+ @override
DartType listTypeInternal(DartType elementType) {
return typeSystem.typeProvider.listType(elementType);
}
diff --git a/pkg/front_end/lib/src/type_inference/type_constraint_gatherer.dart b/pkg/front_end/lib/src/type_inference/type_constraint_gatherer.dart
index cc7f701..1eacba7 100644
--- a/pkg/front_end/lib/src/type_inference/type_constraint_gatherer.dart
+++ b/pkg/front_end/lib/src/type_inference/type_constraint_gatherer.dart
@@ -73,6 +73,72 @@
@override
OperationsCfe get typeAnalyzerOperations => typeOperations;
+ @override
+ (DartType, DartType, {List<StructuralParameter> typeParametersToEliminate})
+ instantiateFunctionTypesAndProvideFreshTypeParameters(
+ covariant FunctionType p, covariant FunctionType q,
+ {required bool leftSchema}) {
+ FunctionType instantiatedP;
+ FunctionType instantiatedQ;
+ if (leftSchema) {
+ List<DartType> typeParametersForAlphaRenaming =
+ new List<DartType>.generate(
+ p.typeFormals.length,
+ (int i) => new StructuralParameterType.forAlphaRenaming(
+ q.typeParameters[i], p.typeParameters[i]));
+ instantiatedP = p.withoutTypeParameters;
+ instantiatedQ = FunctionTypeInstantiator.instantiate(
+ q, typeParametersForAlphaRenaming);
+ } else {
+ // Coverage-ignore-block(suite): Not run.
+ List<DartType> typeParametersForAlphaRenaming =
+ new List<DartType>.generate(
+ p.typeFormals.length,
+ (int i) => new StructuralParameterType.forAlphaRenaming(
+ p.typeParameters[i], q.typeParameters[i]));
+ instantiatedP = FunctionTypeInstantiator.instantiate(
+ p, typeParametersForAlphaRenaming);
+ instantiatedQ = q.withoutTypeParameters;
+ }
+
+ return (
+ instantiatedP,
+ instantiatedQ,
+ typeParametersToEliminate: leftSchema
+ ? p.typeParameters
+ :
+ // Coverage-ignore(suite): Not run.
+ q.typeParameters
+ );
+ }
+
+ @override
+ void eliminateTypeParametersInGeneratedConstraints(
+ covariant List<StructuralParameter> typeParametersToEliminate,
+ shared.TypeConstraintGeneratorState eliminationStartState,
+ {required TreeNode? astNodeForTesting}) {
+ List<GeneratedTypeConstraint> constraints =
+ _protoConstraints.sublist(eliminationStartState.count);
+ _protoConstraints.length = eliminationStartState.count;
+ for (GeneratedTypeConstraint constraint in constraints) {
+ if (constraint.isUpper) {
+ addUpperConstraintForParameter(
+ constraint.typeParameter,
+ typeOperations.leastClosureOfTypeInternal(
+ constraint.constraint.unwrapTypeSchemaView(),
+ typeParametersToEliminate),
+ nodeForTesting: astNodeForTesting);
+ } else {
+ addLowerConstraintForParameter(
+ constraint.typeParameter,
+ typeOperations.greatestClosureOfTypeInternal(
+ constraint.constraint.unwrapTypeSchemaView(),
+ typeParametersToEliminate),
+ nodeForTesting: astNodeForTesting);
+ }
+ }
+ }
+
/// Applies all the argument constraints implied by trying to make
/// [actualTypes] assignable to [formalTypes].
void constrainArguments(
@@ -410,93 +476,6 @@
return true;
}
- // 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,
- treeNodeForTesting: treeNodeForTesting) &&
- _isNullabilityAwareSubtypeMatch(
- q.typeParameters[i].bound, p.typeParameters[i].bound,
- constrainSupertype: !constrainSupertype,
- treeNodeForTesting: treeNodeForTesting);
- }
- if (isMatch) {
- List<DartType> typeParametersOfPAsTypesForQ =
- new List<DartType>.generate(
- p.typeParameters.length,
- (int i) => new StructuralParameterType.forAlphaRenaming(
- q.typeParameters[i], p.typeParameters[i]));
- FunctionType instantiatedP = p.withoutTypeParameters;
- FunctionType instantiatedQ = FunctionTypeInstantiator.instantiate(
- q, typeParametersOfPAsTypesForQ);
- if (_isNullabilityAwareSubtypeMatch(instantiatedP, instantiatedQ,
- constrainSupertype: constrainSupertype,
- treeNodeForTesting: treeNodeForTesting)) {
- List<GeneratedTypeConstraint> constraints =
- _protoConstraints.sublist(baseConstraintCount);
- _protoConstraints.length = baseConstraintCount;
- NullabilityAwareTypeParameterEliminator eliminator =
- new NullabilityAwareTypeParameterEliminator(
- structuralEliminationTargets: p.typeParameters.toSet(),
- nominalEliminationTargets: {},
- bottomType: typeOperations.neverType.unwrapTypeView(),
- topType: typeOperations.objectQuestionType.unwrapTypeView(),
- topFunctionType:
- _environment.coreTypes.functionNonNullableRawType,
- unhandledTypeHandler:
- // Coverage-ignore(suite): Not run.
- (DartType type, ignored) => type is UnknownType
- ? false
- : throw new UnsupportedError(
- "Unsupported type '${type.runtimeType}'."));
- for (GeneratedTypeConstraint constraint in constraints) {
- if (constraint.isUpper) {
- addUpperConstraintForParameter(
- constraint.typeParameter,
- eliminator.eliminateToLeast(
- constraint.constraint.unwrapTypeSchemaView()),
- nodeForTesting: treeNodeForTesting);
- } else {
- addLowerConstraintForParameter(
- constraint.typeParameter,
- eliminator.eliminateToGreatest(
- constraint.constraint.unwrapTypeSchemaView()),
- nodeForTesting: treeNodeForTesting);
- }
- }
- return true;
- }
- }
- // Coverage-ignore-block(suite): Not run.
- _protoConstraints.length = baseConstraintCount;
- }
-
// A type P is a subtype match for Record with respect to L under no
// constraints:
//
diff --git a/pkg/front_end/lib/src/type_inference/type_inference_engine.dart b/pkg/front_end/lib/src/type_inference/type_inference_engine.dart
index b833a66..d8a842a 100644
--- a/pkg/front_end/lib/src/type_inference/type_inference_engine.dart
+++ b/pkg/front_end/lib/src/type_inference/type_inference_engine.dart
@@ -996,6 +996,17 @@
.functionRawType(Nullability.nonNullable))
.eliminateToGreatest(type);
}
+
+ @override
+ DartType leastClosureOfTypeInternal(DartType type,
+ List<SharedTypeParameterStructure<DartType>> typeParametersToEliminate) {
+ return new NullabilityAwareFreeTypeParameterEliminator(
+ bottomType: const NeverType.nonNullable(),
+ topType: typeEnvironment.coreTypes.objectNullableRawType,
+ topFunctionType: typeEnvironment.coreTypes
+ .functionRawType(Nullability.nonNullable))
+ .eliminateToLeast(type);
+ }
}
/// Type inference results used for testing.
diff --git a/pkg/front_end/test/coverage_suite_expected.dart b/pkg/front_end/test/coverage_suite_expected.dart
index 2f65fae..68865bc 100644
--- a/pkg/front_end/test/coverage_suite_expected.dart
+++ b/pkg/front_end/test/coverage_suite_expected.dart
@@ -560,7 +560,7 @@
),
// 100.0%.
"package:front_end/src/kernel/body_builder.dart": (
- hitCount: 7120,
+ hitCount: 7121,
missCount: 0,
),
// 100.0%.
@@ -1036,7 +1036,7 @@
),
// 100.0%.
"package:front_end/src/type_inference/type_constraint_gatherer.dart": (
- hitCount: 311,
+ hitCount: 189,
missCount: 0,
),
// 100.0%.
@@ -1046,7 +1046,7 @@
),
// 100.0%.
"package:front_end/src/type_inference/type_inference_engine.dart": (
- hitCount: 521,
+ hitCount: 530,
missCount: 0,
),
// 100.0%.
diff --git a/pkg/kernel/lib/src/ast/types.dart b/pkg/kernel/lib/src/ast/types.dart
index 3073854..9587ed2 100644
--- a/pkg/kernel/lib/src/ast/types.dart
+++ b/pkg/kernel/lib/src/ast/types.dart
@@ -246,6 +246,7 @@
/// This is set to [unsetBoundSentinel] temporarily during IR construction.
/// This is set to the `Object?` for type parameters without an explicit
/// bound.
+ @override
DartType bound;
/// Sentinel value used for the [defaultType] that has not yet been computed.
