Revert "Optimize subclass/subtype queries"

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 '../common.dart';
 import '../elements/elements.dart' show
     ClassElement;
 import '../util/enumset.dart' show
     EnumSet;
 import '../util/util.dart' show
     Link;
 
 /// Enum for the different kinds of instantiation of a class.
 enum Instantiation {
   UNINSTANTIATED,
@@ skipping 66 matching lines @@
     }
     if (includeIndirectlyInstantiated) {
       mask.add(Instantiation.INDIRECTLY_INSTANTIATED);
     }
     if (includeUninstantiated) {
       mask.add(Instantiation.UNINSTANTIATED);
     }
     return mask;
   }
 
-  final ClassHierarchyNode parentNode;
   final ClassElement cls;
   final EnumSet<Instantiation> _mask =
       new EnumSet<Instantiation>.fromValues(
           const <Instantiation>[Instantiation.UNINSTANTIATED]);
 
   ClassElement _leastUpperInstantiatedSubclass;
-  int _instantiatedSubclassCount = 0;
 
   /// `true` if [cls] has been directly instantiated.
   ///
   /// For instance `C` but _not_ `B` in:
   ///   class B {}
   ///   class C extends B {}
   ///   main() => new C();
   ///
   bool get isDirectlyInstantiated =>
       _mask.contains(Instantiation.DIRECTLY_INSTANTIATED);
 
   void set isDirectlyInstantiated(bool value) {
     if (value != isDirectlyInstantiated) {
-      ClassHierarchyNode parent = parentNode;
       if (value) {
         _mask.remove(Instantiation.UNINSTANTIATED);
         _mask.add(Instantiation.DIRECTLY_INSTANTIATED);
-        while (parent != null) {
-          parent._updateInstantiatedSubclassCount(1);
-          parent = parent.parentNode;
-        }
       } else {
         _mask.remove(Instantiation.DIRECTLY_INSTANTIATED);
         if (_mask.isEmpty) {
           _mask.add(Instantiation.UNINSTANTIATED);
         }
-        while (parent != null) {
-          parent._updateInstantiatedSubclassCount(-1);
-          parent = parent.parentNode;
-        }
       }
     }
   }
 
   /// `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 get isIndirectlyInstantiated => _instantiatedSubclassCount > 0;
+  bool get isIndirectlyInstantiated =>
+      _mask.contains(Instantiation.INDIRECTLY_INSTANTIATED);
 
