pkg/kernel/lib/type_environment.dart - sdk.git - Git at Google

 // Copyright (c) 2016, 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.
 library kernel.type_environment;

 import 'ast.dart';
 import 'class_hierarchy.dart';
 import 'core_types.dart';
 import 'type_algebra.dart';

 typedef void ErrorHandler(TreeNode node, String message);

 class TypeEnvironment extends SubtypeTester {
   final CoreTypes coreTypes;
   final ClassHierarchy hierarchy;
   final bool strongMode;
   InterfaceType thisType;

   DartType returnType;
   DartType yieldType;
   AsyncMarker currentAsyncMarker = AsyncMarker.Sync;

   /// An error handler for use in debugging, or `null` if type errors should not
   /// be tolerated.  See [typeError].
   ErrorHandler errorHandler;

   TypeEnvironment(this.coreTypes, this.hierarchy, {this.strongMode: false});

   InterfaceType get objectType => coreTypes.objectClass.rawType;
   InterfaceType get nullType => coreTypes.nullClass.rawType;
   InterfaceType get boolType => coreTypes.boolClass.rawType;
   InterfaceType get intType => coreTypes.intClass.rawType;
   InterfaceType get numType => coreTypes.numClass.rawType;
   InterfaceType get doubleType => coreTypes.doubleClass.rawType;
   InterfaceType get stringType => coreTypes.stringClass.rawType;
   InterfaceType get symbolType => coreTypes.symbolClass.rawType;
   InterfaceType get typeType => coreTypes.typeClass.rawType;
   InterfaceType get rawFunctionType => coreTypes.functionClass.rawType;

   Class get intClass => coreTypes.intClass;
   Class get numClass => coreTypes.numClass;
   Class get futureOrClass => coreTypes.futureOrClass;

   InterfaceType literalListType(DartType elementType) {
     return new InterfaceType(coreTypes.listClass, <DartType>[elementType]);
   }

   InterfaceType literalMapType(DartType key, DartType value) {
     return new InterfaceType(coreTypes.mapClass, <DartType>[key, value]);
   }

   InterfaceType iterableType(DartType type) {
     return new InterfaceType(coreTypes.iterableClass, <DartType>[type]);
   }

   InterfaceType streamType(DartType type) {
     return new InterfaceType(coreTypes.streamClass, <DartType>[type]);
   }

   InterfaceType futureType(DartType type) {
     return new InterfaceType(coreTypes.futureClass, <DartType>[type]);
   }

   /// Removes a level of `Future<>` types wrapping a type.
   ///
   /// This implements the function `flatten` from the spec, which unwraps a
   /// layer of Future or FutureOr from a type.
   DartType unfutureType(DartType type) {
     if (type is InterfaceType) {
       if (type.classNode == coreTypes.futureOrClass ||
           type.classNode == coreTypes.futureClass) {
         return type.typeArguments[0];
       }
       // It is a compile-time error to implement, extend, or mixin FutureOr so
       // we aren't concerned with it.  If a class implements multiple
       // instantiations of Future, getTypeAsInstanceOf is responsible for
       // picking the least one in the sense required by the spec.
       InterfaceType future =
           hierarchy.getTypeAsInstanceOf(type, coreTypes.futureClass);
       if (future != null) {
         return future.typeArguments[0];
       }
     }
     return type;
   }

   /// Called if the computation of a static type failed due to a type error.
   ///
   /// This should never happen in production.  The frontend should report type
   /// errors, and either recover from the error during translation or abort
   /// compilation if unable to recover.
   ///
   /// By default, this throws an exception, since programs in kernel are assumed
   /// to be correctly typed.
   ///
   /// An [errorHandler] may be provided in order to override the default
   /// behavior and tolerate the presence of type errors.  This can be useful for
   /// debugging IR producers which are required to produce a strongly typed IR.
   void typeError(TreeNode node, String message) {
     if (errorHandler != null) {
       errorHandler(node, message);
     } else {
       throw '$message in $node';
     }
   }

   /// True if [member] is a binary operator that returns an `int` if both
   /// operands are `int`, and otherwise returns `double`.
   ///
   /// This is a case of type-based overloading, which in Dart is only supported
   /// by giving special treatment to certain arithmetic operators.
   bool isOverloadedArithmeticOperator(Procedure member) {
     Class class_ = member.enclosingClass;
     if (class_ == coreTypes.intClass || class_ == coreTypes.numClass) {
       String name = member.name.name;
       return name == '+' ||
           name == '-' ||
           name == '*' ||
           name == 'remainder' ||
           name == '%';
     }
     return false;
   }

   /// Returns the static return type of an overloaded arithmetic operator
   /// (see [isOverloadedArithmeticOperator]) given the static type of the
   /// operands.
   ///
   /// If both types are `int`, the returned type is `int`.
   /// If either type is `double`, the returned type is `double`.
   /// If both types refer to the same type variable (typically with `num` as
   /// the upper bound), then that type variable is returned.
   /// Otherwise `num` is returned.
   DartType getTypeOfOverloadedArithmetic(DartType type1, DartType type2) {
     if (type1 == type2) return type1;
     if (type1 == doubleType || type2 == doubleType) return doubleType;
     return numType;
   }

   /// Returns true if [class_] has no proper subtypes that are usable as type
   /// argument.
   bool isSealedClass(Class class_) {
     // The sealed core classes have subtypes in the patched SDK, but those
     // classes cannot occur as type argument.
     if (class_ == coreTypes.intClass ||
         class_ == coreTypes.doubleClass ||
         class_ == coreTypes.stringClass ||
         class_ == coreTypes.boolClass ||
         class_ == coreTypes.nullClass) {
       return true;
     }
     return !hierarchy.hasProperSubtypes(class_);
   }

   bool isObject(DartType type) {
     return type is InterfaceType && type.classNode == objectType.classNode;
   }

   bool isNull(DartType type) {
     return type is InterfaceType && type.classNode == nullType.classNode;
   }

   /// Replaces all covariant occurrences of `dynamic`, `Object`, and `void` with
   /// [BottomType] and all contravariant occurrences of `Null` and [BottomType]
   /// with `Object`.
   DartType convertSuperBoundedToRegularBounded(DartType type,
       {bool isCovariant = true}) {
     if ((type is DynamicType || type is VoidType || isObject(type)) &&
         isCovariant) {
       return const BottomType();
     } else if ((type is BottomType || isNull(type)) && !isCovariant) {
       return objectType;
     } else if (type is InterfaceType && type.classNode.typeParameters != null) {
       List<DartType> replacedTypeArguments =
           new List<DartType>(type.typeArguments.length);
       for (int i = 0; i < replacedTypeArguments.length; i++) {
         replacedTypeArguments[i] = convertSuperBoundedToRegularBounded(
             type.typeArguments[i],
             isCovariant: isCovariant);
       }
       return new InterfaceType(type.classNode, replacedTypeArguments);
     } else if (type is TypedefType && type.typedefNode.typeParameters != null) {
       List<DartType> replacedTypeArguments =
           new List<DartType>(type.typeArguments.length);
       for (int i = 0; i < replacedTypeArguments.length; i++) {
         replacedTypeArguments[i] = convertSuperBoundedToRegularBounded(
             type.typeArguments[i],
             isCovariant: isCovariant);
       }
       return new TypedefType(type.typedefNode, replacedTypeArguments);
     } else if (type is FunctionType) {
       var replacedReturnType = convertSuperBoundedToRegularBounded(
           type.returnType,
           isCovariant: isCovariant);
       var replacedPositionalParameters =
           new List<DartType>(type.positionalParameters.length);
       for (int i = 0; i < replacedPositionalParameters.length; i++) {
         replacedPositionalParameters[i] = convertSuperBoundedToRegularBounded(
             type.positionalParameters[i],
             isCovariant: !isCovariant);
       }
       var replacedNamedParameters =
           new List<NamedType>(type.namedParameters.length);
       for (int i = 0; i < replacedNamedParameters.length; i++) {
         replacedNamedParameters[i] = new NamedType(
             type.namedParameters[i].name,
             convertSuperBoundedToRegularBounded(type.namedParameters[i].type,
                 isCovariant: !isCovariant));
       }
       return new FunctionType(replacedPositionalParameters, replacedReturnType,
           namedParameters: replacedNamedParameters,
           typeParameters: type.typeParameters,
           requiredParameterCount: type.requiredParameterCount,
           typedefReference: type.typedefReference);
     }
     return type;
   }

   // TODO(dmitryas):  Remove [typedefInstantiations] when type arguments passed
   // to typedefs are preserved in the Kernel output.
   List<Object> findBoundViolations(DartType type,
       {bool allowSuperBounded = false,
       Map<FunctionType, List<DartType>> typedefInstantiations}) {
     List<TypeParameter> variables;
     List<DartType> arguments;
     List<Object> typedefRhsResult;

     if (typedefInstantiations != null &&
         typedefInstantiations.containsKey(type)) {
       // [type] is a function type that is an application of a parametrized
       // typedef.  We need to check both the l.h.s. and the r.h.s. of the
       // definition in that case.  For details, see [link]
       // (https://github.com/dart-lang/sdk/blob/master/docs/language/informal/super-bounded-types.md).
       FunctionType functionType = type;
       FunctionType cloned = new FunctionType(
           functionType.positionalParameters, functionType.returnType,
           namedParameters: functionType.namedParameters,
           typeParameters: functionType.typeParameters,
           requiredParameterCount: functionType.requiredParameterCount,
           typedefReference: null);
       typedefRhsResult = findBoundViolations(cloned,
           allowSuperBounded: true,
           typedefInstantiations: typedefInstantiations);
       type = new TypedefType(functionType.typedef, typedefInstantiations[type]);
     }

     if (type is InterfaceType) {
       variables = type.classNode.typeParameters;
       arguments = type.typeArguments;
     } else if (type is TypedefType) {
       variables = type.typedefNode.typeParameters;
       arguments = type.typeArguments;
     } else if (type is FunctionType) {
       List<Object> result = <Object>[];
       for (TypeParameter parameter in type.typeParameters) {
         result.addAll(findBoundViolations(parameter.bound,
                 allowSuperBounded: true,
                 typedefInstantiations: typedefInstantiations) ??
             const <Object>[]);
       }
       for (DartType formal in type.positionalParameters) {
         result.addAll(findBoundViolations(formal,
                 allowSuperBounded: true,
                 typedefInstantiations: typedefInstantiations) ??
             const <Object>[]);
       }
       for (NamedType named in type.namedParameters) {
         result.addAll(findBoundViolations(named.type,
                 allowSuperBounded: true,
                 typedefInstantiations: typedefInstantiations) ??
             const <Object>[]);
       }
       result.addAll(findBoundViolations(type.returnType,
               allowSuperBounded: true,
               typedefInstantiations: typedefInstantiations) ??
           const <Object>[]);
       return result.isEmpty ? null : result;
     } else {
       return null;
     }

     if (variables == null) return null;

     List<Object> result;
     List<Object> argumentsResult;

     Map<TypeParameter, DartType> substitutionMap =
         new Map<TypeParameter, DartType>.fromIterables(variables, arguments);
     for (int i = 0; i < arguments.length; ++i) {
       DartType argument = arguments[i];
       if (argument is FunctionType && argument.typeParameters.length > 0) {
         // Generic function types aren't allowed as type arguments either.
         result ??= <Object>[];
         result.add(argument);
         result.add(variables[i]);
         result.add(type);
       } else if (!isSubtypeOf(
           argument, substitute(variables[i].bound, substitutionMap))) {
         result ??= <Object>[];
         result.add(argument);
         result.add(variables[i]);
         result.add(type);
       }

       List<Object> violations = findBoundViolations(argument,
           allowSuperBounded: true,
           typedefInstantiations: typedefInstantiations);
       if (violations != null) {
         argumentsResult ??= <Object>[];
         argumentsResult.addAll(violations);
       }
     }
     if (argumentsResult != null) {
       result ??= <Object>[];
       result.addAll(argumentsResult);
     }
     if (typedefRhsResult != null) {
       result ??= <Object>[];
       result.addAll(typedefRhsResult);
     }

     // [type] is regular-bounded.
     if (result == null) return null;
     if (!allowSuperBounded) return result;

     result = null;
     type = convertSuperBoundedToRegularBounded(type);
     List<DartType> argumentsToReport = arguments.toList();
     if (type is InterfaceType) {
       variables = type.classNode.typeParameters;
       arguments = type.typeArguments;
     } else if (type is TypedefType) {
       variables = type.typedefNode.typeParameters;
       arguments = type.typeArguments;
     }
     substitutionMap =
         new Map<TypeParameter, DartType>.fromIterables(variables, arguments);
     for (int i = 0; i < arguments.length; ++i) {
       DartType argument = arguments[i];
       if (argument is FunctionType && argument.typeParameters.length > 0) {
         // Generic function types aren't allowed as type arguments either.
         result ??= <Object>[];
         result.add(argumentsToReport[i]);
         result.add(variables[i]);
         result.add(type);
       } else if (!isSubtypeOf(
           argument, substitute(variables[i].bound, substitutionMap))) {
         result ??= <Object>[];
         result.add(argumentsToReport[i]);
         result.add(variables[i]);
         result.add(type);
       }
     }
     if (argumentsResult != null) {
       result ??= <Object>[];
       result.addAll(argumentsResult);
     }
     if (typedefRhsResult != null) {
       result ??= <Object>[];
       result.addAll(typedefRhsResult);
     }
     return result;
   }

   // TODO(dmitryas):  Remove [typedefInstantiations] when type arguments passed
   // to typedefs are preserved in the Kernel output.
   List<Object> findBoundViolationsElementwise(
       List<TypeParameter> parameters, List<DartType> arguments,
       {Map<FunctionType, List<DartType>> typedefInstantiations}) {
     assert(arguments.length == parameters.length);
     List<Object> result;
     var substitutionMap = <TypeParameter, DartType>{};
     for (int i = 0; i < arguments.length; ++i) {
       substitutionMap[parameters[i]] = arguments[i];
     }
     for (int i = 0; i < arguments.length; ++i) {
       DartType argument = arguments[i];
       if (argument is FunctionType && argument.typeParameters.length > 0) {
         // Generic function types aren't allowed as type arguments either.
         result ??= <Object>[];
         result.add(argument);
         result.add(parameters[i]);
         result.add(null);
       } else if (!isSubtypeOf(
           argument, substitute(parameters[i].bound, substitutionMap))) {
         result ??= <Object>[];
         result.add(argument);
         result.add(parameters[i]);
         result.add(null);
       }

       List<Object> violations = findBoundViolations(argument,
           allowSuperBounded: true,
           typedefInstantiations: typedefInstantiations);
       if (violations != null) {
         result ??= <Object>[];
         result.addAll(violations);
       }
     }
     return result;
   }

   String getGenericTypeName(DartType type) {
     if (type is InterfaceType) {
       return type.classNode.name;
     } else if (type is TypedefType) {
       return type.typedefNode.name;
     }
     return type.toString();
   }
 }

 /// The part of [TypeEnvironment] that deals with subtype tests.
 ///
 /// This lives in a separate class so it can be tested independently of the SDK.
 abstract class SubtypeTester {
   InterfaceType get objectType;
   InterfaceType get nullType;
   InterfaceType get rawFunctionType;
   ClassHierarchy get hierarchy;
   Class get futureOrClass;
   InterfaceType futureType(DartType type);
   bool get strongMode;

   /// Determines if the given type is at the bottom of the type hierarchy.  May
   /// be overridden in subclasses.
   bool isBottom(DartType type) =>
       type is BottomType || (strongMode && type == nullType);

   /// Determines if the given type is at the top of the type hierarchy.  May be
   /// overridden in subclasses.
   bool isTop(DartType type) =>
       type is DynamicType || type is VoidType || type == objectType;

   /// Returns true if [subtype] is a subtype of [supertype].
   bool isSubtypeOf(DartType subtype, DartType supertype) {
     subtype = subtype.unalias;
     supertype = supertype.unalias;
     if (identical(subtype, supertype)) return true;
     if (isBottom(subtype)) return true;
     if (isTop(supertype)) return true;

     // Handle FutureOr<T> union type.
     if (strongMode &&
         subtype is InterfaceType &&
         identical(subtype.classNode, futureOrClass)) {
       var subtypeArg = subtype.typeArguments[0];
       if (supertype is InterfaceType &&
           identical(supertype.classNode, futureOrClass)) {
         var supertypeArg = supertype.typeArguments[0];
         // FutureOr<A> <: FutureOr<B> iff A <: B
         return isSubtypeOf(subtypeArg, supertypeArg);
       }

       // given t1 is Future<A> | A, then:
       // (Future<A> | A) <: t2 iff Future<A> <: t2 and A <: t2.
       var subtypeFuture = futureType(subtypeArg);
       return isSubtypeOf(subtypeFuture, supertype) &&
           isSubtypeOf(subtypeArg, supertype);
     }

     if (strongMode &&
         supertype is InterfaceType &&
         identical(supertype.classNode, futureOrClass)) {
       // given t2 is Future<A> | A, then:
       // t1 <: (Future<A> | A) iff t1 <: Future<A> or t1 <: A
       var supertypeArg = supertype.typeArguments[0];
       var supertypeFuture = futureType(supertypeArg);
       return isSubtypeOf(subtype, supertypeFuture) ||
           isSubtypeOf(subtype, supertypeArg);
     }

     if (subtype is InterfaceType && supertype is InterfaceType) {
       var upcastType =
           hierarchy.getTypeAsInstanceOf(subtype, supertype.classNode);
       if (upcastType == null) return false;
       for (int i = 0; i < upcastType.typeArguments.length; ++i) {
         // Termination: the 'supertype' parameter decreases in size.
         if (!isSubtypeOf(
             upcastType.typeArguments[i], supertype.typeArguments[i])) {
           return false;
         }
       }
       return true;
     }
     if (subtype is TypeParameterType) {
       if (supertype is TypeParameterType &&
           subtype.parameter == supertype.parameter) {
         if (supertype.promotedBound != null) {
           return isSubtypeOf(subtype.bound, supertype.bound);
         } else {
           // Promoted bound should always be a subtype of the declared bound.
           assert(subtype.promotedBound == null ||
               isSubtypeOf(subtype.bound, supertype.bound));
           return true;
         }
       }
       // Termination: if there are no cyclically bound type parameters, this
       // recursive call can only occur a finite number of times, before reaching
       // a shrinking recursive call (or terminating).
       return isSubtypeOf(subtype.bound, supertype);
     }
     if (subtype is FunctionType) {
       if (supertype == rawFunctionType) return true;
       if (supertype is FunctionType) {
         return _isFunctionSubtypeOf(subtype, supertype);
       }
     }
     return false;
   }

   bool _isFunctionSubtypeOf(FunctionType subtype, FunctionType supertype) {
     if (subtype.requiredParameterCount > supertype.requiredParameterCount) {
       return false;
     }
     if (subtype.positionalParameters.length <
         supertype.positionalParameters.length) {
       return false;
     }
     if (subtype.typeParameters.length != supertype.typeParameters.length) {
       return false;
     }
     if (subtype.typeParameters.isNotEmpty) {
       var substitution = <TypeParameter, DartType>{};
       for (int i = 0; i < subtype.typeParameters.length; ++i) {
         var subParameter = subtype.typeParameters[i];
         var superParameter = supertype.typeParameters[i];
         substitution[subParameter] = new TypeParameterType(superParameter);
       }
       for (int i = 0; i < subtype.typeParameters.length; ++i) {
         var subParameter = subtype.typeParameters[i];
         var superParameter = supertype.typeParameters[i];
         var subBound = substitute(subParameter.bound, substitution);
         // Termination: if there are no cyclically bound type parameters, this
         // recursive call can only occur a finite number of times before
         // reaching a shrinking recursive call (or terminating).
         // TODO(dmitryas): Replace it with one recursive descent instead of two.
         if (!isSubtypeOf(superParameter.bound, subBound) ||
             !isSubtypeOf(subBound, superParameter.bound)) {
           return false;
         }
       }
       subtype = substitute(subtype.withoutTypeParameters, substitution);
     }
     if (!isSubtypeOf(subtype.returnType, supertype.returnType)) {
       return false;
     }
     for (int i = 0; i < supertype.positionalParameters.length; ++i) {
       var supertypeParameter = supertype.positionalParameters[i];
       var subtypeParameter = subtype.positionalParameters[i];
       // Termination: Both types shrink in size.
       if (!isSubtypeOf(supertypeParameter, subtypeParameter)) {
         return false;
       }
     }
     int subtypeNameIndex = 0;
     for (NamedType supertypeParameter in supertype.namedParameters) {
       while (subtypeNameIndex < subtype.namedParameters.length &&
           subtype.namedParameters[subtypeNameIndex].name !=
               supertypeParameter.name) {
         ++subtypeNameIndex;
       }
       if (subtypeNameIndex == subtype.namedParameters.length) return false;
       NamedType subtypeParameter = subtype.namedParameters[subtypeNameIndex];
       // Termination: Both types shrink in size.
       if (!isSubtypeOf(supertypeParameter.type, subtypeParameter.type)) {
         return false;
       }
     }
     return true;
   }
 }
	// Copyright (c) 2016, 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.
	library kernel.type_environment;

	import 'ast.dart';
	import 'class_hierarchy.dart';
	import 'core_types.dart';
	import 'type_algebra.dart';

	typedef void ErrorHandler(TreeNode node, String message);

	class TypeEnvironment extends SubtypeTester {
	final CoreTypes coreTypes;
	final ClassHierarchy hierarchy;
	final bool strongMode;
	InterfaceType thisType;

	DartType returnType;
	DartType yieldType;
	AsyncMarker currentAsyncMarker = AsyncMarker.Sync;

	/// An error handler for use in debugging, or `null` if type errors should not
	/// be tolerated. See [typeError].
	ErrorHandler errorHandler;

	TypeEnvironment(this.coreTypes, this.hierarchy, {this.strongMode: false});

	InterfaceType get objectType => coreTypes.objectClass.rawType;
	InterfaceType get nullType => coreTypes.nullClass.rawType;
	InterfaceType get boolType => coreTypes.boolClass.rawType;
	InterfaceType get intType => coreTypes.intClass.rawType;
	InterfaceType get numType => coreTypes.numClass.rawType;
	InterfaceType get doubleType => coreTypes.doubleClass.rawType;
	InterfaceType get stringType => coreTypes.stringClass.rawType;
	InterfaceType get symbolType => coreTypes.symbolClass.rawType;
	InterfaceType get typeType => coreTypes.typeClass.rawType;
	InterfaceType get rawFunctionType => coreTypes.functionClass.rawType;

	Class get intClass => coreTypes.intClass;
	Class get numClass => coreTypes.numClass;
	Class get futureOrClass => coreTypes.futureOrClass;

	InterfaceType literalListType(DartType elementType) {
	return new InterfaceType(coreTypes.listClass, <DartType>[elementType]);
	}

	InterfaceType literalMapType(DartType key, DartType value) {
	return new InterfaceType(coreTypes.mapClass, <DartType>[key, value]);
	}

	InterfaceType iterableType(DartType type) {
	return new InterfaceType(coreTypes.iterableClass, <DartType>[type]);
	}

	InterfaceType streamType(DartType type) {
	return new InterfaceType(coreTypes.streamClass, <DartType>[type]);
	}

	InterfaceType futureType(DartType type) {
	return new InterfaceType(coreTypes.futureClass, <DartType>[type]);
	}

	/// Removes a level of `Future<>` types wrapping a type.
	///
	/// This implements the function `flatten` from the spec, which unwraps a
	/// layer of Future or FutureOr from a type.
	DartType unfutureType(DartType type) {
	if (type is InterfaceType) {
	if (type.classNode == coreTypes.futureOrClass \|\|
	type.classNode == coreTypes.futureClass) {
	return type.typeArguments[0];
	}
	// It is a compile-time error to implement, extend, or mixin FutureOr so
	// we aren't concerned with it. If a class implements multiple
	// instantiations of Future, getTypeAsInstanceOf is responsible for
	// picking the least one in the sense required by the spec.
	InterfaceType future =
	hierarchy.getTypeAsInstanceOf(type, coreTypes.futureClass);
	if (future != null) {
	return future.typeArguments[0];
	}
	}
	return type;
	}

	/// Called if the computation of a static type failed due to a type error.
	///
	/// This should never happen in production. The frontend should report type
	/// errors, and either recover from the error during translation or abort
	/// compilation if unable to recover.
	///
	/// By default, this throws an exception, since programs in kernel are assumed
	/// to be correctly typed.
	///
	/// An [errorHandler] may be provided in order to override the default
	/// behavior and tolerate the presence of type errors. This can be useful for
	/// debugging IR producers which are required to produce a strongly typed IR.
	void typeError(TreeNode node, String message) {
	if (errorHandler != null) {
	errorHandler(node, message);
	} else {
	throw '$message in $node';
	}
	}

	/// True if [member] is a binary operator that returns an `int` if both
	/// operands are `int`, and otherwise returns `double`.
	///
	/// This is a case of type-based overloading, which in Dart is only supported
	/// by giving special treatment to certain arithmetic operators.
	bool isOverloadedArithmeticOperator(Procedure member) {
	Class class_ = member.enclosingClass;
	if (class_ == coreTypes.intClass \|\| class_ == coreTypes.numClass) {
	String name = member.name.name;
	return name == '+' \|\|
	name == '-' \|\|
	name == '*' \|\|
	name == 'remainder' \|\|
	name == '%';
	}
	return false;
	}

	/// Returns the static return type of an overloaded arithmetic operator
	/// (see [isOverloadedArithmeticOperator]) given the static type of the
	/// operands.
	///
	/// If both types are `int`, the returned type is `int`.
	/// If either type is `double`, the returned type is `double`.
	/// If both types refer to the same type variable (typically with `num` as
	/// the upper bound), then that type variable is returned.
	/// Otherwise `num` is returned.
	DartType getTypeOfOverloadedArithmetic(DartType type1, DartType type2) {
	if (type1 == type2) return type1;
	if (type1 == doubleType \|\| type2 == doubleType) return doubleType;
	return numType;
	}

	/// Returns true if [class_] has no proper subtypes that are usable as type
	/// argument.
	bool isSealedClass(Class class_) {
	// The sealed core classes have subtypes in the patched SDK, but those
	// classes cannot occur as type argument.
	if (class_ == coreTypes.intClass \|\|
	class_ == coreTypes.doubleClass \|\|
	class_ == coreTypes.stringClass \|\|
	class_ == coreTypes.boolClass \|\|
	class_ == coreTypes.nullClass) {
	return true;
	}
	return !hierarchy.hasProperSubtypes(class_);
	}

	bool isObject(DartType type) {
	return type is InterfaceType && type.classNode == objectType.classNode;
	}

	bool isNull(DartType type) {
	return type is InterfaceType && type.classNode == nullType.classNode;
	}

	/// Replaces all covariant occurrences of `dynamic`, `Object`, and `void` with
	/// [BottomType] and all contravariant occurrences of `Null` and [BottomType]
	/// with `Object`.
	DartType convertSuperBoundedToRegularBounded(DartType type,
	{bool isCovariant = true}) {
	if ((type is DynamicType \|\| type is VoidType \|\| isObject(type)) &&
	isCovariant) {
	return const BottomType();
	} else if ((type is BottomType \|\| isNull(type)) && !isCovariant) {
	return objectType;
	} else if (type is InterfaceType && type.classNode.typeParameters != null) {
	List<DartType> replacedTypeArguments =
	new List<DartType>(type.typeArguments.length);
	for (int i = 0; i < replacedTypeArguments.length; i++) {
	replacedTypeArguments[i] = convertSuperBoundedToRegularBounded(
	type.typeArguments[i],
	isCovariant: isCovariant);
	}
	return new InterfaceType(type.classNode, replacedTypeArguments);
	} else if (type is TypedefType && type.typedefNode.typeParameters != null) {
	List<DartType> replacedTypeArguments =
	new List<DartType>(type.typeArguments.length);
	for (int i = 0; i < replacedTypeArguments.length; i++) {
	replacedTypeArguments[i] = convertSuperBoundedToRegularBounded(
	type.typeArguments[i],
	isCovariant: isCovariant);
	}
	return new TypedefType(type.typedefNode, replacedTypeArguments);
	} else if (type is FunctionType) {
	var replacedReturnType = convertSuperBoundedToRegularBounded(
	type.returnType,
	isCovariant: isCovariant);
	var replacedPositionalParameters =
	new List<DartType>(type.positionalParameters.length);
	for (int i = 0; i < replacedPositionalParameters.length; i++) {
	replacedPositionalParameters[i] = convertSuperBoundedToRegularBounded(
	type.positionalParameters[i],
	isCovariant: !isCovariant);
	}
	var replacedNamedParameters =
	new List<NamedType>(type.namedParameters.length);
	for (int i = 0; i < replacedNamedParameters.length; i++) {
	replacedNamedParameters[i] = new NamedType(
	type.namedParameters[i].name,
	convertSuperBoundedToRegularBounded(type.namedParameters[i].type,
	isCovariant: !isCovariant));
	}
	return new FunctionType(replacedPositionalParameters, replacedReturnType,
	namedParameters: replacedNamedParameters,
	typeParameters: type.typeParameters,
	requiredParameterCount: type.requiredParameterCount,
	typedefReference: type.typedefReference);
	}
	return type;
	}

	// TODO(dmitryas): Remove [typedefInstantiations] when type arguments passed
	// to typedefs are preserved in the Kernel output.
	List<Object> findBoundViolations(DartType type,
	{bool allowSuperBounded = false,
	Map<FunctionType, List<DartType>> typedefInstantiations}) {
	List<TypeParameter> variables;
	List<DartType> arguments;
	List<Object> typedefRhsResult;

	if (typedefInstantiations != null &&
	typedefInstantiations.containsKey(type)) {
	// [type] is a function type that is an application of a parametrized
	// typedef. We need to check both the l.h.s. and the r.h.s. of the
	// definition in that case. For details, see [link]
	// (https://github.com/dart-lang/sdk/blob/master/docs/language/informal/super-bounded-types.md).
	FunctionType functionType = type;
	FunctionType cloned = new FunctionType(
	functionType.positionalParameters, functionType.returnType,
	namedParameters: functionType.namedParameters,
	typeParameters: functionType.typeParameters,
	requiredParameterCount: functionType.requiredParameterCount,
	typedefReference: null);
	typedefRhsResult = findBoundViolations(cloned,
	allowSuperBounded: true,
	typedefInstantiations: typedefInstantiations);
	type = new TypedefType(functionType.typedef, typedefInstantiations[type]);
	}

	if (type is InterfaceType) {
	variables = type.classNode.typeParameters;
	arguments = type.typeArguments;
	} else if (type is TypedefType) {
	variables = type.typedefNode.typeParameters;
	arguments = type.typeArguments;
	} else if (type is FunctionType) {
	List<Object> result = <Object>[];
	for (TypeParameter parameter in type.typeParameters) {
	result.addAll(findBoundViolations(parameter.bound,
	allowSuperBounded: true,
	typedefInstantiations: typedefInstantiations) ??
	const <Object>[]);
	}
	for (DartType formal in type.positionalParameters) {
	result.addAll(findBoundViolations(formal,
	allowSuperBounded: true,
	typedefInstantiations: typedefInstantiations) ??
	const <Object>[]);
	}
	for (NamedType named in type.namedParameters) {
	result.addAll(findBoundViolations(named.type,
	allowSuperBounded: true,
	typedefInstantiations: typedefInstantiations) ??
	const <Object>[]);
	}
	result.addAll(findBoundViolations(type.returnType,
	allowSuperBounded: true,
	typedefInstantiations: typedefInstantiations) ??
	const <Object>[]);
	return result.isEmpty ? null : result;
	} else {
	return null;
	}

	if (variables == null) return null;

	List<Object> result;
	List<Object> argumentsResult;

	Map<TypeParameter, DartType> substitutionMap =
	new Map<TypeParameter, DartType>.fromIterables(variables, arguments);
	for (int i = 0; i < arguments.length; ++i) {
	DartType argument = arguments[i];
	if (argument is FunctionType && argument.typeParameters.length > 0) {
	// Generic function types aren't allowed as type arguments either.
	result ??= <Object>[];
	result.add(argument);
	result.add(variables[i]);
	result.add(type);
	} else if (!isSubtypeOf(
	argument, substitute(variables[i].bound, substitutionMap))) {
	result ??= <Object>[];
	result.add(argument);
	result.add(variables[i]);
	result.add(type);
	}

	List<Object> violations = findBoundViolations(argument,
	allowSuperBounded: true,
	typedefInstantiations: typedefInstantiations);
	if (violations != null) {
	argumentsResult ??= <Object>[];
	argumentsResult.addAll(violations);
	}
	}
	if (argumentsResult != null) {
	result ??= <Object>[];
	result.addAll(argumentsResult);
	}
	if (typedefRhsResult != null) {
	result ??= <Object>[];
	result.addAll(typedefRhsResult);
	}

	// [type] is regular-bounded.
	if (result == null) return null;
	if (!allowSuperBounded) return result;

	result = null;
	type = convertSuperBoundedToRegularBounded(type);
	List<DartType> argumentsToReport = arguments.toList();
	if (type is InterfaceType) {
	variables = type.classNode.typeParameters;
	arguments = type.typeArguments;
	} else if (type is TypedefType) {
	variables = type.typedefNode.typeParameters;
	arguments = type.typeArguments;
	}
	substitutionMap =
	new Map<TypeParameter, DartType>.fromIterables(variables, arguments);
	for (int i = 0; i < arguments.length; ++i) {
	DartType argument = arguments[i];
	if (argument is FunctionType && argument.typeParameters.length > 0) {
	// Generic function types aren't allowed as type arguments either.
	result ??= <Object>[];
	result.add(argumentsToReport[i]);
	result.add(variables[i]);
	result.add(type);
	} else if (!isSubtypeOf(
	argument, substitute(variables[i].bound, substitutionMap))) {
	result ??= <Object>[];
	result.add(argumentsToReport[i]);
	result.add(variables[i]);
	result.add(type);
	}
	}
	if (argumentsResult != null) {
	result ??= <Object>[];
	result.addAll(argumentsResult);
	}
	if (typedefRhsResult != null) {
	result ??= <Object>[];
	result.addAll(typedefRhsResult);
	}
	return result;
	}

	// TODO(dmitryas): Remove [typedefInstantiations] when type arguments passed
	// to typedefs are preserved in the Kernel output.
	List<Object> findBoundViolationsElementwise(
	List<TypeParameter> parameters, List<DartType> arguments,
	{Map<FunctionType, List<DartType>> typedefInstantiations}) {
	assert(arguments.length == parameters.length);
	List<Object> result;
	var substitutionMap = <TypeParameter, DartType>{};
	for (int i = 0; i < arguments.length; ++i) {
	substitutionMap[parameters[i]] = arguments[i];
	}
	for (int i = 0; i < arguments.length; ++i) {
	DartType argument = arguments[i];
	if (argument is FunctionType && argument.typeParameters.length > 0) {
	// Generic function types aren't allowed as type arguments either.
	result ??= <Object>[];
	result.add(argument);
	result.add(parameters[i]);
	result.add(null);
	} else if (!isSubtypeOf(
	argument, substitute(parameters[i].bound, substitutionMap))) {
	result ??= <Object>[];
	result.add(argument);
	result.add(parameters[i]);
	result.add(null);
	}

	List<Object> violations = findBoundViolations(argument,
	allowSuperBounded: true,
	typedefInstantiations: typedefInstantiations);
	if (violations != null) {
	result ??= <Object>[];
	result.addAll(violations);
	}
	}
	return result;
	}

	String getGenericTypeName(DartType type) {
	if (type is InterfaceType) {
	return type.classNode.name;
	} else if (type is TypedefType) {
	return type.typedefNode.name;
	}
	return type.toString();
	}
	}

	/// The part of [TypeEnvironment] that deals with subtype tests.
	///
	/// This lives in a separate class so it can be tested independently of the SDK.
	abstract class SubtypeTester {
	InterfaceType get objectType;
	InterfaceType get nullType;
	InterfaceType get rawFunctionType;
	ClassHierarchy get hierarchy;
	Class get futureOrClass;
	InterfaceType futureType(DartType type);
	bool get strongMode;

	/// Determines if the given type is at the bottom of the type hierarchy. May
	/// be overridden in subclasses.
	bool isBottom(DartType type) =>
	type is BottomType \|\| (strongMode && type == nullType);

	/// Determines if the given type is at the top of the type hierarchy. May be
	/// overridden in subclasses.
	bool isTop(DartType type) =>
	type is DynamicType \|\| type is VoidType \|\| type == objectType;

	/// Returns true if [subtype] is a subtype of [supertype].
	bool isSubtypeOf(DartType subtype, DartType supertype) {
	subtype = subtype.unalias;
	supertype = supertype.unalias;
	if (identical(subtype, supertype)) return true;
	if (isBottom(subtype)) return true;
	if (isTop(supertype)) return true;

	// Handle FutureOr<T> union type.
	if (strongMode &&
	subtype is InterfaceType &&
	identical(subtype.classNode, futureOrClass)) {
	var subtypeArg = subtype.typeArguments[0];
	if (supertype is InterfaceType &&
	identical(supertype.classNode, futureOrClass)) {
	var supertypeArg = supertype.typeArguments[0];
	// FutureOr<A> <: FutureOr<B> iff A <: B
	return isSubtypeOf(subtypeArg, supertypeArg);
	}

	// given t1 is Future<A> \| A, then:
	// (Future<A> \| A) <: t2 iff Future<A> <: t2 and A <: t2.
	var subtypeFuture = futureType(subtypeArg);
	return isSubtypeOf(subtypeFuture, supertype) &&
	isSubtypeOf(subtypeArg, supertype);
	}

	if (strongMode &&
	supertype is InterfaceType &&
	identical(supertype.classNode, futureOrClass)) {
	// given t2 is Future<A> \| A, then:
	// t1 <: (Future<A> \| A) iff t1 <: Future<A> or t1 <: A
	var supertypeArg = supertype.typeArguments[0];
	var supertypeFuture = futureType(supertypeArg);
	return isSubtypeOf(subtype, supertypeFuture) \|\|
	isSubtypeOf(subtype, supertypeArg);
	}

	if (subtype is InterfaceType && supertype is InterfaceType) {
	var upcastType =
	hierarchy.getTypeAsInstanceOf(subtype, supertype.classNode);
	if (upcastType == null) return false;
	for (int i = 0; i < upcastType.typeArguments.length; ++i) {
	// Termination: the 'supertype' parameter decreases in size.
	if (!isSubtypeOf(
	upcastType.typeArguments[i], supertype.typeArguments[i])) {
	return false;
	}
	}
	return true;
	}
	if (subtype is TypeParameterType) {
	if (supertype is TypeParameterType &&
	subtype.parameter == supertype.parameter) {
	if (supertype.promotedBound != null) {
	return isSubtypeOf(subtype.bound, supertype.bound);
	} else {
	// Promoted bound should always be a subtype of the declared bound.
	assert(subtype.promotedBound == null \|\|
	isSubtypeOf(subtype.bound, supertype.bound));
	return true;
	}
	}
	// Termination: if there are no cyclically bound type parameters, this
	// recursive call can only occur a finite number of times, before reaching
	// a shrinking recursive call (or terminating).
	return isSubtypeOf(subtype.bound, supertype);
	}
	if (subtype is FunctionType) {
	if (supertype == rawFunctionType) return true;
	if (supertype is FunctionType) {
	return _isFunctionSubtypeOf(subtype, supertype);
	}
	}
	return false;
	}

	bool _isFunctionSubtypeOf(FunctionType subtype, FunctionType supertype) {
	if (subtype.requiredParameterCount > supertype.requiredParameterCount) {
	return false;
	}
	if (subtype.positionalParameters.length <
	supertype.positionalParameters.length) {
	return false;
	}
	if (subtype.typeParameters.length != supertype.typeParameters.length) {
	return false;
	}
	if (subtype.typeParameters.isNotEmpty) {
	var substitution = <TypeParameter, DartType>{};
	for (int i = 0; i < subtype.typeParameters.length; ++i) {
	var subParameter = subtype.typeParameters[i];
	var superParameter = supertype.typeParameters[i];
	substitution[subParameter] = new TypeParameterType(superParameter);
	}
	for (int i = 0; i < subtype.typeParameters.length; ++i) {
	var subParameter = subtype.typeParameters[i];
	var superParameter = supertype.typeParameters[i];
	var subBound = substitute(subParameter.bound, substitution);
	// Termination: if there are no cyclically bound type parameters, this
	// recursive call can only occur a finite number of times before
	// reaching a shrinking recursive call (or terminating).
	// TODO(dmitryas): Replace it with one recursive descent instead of two.
	if (!isSubtypeOf(superParameter.bound, subBound) \|\|
	!isSubtypeOf(subBound, superParameter.bound)) {
	return false;
	}
	}
	subtype = substitute(subtype.withoutTypeParameters, substitution);
	}
	if (!isSubtypeOf(subtype.returnType, supertype.returnType)) {
	return false;
	}
	for (int i = 0; i < supertype.positionalParameters.length; ++i) {
	var supertypeParameter = supertype.positionalParameters[i];
	var subtypeParameter = subtype.positionalParameters[i];
	// Termination: Both types shrink in size.
	if (!isSubtypeOf(supertypeParameter, subtypeParameter)) {
	return false;
	}
	}
	int subtypeNameIndex = 0;
	for (NamedType supertypeParameter in supertype.namedParameters) {
	while (subtypeNameIndex < subtype.namedParameters.length &&
	subtype.namedParameters[subtypeNameIndex].name !=
	supertypeParameter.name) {
	++subtypeNameIndex;
	}
	if (subtypeNameIndex == subtype.namedParameters.length) return false;
	NamedType subtypeParameter = subtype.namedParameters[subtypeNameIndex];
	// Termination: Both types shrink in size.
	if (!isSubtypeOf(supertypeParameter.type, subtypeParameter.type)) {
	return false;
	}
	}
	return true;
	}
	}