Use bottom-up type inference for invocations of generic functions with non-covariant parameter types

[eernstg]

See dart-lang/sdk#52850 for background information, including a detailed analysis from @stereotype441.

Consider the following example:

abstract class A {}

class C<Y> {}

List<U> Function<U>(U Function(U)) f = <U>(c) => <U>[];

List<Object?> g<W>(W Function(W) d) => f/*<W>*/(d);

This library causes a compile-time error to be reported at f(d), but there is no error if we use f<W>(d).

The context type List<Object?> is used during downwards inference to choose the type argument passed to f, so we make it f<Object?>(d) before we even consider whether that choice of type argument makes d a type correct actual argument.

This normally fine: The context type is usually an upper bound (so if we can't use an actual type argument A which is taken from the context type, or a subtype of A, then the entire expression is a type error). Conversely, if we could have used a subtype of the type from the context then it is usually no problem that we use a subtype.

The reason for this is that most parameter types are covariant in the type parameters of the enclosing generic function. In other words, if f<T>(d) is type correct and T <: S then f<S>(d) is also type correct. Based on the context type, we'd choose the most general type which is allowed by the context, which is again the type that allows for the greatest possible set of types for the actual arguments.

However, in this particular case we can't use a supertype, because the type parameter U occurs both covariantly and contravariantly in the parameter type of f. So when we choose Object? as the actual type argument passed to f in the body of g, the corresponding instantiated parameter type of f is Object? Function(Object?), and that's unrelated to the type of d which is W Function(W), and hence we get a type error (or a type inference failure).

I think we might want to use the current approach (based on the context type whenever possible) in all cases where we are inferring actual type arguments for a generic function invocation where the parameter types are covariant in all type parameters, but in the case where some parameter types are non-covariant in some type parameters we could use bottom-up inference.