pkg/compiler/lib/src/universe/class_set.dart

// Copyright (c) 2015, 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.

library dart2js.world.class_set;

import 'dart:collection' show IterableBase;
import '../elements/elements.dart' show ClassElement;
import '../util/util.dart' show Link;

/// Node for [cls] in a tree forming the subclass relation of [ClassElement]s.
///
/// This is used by the [ClassWorld] to perform queries on subclass and subtype
/// relations.
///
/// For this class hierarchy:
///
///     class A {}
///     class B extends A {}
///     class C extends A {}
///     class D extends B {}
///     class E extends D {}
///
/// the [ClassHierarchyNode]s form this subclass tree:
///
///       Object
///         |
///         A
///        / \
///       B   C
///       |
///       D
///       |
///       E
///
class ClassHierarchyNode {
  final ClassElement cls;

  /// `true` if [cls] has been directly instantiated.
  ///
  /// For instance `C` but _not_ `B` in:
  ///   class B {}
  ///   class C extends B {}
  ///   main() => new C();
  ///
  bool isDirectlyInstantiated = false;

  /// `true` if [cls] has been instantiated through subclasses.
  ///
  /// For instance `A` and `B` but _not_ `C` in:
  ///   class A {}
  ///   class B extends A {}
  ///   class C extends B {}
  ///   main() => [new B(), new C()];
  ///
  bool isIndirectlyInstantiated = false;

  /// The nodes for the direct subclasses of [cls].
  Link<ClassHierarchyNode> _directSubclasses = const Link<ClassHierarchyNode>();

  ClassHierarchyNode(this.cls);

  /// Adds [subclass] as a direct subclass of [cls].
  void addDirectSubclass(ClassHierarchyNode subclass) {
    assert(subclass.cls.superclass == cls);
    assert(!_directSubclasses.contains(subclass));
    _directSubclasses = _directSubclasses.prepend(subclass);
  }

  /// Returns `true` if [other] is contained in the subtree of this node.
  ///
  /// This means that [other] is a subclass of [cls].
  bool contains(ClassElement other) {
    while (other != null) {
      if (cls == other) return true;
      if (cls.hierarchyDepth >= other.hierarchyDepth) return false;
      other = other.superclass;
    }
    return false;
  }

  /// `true` if [cls] has been directly or indirectly instantiated.
  bool get isInstantiated => isDirectlyInstantiated || isIndirectlyInstantiated;

  /// Returns an [Iterable] of the subclasses of [cls] possibly including [cls].
  ///
  /// The directly instantiated, indirectly instantiated and uninstantiated
  /// subclasses of [cls] are returned if [includeDirectlyInstantiated],
  /// [includeIndirectlyInstantiated], and [includeUninstantiated] are `true`,
  /// respectively. If [strict] is `true`, [cls] itself is _not_ returned.
  Iterable<ClassElement> subclasses(
      {bool includeDirectlyInstantiated: true,
       bool includeIndirectlyInstantiated: true,
       bool includeUninstantiated: true,
       bool strict: false}) {
    return new ClassHierarchyNodeIterable(
        this,
        includeRoot: !strict,
        includeDirectlyInstantiated: includeDirectlyInstantiated,
        includeIndirectlyInstantiated: includeIndirectlyInstantiated,
        includeUninstantiated: includeUninstantiated);
  }

  void printOn(StringBuffer sb, String indentation,
               {bool instantiatedOnly: false}) {
    sb.write('$indentation$cls');
    if (isDirectlyInstantiated) {
      sb.write(' directly');
    }
    if (isIndirectlyInstantiated) {
      sb.write(' indirectly');
    }
    sb.write(' [');
    if (_directSubclasses.isEmpty) {
      sb.write(']');
    } else {
      bool needsComma = false;
      for (Link<ClassHierarchyNode> link = _directSubclasses;
           !link.isEmpty;
           link = link.tail) {
        if (instantiatedOnly && !link.head.isInstantiated) {
          continue;
        }
        if (needsComma) {
          sb.write(',\n');
        } else {
          sb.write('\n');
        }
        link.head.printOn(
            sb, '$indentation  ', instantiatedOnly: instantiatedOnly);
        needsComma = true;
      }
      if (needsComma) {
        sb.write('\n');
        sb.write('$indentation]');
      } else {
        sb.write(']');
      }
    }
  }

