locateSingleElement improvement for mixins.

pkg/compiler/lib/src/world.dart

 // Copyright (c) 2012, 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 dart2js.world;
 
 import 'closure.dart' show SynthesizedCallMethodElementX;
 import 'common/backend_api.dart' show Backend;
 import 'common.dart';
 import 'compiler.dart' show Compiler;
@@ skipping 149 matching lines @@
   bool isUsedAsMixin(ClassElement cls);
 
   /// Returns `true` if any live class that mixes in [cls] implements [type].
   bool hasAnySubclassOfMixinUseThatImplements(
       ClassElement cls, ClassElement type);
 
   /// Returns `true` if any live class that mixes in [mixin] is also a subclass
   /// 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);
 
   /// Returns `true` if closed-world assumptions can be made, that is,
   /// incremental compilation isn't enabled.
   bool get hasClosedWorldAssumption;
 
   /// Returns a string representation of the closed world.
   ///
   /// If [cls] is provided, the dump will contain only classes related to [cls].
@@ skipping 317 matching lines @@
     return mixinUsesOf(cls)
         .any((use) => hasAnySubclassThatImplements(use, type));
   }
 
   /// Returns `true` if any live class that mixes in [mixin] is also a subclass
   /// of [superclass].
   bool hasAnySubclassThatMixes(ClassElement superclass, ClassElement mixin) {
     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) {
     Set<ClassElement> subclasses = typesImplementedBySubclassesOf(superclass);
     if (subclasses == null) return false;
     return subclasses.contains(type);
   }
 
   final Compiler compiler;
   Backend get backend => compiler.backend;
   final FunctionSet allFunctions;
   final Set<Element> functionsCalledInLoop = new Set<Element>();
   final Map<Element, SideEffects> sideEffects = new Map<Element, SideEffects>();
 
   final Set<TypedefElement> allTypedefs = new Set<TypedefElement>();
 
   final Map<ClassElement, Set<MixinApplicationElement>> _mixinUses =
       new Map<ClassElement, Set<MixinApplicationElement>>();
   Map<ClassElement, List<MixinApplicationElement>> _liveMixinUses;
 
   final Map<ClassElement, Set<ClassElement>> _typesImplementedBySubclasses =
       new Map<ClassElement, Set<ClassElement>>();
 
   // We keep track of subtype and subclass relationships in four
   // distinct sets to make class hierarchy analysis faster.
   final Map<ClassElement, ClassHierarchyNode> _classHierarchyNodes =
       <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>();
 
   final Set<Element> functionsThatMightBePassedToApply =
       new Set<FunctionElement>();
 
   final Set<Element> alreadyPopulated;
 
   bool get isClosed => compiler.phase > Compiler.PHASE_RESOLVING;
@@ skipping 289 matching lines @@
     // function expressions's element.
     // TODO(herhut): Generate classes for function expressions earlier.
     if (element is SynthesizedCallMethodElementX) {
       return getMightBePassedToApply(element.expression);
     }
     return functionsThatMightBePassedToApply.contains(element);
   }
 
   bool get hasClosedWorldAssumption => !compiler.options.hasIncrementalSupport;
 }