Improvements to the kernel tree shaker.

pkg/kernel/lib/class_hierarchy.dart

 // Copyright (c) 2016, 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 kernel.class_hierarchy;
 
 import 'ast.dart';
 import 'dart:math';
 import 'dart:typed_data';
 import 'type_algebra.dart';
 
@@ skipping 216 matching lines @@
         }
         // A given declared member may override multiple interface members,
         // so only move past the interface member.
         ++j;
       }
     }
   }
 
   /// True if the program contains another class that is a subtype of given one.
   bool hasProperSubtypes(Class class_) {
-    var info = _infoFor[class_];
-    var subtypes = info.subtypeIntervalList;
-    return !(subtypes.length == 2 &&
-        subtypes[0] == info.topDownIndex &&
-        subtypes[1] == info.topDownIndex + 1);
+    // If there are no subtypes then the subtype set contains the class itself.
+    return !getSubtypesOf(class_).isSingleton;
+  }
+
+  /// Returns the subtypes of [class_] as an interval list.
+  ClassSet getSubtypesOf(Class class_) {
+    return new ClassSet(this, _infoFor[class_].subtypeIntervalList);
+  }
+
+  /// Returns the subclasses of [class_] as an interval list.
+  ClassSet getSubclassesOf(Class class_) {
+    return new ClassSet(this, _infoFor[class_].subclassIntervalList);
   }
 
   ClassHierarchy._internal(Program program, int numberOfClasses)
       : classes = new List<Class>(numberOfClasses) {
     // Build the class ordering based on a topological sort.
     for (var library in program.libraries) {
       for (var classNode in library.classes) {
         _topologicalSortVisit(classNode);
       }
     }
@@ skipping 605 matching lines @@
 
   /// Non-final instance fields and setters implemented by this class
   /// (declared or inherited).
   List<Member> implementedSetters;
 
   List<Member> interfaceGettersAndCalls;
   List<Member> interfaceSetters;
 
   _ClassInfo(this.classNode);
 }
+
+/// An immutable set of classes, internally represented as an interval list.
+class ClassSet {
+  final ClassHierarchy _hierarchy;
+  final Uint32List _intervalList;
+
+  ClassSet(this._hierarchy, this._intervalList);
+
+  bool get isEmpty => _intervalList.isEmpty;
+
+  bool get isSingleton {
+    var list = _intervalList;
+    return list.length == 2 && list[0] + 1 == list[1];
+  }
+
+  bool contains(Class class_) {
+    return _intervalListContains(
+        _intervalList, _hierarchy._infoFor[class_].topDownIndex);
+  }
+
+  ClassSet union(ClassSet other) {
+    assert(_hierarchy == other._hierarchy);
+    if (identical(_intervalList, other._intervalList)) return this;
+    _IntervalListBuilder builder = new _IntervalListBuilder();
+    builder.addIntervalList(_intervalList);
+    builder.addIntervalList(other._intervalList);
+    return new ClassSet(_hierarchy, builder.buildIntervalList());
+  }
+}