blob: 1bf8409c27b624dd6276db068a0e8281adcf936e [file] [log] [blame]
// 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;
InterfaceType thisType;
bool canInferReturnType = false;
DartType returnType;
DartType yieldType;
AsyncMarker currentAsyncMarker = AsyncMarker.Sync;
Procedure invokeClosure;
/// 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) : invokeClosure = coreTypes.getMember('dart:core', '_Closure', '_invoke') as Procedure;
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 any number of `Future<>` types wrapping a type.
DartType unfutureType(DartType type) {
return type is InterfaceType && type.classNode == coreTypes.futureClass
? unfutureType(type.typeArguments[0])
: 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_);
}
}
/// 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 {
Class get futureOrClass;
InterfaceType get objectType;
InterfaceType get rawFunctionType;
ClassHierarchy get hierarchy;
/// Returns true if [subtype] is a subtype of [supertype].
bool isSubtypeOf(DartType subtype, DartType supertype) {
if (identical(subtype, supertype)) return true;
if (subtype is BottomType) return true;
if (supertype is DynamicType ||
supertype is VoidType ||
supertype == objectType) {
return true;
}
if (subtype is InterfaceType && supertype is InterfaceType) {
if (supertype.classNode == futureOrClass &&
supertype.typeArguments.length == 1) {
if (isSubtypeOf(subtype, supertype.typeArguments[0])) {
return true;
}
}
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) {
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.parameter.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).
if (!isSubtypeOf(superParameter.bound, subBound)) {
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;
}
}