Current "covariance by default" paradigm is not respected by the compiler

[luanpotter]

After some digging around old issues, I can see there has been some discussion in the past about providing a more robust type system to Dart by including specific covariant/contravariant type definitions as provided by other languages (java, kotlin, etc).

That being said, it is my understanding that, currently, the language design is to consider everything to be "covariant by default":

As of Dart 2.4 or earlier, every type variable declared for a generic class is considered covariant

(from this great issue from 2019).

Which is not, as discussed, sound (nor safe) -- and I would love to see that addressed. But I am not sure the status of these proposals, as there are many open, old issues from the community about it. And while I would much prefer that to be the answer to this, I believe that even when considering the current rule, there is an issue with the compiler implementation (if I am not misinterpreting these statements).

Assuming the "covariant by default" rule, a List<double> should be a List<num>, for all intents and purposes:

void take(List<num> ns) {}

void main() {
  take(<num>[]); // ok
  take(<double>[]); // ok
}

However, this does not work when the generics are a bit more involved. See an example below: (dartpad):

void take<T extends Comparable<T>>(List<T> list) {}

void main() {
  take(<num>[]); // ok -- T = num
  take(<double>[]); // not ok -- does no compile, it is trying to resolve T=double instead of the also valid T=num
  take(<double>[] as List<num>); // ok, teach the compiler. but warns and wants to "auto-fix"
}

Here, my function generics satisfy List<num>. But for some reason, it does not compile for List<double>. Of course double itself does not satisfy T extends Comparable<T>, but num does. I believe the current "covariance by default" rule is being violated here, as my List<double> should be treated as a List<num> to satisfy the type constraint.

To make it even more weird, see how I can cast the List<double> to List<num> and then it totally works! But then the compiler correctly points out that since dart is "covariant by default" the cast is unnecessary, and the IDE will auto-fix to remove the cast. This removal actually causes the code to break.

The way I am understanding this, this is a violation of the current rule, but as pointed out in many issues, the current rule isn't good to begin with. So my question/proposal is:

1. am I missing something on my analysis? is there current any way to accomplish this?
2. is there any ongoing plan to add something akin to Java's wildcard + T super U syntax, or explicit covariant/contravariant modifiers like kotlin's in, out, inout?

Because if not, I believe this should be treated as a bug as take(<double>[]) should work with the current ruling, as far as I understand it. And that might be a much quicker fix than to get the actual spec sorted out. Also, having the compiler warning/auto-fix generate non-compiling code is odd.

The reason I am asking this is that this not an abstract, far-off, edge case that I machinated; having a function that takes a list whose elements can be compared seems to be like a very common use case (e.g. sorting, finding min, max, etc). And not being able to pass a list of double or int because of how they implement Comaprable<num> limits our design choices.

If there are approved plans to solve this by the root cause though -- and make the type system more sound--, I am happy to wait for that solution instead, as that would allow for even more cool & safe code :)

[Levi-Lesches]

I think the "proper" workaround is

take<num>(<double>[]);  // OK, no lints

You're correct that Dart gets confused when you imply you want num by having T extends Comparable<T>, but then explicitly specify that your list is List<double>. It can't choose between num and double, despite num being the only valid answer (since double is a Comparable<num>, not Comparable<double>).

The difference is where you correct Dart. One way to do it is to cast your list back to a List<num> using as so that Dart isn't confused by the explicitly typed List<double>. But as you pointed out, that's entirely unnecessary. Instead, be explicit about T, and tell Dart that even though you're giving it a List<double>, it shouldn't think that T = double.

I don't know what's up with the unnecessary_cast lint here, but perhaps it's trying to warn you that your workaround can be fixed to something simpler and more direct. There are a few instances (1, 2) of unnecessary_cast technically being wrong but still pointing out a simpler or cleaner solution.

[lrhn]

What @Levi-Lesches says. The problem is not the covariance, it's the inference.

A List<double> instance can be used anywhere a List<num> instance is expected. Not safely, if you use the contravariant features, but it's allowed to go there.

The take(<double>[]) function invocation does not expect a List<num>. Due to inference, it expects a List<double>, just as if you had written take<double>(<double>[]). That's just not a valid type argument to take because double is not a subtype of Comparable<double>. The parameter to take is F-bounded which means that a supertype being a valid type argument doesn't mean that all subtypes of it are also valid type arguments. The double type is not necessarily allowed anywhere the num type is.

[luanpotter]

Thanks for the detailed explanation! I see now the problem is with inference and how to tell the compiler what we want.

Thus proposed solution:

take<num>(<double>[]);  // OK, no lints

Is very clever and works perfectly for the example I provided. This simple syntax is what I was looking for, and I forgot that you could specify the desired generic type on the function call level.

