| // Copyright (c) 2015, 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. |
| |
| // TODO(jmesserly): this was ported from package:dev_compiler, and needs to be |
| // refactored to fit into analyzer. |
| library analyzer.src.task.strong.rules; |
| |
| import 'package:analyzer/src/generated/ast.dart'; |
| import 'package:analyzer/src/generated/element.dart'; |
| import 'package:analyzer/src/generated/resolver.dart'; |
| |
| import 'info.dart'; |
| |
| // TODO(jmesserly): this entire file needs to be removed in favor of TypeSystem. |
| |
| final _objectMap = new Expando('providerToObjectMap'); |
| Map<String, DartType> getObjectMemberMap(TypeProvider typeProvider) { |
| var map = _objectMap[typeProvider] as Map<String, DartType>; |
| if (map == null) { |
| map = <String, DartType>{}; |
| _objectMap[typeProvider] = map; |
| var objectType = typeProvider.objectType; |
| var element = objectType.element; |
| // Only record methods (including getters) with no parameters. As parameters are contravariant wrt |
| // type, using Object's version may be too strict. |
| // Add instance methods. |
| element.methods.where((method) => !method.isStatic).forEach((method) { |
| map[method.name] = method.type; |
| }); |
| // Add getters. |
| element.accessors |
| .where((member) => !member.isStatic && member.isGetter) |
| .forEach((member) { |
| map[member.name] = member.type.returnType; |
| }); |
| } |
| return map; |
| } |
| |
| class TypeRules { |
| final TypeProvider provider; |
| |
| /// Map of fields / properties / methods on Object. |
| final Map<String, DartType> objectMembers; |
| |
| DownwardsInference inferrer; |
| |
| TypeRules(TypeProvider provider) |
| : provider = provider, |
| objectMembers = getObjectMemberMap(provider) { |
| inferrer = new DownwardsInference(this); |
| } |
| |
| /// Given a type t, if t is an interface type with a call method |
| /// defined, return the function type for the call method, otherwise |
| /// return null. |
| FunctionType getCallMethodType(DartType t) { |
| if (t is InterfaceType) { |
| return t.lookUpMethod("call", null)?.type; |
| } |
| return null; |
| } |
| |
| /// Given an expression, return its type assuming it is |
| /// in the caller position of a call (that is, accounting |
| /// for the possibility of a call method). Returns null |
| /// if expression is not statically callable. |
| FunctionType getTypeAsCaller(Expression applicand) { |
| var t = getStaticType(applicand); |
| if (t is InterfaceType) { |
| return getCallMethodType(t); |
| } |
| if (t is FunctionType) return t; |
| return null; |
| } |
| |
| /// Gets the expected return type of the given function [body], either from |
| /// a normal return/yield, or from a yield*. |
| DartType getExpectedReturnType(FunctionBody body, {bool yieldStar: false}) { |
| FunctionType functionType; |
| var parent = body.parent; |
| if (parent is Declaration) { |
| functionType = elementType(parent.element); |
| } else { |
| assert(parent is FunctionExpression); |
| functionType = getStaticType(parent); |
| } |
| |
| var type = functionType.returnType; |
| |
| InterfaceType expectedType = null; |
| if (body.isAsynchronous) { |
| if (body.isGenerator) { |
| // Stream<T> -> T |
| expectedType = provider.streamType; |
| } else { |
| // Future<T> -> T |
| // TODO(vsm): Revisit with issue #228. |
| expectedType = provider.futureType; |
| } |
| } else { |
| if (body.isGenerator) { |
| // Iterable<T> -> T |
| expectedType = provider.iterableType; |
| } else { |
| // T -> T |
| return type; |
| } |
| } |
| if (yieldStar) { |
| if (type.isDynamic) { |
| // Ensure it's at least a Stream / Iterable. |
| return expectedType.substitute4([provider.dynamicType]); |
| } else { |
| // Analyzer will provide a separate error if expected type |
| // is not compatible with type. |
| return type; |
| } |
| } |
| if (type.isDynamic) { |
| return type; |
| } else if (type is InterfaceType && type.element == expectedType.element) { |
| return type.typeArguments[0]; |
| } else { |
| // Malformed type - fallback on analyzer error. |
| return null; |
| } |
| } |
| |
| DartType getStaticType(Expression expr) { |
| return expr.staticType ?? provider.dynamicType; |
| } |
| |
| bool _isBottom(DartType t, {bool dynamicIsBottom: false}) { |
| if (t.isDynamic && dynamicIsBottom) return true; |
| // TODO(vsm): We need direct support for non-nullability in DartType. |
| // This should check on "true/nonnullable" Bottom |
| if (t.isBottom) return true; |
| return false; |
| } |
| |
| bool _isTop(DartType t, {bool dynamicIsBottom: false}) { |
| if (t.isDynamic && !dynamicIsBottom) return true; |
| if (t.isObject) return true; |
| return false; |
| } |
| |
| bool _anyParameterType(FunctionType ft, bool predicate(DartType t)) { |
| return ft.normalParameterTypes.any(predicate) || |
| ft.optionalParameterTypes.any(predicate) || |
| ft.namedParameterTypes.values.any(predicate); |
| } |
| |
| // TODO(leafp): Revisit this. |
| bool isGroundType(DartType t) { |
| if (t is TypeParameterType) return false; |
| if (_isTop(t)) return true; |
| |
| if (t is FunctionType) { |
| if (!_isTop(t.returnType) || |
| _anyParameterType(t, (pt) => !_isBottom(pt, dynamicIsBottom: true))) { |
| return false; |
| } else { |
| return true; |
| } |
| } |
| |
| if (t is InterfaceType) { |
| var typeArguments = t.typeArguments; |
| for (var typeArgument in typeArguments) { |
| if (!_isTop(typeArgument)) return false; |
| } |
| return true; |
| } |
| |
| // We should not see any other type aside from malformed code. |
| return false; |
| } |
| |
| /// Check that f1 is a subtype of f2. [ignoreReturn] is used in the DDC |
| /// checker to determine whether f1 would be a subtype of f2 if the return |
| /// type of f1 is set to match f2's return type. |
| // [fuzzyArrows] indicates whether or not the f1 and f2 should be |
| // treated as fuzzy arrow types (and hence dynamic parameters to f2 treated as |
| // bottom). |
| bool isFunctionSubTypeOf(FunctionType f1, FunctionType f2, |
| {bool fuzzyArrows: true, bool ignoreReturn: false}) { |
| final r1s = f1.normalParameterTypes; |
| final o1s = f1.optionalParameterTypes; |
| final n1s = f1.namedParameterTypes; |
| final r2s = f2.normalParameterTypes; |
| final o2s = f2.optionalParameterTypes; |
| final n2s = f2.namedParameterTypes; |
| final ret1 = ignoreReturn ? f2.returnType : f1.returnType; |
| final ret2 = f2.returnType; |
| |
| // A -> B <: C -> D if C <: A and |
| // either D is void or B <: D |
| if (!ret2.isVoid && !isSubTypeOf(ret1, ret2)) return false; |
| |
| // Reject if one has named and the other has optional |
| if (n1s.length > 0 && o2s.length > 0) return false; |
| if (n2s.length > 0 && o1s.length > 0) return false; |
| |
| // f2 has named parameters |
| if (n2s.length > 0) { |
| // Check that every named parameter in f2 has a match in f1 |
| for (String k2 in n2s.keys) { |
| if (!n1s.containsKey(k2)) return false; |
| if (!isSubTypeOf(n2s[k2], n1s[k2], |
| dynamicIsBottom: fuzzyArrows)) return false; |
| } |
| } |
| // If we get here, we either have no named parameters, |
| // or else the named parameters match and we have no optional |
| // parameters |
| |
| // If f1 has more required parameters, reject |
| if (r1s.length > r2s.length) return false; |
| |
| // If f2 has more required + optional parameters, reject |
| if (r2s.length + o2s.length > r1s.length + o1s.length) return false; |
| |
| // The parameter lists must look like the following at this point |
| // where rrr is a region of required, and ooo is a region of optionals. |
| // f1: rrr ooo ooo ooo |
| // f2: rrr rrr ooo |
| int rr = r1s.length; // required in both |
| int or = r2s.length - r1s.length; // optional in f1, required in f2 |
| int oo = o2s.length; // optional in both |
| |
| for (int i = 0; i < rr; ++i) { |
| if (!isSubTypeOf(r2s[i], r1s[i], |
| dynamicIsBottom: fuzzyArrows)) return false; |
| } |
| for (int i = 0, j = rr; i < or; ++i, ++j) { |
| if (!isSubTypeOf(r2s[j], o1s[i], |
| dynamicIsBottom: fuzzyArrows)) return false; |
| } |
| for (int i = or, j = 0; i < oo; ++i, ++j) { |
| if (!isSubTypeOf(o2s[j], o1s[i], |
| dynamicIsBottom: fuzzyArrows)) return false; |
| } |
| return true; |
| } |
| |
| bool _isInterfaceSubTypeOf(InterfaceType i1, InterfaceType i2) { |
| if (i1 == i2) return true; |
| |
| if (i1.element == i2.element) { |
| List<DartType> tArgs1 = i1.typeArguments; |
| List<DartType> tArgs2 = i2.typeArguments; |
| |
| // TODO(leafp): Verify that this is always true |
| // Do raw types get filled in? |
| assert(tArgs1.length == tArgs2.length); |
| |
| for (int i = 0; i < tArgs1.length; i++) { |
| DartType t1 = tArgs1[i]; |
| DartType t2 = tArgs2[i]; |
| if (!isSubTypeOf(t1, t2)) return false; |
| } |
| return true; |
| } |
| |
| if (i2.isDartCoreFunction) { |
| if (i1.element.getMethod("call") != null) return true; |
| } |
| |
| if (i1 == provider.objectType) return false; |
| |
| if (_isInterfaceSubTypeOf(i1.superclass, i2)) return true; |
| |
| for (final parent in i1.interfaces) { |
| if (_isInterfaceSubTypeOf(parent, i2)) return true; |
| } |
| |
| for (final parent in i1.mixins) { |
| if (_isInterfaceSubTypeOf(parent, i2)) return true; |
| } |
| |
| return false; |
| } |
| |
| bool isSubTypeOf(DartType t1, DartType t2, {bool dynamicIsBottom: false}) { |
| if (t1 == t2) return true; |
| |
| // Trivially true. |
| if (_isTop(t2, dynamicIsBottom: dynamicIsBottom) || |
| _isBottom(t1, dynamicIsBottom: dynamicIsBottom)) { |
| return true; |
| } |
| |
| // Trivially false. |
| if (_isTop(t1, dynamicIsBottom: dynamicIsBottom) || |
| _isBottom(t2, dynamicIsBottom: dynamicIsBottom)) { |
| return false; |
| } |
| |
| // The null type is a subtype of any nullable type, which is all Dart types. |
| // TODO(vsm): Note, t1.isBottom still allows for null confusingly. |
| // _isBottom(t1) does not necessarily imply t1.isBottom if there are |
| // nonnullable types in the system. |
| if (t1.isBottom) { |
| return true; |
| } |
| |
| // S <: T where S is a type variable |
| // T is not dynamic or object (handled above) |
| // S != T (handled above) |
| // So only true if bound of S is S' and |
| // S' <: T |
| if (t1 is TypeParameterType) { |
| DartType bound = t1.element.bound; |
| if (bound == null) return false; |
| return isSubTypeOf(bound, t2); |
| } |
| |
| if (t2 is TypeParameterType) { |
| return false; |
| } |
| |
| if (t1.isVoid || t2.isVoid) { |
| return false; |
| } |
| |
| if (t2.isDartCoreFunction) { |
| if (t1 is FunctionType) return true; |
| if (t1.element is ClassElement) { |
| if ((t1.element as ClassElement).getMethod("call") != null) return true; |
| } |
| } |
| |
| // "Traditional" name-based subtype check. |
| if (t1 is InterfaceType && t2 is InterfaceType) { |
| return _isInterfaceSubTypeOf(t1, t2); |
| } |
| |
| if (t1 is! FunctionType && t2 is! FunctionType) return false; |
| |
| if (t1 is InterfaceType && t2 is FunctionType) { |
| var callType = getCallMethodType(t1); |
| if (callType == null) return false; |
| return isFunctionSubTypeOf(callType, t2); |
| } |
| |
| if (t1 is FunctionType && t2 is InterfaceType) { |
| return false; |
| } |
| |
| // Functions |
| // Note: it appears under the hood all Dart functions map to a class / |
| // hidden type that: |
| // (a) subtypes Object (an internal _FunctionImpl in the VM) |
| // (b) implements Function |
| // (c) provides standard Object members (hashCode, toString) |
| // (d) contains private members (corresponding to _FunctionImpl?) |
| // (e) provides a call method to handle the actual function invocation |
| // |
| // The standard Dart subtyping rules are structural in nature. I.e., |
| // bivariant on arguments and return type. |
| // |
| // The below tries for a more traditional subtyping rule: |
| // - covariant on return type |
| // - contravariant on parameters |
| // - 'sensible' (?) rules on optional and/or named params |
| // but doesn't properly mix with class subtyping. I suspect Java 8 lambdas |
| // essentially map to dynamic (and rely on invokedynamic) due to similar |
| // issues. |
| return isFunctionSubTypeOf(t1 as FunctionType, t2 as FunctionType); |
| } |
| |
| bool isAssignable(DartType t1, DartType t2) { |
| return isSubTypeOf(t1, t2); |
| } |
| |
| // Produce a coercion which coerces something of type fromT |
| // to something of type toT. |
| // Returns the error coercion if the types cannot be coerced |
| // according to our current criteria. |
| Coercion _coerceTo(DartType fromT, DartType toT) { |
| // We can use anything as void |
| if (toT.isVoid) return Coercion.identity(toT); |
| |
| // fromT <: toT, no coercion needed |
| if (isSubTypeOf(fromT, toT)) return Coercion.identity(toT); |
| |
| // TODO(vsm): We can get rid of the second clause if we disallow |
| // all sideways casts - see TODO below. |
| // ------- |
| // Note: a function type is never assignable to a class per the Dart |
| // spec - even if it has a compatible call method. We disallow as |
| // well for consistency. |
| if ((fromT is FunctionType && getCallMethodType(toT) != null) || |
| (toT is FunctionType && getCallMethodType(fromT) != null)) { |
| return Coercion.error(); |
| } |
| |
| // Downcast if toT <: fromT |
| if (isSubTypeOf(toT, fromT)) return Coercion.cast(fromT, toT); |
| |
| // TODO(vsm): Once we have generic methods, we should delete this |
| // workaround. These sideways casts are always ones we warn about |
| // - i.e., we think they are likely to fail at runtime. |
| // ------- |
| // Downcast if toT <===> fromT |
| // The intention here is to allow casts that are sideways in the restricted |
| // type system, but allowed in the regular dart type system, since these |
| // are likely to succeed. The canonical example is List<dynamic> and |
| // Iterable<T> for some concrete T (e.g. Object). These are unrelated |
| // in the restricted system, but List<dynamic> <: Iterable<T> in dart. |
| if (fromT.isAssignableTo(toT)) { |
| return Coercion.cast(fromT, toT); |
| } |
| |
| return Coercion.error(); |
| } |
| |
| StaticInfo checkAssignment(Expression expr, DartType toT) { |
| final fromT = getStaticType(expr); |
| final Coercion c = _coerceTo(fromT, toT); |
| if (c is Identity) return null; |
| if (c is CoercionError) return new StaticTypeError(this, expr, toT); |
| var reason = null; |
| |
| var errors = <String>[]; |
| |
| var ok = inferrer.inferExpression(expr, toT, errors); |
| if (ok) return InferredType.create(this, expr, toT); |
| reason = (errors.isNotEmpty) ? errors.first : null; |
| |
| if (c is Cast) return DownCast.create(this, expr, c, reason: reason); |
| assert(false); |
| return null; |
| } |
| |
| DartType elementType(Element e) { |
| if (e == null) { |
| // Malformed code - just return dynamic. |
| return provider.dynamicType; |
| } |
| return (e as dynamic).type; |
| } |
| |
| bool _isLibraryPrefix(Expression node) => |
| node is SimpleIdentifier && node.staticElement is PrefixElement; |
| |
| /// Returns `true` if the target expression is dynamic. |
| bool isDynamicTarget(Expression node) { |
| if (node == null) return false; |
| |
| if (_isLibraryPrefix(node)) return false; |
| |
| // Null type happens when we have unknown identifiers, like a dart: import |
| // that doesn't resolve. |
| var type = node.staticType; |
| return type == null || type.isDynamic; |
| } |
| |
| /// Returns `true` if the expression is a dynamic function call or method |
| /// invocation. |
| bool isDynamicCall(Expression call) { |
| var ft = getTypeAsCaller(call); |
| // TODO(leafp): This will currently return true if t is Function |
| // This is probably the most correct thing to do for now, since |
| // this code is also used by the back end. Maybe revisit at some |
| // point? |
| if (ft == null) return true; |
| // Dynamic as the parameter type is treated as bottom. A function with |
| // a dynamic parameter type requires a dynamic call in general. |
| // However, as an optimization, if we have an original definition, we know |
| // dynamic is reified as Object - in this case a regular call is fine. |
| if (call is SimpleIdentifier) { |
| var element = call.staticElement; |
| if (element is FunctionElement || element is MethodElement) { |
| // An original declaration. |
| return false; |
| } |
| } |
| |
| return _anyParameterType(ft, (pt) => pt.isDynamic); |
| } |
| } |
| |
| class DownwardsInference { |
| final TypeRules rules; |
| |
| DownwardsInference(this.rules); |
| |
| /// Called for each list literal which gets inferred |
| void annotateListLiteral(ListLiteral e, List<DartType> targs) {} |
| |
| /// Called for each map literal which gets inferred |
| void annotateMapLiteral(MapLiteral e, List<DartType> targs) {} |
| |
| /// Called for each new/const which gets inferred |
| void annotateInstanceCreationExpression( |
| InstanceCreationExpression e, List<DartType> targs) {} |
| |
| /// Called for cast from dynamic required for inference to succeed |
| void annotateCastFromDynamic(Expression e, DartType t) {} |
| |
| /// Called for each function expression return type inferred |
| void annotateFunctionExpression(FunctionExpression e, DartType returnType) {} |
| |
| /// Downward inference |
| bool inferExpression(Expression e, DartType t, List<String> errors) { |
| // Don't cast top level expressions, only sub-expressions |
| return _inferExpression(e, t, errors, cast: false); |
| } |
| |
| /// Downward inference |
| bool _inferExpression(Expression e, DartType t, List<String> errors, |
| {cast: true}) { |
| if (rules.isSubTypeOf(rules.getStaticType(e), t)) return true; |
| if (cast && rules.getStaticType(e).isDynamic) { |
| annotateCastFromDynamic(e, t); |
| return true; |
| } |
| errors.add("$e cannot be typed as $t"); |
| return false; |
| } |
| } |