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

sdk/lib/_internal/compiler/implementation/world.dart

Index: sdk/lib/_internal/compiler/implementation/world.dart
diff --git a/sdk/lib/_internal/compiler/implementation/world.dart b/sdk/lib/_internal/compiler/implementation/world.dart
index a09f62967aaa8608a2da88bdbf03e330f62f9f36..8b737bf3057520084a2c77f7a564c2258a17aff3 100644
--- a/sdk/lib/_internal/compiler/implementation/world.dart
+++ b/sdk/lib/_internal/compiler/implementation/world.dart
@@ -6,16 +6,25 @@ 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>(),
@@ -31,18 +40,28 @@ class World {
       }
 
       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);
         }
@@ -113,6 +132,22 @@ class World {
     });
   }
 
+  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 =