Downwards inference of yield* is underspecified

[stereotype441]

How should we expect this code to be analyzed?

dynamic f() sync* {
  yield* g()..foo();
}

T g<T>() => throw 'T=$T';

main() {
  for (var x in f()) {
    print('x=$x');
  }
}

Currently, the analyzer and CFE both accepts this code without issuing any compile-time errors. The runtime behavior is to print:

Unhandled exception:
T=dynamic
#0      g (file:///home/paulberry/tmp/proj/test.dart:5:13)
#1      f (file:///home/paulberry/tmp/proj/test.dart:2:10)
#2      _SyncStarIterator.moveNext (dart:async-patch/async_patch.dart:595:13)
#3      main (file:///home/paulberry/tmp/proj/test.dart:8:17)
#4      _delayEntrypointInvocation.<anonymous closure> (dart:isolate-patch/isolate_patch.dart:313:19)
#5      _RawReceivePort._handleMessage (dart:isolate-patch/isolate_patch.dart:192:12)

This indicates that the context type being passed to the operand of yield* is either the unknown type (_) or dynamic. Reading through the implementation, I'm pretty certain it's the unknown type.

But resources/type-system/inference.md says:

• If the enclosing function is marked sync*, then for each yield* e; statement in the block, let S be the inferred type of e, using the local type inference algorithm described below with a typing context of Iterable<K>; let E be the type such that Iterable<E> is a super-interface of S; and update T to be UP(E, T).

Which suggests that the context should be Iterable<K> for some K.

K is defined to be "the typing context for the function body as computed above from the imposed return type schema." It's not entirely clear what this refers to, but the definition of the "imposed return type schema" is as follows:

The return type of the context function type is used at several points during inference. We refer to this type as the imposed return type schema. Inference for each returned or yielded expression in the body of the function literal is done using a context type derived from the imposed return type schema S as follows:

• If the function expression is neither async nor a generator, then the context type is S.
• If the function expression is declared async* and S is of the form Stream<S1> for some S1, then the context type is S1.
• If the function expression is declared sync* and S is of the form Iterable<S1> for some S1, then the context type is S1.
• Otherwise, without null safety, the context type is FutureOr<flatten(T)> where T is the imposed return type schema; with null safety, the context type is FutureOr<futureValueTypeSchema(S)>.

It's difficult to say whether this spec text is meant to apply to the function f in the code example above. On the one hand, the spec text is clearly talking about a "function expression" (which the function f is not). On the other hand, there are no other mentions of yield* anywhere else in the doc specifying the expected behavior when the yield* appears in a function rather than a function expression.

If we assume the text is intended to apply in this case, then it a literal reading of it produces suggests that the imposed return type schema should be FutureOr<futureValueTypeSchema(_)>, which is FutureOr<_>. But this can't be what we want, because it never makes sense for the operand of yield* to be a future.

To make matters worse, the current behavior (where a return type of dynamic causes the operand of yield* to be inferred with a type context of _) is not covered by any tests. (I found this out by breaking it and seeing that no tests failed).

I'm not 100% sure what the right fix is here; I'm still researching. Filing this issue to document what I've learned so far.

[eernstg]

I think it would be useful to distinguish the case where the generator function is specified as a function declaration (a top-level or local function, or a static or instance method), and the case where it is a function literal (aka function expression).

A function declaration that includes a return type annotation has the denoted type (which is not a type schema) as its return type. A top-level function declaration or a static method declaration with no return type annotation has the return type dynamic. An instance method with no return type annotation may obtain its return type by override inference, and otherwise the return type is dynamic.

The language specification defines the element type of a generator function here. For example, a synchronous generator function with return type Iterable<int>? has element type int.

This implies that we can determine the return type of a given generator function of any of those kinds unambiguously, and it is a type rather than a type schema, and this yields a specific type which is the element type of that function.

Consider a generator function f of any of those kinds with return type R and element type E. I would expect the context type of e in a statement of the form yield* e; that occurs in the body of f to be Iterable<E> when that function is synchronous, and Stream<E> when it is asynchronous.

I think 'inference.md' needs to be adjusted to say this if (as it seems) the current text has no rules about these cases.

---

The remaining kinds are local functions and function literals, and they are handled using the rules in 'Function literal return type inference' (and 'Local return type inference' where it just says that we should use the same rules as for a function literal with no context type).

I think those rules are nearly working as stated:

