Function literal return type inference fails on divergent future

[eernstg]

Consider the following program:

class Divergent<T> implements Future<Divergent<Divergent<T>>> {
  noSuchMethod(Invocation invocation) => super.noSuchMethod(invocation);
}

void main() => () async => Divergent<int>();

This program is rejected by the CFE and the analyzer with similar error messages. Analyzer:

The return type 'Divergent<int>' isn't a 'Future<Divergent<Divergent<Divergent<int>>>>', as required by the closure's context.

CFE:

lib/main.dart:6:28:
Error: A value of type 'Divergent<int>' can't be returned from an async function with return type 'Future<Divergent<Divergent<Divergent<int>>>>'.
 - 'Divergent' is from 'package:dartpad_sample/main.dart' ('lib/main.dart').
 - 'Future' is from 'dart:async'.
void main() => () async => Divergent<int>();
                           ^

The return type inference for a function literal is specified here.

Checking the current definition of flatten we get flatten(Divergent<T>) == Divergent<Divergent<T>>.

For the inference of the return type of the function literal, we note that the imposed return type schema has no relevant information (and we get the same error with var _ = /*same function literal*/;), and also that the returned expression has type Divergent<int> as stated, which is then also the type of the returned expression after type inference for any context type because there's no thing for type inference to do.

So the actual returned type is flatten(Divergent<int>), that is, Divergent<Divergent<int>>. This implies that the inferred return type R for the function literal is Future<flatten(Divergent<Divergent<int>>)>, that is, R == Future<Divergent<Divergent<Divergent<int>>>>.

This shows that the implementations are computing the specified return type, and the only remaining problem is that the given returned expression does not satisfy the typing constraints associated with that return type.

So is it justified that we're returning a Divergent<int> in an async function whose return type is R == Future<Divergent<Divergent<Divergent<int>>>>? Should we get an error or not?

Let's explore some parts of the supertype graph of Divergent<int>, in order to see whether or not we can find a supertype which should be accepted. If this is true then Divergent<int> should arguably also be accepted.

By the declaration, Divergent<int> <: Future<Divergent<Divergent<int>>>. Other supertypes can be created by a rewrite operation that changes Divergent<T> to Future<Divergent<Divergent<T>>> for any T. No matter which steps we take, this will yield a type of the form Future^k<(Divergent|Future)^m<int>> for some k >0. Let S be the type we computed by any set of steps like this.

The test is that Future<flatten(S)> must be assignable to the return type R, that is, it must be a subtype of R. However, that is never true because the expansion steps described above will always create an S where Future is applied to the type argument at some level of nesting for any number of expansion steps greater than 1, and the types Divergent<int> and Future<Divergent<Divergent<int>>> (zero steps plus one step) are not subtypes of R.

The rules about inference of the return type of a function literal are surely intended to satisfy the sanity condition that each returned expression must satisfy the typing requirements for a returned expression, but that doesn't hold in this particular case.

In general, we don't want type inference (of any kind) to yield a program with type errors based on the failure to satisfy a subtype requirement where an inferred type is one of the operands. ("If we infer a type then it must be a type that works.")

However, the conclusion is probably the following:

• It is now known that some typing situations can give rise to this kind of type error.
• We could detect the situation and use an inferred return type of Future<Object?> or something like that.
• We could also do nothing, and accept that it is possible to get this kind of error.

Note that, presumably, the class Divergent has a very unusual typing structure, and it is not obvious that anything with that structure would be useful or important to support.

@dart-lang/language-team, WDYT? Do we just keep everything as it is? Or do we use the return type Future<Object?> (or something like that) when this kind of type error occurs?

[lrhn]

Let's work towards #870, and get rid of the implicit FutureOr<T> context of returns in async functions, please!

Looking at:

class Divergent<T> implements Future<Divergent<Divergent<T>>> {
  noSuchMethod(Invocation invocation) => super.noSuchMethod(invocation);
}

void main() => () async => Divergent<int>();

So the actual returned type is flatten(Divergent<int>), that is, Divergent<Divergent<int>>. This implies that the inferred return type R for the function literal is Future<flatten(Divergent<Divergent<int>>)>, that is, R == Future<Divergent<Divergent<Divergent<int>>>>

Not sure I follow that, or agree.

There is a number of types involved here. I'll use my own names, since I don't remember official names.

• Function return type. (Not specified, so to be inferred.)
• Function future value type. (Not specified, inferred, or derived from inferred function return type. Future<FutureValueType> must be subtype of return type.)
• Returned value type. (The type of the value actually returned, which may be after an implicit await in the return. Must be subtype of future value type.) Probably what is called "actual returned type" above.
• Return expression static type. (Actual static type of e in return e/=> e. Must be assignable to FutureOr<FutureValueType>).

