Implement optimized mixin application in dart2js

pkg/compiler/lib/src/resolution/class_hierarchy.dart

 // Copyright (c) 2015, 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.resolution.class_hierarchy;
 
 import '../common.dart';
 import '../common/resolution.dart' show Resolution;
 import '../common_elements.dart' show CommonElements;
 import '../elements/resolution_types.dart';
 import '../elements/elements.dart';
 import '../elements/modelx.dart'
     show
         BaseClassElementX,
         ErroneousElementX,
+        LibraryElementX,
         MixinApplicationElementX,
         SynthesizedConstructorElementX,
         TypeVariableElementX,
         UnnamedMixinApplicationElementX;
 import '../elements/names.dart';
 import '../ordered_typeset.dart'
     show OrderedTypeSet, ResolutionOrderedTypeSetBuilder;
 import '../tree/tree.dart';
 import '../universe/call_structure.dart' show CallStructure;
 import '../universe/feature.dart' show Feature;
 import '../util/util.dart' show Link, Setlet;
 import 'enum_creator.dart';
 import 'members.dart' show lookupInScope;
 import 'registry.dart' show ResolutionRegistry;
 import 'resolution_common.dart' show CommonResolverVisitor, MappingVisitor;
 import 'scope.dart' show Scope, TypeDeclarationScope;
 
