Generator functions element type issue

[sgrekhov]

Edit by eernstg: This issue is now an implementation issue for the soundness violation which is described below. We have the following remaining subtasks:

• [ddc] Generator functions element type soundness issue #54412
• [dart2wasm] Generator functions element type soundness issue #54413

---

The following co19 tests fail on all runtime platforms
https://github.com/dart-lang/co19/blob/master/Language/Functions/element_type_A01_t03.dart
https://github.com/dart-lang/co19/blob/master/Language/Functions/element_type_A01_t04.dart
https://github.com/dart-lang/co19/blob/master/Language/Functions/element_type_A01_t06.dart
https://github.com/dart-lang/co19/blob/master/Language/Functions/element_type_A02_t03.dart
https://github.com/dart-lang/co19/blob/master/Language/Functions/element_type_A02_t04.dart
https://github.com/dart-lang/co19/blob/master/Language/Functions/element_type_A02_t06.dart

Example

import "dart:async";
import "../../Utils/expect.dart";

FutureOr<Iterable<int>?> foo() sync* {
  yield 1;
  yield 2;
  yield 3;
}

main() {
  FutureOr<Iterable<int>?> o = foo() as dynamic; // Runrime error: type '_SyncStarIterable<dynamic>' is not a subtype of type 'FutureOr<Iterable<int>?>'
  o as FutureOr<Iterable<int>>;
  Expect.isRuntimeTypeImplementsIterable<int>(o);
}

According to the Dart specification

We define the element type of a generator function f as follows: Let S
be the union-free type derived from the declared return type of f. If f is a
synchronous generator and S implements Iterable for some U (11.2) then
the element type of f is U. If f is an asynchronous generator and S implements
Stream for some U then the element type of f is U. Otherwise, if f is a
generator (synchronous or asynchronous) and S is a supertype of Object (which
includes Object itself) then the element type of f is dynamic.

In fact, it looks like the element type of a generator function is always dynamic

Tested on Dart SDK version: 3.3.0-149.0.dev (dev) (Fri Nov 17 16:02:24 2023 -0800) on "windows_x64"

[eernstg]

Note that the observed behavior causes soundness issues:

import "dart:async";

FutureOr<Iterable<int>?> foo() sync* {
  yield 1;
  yield 2;
  yield 3;
}

main() {
  var o = foo(); // `FutureOr<Iterable<int>?>`.
  if (o is! Future<Object?>) {
    // Not a future, so `o` is promoted to `Iterable<int>?`:
    // o.length; // Error, confirms `?` in the type.
    o?.length; // OK, confirms `Iterable` in the type.
    o!; // Promote to `Iterable<int>`.
    var xs = o.toList(); // Static type of `xs` is `List<int>`.
    (xs as dynamic).add(true); // Succeeds -- it's not a `List<int>` after all.
    print(xs.last.isEven); // Soundness issue: Calling `isEven` on `true`.
  }
}

[eernstg]

Actually, it looks like this issue could be turned into a comment on #53052: That's already the implementation issue for the spec update that introduced the text which was quoted here.

@chloestefantsova, it looks like something wasn't handled in 4352f10 after all?

[chloestefantsova]

@eernstg I don't see how that's a CFE issue. The generated Kernel code looks ok to me. Do I miss anything?

library;
import self as self;
import "dart:core" as core;
import "dart:async" as asy;

import "dart:async";

static method foo() → FutureOr<core::Iterable<core::int>?> sync* {
  yield 1;
  yield 2;
  yield 3;
}
static method main() → dynamic {
  FutureOr<core::Iterable<core::int>?>o = self::foo();
  if(!(o is asy::Future<core::Object?>)) {
    let final core::Iterable<core::int>? #t1 = o{core::Iterable<core::int>?} in #t1 == null ?{core::int?} null : #t1{core::Iterable<core::int>}.{core::Iterable::length}{core::int};
    o{core::Iterable<core::int>?}!;
    core::List<core::int> xs = o{core::Iterable<core::int>}.{core::Iterable::toList}(){({growable: core::bool}) → core::List<core::int>};
    (xs as dynamic){dynamic}.add(true);
    core::print(xs.{core::Iterable::last}{core::int}.{core::int::isEven}{core::bool});
  }
}

[eernstg]

If it isn't an CFE issue then it must be a backend issue, because it isn't a non-issue. ;-)

