locateSingleElement improvement for mixins.

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 88cd29496623428cd6936bbc33b6a8c04ee625c0..7ffd10f0046255a63cf319a13db24a1f4186e701 100644
--- a/pkg/compiler/lib/src/world.dart
+++ b/pkg/compiler/lib/src/world.dart
@@ -167,6 +167,13 @@ abstract class ClassWorld {
   /// of [superclass].
   bool hasAnySubclassThatMixes(ClassElement superclass, ClassElement mixin);
 
+  /// Returns `true` if [cls] or any superclass mixes in [mixin].
+  bool isSubclassOfMixinOf(ClassElement cls, ClassElement mixin);
+
+  /// Returns `true` if every subtype of [x] is a subclass of [y] or a subclass
+  /// of a mixin application of [y].
+  bool everySubtypeIsSubclassOrMixinOf(ClassElement x, ClassElement y);
+
   /// Returns `true` if any subclass of [superclass] implements [type].
   bool hasAnySubclassThatImplements(ClassElement superclass, ClassElement type);
 
@@ -504,6 +511,36 @@ class World implements ClassWorld {
     return mixinUsesOf(mixin).any((each) => each.isSubclassOf(superclass));
   }
 
+  /// Returns `true` if [cls] or any superclass mixes in [mixin].
+  bool isSubclassOfMixinOf(ClassElement cls, ClassElement mixin) {

[Siggi Cherem (dart-lang), 2016/08/29 19:26:00]

nit: _Of_Of confuses me a bit, consider renaming?

An idea: isSubclassOfMixinApplication(cls, mixin)?

[sra1, 2016/08/29 20:37:18]

Johnni - what do you think?

For consistency with the rest of the file I think maybe change it to
isSubclassOfMixinUseOf

[Johnni Winther, 2016/08/30 11:36:08]

I'd go for 'isSubclassOfMixinUseOf' or maybe `inheritsMixin(cls, mixin)`. 

+    if (isUsedAsMixin(mixin)) {
+      ClassElement current = cls.declaration;
+      mixin = mixin.declaration;
+      while (current != null) {
+        current = current.declaration;
+        if (current.isMixinApplication) {
+          MixinApplicationElement application = current;
+          if (application.mixin.declaration == mixin) return true;
+        }
+        current = current.superclass;
+      }
+    }
+    return false;
+  }
+
+  /// Returns `true` if every subtype of [x] is a subclass of [y] or a subclass
+  /// of a mixin application of [y].
+  bool everySubtypeIsSubclassOrMixinOf(ClassElement x, ClassElement y) {
+    x = x.declaration;
+    y = y.declaration;
+    Map<ClassElement, bool> secondMap =
+        _subtypeCoveredByCache[x] ??= <ClassElement, bool>{};
+    return secondMap[y] ??=
+        subtypesOf(x).every(

[Siggi Cherem (dart-lang), 2016/08/29 19:26:01]

I wonder how much this affects compile-time.

If it is expensive, could switching the order here help? I mean, instead of
first searching for subtypes and then checking for the subclass/mixin check, I
wonder if there is a way to use `mixinUsesOf` as a way to limit the search space
first.

[sra1, 2016/08/29 20:37:17]

I didn't see any perf issues on Golem.
Two things tend to weed out massive queries:

1. The query is only called when there is a single possible target method.
2. The query is only called when the mask is a subtype mask. Many subtype masks
are strengthened to subclass masks.

+            (ClassElement cls) =>
+            isSubclassOf(cls, y) || isSubclassOfMixinOf(cls, y));
+  }
+
   /// Returns `true` if any subclass of [superclass] implements [type].
   bool hasAnySubclassThatImplements(
       ClassElement superclass, ClassElement type) {
@@ -533,6 +570,9 @@ class World implements ClassWorld {
       <ClassElement, ClassHierarchyNode>{};
   final Map<ClassElement, ClassSet> _classSets = <ClassElement, ClassSet>{};
 
+  final Map<ClassElement, Map<ClassElement, bool>> _subtypeCoveredByCache =
+      <ClassElement, Map<ClassElement, bool>>{};
+
   final Set<Element> sideEffectsFreeElements = new Set<Element>();
 
   final Set<Element> elementsThatCannotThrow = new Set<Element>();