Object patterns with extension methods in switch showing as inexhaustive in analyzer but program compiles and runs successfully

[mmcdon20]

Dart SDK version: 3.0.0-366.0.dev (dev) (Fri Mar 24 06:44:03 2023 -0700) on "windows_x64"

Consider this program.

example.dart

void main() {
  print(sum([1, 2, 3, 4, 5]));
}

int sum(Iterable<int> list) => switch (list) {
      Iterable(isEmpty: true) => 0,
      Iterable(first: var x, rest: var xs) => x + sum(xs),
    };

extension<A> on Iterable<A> {
  Iterable<A> get rest => skip(1);
}

analysis_options.yaml

analyzer:
  enable-experiment:
    - patterns

The above program compiles and runs successfully using

dart --enable-experiment=patterns bin/example.dart

However the analyzer is reporting the following error.

The type 'Iterable<int>' is not exhaustively matched by the switch cases.
Try adding a default case or cases that match 'Iterable<int>(first: int(), isEmpty: false, rest: Object())'.dart(non_exhaustive_switch)

The error message goes away if you declare rest: Object? xs, or rest: dynamic xs, instead of rest: var xs, so maybe type inference has something to do with it? Possibly related to #51437.

[Mike278]

This specific pattern is actually built right in to pattern matching - it's even called a rest element!

So you could write your example like:

void main() {
  print(sum([1, 2, 3, 4, 5]));
}

int sum(List<int> list) => switch (list) {
      [] => 0,
      [var x, ...var xs] => x + sum(xs),
    };

(which, can I just say, looks so clean. Hats off to the Dart team 🎉)

I tried to come up with a good way to explain why your original example isn't exhaustive, but the mental model that works for me is that exhaustiveness checking is based on a type's "cardinality" - how many possible values can inhabit a type. A set of patterns is exhaustive if it covers all the possible values. For most primitive types - numbers, strings, lists, maps - the cardinality is effectively infinite. So to exhaustively check some property of one of these types, you want to try expressing your patterns in terms of types with lower cardinality (like bool or subclasses of a sealed class) or in terms of built-in pattern matching features (like rest elements or null checking).

For example:

// not exhaustive, can't reason about the relationship between `isEmpty` and `isNotEmpty`
final x = switch([1,2,3]) {
  List(isEmpty: true) => 'a',
  List(isNotEmpty: true) => 'b',
};
// exhaustive, covered the only 2 possible values for a `bool`
final x = switch([1,2,3]) {
  List(isEmpty: true) => 'a',
  List(isEmpty: false) => 'b',
};

Some good related reading: dart-lang/language#2693

[mmcdon20]

I am aware that list patterns support ..., but that is irrelevant to this issue.

The code I posted is considered exhaustive by the compiler, but not by the analyzer so clearly there is a discrepancy here.

I believe that the compiler is correct and that there should be no analyzer warning.

Iterable(first: var x, rest: var xs) should exhaustively match any value of type Iterable and list is an Iterable<int>.

It is exhaustive because an Iterable has getters for first and rest and declaring x and xs as var should match any possible value for x and xs.

Additionally, as I mentioned in the original post, if you use the pattern Iterable(first: var x, rest: dynamic xs) instead then there is no analyzer warning. It appears to be a combination of extension types, object patterns, and type inference that is causing this behavior.

[Mike278]

Right, I missed the lack of constraints on x and xs.

[lrhn]

The switch should be exhaustive, as you say the, Iterable(first: var x, rest: var xs) is irrefutable for an Iterable.

(Also, be aware that code written like this is very likely to have atrocious performance.
The platform iterables actually have an optimization, so iterable.skip(1).skip(1).skip(1).skip(1) won't be five nested iterables, but that's not something anyone promises, and not something you can assume every iterable does.
If they don't, a recursive

sum(Iterable<int> it) => switch (it) { 
  Iterable(isEmpty: true) => 0, 
  Iterable(first: var x, rest: xs) => x + sum(xs)
};`

on an iterable of length n would build up a stack of n skip(1) wrappers around the original iterable,
then recursively traverse those, each step taking longer than the previous, for a quadratic total execution time.
The idiomatic way to process a list or iterable in Dart is iteration. Recursion which creates new objects to recurse on is rarely going to be efficient.)

[bwilkerson]

@johnniwinther I'm guessing that the exhaustiveness checker is working correctly and that the bug is in the way the analyzer interacts with the checker. Can you confirm that, and can you point me to where the interaction occurs?

[johnniwinther]

I think this is a problem in both the CFE and the analyzer. Currently the exhaustiveness only recognizes the types of instance properties and just has a fallback for unknown properties (wrongfully) assuming that these are error cases. For these it uses the top type Object? for the value space and therefore thinks that xs with its inferred type Iterable<int> Function() doesn't cover the value Object().

[johnniwinther]

@bwilkerson do you know if available extensions methods are easily available in the analyzer (from the constant_verifier) ? - the are not easily available in the CFE.

[bwilkerson]

Sorry I missed your comment earlier.

I believe that we can fairly easily look through the import scope for visible extensions that match the type.

@scheglov In case I'm wrong.

[johnniwinther]

@scheglov Could you give me a pointer of how to do this in the analyzer? Then I'll implement this in the shared exhaustiveness code.

[bwilkerson]

See pkg/analyzer/lib/src/dart/resolver/extension_member_resolver.dart.

[johnniwinther]

If a pattern field in an object pattern resolves to an extension method, is that information available on the pattern field object (the DartPattern for the pattern field)?

[scheglov]

Yes, I suspect there is a bug in the integration of the exhaustiveness checking with the analyzer.
Looking into _getInterfaceFieldTypes it seems that we iterate over all available properties in a type.
Not sure why we do this.
Don't we have to split the space only when we check a specific property?
I have no idea what I'm talking about...

But if we want to know every property available, it seems to be similar to code completion.

Yes, the resolved property is available in PatternField.element.

[johnniwinther]

We only need to check the individual properties mentioned but we have to get their declared static types to do the matching. This what goes wrong here; the rest property is unknown to the type Iterable<int> so we hit the fallback to Object? (put there to avoid crashes in erroneous code), and given the (inferred) type of xs, Iterable<int> doesn't cover Object? we see the case as non-exhaustive.

I hope I'll be able to derive the needed type from the PatternField.element but otherwise I'll have to do extension member lookup.

[johnniwinther]

Btw this isn't a bug in the integration with the analyzer but a missing piece of the exhaustiveness checking - it's also missing in the CFE. I forgot about the existence of extension method when adding support for member access.

[scheglov]

Yeah, I think I mentioned once in the review that we need to support extension methods, but forgot about it later.
I think PatternField.element will help, at least for the analyzer, don't know if something like this is a good fit for CFE.