  String dump({String indentation: '', bool instantiatedOnly: false}) {
    StringBuffer sb = new StringBuffer();
    printOn(sb, indentation, instantiatedOnly: instantiatedOnly);
    return sb.toString();
  }

  String toString() => cls.toString();
}

/// Object holding the subclass and subtype relation for a single
/// [ClassElement].
///
/// The subclass relation for a class `C` is modelled through a reference to
/// the [ClassHierarchyNode] for `C` in the global [ClassHierarchyNode] tree
/// computed in [World].
///
/// The subtype relation for a class `C` is modelled through a collection of
/// disjoint [ClassHierarchyNode] subtrees. The subclasses of `C`, modelled
/// through the aforementioned [ClassHierarchyNode] pointer, are extended with
/// the subtypes that do not extend `C` through a list of additional
/// [ClassHierarchyNode] nodes. This list is normalized to contain only the
/// nodes for the topmost subtypes and is furthermore ordered in increasing
/// hierarchy depth order.
///
/// For this class hierarchy:
///
///     class A {}
///     class B extends A {}
///     class C implements B {}
///     class D implements A {}
///     class E extends D {}
///     class F implements D {}
///
/// the [ClassHierarchyNode] tree is
///
///       Object
///      / |  | \
///     A  C  D  F
///     |     |
///     B     E
///
/// and the [ClassSet] for `A` holds these [ClassHierarchyNode] nodes:
///
///      A  ->  [C, D, F]
///
/// The subtypes `B` and `E` are not directly modeled because they are implied
/// by their subclass relation to `A` and `D`, repectively. This can be seen
/// if we expand the subclass subtrees:
///
///      A  ->  [C, D, F]
///      |          |
///      B          E
///
class ClassSet {
  final ClassHierarchyNode node;

  List<ClassHierarchyNode> _directSubtypes;

  ClassSet(this.node);

  ClassElement get cls => node.cls;

  /// Returns an [Iterable] of the subclasses of [cls] possibly including [cls].
  ///
  /// The directly instantiated, indirectly instantiated and uninstantiated
  /// subclasses of [cls] are returned if [includeDirectlyInstantiated],
  /// [includeIndirectlyInstantiated], and [includeUninstantiated] are `true`,
  /// respectively. If [strict] is `true`, [cls] itself is _not_ returned.
  Iterable<ClassElement> subclasses(
      {bool includeDirectlyInstantiated: true,
       bool includeIndirectlyInstantiated: true,
       bool includeUninstantiated: true,
       bool strict: false}) {
    return node.subclasses(
        strict: strict,
        includeDirectlyInstantiated: includeDirectlyInstantiated,
        includeIndirectlyInstantiated: includeIndirectlyInstantiated,
        includeUninstantiated: includeUninstantiated);
  }

  /// Returns an [Iterable] of the subtypes of [cls] possibly including [cls].
  ///
  /// The directly instantiated, indirectly instantiated and uninstantiated
  /// subtypes of [cls] are returned if [includeDirectlyInstantiated],
  /// [includeIndirectlyInstantiated], and [includeUninstantiated] are `true`,
  /// respectively. If [strict] is `true`, [cls] itself is _not_ returned.
  Iterable<ClassElement> subtypes(
      {bool includeDirectlyInstantiated: true,
       bool includeIndirectlyInstantiated: true,
       bool includeUninstantiated: true,
       bool strict: false}) {
    if (_directSubtypes == null) {
      return node.subclasses(
          strict: strict,
          includeDirectlyInstantiated: includeDirectlyInstantiated,
          includeIndirectlyInstantiated: includeIndirectlyInstantiated,
          includeUninstantiated: includeUninstantiated);
    }
    return new SubtypesIterable.SubtypesIterator(this,
        includeRoot: !strict,
        includeDirectlyInstantiated: includeDirectlyInstantiated,
        includeIndirectlyInstantiated: includeIndirectlyInstantiated,
        includeUninstantiated: includeUninstantiated);
  }