+/// If `true` compatible mixin applications are shared within a library. This
+/// matches the mixins generated by fasta.
+bool useOptimizedMixins = false;
+
 class TypeDefinitionVisitor extends MappingVisitor<ResolutionDartType> {
   Scope scope;
   final TypeDeclarationElement enclosingElement;
   TypeDeclarationElement get element => enclosingElement;
 
   TypeDefinitionVisitor(Resolution resolution, TypeDeclarationElement element,
       ResolutionRegistry registry)
       : this.enclosingElement = element,
         scope = Scope.buildEnclosingScope(element),
         super(resolution, registry);
@@ skipping 95 matching lines @@
     // TODO(ahe): It is not safe to call resolveTypeVariableBounds yet.
     // As a side-effect, this may get us back here trying to
     // resolve this class again.
     resolveTypeVariableBounds(node.typeParameters);
 
     // Setup the supertype for the element (if there is a cycle in the
     // class hierarchy, it has already been set to Object).
     if (element.supertype == null && node.superclass != null) {
       MixinApplication superMixin = node.superclass.asMixinApplication();
       if (superMixin != null) {
-        ResolutionDartType supertype =
-            resolveSupertype(element, superMixin.superclass);
-        Link<Node> link = superMixin.mixins.nodes;
-        while (!link.isEmpty) {
-          supertype =
-              applyMixin(supertype, checkMixinType(link.head), link.head);
-          link = link.tail;
+        if (useOptimizedMixins) {
+          element.supertype = createMixinsOptimized(element, superMixin);
+        } else {
+          element.supertype = createMixins(element, superMixin);
         }
-        element.supertype = supertype;
       } else {
         element.supertype = resolveSupertype(element, node.superclass);
       }
     }
     // If the super type isn't specified, we provide a default.  The language
     // specifies [Object] but the backend can pick a specific 'implementation'
     // of Object - the JavaScript backend chooses between Object and
     // Interceptor.
     if (element.supertype == null) {
       ClassElement superElement = registry.defaultSuperclass(element);
@@ skipping 111 matching lines @@
       throw reporter.internalError(
           element, 'cyclic resolution of class $element');
     }
 
     element.computeType(resolution);
     scope = new TypeDeclarationScope(scope, element);
     resolveTypeVariableBounds(node.typeParameters);
 
     // Generate anonymous mixin application elements for the
     // intermediate mixin applications (excluding the last).
+    if (useOptimizedMixins) {
+      createMixinsOptimized(element, node, isNamed: true);
+    } else {
+      createMixins(element, node, isNamed: true);
+    }
+    return element.computeType(resolution);
+  }
+
+  /// Create the mixin applications for [superMixin].
+  ///
+  /// This algorithm is ported from
+  /// `package:front_end/src/fasta/kernel/kernel_library_builder.dart` and
+  /// added create allow for equivalence testing between the AST and kernel
+  /// based compilations in face of shared mixins. It will be removed when we
+  /// no longer need equivalence testing.
+  ResolutionDartType createMixinsOptimized(
+      BaseClassElementX element, MixinApplication superMixin,
+      {bool isNamed: false}) {
+    LibraryElementX library = element.library;
+    Map<String, MixinApplicationElementX> mixinApplicationClasses =
+        library.mixinApplicationCache;
+
+    String name = element.isNamedMixinApplication ? element.name : null;
+    ResolutionDartType supertype =
+        resolveSupertype(element, superMixin.superclass);
+    Link<Node> link = superMixin.mixins.nodes;
+    List<ResolutionDartType> mixins = <ResolutionDartType>[];
+    List<Node> mixinNodes = <Node>[];
+    while (!link.isEmpty) {
+      mixins.add(checkMixinType(link.head));
+      mixinNodes.add(link.head);
+      link = link.tail;
+    }
+
+    List<List<String>> signatureParts = <List<String>>[];
+    Map<String, ResolutionDartType> freeTypes = <String, ResolutionDartType>{};
+
+    {
+      Map<String, String> unresolved = <String, String>{};
+      int unresolvedCount = 0;
+
+      /// Compute a signature of the type arguments used by the supertype and
+      /// mixins. These types are free variables. At this point we can't
+      /// trust that the number of type arguments match the type parameters,
+      /// so we also need to be able to detect missing type arguments.  To do
+      /// so, we separate each list of type arguments by `^` and type
+      /// arguments by `&`. For example, the mixin `C<S> with M<T, U>` would
+      /// look like this:
+      ///
+      ///     ^#U0^#U1&#U2
+      ///
+      /// Where `#U0`, `#U1`, and `#U2` are the free variables arising from
+      /// `S`, `T`, and `U` respectively.
+      ///
+      /// As we can resolve any type parameters used at this point, those are
+      /// named `#T0` and so forth. This reduces the number of free variables
+      /// which is crucial for memory usage and the Dart VM's bootstrap
+      /// sequence.
+      ///
+      /// For example, consider this use of mixin applications:
+      ///
+      ///     class _InternalLinkedHashMap<K, V> extends _HashVMBase
+      ///         with
+      ///             MapMixin<K, V>,
+      ///             _LinkedHashMapMixin<K, V>,
+      ///             _HashBase,
+      ///             _OperatorEqualsAndHashCode {}
+      ///
+      /// In this case, only two variables are free, and we produce this
+      /// signature: `^^#T0&#T1^#T0&#T1^^`. Assume another class uses the
+      /// sames mixins but with missing type arguments for `MapMixin`, its
+      /// signature would be: `^^^#T0&#T1^^`.
+      ///
+      /// Note that we do not need to compute a signature for a named mixin
+      /// application with only one mixin as we don't have to invent a name
+      /// for any classes in this situation.
+      void analyzeArguments(ResolutionDartType type, {bool isLast}) {
+        if (isNamed && isLast) {
+          // The last mixin of a named mixin application doesn't contribute
+          // to free variables.
+          return;
+        }
+        if (type is GenericType) {
+          List<String> part = <String>[];
+          for (int i = 0; i < type.typeArguments.length; i++) {
+            var argument = type.typeArguments[i];
+            String name;
+            if (argument is ResolutionTypeVariableType) {
+              int index = element.typeVariables.indexOf(argument) ?? -1;
+              if (index != -1) {
+                name = "#T${index}";
+              }
+            } else if (argument is GenericType && argument.isRaw) {
+              name = unresolved[argument.name] ??= "#U${unresolvedCount++}";
+            }
+            name ??= "#U${unresolvedCount++}";
+            freeTypes[name] = argument;
+            part.add(name);
+          }
+          signatureParts.add(part);
+        }
+      }
+
+      analyzeArguments(supertype, isLast: false);
+      for (int i = 0; i < mixins.length; i++) {
+        analyzeArguments(mixins[i], isLast: i == mixins.length - 1);
+      }
+    }
+
+    List<List<String>> currentSignatureParts = <List<String>>[];
+    String computeSignature(int index) {
+      if (freeTypes.isEmpty) return "";
+      currentSignatureParts.add(signatureParts[index]);
+      if (currentSignatureParts.any((l) => l.isNotEmpty)) {
+        return "^${currentSignatureParts.map((l) => l.join('&')).join('^')}";
+      } else {
+        return "";
+      }
+    }
+
+    Map<String, ResolutionTypeVariableType> computeTypeVariables(
+        ClassElement cls, Node node) {
+      Map<String, ResolutionTypeVariableType> variables =
+          <String, ResolutionTypeVariableType>{};
+      int index = 0;
+      for (List<String> strings in currentSignatureParts) {
+        for (String name in strings) {
+          variables[name] ??= new ResolutionTypeVariableType(
+              new TypeVariableElementX(name, cls, index++, node));
+        }
+      }
+      return variables;
+    }
+
+    computeSignature(0); // This combines the supertype with the first mixin.
+
+    for (int i = 0; i < mixins.length; i++) {
+      int signatureIndex = i + 1;
+      Set<String> supertypeArguments = new Set<String>();
+      for (List<String> part in currentSignatureParts) {
+        supertypeArguments.addAll(part);
+      }
+      Node node = mixinNodes[i];
+      ResolutionDartType mixin = mixins[i];
+
+      bool lastAndNamed = i == mixins.length - 1 && isNamed;
+
+      ResolutionInterfaceType createMixinApplication() {
+        Map<String, ResolutionDartType> variables;
+        MixinApplicationElementX mixinElement;
+        ResolutionInterfaceType mixinType;
+        if (lastAndNamed) {
+          mixinElement = element;
+          variables = freeTypes;
+        } else {
+          String signature = computeSignature(signatureIndex);
+          name = supertype.name;
+          int index = name.indexOf("^");
+          if (index != -1) {
+            name = name.substring(0, index);
+          }
+          name = "$name&${mixin.name}$signature";
+          mixinElement = mixinApplicationClasses[name];
+          if (mixinElement != null) return mixinElement.thisType;
+
+          mixinElement = new UnnamedMixinApplicationElementX(
+              name, element, resolution.idGenerator.getNextFreeId(), node);
+          variables = computeTypeVariables(mixinElement, node);
+          mixinElement.setThisAndRawTypes(variables.values.toList());
+          mixinApplicationClasses[name] = mixinElement;
+        }
+
+        if (supertypeArguments.isNotEmpty) {
+          List<ResolutionDartType> supertypeTypeArguments =
+              <ResolutionDartType>[];
+          for (String part in supertypeArguments) {
+            supertypeTypeArguments.add(variables[part]);
+          }
+          supertype = new ResolutionInterfaceType(
+              supertype.element, supertypeTypeArguments);
+        }
+
+        if (lastAndNamed) {
+          mixinType = mixin;
+        } else {
+          List<ResolutionDartType> mixinTypeArguments = <ResolutionDartType>[];
+          for (String part in signatureParts[signatureIndex]) {
+            mixinTypeArguments.add(variables[part]);
+          }
+          mixinType =
+              new ResolutionInterfaceType(mixin.element, mixinTypeArguments);
+        }
+
+        doApplyMixinTo(mixinElement, supertype, mixinType);
+        mixinElement.resolutionState = STATE_DONE;
+        mixinElement.supertypeLoadState = STATE_DONE;
+        return mixinElement.thisType;
+      }
+
+      supertype = createMixinApplication();
+    }
+
+    return new ResolutionInterfaceType(
+        supertype.element, freeTypes.values.toList());
+  }
+
+  ResolutionDartType createMixins(ClassElement element, MixinApplication node,
+      {bool isNamed: false}) {
     ResolutionDartType supertype = resolveSupertype(element, node.superclass);
     Link<Node> link = node.mixins.nodes;
-    while (!link.tail.isEmpty) {
+    while (!link.isEmpty) {
+      if (isNamed && link.tail.isEmpty) {
+        doApplyMixinTo(element, supertype, checkMixinType(link.head));
+        return supertype;
+      }
       supertype = applyMixin(supertype, checkMixinType(link.head), link.head);
       link = link.tail;
     }
-    doApplyMixinTo(element, supertype, checkMixinType(link.head));
-    return element.computeType(resolution);
+    return supertype;
   }
 
   ResolutionDartType applyMixin(
       ResolutionDartType supertype, ResolutionDartType mixinType, Node node) {
     String superName = supertype.name;
     String mixinName = mixinType.name;
     MixinApplicationElementX mixinApplication =
         new UnnamedMixinApplicationElementX("${superName}+${mixinName}",
             element, resolution.idGenerator.getNextFreeId(), node);
     // Create synthetic type variables for the mixin application.
@@ skipping 340 matching lines @@
     Identifier selector = node.selector.asIdentifier();
     var e = prefixElement.lookupLocalMember(selector.source);
     if (e == null || !e.impliesType) {
       reporter.reportErrorMessage(node.selector,
           MessageKind.CANNOT_RESOLVE_TYPE, {'typeName': node.selector});
       return;
     }
     loadSupertype(e, node);
   }
 }