| // 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.transformations.insert_covariance_checks; |
| |
| import '../class_hierarchy.dart'; |
| import '../clone.dart'; |
| import '../core_types.dart'; |
| import '../kernel.dart'; |
| import '../log.dart'; |
| import '../type_algebra.dart'; |
| import '../type_environment.dart'; |
| |
| DartType substituteBounds(DartType type, Map<TypeParameter, DartType> upper, |
| Map<TypeParameter, DartType> lower) { |
| return Substitution |
| .fromUpperAndLowerBounds(upper, lower) |
| .substituteType(type); |
| } |
| |
| /// Inserts checked entry points for methods in order to enforce type safety |
| /// in face on covariant subtyping. |
| /// |
| /// An 'unsafe parameter' is a parameter whose type mentions a class type |
| /// parameter T, but is not contravariant in T. For instance, the argument |
| /// to `List.add` is unsafe, whereas the function parameter to `List.forEach` |
| /// is safe: |
| /// |
| /// class List<T> { |
| /// ... |
| /// void add(T x) {...} // unsafe |
| /// void forEach(void action(T x)) {...} // safe |
| /// } |
| /// |
| /// For every method with unsafe parameters, a checked entry point suffixed |
| /// with `$cc` is inserted, which casts the unsafe parameters to their expected |
| /// types and calls the actual implementation: |
| /// |
| /// class List<T> { |
| /// ... |
| /// void add$cc(Object x) => this.add(x as T); |
| /// } |
| /// |
| /// Calls whose interface target declares unsafe parameters are then rewritten |
| /// to target the `$cc` entry point instead, unless it can be determined that |
| /// the type argument is exact. For example: |
| /// |
| /// void foo(List<num> numbers) { |
| /// numbers.add(3.5); // before |
| /// numbers.add$cc(3.5); // after |
| /// } |
| /// |
| /// Currently, we only deduce that the type arguments are exact when the |
| /// receiver is `this`. |
| class InsertCovarianceChecks { |
| ClassHierarchy hierarchy; |
| CoreTypes coreTypes; |
| TypeEnvironment types; |
| |
| /// Maps unsafe members to their checked entry point, to be used at call sites |
| /// where the arguments cannot be guaranteed to satisfy the generic parameter |
| /// types of the actual target. |
| final Map<Member, Procedure> unsafeMemberEntryPoint = <Member, Procedure>{}; |
| |
| /// Members that may be invoked through a checked entry point. |
| /// |
| /// Note that these members are not necessarily unsafe, because a safe member |
| /// can override an unsafe member, and thereby be invoked through a checked |
| /// entry point. This set is not therefore not the same as the set of keys |
| /// in [unsafeMemberEntryPoint]. |
| final Set<Member> membersWithCheckedEntryPoint = new Set<Member>(); |
| |
| InsertCovarianceChecks({this.hierarchy, this.coreTypes}); |
| |
| void transformProgram(Program program) { |
| hierarchy ??= new ClassHierarchy(program); |
| coreTypes ??= new CoreTypes(program); |
| types = new TypeEnvironment(coreTypes, hierarchy); |
| // We transform every class before their subtypes. |
| // This ensures that transitive overrides are taken into account. |
| hierarchy.classes.forEach(transformClass); |
| |
| program.accept(new _CallTransformer(this)); |
| } |
| |
| void transformClass(Class class_) { |
| new _ClassTransformer(class_, this).transformClass(); |
| } |
| } |
| |
| class _ClassTransformer { |
| final Class host; |
| final ClassHierarchy hierarchy; |
| final TypeEnvironment types; |
| final InsertCovarianceChecks global; |
| |
| final Map<Field, VariableDeclaration> fieldSetterParameter = |
| <Field, VariableDeclaration>{}; |
| |
| final Map<VariableDeclaration, List<DartType>> unsafeParameterTypes = |
| new Map<VariableDeclaration, List<DartType>>(); |
| |
| // The following four maps translate types from the context of a supertype |
| // into the context of the current class. |
| // |
| // When analyzing an override relation "ownMember <: superMember", the two |
| // "own" maps translate types from the context of the ownMember, while the |
| // "super" maps translate types from the context of superMember. |
| // |
| // The "substitution" maps translate type parameters to their exact type, |
| // while the "upper bound" maps translate type parameters to their erased |
| // upper bounds. |
| Map<TypeParameter, DartType> ownSubstitution; |
| Map<TypeParameter, DartType> ownUpperBounds; |
| Map<TypeParameter, DartType> superSubstitution; |
| Map<TypeParameter, DartType> superUpperBounds; |
| |
| /// Members for which a checked entry point must be created in this current |
| /// class, indexed by name. |
| Map<Name, Member> membersNeedingCheckedEntryPoint = <Name, Member>{}; |
| |
| _ClassTransformer(this.host, InsertCovarianceChecks global) |
| : hierarchy = global.hierarchy, |
| types = global.types, |
| this.global = global; |
| |
| /// Mark [parameter] unsafe, with [type] as a potential argument type. |
| void addUnsafeParameter( |
| VariableDeclaration parameter, DartType type, Member member) { |
| unsafeParameterTypes.putIfAbsent(parameter, () => <DartType>[]).add(type); |
| requireLocalCheckedEntryPoint(member); |
| } |
| |
| /// Get a parameter representing the argument to the implicit setter |
| /// for [field]. |
| VariableDeclaration getFieldSetterParameter(Field field) { |
| return fieldSetterParameter.putIfAbsent(field, () { |
| return new VariableDeclaration('${field.name.name}_', type: field.type); |
| }); |
| } |
| |
| /// Mark [field] as unsafe, with [type] as a potential argument to its setter. |
| void addUnsafeField(Field field, DartType type) { |
| addUnsafeParameter(getFieldSetterParameter(field), type, field); |
| } |
| |
| /// True if [member] can be invoked through a checked entry point. |
| /// |
| /// This does not imply that the member has unsafe parameters. |
| bool hasCheckedEntryPoint(Member member, {bool setter: false}) { |
| if (!setter && member is Field) { |
| return false; // Field getters never have checked entry points. |
| } |
| return global.membersWithCheckedEntryPoint.contains(member); |
| } |
| |
| /// Ensures that a checked entry point for [member] will be emitted in the |
| /// current class. |
| void requireLocalCheckedEntryPoint(Member member) { |
| membersNeedingCheckedEntryPoint[member.name] = member; |
| global.membersWithCheckedEntryPoint.add(member); |
| } |
| |
| void transformClass() { |
| if (host.isMixinApplication) { |
| // TODO(asgerf): We need a way to support mixin applications with unsafe |
| // overrides. This version assumes mixins have been resolved by cloning. |
| // We could generate a subclass of the mixin application containing the |
| // checked entry points. |
| throw 'Mixin applications must be resolved before inserting covariance ' |
| 'checks'; |
| } |
| // Find parameters with an unsafe reference to a class type parameter. |
| if (host.typeParameters.isNotEmpty) { |
| var upperBounds = getUpperBoundSubstitutionMap(host); |
| for (var field in host.fields) { |
| if (field.hasImplicitSetter) { |
| var rawType = substituteBounds(field.type, upperBounds, {}); |
| if (!identical(rawType, field.type)) { |
| requireLocalCheckedEntryPoint(field); |
| addUnsafeField(field, rawType); |
| } |
| } |
| } |
| for (var procedure in host.procedures) { |
| if (procedure.isStatic) continue; |
| void handleParameter(VariableDeclaration parameter) { |
| var rawType = substituteBounds(parameter.type, upperBounds, {}); |
| if (!identical(rawType, parameter.type)) { |
| requireLocalCheckedEntryPoint(procedure); |
| addUnsafeParameter(parameter, rawType, procedure); |
| } |
| } |
| |
| procedure.function.positionalParameters.forEach(handleParameter); |
| procedure.function.namedParameters.forEach(handleParameter); |
| } |
| } |
| |
| // Find (possibly inherited) members that override a method that has |
| // unsafe parameters. |
| hierarchy.forEachOverridePair(host, |
| (Member ownMember, Member superMember, bool isSetter) { |
| if (hasCheckedEntryPoint(superMember, setter: isSetter)) { |
| requireLocalCheckedEntryPoint(ownMember); |
| } |
| if (superMember.enclosingClass.typeParameters.isEmpty) return; |
| ownSubstitution = getSubstitutionMap( |
| hierarchy.getClassAsInstanceOf(host, ownMember.enclosingClass)); |
| ownUpperBounds = getUpperBoundSubstitutionMap(ownMember.enclosingClass); |
| superSubstitution = getSubstitutionMap( |
| hierarchy.getClassAsInstanceOf(host, superMember.enclosingClass)); |
| superUpperBounds = |
| getUpperBoundSubstitutionMap(superMember.enclosingClass); |
| if (ownMember is Procedure) { |
| if (superMember is Procedure) { |
| checkProcedureOverride(ownMember, superMember); |
| } else if (superMember is Field && isSetter) { |
| checkSetterFieldOverride(ownMember, superMember); |
| } |
| } else if (isSetter) { |
| checkFieldOverride(ownMember, superMember); |
| } |
| }); |
| |
| for (Member member in membersNeedingCheckedEntryPoint.values) { |
| ownSubstitution = getSubstitutionMap( |
| hierarchy.getClassAsInstanceOf(host, member.enclosingClass)); |
| ownSubstitution = ensureMutable(ownSubstitution); |
| generateCheckedEntryPoint(member); |
| } |
| } |
| |
| /// Compute an upper bound of the types in [inputTypes]. |
| /// |
| /// We use this to compute a trustworthy type for a parameter, given a list |
| /// of types that may actually be passed into the parameter. |
| DartType getSafeType(List<DartType> inputTypes) { |
| var safeType = inputTypes[0]; |
| for (int i = 1; i < inputTypes.length; ++i) { |
| if (inputTypes[i] != safeType) { |
| // Multiple types are being overridden. Fall back to dynamic. |
| // There are cases where a better upper bound could be found, but they |
| // are quite rare. |
| return const DynamicType(); |
| } |
| } |
| return safeType; |
| } |
| |
| void fail(String message) { |
| log.warning('[unsoundness] $message'); |
| } |
| |
| void checkFieldOverride(Field field, Member superMember) { |
| var fieldType = |
| substituteBounds(field.type, ownUpperBounds, ownSubstitution); |
| var superType = substituteBounds( |
| superMember.setterType, superUpperBounds, superSubstitution); |
| if (!types.isSubtypeOf(superType, fieldType)) { |
| addUnsafeField(field, superType); |
| } |
| } |
| |
| void checkSetterFieldOverride(Procedure ownMember, Field superMember) { |
| assert(ownMember.isSetter); |
| var ownParameter = ownMember.function.positionalParameters[0]; |
| var ownType = |
| substituteBounds(ownParameter.type, ownUpperBounds, ownSubstitution); |
| var superType = substituteBounds( |
| superMember.setterType, superUpperBounds, superSubstitution); |
| if (!types.isSubtypeOf(superType, ownType)) { |
| addUnsafeParameter(ownParameter, superType, ownMember); |
| } |
| } |
| |
| void checkProcedureOverride(Procedure ownMember, Procedure superMember) { |
| var ownFunction = ownMember.function; |
| var superFunction = superMember.function; |
| // We perform some checks here to avoid crashing, but the frontend is |
| // responsible for generating IR that does not violate these restrictions. |
| if (ownFunction.requiredParameterCount > |
| superFunction.requiredParameterCount) { |
| fail('$ownMember requires more parameters than $superMember'); |
| return; |
| } |
| if (ownFunction.positionalParameters.length < |
| superFunction.positionalParameters.length) { |
| fail('$ownMember allows fewer parameters than $superMember'); |
| return; |
| } |
| if (ownFunction.typeParameters.length != |
| superFunction.typeParameters.length) { |
| fail('$ownMember declares a different number of type parameters ' |
| 'than $superMember'); |
| return; |
| } |
| if (superFunction.typeParameters.isNotEmpty) { |
| // Ensure these maps are not constant, so we can add bindings for the |
| // function type parameters. |
| superSubstitution = ensureMutable(superSubstitution); |
| superUpperBounds = ensureMutable(superUpperBounds); |
| } |
| for (int i = 0; i < superFunction.typeParameters.length; ++i) { |
| var ownTypeParameter = ownFunction.typeParameters[i]; |
| var superTypeParameter = superFunction.typeParameters[i]; |
| var type = new TypeParameterType(ownTypeParameter); |
| superSubstitution[superTypeParameter] = type; |
| superUpperBounds[superTypeParameter] = type; |
| } |
| void checkParameterPair( |
| VariableDeclaration ownParameter, VariableDeclaration superParameter) { |
| var ownType = substitute(ownParameter.type, ownSubstitution); |
| var superType = substituteBounds( |
| superParameter.type, superUpperBounds, superSubstitution); |
| if (!types.isSubtypeOf(superType, ownType)) { |
| addUnsafeParameter(ownParameter, superType, ownMember); |
| } |
| } |
| |
| for (int i = 0; i < superFunction.positionalParameters.length; ++i) { |
| checkParameterPair(ownFunction.positionalParameters[i], |
| superFunction.positionalParameters[i]); |
| } |
| for (int i = 0; i < superFunction.namedParameters.length; ++i) { |
| var superParameter = superFunction.namedParameters[i]; |
| bool found = false; |
| for (int j = 0; j < ownFunction.namedParameters.length; ++j) { |
| var ownParameter = ownFunction.namedParameters[j]; |
| if (ownParameter.name == superParameter.name) { |
| found = true; |
| checkParameterPair(ownParameter, superParameter); |
| break; |
| } |
| } |
| if (!found) { |
| fail('$ownMember is missing the named parameter ' |
| '${superParameter.name} from $superMember'); |
| } |
| } |
| } |
| |
| void generateCheckedEntryPoint(Member member) { |
| // TODO(asgerf): It may be worthwhile to try to reuse a checked entry |
| // point from the supertype when the same checks are needed and the |
| // dispatch target is the same. |
| if (member is Procedure) { |
| generateCheckedProcedure(member); |
| } else { |
| generateCheckedFieldSetter(member); |
| } |
| } |
| |
| void generateCheckedProcedure(Procedure procedure) { |
| var function = procedure.function; |
| |
| // Clone the function without its body. |
| var body = function.body; |
| function.body = null; |
| var cloner = new CloneVisitor(typeSubstitution: ownSubstitution); |
| Procedure checkedProcedure = cloner.clone(procedure); |
| FunctionNode checkedFunction = checkedProcedure.function; |
| function.body = body; |
| |
| checkedFunction.asyncMarker = AsyncMarker.Sync; |
| checkedProcedure.isExternal = false; |
| |
| Expression getParameter(VariableDeclaration parameter) { |
| var cloneParameter = cloner.variables[parameter]; |
| var unsafeInputs = unsafeParameterTypes[parameter]; |
| if (unsafeInputs == null) { |
| return new VariableGet(cloneParameter); // No check needed. |
| } |
| // Change the actual parameter type to the safe type, and cast to the |
| // type declared on the original parameter. |
| // Use the cloner to map function type parameters to the cloned |
| // function type parameters (in case the function is generic). |
| var targetType = cloneParameter.type; |
| cloneParameter.type = cloner.visitType(getSafeType(unsafeInputs)); |
| return new AsExpression(new VariableGet(cloneParameter), targetType) |
| ..fileOffset = parameter.fileOffset; |
| } |
| |
| // TODO: Insert checks for type parameter bounds. |
| var types = checkedFunction.typeParameters |
| .map((p) => new TypeParameterType(p)) |
| .toList(); |
| var positional = function.positionalParameters.map(getParameter).toList(); |
| var named = function.namedParameters |
| .map((p) => new NamedExpression(p.name, getParameter(p))) |
| .toList(); |
| |
| checkedProcedure.name = covariantCheckedName(procedure.name); |
| host.addMember(checkedProcedure); |
| |
| // Only generate a body if the original method had one. |
| if (!procedure.isAbstract && !procedure.isInExternalLibrary) { |
| var call = procedure.isSetter |
| ? new DirectPropertySet( |
| new ThisExpression(), procedure, positional[0]) |
| : new DirectMethodInvocation(new ThisExpression(), procedure, |
| new Arguments(positional, named: named, types: types)); |
| var checkedBody = function.returnType is VoidType |
| ? new ExpressionStatement(call) |
| : new ReturnStatement(call); |
| checkedFunction.body = checkedBody..parent = checkedFunction; |
| } |
| |
| if (procedure.enclosingClass == host) { |
| global.unsafeMemberEntryPoint[procedure] = checkedProcedure; |
| } |
| } |
| |
| void generateCheckedFieldSetter(Field field) { |
| var parameter = getFieldSetterParameter(field); |
| var unsafeTypes = unsafeParameterTypes[parameter]; |
| Expression argument = new VariableGet(parameter); |
| if (unsafeTypes != null) { |
| var castType = substitute(field.type, ownSubstitution); |
| argument = new AsExpression(argument, castType) |
| ..fileOffset = field.fileOffset; |
| var inputType = substitute(getSafeType(unsafeTypes), ownSubstitution); |
| parameter.type = inputType; |
| } |
| |
| Statement body = field.isInExternalLibrary |
| ? null |
| : new ExpressionStatement( |
| new DirectPropertySet(new ThisExpression(), field, argument)); |
| |
| var setter = new Procedure( |
| covariantCheckedName(field.name), |
| ProcedureKind.Setter, |
| new FunctionNode(body, positionalParameters: [parameter])) |
| ..fileUri = field.fileUri; |
| host.addMember(setter); |
| |
| if (field.enclosingClass == host) { |
| global.unsafeMemberEntryPoint[field] = setter; |
| } |
| } |
| |
| /// Generates a synthetic name representing the covariant-checked entry point |
| /// to a method. |
| static Name covariantCheckedName(Name name) { |
| return new Name('${name.name}\$cc', name.library); |
| } |
| |
| static Map<TypeParameter, DartType> ensureMutable( |
| Map<TypeParameter, DartType> map) { |
| if (map.isEmpty) return <TypeParameter, DartType>{}; |
| return map; |
| } |
| } |
| |
| // TODO(asgerf): We should be able to avoid checked calls in a lot more cases: |
| // - the arguments to every unsafe parameter is null or is omitted |
| // - allocation site of receiver can easily be seen statically |
| class _CallTransformer extends RecursiveVisitor { |
| final InsertCovarianceChecks global; |
| final TypeEnvironment types; |
| final Map<Member, Procedure> checkedInterfaceMethod; |
| |
| _CallTransformer(InsertCovarianceChecks global) |
| : checkedInterfaceMethod = global.unsafeMemberEntryPoint, |
| types = global.types, |
| this.global = global; |
| |
| Member getChecked(Expression receiver, Member member) { |
| var checked = checkedInterfaceMethod[member]; |
| if (checked == null) return member; |
| if (!receiverNeedsChecks(receiver)) return member; |
| return checked; |
| } |
| |
| bool receiverNeedsChecks(Expression node) { |
| if (node is ThisExpression) return false; |
| var type = node.getStaticType(types); |
| if (type is InterfaceType && type.typeArguments.every(isSealedType)) { |
| return false; |
| } |
| return true; |
| } |
| |
| bool isSealedType(DartType type) { |
| return type is InterfaceType && types.isSealedClass(type.classNode); |
| } |
| |
| bool isTrustedLibrary(Library node) { |
| return node.importUri.scheme == 'dart'; |
| } |
| |
| @override |
| visitClass(Class node) { |
| types.thisType = node.thisType; |
| node.visitChildren(this); |
| } |
| |
| @override |
| visitLibrary(Library node) { |
| if (!isTrustedLibrary(node)) { |
| node.visitChildren(this); |
| } |
| } |
| |
| @override |
| visitMethodInvocation(MethodInvocation node) { |
| var target = getChecked(node.receiver, node.interfaceTarget); |
| if (target != null) { |
| node.interfaceTarget = target; |
| node.name = target.name; |
| } |
| node.visitChildren(this); |
| } |
| |
| @override |
| visitPropertySet(PropertySet node) { |
| var target = getChecked(node.receiver, node.interfaceTarget); |
| if (target != null) { |
| node.interfaceTarget = target; |
| node.name = target.name; |
| } |
| node.visitChildren(this); |
| } |
| } |