Implement IncrementalClassHierarchy.getRankedSuperclasses().

pkg/kernel/lib/src/incremental_class_hierarchy.dart

Index: pkg/kernel/lib/src/incremental_class_hierarchy.dart
diff --git a/pkg/kernel/lib/src/incremental_class_hierarchy.dart b/pkg/kernel/lib/src/incremental_class_hierarchy.dart
index cb1696e9b5eadd298634bcc39c17f2382a17de94..bdca807d4ca06740978362fe52f538992cc66f02 100644
--- a/pkg/kernel/lib/src/incremental_class_hierarchy.dart
+++ b/pkg/kernel/lib/src/incremental_class_hierarchy.dart
@@ -7,9 +7,13 @@ import 'dart:math';
 
 import 'package:kernel/ast.dart';
 import 'package:kernel/class_hierarchy.dart';
+import 'package:kernel/src/heap.dart';
 
 /// Lazy and incremental implementation of [ClassHierarchy].
 class IncrementalClassHierarchy implements ClassHierarchy {
+  /// The next unique identifier for [_ClassInfo]s.
+  int _nextId = 0;
+
   /// The mapping from [Class]es to the corresponding [_ClassInfo]s.
   /// It is filled lazily as the client requests information about classes.
   final Map<Class, _ClassInfo> _info = {};
@@ -35,22 +39,7 @@ class IncrementalClassHierarchy implements ClassHierarchy {
 
   @override
   int getClassDepth(Class node) {
-    var info = _getInfo(node);
-    if (info.depth < 0) {
-      int superDepth = -1;
-      if (node.supertype != null) {
-        superDepth = max(superDepth, getClassDepth(node.supertype.classNode));
-      }
-      if (node.mixedInType != null) {
-        superDepth = max(superDepth, getClassDepth(node.mixedInType.classNode));
-      }
-      for (var supertype in node.implementedTypes) {
-        superDepth = max(superDepth, getClassDepth(supertype.classNode));
-      }
-      info.depth = superDepth + 1;
-    }
-
-    return info.depth;
+    return _getInfo(node).depth;
   }
 
   @override
@@ -61,9 +50,8 @@ class IncrementalClassHierarchy implements ClassHierarchy {
   }
 
   @override
-  int getClassIndex(Class class_) {
-    // TODO(scheglov): implement getClassIndex
-    throw new UnimplementedError();
+  int getClassIndex(Class node) {
+    return _getInfo(node).id;
   }
 
   @override
@@ -79,9 +67,9 @@ class IncrementalClassHierarchy implements ClassHierarchy {
   }
 
   @override
-  List<Class> getRankedSuperclasses(Class class_) {
-    // TODO(scheglov): implement getRankedSuperclasses
-    throw new UnimplementedError();
+  List<Class> getRankedSuperclasses(Class node) {
+    var info = _getInfo(node);
+    return _getRankedSuperclassList(info).map((info) => info.node).toList();
   }
 
   @override
@@ -98,17 +86,95 @@ class IncrementalClassHierarchy implements ClassHierarchy {
 
   /// Return the [_ClassInfo] for the [node].
   _ClassInfo _getInfo(Class node) {
-    return _info.putIfAbsent(node, () => new _ClassInfo(node));
+    var info = _info[node];
+    if (info == null) {
+      info = new _ClassInfo(_nextId++, node);
+      _info[node] = info;
+
+      int superDepth = -1;
+      if (node.supertype != null) {
+        var superInfo = _getInfo(node.supertype.classNode);
+        superDepth = max(superDepth, superInfo.depth);
+      }
+      if (node.mixedInType != null) {
+        var mixedInfo = _getInfo(node.mixedInType.classNode);
+        superDepth = max(superDepth, mixedInfo.depth);
+      }
+      for (var supertype in node.implementedTypes) {
+        var implementedInfo = _getInfo(supertype.classNode);
+        superDepth = max(superDepth, implementedInfo.depth);
+      }
+      info.depth = superDepth + 1;
+    }
+    return info;
+  }
+
+  List<_ClassInfo> _getRankedSuperclassList(_ClassInfo info) {
+    if (info.rankedSuperclassList != null) {
+      return info.rankedSuperclassList;
+    }
+
+    var heap = new _LubHeap()..add(info);
+    var chain = <_ClassInfo>[];
+    info.rankedSuperclassList = chain;
+
+    _ClassInfo lastInfo = null;
+    while (heap.isNotEmpty) {
+      var nextInfo = heap.remove();
+      if (identical(nextInfo, lastInfo)) continue;
+      lastInfo = nextInfo;
+
+      chain.add(nextInfo);
+
+      void addToHeap(Supertype supertype) {
+        var superInfo = _getInfo(supertype.classNode);
+        heap.add(superInfo);
+      }
+
+      var classNode = nextInfo.node;
+      if (classNode.supertype != null) addToHeap(classNode.supertype);
+      if (classNode.mixedInType != null) addToHeap(classNode.mixedInType);
+      classNode.implementedTypes.forEach(addToHeap);
+    }
+    return chain;
   }
 }
 
 /// Information about a [Class].
 class _ClassInfo {
+  /// The unique identifier of the [_ClassInfo].
+  final int id;
+
+  /// The [Class] node described by this [_ClassInfo].
   final Class node;
 
   /// The number of steps in the longest inheritance path from the class
-  /// to [Object], or -1 if the depth has not been computed yet.
+  /// to [Object], or `-1` if the depth has not been computed yet.
   int depth = -1;
 
-  _ClassInfo(this.node);
+  /// The list of superclasses sorted by depth (descending order) and
+  /// unique identifiers (ascending order), or `null` if the lit has not
+  /// been computed yet.
+  List<_ClassInfo> rankedSuperclassList;
+
+  _ClassInfo(this.id, this.node);
+
+  @override
+  String toString() => node.toString();
+}
+
+/// Heap for use in computing least upper bounds.
+///
+/// The heap is sorted such that classes that are deepest in the hierarchy
+/// are removed first; in the case of ties, classes with lower unique
+/// identifiers removed first.
+class _LubHeap extends Heap<_ClassInfo> {
+  @override
+  bool sortsBefore(_ClassInfo a, _ClassInfo b) => sortsBeforeStatic(a, b);
+
+  static bool sortsBeforeStatic(_ClassInfo a, _ClassInfo b) {
+    if (a.depth > b.depth) return true;
+    if (a.depth < b.depth) return false;
+    return a.id < b.id;
+  }
 }