Fixes incorrect generic function type capture

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

 // Copyright (c) 2014, 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 engine.element;
 
 import 'dart:collection';
 import 'dart:math' show min;
 
 import 'package:analyzer/src/generated/utilities_general.dart';
@@ skipping 4559 matching lines @@
    * of the function.
    */
   List<ParameterElement> get parameters;
 
   /**
    * Return the type of object returned by this type of function.
    */
   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
    * a subtype of the function type <i>(S<sub>1</sub>, &hellip;, S<sub>n</sub>)
    * &rarr; S</i>, if all of the following conditions are met:
    *
    * * Either
    *   * <i>S</i> is void, or
    *   * <i>T &hArr; S</i>.
    *
@@ skipping 50 matching lines @@
 
   @override
   FunctionType substitute2(
       List<DartType> argumentTypes, List<DartType> parameterTypes);
 
   /**
    * Return the type resulting from substituting the given [argumentTypes] for
    * this type's parameters. This is fully equivalent to
    * `substitute(argumentTypes, getTypeArguments())`.
    */
+  @deprecated // use instantiate
   FunctionType substitute3(List<DartType> argumentTypes);
 }
 
 /**
  * A function type alias (`typedef`).
  */
 abstract class FunctionTypeAliasElement
     implements TypeDefiningElement, TypeParameterizedElement {
   /**
    * An empty array of type alias elements.
@@ skipping 177 matching lines @@
   }
 }
 
 /**
  * The type of a function, method, constructor, getter, or setter.
  */
 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,
    * to avoid creating infinite types in response to self-referential typedefs.
    */
   final List<FunctionTypeAliasElement> prunedTypedefs;
 
   /**
    * Initialize a newly created function type to be declared by the given
    * [element], and also initialize [typeArguments] to match the
    * [typeParameters], which permits later substitution.
    */
   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
    * [element].
    */
   @deprecated // Use new FunctionTypeImpl(element)
   FunctionTypeImpl.con1(ExecutableElement element) : this(element);
 
   /**
    * Initialize a newly created function type to be declared by the given
    * [element].
    */
   @deprecated // Use new FunctionTypeImpl.forTypedef(element)
   FunctionTypeImpl.con2(FunctionTypeAliasElement element)
       : this.forTypedef(element);
 
   /**
    * Initialize a newly created function type to be declared by the given
    * [element].
    */
   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;
   }
 
   /**
    * Return the base parameter elements of this function element.
    */
   List<ParameterElement> get baseParameters {
     Element element = this.element;
     if (element is ExecutableElement) {
       return element.parameters;
     } else {
       return (element as FunctionTypeAliasElement).parameters;
     }
   }
 
   /**
    * Return the return type defined by this function's element.
    */
   DartType get baseReturnType {
     Element element = this.element;
     if (element is ExecutableElement) {
       return element.returnType;
     } else {
       return (element as FunctionTypeAliasElement).returnType;
     }
   }
 
   @override
+  List<TypeParameterElement> get boundTypeParameters => _boundTypeParameters;
+
+  @override
   String get displayName {
     String name = this.name;
     if (name == null || name.length == 0) {
       // Function types have an empty name when they are defined implicitly by
       // either a closure or as part of a parameter declaration.
       List<DartType> normalParameterTypes = this.normalParameterTypes;
       List<DartType> optionalParameterTypes = this.optionalParameterTypes;
       Map<String, DartType> namedParameterTypes = this.namedParameterTypes;
       DartType returnType = this.returnType;
       StringBuffer buffer = new StringBuffer();
@@ skipping 211 matching lines @@
     return (baseReturnType as TypeImpl).substitute2(typeArguments,
         TypeParameterTypeImpl.getTypes(typeParameters), newPrune);
   }
 
   /**
    * A list containing the actual types of the type arguments.
    */
   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) {
     if (object is! FunctionTypeImpl) {
       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) &&
         TypeImpl.equalArrays(
             optionalParameterTypes, otherType.optionalParameterTypes) &&
         _equals(namedParameterTypes, otherType.namedParameterTypes);
   }
 
   @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(", ");
         } else {
           needsComma = true;
         }
         (type as TypeImpl).appendTo(buffer);
       }
     }
