Optimize needNoSuchMethodHandling computation

pkg/compiler/lib/src/world.dart

Index: pkg/compiler/lib/src/world.dart
diff --git a/pkg/compiler/lib/src/world.dart b/pkg/compiler/lib/src/world.dart
index 8c69baeb5c8c2653543e8988748a292d6d46405e..52d414f3a29b90e3916f37e508608adcc7c5ba37 100644
--- a/pkg/compiler/lib/src/world.dart
+++ b/pkg/compiler/lib/src/world.dart
@@ -728,16 +728,19 @@ class WorldImpl implements ClosedWorld, ClosedWorldRefiner, OpenWorld {
         : result.implementation == element.implementation;
   }
 
-  Element findMatchIn(ClassElement cls, Selector selector) {
+  Element findMatchIn(ClassElement cls, Selector selector,
+      {ClassElement stopAtSuperclass}) {
     // Use the [:implementation] of [cls] in case the found [element]
     // is in the patch class.
-    var result = cls.implementation.lookupByName(selector.memberName);
+    var result = cls.implementation
+        .lookupByName(selector.memberName, stopAtSuperclass: stopAtSuperclass);
     return result;
   }
 
   /// Returns whether a [selector] call on an instance of [cls]
   /// will hit a method at runtime, and not go through [noSuchMethod].
-  bool hasConcreteMatch(ClassElement cls, Selector selector) {
+  bool hasConcreteMatch(ClassElement cls, Selector selector,
+      {ClassElement stopAtSuperclass}) {
     assert(invariant(cls, isInstantiated(cls),
         message: '$cls has not been instantiated.'));
     Element element = findMatchIn(cls, selector);
@@ -753,35 +756,49 @@ class WorldImpl implements ClosedWorld, ClosedWorldRefiner, OpenWorld {
   @override
   bool needsNoSuchMethod(
       ClassElement base, Selector selector, ClassQuery query) {
-    /// Returns `true` if [cls] is an instantiated class that does not have
-    /// a concrete method matching [selector].
-    bool needsNoSuchMethod(ClassElement cls) {
-      // We can skip uninstantiated subclasses.
-      if (!isInstantiated(cls)) {
+    /// Returns `true` if subclasses in the [rootNode] tree needs noSuchMethod
+    /// handling.
+    bool subclassesNeedNoSuchMethod(ClassHierarchyNode rootNode) {
+      if (!rootNode.isInstantiated) {
+        // No subclass needs noSuchMethod handling since they are all
+        // uninstantiated.
         return false;
       }
-      // We can just skip abstract classes because we know no
-      // instance of them will be created at runtime, and
-      // therefore there is no instance that will require
-      // [noSuchMethod] handling.
-      return !cls.isAbstract && !hasConcreteMatch(cls, selector);
-    }
-
-    bool baseNeedsNoSuchMethod = needsNoSuchMethod(base);
-    if (query == ClassQuery.EXACT || baseNeedsNoSuchMethod) {
-      return baseNeedsNoSuchMethod;
+      ClassElement rootClass = rootNode.cls;
+      if (hasConcreteMatch(rootClass, selector)) {
+        // The root subclass has a concrete implementation so no subclass needs
+        // noSuchMethod handling.
+        return false;
+      } else if (rootNode.isDirectlyInstantiated && !rootClass.isAbstract) {
+        // The root class need noSuchMethod handling.
+        return true;
+      }
+      IterationStep result = rootNode.forEachSubclass((ClassElement subclass) {
+        if (hasConcreteMatch(subclass, selector, stopAtSuperclass: rootClass)) {
+          // Found a match - skip all subclasses.
+          return IterationStep.SKIP_SUBCLASSES;
+        } else {
+          // Stop fast - we found a need for noSuchMethod handling.
+          return IterationStep.STOP;

[Siggi Cherem (dart-lang), 2016/10/17 19:30:34]

should we also check that subclass is not abstract?

[Johnni Winther, 2016/10/18 08:13:51]

Wasn't needed above either (now that type inference behaves wrt. super calls)

+        }
+      }, ClassHierarchyNode.DIRECTLY_INSTANTIATED, strict: true);
+      // We stopped fast so we need noSuchMethod handling.
+      return result == IterationStep.STOP;
     }
 
-    Iterable<ClassElement> subclassesToCheck;
-    if (query == ClassQuery.SUBTYPE) {
-      subclassesToCheck = strictSubtypesOf(base);
+    ClassSet classSet = getClassSet(base);
+    ClassHierarchyNode node = classSet.node;
+    if (query == ClassQuery.EXACT) {
+      return node.isDirectlyInstantiated && !hasConcreteMatch(base, selector);
+    } else if (query == ClassQuery.SUBCLASS) {
+      return subclassesNeedNoSuchMethod(node);
     } else {
-      assert(query == ClassQuery.SUBCLASS);
-      subclassesToCheck = strictSubclassesOf(base);
+      if (subclassesNeedNoSuchMethod(node)) return true;
+      for (ClassHierarchyNode subtypeNode in classSet.subtypeNodes) {

[Siggi Cherem (dart-lang), 2016/10/17 19:30:34]

remind me - do subtype nodes include just the immediate set of subtypes or the
recursive set? (do we need to use needsNoSuchMethod below, instead of
subclassesNeedNoSuchMethod)

[Johnni Winther, 2016/10/18 08:13:51]

It contains the roots for subclass trees that implement [base]. For instance

class A {}
class B implements A {}
class C extends B {}
class D implements C {}

for A the subtypeNodes will have roots B and D. C is in the subclass tree of B.

+        if (subclassesNeedNoSuchMethod(subtypeNode)) return true;

[Siggi Cherem (dart-lang), 2016/10/17 19:30:34]

Q: are we guaranteed that subtypes here can't be subclasses too? If not, should
we add an extra optinoal arg here to pass "node" as a stopAtSuperclass in line
768?

[Johnni Winther, 2016/10/18 08:13:51]

Yes. The are not subclasses of [base] (then they would be in [node]). They can,
though, extend superclasses of [base] and thus we still have some potential
repetition. This happens in two ways:

class A {}
class B extends A {}
class C extends B {}
class D extends B {}

when checking D the stopAt class is A (the root of the subclass tree) instead of
B.

class A {}
class B extends A {}
class C extends A implements B {}

when checking the subtypes of B we will search A (and Object) for both B and C.

We could add a set of stop classes but I'm not sure it's worthwhile.

+      }
+      return false;
     }
-
-    return subclassesToCheck != null &&
-        subclassesToCheck.any(needsNoSuchMethod);
   }
 
   final Compiler _compiler;