commit 29c5b5da9ac58222cddfdce73c1e93051e3edc2d
author Johnni Winther <johnniwinther@google.com> Tue Mar 14 16:38:43 2023 +0000
committer Commit Queue <dart-scoped@luci-project-accounts.iam.gserviceaccount.com> Tue Mar 14 16:38:43 2023 +0000
tree ecdb2592c7717d1ae6c63fa3710f0d861e54f764
parent 5b3f387f4daf17e8edda36270fb8d91b33865cad

[_fe_analyzer_shared] Improve support for list patterns

This adds support for exhaustiveness checking of list types by
contextually dividing the list type into relevant cases for checking.

For instance, the exhaustiveness can be achieved by a single pattern

    case [...]:

or by two disjoint patterns:

    case []:
    case [_, ...]:

When checking for exhaustiveness, witness candidates are created and tested against the available cases. This means that the chosen candidates must be matched by at least one case or the candidate is considered a witness of non-exhaustiveness.

Looking at the first example, we could choose `[...]`, the list of
arbitrary size, as a candidate. This works for the first example, since the case `[...]` matches the list of arbitrary size. But if we tried to use this on the second example it would fail, since neither `[]` nor `[_, ...]` fully matches the list of arbitrary size.

A solution could be to choose candidates `[]` and `[_, ...]`, the empty list and the list of 1 or more elements. This would work for the first example, since `[...]` matches both the empty list and the list of 1 or more elements. It also works for the second example, since `[]` matches the empty list and `[_, ...]` matches the list of 1 or more elements.

But now comes a third way of exhaustively matching a list:

    case []:
    case [_]:
    case [_, _, ...]:

and our candidates no longer work, since while `[]` does match the empty
list, neither `[_]` nor `[_, _, ...]` matches the list of 1 or more
elements.

This shows us that there can be no fixed set of witness candidates that we can use to match a list type.

What we do instead, is to create the set of witness candidates based on the cases that should match it. We find the maximal number, n, of fixed, i.e. non-rest, elements in the cases, and then create the lists of sizes 0 to n-1 and the list of n or more elements as the witness candidates.

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