Adjust the last case in UP to use classes rather than types

[eernstg]

The last case in the definition of the UP type function which is used to compute the standard upper bound of two types is the Dart 1 algorithm which was used for the same purpose.

That algorithm fails to detect that a parameterized type T<...> is a shared supertype in the case where two parameterized types based on distinct generic types both implement T, but with different type arguments. For example:

bool b = true;

void main() {
  List<num> xs = [1, 1.5];
  Iterable<int> ys = [1, 2];
  var x = b ? xs : ys; // Bummer! `x` has static type `Object`, not `Iterable<num>`.
}

If we compute the standard upper bound of Iterable<int> and Iterable<num> then we will get the desired outcome: Iterable<num>, and similarly for List<int> and List<num>. The disappointing result Object only occurs when the generic types are different (like List and Iterable), and the type arguments are different (like num and int), and the types don't have a subtype relationship (unlike List<int> and Iterable<num>).

In other words, we only get the overly general result when we're unlucky "in both dimensions", but it is very disappointing when we do get a type like Object.

Here is the Dart 1 algorithm that we're using today:

Given two interfaces I and J, let S_I be the set of superinterfaces of I, let S_J be the set of superinterfaces of J, and let S = ({I} ∪ S_I) ∩ ({J} ∪ S_J ). Furthermore, we define S_n = {T |T ∈ S ∧ depth(T) = n} for any finite n, where depth(T) is the number of steps in the longest inheritance path from T to Object. Let q be the largest number such that S_q has cardinality one, which must exist because S0 is {Object}. The least upper bound of I and J is the sole element of S_q .

Here is a proposal for a revised version of the algorithm:

Given two interfaces I and J, let S_I be the set of superinterfaces of I, let S_J be the set of superinterfaces of J, and let S = classesOf(({I} ∪ S_I) ∩ ({J} ∪ S_J )), where classesOf is a function that maps a non-generic class used as a type to itself, and a parameterized type G<T1 .. Tk> to G (classesOf works on a single type, and is implicitly lifted to work on sets of types). Furthermore, we define S_n = {T |T ∈ S ∧ depth(T) = n} for any finite n, where depth(T) is the number of steps in the longest inheritance path from T to Object. Let q be the largest number such that S_q has cardinality one, which must exist because S0 is {Any}. Let C be the sole element of S_q. The least upper bound of I and J is then UP(T_I, T_J), where T_I is the type of the form C<...> such that I implements T_I, where T_J is the type of the form C<...> such that J implements T_J.

There are two obvious issues to consider:

• Is this a breaking change?
• Will UP be guaranteed to terminate on all arguments? (note this remark)

It is highly likely that this change is somewhat breaking, because any change to the computation of the type of an expression can break some code. However, it seems likely that the change will give many expressions a more precise type, and hence it will typically improve on the software engineering properties of the affected expressions, even in some cases where it causes existing code to have errors (that is: we'll fix those errors, and the resulting code is better than the old code).

The termination question is non-trivial. However, we can easily ensure termination by using the new rule only during the first invocation of the last rule of UP, and revert to the current rule for recursive invocations.

[eernstg]

@dart-lang/language-team, WDYT?

[lrhn]

Probably won't terminate for

abstract class C implements List<C> {}
abstract class D implements List<D> {}

and doing Up(C, D).

Not recursing with the same algorithm means that List<Up(C, D)> it's not necessarily the same as Up(List<C>, List<D>)>. How confusing that is is an open question.

I don't think caching to recognize the same pair of types showing up again it's enough, we can probably do an expansive supertype that doesn't have the exact same type again, ever.

[eernstg]

That's a very effective example:

UP(C, D) == // Last rule, new version.
UP(List<C>, List<D>) == // Covariance.
List<UP(C, D)> == // Last rule, new version.
List<UP(List<C>, List<D>)> == ... // Infinite loop.

But if we use the new version of the last rule at most k times for some k (I mentioned k == 1) then we'll stop the recursion and get List<List<....List<Object>....>> (with k+1 occurrences of List, that is, List<List<Object>> with k == 1).

That's clearly better than the plain Object that we get today.

[lukehutch]

Another test case for the proposed change:

https://github.com/dart-lang/sdk/issues/55582