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';
 
+/// 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 ClassHierarchyImpl(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));
+}
+
 /// Data structure for answering various subclassing queries.
-class ClassHierarchy {
+class ClassHierarchyImpl implements ClassHierarchy {

[ahe, 2017/05/29 13:56:18]

I suggest that this class is renamed to, for example, ClosedWorldClassHierarchy.

The reason for that is that this class ends up be used in several places, and
all these places it seems like the important reason for using this class is that
it is based on a closed-world assumption.

[scheglov, 2017/05/30 01:18:18]

Good idea.
Done.

   /// 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)
+  ClassHierarchyImpl(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)
+  ClassHierarchyImpl._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 ClassHierarchyImpl _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;
   }
 }