| 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 |
|---|
Chromium Code Reviews
Issue 694353007:
Move dart2js from sdk/lib/_internal/compiler to pkg/compiler (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart