OLD | NEW |
1 // Copyright (c) 2017, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2017, 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.md file. | 3 // BSD-style license that can be found in the LICENSE.md file. |
4 | 4 |
5 import 'package:front_end/src/fasta/type_inference/type_schema.dart'; | 5 import 'package:front_end/src/fasta/type_inference/type_schema.dart'; |
6 import 'package:front_end/src/fasta/type_inference/type_schema_environment.dart'
; | 6 import 'package:front_end/src/fasta/type_inference/type_schema_environment.dart'
; |
7 import 'package:kernel/ast.dart'; | 7 import 'package:kernel/ast.dart'; |
| 8 import 'package:kernel/type_algebra.dart'; |
8 | 9 |
9 /// Creates a collection of [TypeConstraint]s corresponding to type parameters, | 10 /// Creates a collection of [TypeConstraint]s corresponding to type parameters, |
10 /// based on an attempt to make one type schema a subtype of another. | 11 /// based on an attempt to make one type schema a subtype of another. |
11 class TypeConstraintGatherer { | 12 class TypeConstraintGatherer { |
12 final TypeSchemaEnvironment environment; | 13 final TypeSchemaEnvironment environment; |
13 | 14 |
14 final _protoConstraints = <_ProtoConstraint>[]; | 15 final _protoConstraints = <_ProtoConstraint>[]; |
15 | 16 |
16 final List<TypeParameter> _parametersToConstrain; | 17 final List<TypeParameter> _parametersToConstrain; |
17 | 18 |
(...skipping 28 matching lines...) Expand all Loading... |
46 /// constraints is unchanged. | 47 /// constraints is unchanged. |
47 bool trySubtypeMatch(DartType subtype, DartType supertype) { | 48 bool trySubtypeMatch(DartType subtype, DartType supertype) { |
48 int oldProtoConstraintsLength = _protoConstraints.length; | 49 int oldProtoConstraintsLength = _protoConstraints.length; |
49 bool isMatch = _isSubtypeMatch(subtype, supertype); | 50 bool isMatch = _isSubtypeMatch(subtype, supertype); |
50 if (!isMatch) { | 51 if (!isMatch) { |
51 _protoConstraints.length = oldProtoConstraintsLength; | 52 _protoConstraints.length = oldProtoConstraintsLength; |
52 } | 53 } |
53 return isMatch; | 54 return isMatch; |
54 } | 55 } |
55 | 56 |
| 57 void _constrainLower(TypeParameter parameter, DartType lower) { |
| 58 _protoConstraints.add(new _ProtoConstraint.lower(parameter, lower)); |
| 59 } |
| 60 |
| 61 void _constrainUpper(TypeParameter parameter, DartType upper) { |
| 62 _protoConstraints.add(new _ProtoConstraint.upper(parameter, upper)); |
| 63 } |
| 64 |
| 65 bool _isFunctionSubtypeMatch(FunctionType subtype, FunctionType supertype) { |
| 66 // A function type `(M0,..., Mn, [M{n+1}, ..., Mm]) -> R0` is a subtype |
| 67 // match for a function type `(N0,..., Nk, [N{k+1}, ..., Nr]) -> R1` with |
| 68 // respect to `L` under constraints `C0 + ... + Cr + C` |
| 69 // - If `R0` is a subtype match for a type `R1` with respect to `L` under |
| 70 // constraints `C`: |
| 71 // - If `n <= k` and `r <= m`. |
| 72 // - And for `i` in `0...r`, `Ni` is a subtype match for `Mi` with respect |
| 73 // to `L` under constraints `Ci`. |
| 74 // Function types with named parameters are treated analogously to the |
| 75 // positional parameter case above. |
| 76 // A generic function type `<T0 extends B0, ..., Tn extends Bn>F0` is a |
| 77 // subtype match for a generic function type `<S0 extends B0, ..., Sn |
| 78 // extends Bn>F1` with respect to `L` under constraints `Cl`: |
| 79 // - If `F0[Z0/T0, ..., Zn/Tn]` is a subtype match for `F0[Z0/S0, ..., |
| 80 // Zn/Sn]` with respect to `L` under constraints `C`, where each `Zi` is a |
| 81 // fresh type variable with bound `Bi`. |
| 82 // - And `Cl` is `C` with each constraint replaced with its closure with |
| 83 // respect to `[Z0, ..., Zn]`. |
| 84 if (subtype.requiredParameterCount > supertype.requiredParameterCount) { |
| 85 return false; |
| 86 } |
| 87 if (subtype.positionalParameters.length < |
| 88 supertype.positionalParameters.length) { |
| 89 return false; |
| 90 } |
| 91 if (subtype.typeParameters.isNotEmpty || |
| 92 supertype.typeParameters.isNotEmpty) { |
| 93 var subtypeSubstitution = <TypeParameter, DartType>{}; |
| 94 var supertypeSubstitution = <TypeParameter, DartType>{}; |
| 95 if (!_matchTypeFormals(subtype.typeParameters, supertype.typeParameters, |
| 96 subtypeSubstitution, supertypeSubstitution)) { |
| 97 return false; |
| 98 } |
| 99 |
| 100 // TODO(paulberry): try to push this functionality into kernel. |
| 101 FunctionType substituteTypeParams( |
| 102 FunctionType type, Map<TypeParameter, DartType> substitutionMap) { |
| 103 var substitution = Substitution.fromMap(substitutionMap); |
| 104 return new FunctionType( |
| 105 type.positionalParameters.map(substitution.substituteType).toList(), |
| 106 substitution.substituteType(type.returnType), |
| 107 namedParameters: type.namedParameters |
| 108 .map((named) => new NamedType( |
| 109 named.name, substitution.substituteType(named.type))) |
| 110 .toList(), |
| 111 typeParameters: substitutionMap.keys.toList(), |
| 112 requiredParameterCount: type.requiredParameterCount); |
| 113 } |
| 114 |
| 115 subtype = substituteTypeParams(subtype, subtypeSubstitution); |
| 116 supertype = substituteTypeParams(supertype, supertypeSubstitution); |
| 117 } |
| 118 |
| 119 // Test the return types. |
| 120 if (supertype.returnType is! VoidType && |
| 121 !_isSubtypeMatch(subtype.returnType, supertype.returnType)) { |
| 122 return false; |
| 123 } |
| 124 |
| 125 // Test the parameter types. |
| 126 for (int i = 0; i < supertype.positionalParameters.length; ++i) { |
| 127 var supertypeParameter = supertype.positionalParameters[i]; |
| 128 var subtypeParameter = subtype.positionalParameters[i]; |
| 129 // Termination: Both types shrink in size. |
| 130 if (!_isSubtypeMatch(supertypeParameter, subtypeParameter)) { |
| 131 return false; |
| 132 } |
| 133 } |
| 134 int subtypeNameIndex = 0; |
| 135 for (NamedType supertypeParameter in supertype.namedParameters) { |
| 136 while (subtypeNameIndex < subtype.namedParameters.length && |
| 137 subtype.namedParameters[subtypeNameIndex].name != |
| 138 supertypeParameter.name) { |
| 139 ++subtypeNameIndex; |
| 140 } |
| 141 if (subtypeNameIndex == subtype.namedParameters.length) return false; |
| 142 NamedType subtypeParameter = subtype.namedParameters[subtypeNameIndex]; |
| 143 // Termination: Both types shrink in size. |
| 144 if (!_isSubtypeMatch(supertypeParameter.type, subtypeParameter.type)) { |
| 145 return false; |
| 146 } |
| 147 } |
| 148 return true; |
| 149 } |
| 150 |
| 151 bool _isInterfaceSubtypeMatch( |
| 152 InterfaceType subtype, InterfaceType supertype) { |
| 153 // A type `P<M0, ..., Mk>` is a subtype match for `P<N0, ..., Nk>` with |
| 154 // respect to `L` under constraints `C0 + ... + Ck`: |
| 155 // - If `Mi` is a subtype match for `Ni` with respect to `L` under |
| 156 // constraints `Ci`. |
| 157 // A type `P<M0, ..., Mk>` is a subtype match for `Q<N0, ..., Nj>` with |
| 158 // respect to `L` under constraints `C`: |
| 159 // - If `R<B0, ..., Bj>` is the superclass of `P<M0, ..., Mk>` and `R<B0, |
| 160 // ..., Bj>` is a subtype match for `Q<N0, ..., Nj>` with respect to `L` |
| 161 // under constraints `C`. |
| 162 // - Or `R<B0, ..., Bj>` is one of the interfaces implemented by `P<M0, ..., |
| 163 // Mk>` (considered in lexical order) and `R<B0, ..., Bj>` is a subtype |
| 164 // match for `Q<N0, ..., Nj>` with respect to `L` under constraints `C`. |
| 165 // - Or `R<B0, ..., Bj>` is a mixin into `P<M0, ..., Mk>` (considered in |
| 166 // lexical order) and `R<B0, ..., Bj>` is a subtype match for `Q<N0, ..., |
| 167 // Nj>` with respect to `L` under constraints `C`. |
| 168 |
| 169 // Note that since kernel requires that no class may only appear in the set |
| 170 // of supertypes of a given type more than once, the order of the checks |
| 171 // above is irrelevant; we just need to find the matched superclass, |
| 172 // substitute, and then iterate through type variables. |
| 173 var matchingSupertypeOfSubtype = |
| 174 environment.hierarchy.getTypeAsInstanceOf(subtype, supertype.classNode); |
| 175 if (matchingSupertypeOfSubtype == null) return false; |
| 176 for (int i = 0; i < supertype.classNode.typeParameters.length; i++) { |
| 177 if (!_isSubtypeMatch(matchingSupertypeOfSubtype.typeArguments[i], |
| 178 supertype.typeArguments[i])) { |
| 179 return false; |
| 180 } |
| 181 } |
| 182 return true; |
| 183 } |
| 184 |
| 185 bool _isNull(DartType type) { |
| 186 // TODO(paulberry): would it be better to call this "_isBottom", and to have |
| 187 // it return `true` for both Null and bottom types? Revisit this once |
| 188 // enough functionality is implemented that we can compare the behavior with |
| 189 // the old analyzer-based implementation. |
| 190 return type is InterfaceType && |
| 191 identical(type.classNode, environment.coreTypes.nullClass); |
| 192 } |
| 193 |
56 /// Attempts to match [subtype] as a subtype of [supertype], gathering any | 194 /// Attempts to match [subtype] as a subtype of [supertype], gathering any |
57 /// constraints discovered in the process. | 195 /// constraints discovered in the process. |
58 /// | 196 /// |
59 /// If a set of constraints was found, `true` is returned and the caller | 197 /// If a set of constraints was found, `true` is returned and the caller |
60 /// may proceed to call [computeConstraints]. Otherwise, `false` is returned. | 198 /// may proceed to call [computeConstraints]. Otherwise, `false` is returned. |
61 /// | 199 /// |
62 /// In the case where `false` is returned, some bogus constraints may have | 200 /// In the case where `false` is returned, some bogus constraints may have |
63 /// been added to [_protoConstraints]. It is the caller's responsibility to | 201 /// been added to [_protoConstraints]. It is the caller's responsibility to |
64 /// discard them if necessary. | 202 /// discard them if necessary. |
65 bool _isSubtypeMatch(DartType subtype, DartType supertype) { | 203 bool _isSubtypeMatch(DartType subtype, DartType supertype) { |
(...skipping 77 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
143 // constraints: | 281 // constraints: |
144 // - If `P` implements a call method. | 282 // - If `P` implements a call method. |
145 // - Or if `P` is a function type. | 283 // - Or if `P` is a function type. |
146 // TODO(paulberry): implement this case. | 284 // TODO(paulberry): implement this case. |
147 // A type `P` is a subtype match for a type `Q` with respect to `L` under | 285 // A type `P` is a subtype match for a type `Q` with respect to `L` under |
148 // constraints `C`: | 286 // constraints `C`: |
149 // - If `P` is an interface type which implements a call method of type `F`, | 287 // - If `P` is an interface type which implements a call method of type `F`, |
150 // and `F` is a subtype match for a type `Q` with respect to `L` under | 288 // and `F` is a subtype match for a type `Q` with respect to `L` under |
151 // constraints `C`. | 289 // constraints `C`. |
152 // TODO(paulberry): implement this case. | 290 // TODO(paulberry): implement this case. |
153 // A function type `(M0,..., Mn, [M{n+1}, ..., Mm]) -> R0` is a subtype | 291 if (subtype is FunctionType) { |
154 // match for a function type `(N0,..., Nk, [N{k+1}, ..., Nr]) -> R1` with | 292 if (supertype is InterfaceType) { |
155 // respect to `L` under constraints `C0 + ... + Cr + C` | 293 if (identical( |
156 // - If `R0` is a subtype match for a type `R1` with respect to `L` under | 294 supertype.classNode, environment.coreTypes.functionClass) || |
157 // constraints `C`: | 295 identical(supertype.classNode, environment.coreTypes.objectClass)) { |
158 // - If `n <= k` and `r <= m`. | 296 return true; |
159 // - And for `i` in `0...r`, `Ni` is a subtype match for `Mi` with respect | 297 } else { |
160 // to `L` under constraints `Ci`. | 298 return false; |
161 // Function types with named parameters are treated analogously to the | 299 } |
162 // positional parameter case above. | 300 } |
163 // TODO(paulberry): implement this case. | 301 if (supertype is FunctionType) { |
164 // A generic function type `<T0 extends B0, ..., Tn extends Bn>F0` is a | 302 return _isFunctionSubtypeMatch(subtype, supertype); |
165 // subtype match for a generic function type `<S0 extends B0, ..., Sn | 303 } |
166 // extends Bn>F1` with respect to `L` under constraints `Cl`: | 304 } |
167 // - If `F0[Z0/T0, ..., Zn/Tn]` is a subtype match for `F0[Z0/S0, ..., | |
168 // Zn/Sn]` with respect to `L` under constraints `C`, where each `Zi` is a | |
169 // fresh type variable with bound `Bi`. | |
170 // - And `Cl` is `C` with each constraint replaced with its closure with | |
171 // respect to `[Z0, ..., Zn]`. | |
172 // TODO(paulberry): implement this case. | |
173 return false; | 305 return false; |
174 } | 306 } |
175 | 307 |
176 void _constrainLower(TypeParameter parameter, DartType lower) { | |
177 _protoConstraints.add(new _ProtoConstraint.lower(parameter, lower)); | |
178 } | |
179 | |
180 void _constrainUpper(TypeParameter parameter, DartType upper) { | |
181 _protoConstraints.add(new _ProtoConstraint.upper(parameter, upper)); | |
182 } | |
183 | |
184 bool _isInterfaceSubtypeMatch( | |
185 InterfaceType subtype, InterfaceType supertype) { | |
186 // A type `P<M0, ..., Mk>` is a subtype match for `P<N0, ..., Nk>` with | |
187 // respect to `L` under constraints `C0 + ... + Ck`: | |
188 // - If `Mi` is a subtype match for `Ni` with respect to `L` under | |
189 // constraints `Ci`. | |
190 // A type `P<M0, ..., Mk>` is a subtype match for `Q<N0, ..., Nj>` with | |
191 // respect to `L` under constraints `C`: | |
192 // - If `R<B0, ..., Bj>` is the superclass of `P<M0, ..., Mk>` and `R<B0, | |
193 // ..., Bj>` is a subtype match for `Q<N0, ..., Nj>` with respect to `L` | |
194 // under constraints `C`. | |
195 // - Or `R<B0, ..., Bj>` is one of the interfaces implemented by `P<M0, ..., | |
196 // Mk>` (considered in lexical order) and `R<B0, ..., Bj>` is a subtype | |
197 // match for `Q<N0, ..., Nj>` with respect to `L` under constraints `C`. | |
198 // - Or `R<B0, ..., Bj>` is a mixin into `P<M0, ..., Mk>` (considered in | |
199 // lexical order) and `R<B0, ..., Bj>` is a subtype match for `Q<N0, ..., | |
200 // Nj>` with respect to `L` under constraints `C`. | |
201 | |
202 // Note that since kernel requires that no class may only appear in the set | |
203 // of supertypes of a given type more than once, the order of the checks | |
204 // above is irrelevant; we just need to find the matched superclass, | |
205 // substitute, and then iterate through type variables. | |
206 var matchingSupertypeOfSubtype = | |
207 environment.hierarchy.getTypeAsInstanceOf(subtype, supertype.classNode); | |
208 if (matchingSupertypeOfSubtype == null) return false; | |
209 for (int i = 0; i < supertype.classNode.typeParameters.length; i++) { | |
210 if (!_isSubtypeMatch(matchingSupertypeOfSubtype.typeArguments[i], | |
211 supertype.typeArguments[i])) { | |
212 return false; | |
213 } | |
214 } | |
215 return true; | |
216 } | |
217 | |
218 bool _isNull(DartType type) { | |
219 // TODO(paulberry): would it be better to call this "_isBottom", and to have | |
220 // it return `true` for both Null and bottom types? Revisit this once | |
221 // enough functionality is implemented that we can compare the behavior with | |
222 // the old analyzer-based implementation. | |
223 return type is InterfaceType && | |
224 identical(type.classNode, environment.coreTypes.nullClass); | |
225 } | |
226 | |
227 bool _isTop(DartType type) => | 308 bool _isTop(DartType type) => |
228 type is DynamicType || | 309 type is DynamicType || |
229 type is VoidType || | 310 type is VoidType || |
230 (type is InterfaceType && | 311 (type is InterfaceType && |
231 identical(type.classNode, environment.coreTypes.objectClass)); | 312 identical(type.classNode, environment.coreTypes.objectClass)); |
| 313 |
| 314 /// Given two lists of function type formal parameters, checks that their |
| 315 /// bounds are compatible. |
| 316 /// |
| 317 /// The return value indicates whether a match was found. If it was, entries |
| 318 /// are added to [substitution1] and [substitution2] which substitute a fresh |
| 319 /// set of type variables for the type parameters [params1] and [params2], |
| 320 /// respectively, allowing further comparison. |
| 321 bool _matchTypeFormals( |
| 322 List<TypeParameter> params1, |
| 323 List<TypeParameter> params2, |
| 324 Map<TypeParameter, DartType> substitution1, |
| 325 Map<TypeParameter, DartType> substitution2) { |
| 326 int count = params1.length; |
| 327 if (count != params2.length) return false; |
| 328 // TODO(paulberry): in imitation of analyzer, we're checking the bounds as |
| 329 // we build up the substitutions. But I don't think that's correct--I think |
| 330 // we should build up both substitutions completely before checking any |
| 331 // bounds. |
| 332 for (int i = 0; i < count; i++) { |
| 333 TypeParameter pFresh = new TypeParameter(params2[i].name); |
| 334 DartType variableFresh = new TypeParameterType(pFresh); |
| 335 substitution1[params1[i]] = variableFresh; |
| 336 substitution2[params2[i]] = variableFresh; |
| 337 DartType bound1 = substitute(params1[i].bound, substitution1); |
| 338 DartType bound2 = substitute(params2[i].bound, substitution2); |
| 339 pFresh.bound = bound2; |
| 340 if (!_isSubtypeMatch(bound2, bound1)) return false; |
| 341 } |
| 342 return true; |
| 343 } |
232 } | 344 } |
233 | 345 |
234 /// Tracks a single constraint on a single type variable. | 346 /// Tracks a single constraint on a single type variable. |
235 /// | 347 /// |
236 /// This is called "_ProtoConstraint" to distinguish from [TypeConstraint], | 348 /// This is called "_ProtoConstraint" to distinguish from [TypeConstraint], |
237 /// which tracks the upper and lower bounds that are together implied by a set | 349 /// which tracks the upper and lower bounds that are together implied by a set |
238 /// of [_ProtoConstraint]s. | 350 /// of [_ProtoConstraint]s. |
239 class _ProtoConstraint { | 351 class _ProtoConstraint { |
240 final TypeParameter parameter; | 352 final TypeParameter parameter; |
241 | 353 |
242 final DartType bound; | 354 final DartType bound; |
243 | 355 |
244 final bool isUpper; | 356 final bool isUpper; |
245 | 357 |
246 _ProtoConstraint.lower(this.parameter, this.bound) : isUpper = false; | 358 _ProtoConstraint.lower(this.parameter, this.bound) : isUpper = false; |
247 | 359 |
248 _ProtoConstraint.upper(this.parameter, this.bound) : isUpper = true; | 360 _ProtoConstraint.upper(this.parameter, this.bound) : isUpper = true; |
249 } | 361 } |
OLD | NEW |