Fixes incorrect generic function type capture

pkg/analyzer/lib/src/generated/element.dart

Index: pkg/analyzer/lib/src/generated/element.dart
diff --git a/pkg/analyzer/lib/src/generated/element.dart b/pkg/analyzer/lib/src/generated/element.dart
index b379ebd913810fd0c5c276cd4a04b07fcbddde58..8102be6e6b3ed39b067858cdbfeafd9828ab4643 100644
--- a/pkg/analyzer/lib/src/generated/element.dart
+++ b/pkg/analyzer/lib/src/generated/element.dart
@@ -4577,6 +4577,21 @@ abstract class FunctionType implements ParameterizedType {
   DartType get returnType;
 
   /**
+   * The type parameters of this generic function. For example `<T> T -> T`.
+   *
+   * These are distinct from the [typeParameters] list, which contains type
+   * parameters from surrounding contexts, and thus are free type variables from
+   * the perspective of this function type.
+   */
+  List<TypeParameterElement> get boundTypeParameters;
+
+  /**
+   * Return the type resulting from instantiating the given [argumentTypes] for

[Brian Wilkerson, 2015/12/03 15:03:17]

"instantiating" --> "instantiating (replacing)"?

[Jennifer Messerly, 2015/12/03 17:35:04]

Done. Yeah I wondered if there was a better name for this method...

[Brian Wilkerson, 2015/12/03 17:42:16]

Me too. I think of "instantiate" as "create an instance of a class", but if it's
commonly used terminology in type theory, then I'm ok with it.

[Leaf, 2015/12/03 18:46:35]

Yeah, instantiate is the most common term that I know of - it's actually almost
by analogy of creating an instance of a class: the universal type is like a
template from which you stamp out particular concrete instances.  Other
possibilities might be "reduce" or "apply", "makeConcrete"?  I'm not coming up
with anything else I like very much right now.

+   * this function's bound type parameters.
+   */
+  FunctionType instantiate(List<DartType> argumentTypes);
+
+  /**
    * Return `true` if this type is a subtype of the given [type].
    *
    * A function type <i>(T<sub>1</sub>, &hellip;, T<sub>n</sub>) &rarr; T</i> is
@@ -4647,6 +4662,7 @@ abstract class FunctionType implements ParameterizedType {
    * this type's parameters. This is fully equivalent to
    * `substitute(argumentTypes, getTypeArguments())`.
    */
+  @deprecated // use instantiate
   FunctionType substitute3(List<DartType> argumentTypes);
 }
 