Here the context provides nothing nothing, and we start at the return expression static type of Divergent<int>, and have to infer the rest by solving constraints backwards.

The expression type must be assignable to FutureOr<FutureValueType>, so we try to derive the future value type from it.
That should just use flatten of the expression static type as the returned value type. If the expression type is not a future-related type, it'll be the same as the expression type, otherwise we're probably going to want to be awaiting.

So the returned value type is Divergent<Divergent<int>>, which is known to be a subtype of the future value type.

This is the only return we have, so the only constraint on the future value type, so the future value type should also be found to be Diverget<Divergent<int>>.

Then the function return type must be a supertype of Future<Divergent<Divergent<int>>>, and we solve by choosing precisely that.

That seems like it should work.

The extra flatten introduced in Future<flatten(Divergent<Divergent<int>>)>, as quoted above, doesn't correspond to anything in the runtime semantics, so if we specify it, it's probably a bug in the specification.

Basically, to infer the return type of an async function with no context type scheme,
take flatten of the return expression types of each return in the function, each inferred with no context type,
and take their least upper bound. That's the desired future value type, FVT. Then put Future<....> around it to get the return type.

Then the runtime semantics are that return will do, effectively:

var value = e;
FutureOr<FVT> futureOrValue = value;
if (futureOrValue is Future<FVT>) real_return await futureOrValue;
real_return futureOrValue;

That should be safe, since the FVT is a supertype of flatten of the static type of (each) e, and therefore FutureOr<FVT> is a supertype of the static type of e. (I believe that equational reasoning is sound. Have we proven it?)

[leafpetersen]

@eernstg The spec you link to (which I think I wrote) looks buggy to me. In particular, it applies flatten twice, which seems wrong to me, is there a reason it does so that I'm missing? That is, we have:

For each return e; statement in the block, let S be the inferred type of e, using the local type inference algorithm described below with typing context K, and update T to be UP(flatten(S), T) if the enclosing function is async, or UP(S, T) otherwise.

which in the case of an async function does a flatten to produce an actual return type T, and then:

If the function literal is marked async then the inferred return type is Future<flatten(S)>.

where S is the actual return type (that is, T above).

I don't see why doing two flattens here is correct. Am I missing something, or is this a bug? Presumably in most cases doing a double flatten doesn't do anything, but in some cases it does (and seems wrong). Simpler example:

void test1() async {
  var f = Future<Future<int>>.value(Future<int>.value(3));
  var g = () async => (f as dynamic);
  print(g());
  print(await g());
}

void test2() async {
  var f = Future<Future<int>>.value(Future<int>.value(3));
//  var g = () async => f;
//  print(await g());
}


void main() {
  test1();
  test2();
}

Running this program prints out:

Instance of 'Future<dynamic>'
Instance of 'Future<int>'

Implying ( as expected ) that semantically we are doing a single await on the return value, returning a value of type Future<int> and then wrapping that in a Future<dynamic>.

If you uncomment the second line in the second test, you get the static error:

../../../tmp/example.dart:120:23: Error: A value of type 'Future<Future<int>>' can't be returned from an async function with return type 'Future<int>'.

which is as specified, but seems wrong.

[eernstg]

Good catch! I didn't have the intuition firmly enough in place to tell me that the second flatten should be double checked. ;-)

@lrhn wrote:

The extra flatten introduced in Future<flatten(Divergent<Divergent<int>>)>, as quoted above, doesn't correspond to anything in the runtime semantics, so if we specify it, it's probably a bug in the specification.

@leafpetersen wrote:

I don't see why doing two flattens here is correct.