Assume that the function literal has a context type schema C0 which is a function type, and C0 has a return type schema S, then the context type schema for e in yield* e; in a synchronous generator function is S1 when S is Iterable<S1> for some type schema S1.

The case where S is not of the form Iterable<S1> for any S1 is missing. We should use the notion of the element type (schema) of the given imposed return type schema S, such that we could handle an S which is dynamic (or any other type which is not an error and not of the form Iterable<...>), and get a reasonable context type.

Given that this case fails to match the situation where S is dynamic, it seems that we'd proceed to use the 4th item in the list, which is only intended to be applicable for a function whose body is marked async.

I proposed some changes in #4673.

[stereotype441]

I think it would be useful to distinguish the case where the generator function is specified as a function declaration (a top-level or local function, or a static or instance method), and the case where it is a function literal (aka function expression).

I’m happy to distinguish these two cases as part of our thought process, but I hope once we're done thinking things through we will be able to come up with rules for how to type infer yield and yield* that mostly unify the two cases, because (a) the analyzer and front end implementations unify these two cases pretty early on in the analysis process, and it would be nice not to have to change that, and (b) unifying these cases seems like it would align well with our design intent (which is for the type analysis of function declarations and function literals to match very closely).

A function declaration that includes a return type annotation has the denoted type (which is not a type schema) as its return type. A top-level function declaration or a static method declaration with no return type annotation has the return type dynamic. An instance method with no return type annotation may obtain its return type by override inference, and otherwise the return type is dynamic.

The language specification defines the element type of a generator function here. For example, a synchronous generator function with return type Iterable<int>? has element type int.

This implies that we can determine the return type of a given generator function of any of those kinds unambiguously, and it is a type rather than a type schema, and this yields a specific type which is the element type of that function.

Consider a generator function f of any of those kinds with return type R and element type E. I would expect the context type of e in a statement of the form yield* e; that occurs in the body of f to be Iterable<E> when that function is synchronous, and Stream<E> when it is asynchronous.

I think this is a reasonable expectation. I dug through the analyzer implementation carefully, and AFAICT, it differs from your expectation solely in the case where the generator function's return type is dynamic (which is what led me to file this issue in the first place, so no surprise there).

I haven't dug carefully through the front end implementation yet; its nomenclature and algorithms don't seem to line up with the spec as well as the analyzer's, though I suspect its behavior is similar, based on the fact that the world isn't on fire 😃.

I think 'inference.md' needs to be adjusted to say this if (as it seems) the current text has no rules about these cases.

Agreed!

The remaining kinds are local functions and function literals, and they are handled using the rules in 'Function literal return type inference' (and 'Local return type inference' where it just says that we should use the same rules as for a function literal with no context type).

