Implement getInterfaceMember() for IncrementalClassHierarchy.

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 93e44da4de128053f08408066e257589bf80cf3f..c1fefa06fb31ac643c123f128b27264c3abbf86d 100644
--- a/pkg/kernel/lib/src/incremental_class_hierarchy.dart
+++ b/pkg/kernel/lib/src/incremental_class_hierarchy.dart
@@ -215,9 +215,11 @@ class IncrementalClassHierarchy implements ClassHierarchy {
   }
 
   @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
@@ -241,7 +243,7 @@ class IncrementalClassHierarchy implements ClassHierarchy {
     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) {
@@ -293,6 +295,38 @@ class IncrementalClassHierarchy implements ClassHierarchy {
         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];
@@ -328,6 +362,7 @@ class IncrementalClassHierarchy implements ClassHierarchy {
 
       _buildDeclaredMembers(info);
       _buildImplementedMembers(info);
+      _buildInterfaceMembers(info);
     }
     return info;
   }
@@ -398,6 +433,39 @@ class IncrementalClassHierarchy implements ClassHierarchy {
     }
   }
 
+  /// 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.
   ///
@@ -448,6 +516,42 @@ class IncrementalClassHierarchy implements ClassHierarchy {
     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].
@@ -515,6 +619,16 @@ class _ClassInfo {
   /// (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.