Right, it is also my understanding that the last use of flatten is incorrect (and also that we've had it for quite some time without noticing the issue because it is almost always a no-op). However, I think we'd still need to apply flatten on the context type. So we would have this rule:

Otherwise, if T <: R then let S be T. Otherwise, let S be flatten(R) if the function literal is marked async, and R otherwise. The inferred return type of the function literal is then defined as follows:

• If the function literal is marked async then the inferred return type is Future<S>.

The updates are 'let S be flatten(R) ...' rather than R, and 'inferred return type is Future<S>' rather than Future<flatten(S)>.

[eernstg]

Cf. #3149.

[lrhn]

We have more problems, real soundness problems, with the generator functions.

import"dart:async";

void main() {
  FutureOr<Iterable<int>?> o1 = function();

  // Already here we have an `Iterable<dynamic>` with a static type which implies `Iterable<int>`.
  o1..l; // (1, null): _SyncStarIterable<dynamic> @ FutureOr<Iterable<int>?>
  
  // Hard to prove, since dart2js assumes soundness and doesn't do type checks which "can't fail".
  FutureOr<Iterable<int>?> o2 = function() as dynamic; // Error optimized away.
  o2 as FutureOr<Iterable<int>?>; // Error optimizied away.
  
  // Promote the other union types away.
  if (o2 is Future<Iterable<int>?>) {
    print("not");
  } else if (o2 == null) {
    print("not");
  } else {
    // Now static type is `Iterable<int>`, runtime type is `Iterable<dynamic>`. Unsoundness achieved!
    o2..l; // (1, null): _SyncStarIterable<dynamic> @ Iterable<int>
  }
  
  var t = DateTime.now().millisecondsSinceEpoch > 0; // Unpredictable true
  (t ? o2 : "") as FutureOr<Iterable<int>?>; // Finally throws!
}

// Return type of supertype of `Iterable<Never>`, so allowed.
// Inferred value type is `dynamic`, because we don't find the `int`. That's unsound.
FutureOr<Iterable<int>?> function() sync* {
  yield 1;
  yield null; // Should not be allowed. Is.
}

extension <T> on T {
  void get l {
    print("$this: $runtimeType @ $T");
  }
}

(Same issue for async* and Stream).

This is from dart2js, so I assume all compilers are affected to some extent. They may fail earlier if they don't optimize away as many "safe" type-checks. The VM fails on the first downcast from dynamic, but not on the direct o2 as ...; check.

On the other hand, with no declaration, but only a context type, it works fine:

  FutureOr<Stream<int>?> Function() f = () async* {
    yield 1;
    yield null;
  };

gives an error because Stream<int?> Function() is not assignable to FutureOr<Stream<int>?> Function();.
It's the lack of checking that the resulting Iterable<dynamic> return value is assignable to the declared ...Iterable<int>... return type that makes this go bad.

Probably because the inferred "element type" from the context is incorrectly set to Object? or dynamic, and the body then assuming that it can return an Iterable<dynamic>, and never checking again.

[eernstg]

The language specification does indeed specify a generator element type for the return type FutureOr<Iterable<int>?> which is dynamic (and similarly for other union types), so we need to change that. This PR proposes an updated text.

[leafpetersen]

// Return type of supertype of `Iterable<Never>`, so allowed.

Is it ever useful to have a return type which is not actually a subtype of Iterable<Object?> or a top type? Perhaps we should start by rejecting this program?

[lrhn]

It's no more or less reasonable to return Object than it is to return a top type.
If we should disallow some supertypes of Iterable, we should probably disallow any type which isn't assignable to Iterable<Object?>, and retain the "assignable to by Iterable<Never>" lower bound, leaving only Iterable<T> and dynamic types.

But it can actually be reasonable to have a return type of FutureOr<Iterable<T>>, because that's what you're given for free by inference in the callback of Future.then.
Similarly you may want to declare a method with return type Iterable<T>? and give it a default implementation that does not return null.

There is no good reason to disallow supertypes of Iterable which do specify the element type, and there is no good reason to disallow some of the supertypes which do not, but not all (except perhaps dynamic). It's fairly easy to figure out which is which, and what the specified element type is, we just haven't done so yet.
That's just an oversight, blindly inherited from a less sound language.

And it's not like we can't figure it out in other places:

FutureOr<Iterable<double>?> Function() l1 =
   ()=> [42];
   
  FutureOr<Iterable<double>?> Function() l2 =
    () sync* { yield* [42]; };

The first declaration "just works".
The second ... does less well, and it's not because it couldn't do just as well.
The error varies between analyzer and CFE, but neither gets the right element type.

[eernstg]

@leafpetersen wrote:

Is it ever useful to have a return type which is not actually a subtype of Iterable<Object?> or a top type?

As always, the return type of any given method could be forced by overrides:

class A {
  FutureOr<Iterable<int>?> m() => null;
}

class B extends A {
  FutureOr<Iterable<int>?> m() sync* { yield 1; yield 2; }
}

class C extends B {
  FutureOr<Iterable<int>?> m() => Future.value();
}

One might argue that an error on B.m would be gratuitous if it's only justified by "nobody needs that!".

[lrhn]

The quickest fix here would be to insert the check that the generated function type is actually assignable to the context type. Since it's not guaranteed. Then we can fix the spec to allow more things to insert compilable types.

[leafpetersen]

Similarly you may want to declare a method with return type Iterable<T>? and give it a default implementation that does not return null.

Ok, that makes sense. Seems a bit stretched, but in principle it's reasonable.