[analyzer, cfe] Type inference fails with function type as type argument

[eernstg]

Consider the following program:

abstract class A {}

class B extends A {}

class _C<X1 extends A, Invariance> {
  R m<R>(R Function<X2 extends A>(C<X2>) body) => body<X1>(this as C<X1>);
}

abstract class _D<X3, Invariance> {}

class _E<X4 extends A, X5> extends _D<X4, X5> {}

typedef C<X6 extends A> = _C<X6, Inv<X6>>;
typedef D<X7> = _D<X7, Inv<X7>>;
typedef E<X8 extends A> = _E<X8, Inv<X8>>;
typedef F = List<X9> Function<X9 extends A>(C<X9>);
typedef Inv<X> = X Function(X);

void foo(F f, C<B> c) {
  c.m<List<A>>(<X10 extends A>(d) => f/*<X10>*/(d));
}

void main() {}

This program is rejected by the analyzer and the CFE (6a4ef6c), indicating that the type inference step failed to find a suitable type argument for the invocation of f:

Analyzing n008.dart...                 0.7s

  error • n008.dart:20:49 • The argument type '_C<X10, X10 Function(X10)>'
          can't be assigned to the parameter type '_C<A, A Function(A)>'. •
          argument_type_not_assignable

1 issue found.

n008.dart:20:49: Error: The argument type '_C<X10, X10 Function(X10)>' can't be assigned to the parameter type '_C<A, A Function(A)>'.
 - '_C' is from 'n008.dart'.
 - 'A' is from 'n008.dart'.
  c.m<List<A>>(<X10 extends A>(d) => f/*<X10>*/(d));
                                                ^

The program has no errors if f(d) is replaced by f<X10>(d).

The surprising part is that the error message seems to imply that the static type of the actual argument is _C<X10, X10 Function(X10)> (which may also be written as C<X10>), and the formal parameter type is _C<A, A Function(A)> aka C<A>, so the inferred type argument for the invocation of f is A, even though that does not satisfy the given constraints.

Is this working as intended, or should we generate some additional constraints during this type inference step?

[eernstg]

Here is a simpler version where type inference still fails (and uncommenting /*<W>*/ eliminates the error):

abstract class A {}

class C<Y, Z> {}

R m<R>(R Function<V>(C<V, V Function(V)>) body) => throw 0;

typedef F = List<U> Function<U>(C<U, U Function(U)>);

List<Object?> bar(F f) => m(<W>(d) => f/*<W>*/(d));

void main() {}

This may or may not be related, but there is another behavior which is surprising: Comment out bar's return type. If we do this then the following error is reported by the analyzer, but no error is reported by the CFE (and it doesn't matter whether we have /*<W>*/ or <W>):

The argument type 'List<W> Function<W>(C<W, W Function(W)>)' can't be assigned to the parameter type 'List<Z0> Function<V>(C<V, V Function(V)>)'.

[stereotype441]

abstract class A {}

class C<Y, Z> {}

R m<R>(R Function<V>(C<V, V Function(V)>) body) => throw 0;

typedef F = List<U> Function<U>(C<U, U Function(U)>);

List<Object?> bar(F f) => m(<W>(d) => f/*<W>*/(d));

void main() {}

Here's what's happening in this example (with /*<W>*/ commented out):

• First, m(<W>(d) => f(d)) is visited, with context List<Object?>; this makes sense because we're visiting the expression function body of bar, and the context is the return type of bar.
• Since m is a generic method with type parameter R, downward inference is used to try to guess the correct type for R. Since the return type of m is R, and the context is List<Object?>, downward inference is successful, and chooses List<Object?> to be substituted for R.
• Now, the argument to m, which is <W>(d) => f(d)), is visited, with context List<Object?> Function<V>(C<V, V Function(V)>); this makes sense because this is the argument type of m with List<Object?> substituted in place of R.
• The rule for type inferring a function expression (PARAMS) => EXPR (in a function-typed context) is to first assign types to untyped parameters in PARAMS based on the parameter types in the context, then visit EXPR using a context based on the return type of the context.
  • The aforementioned function-typed context (List<Object?> Function<V>(C<V, V Function(V)>)) has a single parameter with type C<V, V Function(V)>. This is transformed into C<W, W Function(W)> (because the function type parameter is explicitly given as W), so the type C<W, W Function(W)> is assigned to d.
  • The aforementioned function-typed context has a return type of List<Object?>. So this is used as the context for type-inferring the expression f(d).
• Since f is also generic (with type List<U> Function<U>(C<U, U Function(U)>)), downward inference now tries to find a type for U. It does so by matching the expected return type coming in from the surrounding context (List<Object?>) against the return type of f (List<U>), so it chooses Object? to be substituted for U.
• At this point all value for all type parameters have been chosen, so everything else is just type checking. f now has been instantiated with a type of List<Object?> Function(C<Object?, Object? Function(Object?)>), but the argument provided to it (d) was assigned a type of C<W, W Function(W)>. W Function(W) is neither a subtype nor a supertype of Object? Function(Object?) (because Object? is substituted for W both in a covariant and a contravariant position), so the argument type doesn't match.

So as far as I can tell, everything is happening as designed. Our algorithm for type inference was deliberately designed to eagerly choose types after downwards inference if possible, because this makes things more tractable and tends to reduce spooky action at a distance. But it has the disadvantage that it doesn't take advantage of all the information that's avaiable. Specifically, in this case, at the time of downward inference on f(d), the only type inference constraint that has been discovered is:

• List<U> <: List<Object?>

...which is trivially satisfied by any choice of U.
A more complex type inference algorithm, such as one based on Hindley–Milner, would have delayed choosing the type of U until after visiting f(d), at which point it would have discovered the additional constraint:

• C<W, W Function(W)> <: C<U, U Function(U)>

...which is equivalent to:

• W <: U
• U <: W

...and hence can only be satisfied by choosing to set U to W.

A possible improvement we could consider would be to leave the type U undetermined after downwards inference (on the grounds that the constraint List<U> <: List<Object?> is trivially satisfied regardless of the type chosen for U), and allow more type inference constraints to be gathered by upwards inference before fixing its type. However, we'd have to be careful to preserve behaviours like the following (which is heavily relied upon by idiomatic Dart code):

List<Object?> x = [1, 2, 3]; // Means `<Object?>[1, 2, 3]` due to downwards inference
x.add('foo'); // If the line above is inferred differently, this will become a runtime error

We might be able to achieve this by an algorithm like this:

• If the constraints produced by downwards inference are trivially satisfied, don't fix any types yet, however remember any types that downwards inference "suggests" for later (e.g. in the example of List<Object?> x = [1, 2, 3], remember Object? as the "suggested" type for the list element).
• After upwards inference, if all type constraints are satisfied by the types suggested by downwards inference, use those types. Otherwise, compute the types based on looking at all constraints.

[eernstg]

That's an amazing analysis, @stereotype441!

Here is a minimal 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).

In short, the context type List<Object?> gets 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.

However, in this particular case we can't use the supertype, because the type parameter U occurs both covariantly and contravariantly in the parameter type of f. So when we choose Object?, the parameter type of the instantiated f is Object Function(Object?), and that's unrelated to W Function(W), as you mention.

In other words, 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.

[eernstg]

I've developed the idea above a bit more and created dart-lang/language#3212 to discuss it.

[eernstg]

I'll close this issue because type inference proceeds as intended. The issue dart-lang/language#3212 contains a proposal about how it could be adjusted, based on the lessons learned in this issue.