OLD | NEW |
| (Empty) |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | |
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. | |
4 | |
5 part of types; | |
6 | |
7 class UnionTypeMask implements TypeMask { | |
8 final Iterable<FlatTypeMask> disjointMasks; | |
9 | |
10 static const int MAX_UNION_LENGTH = 4; | |
11 | |
12 UnionTypeMask._internal(this.disjointMasks) { | |
13 assert(disjointMasks.length > 1); | |
14 assert(disjointMasks.every((TypeMask mask) => !mask.isUnion)); | |
15 } | |
16 | |
17 static TypeMask unionOf(Iterable<TypeMask> masks, ClassWorld classWorld) { | |
18 assert(masks.every((mask) => TypeMask.assertIsNormalized(mask, classWorld)))
; | |
19 List<FlatTypeMask> disjoint = <FlatTypeMask>[]; | |
20 unionOfHelper(masks, disjoint, classWorld); | |
21 if (disjoint.isEmpty) return new TypeMask.nonNullEmpty(); | |
22 if (disjoint.length > MAX_UNION_LENGTH) { | |
23 return flatten(disjoint, classWorld); | |
24 } | |
25 if (disjoint.length == 1) return disjoint[0]; | |
26 UnionTypeMask union = new UnionTypeMask._internal(disjoint); | |
27 assert(TypeMask.assertIsNormalized(union, classWorld)); | |
28 return union; | |
29 } | |
30 | |
31 static void unionOfHelper(Iterable<TypeMask> masks, | |
32 List<FlatTypeMask> disjoint, | |
33 ClassWorld classWorld) { | |
34 // TODO(johnniwinther): Impose an order on the mask to ensure subclass masks | |
35 // are preferred to subtype masks. | |
36 for (TypeMask mask in masks) { | |
37 mask = TypeMask.nonForwardingMask(mask); | |
38 if (mask.isUnion) { | |
39 UnionTypeMask union = mask; | |
40 unionOfHelper(union.disjointMasks, disjoint, classWorld); | |
41 } else if (mask.isEmpty && !mask.isNullable) { | |
42 continue; | |
43 } else { | |
44 FlatTypeMask flatMask = mask; | |
45 int inListIndex = -1; | |
46 bool covered = false; | |
47 | |
48 // Iterate over [disjoint] to find out if one of the mask | |
49 // already covers [mask]. | |
50 for (int i = 0; i < disjoint.length; i++) { | |
51 FlatTypeMask current = disjoint[i]; | |
52 if (current == null) continue; | |
53 TypeMask newMask = flatMask.union(current, classWorld); | |
54 // If we have found a disjoint union, continue iterating. | |
55 if (newMask.isUnion) continue; | |
56 covered = true; | |
57 // We found a mask that is either equal to [mask] or is a | |
58 // supertype of [mask]. | |
59 if (current == newMask) break; | |
60 | |
61 // [mask] is a supertype of [current], replace the [disjoint] | |
62 // list with [newMask] instead of [current]. Note that | |
63 // [newMask] may contain different information than [mask], | |
64 // like nullability. | |
65 disjoint[i] = newMask; | |
66 flatMask = newMask; | |
67 | |
68 if (inListIndex != -1) { | |
69 // If the mask was already covered, we remove the previous | |
70 // place where it was inserted. This new mask subsumes the | |
71 // previously covered one. | |
72 disjoint.removeAt(inListIndex); | |
73 i--; | |
74 } | |
75 // Record where the mask was inserted. | |
76 inListIndex = i; | |
77 } | |
78 // If none of the masks in [disjoint] covers [mask], we just | |
79 // add [mask] to the list. | |
80 if (!covered) disjoint.add(flatMask); | |
81 } | |
82 } | |
83 } | |
84 | |
85 static TypeMask flatten(List<FlatTypeMask> masks, ClassWorld classWorld) { | |
86 assert(masks.length > 1); | |
87 // If either type mask is a subtype type mask, we cannot use a | |
88 // subclass type mask to represent their union. | |
89 bool useSubclass = masks.every((e) => !e.isSubtype); | |
90 bool isNullable = masks.any((e) => e.isNullable); | |
91 | |
92 Iterable<ClassElement> candidates = | |
93 classWorld.commonSupertypesOf(masks.map((mask) => mask.base)); | |
94 | |
95 // Compute the best candidate and its kind. | |
96 ClassElement bestElement; | |
97 int bestKind; | |
98 int bestSize; | |
99 for (ClassElement candidate in candidates) { | |
100 Iterable<ClassElement> subclasses = useSubclass | |
101 ? classWorld.subclassesOf(candidate) | |
102 : const <ClassElement>[]; | |
103 int size; | |
104 int kind; | |
105 if (masks.every((t) => subclasses.contains(t.base))) { | |
106 // If both [this] and [other] are subclasses of the supertype, | |
107 // then we prefer to construct a subclass type mask because it | |
108 // will always be at least as small as the corresponding | |
109 // subtype type mask. | |
110 kind = FlatTypeMask.SUBCLASS; | |
111 size = subclasses.length; | |
112 assert(size <= classWorld.subtypesOf(candidate).length); | |
113 } else { | |
114 kind = FlatTypeMask.SUBTYPE; | |
115 size = classWorld.subtypesOf(candidate).length; | |
116 } | |
117 // Update the best candidate if the new one is better. | |
118 if (bestElement == null || size < bestSize) { | |
119 bestElement = candidate; | |
120 bestSize = size; | |
121 bestKind = kind; | |
122 } | |
123 } | |
124 return new TypeMask(bestElement, bestKind, isNullable, classWorld); | |
125 } | |
126 | |
127 TypeMask union(var other, ClassWorld classWorld) { | |
128 other = TypeMask.nonForwardingMask(other); | |
129 if (!other.isUnion && disjointMasks.contains(other)) return this; | |
130 | |
131 List<FlatTypeMask> newList = | |
132 new List<FlatTypeMask>.from(disjointMasks); | |
133 if (!other.isUnion) { | |
134 newList.add(other); | |
135 } else { | |
136 assert(other is UnionTypeMask); | |
137 newList.addAll(other.disjointMasks); | |
138 } | |
139 return new TypeMask.unionOf(newList, classWorld); | |
140 } | |
141 | |
142 TypeMask intersection(var other, ClassWorld classWorld) { | |
143 other = TypeMask.nonForwardingMask(other); | |
144 if (!other.isUnion && disjointMasks.contains(other)) return other; | |
145 | |
146 List<TypeMask> intersections = <TypeMask>[]; | |
147 for (TypeMask current in disjointMasks) { | |
148 if (other.isUnion) { | |
149 for (FlatTypeMask flatOther in other.disjointMasks) { | |
150 intersections.add(current.intersection(flatOther, classWorld)); | |
151 } | |
152 } else { | |
153 intersections.add(current.intersection(other, classWorld)); | |
154 } | |
155 } | |
156 return new TypeMask.unionOf(intersections, classWorld); | |
157 } | |
158 | |
159 TypeMask nullable() { | |
160 if (isNullable) return this; | |
161 List<FlatTypeMask> newList = new List<FlatTypeMask>.from(disjointMasks); | |
162 newList[0] = newList[0].nullable(); | |
163 return new UnionTypeMask._internal(newList); | |
164 } | |
165 | |
166 TypeMask nonNullable() { | |
167 if (!isNullable) return this; | |
168 Iterable<FlatTypeMask> newIterable = | |
169 disjointMasks.map((e) => e.nonNullable()); | |
170 return new UnionTypeMask._internal(newIterable); | |
171 } | |
172 | |
173 bool get isEmpty => false; | |
174 bool get isNullable => disjointMasks.any((e) => e.isNullable); | |
175 bool get isExact => false; | |
176 bool get isUnion => true; | |
177 bool get isContainer => false; | |
178 bool get isMap => false; | |
179 bool get isDictionary => false; | |
180 bool get isForwarding => false; | |
181 bool get isValue => false; | |
182 | |
183 /** | |
184 * Checks whether [other] is contained in this union. | |
185 * | |
186 * Invariants: | |
187 * - [other] may not be a [UnionTypeMask] itself | |
188 * - the cheap test matching against individual members of [disjointMasks] | |
189 * must have failed. | |
190 */ | |
191 bool slowContainsCheck(TypeMask other, ClassWorld classWorld) { | |
192 // Unions should never make it here. | |
193 assert(!other.isUnion); | |
194 // Ensure the cheap test fails. | |
195 assert(!disjointMasks.any((mask) => mask.containsMask(other, classWorld))); | |
196 // If we cover object, we should never get here. | |
197 assert(!contains(classWorld.objectClass, classWorld)); | |
198 // Likewise, nullness should be covered. | |
199 assert(isNullable || !other.isNullable); | |
200 // The fast test is precise for exact types. | |
201 if (other.isExact) return false; | |
202 // We cannot contain object. | |
203 if (other.contains(classWorld.objectClass, classWorld)) return false; | |
204 FlatTypeMask flat = TypeMask.nonForwardingMask(other); | |
205 // Check we cover the base class. | |
206 if (!contains(flat.base, classWorld)) return false; | |
207 // Check for other members. | |
208 Iterable<ClassElement> members; | |
209 if (flat.isSubclass) { | |
210 members = classWorld.subclassesOf(flat.base); | |
211 } else { | |
212 assert(flat.isSubtype); | |
213 members = classWorld.subtypesOf(flat.base); | |
214 } | |
215 return members.every((ClassElement cls) => this.contains(cls, classWorld)); | |
216 } | |
217 | |
218 bool isInMask(TypeMask other, ClassWorld classWorld) { | |
219 other = TypeMask.nonForwardingMask(other); | |
220 if (isNullable && !other.isNullable) return false; | |
221 if (other.isUnion) { | |
222 UnionTypeMask union = other; | |
223 bool containedInAnyOf(FlatTypeMask mask, Iterable<FlatTypeMask> masks) { | |
224 // null is not canonicalized for the union but stored only on some | |
225 // masks in [disjointMask]. It has been checked in the surrounding | |
226 // context, so we can safely ignore it here. | |
227 FlatTypeMask maskDisregardNull = mask.nonNullable(); | |
228 return masks.any((FlatTypeMask other) { | |
229 return other.containsMask(maskDisregardNull, classWorld); | |
230 }); | |
231 } | |
232 return disjointMasks.every((FlatTypeMask disjointMask) { | |
233 bool contained = containedInAnyOf(disjointMask, union.disjointMasks); | |
234 assert(contained || !union.slowContainsCheck(disjointMask, classWorld)); | |
235 return contained; | |
236 }); | |
237 } | |
238 return disjointMasks.every((mask) => mask.isInMask(other, classWorld)); | |
239 } | |
240 | |
241 bool containsMask(TypeMask other, ClassWorld classWorld) { | |
242 other = TypeMask.nonForwardingMask(other); | |
243 if (other.isNullable && !isNullable) return false; | |
244 if (other.isUnion) return other.isInMask(this, classWorld); | |
245 other = other.nonNullable(); // nullable is not canonicalized, so drop it. | |
246 bool contained = | |
247 disjointMasks.any((mask) => mask.containsMask(other, classWorld)); | |
248 assert(contained || !slowContainsCheck(other, classWorld)); | |
249 return contained; | |
250 } | |
251 | |
252 bool containsOnlyInt(ClassWorld classWorld) { | |
253 return disjointMasks.every((mask) => mask.containsOnlyInt(classWorld)); | |
254 } | |
255 | |
256 bool containsOnlyDouble(ClassWorld classWorld) { | |
257 return disjointMasks.every((mask) => mask.containsOnlyDouble(classWorld)); | |
258 } | |
259 | |
260 bool containsOnlyNum(ClassWorld classWorld) { | |
261 return disjointMasks.every((mask) { | |
262 return mask.containsOnlyNum(classWorld); | |
263 }); | |
264 } | |
265 | |
266 bool containsOnlyBool(ClassWorld classWorld) { | |
267 return disjointMasks.every((mask) => mask.containsOnlyBool(classWorld)); | |
268 } | |
269 | |
270 bool containsOnlyString(ClassWorld classWorld) { | |
271 return disjointMasks.every((mask) => mask.containsOnlyString(classWorld)); | |
272 } | |
273 | |
274 bool containsOnly(ClassElement element) { | |
275 return disjointMasks.every((mask) => mask.containsOnly(element)); | |
276 } | |
277 | |
278 bool satisfies(ClassElement cls, ClassWorld classWorld) { | |
279 return disjointMasks.every((mask) => mask.satisfies(cls, classWorld)); | |
280 } | |
281 | |
282 bool contains(ClassElement type, ClassWorld classWorld) { | |
283 return disjointMasks.any((e) => e.contains(type, classWorld)); | |
284 } | |
285 | |
286 bool containsAll(ClassWorld classWorld) { | |
287 return disjointMasks.any((mask) => mask.containsAll(classWorld)); | |
288 } | |
289 | |
290 ClassElement singleClass(ClassWorld classWorld) => null; | |
291 | |
292 bool needsNoSuchMethodHandling(Selector selector, ClassWorld classWorld) { | |
293 return disjointMasks.any( | |
294 (e) => e.needsNoSuchMethodHandling(selector, classWorld)); | |
295 } | |
296 | |
297 bool canHit(Element element, Selector selector, ClassWorld classWorld) { | |
298 return disjointMasks.any((e) => e.canHit(element, selector, classWorld)); | |
299 } | |
300 | |
301 Element locateSingleElement(Selector selector, Compiler compiler) { | |
302 Element candidate; | |
303 for (FlatTypeMask mask in disjointMasks) { | |
304 Element current = mask.locateSingleElement(selector, compiler); | |
305 if (current == null) { | |
306 return null; | |
307 } else if (candidate == null) { | |
308 candidate = current; | |
309 } else if (candidate != current) { | |
310 return null; | |
311 } | |
312 } | |
313 return candidate; | |
314 } | |
315 | |
316 String toString() { | |
317 String masksString = (disjointMasks.map((TypeMask mask) => mask.toString()) | |
318 .toList()..sort()).join(", "); | |
319 return 'Union of [$masksString]'; | |
320 } | |
321 | |
322 bool operator==(other) { | |
323 if (identical(this, other)) return true; | |
324 | |
325 bool containsAll() { | |
326 return other.disjointMasks.every((e) { | |
327 var map = disjointMasks.map((e) => e.nonNullable()); | |
328 return map.contains(e.nonNullable()); | |
329 }); | |
330 } | |
331 | |
332 return other is UnionTypeMask | |
333 && other.isNullable == isNullable | |
334 && other.disjointMasks.length == disjointMasks.length | |
335 && containsAll(); | |
336 } | |
337 | |
338 int get hashCode { | |
339 int hashCode = isNullable ? 86 : 43; | |
340 // The order of the masks in [disjointMasks] must not affect the | |
341 // hashCode. | |
342 for (var mask in disjointMasks) { | |
343 hashCode = (hashCode ^ mask.nonNullable().hashCode) & 0x3fffffff; | |
344 } | |
345 return hashCode; | |
346 } | |
347 } | |
OLD | NEW |