Problem: contravariant return types on instance members interact badly with covariant generics

[leafpetersen]

Recovering soundness in the presence of covariant generics requires runtime checks to be inserted in certain positions. In the case of a member the type of which contains a contravariant occurrence of a covariant type variable, a caller side check is currently inserted. This is a very brittle check and causes confusing errors. See for example this discussion among others for concrete examples and further discussion of the check.

It would be good if we could improve the programmer experience around this. There are a number of possible paths that have been proposed.

Sound variance

Using sound variance solves the issue, at some expense either in terms of cognitive load (if sound co and contravariance are used) or subtype polymorphism (if invariance is used). There are proposals on the table for adding one or more of declaration site variance, use site invariance or use site variance.

Weaken contravariant return types on getters

There is a proposal from @eernstg to weaken the return type of members with contravariant return types to a sound approximation of the actual type. This avoids the need for a read side check, at the expense of receiving an unexpectedly vague type at the call site.

Eliminate the check at sound use sites

There are a number of patterns where currently the check is inserted, and may fail, even though the result of the member access is immediately promoted to a sound super type (e.g. dynamic), or otherwise used in a safe way (e.g. simply compared to null). It would be possible to specify a set of conditions in which the check should not be performed that would make it less likely to encounter this.

Wrap return values

An approach used in some gradual typing systems is to wrap return values in checking code. Either on the caller or on the callee side, we would wrap a returned value of type int Function(int) with guards on the parameters as required to ensure that soundness is preserved. This has a significant runtime expense and changes identity semantics, and so is unlikely to be feasible.

This issue is intended to track the user issue, and centralize the list of proposals for addressing this. Additional proposed solutions should be linked into this thread.

[leafpetersen]

cc @Hixie @vsmenon @eernstg @lrhn @munificent @natebosch @jakemac53 @stereotype441

[natebosch]

My gut reaction is that I would prefer to avoid weakening the runtime checking based on surrounding code unless the patterns are very narrow. I like that I can fully trust the static types, even the inferred ones.

[Hixie]

I don't have much to contribute here on the theoretical side, but I very much appreciate that we are investigating this.
FWIW, I'm skeptical that we can do the "sound variance" option without making it overly confusing. I haven't seen this done well in other languages.

[munificent]

Using sound variance solves the issue, at some expense either in terms of cognitive load (if sound co and contravariance are used) or subtype polymorphism (if invariance is used).

I like this approach in part because there's no performance or safety cost. In cases where a caller-side check has to be inserted, I think it's very unlikely that users today realize they are paying for it and that it can fail. So in some sense, the cognitive load is already there, they just don't know that they don't know it.

There is a proposal from @eernstg to weaken the return type of members with contravariant return types to a sound approximation of the actual type.

This reminds me of the loosening we do for tear-offs with covariant parameter types, so doesn't seem unreasonable to me. But it's kind of weird and magical.

There are a number of patterns where currently the check is inserted, and may fail, even though the result of the member access is immediately promoted to a sound super type (e.g. dynamic), or otherwise used in a safe way (e.g. simply compared to null).

This sounds like we'd end up playing an endless game of use case whack-a-mole.

FWIW, I'm skeptical that we can do the "sound variance" option without making it overly confusing. I haven't seen this done well in other languages.

I agree it's a real challenge. The cognitive load of generics is already quite high and most users only have an informal understanding of them. One aspect I very much like about declaration-site variance is that it shifts most of the cognitive burden off consumers of generic classes and onto their authors, who are more likely to have the sophistication to know how to use them. (This is in contrast to Java generics where they bleed out of the API into the consumer's code in weird ways.)

An author can provide a generic class to users that Just Works™ in that it is sound and reports compile errors if users try to use it in invalid ways. In other words, the class author can define the rails and the user just has to stay on them. Users may need some expertise to understand those errors, but my experience is that they are pretty rare. Most generic classes are used in completely invariant ways. C# had zero support for anything but invariance for several years and it was surprisingly pain-free.

[leafpetersen]

Most generic classes are used in completely invariant ways. C# had zero support for anything but invariance for several years and it was surprisingly pain-free.

This is largely my experience. Generally in my experience invariance is not confusing to people at all. If the thing says it takes a Foo<Widget>, then you better pass it a Foo<Widget>. And in general, I find programming with generic methods + invariance to be much simpler and more robust. Subtype polymorphism is "lossy": once you've subsumed a Foo<Widget> to a Foo<Object> the only way to get back out is via runtime checking, whereas when you use parametric polymorphism you just write your code to take a Foo<T> and you have a name for the actual type that you have a Foo of! So I'm somewhat skeptical of the idea that invariance carries a high cognitive load.

Sound covariance does have something of a cognitive load for people writing/implementing classes. That is, there is a load on the producer, because they have to write their API signatures to be valid covariant signatures. However, the load on end users is, conversely fairly low. It's no worse (and in fact better) than the experience of end users with unsound covariance.

Unsound covariance relieves some of the cognitive load for class implementers because they can just write their classes any way they want. This comes at the expense of pushing more cognitive load onto end users though. Whereas with sound covariance everything just works for the end user, with unsound covariance they can hit unexpected runtime errors because they are "using it wrong". This is unavoidable if we want soundness. A List<int> is a subtype of a List<num>, so either we dynamically stop you from putting double values into that List<num> or we give up on soundness. But that check to stop you from putting a double in there is a load on the end user of the type.

Contravariance is definitely hard for people to reason about. People manifestly find it non-intuitive even on the consumer side, and it's harder for class implementers to reason about as well. Fortunately, it's very rare that you need it. So why not leave it out? Because if you want sound covariance, then in rare cases you need its dual, contravariance, or you're really SOL. This is confusing, but it is fortunately rare (except for function types, which we already have in abundance, so maybe it's not too, too bad?).