Here's a variant of the example that shows (1) we have unsoundness, and (2) some tests do not reveal the unsoundness (presumably because they are translated into a no-op):

import "dart:async";

FutureOr<Iterable<int>?> foo() sync* {
  yield 1;
  yield 2;
  yield 3;
}

Object? id(Object? x) => x;

main() {
  FutureOr<Iterable<int>?> o = foo() as dynamic;
  print(o.runtimeType); // '_SyncStarIterable<dynamic>'.
  print(o is Iterable<int>); // 'false'.
  print(o is Iterable<int>?); // 'false'.
  print(o is FutureOr<Iterable<int>?>); // "Unnecessary type check; the result is always 'true'", but prints 'false'.
  o as FutureOr<Iterable<int>?>; // Succeeds.
  print('Still running!');
  id(o) as FutureOr<Iterable<int>?>; // Throws.
}

The execution throws at the end, demonstrating that we can get as to detect that o isn't a FutureOr<Iterable<int>?>. However, the type check 2 lines earlier didn't detect this fact, and neither did the dynamic type check that I would expect to get at the initialization of o.

Of course, the underlying issue is that foo returns an Iterable<dynamic>, and it should have been an Iterable<int>.

About configurations: I see "Still running!" (that is, I see the bug) with dart compile js, dart compile exe, but not with a plain dart.

[eernstg]

@mkustermann, @sigmundch, WDYT? Can you explain how a function with return type FutureOr<Iterable<int>?> can return an object of type Iterable<dynamic>?

I guess it's perfectly OK that this unsoundness isn't detected by the subsequent type checks because they can be compiled to no-ops when we have soundness. It just looks funny when we have "the result is always 'true'" from the analyzer and then 'false' at run time. ;-)

[sigmundch]

cc @rakudrama

It's quite possible this is an implementation bug - it doesn't appear like dart2js and ddc are using the type parameter extracted from the generator signature in their lowering for generator methods. In contrast, it does appear that they use it for async* generators.

[sigmundch]

Actually, we do seem to extract the type parameter when the type is not a FutureOr type, for example:

Iterable<int>? g() sync* { yield 1; }

Produces a _SyncStarIterable<int>, instead of a _SyncStarIterable<dynamic>.

[sigmundch]

Based on the logic here:

sdk/pkg/compiler/lib/src/js_model/element_map_impl.dart

Line 2234 in c3210c3

case AsyncMarker.SYNC_STAR:

it appears that we may need to incorporate additional logic to model FutureOr return types when inferring the element type from sync* and async* functions.

[sigmundch]

cc @fishythefish - I don't believe this relates to #54311, but there is some overlap, so you may be interested in this as well.

[fishythefish]

Ack. When I was fixing that issue, I was wondering if I should do something similar for the sync* and async* cases. AFAIK, we have futureValueType only for the async case (because we have FutureOr to complicate matters but not IterableOr or StreamOr). If there's an equivalent precomputed type for the generator cases, that would be great. Otherwise, I can look into where we're deviating from the spec.

This is also an area of the compiler where we seem to always use dynamic as the last resort rather than throwing. It might be worth changing that so we can distinguish between failure and an intentional dynamic.

[fishythefish]

https://dart-review.googlesource.com/c/sdk/+/341337 should fix this in dart2js, though it would be nice to get the element type directly from the CFE rather than having yet another implementation of the element type computation.

@sgrekhov: https://github.com/dart-lang/co19/blob/master/Language/Functions/element_type_A02_t06.dart does not start passing, but I think that test is incorrect: Stream.toList has return type Future<List<T>>, not List<T>. I think the it2 case is missing the second await that it1 has.

[fishythefish]

@eernstg: What's the expected behavior of the two snippets you provided above?

For the first one, dart2js previously showed unsoundness (by trying to invoke a nonexistent method) and now instead throws a TypeError when we attempt to add a bool instead of an int. I think this is correct.

For the second one, you said that Still running! indicates a bug, but that doesn't seem right. Since o is an Iterable<int>, I believe it should print _SyncStarIterable<int>, then true three times, then Still running!, with both casts succeeding. If I run the example with plain dart, it's true that I don't see Still running!, but I think it's because the initial assignment to o fails (incorrectly):

Unhandled exception:
type '_SyncStarIterable<dynamic>' is not a subtype of type 'FutureOr<Iterable<int>?>'

