Implement getInterfaceMember() for IncrementalClassHierarchy.

pkg/kernel/lib/src/incremental_class_hierarchy.dart

 // Copyright (c) 2017, 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.incremental_class_hierarchy;
 
 import 'dart:collection';
 import 'dart:math';
 
 import 'package:kernel/ast.dart';
 import 'package:kernel/class_hierarchy.dart';
@@ skipping 197 matching lines @@
 
   @override
   Member getDispatchTarget(Class node, Name name, {bool setter: false}) {
     _ClassInfo info = _getInfo(node);
     List<Member> targets =
         setter ? info.implementedSetters : info.implementedGettersAndCalls;
     return _findMemberByName(targets, name);
   }
 
   @override
-  Member getInterfaceMember(Class class_, Name name, {bool setter: false}) {
-    // TODO(scheglov): implement getInterfaceMember
-    throw new UnimplementedError();
+  Member getInterfaceMember(Class node, Name name, {bool setter: false}) {
+    _ClassInfo info = _getInfo(node);
+    List<Member> members =
+        setter ? info.interfaceSetters : info.interfaceGettersAndCalls;
+    return _findMemberByName(members, name);
   }
 
   @override
   List<Class> getRankedSuperclasses(Class node) {
     var info = _getInfo(node);
     return _getRankedSuperclassList(info).map((info) => info.node).toList();
   }
 
   @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);
   }
 
   @override
   bool hasProperSubtypes(Class class_) {
     // TODO(scheglov): implement hasProperSubtypes
     throw new UnimplementedError();
   }
 
-  /// Fill the given [info] with declared methods and setters.
+  /// Fill the given [info] with declared instance methods and setters.
   void _buildDeclaredMembers(_ClassInfo info) {
     Class node = info.node;
     if (node.mixedInType != null) {
       _ClassInfo mixedInfo = _getInfo(node.mixedInType.classNode);
       info.declaredGettersAndCalls = mixedInfo.declaredGettersAndCalls;
       info.declaredSetters = mixedInfo.declaredSetters;
     } else {
       var members = info.declaredGettersAndCalls = <Member>[];
       var setters = info.declaredSetters = <Member>[];
       for (Procedure procedure in node.procedures) {
@@ skipping 31 matching lines @@
       inheritedSetters = superInfo.implementedSetters;
     }
     info.implementedGettersAndCalls = _inheritMembers(
         info.declaredGettersAndCalls, inheritedMembers,
         skipAbstractMembers: true);
     info.implementedSetters = _inheritMembers(
         info.declaredSetters, inheritedSetters,
         skipAbstractMembers: true);
   }
 
+  /// Build interface methods or setters for the class described by [info].
+  void _buildInterfaceMembers(_ClassInfo info) {
+    List<Member> declaredGetters = info.declaredGettersAndCalls;
+    List<Member> declaredSetters = info.declaredSetters;
+    List<Member> allInheritedGetters = <Member>[];
+    List<Member> allInheritedSetters = <Member>[];
+
+    void inheritFrom(Supertype type) {
+      if (type == null) return;
+      var info = _getInfo(type.classNode);
+      // TODO(scheglov): Can we optimize this with yield?
+
+      var inheritedGetters = _getUnshadowedInheritedMembers(
+          declaredGetters, info.interfaceGettersAndCalls);
+      allInheritedGetters = _merge(allInheritedGetters, inheritedGetters);
+
+      var inheritedSetters = _getUnshadowedInheritedMembers(
+          declaredSetters, info.interfaceSetters);
+      allInheritedSetters = _merge(allInheritedSetters, inheritedSetters);
+    }
+
+    Class node = info.node;
+    inheritFrom(node.supertype);
+    inheritFrom(node.mixedInType);
+    node.implementedTypes.forEach(inheritFrom);
+
+    info.interfaceGettersAndCalls =
+        _inheritMembers(declaredGetters, allInheritedGetters);
+    info.interfaceSetters =
+        _inheritMembers(declaredSetters, allInheritedSetters);
+  }
+
   /// Return the [_ClassInfo] for the [node].
   _ClassInfo _getInfo(Class node) {
     var info = _info[node];
     if (info == null) {
       info = new _ClassInfo(_nextId++, node);
       _info[node] = info;
 
       void addSupertypeIdentifiers(_ClassInfo superInfo) {
         info.supertypeIdSet.add(superInfo.id);
         info.supertypeIdSet.addAll(superInfo.supertypeIdSet);
@@ skipping 15 matching lines @@
       for (var implementedType in node.implementedTypes) {
         var implementedInfo = _getInfo(implementedType.classNode);
         superDepth = max(superDepth, implementedInfo.depth);
         addSupertypeIdentifiers(implementedInfo);
         _recordSuperTypes(info, implementedType, implementedInfo);
       }
       info.depth = superDepth + 1;
 
       _buildDeclaredMembers(info);
       _buildImplementedMembers(info);
+      _buildInterfaceMembers(info);
     }
     return info;
   }
 
   List<_ClassInfo> _getRankedSuperclassList(_ClassInfo info) {
     if (info.rankedSuperclassList != null) {
       return info.rankedSuperclassList;
     }
 
     var heap = new _LubHeap()..add(info);
@@ skipping 50 matching lines @@
       var substitution = Substitution.fromPairs(
           superclass.typeParameters, supertype.typeArguments);
       subInfo.genericSuperTypes ??= <Class, Supertype>{};
       superInfo.genericSuperTypes?.forEach((Class key, Supertype type) {
         subInfo.genericSuperTypes[key] = substitution.substituteSupertype(type);
       });
       subInfo.genericSuperTypes[superclass] = supertype;
     }
   }
 
+  /// Returns the subset of members in [inherited] for which a member with the
+  /// same name does not occur in [declared].
+  ///
+  /// The input lists must be sorted, and the returned list is sorted.
+  static List<Member> _getUnshadowedInheritedMembers(
+      List<Member> declared, List<Member> inherited) {
+    List<Member> result = <Member>[]..length = inherited.length;

[Paul Berry, 2017/06/03 13:27:34]

Creating the list and then setting its length as two separate steps seems
wasteful.  How about:

var result = new List<Member>.filled(inherited.length, null, growable: true);

[scheglov, 2017/06/04 00:47:47]

Done.

+    int storeIndex = 0;
+    int i = 0, j = 0;
+    while (i < declared.length && j < inherited.length) {
+      Member declaredMember = declared[i];
+      Member inheritedMember = inherited[j];
+      int comparison = _compareMembers(declaredMember, inheritedMember);
+      if (comparison < 0) {
+        ++i;
+      } else if (comparison > 0) {
+        result[storeIndex++] = inheritedMember;
+        ++j;
+      } else {
+        // Move past the shadowed member, but retain the declared member, as
+        // it may shadow multiple members.
+        ++j;
+      }
+    }
+    // If the list of declared members is exhausted, copy over the remains of
+    // the inherited members.
+    while (j < inherited.length) {
+      result[storeIndex++] = inherited[j++];
+    }
+    result.length = storeIndex;
+    return result;
+  }
+
   /// Computes the list of implemented members, based on the declared instance
   /// members and inherited instance members.
   ///
   /// Both lists must be sorted by name beforehand.
   static List<Member> _inheritMembers(
       List<Member> declared, List<Member> inherited,
       {bool skipAbstractMembers: false}) {
     List<Member> result = <Member>[]..length =
         declared.length + inherited.length;
     // Since both lists are sorted, we can fuse them like in merge sort.
@@ skipping 30 matching lines @@
       result[storeIndex++] = declaredMember;
     }
     while (j < inherited.length) {
       Member inheritedMember = inherited[j++];
       if (skipAbstractMembers && inheritedMember.isAbstract) continue;
       result[storeIndex++] = inheritedMember;
     }
     result.length = storeIndex;
     return result;
   }
