Add SubclassNode to prepare for optimized queries on ClassWorld.

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.
 
 part of dart2js;
 
 abstract class ClassWorld {
   // TODO(johnniwinther): Refine this into a `BackendClasses` interface.
   Backend get backend;
 
@@ skipping 28 matching lines @@
   /// Returns `true` if the class world is closed.
   bool get isClosed;
 
   /// Return `true` if [x] is a subclass of [y].
   bool isSubclassOf(ClassElement x, ClassElement y);
 
   /// Returns `true` if [x] is a subtype of [y], that is, if [x] implements an
   /// instance of [y].
   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 an iterable over the live classes that implement [cls] _not_
   /// including [cls] if it is live.
   Iterable<ClassElement> strictSubtypesOf(ClassElement cls);
 
   /// Returns `true` if any live class other than [cls] extends [cls].
   bool hasAnyStrictSubclass(ClassElement cls);
@@ skipping 79 matching lines @@
       x = x.superclass;
     }
     return false;
   }
 
   /// Returns `true` if [cls] is instantiated.
   bool isInstantiated(ClassElement cls) {
     return compiler.resolverWorld.isInstantiated(cls);
   }
 
-  /// Returns an iterable over the live classes that extend [cls] _not_
-  /// including [cls] itself.
-  Iterable<ClassElement> strictSubclassesOf(ClassElement cls) {
-    Set<ClassElement> subclasses = _subclasses[cls.declaration];
+  /// Returns an iterable over the directly instantiated classes that extend
+  /// [cls] possibly including [cls] itself.
+  Iterable<ClassElement> subclassesOf(ClassElement cls) {
+    SubclassNode subclasses = _subclassNodes[cls.declaration];
     if (subclasses == null) return const <ClassElement>[];
     assert(invariant(cls, isInstantiated(cls.declaration),
         message: 'Class $cls has not been instantiated.'));
-    return subclasses;
+    return subclasses.subclasses();
   }
 
-  /// Returns an iterable over the live classes that implement [cls] _not_
-  /// including [cls] if it is live.
+  /// Returns an iterable over the directly instantiated classes that extend
+  /// [cls] _not_ including [cls] itself.
+  Iterable<ClassElement> strictSubclassesOf(ClassElement cls) {
+    SubclassNode subclasses = _subclassNodes[cls.declaration];
+    if (subclasses == null) return const <ClassElement>[];
+    assert(invariant(cls, isInstantiated(cls.declaration),
+        message: 'Class $cls has not been instantiated.'));
+    return subclasses.strictSubclasses();
+  }
+
+  /// Returns an iterable over the directly instantiated that implement [cls]
+  /// _not_ including [cls] if it is live.
   Iterable<ClassElement> strictSubtypesOf(ClassElement cls) {
     Set<ClassElement> subtypes = _subtypes[cls.declaration];
     return subtypes != null ? subtypes : const <ClassElement>[];
   }
 
-  /// Returns `true` if any live class other than [cls] extends [cls].
+  /// Returns `true` if any directly instantiated class other than [cls] extends
+  /// [cls].
   bool hasAnyStrictSubclass(ClassElement cls) {
-    return !strictSubclassesOf(cls).isEmpty;
+    SubclassNode subclasses = _subclassNodes[cls.declaration];
+    if (subclasses == null) return false;
+    assert(invariant(cls, isInstantiated(cls.declaration),
+        message: 'Class $cls has not been instantiated.'));
+    return subclasses.isIndirectlyInstantiated;
   }
 
-  /// Returns `true` if any live class other than [cls] implements [cls].
+  /// Returns `true` if any directly instantiated class other than [cls]
+  /// implements [cls].
   bool hasAnyStrictSubtype(ClassElement cls) {
     return !strictSubtypesOf(cls).isEmpty;
   }
 
-  /// Returns `true` if all live classes that implement [cls] extend it.
+  /// Returns `true` if all directly instantiated classes that implement [cls]
+  /// extend it.
   bool hasOnlySubclasses(ClassElement cls) {
     Iterable<ClassElement> subtypes = strictSubtypesOf(cls);
     if (subtypes == null) return true;
     Iterable<ClassElement> subclasses = strictSubclassesOf(cls);
     return subclasses != null && (subclasses.length == subtypes.length);
   }
 
   /// Returns an iterable over the common supertypes of the [classes].
   Iterable<ClassElement> commonSupertypesOf(Iterable<ClassElement> classes) {
     Iterator<ClassElement> iterator = classes.iterator;
@@ skipping 91 matching lines @@
 
   final Map<ClassElement, List<MixinApplicationElement>> _mixinUses =
       new Map<ClassElement, List<MixinApplicationElement>>();
   Map<ClassElement, List<MixinApplicationElement>> _liveMixinUses;
 
   final Map<ClassElement, Set<ClassElement>> _typesImplementedBySubclasses =
       new Map<ClassElement, Set<ClassElement>>();
 
   // We keep track of subtype and subclass relationships in four
   // distinct sets to make class hierarchy analysis faster.
-  final Map<ClassElement, Set<ClassElement>> _subclasses =
-      new Map<ClassElement, Set<ClassElement>>();
+  final Map<ClassElement, SubclassNode> _subclassNodes =
+      <ClassElement, SubclassNode>{};
   final Map<ClassElement, Set<ClassElement>> _subtypes =
       new Map<ClassElement, Set<ClassElement>>();
 
   final Set<Element> sideEffectsFreeElements = new Set<Element>();
 
   final Set<Element> elementsThatCannotThrow = new Set<Element>();
 
   final Set<Element> functionsThatMightBePassedToApply =
       new Set<FunctionElement>();
 
@@ skipping 13 matching lines @@
 
   Set<ClassElement> typesImplementedBySubclassesOf(ClassElement cls) {
     return _typesImplementedBySubclasses[cls.declaration];
   }
 
   World(Compiler compiler)
       : allFunctions = new FunctionSet(compiler),
         this.compiler = compiler,
         alreadyPopulated = compiler.cacheStrategy.newSet();
 
+  SubclassNode subclassNode(ClassElement cls) {
+    return _subclassNodes[cls];
+  }
+
+  /// Ensure that a [SubclassNode] exists for [cls]. Updates the
+  /// `isDirectlyInstantiated` and `isIndirectlyInstantiated` property of the
+  /// node according the provided arguments and returns the node.
+  SubclassNode createNodeForClass(ClassElement cls,

[Siggi Cherem (dart-lang), 2015/07/14 23:51:07]

nit, rename to: `ensureNodeForClass` (that helps convey that the boolean
properties might be updated).

+                                  {bool directlyInstantiated: false,
+                                   bool indirectlyInstantiated: false}) {
+    SubclassNode node = _subclassNodes.putIfAbsent(cls, () {
+      SubclassNode node = new SubclassNode(cls);
+      if (cls.superclass != null) {
+        createNodeForClass(cls.superclass,
+            indirectlyInstantiated:
+              directlyInstantiated || indirectlyInstantiated)
+            .addDirectSubclass(node);
+      }
+      return node;
+    });
+    if (directlyInstantiated) {
+      node.isDirectlyInstantiated = true;
+    }
+    if (indirectlyInstantiated) {
+      node.isIndirectlyInstantiated = true;
+    }
+    return node;
+  }
+
   void populate() {
+
     void addSubtypes(ClassElement cls) {
       if (compiler.hasIncrementalSupport && !alreadyPopulated.add(cls)) {
         return;
       }
       assert(cls.isDeclaration);
       if (!cls.isResolved) {
         compiler.internalError(cls, 'Class "${cls.name}" is not resolved.');
       }
 
+      createNodeForClass(cls, directlyInstantiated: true);
+
       for (DartType type in cls.allSupertypes) {
         Set<Element> subtypesOfSupertype =
             _subtypes.putIfAbsent(type.element, () => new Set<ClassElement>());
         subtypesOfSupertype.add(cls);
       }
 
       // Walk through the superclasses, and record the types
       // implemented by that type on the superclasses.
       ClassElement superclass = cls.superclass;
       while (superclass != null) {
-        Set<Element> subclassesOfSuperclass =
-            _subclasses.putIfAbsent(superclass, () => new Set<ClassElement>());
-        subclassesOfSuperclass.add(cls);
-
         Set<Element> typesImplementedBySubclassesOfCls =
             _typesImplementedBySubclasses.putIfAbsent(
                 superclass, () => new Set<ClassElement>());
         for (DartType current in cls.allSupertypes) {
           typesImplementedBySubclassesOfCls.add(current.element);
         }
         superclass = superclass.superclass;
       }
     }
 
@@ skipping 144 matching lines @@
     // function expressions's element.
     // TODO(herhut): Generate classes for function expressions earlier.
     if (element is closureMapping.SynthesizedCallMethodElementX) {
       return getMightBePassedToApply(element.expression);
     }
     return functionsThatMightBePassedToApply.contains(element);
   }
 
   bool get hasClosedWorldAssumption => !compiler.hasIncrementalSupport;
 }