  /// Adds [subtype] as a subtype of [cls].
  void addSubtype(ClassHierarchyNode subtype) {
    if (node.contains(subtype.cls)) {
      return;
    }
    if (_directSubtypes == null) {
      _directSubtypes = <ClassHierarchyNode>[subtype];
    } else {
      int hierarchyDepth = subtype.cls.hierarchyDepth;
      List<ClassHierarchyNode> newSubtypes = <ClassHierarchyNode>[];
      bool added = false;
      for (ClassHierarchyNode otherSubtype in _directSubtypes) {
        int otherHierarchyDepth = otherSubtype.cls.hierarchyDepth;
        if (hierarchyDepth == otherHierarchyDepth) {
          if (subtype == otherSubtype) {
            return;
          } else {
            // [otherSubtype] is unrelated to [subtype].
            newSubtypes.add(otherSubtype);
          }
        } else if (hierarchyDepth > otherSubtype.cls.hierarchyDepth) {
          // [otherSubtype] could be a superclass of [subtype].
          if (otherSubtype.contains(subtype.cls)) {
            // [subtype] is already in this set.
            return;
          } else {
            // [otherSubtype] is unrelated to [subtype].
            newSubtypes.add(otherSubtype);
          }
        } else {
          if (!added) {
            // Insert [subtype] before other subtypes of higher hierarchy depth.
            newSubtypes.add(subtype);
            added = true;
          }
          // [subtype] could be a superclass of [otherSubtype].
          if (subtype.contains(otherSubtype.cls)) {
            // Replace [otherSubtype].
          } else {
            newSubtypes.add(otherSubtype);
          }
        }
      }
      if (!added) {
        newSubtypes.add(subtype);
      }
      _directSubtypes = newSubtypes;
    }
  }

  String toString() {
    StringBuffer sb = new StringBuffer();
    sb.write('[\n');
    node.printOn(sb, '  ');
    sb.write('\n');
    if (_directSubtypes != null) {
      for (ClassHierarchyNode node in _directSubtypes) {
        node.printOn(sb, '  ');
        sb.write('\n');
      }
    }
    sb.write(']');
    return sb.toString();
  }
}

/// Iterable for subclasses of a [ClassHierarchyNode].
class ClassHierarchyNodeIterable extends IterableBase<ClassElement> {
  final ClassHierarchyNode root;
  final bool includeRoot;
  final bool includeDirectlyInstantiated;
  final bool includeIndirectlyInstantiated;
  final bool includeUninstantiated;

  ClassHierarchyNodeIterable(
      this.root,
      {this.includeRoot: true,
       this.includeDirectlyInstantiated: true,
       this.includeIndirectlyInstantiated: true,
       this.includeUninstantiated: true}) {
    if (root == null) throw new StateError("No root for iterable.");
  }

  @override
  Iterator<ClassElement> get iterator {
    return new ClassHierarchyNodeIterator(this);
  }
}

/// Iterator for subclasses of a [ClassHierarchyNode].
///
/// Classes are returned in pre-order DFS fashion.
class ClassHierarchyNodeIterator implements Iterator<ClassElement> {
  final ClassHierarchyNodeIterable iterable;

  /// The class node holding the [current] class.
  ///
  /// This is `null` before the first call to [moveNext] and at the end of
  /// iteration, i.e. after [moveNext] has returned `false`.
  ClassHierarchyNode currentNode;

  /// Stack of pending class nodes.
  ///
  /// This is `null` before the first call to [moveNext].
  Link<ClassHierarchyNode> stack;

  ClassHierarchyNodeIterator(this.iterable);

  ClassHierarchyNode get root => iterable.root;

  bool get includeRoot => iterable.includeRoot;

  bool get includeDirectlyInstantiated => iterable.includeDirectlyInstantiated;

  bool get includeIndirectlyInstantiated {
    return iterable.includeIndirectlyInstantiated;
  }

  bool get includeUninstantiated => iterable.includeUninstantiated;

