fixes #27586, prefer context type in generic 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 b951f4f4dff2f4099045d17b8f5858af7ee0475e..a599dfac29e89ffb86a9298b43b50388dec7ca56 100644
--- a/pkg/analyzer/lib/src/generated/type_system.dart
+++ b/pkg/analyzer/lib/src/generated/type_system.dart
@@ -8,7 +8,7 @@ import 'dart:collection';
 import 'dart:math' as math;
 
 import 'package:analyzer/dart/ast/ast.dart' show AstNode;
-import 'package:analyzer/dart/ast/token.dart' show TokenType;
+import 'package:analyzer/dart/ast/token.dart' show Keyword, TokenType;
 import 'package:analyzer/dart/element/element.dart';
 import 'package:analyzer/dart/element/type.dart';
 import 'package:analyzer/error/listener.dart' show ErrorReporter;
@@ -204,7 +204,7 @@ class StrongTypeSystemImpl extends TypeSystem {
    * Given a generic function type `F<T0, T1, ... Tn>` and a context type C,
    * infer an instantiation of F, such that `F<S0, S1, ..., Sn>` <: C.
    *
-   * This is similar to [inferGenericFunctionCall], but the return type is also
+   * This is similar to [inferGenericFunctionOrType], but the return type is also
    * considered as part of the solution.
    *
    * If this function is called with a [contextType] that is also
@@ -212,7 +212,8 @@ class StrongTypeSystemImpl extends TypeSystem {
    * no effect and return [fnType].
    */
   FunctionType inferFunctionTypeInstantiation(
-      FunctionType contextType, FunctionType fnType) {
+      FunctionType contextType, FunctionType fnType,
+      {ErrorReporter errorReporter, AstNode errorNode}) {
     if (contextType.typeFormals.isNotEmpty || fnType.typeFormals.isEmpty) {

[Leaf, 2017/02/17 06:41:21]

Not new to this CL, but in passing I think this is kind of wrong.

S Function<T>(T x) f<S>();

int Function<T>(T x) f = f();  

Seems like it should work, and I think this will cause it to bail out.  Am I
wrong?   

If not, maybe TODO it?

Also, do you know what the check that the context type is not generic is
supposed to catch here?

[Jennifer Messerly, 2017/03/14 02:07:07]

I don't understand your example.
Since this is not related to the CL can we take it offline?

       return fnType;
     }
@@ -228,29 +229,25 @@ class StrongTypeSystemImpl extends TypeSystem {
     // formals as we check the parameters and return type.
     var inferFnType =
         fnType.instantiate(TypeParameterTypeImpl.getTypes(fnType.typeFormals));
-    if (!inferringTypeSystem.isSubtypeOf(inferFnType, contextType)) {
+    if (!inferringTypeSystem.constrainReturnType(inferFnType, contextType)) {
       return fnType;
     }
 
-    // Try to infer and instantiate the resulting type.
-    var resultType = inferringTypeSystem._infer(
-        fnType, fnType.typeFormals, fnType.returnType);
-
-    // If the instantiation failed (because some type variable constraints
-    // could not be solved, in other words, we could not find a valid subtype),
-    // then return the original type, so the error is in terms of it.
-    //
-    // It would be safe to return a partial solution here, but the user
-    // experience may be better if we simply do not infer in this case.
-    //
-    // TODO(jmesserly): this heuristic is old. Maybe we should we issue the
-    // inference error?
-    return resultType ?? fnType;
+    // Infer and instantiate the resulting type.
+    // TODO(jmesserly): should we issue an inference error here, or rely on it

[Leaf, 2017/02/17 06:41:21]

I don't know should we?  :)  Is this a question we should resolve in this CL?  

[Jennifer Messerly, 2017/03/14 02:07:07]

let's leave changes to generic tear-offs out of scope for the CL. :)

universal functions being passed to places where instantiations are expected is
fairly rare. It arose from us not having syntax to explicitly instantiate them.
IIRC, the language team was thinking about getting rid of this support anyway?

+    // to happen later?
+    return inferringTypeSystem._infer(
+        fnType, fnType.typeFormals, fnType.returnType,
+        errorReporter: errorReporter, errorNode: errorNode);
   }
 
-  /// Given a function type with generic type parameters, infer the type
-  /// parameters from the actual argument types, and return the instantiated
-  /// function type. If we can't, returns the original function type.
+  /// Infers a generic type, function, method, or list/map literal
+  /// instantiation, using the downward context type as well as the argument
+  /// types if available.
+  ///
+  /// For example, given a function type with generic type parameters, this
+  /// infers the type parameters from the actual argument types, and returns the
+  /// instantiated 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
@@ -261,17 +258,19 @@ class StrongTypeSystemImpl extends TypeSystem {
   /// 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 Tj. Instead we track Uj and Lj where U is the upper bound and
-  /// L is the lower bound of that type parameter.
-  /*=T*/ inferGenericFunctionCall/*<T extends ParameterizedType>*/(
+  /// All constraints on each type parameter Tj are tracked, as well as where
+  /// they originated, so we can issue an error message tracing back to the
+  /// argument values, type parameter "extends" clause, or the return type
+  /// context.
+  /*=T*/ inferGenericFunctionOrType/*<T extends ParameterizedType>*/(
       /*=T*/ genericType,
-      List<DartType> declaredParameterTypes,
+      List<ParameterElement> parameters,
       List<DartType> argumentTypes,
       DartType declaredReturnType,

[Leaf, 2017/02/17 06:41:22]

I think this is always either equal to genericType (when T is InterfaceType) or
genericType.returnType (when T is Functiontype).  Since you have to do an is
check anyway, what do you think of just passing in genericType and projecting
out returnType if it exists?

Alternatively, you could split this into two non-generic entry points which call
this internal generic with the appropriate args.

FunctionType inferGenericFunction(FunctionType genericType. ...) {
  return _inferGenericFunctionOrType(genericType, ..., genericType.returnType,
...)
}

WDYT?

[Jennifer Messerly, 2017/03/14 02:07:06]

done

       DartType returnContextType,
       {ErrorReporter errorReporter,
-      AstNode errorNode}) {
+      AstNode errorNode,
+      bool downwards: false}) {
     // TODO(jmesserly): expose typeFormals on ParameterizedType.
     List<TypeParameterElement> typeFormals = genericType is FunctionType
         ? genericType.typeFormals
@@ -288,18 +287,24 @@ class StrongTypeSystemImpl extends TypeSystem {
         new _StrongInferenceTypeSystem(typeProvider, this, typeFormals);
 
     if (returnContextType != null) {
-      inferringTypeSystem.isSubtypeOf(declaredReturnType, returnContextType);
+      inferringTypeSystem.constrainReturnType(
+          declaredReturnType, returnContextType);
     }
 
     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.
-      inferringTypeSystem.isSubtypeOf(
-          argumentTypes[i], declaredParameterTypes[i]);
+      inferringTypeSystem.constrainArgument(
+          argumentTypes[i], parameters[i].type, parameters[i].name,
+          genericType: genericType);
     }
 
     return inferringTypeSystem._infer(
-        genericType, typeFormals, declaredReturnType, errorReporter, errorNode);
+        genericType, typeFormals, declaredReturnType,
+        returnContextType: returnContextType,
+        errorReporter: errorReporter,
+        errorNode: errorNode,
+        downwardsInferPhase: downwards);
   }
 
   /**
@@ -1445,33 +1450,82 @@ class _StrongInferenceTypeSystem extends StrongTypeSystemImpl {
   /// The outer strong mode type system, used for GLB and LUB, so we don't
   /// recurse into our constraint solving code.
   final StrongTypeSystemImpl _typeSystem;
-  final Map<TypeParameterType, _TypeParameterBound> _bounds;
+  final Map<TypeParameterType, List<_TypeConstraint>> _constraints;
+
+  /// Where this type constraint came from.
+  ///
+  /// Used for error messages, as well as in upwards inference, to determine
+  /// which constraints came from the downwards information and to fix the type
+  /// parameter based on those.
+  _TypeConstraintOrigin _constraintOrigin;
 
   _StrongInferenceTypeSystem(TypeProvider typeProvider, this._typeSystem,
       Iterable<TypeParameterElement> typeFormals)
-      : _bounds = new Map.fromIterable(typeFormals,
-            key: (t) => t.type, value: (t) => new _TypeParameterBound()),
+      : _constraints = new Map.fromIterable(typeFormals,
+            key: (t) => t.type, value: (t) => []),
         super(typeProvider);
 
+  /// Apply a return type constraint, which asserts that the [declaredType]
+  /// is a subtype of the [contextType].
+  bool constrainReturnType(DartType declaredType, DartType contextType) {
+    _constraintOrigin =
+        new _TypeConstraintFromReturnType(declaredType, contextType);
+    return isSubtypeOf(declaredType, contextType);
+  }
+
+  /// Apply an argument constraint, which asserts that the [argument] staticType
+  /// is a subtype of the [parameterType].
+  void constrainArgument(
+      DartType argumentType, DartType parameterType, String parameterName,
+      {DartType genericType}) {
+    _constraintOrigin = new _TypeConstraintFromArgument(
+        argumentType, parameterType, parameterName,
+        genericType: genericType);
+    isSubtypeOf(argumentType, parameterType);
+  }
+
+  void constrainTypeParameterIsSubtypeOf(TypeParameterType t1, DartType t2) {
+    var constraints = _constraints[t1];
+    if (constraints != null) {
+      if (!identical(t2, UnknownInferredType.instance)) {
+        constraints.add(new _TypeConstraint.typeParameterIsSubtypeOf(t1, t2,
+            origin: new _TypeConstraintFromExtendsClause(t1, t2)));
+      }
+    }
+  }
+
   /// Given the constraints that were given by calling [isSubtypeOf], find the
   /// instantiation of the generic function that satisfies these constraints.
+  ///
+  /// If [downwardsInferPhase] is set, we are in the first pass of inference,
+  /// pushing context types down. At that point we are allowed to push down
+  /// `?` to precisely represent an unknown type. If [downwardsInferPhase] is
+  /// false, we are on our final inference pass, have all available information
+  /// including argument types, and must not conclude `?` for any type formal.
   /*=T*/ _infer/*<T extends ParameterizedType>*/(/*=T*/ genericType,
       List<TypeParameterElement> typeFormals, DartType declaredReturnType,
-      [ErrorReporter errorReporter, AstNode errorNode]) {
+      {DartType returnContextType,
+      ErrorReporter errorReporter,
+      AstNode errorNode,
+      bool downwardsInferPhase: false}) {
     List<TypeParameterType> fnTypeParams =
         TypeParameterTypeImpl.getTypes(typeFormals);
 
     // Initialize the inferred type array.
     //
-    // They all start as `dynamic` to offer reasonable degradation for f-bounded
-    // type parameters.
+    // In the downwards phase, they all start as `?` to offer reasonable
+    // degradation for f-bounded type parameters. On the upwards phase, we use
+    // `dynamic` to maintain the invariant that `?` does not appear in a final
+    // inferred type.
     var inferredTypes = new List<DartType>.filled(
-        fnTypeParams.length, DynamicTypeImpl.instance,
+        fnTypeParams.length,
+        downwardsInferPhase
+            ? UnknownInferredType.instance
+            : DynamicTypeImpl.instance,
         growable: false);
 
     for (int i = 0; i < fnTypeParams.length; i++) {
       TypeParameterType typeParam = fnTypeParams[i];
-      _TypeParameterBound bound = _bounds[typeParam];
 
       // Apply the `extends` clause for the type parameter, if any.
       //
@@ -1491,104 +1545,259 @@ class _StrongInferenceTypeSystem extends StrongTypeSystemImpl {
       //
       //     <T extends Clonable<T>>
       DartType declaredUpperBound = typeParam.element.bound;
-      if (declaredUpperBound != null) {
-        // Assert that the type parameter is a subtype of its bound.
-        // TODO(jmesserly): the order of calling GLB here matters, because of
-        // https://github.com/dart-lang/sdk/issues/28513
-        bound.upper = _typeSystem.getGreatestLowerBound(bound.upper,
-            declaredUpperBound.substitute2(inferredTypes, fnTypeParams));
+      if (declaredUpperBound != null && !declaredUpperBound.isDynamic) {
+        // We consider the type parameter bound in the following cases:
+        // 1. final upwards inference
+        // 2. downwards inference, if we have a known context type, we can
+        //    strengthen this type before pushing it down further.
+        if (!downwardsInferPhase ||
+            _shouldConsiderTypeParameterBound(returnContextType)) {

[Leaf, 2017/02/17 06:41:22]

Why do we check if the context type is fully known?  This seems neither
necessary nor sufficient.  e.g.

returnContextType = Map<num, ?>

trying to instantiate 

  f((List<int> x) => x[0]);

where

  Map<S, T> f<S extends int, T extends String, U extends Iterable<int>>(int f(U
x));

then S will be constrained by the context type, and we do want to apply the
information from the bounds now, even though the returnContextType is partially
unknown.  But we don't want to constrain T and U yet, since if we constrain U
now we will over-constrain it.

But if 

  returnContextType = Map<int, String>

we still don't want to (yet) constrain U, we want to wait until we hit the
upwards pass.

Do we not have a way of tracking which variables have been constrained yet?

+          // Assert that the type parameter is a subtype of its bound.
+          constrainTypeParameterIsSubtypeOf(typeParam,
+              declaredUpperBound.substitute2(inferredTypes, fnTypeParams));
+        }
       }
 
-      // Now we've computed lower and upper bounds for each type parameter.
+      var variance =
+          new _TypeParameterVariance.from(typeParam, declaredReturnType);
+
+      var inferredType = _inferTypeForTypeParameter(typeParam, variance,
+          downwardsInferPhase: downwardsInferPhase,
+          errorReporter: errorReporter,
+          errorNode: errorNode);
+      if (inferredType == null) {
+        return null; // could not infer error.
+      }
+
+      // Final inferred type should not have `?`, because we eliminated it
+      // when computing constraints.
+      assert(downwardsInferPhase ||
+          !UnknownInferredType.typeIsUnknown(inferredType));
+
+      inferredTypes[i] = inferredType;
+    }
+
+    // Return the instantiated type.
+    var inferred = genericType.instantiate(inferredTypes);
+    return inferred as dynamic/*=T*/;
+  }
+
+  bool _shouldConsiderTypeParameterBound(DartType context) {
+    return context != null && !UnknownInferredType.typeIsUnknown(context);
+  }
+
+  DartType _inferTypeForTypeParameter(
+      TypeParameterType typeParam, _TypeParameterVariance variance,
+      {bool downwardsInferPhase,
+      ErrorReporter errorReporter,
+      AstNode errorNode}) {
+    // Combine constraints and compute the lower and upper bounds.
+    var constraints = _constraints[typeParam];
+    var bounds = _mergeConstraints(constraints,
+        downwardsInferPhase: downwardsInferPhase);
+    var boundsToUse = bounds;
+    bool isFixed;
+    if (downwardsInferPhase) {
+      isFixed = constraints.isNotEmpty;
+    } else {
+      // Figure out if the type variables are constrained by downwards
+      // inference and fix those. They are not allowed to change based on
+      // argument types.
       //
-      // To decide on which type to assign, we look at the return type and see
-      // if the type parameter occurs in covariant or contravariant positions.
+      // NOTE: types that are used by inference, such as `?` and future unions,

[Leaf, 2017/02/17 06:41:21]

remove "future unions" from comment now?

[Jennifer Messerly, 2017/03/14 02:07:07]

done

+      // are not fixed by this process.
+      var returnConstraints = constraints
+          .where((c) => c.origin.fromReturnType && !c.isUnknownType)
+          .toList();
+      isFixed = returnConstraints.isNotEmpty;
+      if (isFixed) {
+        returnConstraints.addAll(constraints
+            .where((c) => c.origin is _TypeConstraintFromExtendsClause));
+        boundsToUse =
+            _mergeConstraints(returnConstraints, downwardsInferPhase: false);
+      }
+    }
+
+    DartType choice =
+        _chooseTypeFromBounds(boundsToUse, variance, isFixed: isFixed);
+
+    if (errorReporter != null) {
+      DartType u = bounds.upperBound;
+      DartType l = bounds.lowerBound;
+      if (u != null && !_typeSystem.isSubtypeOf(choice, u) ||
+          l != null && !_typeSystem.isSubtypeOf(l, choice)) {
+        errorReporter.reportErrorForNode(
+            StrongModeCode.COULD_NOT_INFER,
+            errorNode,
+            [typeParam, _formatError(constraints, choice, isFixed: isFixed)]);
+      }
+    }
+
+    return choice;
+  }
+
+  /// Choose the bound that was implied by the return type, if any.
+  ///
+  /// Which bound this is depends on what positions the type parameter
+  /// appears in. If the type only appears only in a contravariant position,
+  /// we will choose the lower bound instead.
+  ///
+  /// For example given:
+  ///
+  ///     Func1<T, bool> makeComparer<T>(T x) => (T y) => x() == y;
+  ///
+  ///     main() {
+  ///       Func1<num, bool> t = makeComparer/* infer <num> */(42);
+  ///       print(t(42.0)); /// false, no error.
+  ///     }
+  ///
+  /// The constraints we collect are:
+  ///
+  /// * `num <: T`
+  /// * `int <: T`
+  ///
+  /// ... and no upper bound. Therefore the lower bound is the best choice.
+  DartType _chooseTypeFromBounds(
+      _TypeRange bounds, _TypeParameterVariance variance,
+      {bool isFixed}) {
+    var lower = bounds.lowerBound;
+    var upper = bounds.upperBound;
+
+    bool preferUpperBound = false;
+    if (variance.passedIn) {

[Leaf, 2017/02/17 06:41:22]

Can you explain this bit too me (probably worth a comment).  isFixed basically
tells you whether there were any constraints for this variable.  Why are we
preferring an upper bound for contra-variant parameters that are un-constrained
(in this case we shouldn't have a bound , right?), but lower bound otherwise,
etc?

[Jennifer Messerly, 2017/03/14 02:07:06]

done! this is gone in new code :)

+      preferUpperBound = !isFixed;
+    } else if (variance.passedOut) {
+      preferUpperBound = isFixed;
+    }
+
+    // These heuristics ensure two things:
+    // 1. That we choose Null instead of <bottom>
+    // 2. That we avoid Null whenever possible, preferring the upper bound
+    //    or `dynamic`. For example: `[null]` will become a `List<dynamic>`
+    //    rather than a `List<Null>`.
+    //
+    // TODO(jmesserly): choosing Null over bottom will need to be reevaluated
+    // once we support non-nullable types.
+    if (upper != null && upper.isBottom) {
+      upper = typeProvider.nullType;
+    }
+
+    if (lower != null) {
+      if (lower.isBottom) {
+        lower = typeProvider.nullType;
+      }
+      if (lower.isDartCoreNull) {

[Leaf, 2017/02/17 06:41:21]

I'm not sure about this heuristic now.  We're going to be inferring Null for

  var x = Null;

and as the return type for

  (int x) { return null; }

so it feels like

  [null]

should be List<Null> as well.



WDYT?  Are there examples where this goes really bad?

[Jennifer Messerly, 2017/03/14 02:07:07]

done! this is gone now in new code :)

+        preferUpperBound = true;
+        upper ??= DynamicTypeImpl.instance;
+      }
+    }
+
+    var result = preferUpperBound ? (upper ?? lower) : (lower ?? upper);
+    return result;
+  }
+
+  _TypeRange _mergeConstraints(Iterable<_TypeConstraint> constraints,
+      {bool downwardsInferPhase}) {
+    DartType lower;
+    DartType upper;
+    for (var constraint in constraints) {
+      // Ensure T1 <: T2, where T1 is a type parameter we are inferring.
+      // T2 is an upper bound, so merge it with our existing upper bound.
+      //
+      // We already know T1 <: U, for some U.
+      // So update U to reflect the new constraint T1 <: GLB(U, T2)
+      var constraintUpper = constraint.upperBound;
+      if (constraintUpper != null) {
+        if (!downwardsInferPhase) {
+          constraintUpper =
+              UnknownInferredType.upperBoundForType(constraintUpper);
+        }
+        upper = getGreatestLowerBound(
+            upper ?? DynamicTypeImpl.instance, constraintUpper);
+      }
+      // Ensure T1 <: T2, where T2 is a type parameter we are inferring.
+      // T1 is a lower bound, so merge it with our existing lower bound.
       //
-      // If the type is "passed in" at all, or if our lower bound was bottom,
-      // we choose the upper bound as being the most useful.
+      // We already know L <: T2, for some L.
+      // So update L to reflect the new constraint LUB(L, T1) <: T2
       //
-      // Otherwise we choose the more precise lower bound.
-      _TypeParameterVariance variance =
-          new _TypeParameterVariance.from(typeParam, declaredReturnType);
-
-      DartType lowerBound = bound.lower;
-      DartType upperBound = bound.upper;
-
-      // See if the bounds can be satisfied.
-      // TODO(jmesserly): also we should have an error for unconstrained type
-      // parameters, rather than silently inferring dynamic.
-      if (upperBound.isBottom ||
-          !_typeSystem.isSubtypeOf(lowerBound, upperBound)) {
-        // Inference failed.
-        if (errorReporter == null) {
-          return null;
+      var constraintLower = constraint.lowerBound;
+      if (constraintLower != null) {
+        if (!downwardsInferPhase) {
+          constraintLower =
+              UnknownInferredType.lowerBoundForType(constraintLower);
         }
-        errorReporter.reportErrorForNode(StrongModeCode.COULD_NOT_INFER,
-            errorNode, [typeParam, lowerBound, upperBound]);
-
-        // To make the errors more useful, we swap the normal heuristic.
-        //
-        // The normal heuristic prefers using the argument types (upwards
-        // inference, lower bound) to choose a tighter type.
-        //
-        // Here we want to prefer the return context type, so we can put the
-        // blame on the arguments to the function. That will result in narrow
-        // error spans. But ultimately it's just a heuristic, as the code is
-        // already erroneous.
-        //
-        // (we may adjust the normal heuristic too, once upwards+downwards
-        // inference are fully integrated, to prefer downwards info).
-        lowerBound = bound.upper;
-        upperBound = bound.lower;
+        lower = getLeastUpperBound(
+            lower ?? BottomTypeImpl.instance, constraintLower);
       }
+    }
 
-      inferredTypes[i] =
-          variance.passedIn && !upperBound.isDynamic || lowerBound.isBottom
-              ? upperBound
-              : lowerBound;
+    // Handle the case where we had no constraints at all.
+    if (lower == null && upper == null) {
+      // TODO(jmesserly): report an error for an unconstrained type parameter in
+      // final upwards inference?
+      upper = downwardsInferPhase
+          ? UnknownInferredType.instance
+          : DynamicTypeImpl.instance;
     }
 
-    // Return the instantiated type.
-    return genericType.instantiate(inferredTypes) as dynamic/*=T*/;
+    return new _TypeRange(lower: lower, upper: upper);
+  }
+
+  static String _formatError(
+      Iterable<_TypeConstraint> constraints, DartType choice,
+      {bool isFixed}) {
+    // Only report unique constraint origins.
+    List<List<String>> lineParts =
+        new Set<_TypeConstraintOrigin>.from(constraints.map((c) => c.origin))
+            .map((o) => o.formatError())
+            .toList();
+
+    int prefixMax = lineParts.map((p) => p[0].length).fold(0, math.max);
+    int middleMax = lineParts.map((p) => p[1].length).fold(0, math.max);
+
+    // Use a set to prevent identical message lines.
+    // (It's not uncommon for the same constraint to show up in a few places.)
+    var messageLines = new Set<String>.from(lineParts.map((parts) {
+      var prefix = parts[0];
+      var middle = parts[1];
+      var prefixPad = ' ' * (prefixMax - prefix.length);
+      var middlePad = ' ' * (middleMax - middle.length);
+      return '  $prefix$prefixPad $middle$middlePad ${parts[2]}'.trimRight();
+    }));
+
+    var intro = isFixed
+        ? "Inferred '$choice' based on the return type, "
+            "but it does not satisfy all constraints:"
+        : "Tried '$choice' but this did not work with all constraints:";
+
+    return "\n\n$intro\n${messageLines.join('\n')}\n\n"
+        'Consider passing explicit type argument(s) to the generic.\n\n';
   }
 
   @override
   bool _isSubtypeOf(DartType t1, DartType t2, Set<Element> visited,
       {bool dynamicIsBottom: false}) {
-    // TODO(jmesserly): the trivial constraints are not treated as part of
-    // the constraint set here. This seems incorrect once we are able to pin the
-    // inferred type of a type parameter based on the downwards information.
-    if (identical(t1, t2) ||
-        _isTop(t2, dynamicIsBottom: dynamicIsBottom) ||
-        _isBottom(t1, dynamicIsBottom: dynamicIsBottom)) {
-      return true;
-    }
-
     if (t1 is TypeParameterType) {
-      // TODO(jmesserly): we ignore `dynamicIsBottom` here, is that correct?
-      _TypeParameterBound bound = _bounds[t1];
-      if (bound != null) {
-        // Ensure T1 <: T2, where T1 is a type parameter we are inferring.
-        // T2 is an upper bound, so merge it with our existing upper bound.
-        //
-        // We already know T1 <: U, for some U.
-        // So update U to reflect the new constraint T1 <: GLB(U, T2)
-        //
-        bound.upper = _typeSystem.getGreatestLowerBound(bound.upper, t2);
+      var constraints = _constraints[t1];
+      if (constraints != null) {
+        // TODO(jmesserly): we ignore `dynamicIsBottom` here, is that correct?
+        if (!identical(t2, UnknownInferredType.instance)) {
+          constraints.add(new _TypeConstraint.typeParameterIsSubtypeOf(t1, t2,
+              origin: _constraintOrigin));
+        }
+
         // Optimistically assume we will be able to satisfy the constraint.
         return true;
       }
     }
     if (t2 is TypeParameterType) {
-      _TypeParameterBound bound = _bounds[t2];
-      if (bound != null) {
-        // Ensure T1 <: T2, where T2 is a type parameter we are inferring.
-        // T1 is a lower bound, so merge it with our existing lower bound.
-        //
-        // We already know L <: T2, for some L.
-        // So update L to reflect the new constraint LUB(L, T1) <: T2
-        //
-        bound.lower = _typeSystem.getLeastUpperBound(bound.lower, t1);
+      var constraints = _constraints[t2];
+      if (constraints != null) {
+        if (!(identical(t1, UnknownInferredType.instance))) {
+          constraints.add(new _TypeConstraint.isSubtypeOfTypeParameter(t1, t2,
+              origin: _constraintOrigin));
+        }
         // Optimistically assume we will be able to satisfy the constraint.
         return true;
       }
@@ -1598,8 +1807,85 @@ class _StrongInferenceTypeSystem extends StrongTypeSystemImpl {
   }
 }
 
-/// An [upper] and [lower] bound for a type variable.
-class _TypeParameterBound {
+/// The origin of a type constraint, for the purposes of producing a human
+/// readable error message during type inference as well as determining whether
+/// the constraint was used to fix the type parameter or not.
+abstract class _TypeConstraintOrigin {
+  bool get fromReturnType => false;
+  List<String> formatError();
+}
+
+class _TypeConstraintFromArgument extends _TypeConstraintOrigin {
+  final DartType argumentType;
+  final DartType parameterType;
+  final String parameterName;
+  final DartType genericType;
+
+  _TypeConstraintFromArgument(
+      this.argumentType, this.parameterType, this.parameterName,
+      {this.genericType});
+
+  @override
+  formatError() {
+    // TODO(jmesserly): we should highlight the span. That would be more useful.
+    // However in summary code it doesn't look like the AST node with span is
+    // available.
+    String prefix;
+    if ((genericType.name == "List" || genericType.name == "Map") &&
+        genericType?.element?.library?.isDartCore == true) {
+      // This will become:
+      //     "List element"
+      //     "Map key"
+      //     "Map value"
+      prefix = "${genericType.name} $parameterName";
+    } else {
+      prefix = "Argument '$parameterName'";
+    }
+
+    return [
+      prefix,
+      "inferred as '$argumentType'",
+      "must be a '$parameterType'."
+    ];
+  }
+}
+
+class _TypeConstraintFromReturnType extends _TypeConstraintOrigin {
+  final DartType contextType;
+  final DartType declaredType;
+
+  _TypeConstraintFromReturnType(this.declaredType, this.contextType);
+
+  @override
+  bool get fromReturnType => true;
+
+  @override
+  formatError() {
+    return [
+      "Return type",
+      "declared as '$declaredType'",
+      "must be a '$contextType'."

[Leaf, 2017/02/17 22:26:03]

 Can we say anything that's more helpful than "must be"?  Maybe something like:

"used where a $contextType is required"

or something like that?

[Jennifer Messerly, 2017/03/14 02:07:07]

fixed

+    ];
+  }
+}
+
+class _TypeConstraintFromExtendsClause extends _TypeConstraintOrigin {
+  final TypeParameterType typeParam;
+  final DartType extendsType;
+
+  _TypeConstraintFromExtendsClause(this.typeParam, this.extendsType);
+
+  @override
+  formatError() {
+    return [
+      "Type parameter '$typeParam'",
+      "declared to extend '$extendsType'.",
+      ""
+    ];
+  }
+}
+
+class _TypeRange {
   /// The upper bound of the type parameter. In other words, T <: upperBound.
   ///
   /// In Dart this can be written as `<T extends UpperBoundType>`.
@@ -1621,7 +1907,7 @@ class _TypeParameterBound {
   ///
   /// 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;
+  final DartType upperBound;
 
   /// The lower bound of the type parameter. In other words, lowerBound <: T.
   ///
@@ -1640,7 +1926,44 @@ class _TypeParameterBound {
   ///
   /// 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;
+  final DartType lowerBound;
+
+  _TypeRange({DartType lower, DartType upper})
+      : lowerBound = lower,
+        upperBound = upper;
+}
+
+/// A constraint on a type parameter that we're inferring.
+class _TypeConstraint extends _TypeRange {
+  /// The type parameter that is constrained by [lowerBound] or [upperBound].
+  final TypeParameterType typeParameter;
+
+  /// Where this constraint comes from, used for error messages.
+  ///
+  /// See [toString].
+  final _TypeConstraintOrigin origin;
+
+  _TypeConstraint.typeParameterIsSubtypeOf(this.typeParameter, DartType upper,
+      {this.origin})
+      : super(upper: upper) {
+    assert(origin != null);
+  }
+
+  _TypeConstraint.isSubtypeOfTypeParameter(DartType lower, this.typeParameter,
+      {this.origin})
+      : super(lower: lower) {
+    assert(origin != null);
+  }
+
+  bool get isUnknownType =>
+      UnknownInferredType.typeIsUnknown(upperBound) ||

[Leaf, 2017/02/17 22:26:03]

Just trying to think through this code.  This is used to decide whether to treat
a type parameter as fixed or not.  It kind of feel like we should only ignore
the return constraints if both of these are unfixed.  Example:

returnContextType is int -> ?

matched against declared return type of T -> T

we end up with 

int <: T

T <: ?

seems like maybe we should use the int constraint here?

Does that make sense?  Very corner case.

[Jennifer Messerly, 2017/03/14 02:07:07]

fixed in the new code :)

+      UnknownInferredType.typeIsUnknown(lowerBound);
+
+  /// Converts this constraint to a message suitable for a type inference error.
+  @override
+  String toString() => upperBound != null
+      ? "'$typeParameter' must extend '$upperBound'"
+      : "'$lowerBound' must extend '$typeParameter'";
 }
 
 /// Records what positions a type parameter is used in.
@@ -1708,3 +2031,189 @@ class _TypeParameterVariance {
     }
   }
 }
+
+/// The synthetic element for [UnknownInferredType].
+class UnknownInferredTypeElement extends ElementImpl
+    implements TypeDefiningElement {
+  static final UnknownInferredTypeElement instance =
+      new UnknownInferredTypeElement._();
+
+  @override
+  UnknownInferredType get type => UnknownInferredType.instance;
+
+  UnknownInferredTypeElement._() : super(Keyword.DYNAMIC.syntax, -1) {
+    setModifier(Modifier.SYNTHETIC, true);
+  }
+
+  @override
+  ElementKind get kind => ElementKind.DYNAMIC;
+
+  @override
+  /*=T*/ accept/*<T>*/(ElementVisitor visitor) => null;
+}
+
+/// A type that is being inferred but is not currently known.
+///
+/// This type will only appear in a downward inference context for type
+/// parameters that we do not know yet. Notationally it is written `?`, for
+/// example `List<?>`. This is distinct from `List<dynamic>`. These types will
+/// never appear in the final resolved AST.
+class UnknownInferredType extends TypeImpl {
+  static final UnknownInferredType instance = new UnknownInferredType._();
+
+  UnknownInferredType._()
+      : super(UnknownInferredTypeElement.instance, Keyword.DYNAMIC.syntax);
+
+  @override
+  int get hashCode => 1;
+
+  @override
+  bool get isDynamic => true;
+
+  @override
+  bool operator ==(Object object) => identical(object, this);
+
+  @override
+  bool isMoreSpecificThan(DartType type,
+      [bool withDynamic = false, Set<Element> visitedElements]) {
+    // T is S
+    if (identical(this, type)) {
+      return true;
+    }
+    // else
+    return withDynamic;
+  }
+
+  @override
+  bool isSubtypeOf(DartType type) => true;
+
+  @override
+  bool isSupertypeOf(DartType type) => true;
+
+  @override
+  TypeImpl pruned(List<FunctionTypeAliasElement> prune) => this;
+
+  @override
+  DartType substitute2(
+      List<DartType> argumentTypes, List<DartType> parameterTypes,
+      [List<FunctionTypeAliasElement> prune]) {
+    int length = parameterTypes.length;
+    for (int i = 0; i < length; i++) {
+      if (parameterTypes[i] == this) {
+        return argumentTypes[i];
+      }
+    }
+    return this;
+  }
+
+  @override
+  void appendTo(StringBuffer buffer) {
+    buffer.write('?');
+  }
+
+  // Given a [type] T, return true if it has an unknown type `?`.
+  static bool typeIsUnknown(DartType type) {
+    if (identical(type, UnknownInferredType.instance)) {
+      return true;
+    }
+    if (type is InterfaceTypeImpl) {
+      return type.typeArguments.any(typeIsUnknown);
+    }
+    if (type is FunctionType) {
+      return typeIsUnknown(type.returnType) ||
+          type.parameters.any((p) => typeIsUnknown(p.type));
+    }
+    return false;
+  }
+
+  // Given a [type] T that may have an unknown type `?`, returns a type
+  // R such that T <: R for any type substituted for `?`.
+  //
+  // In practice this will always replace `?` with either bottom or top
+  // (dynamic), depending on the position of `?`.
+  static DartType upperBoundForType(DartType type) {
+    return _substituteForUnknownType(type, _useDynamicOrBottom);
+  }
+
+  // Given a [type] T that may have an unknown type `?`, returns a type
+  // R such that R <: T for any type substituted for `?`.
+  //
+  // In practice this will always replace `?` with either bottom or top
+  // (dynamic), depending on the position of `?`.
+  static DartType lowerBoundForType(DartType t) {
+    return _substituteForUnknownType(t, _useDynamicOrBottom, lowerBound: true);
+  }
+
+  // Given a [type] T that may have an unknown type `?`,  substitutes `dynamic`
+  // for `?` and returns a new type.
+  static DartType substituteDynamic(DartType t) {
+    // TODO(jmesserly): we can't use substitute2 because it contains an
+    // assertion that types aren't substituted more than once.
+    return _substituteForUnknownType(t, (_) => DynamicTypeImpl.instance);
+  }
+
+  static DartType _useDynamicOrBottom(bool bottomType) {
+    return bottomType ? BottomTypeImpl.instance : DynamicTypeImpl.instance;
+  }
+
+  static DartType _substituteForUnknownType(
+      DartType type, DartType visitUnknown(bool bottomType),
+      {bool lowerBound: false, dynamicIsBottom: false}) {
+    if (identical(type, UnknownInferredType.instance)) {
+      return visitUnknown(lowerBound && !dynamicIsBottom);
+    }
+    if (type is InterfaceTypeImpl) {
+      // Generic types are covariant, so keep the constraint direction.
+      var newTypeArgs = _transformList(
+          type.typeArguments,
+          (t) => _substituteForUnknownType(t, visitUnknown,
+              lowerBound: lowerBound));
+      if (identical(type.typeArguments, newTypeArgs)) return type;
+      return new InterfaceTypeImpl(type.element, type.prunedTypedefs)
+        ..typeArguments = newTypeArgs;
+    }
+    if (type is FunctionType) {
+      var parameters = type.parameters;
+      var returnType = type.returnType;
+      var newParameters = _transformList(parameters, (ParameterElement p) {
+        // Parameters are contravariant, so flip the constraint direction.
+        // Also pass dynamicIsBottom, because this is a fuzzy arrow.
+        var newType = _substituteForUnknownType(p.type, visitUnknown,
+            lowerBound: !lowerBound, dynamicIsBottom: true);
+        return identical(p.type, newType) && p is ParameterElementImpl
+            ? p
+            : new ParameterElementImpl.synthetic(
+                p.name, newType, p.parameterKind);
+      });
+      // Return type is covariant.
+      var newReturnType = _substituteForUnknownType(returnType, visitUnknown,
+          lowerBound: lowerBound);
+      if (identical(parameters, newParameters) &&
+          identical(returnType, newReturnType)) {
+        return type;
+      }
+
+      var function = new FunctionElementImpl(type.name, -1)
+        ..isSynthetic = true
+        ..returnType = newReturnType
+        ..shareTypeParameters(type.typeFormals)
+        ..shareParameters(newParameters);
+      return function.type = new FunctionTypeImpl(function);
+    }
+    return type;
+  }
+
+  static List/*<T>*/ _transformList/*<T>*/(
+      List/*<T>*/ list, /*=T*/ f(/*=T*/ t)) {
+    List/*<T>*/ newList = null;
+    for (var i = 0; i < list.length; i++) {
+      var item = list[i];
+      var newItem = f(item);
+      if (!identical(item, newItem)) {
+        newList ??= new List.from(list);
+        newList[i] = newItem;
+      }
+    }
+    return newList ?? list;
+  }
+}