Extract ClassHierarchyImpl implementation from ClassHierarchy.

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 'src/heap.dart';
 import 'type_algebra.dart';
 
-/// Data structure for answering various subclassing queries.
-class ClassHierarchy {
+/// Interface for answering various subclassing queries.
+/// TODO(scheglov) Several methods are not used, or used only in tests.
+/// Check if these methods are not useful and should be removed .
+abstract class ClassHierarchy {
+  factory ClassHierarchy(Program program) =>
+      new ClosedWorldClassHierarchy(program);
+
+  /// All classes in the program.
+  ///
+  /// The iterable is ordered so that classes occur after their super classes.
+  Iterable<Class> get classes;
+
+  Class get rootClass;
+
+  /// Returns the index of [class_] in the [classes] list.
+  int getClassIndex(Class class_);
+
+  /// True if the program contains another class that is a subtype of given one.
+  bool hasProperSubtypes(Class class_);
+
+  /// Returns the number of steps in the longest inheritance path from [class_]
+  /// to [rootClass].
+  int getClassDepth(Class class_);
+
+  /// Returns a list of classes appropriate for use in calculating a least upper
+  /// bound.
+  ///
+  /// The returned list is a list of all classes that [class_] is a subtype of
+  /// (including itself), sorted first by depth (deepest first) and then by
+  /// class index.
+  List<Class> getRankedSuperclasses(Class class_);
+
+  /// Returns the least upper bound of two interface types, as defined by Dart
+  /// 1.0.
+  ///
+  /// Given two interfaces I and J, let S_I be the set of superinterfaces of I,
+  /// let S_J be the set of superinterfaces of J, and let
+  /// S = (I union S_I) intersect (J union S_J).  Furthermore, we define
+  /// S_n = {T | T in S and depth(T) = n} for any finite n where depth(T) is
+  /// the number of steps in the longest inheritance path from T to Object.  Let
+  /// q be the largest number such that S_q has cardinality one.  The least
+  /// upper bound of I and J is the sole element of S_q.
+  ///
+  /// This is called the "classic" least upper bound to distinguish it from the
+  /// strong mode least upper bound, which has special behaviors in the case
+  /// where one type is a subtype of the other, or where both types are based on
+  /// the same class.
+  InterfaceType getClassicLeastUpperBound(
+      InterfaceType type1, InterfaceType type2);
+
+  /// Returns the instantiation of [superclass] that is implemented by [class_],
+  /// or `null` if [class_] does not implement [superclass] at all.
+  Supertype getClassAsInstanceOf(Class class_, Class superclass);
+
+  /// Returns the instantiation of [superclass] that is implemented by [type],
+  /// or `null` if [type] does not implement [superclass] at all.
+  InterfaceType getTypeAsInstanceOf(InterfaceType type, Class superclass);
+
+  /// Returns the instance member that would respond to a dynamic dispatch of
+  /// [name] to an instance of [class_], or `null` if no such member exists.
+  ///
+  /// If [setter] is `false`, the name is dispatched as a getter or call,
+  /// and will return a field, getter, method, or operator (or null).
+  ///
+  /// If [setter] is `true`, the name is dispatched as a setter, roughly
+  /// corresponding to `name=` in the Dart specification, but note that the
+  /// returned member will not have a name ending with `=`.  In this case,
+  /// a non-final field or setter (or null) will be returned.
+  ///
+  /// If the class is abstract, abstract members are ignored and the dispatch
+  /// is resolved if the class was not abstract.
+  Member getDispatchTarget(Class class_, Name name, {bool setter: false});
+
+  /// Returns the possibly abstract interface member of [class_] with the given
+  /// [name].
+  ///
+  /// If [setter] is `false`, only fields, methods, and getters with that name
+  /// will be found.  If [setter] is `true`, only non-final fields and setters
+  /// will be found.
+  ///
+  /// If multiple members with that name are inherited and not overridden, the
+  /// member from the first declared supertype is returned.
+  Member getInterfaceMember(Class class_, Name name, {bool setter: false});
+
+  /// Invokes [callback] for every member declared in or inherited by [class_]
+  /// that overrides or implements a member in a supertype of [class_]
+  /// (or in rare cases, overrides a member declared in [class_]).
+  ///
+  /// We use the term "inheritable" for members that are candidates for
+  /// inheritance but may have been overridden.  The "declared" members of a
+  /// mixin application are those declared in the mixed-in type. The callback is
+  /// invoked in the following cases:
+  ///
+  /// 1. A member declared in the class overrides a member inheritable through
+  /// one of the supertypes of the class.
+  ///
+  /// 2. A non-abstract member is inherited from a superclass, and in the
+  /// context of this class, it overrides an abstract member inheritable through
+  /// one of its superinterfaces.
+  ///
+  /// 3. A non-abstract member is inherited from a superclass, and it overrides
+  /// an abstract member declared in this class.
+  ///
+  /// This method will not report that a member overrides itself. A given pair
+  /// may be reported multiple times when there are multiple inheritance paths
+  /// to the overridden member.
+  ///
+  /// It is possible for two methods to override one another in both directions.
+  ///
+  /// Getters and setters are overridden separately.  The [isSetter] callback
+  /// parameter determines which type of access is being overridden.
+  void forEachOverridePair(Class class_,
+      callback(Member declaredMember, Member interfaceMember, bool isSetter));
+}
+
+/// Implementation of [ClassHierarchy] for closed world.
+class ClosedWorldClassHierarchy implements ClassHierarchy {
   /// All classes in the program.
   ///
   /// The list is ordered so that classes occur after their super classes.
   final List<Class> classes;
 
   final Map<Class, _ClassInfo> _infoFor = <Class, _ClassInfo>{};
 
-  ClassHierarchy(Program program)
+  ClosedWorldClassHierarchy(Program program)
       : this._internal(program, _countClasses(program));
 
   Class get rootClass => classes[0];
 
-  /// Returns the index of [class_] in the [classes] list.
+  @override
   int getClassIndex(Class class_) => _infoFor[class_].topologicalIndex;
 
   /// True if [subclass] inherits from [superclass] though zero or more
   /// `extends` relationships.
   bool isSubclassOf(Class subclass, Class superclass) {
     if (identical(subclass, superclass)) return true;
     return _infoFor[subclass].isSubclassOf(_infoFor[superclass]);
   }
 
   /// True if [submixture] inherits from [superclass] though zero or more
@@ skipping 19 matching lines @@
   /// mixin application (i.e. [Class.mixedInType]).
   bool isUsedAsMixin(Class class_) {
     return _infoFor[class_].directMixers.isNotEmpty;
   }
 
   /// True if the given class is used in an `implements` clause.
   bool isUsedAsSuperInterface(Class class_) {
     return _infoFor[class_].directImplementers.isNotEmpty;
   }
 
-  /// Returns the number of steps in the longest inheritance path from [class_]
-  /// to [rootClass].
+  @override
   int getClassDepth(Class class_) => _infoFor[class_].depth;
 
-  /// Returns a list of classes appropriate for use in calculating a least upper
-  /// bound.
-  ///
-  /// The returned list is a list of all classes that [class_] is a subtype of
-  /// (including itself), sorted first by depth (deepest first) and then by
-  /// class index.
+  @override
   List<Class> getRankedSuperclasses(Class class_) {
     return _getRankedSuperclassInfos(_infoFor[class_])
         .map((info) => info.classNode)
         .toList();
   }
 
   List<_ClassInfo> _getRankedSuperclassInfos(_ClassInfo info) {
     if (info.leastUpperBoundInfos != null) return info.leastUpperBoundInfos;
     var heap = new _LubHeap()..add(info);
     var chain = <_ClassInfo>[];
     info.leastUpperBoundInfos = chain;
     _ClassInfo lastInfo = null;
     while (heap.isNotEmpty) {
       var nextInfo = heap.remove();
       if (identical(nextInfo, lastInfo)) continue;
       chain.add(nextInfo);
       lastInfo = nextInfo;
       var classNode = nextInfo.classNode;
       void addToHeap(Supertype supertype) {
         heap.add(_infoFor[supertype.classNode]);
       }
 
       if (classNode.supertype != null) addToHeap(classNode.supertype);
       if (classNode.mixedInType != null) addToHeap(classNode.mixedInType);
       classNode.implementedTypes.forEach(addToHeap);
     }
     return chain;
   }
 
-  /// Returns the least upper bound of two interface types, as defined by Dart
-  /// 1.0.
-  ///
-  /// Given two interfaces I and J, let S_I be the set of superinterfaces of I,
-  /// let S_J be the set of superinterfaces of J, and let
-  /// S = (I union S_I) intersect (J union S_J).  Furthermore, we define
-  /// S_n = {T | T in S and depth(T) = n} for any finite n where depth(T) is
-  /// the number of steps in the longest inheritance path from T to Object.  Let
-  /// q be the largest number such that S_q has cardinality one.  The least
-  /// upper bound of I and J is the sole element of S_q.
-  ///
-  /// This is called the "classic" least upper bound to distinguish it from the
-  /// strong mode least upper bound, which has special behaviors in the case
-  /// where one type is a subtype of the other, or where both types are based on
-  /// the same class.
+  @override
   InterfaceType getClassicLeastUpperBound(
       InterfaceType type1, InterfaceType type2) {
     // The algorithm is: first we compute a list of superclasses for both types,
     // ordered from greatest to least depth, and ordered by topological sort
     // index within each depth.  Due to the sort order, we can find the
     // intersection of these lists by a simple walk.
     //
     // Then, for each class in the intersection, determine the exact type that
     // is implemented by type1 and type2.  If the types match, that type is a
     // candidate (it's a member of S_n).  As soon as we find a candidate which
@@ skipping 75 matching lines @@
             : Substitution.fromInterfaceType(type2).substituteType(
                 info2.genericSuperTypes[next.classNode].asInterfaceType);
         if (superType1 == superType2) {
           candidate = superType1;
           ++numCandidatesAtThisDepth;
         }
       }
     }
   }
 