  @override
  ClassElement get current {
    return currentNode != null ? currentNode.cls : null;
  }

  @override
  bool moveNext() {
    if (stack == null) {
      // First call to moveNext
      stack = const Link<ClassHierarchyNode>().prepend(root);
      return _findNext();
    } else {
      // Initialized state.
      if (currentNode == null) return false;
      return _findNext();
    }
  }

  /// Find the next class using the [stack].
  bool _findNext() {
    while (true) {
      if (stack.isEmpty) {
        // No more classes. Set [currentNode] to `null` to signal the end of
        // iteration.
        currentNode = null;
        return false;
      }
      currentNode = stack.head;
      stack = stack.tail;
      if (!includeUninstantiated && !currentNode.isInstantiated) {
        // We're only iterating instantiated classes so there is no use in
        // visiting the current node and its subtree.
        continue;
      }
      for (Link<ClassHierarchyNode> link = currentNode._directSubclasses;
           !link.isEmpty;
           link = link.tail) {
        stack = stack.prepend(link.head);
      }
      if (_isValid(currentNode)) {
        return true;
      }
    }
  }

  /// Returns `true` if the class of [node] is a valid result for this iterator.
  bool _isValid(ClassHierarchyNode node) {
    if (!includeRoot && node == root) return false;
    if (includeDirectlyInstantiated && node.isDirectlyInstantiated) {
      return true;
    }
    if (includeIndirectlyInstantiated && node.isIndirectlyInstantiated) {
      return true;
    }
    if (includeUninstantiated && !node.isInstantiated) {
      return true;
    }
    return false;
  }
}

/// Iterable for the subtypes in a [ClassSet].
class SubtypesIterable extends IterableBase<ClassElement> {
  final ClassSet subtypeSet;
  final bool includeRoot;
  final bool includeDirectlyInstantiated;
  final bool includeIndirectlyInstantiated;
  final bool includeUninstantiated;

  SubtypesIterable.SubtypesIterator(
      this.subtypeSet,
      {this.includeRoot: true,
       this.includeDirectlyInstantiated: true,
       this.includeIndirectlyInstantiated: true,
       this.includeUninstantiated: true});

  @override
  Iterator<ClassElement> get iterator => new SubtypesIterator(this);
}

/// Iterator for the subtypes in a [ClassSet].
class SubtypesIterator extends Iterator<ClassElement> {
  final SubtypesIterable iterable;
  Iterator<ClassElement> elements;
  Iterator<ClassHierarchyNode> hierarchyNodes;

  SubtypesIterator(this.iterable);

  bool get includeRoot => iterable.includeRoot;

  bool get includeDirectlyInstantiated => iterable.includeDirectlyInstantiated;

  bool get includeIndirectlyInstantiated {
    return iterable.includeIndirectlyInstantiated;
  }

  bool get includeUninstantiated => iterable.includeUninstantiated;

  @override
  ClassElement get current {
    if (elements != null) {
      return elements.current;
    }
    return null;
  }

  @override
  bool moveNext() {
    if (elements == null && hierarchyNodes == null) {
      // Initial state. Iterate through subclasses.
      elements = iterable.subtypeSet.node.subclasses(
          strict: !includeRoot,
          includeDirectlyInstantiated: includeDirectlyInstantiated,
          includeIndirectlyInstantiated: includeIndirectlyInstantiated,
          includeUninstantiated: includeUninstantiated).iterator;
    }
    if (elements != null && elements.moveNext()) {
      return true;
    }
    if (hierarchyNodes == null) {
      // Start iterating through subtypes.
      hierarchyNodes = iterable.subtypeSet._directSubtypes.iterator;
    }
    while (hierarchyNodes.moveNext()) {
      elements = hierarchyNodes.current.subclasses(
          includeDirectlyInstantiated: includeDirectlyInstantiated,
          includeIndirectlyInstantiated: includeIndirectlyInstantiated,
          includeUninstantiated: includeUninstantiated).iterator;
      if (elements.moveNext()) {
        return true;
      }
    }
    return false;
  }
}