I agree that the rules in 'Function literal return type inference' should be applied to function literals (also known as "function expressions" in the spec). But for local functions (by which I assume you mean those introduced by a function declaration statement, which the spec also calls a "local function declaration"), I'm not convinced that the rules in 'Function literal return type inference' should apply. Those rules refer extensively to the typing context, which is the context type in which the function literal expression is being inferred, and that notion doesn't really apply to function declaration statements (because they're not expressions).

For what it's worth, the analyzer uses nearly all the same logic to handle function declaration statements and top level function declarations (and there are no functional differences between the two), so I would recommend lumping function declaration statements into the first category rather than the second.

I think those rules are nearly working as stated:

Assume that the function literal has a context type schema C0 which is a function type, and C0 has a return type schema S, then the context type schema for e in yield* e; in a synchronous generator function is S1 when S is Iterable<S1> for some type schema S1.

The case where S is not of the form Iterable<S1> for any S1 is missing. We should use the notion of the element type (schema) of the given imposed return type schema S, such that we could handle an S which is dynamic (or any other type which is not an error and not of the form Iterable<...>), and get a reasonable context type.

Given that this case fails to match the situation where S is dynamic, it seems that we'd proceed to use the 4th item in the list, which is only intended to be applicable for a function whose body is marked async.

I think I'm on board with the gist of what you're proposing, though as I said before I would prefer if we can find a way to specify it that aligns better with the way the implementations unify the two cases. In particular, here's the complete set of rules for how the analyzer handles yield and yield* in generators, and how I believe I would change it to match what you're proposing:

• For any top level function, method, or local function declaration (statement), let BodyInferenceContext.imposedType be:
  • null if the return type of the function, method, or local function declaration is dynamic. (I would change this from null to _.)
  • T if the return type of the function, method, or local function declaration is T.
• For any function expression, let BodyInferenceContext.imposedType be:
  • null if the context type of the function expression is not a function type schema. (I would change this from null to _.)
  • Otherwise, null if the context type of the function expression is a function type schema whose return type schema is dynamic or _ (I would change this from null to _.)
  • Otherwise, S if the context type of the function expression is a function type whose return type schema is S.
• Let BodyInferenceContext.contextType be:
  • null if BodyInferenceContext.imposedType is null. (This would no longer apply.)
  • Otherwise, S if the function is sync* and BodyInferenceContext.imposedType implements* Iterable<S>.
  • Otherwise, S if the function is async* and BodyInferenceContext.imposedType implements* Stream<S>.
  • Otherwise, _.
• Let the type context for the expression e in yield e; be:
  • _ if BodyInferenceContext.contextType is null. (This would no longer apply.)
  • Otherwise, BodyInferenceContext.contextType.
• Let the type context for the expression e in yield* e; be:
  • _ if BodyInferenceContext.contextType is null. (This would no longer apply.)
  • Otherwise, Iterable<BodyInferenceContext.contextType> if the function is sync*.
  • Otherwise, Stream<BodyInferenceContext.contextType> if the function is async*.

*Note that the analyzer has a notion of what it means for one type schema to implements another; this is basically an extension of the spec's notion of what it means for one type to implement another, except that it handles _ in the obvious way. We should probably update the spec's definition to handle type schemas.

(I've simplified this from what's in the analyzer implementation by dropping the cases that aren't relevant to generators, to make the discussion easier to follow.)

I proposed some changes in #4673.

Thanks! I'll go make additional comments over there.

[eernstg]

I think I've actually written the rules in #4673 such that they match up with your rules here, except that I'm using 'imposed return type schema' to denote the actual context type schema which is used with e in return e; and yield e; (and in the expression which is the body for an => function).

This means that we don't have to change T to Iterable<T> when we're considering each return of an async function, or each yield of a generator function.

This also means that there's less room for confusion when we use this imposed return type schema K with a yield* e; statement, because we already have a K which is suitable for inference of individual objects, and then we use Iterable<K> to infer the e which is an iterable, and similarly for Stream<K> and an e which is a stream.

[lrhn]

I think we should look towards FutureValueTypeScheme for how to extract the element type from the function's return type.

That's specified as:

• FutureValueTypeScheme(Future<S>) = S
• FutureValueTypeScheme(FutureOr<S>) = S
• FutureValueTypeScheme(Object) = Object?
• FutureValueTypeScheme(S?) = FutureValueTypeScheme(S)
• FutureValueTypeScheme(Object) = Object?
• FutureValueTypeScheme(void) = void
• FutureValueTypeScheme(dynamic) = dynamic (or _, does it ever matter?)
• FutureValueTypeScheme(_) = _

We should have similar IterableElementTypeScheme and StreamElementTypeScheme functions that extract the type of the iterable/stream, but also preserves being void or being non-dynamic.

So:

• IterableElementTypeScheme(Iterable<S>) = S
• IterableElementTypeScheme(Object) = Object?
• IterableElementTypeScheme(S?) = IterableElementTypeScheme(S)
• IterableElementTypeScheme(Object) = Object?
• IterableElementTypeScheme(void) = void
• IterableElementTypeScheme(dynamic) = dynamic (or _)
• IterableElementTypeScheme(_) = _

The rule for finding the context type for sync*/async* would then be:

Let BodyInferenceContext.contextType be:

• null if BodyInferenceContext.imposedType is null. (This would no longer apply.)
• Otherwise, IterableElementTypeScheme(S) if the function is sync* and BodyInferenceContext.imposedType is S.
• Otherwise, StreamElementTypeScheme(S) if the function is async* and BodyInferenceContext.imposedType is S.
• Otherwise, _.

Hmm. I'm pretty sure I have written a specification for that at some point ... and there it was: https://github.com/dart-lang/language/pull/3151/changes - I can't even remember why it wasn't landed any more.

(The rest looks fine to me ... other than the spurious flatten in FutureOr<flatten(S)>.)

[eernstg]

Right, the language specification uses the element type of a generator function to denote nearly the same thing as the type function that you've named IterableElementTypeScheme. The PR #4673 introduces the 'element type of a type' in order to separate out just the type function, and updates inference.md to use this.

I had forgotten about #3151. I think #3151 and #4673 have a rather similar purpose, but #3151 is from 2023, so perhaps it's going to require some more updates before it would fit into today's inference.md. What do you think about #4673?