dart-lang / dart-lang/language

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

Open
#3,282 4 comments 3 reactions 0 assignees View on GitHub
feature least-upper-bound technical-debt
Dominant language
TeX
Stars
2.9k
Forks
239
Avg merge
2d 18h
Merged PRs (30d)
14

Description

The [last case](https://github.com/dart-lang/language/blob/main/resources/type-system/upper-lower-bounds.md#:~:text=UP(C0%3CT0%2C%20...%2C%20Tn%3E%2C%20C1%3CS0%2C%20...%2C%20Sk%3E)%20%3D) 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:

```dart
bool b = true;

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

If we compute the standard upper bound of `Iterable` and `Iterable` then we will get the desired outcome: `Iterable`, and similarly for `List` and `List`. 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` and `Iterable`).

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 _SI_ be the set of superinterfaces of _I_, let
_SJ_ be the set of superinterfaces of _J_, and let _S = ({I} ∪ SI) ∩ ({J} ∪ SJ )_.
Furthermore, we define _Sn = {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 _Sq_ has cardinality one, which
must exist because _S0_ is {`Object`}. The least upper bound of _I_ and _J_ is the
sole element of _Sq_ .

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

> Given two interfaces _I_ and _J_, let _SI_ be the set of superinterfaces of _I_, let
_SJ_ be the set of superinterfaces of _J_, and let
_S = classesOf(({I} ∪ SI) ∩ ({J} ∪ SJ ))_, where _classesOf_ is a function that maps
a non-generic class used as a type to itself, and a parameterized type `G` to `G`
(_classesOf_ works on a single type, and is implicitly lifted to work on sets of types).
Furthermore, we define _Sn = {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 _Sq_ has cardinality one, which
must exist because _S0_ is {`Any`}. Let `C` be the sole element of _Sq_.
The least upper bound of _I_ and _J_ is then _UP(TI, TJ)_,
where _TI_ is the type of the form `C<...>` such that _I_ implements _TI_,
where _TJ_ is the type of the form `C<...>` such that _J_ implements _TJ_.

There are two obvious issues to consider:
- Is this a breaking change?
- Will _UP_ be guaranteed to terminate on all arguments? (note [this remark](https://github.com/dart-lang/language/blob/main/resources/type-system/upper-lower-bounds.md#type-variable-bounds))

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.

Contributor guide

Open the contributing guide

Research direction

Start with resources/type-system/upper-lower-bounds.md and read the current last UP case alongside the proposed classesOf-based rule. Check the linked type-system examples and the questions about breaking changes and termination. Done means the specification has an agreed, precise replacement for the last case, including how recursive invocations terminate.

Written by the indexing model from the issue text.

Assessment

Tech stack
dart
Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.