Optimize subclass/subtype queries

pkg/compiler/lib/src/world.dart

 // Copyright (c) 2012, 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;
 
 import 'closure.dart' show
     SynthesizedCallMethodElementX;
 import 'common.dart';
 import 'common/backend_api.dart' show
@@ skipping 75 matching lines @@
   bool isSubtypeOf(ClassElement x, ClassElement y);
 
   /// Returns an iterable over the live classes that extend [cls] including
   /// [cls] itself.
   Iterable<ClassElement> subclassesOf(ClassElement cls);
 
   /// Returns an iterable over the live classes that extend [cls] _not_
   /// including [cls] itself.
   Iterable<ClassElement> strictSubclassesOf(ClassElement cls);
 
+  /// Returns the number of live classes that extend [cls] _not_
+  /// including [cls] itself.
+  int strictSubclassCount(ClassElement cls);
+
+  /// Applies [f] to each live class that extend [cls] _not_ including [cls]
+  /// itself.
+  void forEachStrictSubclassOf(ClassElement cls, ForEach f(ClassElement cls));
+
+  /// Returns `true` if [predicate] applies to any live class that extend [cls]
+  /// _not_ including [cls] itself.
+  bool anyStrictSubclassOf(ClassElement cls, bool predicate(ClassElement cls));
+
   /// Returns an iterable over the directly instantiated that implement [cls]
   /// possibly including [cls] itself, if it is live.
   Iterable<ClassElement> subtypesOf(ClassElement cls);
 
   /// Returns an iterable over the live classes that implement [cls] _not_
   /// including [cls] if it is live.
   Iterable<ClassElement> strictSubtypesOf(ClassElement cls);
 
+  /// Returns the number of live classes that implement [cls] _not_
+  /// including [cls] itself.
+  int strictSubtypeCount(ClassElement cls);
+
+  /// Applies [f] to each live class that implements [cls] _not_ including [cls]
+  /// itself.
+  void forEachStrictSubtypeOf(ClassElement cls, ForEach f(ClassElement cls));
+
+  /// Returns `true` if [predicate] applies to any live class that implements
+  /// [cls] _not_ including [cls] itself.
+  bool anyStrictSubtypeOf(ClassElement cls, bool predicate(ClassElement cls));
+
   /// Returns `true` if [a] and [b] have any known common subtypes.
   bool haveAnyCommonSubtypes(ClassElement a, ClassElement b);
 
   /// Returns `true` if any live class other than [cls] extends [cls].
   bool hasAnyStrictSubclass(ClassElement cls);
 
   /// Returns `true` if any live class other than [cls] implements [cls].
   bool hasAnyStrictSubtype(ClassElement cls);
 
   /// Returns `true` if all live classes that implement [cls] extend it.
@@ skipping 127 matching lines @@
 
   /// Returns an iterable over the directly instantiated classes that extend
   /// [cls] _not_ including [cls] itself.
   Iterable<ClassElement> strictSubclassesOf(ClassElement cls) {
     ClassHierarchyNode subclasses = _classHierarchyNodes[cls.declaration];
     if (subclasses == null) return const <ClassElement>[];
     return subclasses.subclassesByMask(
         ClassHierarchyNode.DIRECTLY_INSTANTIATED, strict: true);
   }
 
+  /// Returns the number of live classes that extend [cls] _not_
+  /// including [cls] itself.
+  int strictSubclassCount(ClassElement cls) {
+    ClassHierarchyNode subclasses = _classHierarchyNodes[cls.declaration];
+    if (subclasses == null) return 0;
+    return subclasses.instantiatedSubclassCount;
+  }
+
+  /// Applies [f] to each live class that extend [cls] _not_ including [cls]
+  /// itself.
+  void forEachStrictSubclassOf(ClassElement cls, ForEach f(ClassElement cls)) {
+    ClassHierarchyNode subclasses = _classHierarchyNodes[cls.declaration];
+    if (subclasses == null) return;
+    subclasses.forEachSubclass(
+        f,
+        ClassHierarchyNode.DIRECTLY_INSTANTIATED,
+        strict: true);
+  }
+
+  /// Returns `true` if [predicate] applies to any live class that extend [cls]
+  /// _not_ including [cls] itself.
+  bool anyStrictSubclassOf(ClassElement cls, bool predicate(ClassElement cls)) {
+    ClassHierarchyNode subclasses = _classHierarchyNodes[cls.declaration];
+    if (subclasses == null) return false;
+    return subclasses.anySubclass(
+        predicate,
+        ClassHierarchyNode.DIRECTLY_INSTANTIATED,
+        strict: true);
+  }
+
   /// Returns an iterable over the directly instantiated that implement [cls]
   /// possibly including [cls] itself, if it is live.
   Iterable<ClassElement> subtypesOf(ClassElement cls) {
     ClassSet classSet = _classSets[cls.declaration];
     if (classSet == null) {
       return const <ClassElement>[];
     } else {
       return classSet.subtypesByMask(ClassHierarchyNode.DIRECTLY_INSTANTIATED);
     }
   }
 
   /// Returns an iterable over the directly instantiated that implement [cls]
   /// _not_ including [cls].
   Iterable<ClassElement> strictSubtypesOf(ClassElement cls) {
     ClassSet classSet = _classSets[cls.declaration];
     if (classSet == null) {
       return const <ClassElement>[];
     } else {
       return classSet.subtypesByMask(
           ClassHierarchyNode.DIRECTLY_INSTANTIATED,
           strict: true);
     }
   }
 