-    if (optionalParameterTypes.length > 0) {
+    if (optionalParameterTypes.isNotEmpty) {
       if (needsComma) {
         buffer.write(", ");
         needsComma = false;
       }
       buffer.write("[");
       for (DartType type in optionalParameterTypes) {
         if (needsComma) {
           buffer.write(", ");
         } else {
           needsComma = true;
         }
         (type as TypeImpl).appendTo(buffer);
       }
       buffer.write("]");
       needsComma = true;
     }
-    if (namedParameterTypes.length > 0) {
+    if (namedParameterTypes.isNotEmpty) {
       if (needsComma) {
         buffer.write(", ");
         needsComma = false;
       }
       buffer.write("{");
       namedParameterTypes.forEach((String name, DartType type) {
         if (needsComma) {
           buffer.write(", ");
         } else {
           needsComma = true;
         }
         buffer.write(name);
         buffer.write(": ");
         (type as TypeImpl).appendTo(buffer);
       });
       buffer.write("}");
       needsComma = true;
     }
     buffer.write(")");
     buffer.write(Element.RIGHT_ARROW);
     if (returnType == null) {
       buffer.write("null");
     } else {
       (returnType as TypeImpl).appendTo(buffer);
     }
   }
 
   @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.
     return isSubtypeOf(type);
   }
 
   @override
   bool isMoreSpecificThan(DartType type,
       [bool withDynamic = false, Set<Element> visitedElements]) {
     // Note: visitedElements is only used for breaking recursion in the type
@@ skipping 228 matching lines @@
       return new CircularTypeImpl();
     } else {
       // There should never be a reason to prune a type that has already been
       // pruned, since pruning is only done when expanding a function type
       // alias, and function type aliases are always expanded by starting with
       // base types.
       assert(this.prunedTypedefs == null);
       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);
     }
   }
 
   @override
   DartType substitute2(
       List<DartType> argumentTypes, List<DartType> parameterTypes,
       [List<FunctionTypeAliasElement> prune]) {
     // Pruned types should only ever result from performing type variable
     // substitution, and it doesn't make sense to substitute again after
     // substituting once.
     assert(this.prunedTypedefs == null);
     if (argumentTypes.length != parameterTypes.length) {
       throw new IllegalArgumentException(
           "argumentTypes.length (${argumentTypes.length}) != parameterTypes.length (${parameterTypes.length})");
     }
     Element element = this.element;
     if (prune != null && prune.contains(element)) {
       // Circularity found.  Prune the type declaration.
       return new CircularTypeImpl();
     }
     if (argumentTypes.length == 0) {
       return this.pruned(prune);
     }
     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
   FunctionTypeImpl substitute3(List<DartType> argumentTypes) =>
       substitute2(argumentTypes, typeArguments);
 
   /**
    * Compute the least upper bound of types [f] and [g], both of which are
    * known to be function types.
    *
@@ skipping 807 matching lines @@
    *   to <i>L</i>. Otherwise, we say that the lookup has failed.
    * </blockquote>
    */
   PropertyAccessorElement lookUpSetterInSuperclass(
       String name, LibraryElement library);
 
   @override
   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,
    * getTypeArguments())`.
    */
   InterfaceType substitute4(List<DartType> argumentTypes);
 
   /**
    * Returns a "smart" version of the "least upper bound" of the given types.
    *
@@ skipping 4783 matching lines @@
 
   @override
   void visitElement(Element element) {
     int offset = element.nameOffset;
     if (offset != -1) {
       map[offset] = element;
     }
     super.visitElement(element);
   }
 }