OLD | NEW |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 library analyzer.src.dart.element.type; | 5 library analyzer.src.dart.element.type; |
6 | 6 |
7 import 'dart:collection'; | 7 import 'dart:collection'; |
8 | 8 |
9 import 'package:analyzer/dart/ast/token.dart'; | 9 import 'package:analyzer/dart/ast/token.dart'; |
10 import 'package:analyzer/dart/element/element.dart'; | 10 import 'package:analyzer/dart/element/element.dart'; |
(...skipping 700 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
711 bool operator ==(Object object) { | 711 bool operator ==(Object object) { |
712 if (object is FunctionTypeImpl) { | 712 if (object is FunctionTypeImpl) { |
713 if (typeFormals.length != object.typeFormals.length) { | 713 if (typeFormals.length != object.typeFormals.length) { |
714 return false; | 714 return false; |
715 } | 715 } |
716 // `<T>T -> T` should be equal to `<U>U -> U` | 716 // `<T>T -> T` should be equal to `<U>U -> U` |
717 // To test this, we instantiate both types with the same (unique) type | 717 // To test this, we instantiate both types with the same (unique) type |
718 // variables, and see if the result is equal. | 718 // variables, and see if the result is equal. |
719 if (typeFormals.isNotEmpty) { | 719 if (typeFormals.isNotEmpty) { |
720 List<DartType> freshVariables = | 720 List<DartType> freshVariables = |
721 relateTypeFormals(this, object, (t, s) => t == s); | 721 relateTypeFormals(this, object, (t, s, _, __) => t == s); |
722 if (freshVariables == null) { | 722 if (freshVariables == null) { |
723 return false; | 723 return false; |
724 } | 724 } |
725 return instantiate(freshVariables) == | 725 return instantiate(freshVariables) == |
726 object.instantiate(freshVariables); | 726 object.instantiate(freshVariables); |
727 } | 727 } |
728 | 728 |
729 return returnType == object.returnType && | 729 return returnType == object.returnType && |
730 TypeImpl.equalArrays( | 730 TypeImpl.equalArrays( |
731 normalParameterTypes, object.normalParameterTypes) && | 731 normalParameterTypes, object.normalParameterTypes) && |
(...skipping 156 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
888 } | 888 } |
889 | 889 |
890 @override | 890 @override |
891 bool isMoreSpecificThan(DartType type, | 891 bool isMoreSpecificThan(DartType type, |
892 [bool withDynamic = false, Set<Element> visitedElements]) { | 892 [bool withDynamic = false, Set<Element> visitedElements]) { |
893 // Note: visitedElements is only used for breaking recursion in the type | 893 // Note: visitedElements is only used for breaking recursion in the type |
894 // hierarchy; we don't use it when recursing into the function type. | 894 // hierarchy; we don't use it when recursing into the function type. |
895 return relate( | 895 return relate( |
896 this, | 896 this, |
897 type, | 897 type, |
898 (DartType t, DartType s, _, __) => | 898 (DartType t, DartType s) => |
899 (t as TypeImpl).isMoreSpecificThan(s, withDynamic), | 899 (t as TypeImpl).isMoreSpecificThan(s, withDynamic), |
900 new TypeSystemImpl(null).instantiateToBounds); | 900 new TypeSystemImpl(null).instantiateToBounds); |
901 } | 901 } |
902 | 902 |
903 @override | 903 @override |
904 bool isSubtypeOf(DartType type) { | 904 bool isSubtypeOf(DartType type) { |
905 var typeSystem = new TypeSystemImpl(null); | 905 var typeSystem = new TypeSystemImpl(null); |
906 return relate( | 906 return relate( |
907 typeSystem.instantiateToBounds(this), | 907 typeSystem.instantiateToBounds(this), |
908 typeSystem.instantiateToBounds(type), | 908 typeSystem.instantiateToBounds(type), |
909 (DartType t, DartType s, _, __) => t.isAssignableTo(s), | 909 (DartType t, DartType s) => t.isAssignableTo(s), |
910 typeSystem.instantiateToBounds); | 910 typeSystem.instantiateToBounds); |
911 } | 911 } |
912 | 912 |
913 @override | 913 @override |
914 FunctionTypeImpl pruned(List<FunctionTypeAliasElement> prune) { | 914 FunctionTypeImpl pruned(List<FunctionTypeAliasElement> prune) { |
915 if (prune == null) { | 915 if (prune == null) { |
916 return this; | 916 return this; |
917 } else if (prune.contains(element)) { | 917 } else if (prune.contains(element)) { |
918 // Circularity found. Prune the type declaration. | 918 // Circularity found. Prune the type declaration. |
919 return new CircularFunctionTypeImpl(); | 919 return new CircularFunctionTypeImpl(); |
(...skipping 149 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1069 | 1069 |
1070 /** | 1070 /** |
1071 * Compares two function types [t] and [s] to see if their corresponding | 1071 * Compares two function types [t] and [s] to see if their corresponding |
1072 * parameter types match [parameterRelation] and their return types match | 1072 * parameter types match [parameterRelation] and their return types match |
1073 * [returnRelation]. | 1073 * [returnRelation]. |
1074 * | 1074 * |
1075 * Used for the various relations on function types which have the same | 1075 * Used for the various relations on function types which have the same |
1076 * structural rules for handling optional parameters and arity, but use their | 1076 * structural rules for handling optional parameters and arity, but use their |
1077 * own relation for comparing corresponding parameters or return types. | 1077 * own relation for comparing corresponding parameters or return types. |
1078 * | 1078 * |
1079 * If [returnRelation] is omitted, uses [parameterRelation] for both. | 1079 * If [parameterRelation] is omitted, uses [returnRelation] for both. This |
| 1080 * is convenient for Dart 1 type system methods. |
1080 */ | 1081 */ |
1081 static bool relate( | 1082 static bool relate( |
1082 FunctionType t, | 1083 FunctionType t, |
1083 DartType other, | 1084 DartType other, |
1084 bool parameterRelation( | 1085 bool returnRelation(DartType t, DartType s), |
1085 DartType t, DartType s, bool tIsCovariant, bool sIsCovariant), | |
1086 DartType instantiateToBounds(DartType t), | 1086 DartType instantiateToBounds(DartType t), |
1087 {bool returnRelation(DartType t, DartType s)}) { | 1087 {bool parameterRelation(ParameterElement t, ParameterElement s)}) { |
1088 returnRelation ??= (t, s) => parameterRelation(t, s, false, false); | 1088 parameterRelation ??= (t, s) => returnRelation(t.type, s.type); |
1089 | 1089 |
1090 // Trivial base cases. | 1090 // Trivial base cases. |
1091 if (other == null) { | 1091 if (other == null) { |
1092 return false; | 1092 return false; |
1093 } else if (identical(t, other) || | 1093 } else if (identical(t, other) || |
1094 other.isDynamic || | 1094 other.isDynamic || |
1095 other.isDartCoreFunction || | 1095 other.isDartCoreFunction || |
1096 other.isObject) { | 1096 other.isObject) { |
1097 return true; | 1097 return true; |
1098 } else if (other is! FunctionType) { | 1098 } else if (other is! FunctionType) { |
1099 return false; | 1099 return false; |
1100 } | 1100 } |
1101 | 1101 |
1102 // This type cast is safe, because we checked it above. | 1102 // This type cast is safe, because we checked it above. |
1103 FunctionType s = other as FunctionType; | 1103 FunctionType s = other as FunctionType; |
1104 if (t.typeFormals.isNotEmpty) { | 1104 if (t.typeFormals.isNotEmpty) { |
1105 List<DartType> freshVariables = relateTypeFormals(t, s, returnRelation); | 1105 List<DartType> freshVariables = |
| 1106 relateTypeFormals(t, s, (s, t, _, __) => returnRelation(s, t)); |
1106 if (freshVariables == null) { | 1107 if (freshVariables == null) { |
1107 return false; | 1108 return false; |
1108 } | 1109 } |
1109 t = t.instantiate(freshVariables); | 1110 t = t.instantiate(freshVariables); |
1110 s = s.instantiate(freshVariables); | 1111 s = s.instantiate(freshVariables); |
1111 } else if (s.typeFormals.isNotEmpty) { | 1112 } else if (s.typeFormals.isNotEmpty) { |
1112 return false; | 1113 return false; |
1113 } | 1114 } |
1114 | 1115 |
1115 // Test the return types. | 1116 // Test the return types. |
1116 DartType sRetType = s.returnType; | 1117 DartType sRetType = s.returnType; |
1117 if (!sRetType.isVoid && !returnRelation(t.returnType, sRetType)) { | 1118 if (!sRetType.isVoid && !returnRelation(t.returnType, sRetType)) { |
1118 return false; | 1119 return false; |
1119 } | 1120 } |
1120 | 1121 |
1121 // Test the parameter types. | 1122 // Test the parameter types. |
| 1123 return relateParameters(t.parameters, s.parameters, parameterRelation); |
| 1124 } |
1122 | 1125 |
| 1126 /** |
| 1127 * Compares parameters [tParams] and [sParams] of two function types, taking |
| 1128 * corresponding parameters from the lists, and see if they match |
| 1129 * [parameterRelation]. |
| 1130 * |
| 1131 * Corresponding parameters are defined as a pair `(t, s)` where `t` is a |
| 1132 * parameter from [tParams] and `s` is a parameter from [sParams], and both |
| 1133 * `t` and `s` are at the same position (for positional parameters) |
| 1134 * or have the same name (for named parameters). |
| 1135 * |
| 1136 * Used for the various relations on function types which have the same |
| 1137 * structural rules for handling optional parameters and arity, but use their |
| 1138 * own relation for comparing the parameters. |
| 1139 */ |
| 1140 static bool relateParameters( |
| 1141 List<ParameterElement> tParams, |
| 1142 List<ParameterElement> sParams, |
| 1143 bool parameterRelation(ParameterElement t, ParameterElement s)) { |
1123 // TODO(jmesserly): this could be implemented with less allocation if we | 1144 // TODO(jmesserly): this could be implemented with less allocation if we |
1124 // wanted, by taking advantage of the fact that positional arguments must | 1145 // wanted, by taking advantage of the fact that positional arguments must |
1125 // appear before named ones. | 1146 // appear before named ones. |
1126 var tRequired = <ParameterElement>[]; | 1147 var tRequired = <ParameterElement>[]; |
1127 var tOptional = <ParameterElement>[]; | 1148 var tOptional = <ParameterElement>[]; |
1128 var tNamed = <String, ParameterElement>{}; | 1149 var tNamed = <String, ParameterElement>{}; |
1129 for (var p in t.parameters) { | 1150 for (var p in tParams) { |
1130 var kind = p.parameterKind; | 1151 var kind = p.parameterKind; |
1131 if (kind == ParameterKind.REQUIRED) { | 1152 if (kind == ParameterKind.REQUIRED) { |
1132 tRequired.add(p); | 1153 tRequired.add(p); |
1133 } else if (kind == ParameterKind.POSITIONAL) { | 1154 } else if (kind == ParameterKind.POSITIONAL) { |
1134 tOptional.add(p); | 1155 tOptional.add(p); |
1135 } else { | 1156 } else { |
1136 assert(kind == ParameterKind.NAMED); | 1157 assert(kind == ParameterKind.NAMED); |
1137 tNamed[p.name] = p; | 1158 tNamed[p.name] = p; |
1138 } | 1159 } |
1139 } | 1160 } |
1140 | 1161 |
1141 var sRequired = <ParameterElement>[]; | 1162 var sRequired = <ParameterElement>[]; |
1142 var sOptional = <ParameterElement>[]; | 1163 var sOptional = <ParameterElement>[]; |
1143 var sNamed = <String, ParameterElement>{}; | 1164 var sNamed = <String, ParameterElement>{}; |
1144 for (var p in s.parameters) { | 1165 for (var p in sParams) { |
1145 var kind = p.parameterKind; | 1166 var kind = p.parameterKind; |
1146 if (kind == ParameterKind.REQUIRED) { | 1167 if (kind == ParameterKind.REQUIRED) { |
1147 sRequired.add(p); | 1168 sRequired.add(p); |
1148 } else if (kind == ParameterKind.POSITIONAL) { | 1169 } else if (kind == ParameterKind.POSITIONAL) { |
1149 sOptional.add(p); | 1170 sOptional.add(p); |
1150 } else { | 1171 } else { |
1151 assert(kind == ParameterKind.NAMED); | 1172 assert(kind == ParameterKind.NAMED); |
1152 sNamed[p.name] = p; | 1173 sNamed[p.name] = p; |
1153 } | 1174 } |
1154 } | 1175 } |
(...skipping 12 matching lines...) Expand all Loading... |
1167 } | 1188 } |
1168 | 1189 |
1169 // For each named parameter in s, make sure we have a corresponding one | 1190 // For each named parameter in s, make sure we have a corresponding one |
1170 // that relates. | 1191 // that relates. |
1171 for (String key in sNamed.keys) { | 1192 for (String key in sNamed.keys) { |
1172 var tParam = tNamed[key]; | 1193 var tParam = tNamed[key]; |
1173 if (tParam == null) { | 1194 if (tParam == null) { |
1174 return false; | 1195 return false; |
1175 } | 1196 } |
1176 var sParam = sNamed[key]; | 1197 var sParam = sNamed[key]; |
1177 if (!parameterRelation( | 1198 if (!parameterRelation(tParam, sParam)) { |
1178 tParam.type, sParam.type, tParam.isCovariant, sParam.isCovariant)) { | |
1179 return false; | 1199 return false; |
1180 } | 1200 } |
1181 } | 1201 } |
1182 | 1202 |
1183 // Make sure all of the positional parameters (both required and optional) | 1203 // Make sure all of the positional parameters (both required and optional) |
1184 // relate to each other. | 1204 // relate to each other. |
1185 var tPositional = tRequired; | 1205 var tPositional = tRequired; |
1186 var sPositional = sRequired; | 1206 var sPositional = sRequired; |
1187 | 1207 |
1188 if (tOptional.isNotEmpty) { | 1208 if (tOptional.isNotEmpty) { |
1189 tPositional = tPositional.toList()..addAll(tOptional); | 1209 tPositional = tPositional.toList()..addAll(tOptional); |
1190 } | 1210 } |
1191 | 1211 |
1192 if (sOptional.isNotEmpty) { | 1212 if (sOptional.isNotEmpty) { |
1193 sPositional = sPositional.toList()..addAll(sOptional); | 1213 sPositional = sPositional.toList()..addAll(sOptional); |
1194 } | 1214 } |
1195 | 1215 |
1196 // Check that s has enough required parameters. | 1216 // Check that s has enough required parameters. |
1197 if (sRequired.length < tRequired.length) { | 1217 if (sRequired.length < tRequired.length) { |
1198 return false; | 1218 return false; |
1199 } | 1219 } |
1200 | 1220 |
1201 // Check that s does not include more positional parameters than we do. | 1221 // Check that s does not include more positional parameters than we do. |
1202 if (tPositional.length < sPositional.length) { | 1222 if (tPositional.length < sPositional.length) { |
1203 return false; | 1223 return false; |
1204 } | 1224 } |
1205 | 1225 |
1206 for (int i = 0; i < sPositional.length; i++) { | 1226 for (int i = 0; i < sPositional.length; i++) { |
1207 var tParam = tPositional[i]; | 1227 if (!parameterRelation(tPositional[i], sPositional[i])) { |
1208 var sParam = sPositional[i]; | |
1209 if (!parameterRelation( | |
1210 tParam.type, sParam.type, tParam.isCovariant, sParam.isCovariant)) { | |
1211 return false; | 1228 return false; |
1212 } | 1229 } |
1213 } | 1230 } |
1214 | 1231 |
1215 return true; | 1232 return true; |
1216 } | 1233 } |
1217 | 1234 |
1218 /** | 1235 /** |
1219 * Given two functions [f1] and [f2] where f1 and f2 are known to be | 1236 * Given two functions [f1] and [f2] where f1 and f2 are known to be |
1220 * generic function types (both have type formals), this checks that they | 1237 * generic function types (both have type formals), this checks that they |
1221 * have the same number of formals, and that those formals have bounds | 1238 * have the same number of formals, and that those formals have bounds |
1222 * (e.g. `<T extends LowerBound>`) that satisfy [relation]. | 1239 * (e.g. `<T extends LowerBound>`) that satisfy [relation]. |
1223 * | 1240 * |
1224 * The return value will be a new list of fresh type variables, that can be | 1241 * The return value will be a new list of fresh type variables, that can be |
1225 * used to instantiate both function types, allowing further comparison. | 1242 * used to instantiate both function types, allowing further comparison. |
1226 * For example, given `<T>T -> T` and `<U>U -> U` we can instantiate them with | 1243 * For example, given `<T>T -> T` and `<U>U -> U` we can instantiate them with |
1227 * `F` to get `F -> F` and `F -> F`, which we can see are equal. | 1244 * `F` to get `F -> F` and `F -> F`, which we can see are equal. |
1228 */ | 1245 */ |
1229 static List<DartType> relateTypeFormals( | 1246 static List<DartType> relateTypeFormals( |
1230 FunctionType f1, FunctionType f2, bool relation(DartType t, DartType s)) { | 1247 FunctionType f1, |
| 1248 FunctionType f2, |
| 1249 bool relation(DartType bound2, DartType bound1, |
| 1250 TypeParameterElement formal2, TypeParameterElement formal1)) { |
1231 List<TypeParameterElement> params1 = f1.typeFormals; | 1251 List<TypeParameterElement> params1 = f1.typeFormals; |
1232 List<TypeParameterElement> params2 = f2.typeFormals; | 1252 List<TypeParameterElement> params2 = f2.typeFormals; |
1233 int count = params1.length; | 1253 int count = params1.length; |
1234 if (params2.length != count) { | 1254 if (params2.length != count) { |
1235 return null; | 1255 return null; |
1236 } | 1256 } |
1237 // We build up a substitution matching up the type parameters | 1257 // We build up a substitution matching up the type parameters |
1238 // from the two types, {variablesFresh/variables1} and | 1258 // from the two types, {variablesFresh/variables1} and |
1239 // {variablesFresh/variables2} | 1259 // {variablesFresh/variables2} |
1240 List<DartType> variables1 = <DartType>[]; | 1260 List<DartType> variables1 = <DartType>[]; |
(...skipping 10 matching lines...) Expand all Loading... |
1251 DartType variableFresh = new TypeParameterTypeImpl(pFresh); | 1271 DartType variableFresh = new TypeParameterTypeImpl(pFresh); |
1252 | 1272 |
1253 variables1.add(variable1); | 1273 variables1.add(variable1); |
1254 variables2.add(variable2); | 1274 variables2.add(variable2); |
1255 variablesFresh.add(variableFresh); | 1275 variablesFresh.add(variableFresh); |
1256 DartType bound1 = p1.bound ?? DynamicTypeImpl.instance; | 1276 DartType bound1 = p1.bound ?? DynamicTypeImpl.instance; |
1257 DartType bound2 = p2.bound ?? DynamicTypeImpl.instance; | 1277 DartType bound2 = p2.bound ?? DynamicTypeImpl.instance; |
1258 bound1 = bound1.substitute2(variablesFresh, variables1); | 1278 bound1 = bound1.substitute2(variablesFresh, variables1); |
1259 bound2 = bound2.substitute2(variablesFresh, variables2); | 1279 bound2 = bound2.substitute2(variablesFresh, variables2); |
1260 pFresh.bound = bound2; | 1280 pFresh.bound = bound2; |
1261 if (!relation(bound2, bound1)) { | 1281 if (!relation(bound2, bound1, p2, p1)) { |
1262 return null; | 1282 return null; |
1263 } | 1283 } |
1264 } | 1284 } |
1265 return variablesFresh; | 1285 return variablesFresh; |
1266 } | 1286 } |
1267 | 1287 |
1268 /** | 1288 /** |
1269 * Return `true` if all of the name/type pairs in the first map ([firstTypes]) | 1289 * Return `true` if all of the name/type pairs in the first map ([firstTypes]) |
1270 * are equal to the corresponding name/type pairs in the second map | 1290 * are equal to the corresponding name/type pairs in the second map |
1271 * ([secondTypes]). The maps are expected to iterate over their entries in the | 1291 * ([secondTypes]). The maps are expected to iterate over their entries in the |
(...skipping 1666 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2938 | 2958 |
2939 @override | 2959 @override |
2940 TypeImpl pruned(List<FunctionTypeAliasElement> prune) => this; | 2960 TypeImpl pruned(List<FunctionTypeAliasElement> prune) => this; |
2941 | 2961 |
2942 @override | 2962 @override |
2943 VoidTypeImpl substitute2( | 2963 VoidTypeImpl substitute2( |
2944 List<DartType> argumentTypes, List<DartType> parameterTypes, | 2964 List<DartType> argumentTypes, List<DartType> parameterTypes, |
2945 [List<FunctionTypeAliasElement> prune]) => | 2965 [List<FunctionTypeAliasElement> prune]) => |
2946 this; | 2966 this; |
2947 } | 2967 } |
OLD | NEW |