Add superclasses, subclasses, and subtypes tracking to the world.

sdk/lib/_internal/compiler/implementation/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;
 
 class World {
   final Compiler compiler;
-  final Map<ClassElement, Set<ClassElement>> subtypes;
   final Map<ClassElement, Set<MixinApplicationElement>> mixinUses;
   final Map<ClassElement, Set<ClassElement>> typesImplementedBySubclasses;
   final Set<ClassElement> classesNeedingRti;
   final Map<ClassElement, Set<ClassElement>> rtiDependencies;
   final FullFunctionSet allFunctions;
 
+  // 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, Set<ClassElement>> superclasses =
+      new Map<ClassElement, Set<ClassElement>>();
+  final Map<ClassElement, Set<ClassElement>> subtypes =
+      new Map<ClassElement, Set<ClassElement>>();
+  final Map<ClassElement, Set<ClassElement>> supertypes =
+      new Map<ClassElement, Set<ClassElement>>();
+
   World(Compiler compiler)
-      : subtypes = new Map<ClassElement, Set<ClassElement>>(),
-        mixinUses = new Map<ClassElement, Set<MixinApplicationElement>>(),
+      : mixinUses = new Map<ClassElement, Set<MixinApplicationElement>>(),
         typesImplementedBySubclasses =
             new Map<ClassElement, Set<ClassElement>>(),
         classesNeedingRti = new Set<ClassElement>(),
         rtiDependencies = new Map<ClassElement, Set<ClassElement>>(),
         allFunctions = new FullFunctionSet(compiler),
         this.compiler = compiler;
 
   void populate() {
     void addSubtypes(ClassElement cls) {
       if (cls.resolutionState != STATE_DONE) {
         compiler.internalErrorOnElement(
             cls, 'Class "${cls.name.slowToString()}" is not resolved.');
       }
 
       for (DartType type in cls.allSupertypes) {
-        Set<Element> subtypesOfCls =
-          subtypes.putIfAbsent(type.element, () => new Set<ClassElement>());
-        subtypesOfCls.add(cls);
+        Set<Element> supertypesOfClass =
+            supertypes.putIfAbsent(cls, () => new Set<ClassElement>());
+        Set<Element> subtypesOfSupertype =
+            subtypes.putIfAbsent(type.element, () => new Set<ClassElement>());
+        supertypesOfClass.add(type.element);
+        subtypesOfSupertype.add(cls);
       }
 
       // Walk through the superclasses, and record the types
       // implemented by that type on the superclasses.
       DartType type = cls.supertype;
       while (type != null) {
+        Set<Element> superclassesOfClass =
+            superclasses.putIfAbsent(cls, () => new Set<ClassElement>());
+        Set<Element> subclassesOfSuperclass =
+            subclasses.putIfAbsent(type.element, () => new Set<ClassElement>());
+        superclassesOfClass.add(type.element);
+        subclassesOfSuperclass.add(cls);
+
         Set<Element> typesImplementedBySubclassesOfCls =
-          typesImplementedBySubclasses.putIfAbsent(
-              type.element, () => new Set<ClassElement>());
+            typesImplementedBySubclasses.putIfAbsent(
+                type.element, () => new Set<ClassElement>());
         for (DartType current in cls.allSupertypes) {
           typesImplementedBySubclassesOfCls.add(current.element);
         }
         ClassElement classElement = type.element;
         type = classElement.supertype;
       }
     }
 
     // Use the [:seenClasses:] set to include non-instantiated
     // classes: if the superclass of these classes require RTI, then
@@ skipping 50 matching lines @@
         if (!itf.isRaw) {
           potentiallyAddForRti(itf.element);
         }
       } else if (type.kind == TypeKind.TYPE_VARIABLE) {
         TypeVariableElement variable = type.element;
         potentiallyAddForRti(variable.enclosingElement);
       }
     });
   }
 
+  Iterable<ClassElement> commonSupertypesOf(ClassElement x, ClassElement y) {

[ngeoffray, 2013/03/05 15:05:50]

Please add a comment on why you're not using Set.intersection.

+    Set<ClassElement> xSet = supertypes[x];
+    if (xSet == null) return const <ClassElement>[];
+    Set<ClassElement> ySet = supertypes[y];
+    if (ySet == null) return const <ClassElement>[];
+    Set<ClassElement> smallSet, largeSet;
+    if (xSet.length <= ySet.length) {
+      smallSet = xSet;
+      largeSet = ySet;
+    } else {
+      smallSet = ySet;
+      largeSet = xSet;
+    }
+    return smallSet.where((ClassElement each) => largeSet.contains(each));
+  }
+
   void registerMixinUse(MixinApplicationElement mixinApplication,
                         ClassElement mixin) {
     Set<MixinApplicationElement> users =
         mixinUses.putIfAbsent(mixin, () =>
                               new Set<MixinApplicationElement>());
     users.add(mixinApplication);
   }
 
   bool isUsedAsMixin(ClassElement cls) {
     Set<MixinApplicationElement> uses = mixinUses[cls];
@@ skipping 69 matching lines @@
     if (mask != null) {
       noSuchMethodSelector = new TypedSelector(mask, noSuchMethodSelector);
     }
     ClassElement objectClass = compiler.objectClass;
     return allFunctions
         .filter(noSuchMethodSelector)
         .map((Element member) => member.getEnclosingClass())
         .where((ClassElement holder) => !identical(holder, objectClass));
   }
 }