| // Copyright (c) 2013, 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. |
| |
| part of masks; |
| |
| class UnionTypeMask extends TypeMask { |
| /// Tag used for identifying serialized [UnionTypeMask] objects in a |
| /// debugging data stream. |
| static const String tag = 'union-type-mask'; |
| |
| static const int MAX_UNION_LENGTH = 4; |
| |
| // Set this flag to `true` to perform a set-membership based containment check |
| // instead of relying on normalized types. This is quite slow but can be |
| // helpful in debugging. |
| static const bool PERFORM_EXTRA_CONTAINS_CHECK = false; |
| |
| /// Components of the union, none of which is itself a union or nullable. |
| final List<FlatTypeMask> disjointMasks; |
| |
| @override |
| final bool isNullable; |
| |
| @override |
| final bool hasLateSentinel; |
| |
| @override |
| AbstractBool get isLateSentinel => AbstractBool.maybeOrFalse(hasLateSentinel); |
| |
| UnionTypeMask._internal(this.disjointMasks, |
| {this.isNullable, this.hasLateSentinel}) |
| : assert(isNullable != null), |
| assert(hasLateSentinel != null), |
| assert(disjointMasks.length > 1), |
| assert(disjointMasks.every((TypeMask mask) => !mask.isUnion)), |
| assert(disjointMasks.every((TypeMask mask) => !mask.isNullable)), |
| assert(disjointMasks.every((TypeMask mask) => !mask.hasLateSentinel)); |
| |
| /// Deserializes a [UnionTypeMask] object from [source]. |
| factory UnionTypeMask.readFromDataSource( |
| DataSource source, CommonMasks domain) { |
| source.begin(tag); |
| List<FlatTypeMask> disjointMasks = |
| source.readList(() => TypeMask.readFromDataSource(source, domain)); |
| bool isNullable = source.readBool(); |
| bool hasLateSentinel = source.readBool(); |
| source.end(tag); |
| return UnionTypeMask._internal(disjointMasks, |
| isNullable: isNullable, hasLateSentinel: hasLateSentinel); |
| } |
| |
| /// Serializes this [UnionTypeMask] to [sink]. |
| @override |
| void writeToDataSink(DataSink sink) { |
| sink.writeEnum(TypeMaskKind.union); |
| sink.begin(tag); |
| sink.writeList( |
| disjointMasks, (FlatTypeMask mask) => mask.writeToDataSink(sink)); |
| sink.writeBool(isNullable); |
| sink.writeBool(hasLateSentinel); |
| sink.end(tag); |
| } |
| |
| static TypeMask unionOf(Iterable<TypeMask> masks, CommonMasks domain) { |
| assert(masks.every( |
| (mask) => TypeMask.assertIsNormalized(mask, domain._closedWorld))); |
| List<FlatTypeMask> disjoint = <FlatTypeMask>[]; |
| bool isNullable = masks.any((TypeMask mask) => mask.isNullable); |
| bool hasLateSentinel = masks.any((TypeMask mask) => mask.hasLateSentinel); |
| unionOfHelper(masks, disjoint, domain); |
| if (disjoint.isEmpty) |
| return isNullable |
| ? TypeMask.empty(hasLateSentinel: hasLateSentinel) |
| : TypeMask.nonNullEmpty(hasLateSentinel: hasLateSentinel); |
| if (disjoint.length > MAX_UNION_LENGTH) { |
| return flatten(disjoint, domain, |
| includeNull: isNullable, includeLateSentinel: hasLateSentinel); |
| } |
| if (disjoint.length == 1) |
| return disjoint.single |
| .withFlags(isNullable: isNullable, hasLateSentinel: hasLateSentinel); |
| UnionTypeMask union = UnionTypeMask._internal(disjoint, |
| isNullable: isNullable, hasLateSentinel: hasLateSentinel); |
| assert(TypeMask.assertIsNormalized(union, domain._closedWorld)); |
| return union; |
| } |
| |
| static void unionOfHelper(Iterable<TypeMask> masks, |
| List<FlatTypeMask> disjoint, CommonMasks domain) { |
| // TODO(johnniwinther): Impose an order on the mask to ensure subclass masks |
| // are preferred to subtype masks. |
| for (TypeMask mask in masks) { |
| mask = TypeMask.nonForwardingMask(mask).withoutFlags(); |
| if (mask.isUnion) { |
| UnionTypeMask union = mask; |
| unionOfHelper(union.disjointMasks, disjoint, domain); |
| } else if (mask.isEmpty) { |
| continue; |
| } else { |
| FlatTypeMask flatMask = mask; |
| int inListIndex = -1; |
| bool covered = false; |
| |
| // Iterate over [disjoint] to find out if one of the mask |
| // already covers [mask]. |
| for (int i = 0; i < disjoint.length; i++) { |
| FlatTypeMask current = disjoint[i]; |
| if (current == null) continue; |
| TypeMask newMask = flatMask.union(current, domain); |
| // If we have found a disjoint union, continue iterating. |
| if (newMask.isUnion) continue; |
| covered = true; |
| // We found a mask that is either equal to [mask] or is a |
| // supertype of [mask]. |
| if (current == newMask) break; |
| |
| // [mask] is a supertype of [current], replace the [disjoint] |
| // list with [newMask] instead of [current]. Note that |
| // [newMask] may contain different information than [mask], |
| // like nullability. |
| disjoint[i] = newMask; |
| flatMask = newMask; |
| |
| if (inListIndex != -1) { |
| // If the mask was already covered, we remove the previous |
| // place where it was inserted. This new mask subsumes the |
| // previously covered one. |
| disjoint.removeAt(inListIndex); |
| i--; |
| } |
| // Record where the mask was inserted. |
| inListIndex = i; |
| } |
| // If none of the masks in [disjoint] covers [mask], we just |
| // add [mask] to the list. |
| if (!covered) disjoint.add(flatMask); |
| } |
| } |
| } |
| |
| static TypeMask flatten(List<FlatTypeMask> masks, CommonMasks domain, |
| {bool includeNull, bool includeLateSentinel}) { |
| assert(includeNull != null); |
| assert(includeLateSentinel != null); |
| |
| // TODO(johnniwinther): Move this computation to [ClosedWorld] and use the |
| // class set structures. |
| if (masks.isEmpty) throw ArgumentError.value(masks, 'masks'); |
| // If either type mask is a subtype type mask, we cannot use a |
| // subclass type mask to represent their union. |
| bool useSubclass = masks.every((e) => !e.isSubtype); |
| |
| List<ClassEntity> masksBases = masks.map((mask) => mask.base).toList(); |
| Iterable<ClassEntity> candidates = |
| domain._closedWorld.commonSupertypesOf(masksBases); |
| |
| // Compute the best candidate and its kind. |
| ClassEntity bestElement; |
| _FlatTypeMaskKind bestKind; |
| int bestSize; |
| for (ClassEntity candidate in candidates) { |
| bool isInstantiatedStrictSubclass(cls) => |
| cls != candidate && |
| domain._closedWorld.classHierarchy.isExplicitlyInstantiated(cls) && |
| domain._closedWorld.classHierarchy.isSubclassOf(cls, candidate); |
| |
| int size; |
| _FlatTypeMaskKind kind; |
| if (useSubclass && masksBases.every(isInstantiatedStrictSubclass)) { |
| // If both [this] and [other] are subclasses of the supertype, |
| // then we prefer to construct a subclass type mask because it |
| // will always be at least as small as the corresponding |
| // subtype type mask. |
| kind = _FlatTypeMaskKind.subclass; |
| // TODO(sigmund, johnniwinther): computing length here (and below) is |
| // expensive. If we can't prevent `flatten` from being called a lot, it |
| // might be worth caching results. |
| size = |
| domain._closedWorld.classHierarchy.strictSubclassCount(candidate); |
| assert(size <= |
| domain._closedWorld.classHierarchy.strictSubtypeCount(candidate)); |
| } else { |
| kind = _FlatTypeMaskKind.subtype; |
| size = domain._closedWorld.classHierarchy.strictSubtypeCount(candidate); |
| } |
| // Update the best candidate if the new one is better. |
| if (bestElement == null || size < bestSize) { |
| bestElement = candidate; |
| bestSize = size; |
| bestKind = kind; |
| } |
| } |
| int flags = FlatTypeMask._computeFlags(bestKind, |
| isNullable: includeNull, hasLateSentinel: includeLateSentinel); |
| return FlatTypeMask.normalized(bestElement, flags, domain); |
| } |
| |
| @override |
| TypeMask union(TypeMask other, CommonMasks domain) { |
| other = TypeMask.nonForwardingMask(other); |
| bool isNullable = this.isNullable || other.isNullable; |
| bool hasLateSentinel = this.hasLateSentinel || other.hasLateSentinel; |
| if (other is UnionTypeMask) { |
| if (_containsDisjointMasks(other)) { |
| return withFlags( |
| isNullable: isNullable, hasLateSentinel: hasLateSentinel); |
| } |
| if (other._containsDisjointMasks(this)) { |
| return other.withFlags( |
| isNullable: isNullable, hasLateSentinel: hasLateSentinel); |
| } |
| } else { |
| if (disjointMasks.contains(other.withoutFlags())) { |
| return withFlags( |
| isNullable: isNullable, hasLateSentinel: hasLateSentinel); |
| } |
| } |
| |
| List<FlatTypeMask> newList = List<FlatTypeMask>.of(disjointMasks); |
| if (other is UnionTypeMask) { |
| newList.addAll(other.disjointMasks); |
| } else { |
| newList.add(other); |
| } |
| TypeMask newMask = TypeMask.unionOf(newList, domain); |
| return newMask.withFlags( |
| isNullable: isNullable, hasLateSentinel: hasLateSentinel); |
| } |
| |
| @override |
| TypeMask intersection(TypeMask other, CommonMasks domain) { |
| other = TypeMask.nonForwardingMask(other); |
| bool isNullable = this.isNullable && other.isNullable; |
| bool hasLateSentinel = this.hasLateSentinel && other.hasLateSentinel; |
| if (other is UnionTypeMask) { |
| if (_containsDisjointMasks(other)) { |
| return other.withFlags( |
| isNullable: isNullable, hasLateSentinel: hasLateSentinel); |
| } |
| if (other._containsDisjointMasks(this)) { |
| return withFlags( |
| isNullable: isNullable, hasLateSentinel: hasLateSentinel); |
| } |
| } else { |
| if (disjointMasks.contains(other.withoutFlags())) { |
| return other.withFlags( |
| isNullable: isNullable, hasLateSentinel: hasLateSentinel); |
| } |
| } |
| |
| List<TypeMask> intersections = <TypeMask>[]; |
| for (TypeMask current in disjointMasks) { |
| if (other is UnionTypeMask) { |
| if (other.disjointMasks.contains(current)) { |
| intersections.add(current); |
| } else { |
| for (FlatTypeMask flatOther in other.disjointMasks) { |
| intersections.add(current.intersection(flatOther, domain)); |
| } |
| } |
| } else { |
| intersections.add(current.intersection(other, domain)); |
| } |
| } |
| TypeMask newMask = TypeMask.unionOf(intersections, domain); |
| return newMask.withFlags( |
| isNullable: isNullable, hasLateSentinel: hasLateSentinel); |
| } |
| |
| @override |
| bool isDisjoint(TypeMask other, JClosedWorld closedWorld) { |
| if (isNullable && other.isNullable) return false; |
| if (hasLateSentinel && other.hasLateSentinel) return false; |
| for (var current in disjointMasks) { |
| if (!current.isDisjoint(other, closedWorld)) return false; |
| } |
| return true; |
| } |
| |
| @override |
| UnionTypeMask withFlags({bool isNullable, bool hasLateSentinel}) { |
| isNullable ??= this.isNullable; |
| hasLateSentinel ??= this.hasLateSentinel; |
| if (isNullable == this.isNullable && |
| hasLateSentinel == this.hasLateSentinel) { |
| return this; |
| } |
| List<FlatTypeMask> newList = List<FlatTypeMask>.of(disjointMasks); |
| return UnionTypeMask._internal(newList, |
| isNullable: isNullable, hasLateSentinel: hasLateSentinel); |
| } |
| |
| @override |
| bool get isEmptyOrFlagged => false; |
| @override |
| bool get isEmpty => false; |
| @override |
| bool get isNull => false; |
| @override |
| bool get isExact => false; |
| @override |
| bool get isUnion => true; |
| @override |
| bool get isContainer => false; |
| @override |
| bool get isSet => false; |
| @override |
| bool get isMap => false; |
| @override |
| bool get isDictionary => false; |
| @override |
| bool get isForwarding => false; |
| @override |
| bool get isValue => false; |
| |
| /// Checks whether [other] is contained in this union. |
| /// |
| /// Invariants: |
| /// - [other] may not be a [UnionTypeMask] itself |
| /// - the cheap test matching against individual members of [disjointMasks] |
| /// must have failed. |
| bool _slowContainsCheck(TypeMask other, JClosedWorld closedWorld) { |
| // Unions should never make it here. |
| assert(!other.isUnion); |
| // Likewise, nullness should be covered. |
| assert(isNullable || !other.isNullable); |
| assert(hasLateSentinel || !other.hasLateSentinel); |
| other = other.withoutFlags(); |
| // Ensure the cheap test fails. |
| assert(!disjointMasks.any((mask) => mask.containsMask(other, closedWorld))); |
| // If we cover object, we should never get here. |
| assert(!contains(closedWorld.commonElements.objectClass, closedWorld)); |
| // The fast test is precise for exact types. |
| if (other.isExact) return false; |
| // We cannot contain object. |
| if (other.contains(closedWorld.commonElements.objectClass, closedWorld)) { |
| return false; |
| } |
| FlatTypeMask flat = TypeMask.nonForwardingMask(other); |
| // Check we cover the base class. |
| if (!contains(flat.base, closedWorld)) return false; |
| // Check for other members. |
| Iterable<ClassEntity> members; |
| if (flat.isSubclass) { |
| members = closedWorld.classHierarchy.strictSubclassesOf(flat.base); |
| } else { |
| assert(flat.isSubtype); |
| members = closedWorld.classHierarchy.strictSubtypesOf(flat.base); |
| } |
| return members.every((ClassEntity cls) => this.contains(cls, closedWorld)); |
| } |
| |
| @override |
| bool isInMask(TypeMask other, JClosedWorld closedWorld) { |
| other = TypeMask.nonForwardingMask(other); |
| if (isNullable && !other.isNullable) return false; |
| if (hasLateSentinel && !other.hasLateSentinel) return false; |
| if (other.isUnion) { |
| UnionTypeMask union = other; |
| return disjointMasks.every((FlatTypeMask disjointMask) { |
| bool contained = union.disjointMasks.any((FlatTypeMask other) => |
| other.containsMask(disjointMask, closedWorld)); |
| if (PERFORM_EXTRA_CONTAINS_CHECK && |
| !contained && |
| union._slowContainsCheck(disjointMask, closedWorld)) { |
| throw "TypeMask based containment check failed for $this and $other."; |
| } |
| return contained; |
| }); |
| } |
| return disjointMasks.every((mask) => mask.isInMask(other, closedWorld)); |
| } |
| |
| @override |
| bool containsMask(TypeMask other, JClosedWorld closedWorld) { |
| other = TypeMask.nonForwardingMask(other); |
| if (other.isNullable && !isNullable) return false; |
| if (other.hasLateSentinel && !hasLateSentinel) return false; |
| if (other.isUnion) return other.isInMask(this, closedWorld); |
| other = other.withoutFlags(); |
| bool contained = |
| disjointMasks.any((mask) => mask.containsMask(other, closedWorld)); |
| if (PERFORM_EXTRA_CONTAINS_CHECK && |
| !contained && |
| _slowContainsCheck(other, closedWorld)) { |
| throw "TypeMask based containment check failed for $this and $other."; |
| } |
| return contained; |
| } |
| |
| @override |
| bool containsOnlyInt(JClosedWorld closedWorld) { |
| return disjointMasks.every((mask) => mask.containsOnlyInt(closedWorld)); |
| } |
| |
| @override |
| bool containsOnlyNum(JClosedWorld closedWorld) { |
| return disjointMasks.every((mask) { |
| return mask.containsOnlyNum(closedWorld); |
| }); |
| } |
| |
| @override |
| bool containsOnlyBool(JClosedWorld closedWorld) { |
| return disjointMasks.every((mask) => mask.containsOnlyBool(closedWorld)); |
| } |
| |
| @override |
| bool containsOnlyString(JClosedWorld closedWorld) { |
| return disjointMasks.every((mask) => mask.containsOnlyString(closedWorld)); |
| } |
| |
| @override |
| bool containsOnly(ClassEntity element) { |
| return disjointMasks.every((mask) => mask.containsOnly(element)); |
| } |
| |
| @override |
| bool satisfies(ClassEntity cls, JClosedWorld closedWorld) { |
| return disjointMasks.every((mask) => mask.satisfies(cls, closedWorld)); |
| } |
| |
| @override |
| bool contains(ClassEntity cls, JClosedWorld closedWorld) { |
| return disjointMasks.any((e) => e.contains(cls, closedWorld)); |
| } |
| |
| @override |
| bool containsAll(JClosedWorld closedWorld) { |
| return disjointMasks.any((mask) => mask.containsAll(closedWorld)); |
| } |
| |
| @override |
| ClassEntity singleClass(JClosedWorld closedWorld) => null; |
| |
| @override |
| bool needsNoSuchMethodHandling(Selector selector, JClosedWorld closedWorld) { |
| return disjointMasks |
| .any((e) => e.needsNoSuchMethodHandling(selector, closedWorld)); |
| } |
| |
| @override |
| bool canHit(MemberEntity element, Name name, JClosedWorld closedWorld) { |
| if (element.enclosingClass == closedWorld.commonElements.jsNullClass) { |
| return isNullable; |
| } |
| return (isNullable && |
| closedWorld.hasElementIn( |
| closedWorld.commonElements.jsNullClass, name, element)) || |
| disjointMasks.any((e) => e.canHit(element, name, closedWorld)); |
| } |
| |
| @override |
| MemberEntity locateSingleMember(Selector selector, CommonMasks domain) { |
| MemberEntity candidate; |
| for (FlatTypeMask mask in disjointMasks) { |
| mask = mask.withFlags( |
| isNullable: isNullable, hasLateSentinel: hasLateSentinel); |
| MemberEntity current = mask.locateSingleMember(selector, domain); |
| if (current == null) { |
| return null; |
| } else if (candidate == null) { |
| candidate = current; |
| } else if (candidate != current) { |
| return null; |
| } |
| } |
| return candidate; |
| } |
| |
| @override |
| String toString() { |
| String masksString = [ |
| if (isNullable) 'null', |
| if (hasLateSentinel) 'sentinel', |
| ...disjointMasks.map((TypeMask mask) => mask.toString()).toList()..sort(), |
| ].join(", "); |
| return 'Union($masksString)'; |
| } |
| |
| @override |
| bool operator ==(other) { |
| if (identical(this, other)) return true; |
| |
| return other is UnionTypeMask && |
| other.isNullable == isNullable && |
| other.hasLateSentinel == hasLateSentinel && |
| other.disjointMasks.length == disjointMasks.length && |
| _containsDisjointMasks(other); |
| } |
| |
| @override |
| int get hashCode { |
| // The order of the masks in [disjointMasks] must not affect the |
| // hashCode. |
| return Hashing.setHash( |
| disjointMasks, Hashing.objectsHash(isNullable, hasLateSentinel)); |
| } |
| |
| bool _containsDisjointMasks(UnionTypeMask other) => |
| other.disjointMasks.every((e) => disjointMasks.contains(e)); |
| } |