| // 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'; |
| |
| import 'src/hierarchy_based_type_environment.dart' |
| show HierarchyBasedTypeEnvironment; |
| |
| typedef void ErrorHandler(TreeNode node, String message); |
| |
| abstract class TypeEnvironment extends SubtypeTester { |
| final CoreTypes coreTypes; |
| |
| 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.fromSubclass(this.coreTypes); |
| |
| factory TypeEnvironment(CoreTypes coreTypes, ClassHierarchy hierarchy) { |
| return new HierarchyBasedTypeEnvironment(coreTypes, hierarchy); |
| } |
| |
| Class get intClass => coreTypes.intClass; |
| Class get numClass => coreTypes.numClass; |
| Class get functionClass => coreTypes.functionClass; |
| Class get futureOrClass => coreTypes.futureOrClass; |
| Class get objectClass => coreTypes.objectClass; |
| |
| InterfaceType get objectLegacyRawType => coreTypes.objectLegacyRawType; |
| InterfaceType get objectNullableRawType => coreTypes.objectNullableRawType; |
| InterfaceType get nullType => coreTypes.nullType; |
| InterfaceType get functionLegacyRawType => coreTypes.functionLegacyRawType; |
| |
| InterfaceType literalListType(DartType elementType) { |
| return new InterfaceType(coreTypes.listClass, <DartType>[elementType]); |
| } |
| |
| InterfaceType literalSetType(DartType elementType) { |
| return new InterfaceType(coreTypes.setClass, <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, |
| [Nullability nullability = Nullability.legacy]) { |
| return new InterfaceType( |
| coreTypes.futureClass, <DartType>[type], nullability); |
| } |
| |
| /// 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 = 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 is InterfaceType && type2 is InterfaceType) { |
| if (type1.classNode == type2.classNode) { |
| return type1; |
| } |
| if (type1.classNode == coreTypes.doubleClass || |
| type2.classNode == coreTypes.doubleClass) { |
| return coreTypes.doubleRawType(type1.nullability); |
| } |
| } |
| |
| return coreTypes.numRawType(type1.nullability); |
| } |
| } |
| |
| /// Result of a nullability-aware subtype check. |
| /// |
| /// It is assumed that if a subtype check succeeds for two types in full-NNBD |
| /// mode, it also succeeds for those two types if the nullability markers on the |
| /// types and all of their sub-terms are ignored (that is, in the pre-NNBD |
| /// mode). By contraposition, if a subtype check fails for two types when the |
| /// nullability markers are ignored, it should also fail for those types in |
| /// full-NNBD mode. |
| class IsSubtypeOf { |
| /// Internal value constructed via [IsSubtypeOf.never]. |
| /// |
| /// The integer values of [_valueNever], [_valueOnlyIfIgnoringNullabilities], |
| /// and [_valueAlways] are important for the implementations of [_joinValues], |
| /// [_all], and [join]. They should be kept in sync. |
| static const int _valueNever = 0; |
| |
| /// Internal value constructed via [IsSubtypeOf.onlyIfIgnoringNullabilities]. |
| static const int _valueOnlyIfIgnoringNullabilities = 1; |
| |
| /// Internal value constructed via [IsSubtypeOf.always]. |
| static const int _valueAlways = 3; |
| |
| static const List<IsSubtypeOf> _all = const <IsSubtypeOf>[ |
| const IsSubtypeOf.never(), |
| const IsSubtypeOf.onlyIfIgnoringNullabilities(), |
| null, // Deliberately left empty because there's no index value for that. |
| const IsSubtypeOf.always() |
| ]; |
| |
| /// Joins results of subtype checks on parts into the overall result. |
| /// |
| /// Both [value1] and [value2] should be chosen from |
| /// [_valueNever], [_valueOnlyIfIgnoringNullabilities], and [_valueAlways]. |
| /// The method produces the result which is one of [_valueNever], |
| /// [_valueOnlyIfIgnoringNullabilities], and [_valueAlways]. |
| static int _joinValues(int value1, int value2) => value1 & value2; |
| |
| /// The only state of an [IsSubtypeOf] object. |
| final int _value; |
| |
| const IsSubtypeOf._internal(int value) : _value = value; |
| |
| /// Subtype check succeeds in both modes. |
| const IsSubtypeOf.always() : this._internal(_valueAlways); |
| |
| /// Subtype check succeeds only if the nullability markers are ignored. |
| /// |
| /// This implies that if the nullability markers aren't ignored, the subtype |
| /// check fails. |
| const IsSubtypeOf.onlyIfIgnoringNullabilities() |
| : this._internal(_valueOnlyIfIgnoringNullabilities); |
| |
| /// Subtype check fails in both modes. |
| const IsSubtypeOf.never() : this._internal(_valueNever); |
| |
| /// Checks if two types are in relation based solely on their nullabilities. |
| factory IsSubtypeOf.basedSolelyOnNullabilities( |
| DartType subtype, DartType supertype) { |
| if (subtype.isPotentiallyNullable && supertype.isPotentiallyNonNullable) { |
| return const IsSubtypeOf.onlyIfIgnoringNullabilities(); |
| } |
| return const IsSubtypeOf.always(); |
| } |
| |
| /// Combines results for the type parts into the overall result for the type. |
| /// |
| /// For example, the result of `A<B1, C1>? <: A<B2, C2>*` can be computed as |
| /// `Rb.join(Rc).join(Rn)` where `Rb` is the result of `B1 <: B2`, `Rc` is the |
| /// result of `C1 <: C2`, and `Rn` is |
| /// `new IsSubtypeOf.basedSolelyOnNullabilities(A<B1, C1>?, A<B2, C2>*)`. |
| IsSubtypeOf join(IsSubtypeOf other) { |
| return _all[_joinValues(_value, other._value)]; |
| } |
| |
| /// Shorts the computation of [join] if `this` is [IsSubtypeOf.never]. |
| /// |
| /// Use this instead of [join] for optimization in case the argument to [join] |
| /// is, for example, a potentially expensive subtype check. Unlike [join], |
| /// [joinWithSubtypeCheckFor] will immediately return if [this] was |
| /// constructed as [IsSubtypeOf.never] because the right-hand side will not |
| /// change the result anyway. |
| IsSubtypeOf joinWithSubtypeCheckFor( |
| DartType subtype, DartType supertype, SubtypeTester tester) { |
| if (_value == _valueNever) return this; |
| return this |
| .join(tester.performNullabilityAwareSubtypeCheck(subtype, supertype)); |
| } |
| |
| bool isSubtypeWhenIgnoringNullabilities() { |
| return _value != _valueNever; |
| } |
| |
| bool isSubtypeWhenUsingNullabilities() { |
| return _value == _valueAlways; |
| } |
| } |
| |
| enum SubtypeCheckMode { |
| withNullabilities, |
| ignoringNullabilities, |
| } |
| |
| /// 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 objectLegacyRawType; |
| InterfaceType get objectNullableRawType; |
| InterfaceType get nullType; |
| InterfaceType get functionLegacyRawType; |
| Class get objectClass; |
| Class get functionClass; |
| Class get futureOrClass; |
| InterfaceType futureType(DartType type, |
| [Nullability nullability = Nullability.legacy]); |
| |
| static List<Object> typeChecks; |
| |
| InterfaceType getTypeAsInstanceOf(InterfaceType type, Class superclass); |
| |
| /// Determines if the given type is at the top of the type hierarchy. May be |
| /// overridden in subclasses. |
| bool isTop(DartType type) { |
| return type is DynamicType || |
| type is VoidType || |
| type == objectLegacyRawType || |
| type == objectNullableRawType; |
| } |
| |
| /// Can be use to collect type checks. To use: |
| /// 1. Rename `isSubtypeOf` to `_isSubtypeOf`. |
| /// 2. Rename `_collect_isSubtypeOf` to `isSubtypeOf`. |
| /// 3. Comment out the call to `_isSubtypeOf` below. |
| // ignore:unused_element |
| bool _collect_isSubtypeOf( |
| DartType subtype, DartType supertype, SubtypeCheckMode mode) { |
| bool result = true; |
| //result = _isSubtypeOf(subtype, supertype, mode); |
| typeChecks ??= <Object>[]; |
| typeChecks.add([subtype, supertype, result]); |
| return result; |
| } |
| |
| /// Returns true if [subtype] is a subtype of [supertype]. |
| bool isSubtypeOf( |
| DartType subtype, DartType supertype, SubtypeCheckMode mode) { |
| IsSubtypeOf result = |
| performNullabilityAwareSubtypeCheck(subtype, supertype); |
| switch (mode) { |
| case SubtypeCheckMode.ignoringNullabilities: |
| return result.isSubtypeWhenIgnoringNullabilities(); |
| case SubtypeCheckMode.withNullabilities: |
| return result.isSubtypeWhenUsingNullabilities(); |
| default: |
| throw new StateError("Unhandled subtype checking mode '$mode'"); |
| } |
| } |
| |
| /// Performs a nullability-aware subtype check. |
| /// |
| /// The outcome is described in the comments to [IsSubtypeOf]. |
| IsSubtypeOf performNullabilityAwareSubtypeCheck( |
| DartType subtype, DartType supertype) { |
| subtype = subtype.unalias; |
| supertype = supertype.unalias; |
| if (identical(subtype, supertype)) return const IsSubtypeOf.always(); |
| if (subtype is BottomType) return const IsSubtypeOf.always(); |
| if (subtype is NeverType) { |
| return supertype is BottomType |
| ? const IsSubtypeOf.never() |
| : new IsSubtypeOf.basedSolelyOnNullabilities(subtype, supertype); |
| } |
| if (subtype == nullType) { |
| // TODO(dmitryas): Remove InvalidType from subtype relation. |
| if (supertype is InvalidType) { |
| // The return value is supposed to keep the backward compatibility. |
| return const IsSubtypeOf.always(); |
| } |
| |
| if (supertype.nullability == Nullability.nullable || |
| supertype.nullability == Nullability.legacy) { |
| return const IsSubtypeOf.always(); |
| } |
| // See rule 4 of the subtype rules from the Dart Language Specification. |
| return supertype is BottomType || supertype is NeverType |
| ? const IsSubtypeOf.never() |
| : const IsSubtypeOf.onlyIfIgnoringNullabilities(); |
| } |
| if (isTop(supertype)) return const IsSubtypeOf.always(); |
| |
| // Handle FutureOr<T> union type. |
| if (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 performNullabilityAwareSubtypeCheck(subtypeArg, supertypeArg); |
| } |
| |
| // given t1 is Future<A> | A, then: |
| // (Future<A> | A) <: t2 iff Future<A> <: t2 and A <: t2. |
| return performNullabilityAwareSubtypeCheck(subtypeArg, supertype) |
| .joinWithSubtypeCheckFor( |
| futureType(subtypeArg, Nullability.nonNullable), supertype, this) |
| .join(new IsSubtypeOf.basedSolelyOnNullabilities(subtype, supertype)); |
| } |
| |
| if (supertype is InterfaceType && supertype.classNode == objectClass) { |
| assert(supertype.nullability == Nullability.nonNullable); |
| return new IsSubtypeOf.basedSolelyOnNullabilities(subtype, supertype); |
| } |
| |
| if (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, Nullability.legacy); |
| return performNullabilityAwareSubtypeCheck(subtype, supertypeFuture) |
| .isSubtypeWhenIgnoringNullabilities() || |
| performNullabilityAwareSubtypeCheck(subtype, supertypeArg) |
| .isSubtypeWhenIgnoringNullabilities() |
| ? const IsSubtypeOf.always() |
| : const IsSubtypeOf.never(); |
| } |
| |
| if (subtype is InterfaceType && supertype is InterfaceType) { |
| var upcastType = getTypeAsInstanceOf(subtype, supertype.classNode); |
| if (upcastType == null) return const IsSubtypeOf.never(); |
| IsSubtypeOf result = const IsSubtypeOf.always(); |
| for (int i = 0; i < upcastType.typeArguments.length; ++i) { |
| // Termination: the 'supertype' parameter decreases in size. |
| int variance = upcastType.classNode.typeParameters[i].variance; |
| DartType leftType = upcastType.typeArguments[i]; |
| DartType rightType = supertype.typeArguments[i]; |
| if (variance == Variance.contravariant) { |
| result = result |
| .join(performNullabilityAwareSubtypeCheck(rightType, leftType)); |
| if (!result.isSubtypeWhenIgnoringNullabilities()) { |
| return const IsSubtypeOf.never(); |
| } |
| } else if (variance == Variance.invariant) { |
| result = result.join( |
| performNullabilityAwareMutualSubtypesCheck(leftType, rightType)); |
| if (!result.isSubtypeWhenIgnoringNullabilities()) { |
| return const IsSubtypeOf.never(); |
| } |
| } else { |
| result = result |
| .join(performNullabilityAwareSubtypeCheck(leftType, rightType)); |
| if (!result.isSubtypeWhenIgnoringNullabilities()) { |
| return const IsSubtypeOf.never(); |
| } |
| } |
| } |
| return result |
| .join(new IsSubtypeOf.basedSolelyOnNullabilities(subtype, supertype)); |
| } |
| if (subtype is TypeParameterType) { |
| if (supertype is TypeParameterType && |
| subtype.parameter == supertype.parameter) { |
| if (supertype.promotedBound != null) { |
| return performNullabilityAwareSubtypeCheck( |
| subtype.bound, supertype.bound); |
| } else { |
| // Promoted bound should always be a subtype of the declared bound. |
| assert(subtype.promotedBound == null || |
| performNullabilityAwareSubtypeCheck( |
| subtype.bound, supertype.bound) |
| .isSubtypeWhenIgnoringNullabilities()); |
| return const IsSubtypeOf.always(); |
| } |
| } |
| // 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 performNullabilityAwareSubtypeCheck(subtype.bound, supertype) |
| .join(new IsSubtypeOf.basedSolelyOnNullabilities(subtype, supertype)); |
| } |
| if (subtype is FunctionType) { |
| if (supertype is InterfaceType && supertype.classNode == functionClass) { |
| return new IsSubtypeOf.basedSolelyOnNullabilities(subtype, supertype); |
| } |
| if (supertype is FunctionType) { |
| return _performNullabilityAwareFunctionSubtypeCheck(subtype, supertype); |
| } |
| } |
| return const IsSubtypeOf.never(); |
| } |
| |
| IsSubtypeOf performNullabilityAwareMutualSubtypesCheck( |
| DartType type1, DartType type2) { |
| return performNullabilityAwareSubtypeCheck(type1, type2) |
| .joinWithSubtypeCheckFor(type2, type1, this); |
| } |
| |
| IsSubtypeOf _performNullabilityAwareFunctionSubtypeCheck( |
| FunctionType subtype, FunctionType supertype) { |
| if (subtype.requiredParameterCount > supertype.requiredParameterCount) { |
| return const IsSubtypeOf.never(); |
| } |
| if (subtype.positionalParameters.length < |
| supertype.positionalParameters.length) { |
| return const IsSubtypeOf.never(); |
| } |
| if (subtype.typeParameters.length != supertype.typeParameters.length) { |
| return const IsSubtypeOf.never(); |
| } |
| 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 (!performNullabilityAwareSubtypeCheck(superParameter.bound, subBound) |
| .isSubtypeWhenIgnoringNullabilities() || |
| !performNullabilityAwareSubtypeCheck(subBound, superParameter.bound) |
| .isSubtypeWhenIgnoringNullabilities()) { |
| return const IsSubtypeOf.never(); |
| } |
| } |
| subtype = substitute(subtype.withoutTypeParameters, substitution); |
| } |
| if (!performNullabilityAwareSubtypeCheck( |
| subtype.returnType, supertype.returnType) |
| .isSubtypeWhenIgnoringNullabilities()) { |
| return const IsSubtypeOf.never(); |
| } |
| 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 (!performNullabilityAwareSubtypeCheck( |
| supertypeParameter, subtypeParameter) |
| .isSubtypeWhenIgnoringNullabilities()) { |
| return const IsSubtypeOf.never(); |
| } |
| } |
| 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 const IsSubtypeOf.never(); |
| } |
| NamedType subtypeParameter = subtype.namedParameters[subtypeNameIndex]; |
| // Termination: Both types shrink in size. |
| if (!performNullabilityAwareSubtypeCheck( |
| supertypeParameter.type, subtypeParameter.type) |
| .isSubtypeWhenIgnoringNullabilities()) { |
| return const IsSubtypeOf.never(); |
| } |
| } |
| return const IsSubtypeOf.always(); |
| } |
| } |