commit 4cd0ca7693ca219183357738288e525a6941cd6c
author Johnni Winther <johnniwinther@google.com> Thu Feb 23 00:16:50 2023 +0000
committer Commit Queue <dart-scoped@luci-project-accounts.iam.gserviceaccount.com> Thu Feb 23 00:16:50 2023 +0000
tree a32b40ad086619155c47a4e076cf259d0a312e20
parent 552fbd0e9720250ce946580179a157a9fd265580

[_fe_analyzer_shared] Support generic types in exhaustiveness

This adds support for generic types in exhaustiveness checking.

There are two main obstacles:

 1) Types that are not Dart subtypes might be related in the context
    of exhaustiveness. For instance

       sealed class A<X> {}
       class B extends A<num> {}
       method<T>(A<T> a) {
         switch (a) {
           case B(): ...
         }
       }

    Here B is not a Dart subtype of A<T> but must still be a subtype
    in the context of exhaustiveness since T could be num at runtime.

 2) It is non-trivial to compute the subtypes of a generic sealed class
    that is both sound and precise enough to be useful. For instance

      sealed class A<X> {}
      class B extends A<num> {}
      class C<X> extends A<X> {}
      class D<X extends num> extends A<X> {}
      class E<X extends E<X>> extends A<X> {}

    Computing the subtypes of A<F> for some type F, we would like to
    exclude B (assuming F is not a supertype of num) because it
    cannot be inhabit A<F>, and include C<F> so that we recognize
    that C<F> exactly covers all C instances of A<F>. We would also
    like to include D<F> but if we don't include the added `extends
    num` bound, we might conclude that D<num> is _not_ sufficient to
    cover D<F>. And what to do about E, can we even come up with a
    type that represents the valid values?

The solution is threefold:

1) We add an 'overapproximate' function of types, which
replaces all type variables with their default types. This will compute
A<dynamic> for A<T>, A<int> for A<int>, A<List<dynamic>> for A<List<T>>,
and E<dynamic> for E<T extends E<T>>. This is similar to instantiate-
to-bounds, but is recursive.

We use this to test whether a type without type variables is a potential
subtype. For instance testing B <: overapproximate(A<F>) = A<F> shows
that B _cannot_ be a subtype of A<F>, and testing
B <: overapproximate(A<T>) = A<dynamic> shows that B _can_ be a subtype
of A<T>.

2) For finding subtypes of a sealed type, we recognize the case
when a type is a trivial subtype in which all type variables are passed
directly to the superclass, for instance like C<T> in the example. For
other cases we overapproximate the this type of the subclass.

3) To ensure that the [StaticType] can be subtype in the normal Dart
sense but also handle the overapproximation when computing sealed
subtypes, a new [WrappedStaticType] is added. This bridges the subtype
relation such that for instance B, when created as a sealed subtype
of A<T>, is both a subtype of A<num> (as it normally is) and of A<T>,
which it is by construction.

Change-Id: I9970c46009938ef15625e1193faf916b7544ce0b
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/284681
Reviewed-by: Konstantin Shcheglov <scheglov@google.com>
Reviewed-by: Paul Berry <paulberry@google.com>
Commit-Queue: Johnni Winther <johnniwinther@google.com>