[Hixie]

One aspect I very much like about declaration-site variance is that it shifts most of the cognitive burden off consumers of generic classes and onto their authors, who are more likely to have the sophistication to know how to use them.

In my experience that kind of reasoning doesn't actually pan out. A programmer needs to know all the tools in the toolbox because their colleagues will use them, whether they understand them or not, and you need to understand them to debug the resulting code.

That said, I'm happy to reserve judgement until we have a concrete proposal and can do real usability tests with it.

[eernstg]

A small clarification about this:

There is a proposal from @eernstg to weaken the return type of members
with contravariant return types to a sound approximation of the actual type.

@munificent wrote:

This reminds me of the loosening we do for tear-offs with covariant parameter
types, so doesn't seem unreasonable to me. But it's kind of weird and magical.

It's actually simpler than that. The tear-offs involve changing the run-time type of a function object and adding dynamic checks (that's magic), but this proposal doesn't involve changes to the run-time type of anything. It simply adjusts the static type of an expression from a type that may or may not be satisfied by the actual value of that expression to a supertype thereof that correctly describes all the possible values. With the new static type there is no need for a caller-side check, because we haven't promised more than we can deliver.

The downside is that the expression now has a more general type, so there may be a need for an explicit downcast in order to allow that expression to occur at that location. So this is clearly a breaking change, though for a situation that may be rare in practice.

However, if the caller-side check was e as T and the context only requires e as S where S is a supertype of T then it's arguably better to have the explicit e as S than the implicit e as T: (1) It's explicit; (2) we could use var x = e; if (x is S) ... if we want to deal with failures; (3) even with the cast e as S that may fail, more program executions will avoid the exception because e as S is a weaker requirement than e as T.

[munificent]

A programmer needs to know all the tools in the toolbox because their colleagues will use them, whether they understand them or not, and you need to understand them to debug the resulting code.

Yeah, I get where you're coming from. C++ is particularly bad for this where it seems that everyone has their own idiosyncratic set of pet features so it's hard to avoid running into them once you work in a group. I don't think generic class declarations are so randomly scattered.

Here's a histogram of the number of type parameters in all of the class declarations of the 1,000 most recently published pub packages (as of earlier this year):

--- Classes (74072 total) ---
  70935 ( 95.765%): 0   ************************************************************************************************
   2299 (  3.104%): 1   ****
    649 (  0.876%): 2   *
     80 (  0.108%): 3   *
     37 (  0.050%): 4   *
     30 (  0.041%): 5   *
     15 (  0.020%): 6   *
      7 (  0.009%): 7   *
      3 (  0.004%): 10  *
      3 (  0.004%): 8   *
      3 (  0.004%): 9   *
      2 (  0.003%): 11  *
      1 (  0.001%): 12  *
      1 (  0.001%): 13  *
      1 (  0.001%): 14  *
      1 (  0.001%): 15  *
      1 (  0.001%): 16  *
      1 (  0.001%): 17  *
      1 (  0.001%): 18  *
      1 (  0.001%): 19  *
      1 (  0.001%): 20  *

So >95% of classes are not generic. This is published pub packages which are intended to be reusable library code and I think thus more likely to use generics. I would expect application code would have even fewer generic classes. That leads me to believe that a typical Dart programmer can probably get pretty far without having to understand maintaining a generic class.

It still adds complexity to the language, definitely, so I'd like to see what we can learn from usability studies too. This is a hard problem. My experience is that as your type system gets more complex, it takes larger and larger complexity jumps to provide incremental expressiveness improvements. At some point, it's not worth it, though that point varies per user.

[escamoteur]

I'm not sure if this is the same problem but I got a very similar error today. May problem is that I have to store A<T> with different types in one list which makes the list type List<A<dynamic>> .

class A<T>{
  A(this.val,this.dispose);
  T val;
  FutureOr Function(T) dispose;
}

But when I try to call dispose on the List's elements

  for(final a in allA){
    a.dispose(a.val);
  }

I get a type error because a is treated as if it's of type A<dynamic> despite the fact that the runtime type of that list element should be a concrete type.

Full example in dartpad here:
https://dartpad.dev/5c48d5e267b48b7103d65639f931e337

[lrhn]

@escamoteur
It's a similar problem. Your class is covariant in T, because that's what classes are in current Dart, but your function-typed instance field is contravariant in T. That makes it unsound to use except at the precise type of T.
By casting the A<X> to A<dynamic>, you get into a situation where a.dispose has static type FutureOr Function(dynamic) and run-time type FutureOr Function(X). That's unsound - the run-time type is not a subtype of the static type.

There is no good solution, any read of a.dispose should trigger a type error immediately because the expression has a run-time type which doesn't satisfy its static type. Indeed, if you only write a.dispose;, without the (a.val) argument, it's still an error.

In this case, I'd add a method to A to do the call:

class A<T> {
  A(this.val, this.dispose);
  T val;
  FutureOr Function(T) dispose;

  FutureOr invoke() => dispose(val);
}

Then you can call a.invoke() instead of a.dispose(a.val), and since it happens inside the object which knows the value of T, it's safe and sound.
That obviously only works when you have access to modify the class.

Allowing you to write a.dispose(a.val) requires existential types. There exists a type, we do not know which (but it's a subtype of dynamic), so that a.dispose can accept an a.val value. Dart doesn't have existential types, you have to actually know the type to do the invocation, and we have no way to access the type of A<X> when it's only known to be A<dynamic>.