-  /// Returns the instantiation of [superclass] that is implemented by [class_],
-  /// or `null` if [class_] does not implement [superclass] at all.
+  @override
   Supertype getClassAsInstanceOf(Class class_, Class superclass) {
     if (identical(class_, superclass)) return class_.asThisSupertype;
     _ClassInfo info = _infoFor[class_];
     _ClassInfo superInfo = _infoFor[superclass];
     if (!info.isSubtypeOf(superInfo)) return null;
     if (superclass.typeParameters.isEmpty) return superclass.asRawSupertype;
     return info.genericSuperTypes[superclass];
   }
 
-  /// Returns the instantiation of [superclass] that is implemented by [type],
-  /// or `null` if [type] does not implement [superclass] at all.
+  @override
   InterfaceType getTypeAsInstanceOf(InterfaceType type, Class superclass) {
     Supertype castedType = getClassAsInstanceOf(type.classNode, superclass);
     if (castedType == null) return null;
     return Substitution
         .fromInterfaceType(type)
         .substituteType(castedType.asInterfaceType);
   }
 
-  /// Returns the instance member that would respond to a dynamic dispatch of
-  /// [name] to an instance of [class_], or `null` if no such member exists.
-  ///
-  /// If [setter] is `false`, the name is dispatched as a getter or call,
-  /// and will return a field, getter, method, or operator (or null).
-  ///
-  /// If [setter] is `true`, the name is dispatched as a setter, roughly
-  /// corresponding to `name=` in the Dart specification, but note that the
-  /// returned member will not have a name ending with `=`.  In this case,
-  /// a non-final field or setter (or null) will be returned.
-  ///
-  /// If the class is abstract, abstract members are ignored and the dispatch
-  /// is resolved if the class was not abstract.
+  @override
   Member getDispatchTarget(Class class_, Name name, {bool setter: false}) {
     _ClassInfo info = _infoFor[class_];
     List<Member> list =
         setter ? info.implementedSetters : info.implementedGettersAndCalls;
     return _findMemberByName(list, name);
   }
 
   /// Returns the list of potential targets of dynamic dispatch to an instance
   /// of [class_].
   ///
   /// If [setters] is `false`, only potential targets of a getter or call
   /// dispatch are returned.  If [setters] is `true`, only potential targets
   /// of a setter dispatch are returned.
   ///
   /// See [getDispatchTarget] for more details.
   ///
   /// The returned list should not be modified.
   List<Member> getDispatchTargets(Class class_, {bool setters: false}) {
     _ClassInfo info = _infoFor[class_];
     return setters ? info.implementedSetters : info.implementedGettersAndCalls;
   }
 
