Its is scary to use <Iterable>.firstWhere(orElse: ...)

[matanlurey]

Similar issues:

• Would like a way to avoid raw generic types #33119 (comment)
• Give users more help in solving contravariance issues #33697
• Allow variadic control of generics (i.e. List) #33812 (/cc @joeconwaystk)

Consider the following, fairly simple example of using <Iterable>.firstWhere:

class Asset {
  final String name;
  Asset(this.name);
  void printMe() => print('$name <$runtimeType>');
}

void main() {
  final assets = [Asset('A'), Asset('B')];
  printBestAsset(assets);
}

void printBestAsset(List<Asset> assets) {
  assets
    .firstWhere((a) => a.name == 'A', orElse: () => assets.first)
    .printMe();
}

This properly prints, as expected, A <Asset>. Neat! Let's get polymorphic.

class Asset {
  final String name;
  Asset(this.name);
  void printMe() => print('$name <$runtimeType>');
}

// The irony of "Sound" is semi-intentional.
class SoundAsset extends Asset {
  SoundAsset(String name) : super(name);
}

void main() {
  final assets = [SoundAsset('A'), SoundAsset('B')];
  printBestAsset(assets);
}

void printBestAsset(List<Asset> assets) {
  //  ERROR:
  // TypeError: Closure 'printBestAsset_closure0': 
  //     type '() => Asset' is not a subtype of type '() => SoundAsset'
  assets
    .firstWhere((a) => a.name == 'A', orElse: () => assets.first)
    .printMe();
}

I looked at this with 3 other Google/Dart team engineers, until @alorenzen mentioned "well, that's why Java has ? extends T". Here is the page from "Effective Java", highlighting exactly that:

... and we realized we could write this in Dart too:

class Asset {
  final String name;
  Asset(this.name);
  void printMe() => print('$name <$runtimeType>');
}

// The irony of "Sound" is semi-intentional.
class SoundAsset extends Asset {
  SoundAsset(String name) : super(name);
}

void main() {
  final assets = [SoundAsset('A'), SoundAsset('B')];
  printBestAsset(assets);
}

void printBestAsset<A extends Asset>(List<A> assets) {
  assets
    .firstWhere((a) => a.name == 'A', orElse: () => assets.first)
    .printMe();
}

... though, contrast this with Java's API of List<? extends Asset>, which seems more obvious.

Questions:

• Where in the language tour or style guide do we have suggestions to help here?
• Can we have lints or strict warnings that aid the user to write this? It was hard for 3 of us.

[DanTup]

Why does this happen? If you copy the implementation of firstWhere out of List and write it with a generic type arg, or either of the specific type, it seems like they all work.

E firstWhere1<E>(List<E> elements, bool test(E element), {E orElse()}) {
  for (E element in elements) {
    if (test(element)) return element;
  }
  if (orElse != null) return orElse();
  throw 'no element';
}

SoundAsset firstWhere2(List<SoundAsset> elements, bool test(SoundAsset element), {SoundAsset orElse()}) {
  for (SoundAsset element in elements) {
    if (test(element)) return element;
  }
  if (orElse != null) return orElse();
  throw 'no element';
}

Asset firstWhere3(List<Asset> elements, bool test(Asset element), {Asset orElse()}) {
  for (Asset element in elements) {
    if (test(element)) return element;
  }
  if (orElse != null) return orElse();
  throw 'no element';
}

(I was wondering if firstWhere could be fixed in List so the user wouldn't need to change anything; but since I couldn't repro it with the function outside of List I got stuck!).

[lrhn]

tl;dr: It happens because of Dart's unsafe covariant class generics combined with static inference.

The signature of List<E>.firstWhere is E firstWhere(bool Function(E), {E Function() orElse}).
Notice how E Function() in a parameter position uses the type parameter E contravariantly.

Now, if you have a List<SoundAsset>, its firstWhere signature is SoundAsset firstWhere(bool Function(SoundAsset), {SoundAsset Functio() orElse }).
The call in printBestAsset has the form

assets.firstWhere((a) => a.name == 'A', orElse: () => assets.first)

where assets has static type List<Asset>. Static inference infers the types of () => assets.first as Asset Function().

We are allowed to call printBestAsset with a List<SoundAsset> because of unsafe covariant class generics. The call above type-checks statically. At run-time we try to pass an Asset Function() as argument where a SundAsset Function() is expected, and that's not a valid assignment so you get a run-time error.

If the type system was smarter (probably way smarter than we can ever expect), it could recognize that the type of elements is not really List<Asset>, but List<T extends Asset> for some T. It would then extract that T and use that as the return type of () => assets.first (which is sound reasoning), and everything would work.

That's what happens when you add the extra type parameter:

void printBestAsset<A extends Asset>(List<A> assets) {
  assets
    .firstWhere((a) => a.name == 'A', orElse: () => assets.first)
    .printMe();
}

Here you say that the list is a List<A extends Asset>. It's not automatic, the caller has to tell you which sub-type of Asset it is, and in this example that's handled by inference. It's not exracting the type from the list, it's just passing the type as well, in parallel with the value (and obviously, you can pass a wrong type, say SoundAsset when the real list is has the proper subtype List<StereoSoundAsset>.

What would actually solve the problem would be to declare List<E>.firstWhere as (in Java terms):

T firstWhere<T super E>(bool Function(E) test, {T Function() orElse});

Then you would be able to say which asset type you want, as long as it includes both the elements of the list and the value returned by orElse. It would make the type of orElse not be restricted by the element type (which is what fails here, because the element type is unsafely covariant), but by the expected return type.
Too bad we don't have super-bounded types :)

[DanTup]

Thanks for the detailed explanation! :-) I think I'd overlooked this:

