Rewrite mixin application handling in Fasta.

pkg/front_end/lib/src/fasta/kernel/kernel_library_builder.dart

Index: pkg/front_end/lib/src/fasta/kernel/kernel_library_builder.dart
diff --git a/pkg/front_end/lib/src/fasta/kernel/kernel_library_builder.dart b/pkg/front_end/lib/src/fasta/kernel/kernel_library_builder.dart
index f18303f2d1dea629e4c5c4a164dd696c56f35cb3..5df1a4a8351331f0953a5889bd86a9626efe115a 100644
--- a/pkg/front_end/lib/src/fasta/kernel/kernel_library_builder.dart
+++ b/pkg/front_end/lib/src/fasta/kernel/kernel_library_builder.dart
@@ -12,7 +12,8 @@ import '../errors.dart' show internalError;
 
 import '../loader.dart' show Loader;
 
-import '../modifier.dart' show abstractMask, staticMask;
+import '../modifier.dart'
+    show abstractMask, namedMixinApplicationMask, staticMask;
 
 import '../source/source_library_builder.dart'
     show DeclarationBuilder, SourceLibraryBuilder;
@@ -39,7 +40,6 @@ import 'kernel_builder.dart'
         KernelFunctionTypeBuilder,
         KernelInvalidTypeBuilder,
         KernelMixinApplicationBuilder,
-        KernelNamedMixinApplicationBuilder,
         KernelNamedTypeBuilder,
         KernelProcedureBuilder,
         KernelTypeBuilder,
@@ -47,7 +47,7 @@ import 'kernel_builder.dart'
         LibraryBuilder,
         MemberBuilder,
         MetadataBuilder,
-        NamedMixinApplicationBuilder,
+        NamedTypeBuilder,
         PrefixBuilder,
         ProcedureBuilder,
         Scope,
@@ -103,7 +103,7 @@ class KernelLibraryBuilder
       List<KernelTypeBuilder> interfaces,
       int charOffset) {
     // Nested declaration began in `OutlineBuilder.beginClassDeclaration`.
-    var declaration = endNestedDeclaration();
+    var declaration = endNestedDeclaration()..resolveTypes(typeVariables, this);
     assert(declaration.parent == libraryDeclaration);
     Map<String, MemberBuilder> members = declaration.members;
     Map<String, MemberBuilder> constructors = declaration.constructors;
@@ -122,7 +122,8 @@ class KernelLibraryBuilder
         modifiers,
         className,
         typeVariables,
-        applyMixins(supertype),
+        applyMixins(supertype,
+            subclassName: className, typeVariables: typeVariables),
         interfaces,
         classScope,
         constructorScope,
@@ -133,6 +134,13 @@ class KernelLibraryBuilder
     Map<String, TypeVariableBuilder> typeVariablesByName =
         checkTypeVariables(typeVariables, cls);
     void setParent(String name, MemberBuilder member) {
+      while (member != null) {
+        member.parent = cls;
+        member = member.next;
+      }
+    }
+
+    void setParentAndCheckConflicts(String name, MemberBuilder member) {
       if (typeVariablesByName != null) {
         TypeVariableBuilder tv = typeVariablesByName[name];
         if (tv != null) {
@@ -141,16 +149,14 @@ class KernelLibraryBuilder
           cls.addCompileTimeError(tv.charOffset, "This is the type variable.");
         }
       }
-      while (member != null) {
-        member.parent = cls;
-        member = member.next;
-      }
+      setParent(name, member);
     }
 
-    members.forEach(setParent);
-    constructors.forEach(setParent);
+    members.forEach(setParentAndCheckConflicts);
+    constructors.forEach(setParentAndCheckConflicts);
+    // Formally, a setter has the name `id=`, so it can never conflict with a
+    // type variable.
     setters.forEach(setParent);
-    declaration.resolveTypes(typeVariables, this);
     addBuilder(className, cls, charOffset);
   }
 
