fix #27256, track type bounds for generic functions

pkg/dev_compiler/tool/input_sdk/private/ddc_runtime/types.dart

Index: pkg/dev_compiler/tool/input_sdk/private/ddc_runtime/types.dart
diff --git a/pkg/dev_compiler/tool/input_sdk/private/ddc_runtime/types.dart b/pkg/dev_compiler/tool/input_sdk/private/ddc_runtime/types.dart
index 5e50cbc9e313f7a667b00c3a8b638c7913e529c5..40ab74d8fbf08b51242c71833440bf450bb6560f 100644
--- a/pkg/dev_compiler/tool/input_sdk/private/ddc_runtime/types.dart
+++ b/pkg/dev_compiler/tool/input_sdk/private/ddc_runtime/types.dart
@@ -247,7 +247,7 @@ _normalizeParameter(a) => JS(
   return ($a == $dynamic) ? $bottom : $a;
 })()''');
 
-_canonicalizeArray(definite, array, map) => JS(
+List _canonicalizeArray(definite, array, map) => JS(
     '',
     '''(() => {
   let arr = ($definite)
@@ -305,8 +305,8 @@ _createSmall(count, definite, returnType, required) => JS(
 
 class FunctionType extends AbstractFunctionType {
   final returnType;
-  dynamic args;
-  dynamic optionals;
+  List args;
+  List optionals;
   final named;
   dynamic metadata;
   String _stringValue;
@@ -328,7 +328,7 @@ class FunctionType extends AbstractFunctionType {
    * that all instances will share.
    *
    */
-  static create(definite, returnType, args, extra) {
+  static create(definite, returnType, List args, extra) {
     // Note that if extra is ever passed as an empty array
     // or an empty map, we can end up with semantically
     // identical function types that don't canonicalize
@@ -356,7 +356,7 @@ class FunctionType extends AbstractFunctionType {
     return _memoizeArray(_fnTypeTypeMap, keys, create);
   }
 
-  _process(array, metadata) {
+  List _process(List array, metadata) {
     var result = [];
     for (var i = 0; JS('bool', '# < #.length', i, array); ++i) {
       var arg = JS('', '#[#]', array, i);
@@ -438,9 +438,12 @@ class Typedef extends AbstractFunctionType {
   }
 }
 
+/// A type variable, used by [GenericFunctionType] to represent a type formal.
 class TypeVariable extends TypeRep {
   final String name;
+
   TypeVariable(this.name);
+
   toString() => name;
 }
 
@@ -448,29 +451,39 @@ class GenericFunctionType extends AbstractFunctionType {
   final bool definite;
   final _instantiateTypeParts;
   final int formalCount;
-  var _typeFormals;
+  final _instantiateTypeBounds;
+  List<TypeVariable> _typeFormals;
 
-  GenericFunctionType(this.definite, instantiateTypeParts)
+  GenericFunctionType(
+      this.definite, instantiateTypeParts, this._instantiateTypeBounds)
       : _instantiateTypeParts = instantiateTypeParts,
         formalCount = JS('int', '#.length', instantiateTypeParts);
 
-  get typeFormals {
+  List<TypeVariable> get typeFormals {
     if (_typeFormals != null) return _typeFormals;
 
     // Extract parameter names from the function parameters.
     //
     // This is not robust in general for user-defined JS functions, but it
     // should handle the functions generated by our compiler.
-    var str = JS('', '#.toString()', _instantiateTypeParts);
-    var match = JS('', r'#.match(/\(([^)]*)\)/)', str);
-    if (match != null) {
-      var names = JS('', r'#[1].split(",")', match);
-      return _typeFormals = JS('',
-          '#.map(function(s) { return new #(s.trim()) })', names, TypeVariable);
+    //
+    // TODO(jmesserly): names of TypeVariables are only used for display
+    // purposes, such as when an error happens or if someone calls
+    // `Type.toString()`. So we could recover them lazily rather than eagerly.
+    // Alternatively we could synthesize new names.
+    var str = JS('String', '#.toString()', _instantiateTypeParts);
+    var hasParens = str[0] == '(';
+    var end = str.indexOf(hasParens ? ')' : '=>');
+    if (hasParens) {
+      _typeFormals = str
+          .substring(1, end)
+          .split(',')
+          .map((n) => new TypeVariable(n.trim()))
+          .toList();
     } else {
-      var name = JS('', r'#.match(/([^=]*)=>/)[1]', str);
-      return _typeFormals = JS('', '[new #(#.trim())]', TypeVariable, name);
+      _typeFormals = [new TypeVariable(str.substring(0, end).trim())];
     }
+    return _typeFormals;
   }
 
   instantiate(typeArgs) {
@@ -479,44 +492,148 @@ class GenericFunctionType extends AbstractFunctionType {
         parts, parts, parts);
   }
 
+  List instantiateTypeBounds(List typeArgs) {
+    var boundsFn = _instantiateTypeBounds;
+    if (boundsFn == null) {
+      // The Dart 1 spec says omitted type parameters have an upper bound of
+      // Object. However strong mode assumes `dynamic` for all purposes
+      // (such as instantiate to bounds) so we use that here.
+      return new List.filled(formalCount, _dynamic);
+    }
+    // If bounds are recursive, we need to apply type formals and return them.
+    return JS('List', '#.apply(null, #)', boundsFn, typeArgs);
+  }
+
   toString() {
-    return JS('', '"<" + #.join(", ") + ">" + #.toString()', typeFormals,
-        instantiate(typeFormals));
+    String s = "<";
+    var typeFormals = this.typeFormals;
+    var typeBounds = instantiateTypeBounds(typeFormals);
+    for (int i = 0, n = typeFormals.length; i < n; i++) {
+      if (i != 0) s += ", ";
+      s += JS('String', '#[#].name', typeFormals, i);
+      var typeBound = typeBounds[i];
+      if (!identical(typeBound, _dynamic)) {
+        s += " extends $typeBound";
+      }
+    }
+    s += ">" + instantiate(typeFormals).toString();
+    return s;
   }
-}
 
-typedef(name, /*FunctionTypeClosure*/ closure) {
-  return new Typedef(name, closure);
-}
+  /// Given a [DartType] [type], if [type] is an uninstantiated
+  /// parameterized type then instantiate the parameters to their
+  /// bounds and return those type arguments.
+  ///
+  /// See the issue for the algorithm description:
+  /// <https://github.com/dart-lang/sdk/issues/27526#issuecomment-260021397>
+  List instantiateDefaultBounds() {
+    var typeFormals = this.typeFormals;
+
+    // All type formals
+    var all = new HashMap<Object, int>.identity();
+    // ground types, by index.
+    //
+    // For each index, this will be a ground type for the corresponding type
+    // formal if known, or it will be the original TypeVariable if we are still
+    // solving for it. This array is passed to `instantiateToBounds` as we are
+    // progressively solving for type variables.
+    var defaults = new List<Object>(typeFormals.length);
+    // not ground
+    var partials = new Map<TypeVariable, Object>.identity();
+
+    var typeBounds = this.instantiateTypeBounds(typeFormals);
+    for (var i = 0; i < typeFormals.length; i++) {
+      var typeFormal = typeFormals[i];
+      var bound = typeBounds[i];
+      all[typeFormal] = i;
+      if (identical(bound, _dynamic)) {
+        defaults[i] = bound;
+      } else {
+        defaults[i] = typeFormal;
+        partials[typeFormal] = bound;
+      }
+    }
 
-_functionType(definite, returnType, args, extra) => JS(
-    '',
-    '''(() => {
-  if ($args === void 0 && $extra === void 0) {
-    return new $GenericFunctionType($definite, $returnType);
+    bool hasFreeFormal(Object t) {
+      if (partials.containsKey(t)) return true;
+
+      // Generic classes and typedefs.
+      var typeArgs = getGenericArgs(t);
+      if (typeArgs != null) return typeArgs.any(hasFreeFormal);
+
+      if (t is GenericFunctionType) {
+        return hasFreeFormal(t.instantiate(t.typeFormals));
+      }
+
+      if (t is FunctionType) {
+        return hasFreeFormal(t.returnType) || t.args.any(hasFreeFormal);
+      }
+
+      return false;
+    }
+
+    var hasProgress = true;
+    while (hasProgress) {
+      hasProgress = false;
+      for (var typeFormal in partials.keys) {
+        var partialBound = partials[typeFormal];
+        if (!hasFreeFormal(partialBound)) {
+          int index = all[typeFormal];
+          defaults[index] = instantiateTypeBounds(defaults)[index];
+          partials.remove(typeFormal);
+          hasProgress = true;
+          break;
+        }
+      }
+    }
+
+    // If we stopped making progress, and not all types are ground,
+    // then the whole type is malbounded and an error should be reported
+    // if errors are requested, and a partially completed type should
+    // be returned.
+    if (partials.isNotEmpty) {
+      throwStrongModeError('Instantiate to bounds failed for type with '
+          'recursive generic bounds: ${typeName(this)}. '
+          'Try passing explicit type arguments.');
+    }
+
+    return defaults;
   }
-  return $FunctionType.create($definite, $returnType, $args, $extra);
-})()''');
+}
 
+typedef(name, closure) => new Typedef(name, closure);
+
+/// Create a definite function type.
 ///
-/// Create a "fuzzy" function type.  If any arguments are dynamic
-/// they will be replaced with bottom.
+/// No substitution of dynamic for bottom occurs.
+fnType(returnType, List args, extra) =>
+    FunctionType.create(true, returnType, args, extra);
+
+/// Create a "fuzzy" function type.
 ///
-functionType(returnType, args, extra) =>
-    _functionType(false, returnType, args, extra);
+/// If any arguments are dynamic they will be replaced with bottom.
+fnTypeFuzzy(returnType, List args, extra) =>
+    FunctionType.create(false, returnType, args, extra);
 
+/// Creates a definite generic function type.
 ///
-/// Create a definite function type. No substitution of dynamic for
-/// bottom occurs.
+/// A function type consists of two things: an instantiate function, and an
+/// function that returns a list of upper bound constraints for each
+/// the type formals. Both functions accept the type parameters, allowing us
+/// to substitute values. The upper bound constraints can be omitted if all
+/// of the type parameters use the default upper bound.
 ///
-definiteFunctionType(returnType, args, extra) =>
-    _functionType(true, returnType, args, extra);
+/// For example given the type <T extends Iterable<T>>(T) -> T, we can declare
+/// this type with `gFnType(T => [T, [T]], T => [Iterable$(T)])`.\
+gFnType(instantiateFn, typeBounds) =>
+    new GenericFunctionType(true, instantiateFn, typeBounds);
+
+gFnTypeFuzzy(instantiateFn, typeBounds) =>
+    new GenericFunctionType(false, instantiateFn, typeBounds);
 
-///
 /// TODO(vsm): Remove when mirrors is deprecated.
 /// This is a temporary workaround to support dart:mirrors, which doesn't
 /// understand generic methods.
-///
 getFunctionTypeMirror(AbstractFunctionType type) {
   if (type is GenericFunctionType) {
     var typeArgs = new List.filled(type.formalCount, dynamic);
@@ -525,11 +642,7 @@ getFunctionTypeMirror(AbstractFunctionType type) {
   return type;
 }
 
-bool isType(obj) => JS(
-    '',
-    '''(() => {
-  return $_getRuntimeType($obj) === $Type;
-  })()''');
+bool isType(obj) => JS('', '# === #', _getRuntimeType(obj), Type);
 
 String typeName(type) => JS(
     '',
@@ -796,15 +909,32 @@ _isSubtype(t1, t2, isCovariant) => JS(
     //
     // where TFresh is a list of fresh type variables that both g1 and g2 will
     // be instantiated with.
-    //
-    // NOTE: this should also verify the bounds of the type parameters of g1
-    // and g2 , but it does not, see this issue:
-    // https://github.com/dart-lang/sdk/issues/27256
     if ($t1.formalCount !== $t2.formalCount) return false;
 
     // Using either function's type formals will work as long as they're both
-    // instantiated with the same ones.
+    // instantiated with the same ones. The instantiate operation is guaranteed
+    // to avoid capture because it does not depend on its TypeVariable objects,
+    // rather it uses JS function parameters to ensure correct binding.
     let fresh = $t2.typeFormals;
+
+    // Check the bounds of the type parameters of g1 and g2.
+    // given a type parameter `T1 extends U1` from g1, and a type parameter
+    // `T2 extends U2` from g2, we must ensure that:
+    //
+    //      U2 <: U1
+    //
+    // (Note the reversal of direction -- type formal bounds are contravariant,
+    // similar to the function's formal parameter types).
+    //
+    let t1Bounds = $t1.instantiateTypeBounds(fresh);
+    let t2Bounds = $t2.instantiateTypeBounds(fresh);
+    // TODO(jmesserly): we could optimize for the common case of no bounds.
+    for (let i = 0; i < $t1.formalCount; i++) {
+      if (!$_isSubtype(t2Bounds[i], t1Bounds[i], !$isCovariant)) {
+        return false;
+      }
+    }
+
     return $isFunctionSubtype(
         $t1.instantiate(fresh), $t2.instantiate(fresh), $isCovariant);
   }