content: // 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 types;
  
  class UnionTypeMask implements TypeMask {
    final Iterable<FlatTypeMask> disjointMasks;
  
    static const int MAX_UNION_LENGTH = 4;
  
    UnionTypeMask._(this.disjointMasks);
  
    static TypeMask unionOf(Iterable<TypeMask> masks, Compiler compiler) {
      List<FlatTypeMask> disjoint = <FlatTypeMask>[];
      unionOfHelper(masks, disjoint, compiler);
      if (disjoint.isEmpty) return new TypeMask.nonNullEmpty();
      if (disjoint.length > MAX_UNION_LENGTH) return flatten(disjoint, compiler);
      if (disjoint.length == 1) return disjoint[0];
      return new UnionTypeMask._(disjoint);
    }
  
    static TypeMask nonForwardingMask(mask) {
      while (mask.isForwarding) mask = mask.forwardTo;
      return mask;
    }
  
    static void unionOfHelper(Iterable<TypeMask> masks,
                              List<FlatTypeMask> disjoint,
                              Compiler compiler) {
      for (TypeMask mask in masks) {
        mask = nonForwardingMask(mask);
        if (mask.isUnion) {
          UnionTypeMask union = mask;
          unionOfHelper(union.disjointMasks, disjoint, compiler);
        } else if (mask.isEmpty && !mask.isNullable) {
          continue;
        } else {
          FlatTypeMask flatMask = mask;
          assert(flatMask.base == null || flatMask.base != compiler.dynamicClass);
          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 = mask.union(current, compiler);
            // 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;
            mask = 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(mask);
        }
      }
    }
  
    static TypeMask flatten(List<FlatTypeMask> masks, Compiler compiler) {
      assert(masks.length > 1);
      // 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);
      bool isNullable = masks.any((e) => e.isNullable);
  
      // Compute the common supertypes of the two types.
      ClassElement firstElement = masks[0].base;
      ClassElement secondElement = masks[1].base;
      Iterable<ClassElement> candidates =
          compiler.world.commonSupertypesOf(firstElement, secondElement);
      bool unseenType = false;
      for (int i = 2; i < masks.length; i++) {
        ClassElement element = masks[i].base;
        Set<ClassElement> supertypes = compiler.world.supertypesOf(element);
        if (supertypes == null) {
          unseenType = true;
          break;
        }
        candidates = candidates.where((e) => supertypes.contains(e));
      }
  
      if (candidates.isEmpty || unseenType) {
        // TODO(kasperl): Get rid of this check. It can only happen when
        // at least one of the two base types is 'unseen'.
        return new TypeMask(compiler.objectClass,
                            FlatTypeMask.SUBCLASS,
                            isNullable);
      }
      // Compute the best candidate and its kind.
      ClassElement bestElement;
      int bestKind;
      int bestSize;
      for (ClassElement candidate in candidates) {
        Set<ClassElement> subclasses = useSubclass
            ? compiler.world.subclassesOf(candidate)
            : null;
        int size;
        int kind;
        if (subclasses != null
            && masks.every((t) => subclasses.contains(t.base))) {
          // 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 = FlatTypeMask.SUBCLASS;
          size = subclasses.length;
          assert(size <= compiler.world.subtypesOf(candidate).length);
        } else {
          kind = FlatTypeMask.SUBTYPE;
          size = compiler.world.subtypesOf(candidate).length;
        }
        // Update the best candidate if the new one is better.
        if (bestElement == null || size < bestSize) {
          bestElement = candidate;
          bestSize = size;
          bestKind = kind;
        }
      }
      if (bestElement == compiler.objectClass) bestKind = FlatTypeMask.SUBCLASS;
      return new TypeMask(bestElement, bestKind, isNullable);
    }
  
    TypeMask union(var other, Compiler compiler) {
      other = nonForwardingMask(other);
      if (!other.isUnion && disjointMasks.contains(other)) return this;
  
      List<FlatTypeMask> newList =
          new List<FlatTypeMask>.from(disjointMasks);
      if (!other.isUnion) {
        newList.add(other);
      } else {
        assert(other is UnionTypeMask);
        newList.addAll(other.disjointMasks);
      }
      return new TypeMask.unionOf(newList, compiler);
    }
  
    TypeMask intersection(var other, Compiler compiler) {
      other = nonForwardingMask(other);
      if (!other.isUnion && disjointMasks.contains(other)) return other;
  
      List<TypeMask> intersections = <TypeMask>[];
      for (TypeMask current in disjointMasks) {
        if (other.isUnion) {
          for (FlatTypeMask flatOther in other.disjointMasks) {
            intersections.add(current.intersection(flatOther, compiler));
          }
        } else {
          intersections.add(current.intersection(other, compiler));
        }
      }
      return new TypeMask.unionOf(intersections, compiler);
    }
  
    TypeMask nullable() {
      if (isNullable) return this;
      List<FlatTypeMask> newList = new List<FlatTypeMask>.from(disjointMasks);
      newList[0] = newList[0].nullable();
      return new UnionTypeMask._(newList);
    }
  
    TypeMask nonNullable() {
      if (!isNullable) return this;
      Iterable<FlatTypeMask> newIterable =
          disjointMasks.map((e) => e.nonNullable());
      return new UnionTypeMask._(newIterable);
    }
  
    TypeMask simplify(Compiler compiler) => flatten(disjointMasks, compiler);
  
    bool get isEmpty => false;
    bool get isNullable => disjointMasks.any((e) => e.isNullable);
    bool get isExact => false;
    bool get isUnion => true;
    bool get isContainer => false;
    bool get isForwarding => false;
  
    bool isInMask(TypeMask other, Compiler compiler) {
      return disjointMasks.every((mask) => mask.isInMask(other, compiler));
    }
  
    bool containsMask(TypeMask other, Compiler compiler) {
      return disjointMasks.any((mask) => mask.containsMask(other, compiler));
    }
  
    bool containsOnlyInt(Compiler compiler) {
      return disjointMasks.every((mask) => mask.containsOnlyInt(compiler));
    }
  
    bool containsOnlyDouble(Compiler compiler) {
      return disjointMasks.every((mask) => mask.containsOnlyDouble(compiler));
    }
  
    bool containsOnlyNum(Compiler compiler) {
      return disjointMasks.every((mask) {
        return mask.containsOnlyNum(compiler);
      });
    }
  
    bool containsOnlyNull(Compiler compiler) {
      return disjointMasks.every((mask) => mask.containsOnlyNull(compiler));
    }
  
    bool containsOnlyBool(Compiler compiler) {
      return disjointMasks.every((mask) => mask.containsOnlyBool(compiler));
    }
  
    bool containsOnlyString(Compiler compiler) {
      return disjointMasks.every((mask) => mask.containsOnlyString(compiler));
    }
  
    bool containsOnly(ClassElement element) {
      return disjointMasks.every((mask) => mask.containsOnly(element));
    }
  
    bool satisfies(ClassElement cls, Compiler compiler) {
      return disjointMasks.every((mask) => mask.satisfies(cls, compiler));
    }
  
    bool contains(ClassElement type, Compiler compiler) {
      return disjointMasks.any((e) => e.contains(type, compiler));
    }
  
    bool containsAll(Compiler compiler) {
      return disjointMasks.any((mask) => mask.containsAll(compiler));
    }
  
    ClassElement singleClass(Compiler compiler) => null;
  
    Iterable<ClassElement> containedClasses(Compiler compiler) {
      return disjointMasks.expand(
          (TypeMask mask) => mask.containedClasses(compiler));
    }
  
    bool understands(Selector selector, Compiler compiler) {
      return disjointMasks.any((e) => e.understands(selector, compiler));
    }
  
    bool needsNoSuchMethodHandling(Selector selector, Compiler compiler) {
      return disjointMasks.any(
          (e) => e.needsNoSuchMethodHandling(selector, compiler));
    }
  
    bool canHit(Element element, Selector selector, Compiler compiler) {
      return disjointMasks.any((e) => e.canHit(element, selector, compiler));
    }
  
    Element locateSingleElement(Selector selector, Compiler compiler) {
      Element candidate;
      for (FlatTypeMask mask in disjointMasks) {
        Element current = mask.locateSingleElement(selector, compiler);
        if (current == null) {
          return null;
        } else if (candidate == null) {
          candidate = current;
        } else if (candidate != current) {
          return null;
        }
      }
      return candidate;
    }
  
    String toString() => 'Union of $disjointMasks';
  
    bool operator==(other) {
      if (identical(this, other)) return true;
  
      bool containsAll() {
        return other.disjointMasks.every((e) {
          var map = disjointMasks.map((e) => e.nonNullable());
          return map.contains(e.nonNullable());
        });
      }
  
      return other is UnionTypeMask
          && other.isNullable == isNullable
          && other.disjointMasks.length == disjointMasks.length
          && containsAll();
    }
  
    int get hashCode {
      int hashCode = isNullable ? 86 : 43;
      // The order of the masks in [disjointMasks] must not affect the
      // hashCode.
      for (var mask in disjointMasks) {
        hashCode = (hashCode ^ mask.nonNullable().hashCode) & 0x3fffffff;
      }
      return hashCode;
    }
  }
  