-  /// Returns the possibly abstract interface member of [class_] with the given
-  /// [name].
-  ///
-  /// If [setters] is `false`, only fields, methods, and getters with that name
-  /// will be found.  If [setters] is `true`, only non-final fields and setters
-  /// will be found.
-  ///
-  /// If multiple members with that name are inherited and not overidden, the
-  /// member from the first declared supertype is returned.
+  @override
   Member getInterfaceMember(Class class_, Name name, {bool setter: false}) {
     List<Member> list = getInterfaceMembers(class_, setters: setter);
     return _findMemberByName(list, name);
   }
 
   /// Returns the list of members denoting the interface for [class_], which
   /// may include abstract members.
   ///
   /// The list may contain multiple members with a given name.  This happens
   /// when members are inherited through different supertypes and not overridden
   /// in the class.
   ///
   /// Also see [getInterfaceMember].
   List<Member> getInterfaceMembers(Class class_, {bool setters: false}) {
     return _buildInterfaceMembers(class_, _infoFor[class_], setters: setters);
   }
 
-  /// Invokes [callback] for every member declared in or inherited by [class_]
-  /// that overrides or implements a member in a supertype of [class_]
-  /// (or in rare cases, overrides a member declared in [class_]).
-  ///
-  /// We use the term "inheritable" for members that are candidates for
-  /// inheritance but may have been overridden.  The "declared" members of a
-  /// mixin application are those declared in the mixed-in type. The callback is
-  /// invoked in the following cases:
-  ///
-  /// 1. A member declared in the class overrides a member inheritable through
-  /// one of the supertypes of the class.
-  ///
-  /// 2. A non-abstract member is inherited from a superclass, and in the
-  /// context of this class, it overrides an abstract member inheritable through
-  /// one of its superinterfaces.
-  ///
-  /// 3. A non-abstract member is inherited from a superclass, and it overrides
-  /// an abstract member declared in this class.
-  ///
-  /// This method will not report that a member overrides itself. A given pair
-  /// may be reported multiple times when there are multiple inheritance paths
-  /// to the overridden member.
-  ///
-  /// It is possible for two methods to override one another in both directions.
-  ///
-  /// Getters and setters are overridden separately.  The [isSetter] callback
-  /// parameter determines which type of access is being overridden.
+  @override
   void forEachOverridePair(Class class_,
       callback(Member declaredMember, Member interfaceMember, bool isSetter)) {
     _ClassInfo info = _infoFor[class_];
     for (var supertype in class_.supers) {
       var superclass = supertype.classNode;
       var superGetters = getInterfaceMembers(superclass);
       var superSetters = getInterfaceMembers(superclass, setters: true);
       _reportOverrides(info.implementedGettersAndCalls, superGetters, callback);
       _reportOverrides(info.declaredGettersAndCalls, superGetters, callback,
           onlyAbstract: true);
@@ skipping 41 matching lines @@
         if (!identical(declared, inherited)) {
           callback(declared, inherited, isSetter);
         }
         // 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.
+  @override
   bool hasProperSubtypes(Class class_) {
     // 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)
+  ClosedWorldClassHierarchy._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);
       }
     }
 
     // Build index of direct children.  Do this after the topological sort so
     // that super types always occur before subtypes.
@@ skipping 615 matching lines @@
   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 ClosedWorldClassHierarchy _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];
   }
@@ skipping 21 matching lines @@
 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.topologicalIndex < b.topologicalIndex;
   }
 }