+
+  /// Merges two sorted lists.
+  ///
+  /// If a given member occurs in both lists, the merge will attempt to exclude
+  /// the duplicate member, but is not strictly guaranteed to do so.
+  static List<Member> _merge(List<Member> first, List<Member> second) {
+    if (first.isEmpty) return second;
+    if (second.isEmpty) return first;
+    List<Member> result = <Member>[]..length = first.length + second.length;
+    int storeIndex = 0;
+    int i = 0, j = 0;
+    while (i < first.length && j < second.length) {
+      Member firstMember = first[i];
+      Member secondMember = second[j];
+      int compare = _compareMembers(firstMember, secondMember);
+      if (compare <= 0) {
+        result[storeIndex++] = firstMember;
+        ++i;
+        // If the same member occurs in both lists, skip the duplicate.
+        if (identical(firstMember, secondMember)) {
+          ++j;
+        }
+      } else {
+        result[storeIndex++] = secondMember;
+        ++j;
+      }
+    }
+    while (i < first.length) {
+      result[storeIndex++] = first[i++];
+    }
+    while (j < second.length) {
+      result[storeIndex++] = second[j++];
+    }
+    result.length = storeIndex;
+    return result;
+  }
 }
 
 /// 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;
 
@@ skipping 47 matching lines @@
   List<Member> declaredSetters;
 
   /// Instance fields, getters, methods, and operators implemented by this class
   /// (declared or inherited).
   List<Member> implementedGettersAndCalls;
 
   /// Non-final instance fields and setters implemented by this class
   /// (declared or inherited).
   List<Member> implementedSetters;
 
+  /// Instance fields, getters, methods, and operators declared in this class,
+  /// or its supertype, or interfaces, sorted according to [_compareMembers],
+  /// or `null` if it has not been computed yet.
+  List<Member> interfaceGettersAndCalls;
+
+  /// Non-final instance fields and setters declared in this class, or its
+  /// supertype, or interfaces, sorted according to [_compareMembers], or
+  /// `null` if it has not been computed yet.
+  List<Member> interfaceSetters;
+
   _ClassInfo(this.id, this.node);
 
   /// Return `true` if the [superInfo] corresponds to a supertype of this class.
   bool isSubtypeOf(_ClassInfo superInfo) {
     return supertypeIdSet.contains(superInfo.id);
   }
 
   @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;
   }
 }