pattern matching type inference issue

[mmcdon20]

Ran into another issue relating to patterns, this time there is a type inference issue when using a getter defined in an extension.

void main() {
  print(split([1, 2, 3]));
}

Iterable<(Iterable<A>, Iterable<A>)> split<A>(Iterable<A> iterable) => switch (iterable) {
  Iterable<A>(isEmpty: true) => [(Iterable<A>.empty(), Iterable<A>.empty())],
  Iterable<A>(first: var x, rest: var xs) => () sync* {
      yield (Iterable<A>.empty(), iterable); 
      for (var (ls, rs) in split(xs)) {
        yield ([x, ...ls], rs);
      }
    }(),
};

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

produces the error

Error: A value of type 'Iterable<(Object, Iterable<dynamic>)>' can't be returned from a function with return type 'Iterable<(Iterable<A>, Iterable<A>)>'.
 - 'Iterable' is from 'dart:core'.
 - 'Object' is from 'dart:core'.
Iterable<(Iterable<A>, Iterable<A>)> split<A>(Iterable<A> iterable) => switch (iterable) {
                                                                       ^

If you change rest: var xs to rest: Iterable<A> xs, the program compiles and runs successfully.

[mmcdon20]

Also, I'm not sure if patterns are intended to work this way or not, but the outer pattern, Iterable<A>(...) doesn't work if you remove the type argument for example Iterable(isEmpty: true) does not work and produces the same sort of error message.

[mmcdon20]

Also this program

void main() {
  print(perms([1, 2, 3]));
}

Iterable<Iterable<A>> perms<A>(Iterable<A> iterable) => switch(iterable) {
  Iterable<A>(isEmpty: true) || Iterable<A>(rest: Iterable<A>(isEmpty: true)) => [iterable],
  Iterable<A>(length: var len, first: var x, rest: Iterable<A> xs) => () sync* {
      for (var i = 0; i < len; i++) {
        for (var perm in perms(xs)) { 
          yield [...perm.take(i), x, ...perm.skip(i)];
        }
      }
    }(),
};

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

Has the following compiler error

Error: A value of type 'Object' can't be returned from a function with return type 'Iterable<Iterable<A>>'.
 - 'Object' is from 'dart:core'.
 - 'Iterable' is from 'dart:core'.
Iterable<Iterable<A>> perms<A>(Iterable<A> iterable) => switch(iterable) {
                                                        ^

But works if you add an explicit type cast

Iterable<Iterable<A>> perms<A>(Iterable<A> iterable) => switch(iterable) {
  Iterable<A>(isEmpty: true) || Iterable<A>(rest: Iterable<A>(isEmpty: true)) => [iterable],
  Iterable<A>(length: var len, first: var x, rest: Iterable<A> xs) => () sync* {
      for (var i = 0; i < len; i++) {
        for (var perm in perms(xs)) { 
          yield [...perm.take(i), x, ...perm.skip(i)];
        }
      }
    }() as Iterable<Iterable<A>>, // type cast here
};

[mraleph]

@chloestefantsova Chloe can you triage? Tentatively marking as a CFE issue, but it might intended semantics.

[chloestefantsova]

It seems like an error in the inference in the CFE.

[eernstg]

I don't see any particular issues with the type inference on these programs: An immediately invoked function literal ((){...}()) does not communicate the context type to the return statements of the function literal, and that's most likely the reason why the function literal returns something which is too general to be an acceptable return expression.

See dart-lang/language#2820 for a discussion about this topic. One way to improve on the inference of function literals which are invoked immediately is to use a very simple generic function iife, declared in the code block below.

The following program is the initial example from this issue, except that it uses iife(() sync* {...}) rather than () sync* {...}(). The two expressions have the same semantics, but the form that uses iife does provide the context type to the function literal and hence also to its yield statements, and this eliminates the compile-time error.

X iife<X>(X Function() f) => f();

void main() {
  print(split([1, 2, 3]));
}

class A {}

Iterable<(Iterable<A>, Iterable<A>)> split<A>(Iterable<A> iterable) => switch (iterable) {
  Iterable<A>(isEmpty: true) => [(Iterable<A>.empty(), Iterable<A>.empty())],
  Iterable<A>(first: var x, rest: var xs) => iife(() sync* {
      yield (Iterable<A>.empty(), iterable); 
      for (var (ls, rs) in split(xs)) {
        yield ([x, ...ls], rs);
      }
    }),
};

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

The implementation of patterns in for elements isn't complete, so unfortunately we can't execute that program (yet, or it might even work on the bleeding edge, otherwise it's coming soon). But the analyzer reports that there are no issues, which shows that type inference is now able to convey the required information.

A later example doesn't use for elements (it uses for statements), and that yields a program which is both free of compile-time errors and runnable:

X iife<X>(X Function() f) => f();

void main() {
  print(perms([1, 2, 3]));
}

class A {}

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

Iterable<Iterable<A>> perms<A>(Iterable<A> iterable) => switch (iterable) {
  Iterable<A>(isEmpty: true) || Iterable<A>(rest: Iterable<A>(isEmpty: true)) =>
      [iterable],
  Iterable<A>(length: var len, first: var x, rest: Iterable<A> xs) =>
      iife(() sync* {
        for (var i = 0; i < len; i++) {
          for (var perm in perms(xs)) { 
            yield [...perm.take(i), x, ...perm.skip(i)];
          }
        }
      }),
};

Again, the only change I made was replacing () sync* {...}() by iife(() sync* {...}).

[mmcdon20]

@eernstg the iife wrapper function seems to improve the type inference, but I'm still having an issue with the split function.

See updated code below.

void main() {
  print(perms([1, 2, 3]));
  print(split([1, 2, 3]));
}

Iterable<(Iterable<A>, Iterable<A>)> split<A>(Iterable<A> iterable) => switch (iterable) {
  Iterable(isEmpty: true) => 
      [(Iterable<A>.empty(), Iterable<A>.empty())],
  Iterable(first: var x, rest: var xs) => 
      iife(() sync* {
        yield (Iterable<A>.empty(), iterable); 
        for (var (ls, rs) in split(xs)) {
          yield ([x, ...ls], rs);
        }
      }),
};

Iterable<Iterable<A>> perms<A>(Iterable<A> iterable) => switch (iterable) {
  Iterable(isEmpty: true) || Iterable(rest: Iterable(isEmpty: true)) =>
      [iterable],
  Iterable(length: var len, first: var x, rest: var xs) =>
      iife(() sync* {
        for (var i = 0; i < len; i++) {
          for (var perm in perms(xs)) { 
            yield [...perm.take(i), x, ...perm.skip(i)];
          }
        }
      }),
};

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

X iife<X>(X Function() f) => f();

Which produces the following error:

Error: A value of type '(List<A>, Iterable<dynamic>)' can't be assigned to a variable of type '(Iterable<A>, Iterable<A>)'.
 - 'List' is from 'dart:core'.
 - 'Iterable' is from 'dart:core'.
          yield ([x, ...ls], rs);
                ^

The issue is only with the split function, and works if you substitute rest: var xs with rest: Iterable<A> xs.

The for patterns do work on the bleeding edge versions, but it isn't related to the issue here. You can use .$1 and .$2 instead and it still has the same error.

One thing to also note is that the patterns no longer seem to require an explicit type argument after switching to using the iife wrapper.

[eernstg]

Apparently, the confusing inference results are caused by a glitch in the typing of pattern declared variables and extension members: #51437.

[mmcdon20]

@eernstg that seems to be it. Should we close this issue in favor of #51437?

[eernstg]

Yes, thanks for raising this issue!