[eernstg]

What's the expected behavior

First, the entire semantics of Dart must be constrained to provide soundness. This means that whatever a program does, if it's not sound then we need to revisit the specified semantics to see if there's a bug in the specification, and the relationship between the specified semantics and the implemented semantics. In this case the implemented semantics differs from the specified semantics, and the result violates soundness.

The specification was corrected recently by the introduction of the element type of a generator function. The type of the object returned from an invocation of a function whose body is sync* was not really specified previously, but now it is specified explicitly: It's an object whose run-time type implements Iterable<T>, where T is the element type of that function.

In the example here we have a sync* function whose return type is FutureOr<Iterable<int>?> and whose returned value is a _SyncStarIterable<dynamic>. The latter is not a subtype of the former, and that is a soundness violation. But the returned object should have a type that implements Iterable<int>, which implies that the soundness violation goes away if the function would just return an object with the specified type.

All other parts of the example are just probing the actual run-time type of the returned object as well as the treatment of the returned object during static analysis. Everything confirms the assumption that the static analysis trusts the declared return type (so we think we have a FutureOr<Iterable<int>?>, and some configurations like dart compile exe will even eliminate some type checks whose result is "known" assuming soundness).

So there is really only one item in the list of expected (but not observed) behaviors: "foo should return an Iterable<int>".

For the first one, ...
I think this is correct.

In this example the unsoundness consists in having a reference of type List<int> to an object whose type implements List<dynamic>. We succeed in adding true to that list (dynamically) and then invoking isEven on that element, but this is all fine for an object of type List<int>. The only thing that needs to be corrected is that we should not be able to get a reference of type List<int> whose value is an object whose type implements List<dynamic>, the rest is good for any sound situation.

If dart2js has been changed such that we get a TypeError during (xs as dynamic).add(true) then the semantics was probably changed such that xs is no more a List<dynamic>, it's actually a List<int>. That's exactly what we need.

For the second one, you said that Still running! indicates a bug

You're right, that was sloppy. The bug is still the soundness violation created by foo returning an Iterable<dynamic>. However, the last type test (is) prints 'false', and then the type check (as) checking for the exact same type completes without throwing. That should never happen (if is says that an object doesn't have a type T then as T should throw), which is bug-ish. You could claim that it isn't a bug because it wouldn't ever happen as long as the assumption about soundness is justified. In any case, soundness is important exactly because there are so many things we can't rely on when it has been violated.

The very last type check uses id(o) rather than o, and this makes all configurations perform an actual type check (clearly, the one that uses o is compiled to a no-op in some configurations, because the compiler "already knows that the type check will succeed"), so here we finally get the dynamic error that we should have gotten in the check on o.

Again, I think everything should be working correctly (including the optimizations that turn o as T into a no-op) if foo is corrected such that it returns an Iterable<int>.

But then we have this:

... it's because the initial assignment to o fails (incorrectly):

Unhandled exception:
type '_SyncStarIterable<dynamic>' is not a subtype of type 'FutureOr<Iterable<int>?>'

As long as we have this, the bug which is the core of this issue has not been fixed. I assume this is what you mean by 'incorrectly': The incorrect thing is that foo returns an Iterable<dynamic>, not that the type check throws in response to that return value.

[sgrekhov]

@sgrekhov: https://github.com/dart-lang/co19/blob/master/Language/Functions/element_type_A02_t06.dart does not start passing, but I think that test is incorrect: Stream.toList has return type Future<List>, not List. I think the it2 case is missing the second await that it1 has.

Thank you! Fixed by dart-lang/co19#2429

[fishythefish]

@eernstg: Thanks, in that case, I think dart2js is working correctly now.

[alexmarkov]

VM is updated for the changed language spec in 6b12473.

Leaving this issue open as DDC and dart2wasm should be also updated.

[eernstg]

@alexmarkov wrote:

Leaving this issue open as DDC and dart2wasm should be also updated.

Thanks! I created separate issues for the subtasks: #54412 and #54413.

[fishythefish]

Highlighting for visibility: https://dart-review.googlesource.com/c/sdk/+/341662 renamed FunctionNode.futureValueType to FunctionNode.emittedValueType, and in the sync*/async* cases, it contains the element type. Hopefully this takes care of the required type algebra for all the backends.