Type parameter is not preserved in type-erased context

[Mike278]

I have a class like this:

abstract class Foo<T extends Object> {
  List<T> read();
  void write(List<T> value);
}

And some subclasses that specify a concrete type parameter:

class StringFoo extends Foo<String> {
  @override List<String> read() => ['hello', 'world'];
  @override void write(List<String> values) {
    print('writing strings $values');
  }
}
class IntFoo extends Foo<int> {
  @override List<int> read() => [1,2,3];
  @override void write(List<int> values) {
    print('writing ints $values');
  }
}

And some top level functions that operate on Foo<T>s:

void processFoo<T extends Object>(Foo<T> f) {
  final data = f.read();
  // do some processing...
  f.write(data);
}

This works well in places where processFoo is called with a concrete type:

void main() {
  processFoo(IntFoo());
}

There are other places where I want to call processFoo with an instance of Foo whose concrete type is not known at compile time. For example:

Foo fooByName(String name) {
  switch (name) {
    case 's': return StringFoo();
    case 'i': return IntFoo();
    default: throw 'bad name $name';
  }
}

void processFooByName(String name) {
  final foo = fooByName(name);
  processFoo(foo);
}

This also seems to work:

void main() {
  processFooByName('i');
}

Months later I made what I thought was a minor refactor to processFoo

void processFoo<T extends Object>(Foo<T> f) {
  final data = f.read();
  // do some processing...
  f.write([for (final (i, x) in data.indexed) if (i % 2 == 0) x]);
}

processFoo(IntFoo()); still works fine, but now processFooByName('i'); throws a runtime type error: type 'List<Object>' is not a subtype of type 'List<int>' of 'values'.

I understand that fooByName has no choice but to return a Foo<Object>, and I understand that the runtime typecheck is required because Dart's class generics are unsafely covariant, but I can't seem to figure out how to implement processFooByName so that it doesn't throw, other than by inlining fooByName like this:

void processFooByName(String name) {
  switch (name) {
    case 's': return processFoo(StringFoo());
    case 'i': return processFoo(IntFoo());
    default: throw 'bad name $name';
  }
}

Is there any other way to preserve Foo's type argument in a "type-erased" context?

[Mike278]

I tried --enable-experiment=variance with the following changes and it looks like this works (because the runtime typecheck is removed?)

abstract class Foo<inout T extends Object> {
                // ^^^^^
  List<T> read();
  void write(List<T> value);
}

// ...

Foo fooByName(String name) {
  switch (name) {
    case 's': return StringFoo() as Foo;
                              // ^^^^^^
    case 'i': return IntFoo() as Foo;
                           // ^^^^^^
    default: throw 'bad name $name';
  }
}

[lrhn]

This is working as expected. And I don't see a better way to avoid it than the inlining that you do.

The static type of f.write inside processFoo is void Function(List<T>).