@@ -4844,7 +4860,17 @@ class FunctionTypeImpl extends TypeImpl implements FunctionType {
   /**
    * The list of [typeArguments].
    */
-  List<DartType> _typeArguments = DartType.EMPTY_LIST;
+  List<DartType> _typeArguments;
+
+  /**
+   * The list of [typeParameters].
+   */
+  List<TypeParameterElement> _typeParameters;
+
+  /**
+   * The list of [boundTypeParameters].
+   */
+  List<TypeParameterElement> _boundTypeParameters;
 
   /**
    * The set of typedefs which should not be expanded when exploring this type,
@@ -4859,7 +4885,7 @@ class FunctionTypeImpl extends TypeImpl implements FunctionType {
    */
   FunctionTypeImpl(ExecutableElement element,
       [List<FunctionTypeAliasElement> prunedTypedefs])
-      : this._(element, null, prunedTypedefs, null);
+      : this._(element, null, prunedTypedefs);
 
   /**
    * Initialize a newly created function type to be declared by the given
@@ -4882,29 +4908,49 @@ class FunctionTypeImpl extends TypeImpl implements FunctionType {
    */
   FunctionTypeImpl.forTypedef(FunctionTypeAliasElement element,
       [List<FunctionTypeAliasElement> prunedTypedefs])
-      : this._(element, element?.name, prunedTypedefs, null);
+      : this._(element, element?.name, prunedTypedefs);
 
   /**
    * Private constructor.
    */
-  FunctionTypeImpl._(Element element, String name, this.prunedTypedefs,
-      List<DartType> typeArguments)
+  FunctionTypeImpl._(
+      TypeParameterizedElement element, String name, this.prunedTypedefs,
+      [List<DartType> typeArguments,

[Brian Wilkerson, 2015/12/03 15:03:17]

It might be better to leave these as required arguments, given that it's a
private constructor and only the last argument (as far as I can see) is ever
omitted.

[Jennifer Messerly, 2015/12/03 17:35:04]

Done. Yeah I can just pass the 3 null's explicitly above.

+      List<TypeParameterElement> typeParameters,
+      List<TypeParameterElement> boundTypeParameters])
       : super(element, name) {
-    if (typeArguments != null) {
-      _typeArguments = typeArguments;
-    } else {
-      List<TypeParameterElement> typeParameters = this.typeParameters;
+    _boundTypeParameters = boundTypeParameters ??
+        element?.typeParameters ??
+        TypeParameterElement.EMPTY_LIST;
+
+    if (typeParameters == null) {
+      // Combine the generic type variables from all enclosing contexts, except
+      // for this generic function's type variables. Those variables are
+      // tracked in [boundTypeParameters].
+      typeParameters = <TypeParameterElement>[];
+      Element e = element?.enclosingElement;
+      while (e != null) {
+        if (e is TypeParameterizedElement) {
+          typeParameters.addAll((e as TypeParameterizedElement).typeParameters);
+        }
+        e = e.enclosingElement;
+      }
+    }
+    _typeParameters = typeParameters;
+
+    if (typeArguments == null) {
       // TODO(jmesserly): reuse TypeParameterTypeImpl.getTypes once we can
       // make it generic, which will allow it to return List<DartType> instead
       // of List<TypeParameterType>.
       if (typeParameters.isEmpty) {
-        _typeArguments = DartType.EMPTY_LIST;
+        typeArguments = DartType.EMPTY_LIST;
       } else {
-        _typeArguments = new List<DartType>.from(
+        typeArguments = new List<DartType>.from(
             typeParameters.map((t) => t.type),
             growable: false);
       }
     }
+    _typeArguments = typeArguments;
   }
 
   /**
@@ -4932,6 +4978,9 @@ class FunctionTypeImpl extends TypeImpl implements FunctionType {
   }
 
   @override
+  List<TypeParameterElement> get boundTypeParameters => _boundTypeParameters;
+
+  @override
   String get displayName {
     String name = this.name;
     if (name == null || name.length == 0) {
@@ -5163,18 +5212,7 @@ class FunctionTypeImpl extends TypeImpl implements FunctionType {
   List<DartType> get typeArguments => _typeArguments;
 
   @override
-  List<TypeParameterElement> get typeParameters {
-    // Combine the generic type arguments from all enclosing contexts.
-    // For example, this could be a generic method in a class, or a local
-    // function within another function.
-    List<TypeParameterElement> typeParams = <TypeParameterElement>[];
-    for (Element e = element; e != null; e = e.enclosingElement) {
-      if (e is TypeParameterizedElement) {
-        typeParams.addAll(e.typeParameters);
-      }
-    }
-    return typeParams;
-  }
+  List<TypeParameterElement> get typeParameters => _typeParameters;
 
   @override
   bool operator ==(Object object) {
@@ -5182,6 +5220,24 @@ class FunctionTypeImpl extends TypeImpl implements FunctionType {
       return false;
     }
     FunctionTypeImpl otherType = object as FunctionTypeImpl;
+    if (boundTypeParameters.length != otherType.boundTypeParameters.length) {
+      return false;
+    }
+    // `<T>T -> T` should be equal to `<U>U -> U`
+    // To test this, we instantiate both types with the same (unique) type
+    // variables, and see if the result is equal.
+    if (boundTypeParameters.isNotEmpty) {
+      List<DartType> instantiateTypeArgs = new List<DartType>();
+      for (TypeParameterElement e in boundTypeParameters) {
+        instantiateTypeArgs.add(new TypeParameterTypeImpl(
+            new TypeParameterElementImpl(e.name, -1)));
+      }
+      // After instantiation, they will no longer have boundTypeParameters,
+      // so we will continue below.
+      return this.instantiate(instantiateTypeArgs) ==
+          otherType.instantiate(instantiateTypeArgs);
+    }
+
     return returnType == otherType.returnType &&
         TypeImpl.equalArrays(
             normalParameterTypes, otherType.normalParameterTypes) &&
@@ -5192,13 +5248,53 @@ class FunctionTypeImpl extends TypeImpl implements FunctionType {
 
   @override
   void appendTo(StringBuffer buffer) {
+    if (boundTypeParameters.isNotEmpty) {
+      // To print a type with type variables, first make sure we have unique
+      // variable names to print.
+      Set<String> namesToAvoid = new HashSet<String>();
+      for (DartType arg in typeArguments) {
+        if (arg is TypeParameterType) {
+          namesToAvoid.add(arg.displayName);
+        }
+      }
+
+      List<DartType> instantiateTypeArgs = new List<DartType>();
+      buffer.write("<");
+      for (TypeParameterElement e in boundTypeParameters) {
+        if (e != boundTypeParameters[0]) {
+          buffer.write(",");
+        }
+        String name = e.name;
+        int counter = 0;
+        while (!namesToAvoid.add(name)) {
+          // Unicode subscript-zero is U+2080, zero is U+0030. Other digits
+          // are sequential from there. Thus +0x2050 will get us the subscript.
+          String subscript = new String.fromCharCodes(
+              counter.toString().codeUnits.map((n) => n + 0x2050));
+
+          name = e.name + subscript;
+          counter++;
+        }
+        TypeParameterTypeImpl t =
+            new TypeParameterTypeImpl(new TypeParameterElementImpl(name, -1));
+        t.appendTo(buffer);
+        instantiateTypeArgs.add(t);
+      }
+      buffer.write(">");
+
+      // Instantiate it and print the resulting type. After instantiation, it
+      // will no longer have boundTypeParameters, so we will continue below.
+      this.instantiate(instantiateTypeArgs).appendTo(buffer);
+      return;
+    }
+
     List<DartType> normalParameterTypes = this.normalParameterTypes;
     List<DartType> optionalParameterTypes = this.optionalParameterTypes;
     Map<String, DartType> namedParameterTypes = this.namedParameterTypes;
     DartType returnType = this.returnType;
     buffer.write("(");
     bool needsComma = false;
-    if (normalParameterTypes.length > 0) {
+    if (normalParameterTypes.isNotEmpty) {
       for (DartType type in normalParameterTypes) {
         if (needsComma) {
           buffer.write(", ");
@@ -5208,7 +5304,7 @@ class FunctionTypeImpl extends TypeImpl implements FunctionType {
         (type as TypeImpl).appendTo(buffer);
       }
     }
-    if (optionalParameterTypes.length > 0) {
+    if (optionalParameterTypes.isNotEmpty) {
       if (needsComma) {
         buffer.write(", ");
         needsComma = false;
@@ -5225,7 +5321,7 @@ class FunctionTypeImpl extends TypeImpl implements FunctionType {
       buffer.write("]");
       needsComma = true;
     }
-    if (namedParameterTypes.length > 0) {
+    if (namedParameterTypes.isNotEmpty) {
       if (needsComma) {
         buffer.write(", ");
         needsComma = false;
@@ -5254,6 +5350,35 @@ class FunctionTypeImpl extends TypeImpl implements FunctionType {
   }
 
   @override
+  FunctionTypeImpl instantiate(List<DartType> argumentTypes) {
+    List<TypeParameterType> parameterTypes =
+        TypeParameterTypeImpl.getTypes(boundTypeParameters);
+    if (argumentTypes.length != parameterTypes.length) {
+      throw new IllegalArgumentException(
+          "argumentTypes.length (${argumentTypes.length}) != "
+          "boundTypeParameters.length (${boundTypeParameters.length})");
+    }
+    if (argumentTypes.isEmpty) {

[Brian Wilkerson, 2015/12/03 15:03:17]

How often will argumentTypes be empty? If it's often enough, then waiting this
long to bail has a performance cost. Performance would be better if we checked
this condition before computing the parameterTypes, but it would allow some
error conditions to go unnoticed. Could we use "boundTypeParameters.length"
rather than "parameterTypes.length" in the previous 'if' statement? (Of course,
if it's not often enough, then the performance hit won't matter.)

[Jennifer Messerly, 2015/12/03 17:35:04]

Good call. Done! In fact I don't even need parameterTypes...think that was
something I forgot to clean up.

+      return this;
+    }
+
+    // Given:
+    //     {U/T} <S> T -> S
+    // Where {U/T} represents the typeArguments (U) and typeParameters (T) list,
+    // and <S> represents the boundTypeParameters.
+    //
+    // Now instantiate([V]), and the result should be:
+    //     {U/T, V/S} T -> S.
+    List<TypeParameterElement> newTypeParams = typeParameters.toList();
+    List<DartType> newTypeArgs = typeArguments.toList();
+    newTypeParams.addAll(boundTypeParameters);
+    newTypeArgs.addAll(argumentTypes);
+
+    return new FunctionTypeImpl._(element, name, prunedTypedefs, newTypeArgs,
+        newTypeParams, TypeParameterElement.EMPTY_LIST);
+  }
+
+  @override
   bool isAssignableTo(DartType type) {
     // A function type T may be assigned to a function type S, written T <=> S,
     // iff T <: S.
@@ -5502,7 +5627,8 @@ class FunctionTypeImpl extends TypeImpl implements FunctionType {
       List<DartType> typeArgs = typeArguments
           .map((TypeImpl t) => t.pruned(prune))
           .toList(growable: false);
-      return new FunctionTypeImpl._(element, name, prune, typeArgs);
+      return new FunctionTypeImpl._(element, name, prune, typeArgs,
+          _typeParameters, _boundTypeParameters);
     }
   }
 
@@ -5528,7 +5654,8 @@ class FunctionTypeImpl extends TypeImpl implements FunctionType {
     }
     List<DartType> typeArgs =
         TypeImpl.substitute(typeArguments, argumentTypes, parameterTypes);
-    return new FunctionTypeImpl._(element, name, prune, typeArgs);
+    return new FunctionTypeImpl._(
+        element, name, prune, typeArgs, _typeParameters, _boundTypeParameters);
   }
 
   @override
@@ -6356,6 +6483,7 @@ abstract class InterfaceType implements ParameterizedType {
   InterfaceType substitute2(
       List<DartType> argumentTypes, List<DartType> parameterTypes);
 
+  // TODO(jmesserly): rename this to instantiate?

[Brian Wilkerson, 2015/12/03 15:03:17]

I like the idea of having a consistent nomenclature. It would be especially nice
if we could design the 'instantiate' method so that we only needed one of them
(unlike the current mess with 'substituteN'). Maybe as a follow-on CL.

[Jennifer Messerly, 2015/12/03 17:35:04]

+1 yeah ... I'll expand the comment, seems like this method should become
"instantiate" and we should likewise have a boundTypeParameters field for
interface types, so there's a symmetry there.

I feel like that would make sense, given:

    class C<T> { T method1() { ... } T method2(T t) { ... } }

that's sort of like: <T> ( method1: () -> T, method2: T -> T, .... )

once you instantiate it becomes:

    {int/T}( method1: () -> T, method2: T -> T, ... )

It wouldn't really change any end-user-observable behavior since classes can't
be nested right now. But if we did get nested classes the distinction would
suddenly make sense. And it would make the API behavior more consistent between
FunctionType/InterfaceType.


@Leaf & Brian, does the above seem right to y'all?

[Brian Wilkerson, 2015/12/03 17:42:16]

It seems consistent to me. I'm fine with postponing that work until a future CL
if you want.

[Leaf, 2015/12/03 18:46:35]

Agreed, I think instantiate would be a good choice here.

   /**
    * Return the type resulting from substituting the given arguments for this
    * type's parameters. This is fully equivalent to `substitute2(argumentTypes,