We are allowed to call printBestAsset with a List<SoundAsset> because of unsafe covariant class generics.

I actually ran this code this in C# before commenting and didn't get any errors - but I just tested again and realise that it was because I'd used an SoundAsset[] and not a List<SoundAsset>. In C# arrays are covariant and type checked at runtime:

System.ArrayTypeMismatchException: Attempted to access an element as a type incompatible with the array.

I'm not sure I'd ever come across this before and always assumed it would've failed to compile (as it does with a List<T>). I think I would've assumed strong Dart also wouldn't allow this; but I guess that's not the case (though I'm curious if it's stuck this way forever?).

Edit: Heh, apparently it's Java's fault C# has it, and it seems to be regretted =)

Unfortunately, this particular kind of covariance is broken. It was added to the CLR because Java requires it and the CLR designers wanted to be able to support Java-like languages. We then up and added it to C# because it was in the CLR. This decision was quite controversial at the time and I am not very happy about it, but there’s nothing we can do about it now.

[matanlurey]

@lrhn:

Is there a particular reason we can't change, say, firstWhere to:

T firstWhere<T extends E>(bool Function(E) test, {T Function() orElse});

[DanTup]

I was wondering that; but wasn't sure if orElse being optional complicated things (you couldn't infer T?). I also wasn't entirely sure how super different from extends; some StackOverflow answers convinced me they are different, but it went over my head!

[alorenzen]

@lrhn Why don't we have super-bounded types?

[eernstg]

An existential open would help:

void printBestAsset(final List<Asset> assets) {
  assets as List<?T0>;
  // Declares `T0` as a fresh type variable and binds it to the
  // actual type argument of `assets`, such that
  // `assets is List<T0>` is true and no subtype `T` of `T0`
  // will make `assets is List<T>` true. We know `Asset <: T0`.
  assets
    .firstWhere((a) => a.name == 'A', orElse: () => assets.first)
    .printMe();
  // Given that `orElse` has type `T0 Function()` and `assets`
  // has type `List<exactly T0>` (even if we haven't introduced
  // syntax for that, the type checker can still know that this type is
  // invariant), there will be no downcast when the function literal
  // is passed to `firstWhere`, and no downcast in the function
  // literal when it returns `assets.first`.
}

This allows us to call printBestAsset with an assets that may be of type List<SoundAsset> or List<Asset> etc. dynamically (statically, we may or may not know more than List<Asset> at the call site), and it it soundly performs the required operations. The difference is that an existential open operation will allow us to obtain an invariant context (where we know that assets has type List<exactly T0> for some T0 that we can use in the code), and then we can program safely from there.

Compared to Java wildcards, this is just as flexible, but more powerful, because we can abstract away from knowledge which has more structure and later regain it (e.g., if we have a Pair<?, ?> in Java we could never discover that the two unknown types are the same type, but we could use if (p is Pair<?X, X> && p is Pair<Y, ?Y>) .. to recognize that we actually have such a "same-typed" pair, and then we could proceed from there.

[lrhn]

@matanlurey
We can't use

T firstWhere<T extends E>(bool Function(E) test, {T Function() orElse});

because it's not type-safe. If we pick a T type that is an actual sub-type of E, then the first element of the list satisfying test might not be a T.

The constraint <T super E> differs from <T extends E> in that the latter requires T to be a subtype of E, the former requires T to be a super-type of E (or, equivalently, E be a sub-type of T).
With

T firstWhere<T super E>(bool Function(E) test, {T Function() orElse});

we know that E is a sub-type of T, so any element of the list is a valid return value. So is any value returned by orElse, so the method is well typed.

It is also a problem that orElse is optional because that leaves us with no good default for T when it is omitted.

With suitable language extensions, maybe we could type it as:

<T|E> firstWhere<T>(bool Function(E) test, {T Funcition() orElse = const (_) => null});
// pr
<T|E> firstWhere<T = void>(bool Function(E) test, {T Funcition() orElse});

That would allow us to specify the exact type of what we get back, independently of E, and have a default-value for the type parameter in the case where orElse is omitted (that is, if there is nothing restricting the type parameter, pick the default type instead of the bound).

As for why we don't have super-bounds, I'll leave that to the type-system experts, but I have heard rumors about potential undecidability. Maybe it's not a problem (Java survived it), but maybe it is when you have first class generic function types.

I don't think there is anything we can reasonably do to improve the typing of the method with the current type system. If/when we get non-nullable types, we might need to reevaluate it, because it would be nice to be able to write List<int> x = ...; int? firstOrNot = x.firstWhere(test, orElse: () => null); and be able to type it.

[vsmenon]

Filing this under language. Is there a tag for covariance issues?

One simple possibility here is to provide an analyzer flag (similar to no-implicit-casts) that warns on covariant up-casts.

E.g., this:

  final assets = [SoundAsset('A'), SoundAsset('B')];
  printBestAsset(assets);

becomes:

  final assets = [SoundAsset('A'), SoundAsset('B')];
  printBestAsset(assets as List<Asset>);

It's a bit odd as it's an upcast and "safe" (in the sense that the cast itself cannot fail), but it does indicate to the user that something potentially unsafe (a later runtime failure due to covariance) is happening.

[lukehutch]

Related: #54108