If T is Object?and the actualFoois aFoo, then doing f.write(f.read())will be allowed because the static types match up, and at runtime thewritemethod will check that it actually gets aList, which it does because it was created by the same fwhich is aFoo`.

However, if you create a new list, like f.write([...f.read()]), then it's implicitly doing f.write([...f.read()]).
If T is Object?, it's effectively doing f.write(<Object?>[...f.read()]), and then f.write will reject, by throwing at runtime, the argument because it's not a List<int>.

The reason T is Object? is that you call it from processFooByName without specifying a type argument, and with an argument which was created by fooByName, which returns Foo<Object?>.

All of this is mostly unavodiable for those particular functions.

I can't see a good way to avoid that without inlining, so that the call to processFoo knows the precise type of Foo it gets called with, so that it gets a type argument that mathces the runtime type of the value.

You have an unsafely covariant class, an generic parameter type, and an actual value which is a proper subtype of the static type. That means you can never use the static type for anything that is retained at runtime, because then it might not match the actual runtime type.

A static type system means that you can't have types that depends on runtime values. That's why fooByName cannot be written in a way where the return type is not at least Foo<Object>.
And that propagates to everywhere else, you cannot invent a type argument at runtime that wasn't in the program at compile-time.

[eernstg]

@Mike278, it is indeed working as intended, but this doesn't mean that it must work like that.

What you need is actually an existential open feature, that is, a construct that will allow you to "discover" and use the value of a type parameter from outside the location where that type parameter is in scope.

We don't have that as a general language mechanism at this time, but for your own classes (or indeed for any class where you have the opportunity to edit the code) you can get the same effect as a special case by adding a suitable instance method to the class. Here is the example, adjusted to have and use such a method (callWithT):

// `Foo` classes.

abstract class Foo<T extends Object> {
  List<T> read();
  void write(List<T> value);
  R callWithT<R>(R callback<X extends Object>(Foo<X> self)) =>
      callback<T>(this);
}

class StringFoo extends Foo<String> {
  @override
  List<String> read() => ['hello', 'world'];
  @override
  void write(List<String> values) {
    print('writing strings $values');
  }
}

class IntFoo extends Foo<int> {
  @override
  List<int> read() => [1, 2, 3];
  @override
  void write(List<int> values) {
    print('writing ints $values');
  }
}

// Functions operating on `Foo` classes.

void processFoo<T extends Object>(Foo<T> f) {
  f.callWithT<void>(<X extends Object>(self) {
    final data = self.read();
    // do some processing...
    self.write(data);
  });
}

void processFoo2<T extends Object>(Foo<T> f) {
  f.callWithT<void>(<X extends Object>(self) {
    final data = self.read();
    // do some processing...
    self.write([
      for (final (i, x) in data.indexed)
        if (i % 2 == 0) x
    ]);
  });
}

Foo<Object> fooByName(String name) {
  switch (name) {
    case 's':
      return StringFoo();
    case 'i':
      return IntFoo();
    default:
      throw 'bad name $name';
  }
}

void processFooByName(String name) {
  final foo = fooByName(name);
  processFoo(foo);
  processFoo2(foo);
}

void main() {
  processFoo(IntFoo());
  processFoo2(IntFoo());
  processFooByName('i');
  processFooByName('s');
}

When you get to this piece of code

    self.write([
      for (final (i, x) in data.indexed)
        if (i % 2 == 0) x
    ]);

you have a suitable typing of f, which allows you to write code that is protected from the covariance related run-time errors.

In particular, the value of T may be Object, which means that Foo<T> is Foo<Object>, in a situation where the actual object denoted by f is an instance of FooInt or FooString, which means that it is also typable as Foo<int> or Foo<String> respectively. In other words, the type Foo<T> is correct based on covariance, but when we are actually using covariance, and the class has a member like write, there is a potential for run-time type errors. This implies that Foo<Object> is a suboptimal type for this object (in a situation where we plan to call write).

The crucial point is that we can now use callWithT to obtain a precise typing (no covariance, hence no run-time type errors caused by covariance).

In the body of the callback, the object which is denoted by f is now accessible as self, and it is typed as a Foo<X>. Crucially, the value of X is precisely the value of the actual type argument of that object (no covariance).

One consequence of this is that the list literal used in the invocation of self.write gets a type argument of X, and it is indeed safe to pass a List<X> as the argument to self.write.

You can see that it works by running the code.

The main considerations are something like:

1. Do you have access to edit the class where callWithT must be added? If yes, proceed to step 2. Note that callWithT is a general 'existential open' feature for Foo, which means that it may be useful for many users of the Foo classes, not just your code, and this could imply that it could be added even to a class that you don't own.
2. Add callWithT to Foo.
3. Change the locations in your code where Foo is used in a manner which is not covariance-safe (that is, all call sites for write), such that they use callWithT as shown above.

Of course, you can use a shortcut in cases where the code is already known to be type safe even without an invocation of callWithT. For example,

    final data = f.read();
    // do some processing...
    f.write(data);

is safe even without the existential open (if f is final or treated as such, that is!), because data is known to be a List<X> such that X is the actual type argument of f at Foo (which may be T or it may be some subtype of T). You just need to be careful about various sources of unsoundness, e.g., that a list literal will get an inferred type argument which is based on the statically known types.

[eernstg]

I think we can close this issue: The discussion shows that the observed behavior is in line with the specification, it mentions that an existential open (emulation) can be used to eliminate the covariance related type errors, and no bugs are reported.

PS: It should be noted that we could have used statically checked variance as well (that is, we could have changed Foo such that it's type argument is invariant), but that would be incompatible with fooByName: That function would then have to use Object as its return type (or something like that) because Foo<int> and Foo<String> are no longer subtypes of Foo<Object>. So that would be a more substantial refactoring, and it's not even obvious how it could be expressed in a way that works well. That's the reason why I did not mention statically checked variance.

[Mike278]

Thank you @lrhn and @eernstg for your replies!

I think I mostly understand, but I have 2 follow-up questions:

1. Why does the invariant approach here work? Specifically, why doesn't as Foo throw? Shouldn't forcing T = Object violate the invariant that it must be exactly an int (for example)?
2. I tried implementing @eernstg's suggestion and realized I oversimplified part of the Foo class - the write method actually returns a Summary<T> (instead of void) that contains some metadata and the data that was written:

class Summary<T extends Object> {/*...*/}
abstract class Foo<T extends Object> {
  List<T> read();
  Summary<T> write(List<T> value);
}
Summary<T> processFoo<T extends Object>(Foo<T> f) {
  final data = f.read();
  // do some processing...
  return f.write(data);
}

With this additional consideration, I couldn't figure out how to spell callWithT:

Summary<T> processFoo<T extends Object>(Foo<T> f) {
  return f.callWithT<Summary<T>>(<X extends Object>(f) {
    final data = f.read();
    // do some processing...
    return f.write([for (final (i, x) in data.indexed) if (i % 2 == 0) x]); // `Summary<X>` isn't a `Summary<T>`
  });
}

---

I also tried implementing the "inline" approach in my real program and encountered a few more surprises. This triggers the error:

Iterable<Summary<Object>> processFoosByName(List<String> names) {
  return names.map(
    (name) => switch (name) {
      's' => processFoo(StringFoo()),
      'i' => processFoo(IntFoo()),
      _ => throw 'bad name $name',
    },
  );
}

but calling .toList() after the .map() fixes it? Presumably this is due to type inference being driven by the function's return type? Because if I assign the whole names.map(...) expression to a local variable and return the local variable, it works regardless of whether .toList() is present.

[eernstg]

Thanks!

Why does the invariant approach here work?

That's because statically checked variance support (dart-lang/language#524) has not yet been fully implemented: The compile-time checks will take variance into account, but the backends have not yet implemented the support for invariance and contravariance, and this means that the cast IntFoo() as Foo (which means IntFoo() as Foo<Object>) will succeed.

You can emulate the full semantics of invariance, though. Here's a slightly shorter version using (partially implemented) statically checked variance:

// Use '--enable-experiment=variance'

abstract class Foo<inout T extends Object> {
  List<T> read() => [];
  void write(List<T> value) {}
}

class IntFoo extends Foo<int> {}
class StringFoo extends Foo<String> {}

Foo fooByName(String name) {
  switch (name) {
    case 's': return StringFoo() as Foo; // Succeeds, incorrectly.
    case 'i': return IntFoo() as Foo; // Succeeds, incorrectly.
    default: throw 'bad name $name';
  }
}

void main() {
  fooByName('i');
  fooByName('s');
}

The same thing, emulated:

typedef Inv<X> = X Function(X);

typedef Foo<T extends Object> = _Foo<T, Inv<T>>;

abstract class _Foo<T extends Object, Invariance extends Inv<T>> {
  List<T> read() => [];
  void write(List<T> value) {}
}

class IntFoo extends Foo<int> {}
class StringFoo extends Foo<String> {}

Foo fooByName(String name) {
  switch (name) {
    case 's': return StringFoo() as Foo; // Throws, as it should.
    case 'i': return IntFoo() as Foo; // Throws, as it should.
    default: throw 'bad name $name';
  }
}

the write method actually returns a Summary<T>

This is the point where we need to help the type system a little bit: It is actually true that X is a subtype of T (and hence, Summary<X> is a subtype of Summary<T>). This means that it is safe to put as Summary<T> on the returned expression when you know that it has type Summary<X>.

That's not nice, but there is no way that I can think of which will establish as a statically known property that X is a subtype of T. We would probably need to have a proper language mechanism ('existential open') for that.

class Summary<T extends Object> {/*...*/}

abstract class Foo<T extends Object> {
  List<T> read();
  Summary<T> write(List<T> value);
  R callWithT<R>(R callback<X extends Object>(Foo<X> self)) => callback(this);
}

/*
Summary<T> processFoo<T extends Object>(Foo<T> f) {
  final data = f.read();
  // do some processing...
  return f.write(data);
}
*/

Summary<T> processFoo<T extends Object>(Foo<T> f) {
  return f.callWithT<Summary<T>>(<X extends Object>(f) { // The type argument would be inferred, too.
    final data = f.read();
    // do some processing...
    return f.write([
      for (final (i, x) in data.indexed)
        if (i % 2 == 0) x
    ]) as Summary<T>; // Using guaranteed property `X <: T`.
  });
}

We could of course also test this using is Summary<T>, but we can't do anything useful if it fails, given that X <: T is a fact, it's just not a fact that the type system knows about. (So it doesn't fail, period! ;-).

The map issue is surely because of type inference.

[Mike278]

has not yet been fully implemented

Ah gotcha, I didn't realize it shouldn't have worked! I actually first tried the emulated invariance approach, as I'd seen it suggested in some other similar issues, and I got the compile-time error on as Foo as expected... but then had no idea how to leverage that into a solution 😝

It is actually true that X is a subtype of T (and hence, Summary<X> is a subtype of Summary<T>)

Thanks, this helped it click for me.