+  /// Returns the number of live classes that implement [cls] _not_
+  /// including [cls] itself.
+  int strictSubtypeCount(ClassElement cls) {
+    ClassSet classSet = _classSets[cls.declaration];
+    if (classSet == null) return 0;
+    return classSet.instantiatedSubtypeCount;
+  }
+
+  /// Applies [f] to each live class that implements [cls] _not_ including [cls]
+  /// itself.
+  void forEachStrictSubtypeOf(ClassElement cls, ForEach f(ClassElement cls)) {
+    ClassSet classSet = _classSets[cls.declaration];
+    if (classSet == null) return;
+    classSet.forEachSubtype(
+        f,
+        ClassHierarchyNode.DIRECTLY_INSTANTIATED,
+        strict: true);
+  }
+
+  /// Returns `true` if [predicate] applies to any live class that extend [cls]
+  /// _not_ including [cls] itself.
+  bool anyStrictSubtypeOf(ClassElement cls, bool predicate(ClassElement cls)) {
+    ClassSet classSet = _classSets[cls.declaration];
+    if (classSet == null) return false;
+    return classSet.anySubtype(
+        predicate,
+        ClassHierarchyNode.DIRECTLY_INSTANTIATED,
+        strict: true);
+  }
+
   /// Returns `true` if [a] and [b] have any known common subtypes.
   bool haveAnyCommonSubtypes(ClassElement a, ClassElement b) {
     ClassSet classSetA = _classSets[a.declaration];
     ClassSet classSetB = _classSets[b.declaration];
     if (classSetA == null || classSetB == null) return false;
     // TODO(johnniwinther): Implement an optimized query on [ClassSet].
     Set<ClassElement> subtypesOfB = classSetB.subtypes().toSet();
     for (ClassElement subtypeOfA in classSetA.subtypes()) {
       if (subtypesOfB.contains(subtypeOfA)) {
         return true;
       }
     }
     return false;
   }
 
   /// Returns `true` if any directly instantiated class other than [cls] extends
   /// [cls].
   bool hasAnyStrictSubclass(ClassElement cls) {
     ClassHierarchyNode subclasses = _classHierarchyNodes[cls.declaration];
     if (subclasses == null) return false;
     return subclasses.isIndirectlyInstantiated;
   }
 
   /// Returns `true` if any directly instantiated class other than [cls]
   /// implements [cls].
   bool hasAnyStrictSubtype(ClassElement cls) {
-    return !strictSubtypesOf(cls).isEmpty;
+    return strictSubtypeCount(cls) > 0;
   }
 
   /// Returns `true` if all directly instantiated classes that implement [cls]
   /// extend it.
   bool hasOnlySubclasses(ClassElement cls) {
     // TODO(johnniwinther): move this to ClassSet?
     if (cls == objectClass) return true;
-    Iterable<ClassElement> subtypes = strictSubtypesOf(cls);
-    if (subtypes == null) return true;
-    Iterable<ClassElement> subclasses = strictSubclassesOf(cls);
-    return subclasses != null && (subclasses.length == subtypes.length);
+    ClassSet classSet = _classSets[cls.declaration];
+    if (classSet == null) {
+      // Vacuously true.
+      return true;
+    }
+    return classSet.hasOnlyInstantiatedSubclasses;
   }
 
   @override
   ClassElement getLubOfInstantiatedSubclasses(ClassElement cls) {
     ClassHierarchyNode hierarchy = _classHierarchyNodes[cls.declaration];
     return hierarchy != null
         ? hierarchy.getLubOfInstantiatedSubclasses() : null;
   }
 
   @override
