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.

[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;
+    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) {
+    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.strictSubclasses();
+  }
+
+  /// 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;
     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, ClassHierarchyNode> _classHierarchyNodes =
+      <ClassElement, ClassHierarchyNode>{};
   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();
 
+  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;
       }
       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;
 }