generic method type parameter inference

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

Index: pkg/analyzer/lib/src/generated/type_system.dart
diff --git a/pkg/analyzer/lib/src/generated/type_system.dart b/pkg/analyzer/lib/src/generated/type_system.dart
index ef6bbfb850c955135bc1b0fe7f92937e6a09fa7e..17c7a411213665592a2bfd10e90044e6f41a7874 100644
--- a/pkg/analyzer/lib/src/generated/type_system.dart
+++ b/pkg/analyzer/lib/src/generated/type_system.dart
@@ -6,15 +6,14 @@ library analyzer.src.generated.type_system;
 
 import 'dart:collection';
 
+import 'ast.dart' show Expression;
 import 'element.dart';
 import 'engine.dart' show AnalysisContext;
 import 'resolver.dart' show TypeProvider;
 
 typedef bool _GuardedSubtypeChecker<T>(T t1, T t2, Set<Element> visited);
-
 typedef bool _SubtypeChecker<T>(T t1, T t2);
 
-
 /**
  * Implementation of [TypeSystem] using the strong mode rules.
  * https://github.com/dart-lang/dev_compiler/blob/master/STRONG_MODE.md
@@ -22,6 +21,11 @@ typedef bool _SubtypeChecker<T>(T t1, T t2);
 class StrongTypeSystemImpl implements TypeSystem {
   final _specTypeSystem = new TypeSystemImpl();
 
+  /// If we are currently in a context where we are inferring type parameters
+  /// from arguments to a generic function call, this will be set, otherwise it
+  /// will be null.
+  _TypeParameterBounds _typeParamBounds;

[Brian Wilkerson, 2015/11/19 00:10:17]

Storing temporary state in an instance field seems like an error-prone approach.
Are we sure that we will never need to invoke inferCallFromArguments in the
process of invoking inferCallFromArguments?

[Jennifer Messerly, 2015/11/19 00:25:26]

Yeah, I can change it to pass it down if y'all prefer. It just seemed like a lot
of churn to pass it everywhere (there's a lot of recursion within the *subtypeOf
functions).

Maybe an alternative is to move the *subtypeOf functions to a class, which would
also provide a place to store the "visited" set. 
I think the question is, would we ever invoke inferCallFromArguments from
"isSubtypeOf" ... I certainly hope that is never the case. :)

[Jennifer Messerly, 2015/11/19 01:36:39]

I have an idea how to fix this. Working on it.

[Jennifer Messerly, 2015/11/19 01:43:26]

PTAL, I fixed this by creating a subclass that tracks constraints when we are
inferring. It's not perfect but definitely feels a lot cleaner. Thanks for
catching this.

+
   StrongTypeSystemImpl();
 
   @override
@@ -31,6 +35,118 @@ class StrongTypeSystemImpl implements TypeSystem {
     return _specTypeSystem.getLeastUpperBound(typeProvider, type1, type2);
   }
 
+  /// Given a function type with generic type parameters, infer the type
+  /// parameters from the actual argument types, and return it. If we can't.
+  /// returns the original function type.
+  ///
+  /// Concretely, given a function type with parameter types P0, P1, ... Pn,
+  /// result type R, and generic type parameters T0, T1, ... Tm, use the
+  /// argument types A0, A1, ... An to solve for the type parameters.
+  ///
+  /// For each parameter Pi, we want to ensure that Ai <: Pi. We can do this by
+  /// running the subtype algorithm, and when we reach a type parameter Pj,
+  /// recording the lower or upper bound it must satisfy. At the end, all
+  /// constraints can be combined to determine the type.
+  ///
+  /// As a simplification, we do not actually store all constraints on each type
+  /// parameter Pj. Instead we track Uj and Lj where U is the upper bound and
+  /// L is the lower bound of that type parameter.
+  FunctionType inferCallFromArguments(
+      TypeProvider provider,
+      FunctionTypeImpl fnType,
+      List<DartType> correspondingParameterTypes,
+      List<DartType> argumentTypes) {
+    ExecutableElement element = fnType.element;
+    if (element.typeParameters.isEmpty) {
+      return fnType;
+    }
+
+    assert(_typeParamBounds == null);
+
+    int numParams = element.typeParameters.length;
+    List<DartType> fnTypeParams = fnType.typeArguments;
+    fnTypeParams = fnTypeParams.sublist(0, numParams);
+    for (int i = 0; i < numParams; i++) {
+      if (element.typeParameters[i].type != fnTypeParams[i]) {
+        // Only infer if all of the type parameters are unsubstituted.
+        return fnType;
+      }
+    }
+
+    var typeBounds = new _TypeParameterBounds(
+        provider, new List<TypeParameterType>.from(fnTypeParams));
+
+    for (int i = 0; i < argumentTypes.length; i++) {
+      // Try to pass each argument to each parameter, recording any type
+      // parameter bounds that were implied by this assignment.
+      _typeParamBounds = typeBounds;
+      isSubtypeOf(argumentTypes[i], correspondingParameterTypes[i]);
+      _typeParamBounds = null;
+    }
+
+    // Now we've computed lower and upper bounds for each type parameter.
+    //
+    // To decide on which type to assign, we use the following heuristic.

[Jennifer Messerly, 2015/11/19 00:25:26]

Leaf pointed out that the code doesn't implement this anymore.

At one point I had code for this (probably still there in earlier patch sets),
but it didn't seem to be used in any tests, so I got rid of it. But there is a
test case where it matters (parameter type of returned function). Fixing...

+    //
+    // If the type parameter T appears in a contravariant position, such as
+    // the function's return type, or a parameter to a parameter, then we choose
+    // the lower bound. This lets our "out" type be as precise as possible. For
+    // example, this will allow tools to offer the most useful completions on
+    // the result value:
+    //
+    //     min(1.0, 2.0). // <-- we can pick `double` as T and show completions.
+    //     list.fold(0, (x, y) => x. // <-- we can pick `int` as the type of `x`
+    //                                      and show completions.
+    //
+    // Otherwise, if the type only appears in covariant positions, choose the
+    // upper bound.
+    var inferredTypes = new List<DartType>.from(fnTypeParams, growable: false);
+    for (int i = 0; i < fnTypeParams.length; i++) {
+      TypeParameterType typeParam = fnTypeParams[i];
+      _TypeParameterBound bound = typeBounds._bounds[typeParam];
+
+      // If the type parameter occurs passed out, we'll have an "interesting"
+      // lower bound (i.e. not bottom). Use it. Otherwise use the upper bound.
+      inferredTypes[i] = bound.lower.isBottom ? bound.upper : bound.lower;
+
+      // Assumption: if the current type parameter has an "extends" clause
+      // that refers to another type variable we are inferring, it will appear
+      // before us or in this list position. For example:
+      //
+      //     <TFrom, TTo extends TFrom>
+      //
+      // We may infer TTo is TFrom. In that case, we already know what TFrom
+      // is inferred as, so we can substitute it now. This also handles more
+      // complex cases such as:
+      //
+      //     <TFrom, TTo extends Iterable<TFrom>>
+      //
+      // Or if the type parameter's bound depends on itself such as:
+      //
+      //     <T extends Clonable<T>>
+      inferredTypes[i] =
+          inferredTypes[i].substitute2(inferredTypes, fnTypeParams);
+
+      // See if this actually worked.
+      // If not, fall back to the known upper bound (if any) or `dynamic`.
+      if (inferredTypes[i].isBottom ||
+          !isSubtypeOf(inferredTypes[i],
+              bound.upper.substitute2(inferredTypes, fnTypeParams)) ||
+          !isSubtypeOf(bound.lower.substitute2(inferredTypes, fnTypeParams),
+              inferredTypes[i])) {
+
+        inferredTypes[i] = DynamicTypeImpl.instance;
+        if (typeParam.element.bound != null) {
+          inferredTypes[i] =
+              typeParam.element.bound.substitute2(inferredTypes, fnTypeParams);
+        }
+      }
+    }
+
+    // Return the substituted type.
+    return fnType.substitute2(inferredTypes, fnTypeParams);
+  }
+
   // TODO(leafp): Document the rules in play here
   @override
   bool isAssignableTo(DartType fromType, DartType toType) {
@@ -68,6 +184,9 @@ class StrongTypeSystemImpl implements TypeSystem {
     return _isSubtypeOf(leftType, rightType, null);
   }
 
+  // Given a type t, if t is an interface type with a call method
+  // defined, return the function type for the call method, otherwise
+  // return null.
   FunctionType _getCallMethodType(DartType t) {
     if (t is InterfaceType) {
       return t.lookUpInheritedMethod("call")?.type;
@@ -75,9 +194,6 @@ class StrongTypeSystemImpl implements TypeSystem {
     return null;
   }
 
-  // Given a type t, if t is an interface type with a call method
-  // defined, return the function type for the call method, otherwise
-  // return null.
   _GuardedSubtypeChecker<DartType> _guard(
       _GuardedSubtypeChecker<DartType> check) {
     return (DartType t1, DartType t2, Set<Element> visited) {
@@ -96,6 +212,46 @@ class StrongTypeSystemImpl implements TypeSystem {
     };
   }
 
+  /// If [t1] or [t2] is a type parameter we are inferring, update its bound.
+  /// Returns `true` if we could possibly find a compatible type,
+  /// otherwise `false`.
+  bool _inferTypeParameterSubtypeOf(
+      DartType t1, DartType t2, Set<Element> visited) {
+    if (_typeParamBounds == null) {
+      return false;
+    }
+
+    if (t1 is TypeParameterType) {
+      _TypeParameterBound bound = _typeParamBounds._bounds[t1];
+      if (bound != null) {
+        _GuardedSubtypeChecker<DartType> guardedSubtype = _guard(_isSubtypeOf);
+
+        DartType newUpper = t2;
+        if (guardedSubtype(bound.upper, newUpper, visited)) {
+          // upper bound is already covers this. Nothing to do.
+        } else if (guardedSubtype(newUpper, bound.upper, visited)) {
+          // update to the new, more precise upper bound.
+          bound.upper = newUpper;
+        } else {
+          // Failed to find an upper bound. Use bottom to signal no solution.
+          bound.upper = BottomTypeImpl.instance;
+        }
+        return guardedSubtype(bound.lower, bound.upper, visited);
+      }
+    }
+    if (t2 is TypeParameterType) {
+      _TypeParameterBound bound = _typeParamBounds._bounds[t2];
+      if (bound != null) {
+        _GuardedSubtypeChecker<DartType> guardedSubtype = _guard(_isSubtypeOf);
+
+        TypeProvider tp = _typeParamBounds._typeProvider;
+        bound.lower = getLeastUpperBound(tp, bound.lower, t1);
+        return guardedSubtype(bound.lower, bound.upper, visited);
+      }
+    }
+    return false;
+  }
+
   bool _isBottom(DartType t, {bool dynamicIsBottom: false}) {
     return (t.isDynamic && dynamicIsBottom) || t.isBottom;
   }
@@ -245,6 +401,8 @@ class StrongTypeSystemImpl implements TypeSystem {
       {bool dynamicIsBottom: false}) {
     // Guard recursive calls
     _GuardedSubtypeChecker<DartType> guardedSubtype = _guard(_isSubtypeOf);
+    _GuardedSubtypeChecker<DartType> guardedInferTypeParameter =
+        _guard(_inferTypeParameterSubtypeOf);
 
     if (t1 == t2) {
       return true;
@@ -263,7 +421,7 @@ class StrongTypeSystemImpl implements TypeSystem {
     // Trivially false.
     if (_isTop(t1, dynamicIsBottom: dynamicIsBottom) ||
         _isBottom(t2, dynamicIsBottom: dynamicIsBottom)) {
-      return false;
+      return guardedInferTypeParameter(t1, t2, visited);
     }
 
     // S <: T where S is a type variable
@@ -272,13 +430,15 @@ class StrongTypeSystemImpl implements TypeSystem {
     //  So only true if bound of S is S' and
     //  S' <: T
     if (t1 is TypeParameterType) {
+      if (guardedInferTypeParameter(t1, t2, visited)) {
+        return true;
+      }
       DartType bound = t1.element.bound;
-      if (bound == null) return false;
-      return guardedSubtype(bound, t2, visited);
+      return bound == null ? false : guardedSubtype(bound, t2, visited);
     }
 
     if (t2 is TypeParameterType) {
-      return false;
+      return guardedInferTypeParameter(t1, t2, visited);
     }
 
     if (t1.isVoid || t2.isVoid) {
@@ -316,7 +476,6 @@ class StrongTypeSystemImpl implements TypeSystem {
   }
 }
 
-
 /**
  * The interface `TypeSystem` defines the behavior of an object representing
  * the type system.  This provides a common location to put methods that act on
@@ -449,3 +608,62 @@ class TypeSystemImpl implements TypeSystem {
     return leftType.isSubtypeOf(rightType);
   }
 }
+
+/// An [upper] and [lower] bound for a type variable.
+class _TypeParameterBound {
+  /// The upper bound of the type parameter. In other words, T <: upperBound.
+  ///
+  /// In Dart this can be written as `<T extends UpperBoundType>`.
+  ///
+  /// In inference, this can happen as a result of parameters of function type.
+  /// For example, consider a signature like:
+  ///
+  ///     T reduce<T>(List<T> values, T f(T x, T y));
+  ///
+  /// and a call to it like:
+  ///
+  ///     reduce(values, (num x, num y) => ...);
+  ///
+  /// From the function expression's parameters, we conclude `T <: num`. We may
+  /// still be able to conclude a different [lower] based on `values` or
+  /// the type of the elided `=> ...` body. For example:
+  ///
+  ///      reduce(['x'], (num x, num y) => 'hi');
+  ///
+  /// Here the [lower] will be `String` and the upper bound will be `num`,
+  /// which cannot be satisfied, so this is ill typed.
+  DartType upper = DynamicTypeImpl.instance;
+
+  /// The lower bound of the type parameter. In other words, lowerBound <: T.
+  ///
+  /// This kind of constraint cannot be expressed in Dart, but it applies when
+  /// we're doing inference. For example, consider a signature like:
+  ///
+  ///     T pickAtRandom<T>(T x, T y);
+  ///
+  /// and a call to it like:
+  ///
+  ///     pickAtRandom(1, 2.0)
+  ///
+  /// when we see the first parameter is an `int`, we know that `int <: T`.
+  /// When we see `double` this implies `double <: T`.
+  /// Combining these constraints results in a lower bound of `num`.
+  ///
+  /// In general, we choose the lower bound as our inferred type, so we can
+  /// offer the most constrained (strongest) result type.
+  DartType lower = BottomTypeImpl.instance;
+}
+
+/// Tracks upper and lower type bounds for a set of type parameters.
+class _TypeParameterBounds {
+  final TypeProvider _typeProvider;
+  final Map<TypeParameterType, _TypeParameterBound> _bounds;
+
+  _TypeParameterBounds(
+      this._typeProvider, Iterable<TypeParameterType> typeParams)
+      : _bounds = new Map.fromIterable(typeParams, value: (t) {
+          _TypeParameterBound bound = new _TypeParameterBound();
+          if (t.element.bound != null) bound.upper = t.element.bound;
+          return bound;
+        });
+}