However, I believe upon revising my question, I ended up simplifying my example too much. My actual complete use case was an extension function:

extension ComparableIterable<T extends Comparable<T>> on Iterable<T> {
  void fn() { /* .. */ }
}

void main() {
  (<num>[]).fn(); // ok
  (<double>[]).fn(); // not ok -- does no compile
  (<double>[] as List<num>).fn(); // ok but compiler wants to "auto-fix"
}

And when writing the question I at some point thought that fact was irrelevant and converted to a normal function. My problem is that I don't know how to specify the generic parameter used by the receiver of an extension function.

Is there a similar workaround in this case?

[eernstg]

I'd like to comment a little on the reliance on dynamic type checks in relation to covariance.

@luanpotter wrote:

the language design is to consider everything to be "covariant by default"

This is still true. The declaration-site variance proposal is still active, and I hope it will be fully implemented as soon as possible. I believe it's a matter of priority rather than a matter of disagreement, but we do need to sort out some corner cases about mixed inheritance (like class A<inout X> {} together with class B<X> extends A<X> {} and such).

The language Dart is sound in the sense that it strictly enforces that the heap is well-typed. That is, for every variable v, be it a local variable, parameter, instance variable, top-level variable, etc., if v has the static type T and value o, then the run-time type of o is a subtype of T. So anywhere you look, in the heap or on the stack, every stored reference is type correct, at all times. Any exception to this rule is a bug which is given top priority.

Similarly, an expression with static type T will evaluate to an object whose run-time type is a subtype of T, or it will complete in some other way (e.g., throwing an exception). So in that sense it won't yield a type-incorrect object.

However, some expressions may throw an exception at run time because of a type error, even though the program does not have any compile-time errors or warnings. For example, (<int>[] as List<num>).add(1.5).

So I think it's fair to say that Dart doesn't have a "wrong" treatment of covariance (or any other property of the type system), but it does use a typing discipline which is considerably more permissive than it otherwise could, because it performs some type checks at run time rather than compile-time. Still, I'd love to have support for the traditional and well-known approach to variance which is described in #524. I'm actually deeply surprised that there are so few reports (and so few complaints ;-) about run-time type errors caused by covariance.

---

Anyway, the other topic is F-bounded type variables, and in particular the fact that the type inference algorithm does not handle the situation where an F-bound can be shown to be satisfied by using variance and then verifying the F-bound:

class A<X extends A<X>> {}
class B extends A<B> {}
class C extends B {}

void f<X extends A<X>>(X x) {}

void main() {
  f(C()); // Error: Type inference failed.
}

It seems likely that it would be costly to perform a traversal of the entire superinterface graph in order to find a supertype (starting from C, we'd find B) that satisfies the F-bound.

However, Kotlin type inference does handle this task (which would presumably be very similar to the corresponding type inference task in Dart):

open class A<X: A<X>>() {}
open class B() : A<B>() {}
open class C() : B() {}

fun <X: A<X>>f(x : X) {}

fun main() {
    f(C()); // Accepted, that is, it infers `f<B>(C())`.
}

We'd need to consider F-bounds involving more than one class, of course:

class A1<X extends A1<X, Y>, Y extends A2<X, Y>> {}
class A2<X extends A1<X, Y>, Y extends A2<X, Y>> {}
class B1 extends A1<B1, B2> {}
class B2 extends A2<B1, B2> {}
class C1 extends B1 {}
class C2 extends B2 {}

void f<X extends A1<X, Y>, Y extends A2<X, Y>>(X x, Y y) {}

void main() {
  f<B1, B2>(C1(), C2());
  f(C1(), C2()); // Error: Type inference failed.
}

@leafpetersen, do you think we could detect and "delay" constraints that are F-bounds during type inference, and find a result which is satisfying all non-F-bound constraints first, and then search for a supertype that satisfies the F-bounds, and then check whether the resulting type arguments produce a type correct expression? In the case where we have multiple type parameters that participate in an F-bound, we'd have a tuple of types (T1 .. Tk) that are the outcome of the type inference relative to a given list of type variables (X1 .. Xk) with respect to all non-F-bound constraints, and then we'd search for a new tuple (S1 .. Sk) such that Sj is a superinterface (direct or indirect) of Tj, and such that all the F-bound constraints are satisfied, and finally check the result.

[Levi-Lesches]

@luanpotter:

Is there a similar workaround in this case?

Yes. One trick with extensions is that when it's not being recognized, you can specify it by name, as though it were a wrapper:

ComparableIterable(<double>[]).fn();

Now this is similar to calling a function directly, and again we get the problem that double is not a Comparable<double>. Again, we can fix that by adding a generic to the extension name:

ComparableIterable<num>(<double>[]).fn();