Add SubclassNode to prepare for optimized queries on ClassWorld.

pkg/compiler/lib/src/world.dart

Index: pkg/compiler/lib/src/world.dart
diff --git a/pkg/compiler/lib/src/world.dart b/pkg/compiler/lib/src/world.dart
index b4d78dd860c647d5ae058451f3deb9e5b93a5f38..56ef969656ca6f707c944b2e6ced3c6debc11ec9 100644
--- a/pkg/compiler/lib/src/world.dart
+++ b/pkg/compiler/lib/src/world.dart
@@ -46,6 +46,10 @@ abstract class ClassWorld {
   /// 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);
@@ -145,34 +149,51 @@ class World implements ClassWorld {
     return compiler.resolverWorld.isInstantiated(cls);
   }
 
-  /// Returns an iterable over the live classes that extend [cls] _not_
-  /// including [cls] itself.
+  /// Returns an iterable over the directly instantiated classes that extend
+  /// [cls] possibly including [cls] itself.

[karlklose, 2015/07/21 12:47:21]

Maybe extend to '... including [cls] itself, if it live.'

[Johnni Winther, 2015/07/21 14:22:00]

Done.

+  Iterable<ClassElement> subclassesOf(ClassElement cls) {
+    ClassHierarchyNode subclasses = _classHierarchyNodes[cls.declaration];

[karlklose, 2015/07/21 12:47:21]

'subclasses' -> 'hierarchy'?

[Johnni Winther, 2015/07/21 14:22:01]

Done.

+    if (subclasses == null) return const <ClassElement>[];
+    assert(invariant(cls, isInstantiated(cls.declaration),
+        message: 'Class $cls has not been instantiated.'));
+    return subclasses.subclasses();
+  }
+
+  /// Returns an iterable over the directly instantiated classes that extend
+  /// [cls] _not_ including [cls] itself.
   Iterable<ClassElement> strictSubclassesOf(ClassElement cls) {
-    Set<ClassElement> subclasses = _subclasses[cls.declaration];
+    ClassHierarchyNode subclasses = _classHierarchyNodes[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.strictSubclasses();
   }
 
-  /// Returns an iterable over the live classes that implement [cls] _not_
-  /// including [cls] if it is live.
+  /// Returns an iterable over the directly instantiated that implement [cls]
+  /// _not_ including [cls] if it is live.

[karlklose, 2015/07/21 12:47:21]

Remove 'if it is live', it is implied.

[Johnni Winther, 2015/07/21 14:22:00]

Done.

   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;
+    ClassHierarchyNode subclasses = _classHierarchyNodes[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;
@@ -284,8 +305,8 @@ class World implements ClassWorld {
 
   // 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, ClassHierarchyNode> _classHierarchyNodes =
+      <ClassElement, ClassHierarchyNode>{};
   final Map<ClassElement, Set<ClassElement>> _subtypes =
       new Map<ClassElement, Set<ClassElement>>();
 
@@ -319,7 +340,38 @@ class World implements ClassWorld {
         this.compiler = compiler,
         alreadyPopulated = compiler.cacheStrategy.newSet();
 
+  ClassHierarchyNode classHierarchyNode(ClassElement cls) {
+    return _classHierarchyNodes[cls];
+  }
+
+  /// Ensure that a [ClassHierarchyNode] exists for [cls]. Updates the
+  /// `isDirectlyInstantiated` and `isIndirectlyInstantiated` property of the
+  /// node according the provided arguments and returns the node.
+  ClassHierarchyNode createNodeForClass(

[karlklose, 2015/07/21 12:47:21]

'create[Class]HierarchyNodeForClass'?

[Johnni Winther, 2015/07/21 14:22:01]

Done.

+      ClassElement cls,
+      {bool directlyInstantiated: false,
+       bool indirectlyInstantiated: false}) {
+    ClassHierarchyNode node = _classHierarchyNodes.putIfAbsent(cls, () {
+      ClassHierarchyNode node = new ClassHierarchyNode(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;

[karlklose, 2015/07/21 12:47:21]

Is there a contract to only call this method for a class that is eitehr directly
or indirectly instantiated? Then please add an assert.

Otherwise, we can have the situation, that we call it with both booleans false
first, which creates the node for the superclass with
indirectlyInstantiated=false and later updates would not change the flag of the
superclass.

[Johnni Winther, 2015/07/21 14:22:00]

Moved into [populate] and assertion added.

+  }
+
   void populate() {
+
     void addSubtypes(ClassElement cls) {
       if (compiler.hasIncrementalSupport && !alreadyPopulated.add(cls)) {
         return;
@@ -329,6 +381,8 @@ class World implements ClassWorld {
         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>());
@@ -339,10 +393,6 @@ class World implements ClassWorld {
       // 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>());