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 (replacing) the given
+   * [argumentTypes] for 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, null, null, null);
 
   /**
    * 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, null, null, null);
 
   /**
    * Private constructor.
    */
-  FunctionTypeImpl._(Element element, String name, this.prunedTypedefs,
-      List<DartType> typeArguments)
+  FunctionTypeImpl._(
+      TypeParameterizedElement element, String name, this.prunedTypedefs,
+      List<DartType> typeArguments,
+      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) {

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

It doesn't seem to have been done before either, but I wonder if it would be
worth having a fast cutoff here when the two objects are identical?  

[Jennifer Messerly, 2015/12/03 19:20:56]

Done.

     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) {

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

I think you're re-inventing Simon Peyton Jones' rapier here.   :)

http://research.microsoft.com/pubs/67490/inline.pdf

I don't think this is 100% right yet though: if you take this approach I think
you need to compute the full free variable set for the type arguments, rather
than just checking for the case that an argument is a type variable.  Consider:

{List<S>/T}<S> S -> T

You want this to print as <S0> S0 -> List<S> rather than <S> S -> List<S>

The other way to tackle this is to provide a source of generativity (e.g. a 64
bit global counter somewhere) and use some encoding scheme (e.g. a character
that is not valid in normal Dart identifiers) to embed a generative tag in the
variable name.

[Jennifer Messerly, 2015/12/03 19:20:56]

DOH. You're right... I was hoping not to have to visit into anything as it's
slightly annoying to do. Wishful thinking got the better of me :)

BTW, considered the global counter -- it would definitely work but it seems like
the numbers could get quite large. Not sure how odd that would look as we don't
do it anywhere else. Certainly many languages are willing to include ID's in
their toStrings, e.g. Python and Ruby:
|>>> object()
<object object at 0x1015fd090>

irb(main):001:0> Object.new
=> #<Object:0x007f8d02007508>

[Jennifer Messerly, 2015/12/03 22:48:07]

Done.

+        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) {
+    if (argumentTypes.length != boundTypeParameters.length) {
+      throw new IllegalArgumentException(
+          "argumentTypes.length (${argumentTypes.length}) != "
+          "boundTypeParameters.length (${boundTypeParameters.length})");
+    }
+    if (argumentTypes.isEmpty) {
+      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): introduce a new "instantiate" and deprecate this.
+  // The new "instantiate" should work similar to FunctionType.instantiate,
+  // which uses [boundTypeParameters] to model type parameters that haven't been
+  // filled in yet. Those are kept separate from already-substituted type
+  // parameters or free variables from the enclosing scopes, which allows nested
+  // generics to work, such as a generic method in a generic class.
   /**
    * 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 4779 matching lines @@
 
   @override
   void visitElement(Element element) {
     int offset = element.nameOffset;
     if (offset != -1) {
       map[offset] = element;
     }
     super.visitElement(element);
   }
 }