pkg/analyzer/lib/src/dart/element/type_constraint_gatherer.dart - sdk.git - Git at Google

 // Copyright (c) 2020, the Dart project authors. Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.

 import 'package:analyzer/dart/element/element.dart';
 import 'package:analyzer/dart/element/nullability_suffix.dart';
 import 'package:analyzer/dart/element/type.dart';
 import 'package:analyzer/src/dart/element/element.dart';
 import 'package:analyzer/src/dart/element/type.dart';
 import 'package:analyzer/src/dart/element/type_algebra.dart';
 import 'package:analyzer/src/dart/element/type_schema.dart';
 import 'package:analyzer/src/dart/element/type_system.dart';

 /// A constraint on the type [parameter] that we're inferring.
 /// We require that `lower <: parameter <: upper`.
 class TypeConstraint {
   final TypeParameterElement parameter;
   final DartType lower;
   final DartType upper;

   TypeConstraint._(this.parameter, this.lower, this.upper);

   bool get isEmpty {
     return identical(lower, UnknownInferredType.instance) &&
         identical(upper, UnknownInferredType.instance);
   }

   @override
   String toString() {
     var lowerStr = lower.getDisplayString(withNullability: true);
     var upperStr = upper.getDisplayString(withNullability: true);
     return '$lowerStr <: ${parameter.name} <: $upperStr';
   }
 }

 /// Creates sets of [TypeConstraint]s for type parameters, based on an attempt
 /// to make one type schema a subtype of another.
 class TypeConstraintGatherer {
   final TypeSystemImpl _typeSystem;
   final Set<TypeParameterElement> _typeParameters = Set.identity();
   final List<TypeConstraint> _constraints = [];

   TypeConstraintGatherer({
     required TypeSystemImpl typeSystem,
     required Iterable<TypeParameterElement> typeParameters,
   }) : _typeSystem = typeSystem {
     _typeParameters.addAll(typeParameters);
   }

   bool get isConstraintSetEmpty => _constraints.isEmpty;

   DartType get _defaultTypeParameterBound {
     if (_typeSystem.isNonNullableByDefault) {
       return _typeSystem.objectQuestion;
     } else {
       return DynamicTypeImpl.instance;
     }
   }

   /// Returns the set of type constraints that was gathered.
   Map<TypeParameterElement, TypeConstraint> computeConstraints() {
     var result = <TypeParameterElement, TypeConstraint>{};
     for (var parameter in _typeParameters) {
       result[parameter] = TypeConstraint._(
         parameter,
         UnknownInferredType.instance,
         UnknownInferredType.instance,
       );
     }

     for (var constraint in _constraints) {
       var parameter = constraint.parameter;
       var mergedConstraint = result[parameter]!;

       var lower = _typeSystem.getLeastUpperBound(
         mergedConstraint.lower,
         constraint.lower,
       );

       var upper = _typeSystem.getGreatestLowerBound(
         mergedConstraint.upper,
         constraint.upper,
       );

       result[parameter] = TypeConstraint._(parameter, lower, upper);
     }

     return result;
   }

   /// Tries to match [P] as a subtype for [Q].
   ///
   /// If the match succeeds, the resulting type constraints are recorded for
   /// later use by [computeConstraints].  If the match fails, the set of type
   /// constraints is unchanged.
   bool trySubtypeMatch(DartType P, DartType Q, bool leftSchema) {
     // If `P` is `_` then the match holds with no constraints.
     if (identical(P, UnknownInferredType.instance)) {
       return true;
     }

     // If `Q` is `_` then the match holds with no constraints.
     if (identical(Q, UnknownInferredType.instance)) {
       return true;
     }

     // If `P` is a type variable `X` in `L`, then the match holds:
     //   Under constraint `_ <: X <: Q`.
     var P_nullability = P.nullabilitySuffix;
     if (P is TypeParameterType &&
         P_nullability == NullabilitySuffix.none &&
         _typeParameters.contains(P.element)) {
       _addUpper(P.element, Q);
       return true;
     }

     // If `Q` is a type variable `X` in `L`, then the match holds:
     //   Under constraint `P <: X <: _`.
     var Q_nullability = Q.nullabilitySuffix;
     if (Q is TypeParameterType &&
         Q_nullability == NullabilitySuffix.none &&
         _typeParameters.contains(Q.element)) {
       _addLower(Q.element, P);
       return true;
     }

     // If `P` and `Q` are identical types, then the subtype match holds
     // under no constraints.
     if (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 (P_nullability == NullabilitySuffix.star) {
       var P0 = (P as TypeImpl).withNullability(NullabilitySuffix.none);
       return trySubtypeMatch(P0, Q, leftSchema);
     }

     // If `Q` is a legacy type `Q0*` then the match holds under constraint
     // set `C`:
     if (Q_nullability == NullabilitySuffix.star) {
       // If `P` is `dynamic` or `void` and `P` is a subtype match
       // for `Q0` under constraint set `C`.
       if (identical(P, DynamicTypeImpl.instance) ||
           identical(P, VoidTypeImpl.instance)) {
         var rewind = _constraints.length;
         var Q0 = (Q as TypeImpl).withNullability(NullabilitySuffix.none);
         if (trySubtypeMatch(P, Q0, leftSchema)) {
           return true;
         }
         _constraints.length = rewind;
       }
       // Or if `P` is a subtype match for `Q0?` under constraint set `C`.
       var Qq = (Q as TypeImpl).withNullability(NullabilitySuffix.question);
       return trySubtypeMatch(P, Qq, leftSchema);
     }

     // If `Q` is `FutureOr<Q0>` the match holds under constraint set `C`:
     if (Q_nullability == NullabilitySuffix.none &&
         Q is InterfaceType &&
         Q.isDartAsyncFutureOr) {
       var Q0 = Q.typeArguments[0];
       var rewind = _constraints.length;

       // If `P` is `FutureOr<P0>` and `P0` is a subtype match for `Q0` under
       // constraint set `C`.
       if (P_nullability == NullabilitySuffix.none &&
           P is InterfaceType &&
           P.isDartAsyncFutureOr) {
         var P0 = P.typeArguments[0];
         if (trySubtypeMatch(P0, Q0, leftSchema)) {
           return true;
         }
         _constraints.length = rewind;
       }

       // Or if `P` is a subtype match for `Future<Q0>` under non-empty
       // constraint set `C`.
       var futureQ0 = _futureNone(Q0);
       var P_matches_FutureQ0 = trySubtypeMatch(P, futureQ0, leftSchema);
       if (P_matches_FutureQ0 && _constraints.length != rewind) {
         return true;
       }
       _constraints.length = rewind;

       // Or if `P` is a subtype match for `Q0` under constraint set `C`.
       if (trySubtypeMatch(P, Q0, leftSchema)) {
         return true;
       }
       _constraints.length = rewind;

       // Or if `P` is a subtype match for `Future<Q0>` under empty
       // constraint set `C`.
       if (P_matches_FutureQ0) {
         return true;
       }
     }

     // If `Q` is `Q0?` the match holds under constraint set `C`:
     if (Q_nullability == NullabilitySuffix.question) {
       var Q0 = (Q as TypeImpl).withNullability(NullabilitySuffix.none);
       var rewind = _constraints.length;

       // If `P` is `P0?` and `P0` is a subtype match for `Q0` under
       // constraint set `C`.
       if (P_nullability == NullabilitySuffix.question) {
         var P0 = (P as TypeImpl).withNullability(NullabilitySuffix.none);
         if (trySubtypeMatch(P0, Q0, leftSchema)) {
           return true;
         }
         _constraints.length = rewind;
       }

       // Or if `P` is `dynamic` or `void` and `Object` is a subtype match
       // for `Q0` under constraint set `C`.
       if (identical(P, DynamicTypeImpl.instance) ||
           identical(P, VoidTypeImpl.instance)) {
         if (trySubtypeMatch(_typeSystem.objectNone, Q0, leftSchema)) {
           return true;
         }
         _constraints.length = rewind;
       }

       // Or if `P` is a subtype match for `Q0` under non-empty
       // constraint set `C`.
       var P_matches_Q0 = trySubtypeMatch(P, Q0, leftSchema);
       if (P_matches_Q0 && _constraints.length != rewind) {
         return true;
       }
       _constraints.length = rewind;

       // Or if `P` is a subtype match for `Null` under constraint set `C`.
       if (trySubtypeMatch(P, _typeSystem.nullNone, leftSchema)) {
         return true;
       }
       _constraints.length = rewind;

       // Or if `P` is a subtype match for `Q0` under empty
       // constraint set `C`.
       if (P_matches_Q0) {
         return true;
       }
     }

     // If `P` is `FutureOr<P0>` the match holds under constraint set `C1 + C2`:
     if (P_nullability == NullabilitySuffix.none &&
         P is InterfaceType &&
         P.isDartAsyncFutureOr) {
       var P0 = P.typeArguments[0];
       var rewind = _constraints.length;

       // 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`.
       var future_P0 = _futureNone(P0);
       if (trySubtypeMatch(future_P0, Q, leftSchema) &&
           trySubtypeMatch(P0, Q, leftSchema)) {
         return true;
       }

       _constraints.length = rewind;
     }

     // If `P` is `P0?` the match holds under constraint set `C1 + C2`:
     if (P_nullability == NullabilitySuffix.question) {
       var P0 = (P as TypeImpl).withNullability(NullabilitySuffix.none);
       var rewind = _constraints.length;

       // 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 (trySubtypeMatch(P0, Q, leftSchema) &&
           trySubtypeMatch(_typeSystem.nullNone, Q, leftSchema)) {
         return true;
       }

       _constraints.length = rewind;
     }

     // If `Q` is `dynamic`, `Object?`, or `void` then the match holds under
     // no constraints.
     if (identical(Q, DynamicTypeImpl.instance) ||
         identical(Q, VoidTypeImpl.instance) ||
         Q_nullability == NullabilitySuffix.question && Q.isDartCoreObject) {
       return true;
     }

     // If `P` is `Never` then the match holds under no constraints.
     if (identical(P, NeverTypeImpl.instance)) {
       return true;
     }

     // If `Q` is `Object`, then the match holds under no constraints:
     //  Only if `P` is non-nullable.
     if (Q_nullability == NullabilitySuffix.none && Q.isDartCoreObject) {
       return _typeSystem.isNonNullable(P);
     }

     // If `P` is `Null`, then the match holds under no constraints:
     //  Only if `Q` is nullable.
     if (P_nullability == NullabilitySuffix.none && P.isDartCoreNull) {
       return _typeSystem.isNullable(Q);
     }

     // 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: we have already eliminated the case that `X` is a variable in `L`.
     if (P_nullability == NullabilitySuffix.none && P is TypeParameterTypeImpl) {
       var rewind = _constraints.length;
       var B = P.promotedBound ?? P.element.bound;
       if (B != null && trySubtypeMatch(B, Q, leftSchema)) {
         return true;
       }
       _constraints.length = rewind;
     }

     if (P is InterfaceType && Q is InterfaceType) {
       return _interfaceType(P, Q, leftSchema);
     }

     // If `Q` is `Function` then the match holds under no constraints:
     //   If `P` is a function type.
     if (Q_nullability == NullabilitySuffix.none && Q.isDartCoreFunction) {
       if (P is FunctionType) {
         return true;
       }
     }

     if (P is FunctionType && Q is FunctionType) {
       return _functionType(P, Q, leftSchema);
     }

     return false;
   }

   void _addLower(TypeParameterElement element, DartType lower) {
     _constraints.add(
       TypeConstraint._(element, lower, UnknownInferredType.instance),
     );
   }

   void _addUpper(TypeParameterElement element, DartType upper) {
     _constraints.add(
       TypeConstraint._(element, UnknownInferredType.instance, upper),
     );
   }

   bool _functionType(FunctionType P, FunctionType Q, bool leftSchema) {
     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 _functionType0(P, Q, leftSchema);
     }

     // 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 ?? _defaultTypeParameterBound;
       var B1 = Q_typeFormals[i].bound ?? _defaultTypeParameterBound;
       if (!trySubtypeMatch(B0, B1, leftSchema)) {
         _constraints.length = rewind;
         return false;
       }
       if (!trySubtypeMatch(B1, B0, !leftSchema)) {
         _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 (!_functionType0(P_instantiated, Q_instantiated, leftSchema)) {
       _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;
   }

   /// 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`.
   bool _functionType0(FunctionType f, FunctionType g, bool leftSchema) {
     var rewind = _constraints.length;

     // If `R0` is a subtype match for a type `R1` with respect to `L` under
     // constraints `C`.
     if (!trySubtypeMatch(f.returnType, g.returnType, leftSchema)) {
       _constraints.length = rewind;
       return false;
     }

     var fParameters = f.parameters;
     var gParameters = g.parameters;

     // And for `i` in `0...r`, `Ni` is a subtype match for `Mi` with respect
     // to `L` under constraints `Ci`.
     var fIndex = 0;
     var gIndex = 0;
     while (fIndex < fParameters.length && gIndex < gParameters.length) {
       var fParameter = fParameters[fIndex];
       var gParameter = gParameters[gIndex];
       if (fParameter.isRequiredPositional) {
         if (gParameter.isRequiredPositional) {
           if (trySubtypeMatch(gParameter.type, fParameter.type, leftSchema)) {
             fIndex++;
             gIndex++;
           } else {
             _constraints.length = rewind;
             return false;
           }
         } else {
           _constraints.length = rewind;
           return false;
         }
       } else if (fParameter.isOptionalPositional) {
         if (gParameter.isPositional) {
           if (trySubtypeMatch(gParameter.type, fParameter.type, leftSchema)) {
             fIndex++;
             gIndex++;
           } else {
             _constraints.length = rewind;
             return false;
           }
         } else {
           _constraints.length = rewind;
           return false;
         }
       } else if (fParameter.isNamed) {
         if (gParameter.isNamed) {
           var compareNames = fParameter.name.compareTo(gParameter.name);
           if (compareNames == 0) {
             if (trySubtypeMatch(gParameter.type, fParameter.type, leftSchema)) {
               fIndex++;
               gIndex++;
             } else {
               _constraints.length = rewind;
               return false;
             }
           } else if (compareNames < 0) {
             if (fParameter.isRequiredNamed) {
               _constraints.length = rewind;
               return false;
             } else {
               fIndex++;
             }
           } else {
             assert(compareNames > 0);
             // The subtype must accept all parameters of the supertype.
             _constraints.length = rewind;
             return false;
           }
         } else {
           break;
         }
       }
     }

     // The supertype must provide all required parameters to the subtype.
     while (fIndex < fParameters.length) {
       var fParameter = fParameters[fIndex++];
       if (fParameter.isRequired) {
         _constraints.length = rewind;
         return false;
       }
     }

     // The subtype must accept all parameters of the supertype.
     assert(fIndex == fParameters.length);
     if (gIndex < gParameters.length) {
       _constraints.length = rewind;
       return false;
     }

     return true;
   }

   InterfaceType _futureNone(DartType argument) {
     var element = _typeSystem.typeProvider.futureElement;
     return element.instantiate(
       typeArguments: [argument],
       nullabilitySuffix: NullabilitySuffix.none,
     );
   }

   bool _interfaceType(InterfaceType P, InterfaceType Q, bool leftSchema) {
     if (P.nullabilitySuffix != NullabilitySuffix.none) {
       return false;
     }

     if (Q.nullabilitySuffix != NullabilitySuffix.none) {
       return false;
     }

     // 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.element == Q.element) {
       if (!_interfaceType_arguments(P, Q, leftSchema)) {
         return false;
       }
       return true;
     }

     // 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`.
     var C0 = P.element;
     var C1 = Q.element;
     for (var interface in C0.allSupertypes) {
       if (interface.element == C1) {
         var substitution = Substitution.fromInterfaceType(P);
         return _interfaceType_arguments(
           substitution.substituteType(interface) as InterfaceType,
           Q,
           leftSchema,
         );
       }
     }

     return false;
   }

   /// Match arguments of [P] against arguments of [Q].
   /// If returns `false`, the constraints are unchanged.
   bool _interfaceType_arguments(
     InterfaceType P,
     InterfaceType Q,
     bool leftSchema,
   ) {
     assert(P.element == Q.element);

     var rewind = _constraints.length;

     for (var i = 0; i < P.typeArguments.length; i++) {
       var variance =
           (P.element.typeParameters[i] as TypeParameterElementImpl).variance;
       var M = P.typeArguments[i];
       var N = Q.typeArguments[i];
       if ((variance.isCovariant || variance.isInvariant) &&
           !trySubtypeMatch(M, N, leftSchema)) {
         _constraints.length = rewind;
         return false;
       }
       if ((variance.isContravariant || variance.isInvariant) &&
           !trySubtypeMatch(N, M, leftSchema)) {
         _constraints.length = rewind;
         return false;
       }
     }

     return true;
   }
 }
	// Copyright (c) 2020, the Dart project authors. Please see the AUTHORS file
	// for details. All rights reserved. Use of this source code is governed by a
	// BSD-style license that can be found in the LICENSE file.

	import 'package:analyzer/dart/element/element.dart';
	import 'package:analyzer/dart/element/nullability_suffix.dart';
	import 'package:analyzer/dart/element/type.dart';
	import 'package:analyzer/src/dart/element/element.dart';
	import 'package:analyzer/src/dart/element/type.dart';
	import 'package:analyzer/src/dart/element/type_algebra.dart';
	import 'package:analyzer/src/dart/element/type_schema.dart';
	import 'package:analyzer/src/dart/element/type_system.dart';

	/// A constraint on the type [parameter] that we're inferring.
	/// We require that `lower <: parameter <: upper`.
	class TypeConstraint {
	final TypeParameterElement parameter;
	final DartType lower;
	final DartType upper;

	TypeConstraint._(this.parameter, this.lower, this.upper);

	bool get isEmpty {
	return identical(lower, UnknownInferredType.instance) &&
	identical(upper, UnknownInferredType.instance);
	}

	@override
	String toString() {
	var lowerStr = lower.getDisplayString(withNullability: true);
	var upperStr = upper.getDisplayString(withNullability: true);
	return '$lowerStr <: ${parameter.name} <: $upperStr';
	}
	}

	/// Creates sets of [TypeConstraint]s for type parameters, based on an attempt
	/// to make one type schema a subtype of another.
	class TypeConstraintGatherer {
	final TypeSystemImpl _typeSystem;
	final Set<TypeParameterElement> _typeParameters = Set.identity();
	final List<TypeConstraint> _constraints = [];

	TypeConstraintGatherer({
	required TypeSystemImpl typeSystem,
	required Iterable<TypeParameterElement> typeParameters,
	}) : _typeSystem = typeSystem {
	_typeParameters.addAll(typeParameters);
	}

	bool get isConstraintSetEmpty => _constraints.isEmpty;

	DartType get _defaultTypeParameterBound {
	if (_typeSystem.isNonNullableByDefault) {
	return _typeSystem.objectQuestion;
	} else {
	return DynamicTypeImpl.instance;
	}
	}

	/// Returns the set of type constraints that was gathered.
	Map<TypeParameterElement, TypeConstraint> computeConstraints() {
	var result = <TypeParameterElement, TypeConstraint>{};
	for (var parameter in _typeParameters) {
	result[parameter] = TypeConstraint._(
	parameter,
	UnknownInferredType.instance,
	UnknownInferredType.instance,
	);
	}

	for (var constraint in _constraints) {
	var parameter = constraint.parameter;
	var mergedConstraint = result[parameter]!;

	var lower = _typeSystem.getLeastUpperBound(
	mergedConstraint.lower,
	constraint.lower,
	);

	var upper = _typeSystem.getGreatestLowerBound(
	mergedConstraint.upper,
	constraint.upper,
	);

	result[parameter] = TypeConstraint._(parameter, lower, upper);
	}

	return result;
	}

	/// Tries to match [P] as a subtype for [Q].
	///
	/// If the match succeeds, the resulting type constraints are recorded for
	/// later use by [computeConstraints]. If the match fails, the set of type
	/// constraints is unchanged.
	bool trySubtypeMatch(DartType P, DartType Q, bool leftSchema) {
	// If `P` is `_` then the match holds with no constraints.
	if (identical(P, UnknownInferredType.instance)) {
	return true;
	}

	// If `Q` is `_` then the match holds with no constraints.
	if (identical(Q, UnknownInferredType.instance)) {
	return true;
	}

	// If `P` is a type variable `X` in `L`, then the match holds:
	// Under constraint `_ <: X <: Q`.
	var P_nullability = P.nullabilitySuffix;
	if (P is TypeParameterType &&
	P_nullability == NullabilitySuffix.none &&
	_typeParameters.contains(P.element)) {
	_addUpper(P.element, Q);
	return true;
	}

	// If `Q` is a type variable `X` in `L`, then the match holds:
	// Under constraint `P <: X <: _`.
	var Q_nullability = Q.nullabilitySuffix;
	if (Q is TypeParameterType &&
	Q_nullability == NullabilitySuffix.none &&
	_typeParameters.contains(Q.element)) {
	_addLower(Q.element, P);
	return true;
	}

	// If `P` and `Q` are identical types, then the subtype match holds
	// under no constraints.
	if (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 (P_nullability == NullabilitySuffix.star) {
	var P0 = (P as TypeImpl).withNullability(NullabilitySuffix.none);
	return trySubtypeMatch(P0, Q, leftSchema);
	}

	// If `Q` is a legacy type `Q0*` then the match holds under constraint
	// set `C`:
	if (Q_nullability == NullabilitySuffix.star) {
	// If `P` is `dynamic` or `void` and `P` is a subtype match
	// for `Q0` under constraint set `C`.
	if (identical(P, DynamicTypeImpl.instance) \|\|
	identical(P, VoidTypeImpl.instance)) {
	var rewind = _constraints.length;
	var Q0 = (Q as TypeImpl).withNullability(NullabilitySuffix.none);
	if (trySubtypeMatch(P, Q0, leftSchema)) {
	return true;
	}
	_constraints.length = rewind;
	}
	// Or if `P` is a subtype match for `Q0?` under constraint set `C`.
	var Qq = (Q as TypeImpl).withNullability(NullabilitySuffix.question);
	return trySubtypeMatch(P, Qq, leftSchema);
	}

	// If `Q` is `FutureOr<Q0>` the match holds under constraint set `C`:
	if (Q_nullability == NullabilitySuffix.none &&
	Q is InterfaceType &&
	Q.isDartAsyncFutureOr) {
	var Q0 = Q.typeArguments[0];
	var rewind = _constraints.length;

	// If `P` is `FutureOr<P0>` and `P0` is a subtype match for `Q0` under
	// constraint set `C`.
	if (P_nullability == NullabilitySuffix.none &&
	P is InterfaceType &&
	P.isDartAsyncFutureOr) {
	var P0 = P.typeArguments[0];
	if (trySubtypeMatch(P0, Q0, leftSchema)) {
	return true;
	}
	_constraints.length = rewind;
	}

	// Or if `P` is a subtype match for `Future<Q0>` under non-empty
	// constraint set `C`.
	var futureQ0 = _futureNone(Q0);
	var P_matches_FutureQ0 = trySubtypeMatch(P, futureQ0, leftSchema);
	if (P_matches_FutureQ0 && _constraints.length != rewind) {
	return true;
	}
	_constraints.length = rewind;

	// Or if `P` is a subtype match for `Q0` under constraint set `C`.
	if (trySubtypeMatch(P, Q0, leftSchema)) {
	return true;
	}
	_constraints.length = rewind;

	// Or if `P` is a subtype match for `Future<Q0>` under empty
	// constraint set `C`.
	if (P_matches_FutureQ0) {
	return true;
	}
	}

	// If `Q` is `Q0?` the match holds under constraint set `C`:
	if (Q_nullability == NullabilitySuffix.question) {
	var Q0 = (Q as TypeImpl).withNullability(NullabilitySuffix.none);
	var rewind = _constraints.length;

	// If `P` is `P0?` and `P0` is a subtype match for `Q0` under
	// constraint set `C`.
	if (P_nullability == NullabilitySuffix.question) {
	var P0 = (P as TypeImpl).withNullability(NullabilitySuffix.none);
	if (trySubtypeMatch(P0, Q0, leftSchema)) {
	return true;
	}
	_constraints.length = rewind;
	}

	// Or if `P` is `dynamic` or `void` and `Object` is a subtype match
	// for `Q0` under constraint set `C`.
	if (identical(P, DynamicTypeImpl.instance) \|\|
	identical(P, VoidTypeImpl.instance)) {
	if (trySubtypeMatch(_typeSystem.objectNone, Q0, leftSchema)) {
	return true;
	}
	_constraints.length = rewind;
	}

	// Or if `P` is a subtype match for `Q0` under non-empty
	// constraint set `C`.
	var P_matches_Q0 = trySubtypeMatch(P, Q0, leftSchema);
	if (P_matches_Q0 && _constraints.length != rewind) {
	return true;
	}
	_constraints.length = rewind;

	// Or if `P` is a subtype match for `Null` under constraint set `C`.
	if (trySubtypeMatch(P, _typeSystem.nullNone, leftSchema)) {
	return true;
	}
	_constraints.length = rewind;

	// Or if `P` is a subtype match for `Q0` under empty
	// constraint set `C`.
	if (P_matches_Q0) {
	return true;
	}
	}

	// If `P` is `FutureOr<P0>` the match holds under constraint set `C1 + C2`:
	if (P_nullability == NullabilitySuffix.none &&
	P is InterfaceType &&
	P.isDartAsyncFutureOr) {
	var P0 = P.typeArguments[0];
	var rewind = _constraints.length;

	// 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`.
	var future_P0 = _futureNone(P0);
	if (trySubtypeMatch(future_P0, Q, leftSchema) &&
	trySubtypeMatch(P0, Q, leftSchema)) {
	return true;
	}

	_constraints.length = rewind;
	}

	// If `P` is `P0?` the match holds under constraint set `C1 + C2`:
	if (P_nullability == NullabilitySuffix.question) {
	var P0 = (P as TypeImpl).withNullability(NullabilitySuffix.none);
	var rewind = _constraints.length;

	// 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 (trySubtypeMatch(P0, Q, leftSchema) &&
	trySubtypeMatch(_typeSystem.nullNone, Q, leftSchema)) {
	return true;
	}

	_constraints.length = rewind;
	}

	// If `Q` is `dynamic`, `Object?`, or `void` then the match holds under
	// no constraints.
	if (identical(Q, DynamicTypeImpl.instance) \|\|
	identical(Q, VoidTypeImpl.instance) \|\|
	Q_nullability == NullabilitySuffix.question && Q.isDartCoreObject) {
	return true;
	}

	// If `P` is `Never` then the match holds under no constraints.
	if (identical(P, NeverTypeImpl.instance)) {
	return true;
	}

	// If `Q` is `Object`, then the match holds under no constraints:
	// Only if `P` is non-nullable.
	if (Q_nullability == NullabilitySuffix.none && Q.isDartCoreObject) {
	return _typeSystem.isNonNullable(P);
	}

	// If `P` is `Null`, then the match holds under no constraints:
	// Only if `Q` is nullable.
	if (P_nullability == NullabilitySuffix.none && P.isDartCoreNull) {
	return _typeSystem.isNullable(Q);
	}

	// 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: we have already eliminated the case that `X` is a variable in `L`.
	if (P_nullability == NullabilitySuffix.none && P is TypeParameterTypeImpl) {
	var rewind = _constraints.length;
	var B = P.promotedBound ?? P.element.bound;
	if (B != null && trySubtypeMatch(B, Q, leftSchema)) {
	return true;
	}
	_constraints.length = rewind;
	}

	if (P is InterfaceType && Q is InterfaceType) {
	return _interfaceType(P, Q, leftSchema);
	}

	// If `Q` is `Function` then the match holds under no constraints:
	// If `P` is a function type.
	if (Q_nullability == NullabilitySuffix.none && Q.isDartCoreFunction) {
	if (P is FunctionType) {
	return true;
	}
	}

	if (P is FunctionType && Q is FunctionType) {
	return _functionType(P, Q, leftSchema);
	}

	return false;
	}

	void _addLower(TypeParameterElement element, DartType lower) {
	_constraints.add(
	TypeConstraint._(element, lower, UnknownInferredType.instance),
	);
	}

	void _addUpper(TypeParameterElement element, DartType upper) {
	_constraints.add(
	TypeConstraint._(element, UnknownInferredType.instance, upper),
	);
	}

	bool _functionType(FunctionType P, FunctionType Q, bool leftSchema) {
	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 _functionType0(P, Q, leftSchema);
	}

	// 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 ?? _defaultTypeParameterBound;
	var B1 = Q_typeFormals[i].bound ?? _defaultTypeParameterBound;
	if (!trySubtypeMatch(B0, B1, leftSchema)) {
	_constraints.length = rewind;
	return false;
	}
	if (!trySubtypeMatch(B1, B0, !leftSchema)) {
	_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 (!_functionType0(P_instantiated, Q_instantiated, leftSchema)) {
	_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;
	}

	/// 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`.
	bool _functionType0(FunctionType f, FunctionType g, bool leftSchema) {
	var rewind = _constraints.length;

	// If `R0` is a subtype match for a type `R1` with respect to `L` under
	// constraints `C`.
	if (!trySubtypeMatch(f.returnType, g.returnType, leftSchema)) {
	_constraints.length = rewind;
	return false;
	}

	var fParameters = f.parameters;
	var gParameters = g.parameters;

	// And for `i` in `0...r`, `Ni` is a subtype match for `Mi` with respect
	// to `L` under constraints `Ci`.
	var fIndex = 0;
	var gIndex = 0;
	while (fIndex < fParameters.length && gIndex < gParameters.length) {
	var fParameter = fParameters[fIndex];
	var gParameter = gParameters[gIndex];
	if (fParameter.isRequiredPositional) {
	if (gParameter.isRequiredPositional) {
	if (trySubtypeMatch(gParameter.type, fParameter.type, leftSchema)) {
	fIndex++;
	gIndex++;
	} else {
	_constraints.length = rewind;
	return false;
	}
	} else {
	_constraints.length = rewind;
	return false;
	}
	} else if (fParameter.isOptionalPositional) {
	if (gParameter.isPositional) {
	if (trySubtypeMatch(gParameter.type, fParameter.type, leftSchema)) {
	fIndex++;
	gIndex++;
	} else {
	_constraints.length = rewind;
	return false;
	}
	} else {
	_constraints.length = rewind;
	return false;
	}
	} else if (fParameter.isNamed) {
	if (gParameter.isNamed) {
	var compareNames = fParameter.name.compareTo(gParameter.name);
	if (compareNames == 0) {
	if (trySubtypeMatch(gParameter.type, fParameter.type, leftSchema)) {
	fIndex++;
	gIndex++;
	} else {
	_constraints.length = rewind;
	return false;
	}
	} else if (compareNames < 0) {
	if (fParameter.isRequiredNamed) {
	_constraints.length = rewind;
	return false;
	} else {
	fIndex++;
	}
	} else {
	assert(compareNames > 0);
	// The subtype must accept all parameters of the supertype.
	_constraints.length = rewind;
	return false;
	}
	} else {
	break;
	}
	}
	}

	// The supertype must provide all required parameters to the subtype.
	while (fIndex < fParameters.length) {
	var fParameter = fParameters[fIndex++];
	if (fParameter.isRequired) {
	_constraints.length = rewind;
	return false;
	}
	}

	// The subtype must accept all parameters of the supertype.
	assert(fIndex == fParameters.length);
	if (gIndex < gParameters.length) {
	_constraints.length = rewind;
	return false;
	}

	return true;
	}

	InterfaceType _futureNone(DartType argument) {
	var element = _typeSystem.typeProvider.futureElement;
	return element.instantiate(
	typeArguments: [argument],
	nullabilitySuffix: NullabilitySuffix.none,
	);
	}

	bool _interfaceType(InterfaceType P, InterfaceType Q, bool leftSchema) {
	if (P.nullabilitySuffix != NullabilitySuffix.none) {
	return false;
	}

	if (Q.nullabilitySuffix != NullabilitySuffix.none) {
	return false;
	}

	// 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.element == Q.element) {
	if (!_interfaceType_arguments(P, Q, leftSchema)) {
	return false;
	}
	return true;
	}

	// 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`.
	var C0 = P.element;
	var C1 = Q.element;
	for (var interface in C0.allSupertypes) {
	if (interface.element == C1) {
	var substitution = Substitution.fromInterfaceType(P);
	return _interfaceType_arguments(
	substitution.substituteType(interface) as InterfaceType,
	Q,
	leftSchema,
	);
	}
	}

	return false;
	}

	/// Match arguments of [P] against arguments of [Q].
	/// If returns `false`, the constraints are unchanged.
	bool _interfaceType_arguments(
	InterfaceType P,
	InterfaceType Q,
	bool leftSchema,
	) {
	assert(P.element == Q.element);

	var rewind = _constraints.length;

	for (var i = 0; i < P.typeArguments.length; i++) {
	var variance =
	(P.element.typeParameters[i] as TypeParameterElementImpl).variance;
	var M = P.typeArguments[i];
	var N = Q.typeArguments[i];
	if ((variance.isCovariant \|\| variance.isInvariant) &&
	!trySubtypeMatch(M, N, leftSchema)) {
	_constraints.length = rewind;
	return false;
	}
	if ((variance.isContravariant \|\| variance.isInvariant) &&
	!trySubtypeMatch(N, M, leftSchema)) {
	_constraints.length = rewind;
	return false;
	}
	}

	return true;
	}
	}