@@ skipping 171 matching lines @@
   ///
   /// This method is only provided for testing. For queries on classes, use the
   /// methods defined in [ClassWorld].
   ClassHierarchyNode getClassHierarchyNode(ClassElement cls) {
     return _classHierarchyNodes[cls.declaration];
   }
 
   ClassHierarchyNode _ensureClassHierarchyNode(ClassElement cls) {
     cls = cls.declaration;
     return _classHierarchyNodes.putIfAbsent(cls, () {
-      ClassHierarchyNode node = new ClassHierarchyNode(cls);
+      ClassHierarchyNode parentNode;
       if (cls.superclass != null) {
-        _ensureClassHierarchyNode(cls.superclass).addDirectSubclass(node);
+        parentNode = _ensureClassHierarchyNode(cls.superclass);
       }
-      return node;
+      return new ClassHierarchyNode(parentNode, cls);
     });
   }
 
   /// Returns [ClassSet] for [cls] used to model the extends and implements
   /// relations of known classes.
   ///
   /// This method is only provided for testing. For queries on classes, use the
   /// methods defined in [ClassWorld].
   ClassSet getClassSet(ClassElement cls) {
     return _classSets[cls.declaration];
   }
 
   ClassSet _ensureClassSet(ClassElement cls) {
     cls = cls.declaration;
     return _classSets.putIfAbsent(cls, () {
       ClassHierarchyNode node = _ensureClassHierarchyNode(cls);
       ClassSet classSet = new ClassSet(node);
 
       for (InterfaceType type in cls.allSupertypes) {
         // TODO(johnniwinther): Optimization: Avoid adding [cls] to
         // superclasses.
         ClassSet subtypeSet = _ensureClassSet(type.element);
         subtypeSet.addSubtype(node);
       }
       return classSet;
     });
   }
 
+  void _updateSuperClassHierarchyNodeForClass(ClassHierarchyNode node) {
+    // Ensure that classes implicitly implementing `Function` are in its
+    // subtype set.
+    ClassElement cls = node.cls;
+    if (cls != coreClasses.functionClass &&
+        cls.implementsFunction(coreClasses)) {
+      ClassSet subtypeSet = _ensureClassSet(coreClasses.functionClass);
+      subtypeSet.addSubtype(node);
+    }
+    if (!node.isInstantiated && node.parentNode != null) {
+      _updateSuperClassHierarchyNodeForClass(node.parentNode);
+    }
+  }
+
   void _updateClassHierarchyNodeForClass(
       ClassElement cls,
-      {bool directlyInstantiated: false,
-       bool indirectlyInstantiated: false}) {
+      {bool directlyInstantiated: false}) {
     ClassHierarchyNode node = getClassHierarchyNode(cls);
-    bool changed = false;
-    if (directlyInstantiated && !node.isDirectlyInstantiated) {
+    _updateSuperClassHierarchyNodeForClass(node);
+    if (directlyInstantiated) {
       node.isDirectlyInstantiated = true;
-      changed = true;
-    }
-    if (indirectlyInstantiated && !node.isIndirectlyInstantiated) {
-      node.isIndirectlyInstantiated = true;
-      changed = true;
-    }
-    if (changed && cls.superclass != null) {
-      _updateClassHierarchyNodeForClass(
-          cls.superclass, indirectlyInstantiated: true);
-    }
-    // Ensure that classes implicitly implementing `Function` are in its
-    // subtype set.
-    if (cls != coreClasses.functionClass &&
-        cls.implementsFunction(compiler)) {
-      ClassSet subtypeSet = _ensureClassSet(coreClasses.functionClass);
-      subtypeSet.addSubtype(node);
     }
   }
 
   void populate() {
     /// Updates the `isDirectlyInstantiated` and `isIndirectlyInstantiated`
     /// properties of the [ClassHierarchyNode] for [cls].
 
     void addSubtypes(ClassElement cls) {
       if (compiler.hasIncrementalSupport && !alreadyPopulated.add(cls)) {
         return;
@@ skipping 178 matching lines @@
     // function expressions's element.
     // TODO(herhut): Generate classes for function expressions earlier.
     if (element is SynthesizedCallMethodElementX) {
       return getMightBePassedToApply(element.expression);
     }
     return functionsThatMightBePassedToApply.contains(element);
   }
 
   bool get hasClosedWorldAssumption => !compiler.hasIncrementalSupport;
 }