Add ClassSet to support ClassWorld.strictSubtypesOf

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/backend_api.dart' show
     Backend;
@@ skipping 167 matching lines @@
   /// Returns `true` if [cls] is instantiated.
   bool isInstantiated(ClassElement cls) {
     return compiler.resolverWorld.isInstantiated(cls);
   }
 
   /// Returns an iterable over the directly instantiated classes that extend
   /// [cls] possibly including [cls] itself, if it is live.
   Iterable<ClassElement> subclassesOf(ClassElement cls) {
     ClassHierarchyNode hierarchy = _classHierarchyNodes[cls.declaration];
     if (hierarchy == null) return const <ClassElement>[];
-    assert(invariant(cls, isInstantiated(cls.declaration),
-        message: 'Class $cls has not been instantiated.'));
-    return hierarchy.subclasses();
+    return hierarchy.subclasses(
+        includeIndirectlyInstantiated: false,
+        includeUninstantiated: false);
   }
 
   /// 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();
+    return subclasses.subclasses(
+        strict: true,
+        includeIndirectlyInstantiated: false,
+        includeUninstantiated: false);
   }
 
   /// Returns an iterable over the directly instantiated that implement [cls]
   /// _not_ including [cls].
   Iterable<ClassElement> strictSubtypesOf(ClassElement cls) {
-    Set<ClassElement> subtypes = _subtypes[cls.declaration];
-    return subtypes != null ? subtypes : const <ClassElement>[];
+    ClassSet classSet = _classSets[cls.declaration];
+    if (classSet == null) {
+      return const <ClassElement>[];
+    } else {
+      return classSet.subtypes(
+          strict: true,
+          includeIndirectlyInstantiated: false,
+          includeUninstantiated: 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;
-    assert(invariant(cls, isInstantiated(cls.declaration),
-        message: 'Class $cls has not been instantiated.'));
     return subclasses.isIndirectlyInstantiated;
   }
 
   /// Returns `true` if any directly instantiated class other than [cls]
   /// implements [cls].
   bool hasAnyStrictSubtype(ClassElement cls) {
     return !strictSubtypesOf(cls).isEmpty;
   }
 
   /// Returns `true` if all directly instantiated classes that implement [cls]
@@ skipping 104 matching lines @@
       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, ClassHierarchyNode> _classHierarchyNodes =
       <ClassElement, ClassHierarchyNode>{};
-  final Map<ClassElement, Set<ClassElement>> _subtypes =
-      new Map<ClassElement, Set<ClassElement>>();
+  final Map<ClassElement, ClassSet> _classSets =
+        <ClassElement, ClassSet>{};
 
   final Set<Element> sideEffectsFreeElements = new Set<Element>();
 
   final Set<Element> elementsThatCannotThrow = new Set<Element>();
 
   final Set<Element> functionsThatMightBePassedToApply =
       new Set<FunctionElement>();
 
   final Set<Element> alreadyPopulated;
 
@@ skipping 11 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];
+  /// Called to add [cls] to the set of known classes.
+  ///
+  /// This ensures that class hierarchy queries can be performed on [cls] and
+  /// classes that extend or implement it.
+  void registerClass(ClassElement cls) {
+    _ensureClassSet(cls);
+  }
+
+  /// Returns [ClassHierarchyNode] for [cls] used to model the class hierarchies
+  /// of known classes.
+  ///
+  /// 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);
+      if (cls.superclass != null) {
+        _ensureClassHierarchyNode(cls.superclass).addDirectSubclass(node);
+      }
+      return node;
+    });
+  }
+
+  /// 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 populate() {
-
-    /// 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 createClassHierarchyNodeForClass(
+    /// Updates the `isDirectlyInstantiated` and `isIndirectlyInstantiated`
+    /// properties of the [ClassHierarchyNode] for [cls].
+    void updateClassHierarchyNodeForClass(
         ClassElement cls,
         {bool directlyInstantiated: false,
          bool indirectlyInstantiated: false}) {
-      assert(isInstantiated(cls));
-
-      ClassHierarchyNode node = _classHierarchyNodes.putIfAbsent(cls, () {
-        ClassHierarchyNode node = new ClassHierarchyNode(cls);
-        if (cls.superclass != null) {
-          createClassHierarchyNodeForClass(cls.superclass,
-              indirectlyInstantiated:
-                directlyInstantiated || indirectlyInstantiated)
-              .addDirectSubclass(node);
-        }
-        return node;
-      });
-      if (directlyInstantiated) {
+      assert(!directlyInstantiated || isInstantiated(cls));
+      ClassHierarchyNode node = getClassHierarchyNode(cls);
+      bool changed = false;
+      if (directlyInstantiated && !node.isDirectlyInstantiated) {
         node.isDirectlyInstantiated = true;
+        changed = true;
       }
-      if (indirectlyInstantiated) {
+      if (indirectlyInstantiated && !node.isIndirectlyInstantiated) {
         node.isIndirectlyInstantiated = true;
+        changed = true;
       }
-      return node;
+      if (changed && cls.superclass != null) {
+        updateClassHierarchyNodeForClass(
+            cls.superclass, indirectlyInstantiated: true);
+      }
     }
 
     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.');
       }
 
-      createClassHierarchyNodeForClass(cls, directlyInstantiated: true);
-
-      for (DartType type in cls.allSupertypes) {
-        Set<Element> subtypesOfSupertype =
-            _subtypes.putIfAbsent(type.element, () => new Set<ClassElement>());
-        subtypesOfSupertype.add(cls);
-      }
+      updateClassHierarchyNodeForClass(cls, directlyInstantiated: true);
 
       // Walk through the superclasses, and record the types
       // implemented by that type on the superclasses.
       ClassElement superclass = cls.superclass;
       while (superclass != null) {
         Set<Element> typesImplementedBySubclassesOfCls =
             _typesImplementedBySubclasses.putIfAbsent(
                 superclass, () => new Set<ClassElement>());
         for (DartType current in cls.allSupertypes) {
           typesImplementedBySubclassesOfCls.add(current.element);
@@ skipping 149 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;
 }