| // 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; |
| } |
| } |