@@ -168,66 +174,266 @@ class KernelLibraryBuilder
             existing.charOffset, "The other type variable named '${tv.name}'.");
       } else {
         typeVariablesByName[tv.name] = tv;
-        if (tv.name == owner.name) {
-          addCompileTimeError(
-              tv.charOffset,
-              "A type variable can't have the same name as its enclosing "
-              "declaration.");
+        if (owner is ClassBuilder) {

[Johnni Winther, 2017/05/08 10:05:34]

Why is the only for classes? Aren't `typedef F<F>()` and `m<m>() {}` also errors

[ahe, 2017/05/08 11:13:15]

Not according to our tests, and it also seems like the language team is leaning
in the same direction:

https://github.com/dart-lang/sdk/issues/29555

I'll add  a comment about the bug.

+          if (tv.name == owner.name) {
+            addCompileTimeError(
+                tv.charOffset,
+                "A type variable can't have the same name as its enclosing "
+                "declaration.");
+          }
         }
       }
     }
     return typeVariablesByName;
   }
 
-  KernelNamedTypeBuilder removeTypeVariables(KernelNamedTypeBuilder type) {
-    return type.arguments == null
-        ? type
-        : addNamedType(type.name, null, type.charOffset);
-  }
-
   KernelTypeBuilder applyMixin(
-      KernelTypeBuilder supertype, KernelTypeBuilder mixin, String name) {
-    supertype = removeTypeVariables(supertype);
-    mixin = removeTypeVariables(mixin);
+      KernelTypeBuilder supertype, KernelTypeBuilder mixin, String signature,
+      {List<MetadataBuilder> metadata,
+      String name,
+      List<TypeVariableBuilder> typeVariables,
+      int modifiers: abstractMask,
+      List<KernelTypeBuilder> interfaces,
+      int charOffset: -1}) {
     var constructors = <String, MemberBuilder>{};
-    if (name != null) {
-      constructors[""] = new KernelConstructorBuilder(
-          null, 0, null, "", null, null, this, mixin.charOffset, -1, -1, null);
-    }
-    if (name == null) {
-      name = "${supertype.name}&${mixin.name}";
+    bool isNamed = name != null;
+    SourceClassBuilder builder;
+    if (isNamed) {
+      modifiers |= namedMixinApplicationMask;
+    } else {
+      name = supertype.name;
+      int index = name.indexOf("^");
+      if (index != -1) {
+        name = name.substring(0, index);
+      }
+      name = "$name&${mixin.name}$signature";
+      builder = mixinApplicationClasses[name];
     }
-    var builder = mixinApplicationClasses.putIfAbsent(name, () {
-      var builder = new SourceClassBuilder(
-          null, // metadata
-          0, // modifiers
+    if (builder == null) {
+      builder = new SourceClassBuilder(
+          metadata,
+          modifiers,
           name,
-          null, // typeVariables
+          typeVariables,
           supertype,
-          null, // interfaces
+          interfaces,
           new Scope(<String, MemberBuilder>{}, <String, MemberBuilder>{},
-              scope.withTypeVariables(null /* typeVariables */),
+              scope.withTypeVariables(typeVariables),
               isModifiable: false),
           new Scope(constructors, null, null, isModifiable: false),
           this,
           <ConstructorReferenceBuilder>[],
-          -1, // charOffset
+          charOffset,
           null,
           mixin);
-      addBuilder(name, builder, -1 /* charOffset */);
-      return builder;
-    });
-    return new KernelNamedTypeBuilder(name, null, -1 /* charOffset */, fileUri)
-      ..bind(builder);
+      addBuilder(name, builder, charOffset);
+      if (!isNamed) {
+        mixinApplicationClasses[name] = builder;
+      }
+    }
+    return addNamedType(name, <KernelTypeBuilder>[], charOffset)
+      ..bind(isNamed ? builder : null);
   }
 
-  KernelTypeBuilder applyMixins(KernelTypeBuilder type, [String name]) {
+  KernelTypeBuilder applyMixins(KernelTypeBuilder type,
+      {List<MetadataBuilder> metadata,
+      String name,
+      String subclassName,
+      List<TypeVariableBuilder> typeVariables,
+      int modifiers: abstractMask,
+      List<KernelTypeBuilder> interfaces,
+      int charOffset: -1}) {
     if (type is KernelMixinApplicationBuilder) {
+      subclassName ??= name;
+      List<List<String>> signatureParts = <List<String>>[];
+      Map<String, String> unresolved = <String, String>{};
+      Map<String, String> unresolvedReversed = <String, String>{};
+      int unresolvedCount = 0;
+      Map<String, TypeBuilder> freeTypes = <String, TypeBuilder>{};
+
+      if (name == null || type.mixins.length != 1) {
+        TypeBuilder last = type.mixins.last;
+
+        /// 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(TypeBuilder type) {
+          if (name != null && type == last) {
+            // The last mixin of a named mixin application doesn't contribute
+            // to free variables.
+            return;
+          }
+          if (type is NamedTypeBuilder) {
+            List<String> part = <String>[];
+            for (int i = 0; i < (type.arguments?.length ?? 0); i++) {
+              var argument = type.arguments[i];
+              String name;
+              if (argument is NamedTypeBuilder) {
+                if (argument.builder != null) {
+                  int index = typeVariables?.indexOf(argument.builder) ?? -1;
+                  if (index != -1) {
+                    name = "#T${index}";
+                  }
+                } else if (argument.arguments == null) {
+                  name = unresolved[argument.name] ??= "#U${unresolvedCount++}";
+                }
+              }
+              name ??= "#U${unresolvedCount++}";
+              unresolvedReversed[name] = argument.name;
+              freeTypes[name] = argument;
+              part.add(name);
+              type.arguments[i] =
+                  new KernelNamedTypeBuilder(name, null, -1, fileUri);
+            }
+            signatureParts.add(part);
+          }
+        }
+
+        analyzeArguments(type.supertype);
+        type.mixins.forEach(analyzeArguments);
+      }
       KernelTypeBuilder supertype = type.supertype;
+      List<List<String>> currentSignatureParts = <List<String>>[];
+      int currentSignatureCount = 0;
+      String computeSignature() {
+        if (freeTypes.isEmpty) return "";
+        currentSignatureParts.add(signatureParts[currentSignatureCount++]);
+        if (currentSignatureParts.any((l) => l.isNotEmpty)) {
+          return "^${currentSignatureParts.map((l) => l.join('&')).join('^')}";
+        } else {
+          return "";
+        }
+      }
+
+      Map<String, TypeVariableBuilder> computeTypeVariables() {
+        Map<String, TypeVariableBuilder> variables =
+            <String, TypeVariableBuilder>{};
+        for (List<String> strings in currentSignatureParts) {
+          for (String name in strings) {
+            variables[name] ??= addTypeVariable(name, null, -1);
+          }
+        }
+        return variables;
+      }
+
+      checkArguments(t) {
+        for (var argument in t.arguments ?? const []) {
+          if (argument.builder == null && argument.name.startsWith("#")) {
+            throw "No builder on ${argument.name}";
+          }
+        }
+      }
+
+      computeSignature(); // This combines the supertype with the first mixin.
       for (int i = 0; i < type.mixins.length - 1; i++) {
-        supertype = applyMixin(supertype, type.mixins[i], null);
+        Set<String> supertypeArguments = new Set<String>();
+        for (var part in currentSignatureParts) {
+          supertypeArguments.addAll(part);
+        }
+        String signature = computeSignature();
+        var variables = computeTypeVariables();
+        if (supertypeArguments.isNotEmpty) {
+          supertype = addNamedType(
+              supertype.name,
+              supertypeArguments.map((n) {
+                var t = addNamedType(n, null, -1)..bind(variables[n]);

[Johnni Winther, 2017/05/08 10:05:34]

var t = ...
return t;

->

return ...

[ahe, 2017/05/08 11:13:15]

Done.

+                return t;
+              }).toList(),
+              -1);
+        }
+        KernelNamedTypeBuilder mixin = type.mixins[i];
+        for (var type in mixin.arguments ?? const []) {
+          type.bind(variables[type.name]);
+        }
+        checkArguments(supertype);
+        checkArguments(mixin);
+        supertype = applyMixin(supertype, mixin, signature,
+            typeVariables:
+                new List<TypeVariableBuilder>.from(variables.values));
+      }
+      KernelNamedTypeBuilder mixin = type.mixins.last;
+
+      Set<String> supertypeArguments = new Set<String>();
+      for (var part in currentSignatureParts) {
+        supertypeArguments.addAll(part);
+      }
+      String signature = name == null ? computeSignature() : "";
+      var variables;
+      if (name == null) {
+        variables = computeTypeVariables();
+        typeVariables = new List<TypeVariableBuilder>.from(variables.values);
+        if (supertypeArguments.isNotEmpty) {
+          supertype = addNamedType(
+              supertype.name,
+              supertypeArguments.map((n) {
+                var t = addNamedType(n, null, -1)..bind(variables[n]);
+                return t;

[Johnni Winther, 2017/05/08 10:05:34]

Ditto

[ahe, 2017/05/08 11:13:15]

Done.

+              }).toList(),
+              -1);
+        }
+      } else {
+        if (supertypeArguments.isNotEmpty) {
+          supertype = addNamedType(supertype.name,
+              supertypeArguments.map((n) => freeTypes[n]).toList(), -1);
+        }
       }
-      return applyMixin(supertype, type.mixins.last, name);
+
+      if (name == null) {
+        for (var type in mixin.arguments ?? const []) {
+          type.bind(variables[type.name]);
+        }
+      }
+      checkArguments(supertype);
+      checkArguments(mixin);
+
+      KernelNamedTypeBuilder t = applyMixin(supertype, mixin, signature,
+          metadata: metadata,
+          name: name,
+          typeVariables: typeVariables,
+          modifiers: modifiers,
+          interfaces: interfaces,
+          charOffset: charOffset);
+      if (name == null) {
+        var builder = t.builder;
+        t = addNamedType(
+            t.name, freeTypes.keys.map((k) => freeTypes[k]).toList(), -1);
+        if (builder != null) {
+          t.bind(builder);
+        }
+      }
+      return t;
     } else {
       return type;
     }
@@ -242,10 +448,15 @@ class KernelLibraryBuilder
       List<KernelTypeBuilder> interfaces,
       int charOffset) {
     // Nested declaration began in `OutlineBuilder.beginNamedMixinApplication`.
-    var decl = endNestedDeclaration();
-    KernelTypeBuilder supertype = applyMixins(mixinApplication, name);
+    endNestedDeclaration().resolveTypes(typeVariables, this);
+    KernelNamedTypeBuilder supertype = applyMixins(mixinApplication,
+        metadata: metadata,
+        name: name,
+        typeVariables: typeVariables,
+        modifiers: modifiers,
+        interfaces: interfaces,
+        charOffset: charOffset);
     checkTypeVariables(typeVariables, supertype.builder);
-    decl.resolveTypes(typeVariables, this);
   }
 
   void addField(List<MetadataBuilder> metadata, int modifiers,
@@ -634,9 +845,16 @@ class KernelLibraryBuilder
 
   @override
   void includePart(covariant KernelLibraryBuilder part) {
+    part.mixinApplicationClasses
+        .forEach((String name, SourceClassBuilder builder) {
+      SourceClassBuilder existing =
+          mixinApplicationClasses.putIfAbsent(name, () => builder);
+      if (existing != builder) {
+        part.scope.local.remove(name);
+      }
+    });
     super.includePart(part);
     nativeMethods.addAll(part.nativeMethods);
     boundlessTypeVariables.addAll(part.boundlessTypeVariables);
-    assert(mixinApplicationClasses.isEmpty);
   }
 }