-  /// The number of strict subclasses that are directly or indirectly
-  /// instantiated.
-  int get instantiatedSubclassCount => _instantiatedSubclassCount;
-
-  void _updateInstantiatedSubclassCount(int change) {
-    bool before = isIndirectlyInstantiated;
-    _instantiatedSubclassCount += change;
-    bool after = isIndirectlyInstantiated;
-    if (before != after) {
-      if (after) {
+  void set isIndirectlyInstantiated(bool value) {
+    if (value != isIndirectlyInstantiated) {
+      if (value) {
         _mask.remove(Instantiation.UNINSTANTIATED);
         _mask.add(Instantiation.INDIRECTLY_INSTANTIATED);
       } else {
         _mask.remove(Instantiation.INDIRECTLY_INSTANTIATED);
         if (_mask.isEmpty) {
           _mask.add(Instantiation.UNINSTANTIATED);
         }
       }
     }
   }
 
   /// The nodes for the direct subclasses of [cls].
   Link<ClassHierarchyNode> _directSubclasses = const Link<ClassHierarchyNode>();
 
-  ClassHierarchyNode(this.parentNode, this.cls) {
-    if (parentNode != null) {
-      parentNode.addDirectSubclass(this);
-    }
-  }
+  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}) {
+    EnumSet<Instantiation> mask = createMask(
+        includeDirectlyInstantiated: includeDirectlyInstantiated,
+        includeIndirectlyInstantiated:includeIndirectlyInstantiated,
+        includeUninstantiated: includeUninstantiated);
+    return subclassesByMask(mask, strict: strict);
+  }
+
+  /// Returns an [Iterable] of the subclasses of [cls] possibly including [cls].
+  ///
   /// Subclasses are included if their instantiation properties intersect with
   /// their corresponding [Instantiation] values in [mask]. If [strict] is
   /// `true`, [cls] itself is _not_ returned.
   Iterable<ClassElement> subclassesByMask(
       EnumSet<Instantiation> mask,
       {bool strict: false}) {
     return new ClassHierarchyNodeIterable(
         this, mask, includeRoot: !strict);
   }
 
-  /// Applies [predicate] to each subclass of [cls] matching the criteria
-  /// specified by [mask] and [strict]. If [predicate] returns `true` on a
-  /// class, visitation is stopped immediately and the function returns `true`.
-  ///
-  /// [predicate] is applied to subclasses if their instantiation properties
-  /// intersect with their corresponding [Instantiation] values in [mask]. If
-  /// [strict] is `true`, [predicate] is _not_ called on [cls] itself.
-  bool anySubclass(
-      bool predicate(ClassElement cls),
-      EnumSet<Instantiation> mask,
-      {bool strict: false}) {
-
-    ForEach wrapper(ClassElement cls) {
-      return predicate(cls) ? ForEach.STOP : ForEach.CONTINUE;
-    }
-    return forEachSubclass(wrapper, mask, strict: strict) == ForEach.STOP;
-  }
-
-  /// Applies [f] to each subclass of [cls] matching the criteria specified by
-  /// [mask] and [strict].
-  ///
-  /// [f] is a applied to subclasses if their instantiation properties intersect
-  /// with their corresponding [Instantiation] values in [mask]. If [strict] is
-  /// `true`, [f] is _not_ called on [cls] itself.
-  ///
-  /// The visitation of subclasses can be cut short by the return value of [f].
-  /// If [ForEach.STOP] is returned, no further classes are visited and the
-  /// function stops immediately. If [ForEach.SKIP_CHILDREN] is returned, the
-  /// subclasses of the last visited class are skipped, but visitation
-  /// continues. The return value of the function is either [ForEach.STOP], if
-  /// visitation was stopped, or [ForEach.CONTINUE] if visitation continued to
-  /// the end.
-  ForEach forEachSubclass(
-      ForEachFunction f,
-      EnumSet<Instantiation> mask,
-      {bool strict: false}) {
-    ForEach forEach;
-    if (!strict && mask.intersects(_mask)) {
-      forEach = f(cls);
-    }
-    // Interpret `forEach == null` as `forEach == ForEach.CONTINUE`.
-    forEach ??= ForEach.CONTINUE;
-
-    if (!mask.contains(Instantiation.UNINSTANTIATED) && !isInstantiated) {
-      // Bypass children since all are uninstantiated.
-      return forEach;
-    }
-    if (forEach == ForEach.CONTINUE) {
-      for (ClassHierarchyNode subclass in _directSubclasses) {
-        ForEach subForEach = subclass.forEachSubclass(f, mask);
-        if (subForEach == ForEach.STOP) {
-          return subForEach;
-        }
-      }
-    }
-    return forEach;
-  }
-
   /// Returns the most specific subclass of [cls] (including [cls]) that is
   /// directly instantiated or a superclass of all directly instantiated
   /// subclasses. If [cls] is not instantiated, `null` is returned.
   ClassElement getLubOfInstantiatedSubclasses() {
     if (!isInstantiated) return null;
     if (_leastUpperInstantiatedSubclass == null) {
       _leastUpperInstantiatedSubclass =
           _computeLeastUpperInstantiatedSubclass();
     }
     return _leastUpperInstantiatedSubclass;
@@ skipping 50 matching lines @@
       if (sorted) {
         subclasses = _directSubclasses.toList()..sort((a, b) {
           return a.cls.name.compareTo(b.cls.name);
         });
       }
       bool needsComma = false;
       for (ClassHierarchyNode child in subclasses) {
         if (instantiatedOnly && !child.isInstantiated) {
           continue;
         }
-        if (withRespectTo != null &&
-            !child.anySubclass(isRelatedTo, ClassHierarchyNode.ALL)) {
+        if (withRespectTo != null && !child.subclasses().any(isRelatedTo)) {
           continue;
         }
         if (needsComma) {
           sb.write(',\n');
         } else {
           sb.write('\n');
         }
         child.printOn(
             sb,
             '$indentation  ',
@@ skipping 71 matching lines @@
 class ClassSet {
   final ClassHierarchyNode node;
   ClassElement _leastUpperInstantiatedSubtype;
 
   List<ClassHierarchyNode> _directSubtypes;
 
   ClassSet(this.node);
 
   ClassElement get cls => node.cls;
 
-  /// Returns the number of directly instantiated subtypes of [cls].
-  int get instantiatedSubtypeCount {
-    int count = node.instantiatedSubclassCount;
-    if (_directSubtypes != null) {
-      for (ClassHierarchyNode subtypeNode in _directSubtypes) {
-        if (subtypeNode.isDirectlyInstantiated) {
-          count++;
-        }
-        count += subtypeNode.instantiatedSubclassCount;
-      }
-    }
-    return count;
-  }
-
-  /// Returns `true` if all instantiated subtypes of [cls] are subclasses of
-  /// [cls].
-  bool get hasOnlyInstantiatedSubclasses {
-    if (_directSubtypes != null) {
-      for (ClassHierarchyNode subtypeNode in _directSubtypes) {
-        if (subtypeNode.isInstantiated) {
-          return false;
-        }
-      }
-    }
-    return true;
+  /// 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}) {
+    EnumSet<Instantiation> mask = ClassHierarchyNode.createMask(
+        includeDirectlyInstantiated: includeDirectlyInstantiated,
+        includeIndirectlyInstantiated:includeIndirectlyInstantiated,
+        includeUninstantiated: includeUninstantiated);
+    return subclassesByMask(mask, strict: strict);
   }
 
   /// Returns an [Iterable] of the subclasses of [cls] possibly including [cls].
   ///
   /// Subclasses are included if their instantiation properties intersect with
   /// their corresponding [Instantiation] values in [mask]. If [strict] is
   /// `true`, [cls] itself is _not_ returned.
   Iterable<ClassElement> subclassesByMask(
       EnumSet<Instantiation> mask,
       {bool strict: false}) {
@@ skipping 11 matching lines @@
        bool includeIndirectlyInstantiated: true,
        bool includeUninstantiated: true,
        bool strict: false}) {
     EnumSet<Instantiation> mask = ClassHierarchyNode.createMask(
         includeDirectlyInstantiated: includeDirectlyInstantiated,
         includeIndirectlyInstantiated:includeIndirectlyInstantiated,
         includeUninstantiated: includeUninstantiated);
     return subtypesByMask(mask, strict: strict);
   }
 
+
   /// Returns an [Iterable] of the subtypes of [cls] possibly including [cls].
   ///
   /// Subtypes are included if their instantiation properties intersect with
   /// their corresponding [Instantiation] values in [mask]. If [strict] is
   /// `true`, [cls] itself is _not_ returned.
   Iterable<ClassElement> subtypesByMask(
       EnumSet<Instantiation> mask,
       {bool strict: false}) {
     if (_directSubtypes == null) {
       return node.subclassesByMask(
           mask,
           strict: strict);
     }
 
     return new SubtypesIterable.SubtypesIterator(this,
         mask,
         includeRoot: !strict);
   }
 
-  /// Applies [predicate] to each subclass of [cls] matching the criteria
-  /// specified by [mask] and [strict]. If [predicate] returns `true` on a
-  /// class, visitation is stopped immediately and the function returns `true`.
-  ///
-  /// [predicate] is applied to subclasses if their instantiation properties
-  /// intersect with their corresponding [Instantiation] values in [mask]. If
-  /// [strict] is `true`, [predicate] is _not_ called on [cls] itself.
-  bool anySubclass(
-      bool predicate(ClassElement cls),
-      EnumSet<Instantiation> mask,
-      {bool strict: false}) {
-    return node.anySubclass(predicate, mask, strict: strict);
-  }
-
-  /// Applies [f] to each subclass of [cls] matching the criteria specified by
-  /// [mask] and [strict].
-  ///
-  /// [f] is a applied to subclasses if their instantiation properties intersect
-  /// with their corresponding [Instantiation] values in [mask]. If [strict] is
-  /// `true`, [f] is _not_ called on [cls] itself.
-  ///
-  /// The visitation of subclasses can be cut short by the return value of [f].
-  /// If [ForEach.STOP] is returned, no further classes are visited and the
-  /// function stops immediately. If [ForEach.SKIP_CHILDREN] is returned, the
-  /// subclasses of the last visited class are skipped, but visitation
-  /// continues. The return value of the function is either [ForEach.STOP], if
-  /// visitation was stopped, or [ForEach.CONTINUE] if visitation continued to
-  /// the end.
-  ForEach forEachSubclass(
-      ForEachFunction f,
-      EnumSet<Instantiation> mask,
-      {bool strict: false}) {
-    return node.forEachSubclass(f, mask, strict: strict);
-  }
-
-  /// Applies [predicate] to each subtype of [cls] matching the criteria
-  /// specified by [mask] and [strict]. If [predicate] returns `true` on a
-  /// class, visitation is stopped immediately and the function returns `true`.
-  ///
-  /// [predicate] is applied to subtypes if their instantiation properties
-  /// intersect with their corresponding [Instantiation] values in [mask]. If
-  /// [strict] is `true`, [predicate] is _not_ called on [cls] itself.
-  bool anySubtype(
-      bool predicate(ClassElement cls),
-      EnumSet<Instantiation> mask,
-      {bool strict: false}) {
-
-    ForEach wrapper(ClassElement cls) {
-      return predicate(cls) ? ForEach.STOP : ForEach.CONTINUE;
-    }
-    return forEachSubtype(wrapper, mask, strict: strict) == ForEach.STOP;
-  }
-
-  /// Applies [f] to each subtype of [cls] matching the criteria specified by
-  /// [mask] and [strict].
-  ///
-  /// [f] is a applied to subtypes if their instantiation properties intersect
-  /// with their corresponding [Instantiation] values in [mask]. If [strict] is
-  /// `true`, [f] is _not_ called on [cls] itself.
-  ///
-  /// The visitation of subtypes can be cut short by the return value of [f].
-  /// If [ForEach.STOP] is returned, no further classes are visited and the
-  /// function stops immediately. If [ForEach.SKIP_CHILDREN] is returned, the
-  /// subclasses of the last visited class are skipped, but visitation
-  /// continues. The return value of the function is either [ForEach.STOP], if
-  /// visitation was stopped, or [ForEach.CONTINUE] if visitation continued to
-  /// the end.
-  ForEach forEachSubtype(
-      ForEachFunction f,
-      EnumSet<Instantiation> mask,
-      {bool strict: false}) {
-    if (!mask.contains(Instantiation.UNINSTANTIATED) && !node.isInstantiated) {
-      // Bypass children since all are uninstantiated.
-      return ForEach.CONTINUE;
-    }
-    ForEach forEach = node.forEachSubclass(f, mask, strict: strict);
-    forEach ??= ForEach.CONTINUE;
-    if (forEach == ForEach.CONTINUE && _directSubtypes != null) {
-      for (ClassHierarchyNode subclass in _directSubtypes) {
-        ForEach subForEach = subclass.forEachSubclass(f, mask);
-        if (subForEach == ForEach.STOP) {
-          return subForEach;
-        }
-      }
-    }
-    return forEach;
-  }
-
   /// 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>[];
@@ skipping 241 matching lines @@
     }
     while (hierarchyNodes.moveNext()) {
       elements = hierarchyNodes.current.subclassesByMask(mask).iterator;
       if (elements.moveNext()) {
         return true;
       }
     }
     return false;
   }
 }
-
-/// Enum values returned from the [ForEachFunction] provided to the `forEachX`
-/// functions of [ClassHierarchyNode] and [ClassSet]. The value is used to
-/// control the continued iteration.
-enum ForEach {
-  /// Iteration continues.
-  CONTINUE,
-  /// Iteration stops immediately.
-  STOP,
-  /// Iteration skips the child classes of the current class.
-  SKIP_CHILDREN,
-}
-
-/// Visiting function used for the `forEachX` functions of [ClassHierarchyNode]
-/// and [ClassSet]. The return value controls the continued iteration. If `null`
-/// is returned, iteration continues to the end.
-typedef ForEach ForEachFunction(ClassElement cls);