CFE inference issue on generic method type param? #32291

vsmenon · 2018-02-23T14:19:30Z

The following gives no static error with the analyzer and runs without runtime error on DDC:

void main() {
  var l = [["hi", "world"]];
  var i1 = l.map((ll) => ll ?? []);
  var i2 = i1.map((List<String> l) => l.length);
  print(i2);
}

With the CFE, I get the following static error:

org-dartlang-app:///infer.dart:5:19: Error: A value of type '(dart.core::List<dart.core::String>) → dart.core::int' can't be assigned to a variable of type '(dart.core::List<dynamic>) → dynamic'.
Try changing the type of the left hand side, or casting the right hand side to '(dart.core::List<dynamic>) → dynamic'.
  var i2 = i1.map((List<String> l) => l.length);

I believe the analyzer is computing the static type of i1 as an Iterable<List<String>> and the CFE as Iterable<List<dynamic>>.

@leafpetersen @lrhn - can you please double check that the analyzer behavior is as expected? I'm not entirely sure given the ?? operator.

This appears to come up in an internal Flutter app. We can probably workaround this.

The text was updated successfully, but these errors were encountered:

leafpetersen · 2018-02-23T18:11:32Z

The analyzer is correct, because of the asymmetry in our treatment of ??. From the informal spec:

- The expression `e0 ?? e1` is inferred as `m0 ?? m1` of type `T` in
  context `K`:
  - If `e0` is inferred as `m0` of type `T0` in context `K`
  - And `e1` is inferred as `m1` of type `T1` in context `J`
  - Where `J` is `T0` if `K` is `_` and otherwise `K`
  - Where `T` is the greatest closure of `K` with respect to `?` if `K` is not
    `_` and otherwise `UP(T0, T1)`

My guess is that the CFE is using UP(T0, T1) when there is a downwards context of _ but not when there is no downwards context at all (since it seems to do the right thing if I pull the lambda out of the call to .map.

leafpetersen · 2018-02-23T18:11:45Z

cc @stereotype441

stereotype441 · 2018-02-26T12:38:44Z

@leafpetersen I dug into the CFE behavior and it's not exactly what you guessed. Two things are going on:

First of all, the context passed down when inferring ll ?? [] is not _. It's ?. This comes from the fact that l.map has type Iterable<T> Function<T>(T Function(List<String>)), therefore with ? substituted for T, the closure (ll) => ll ?? [] is being inferred in context ? Function(List<String>), so ll ?? [] is inferred in context ?.

Secondly, the CFE contains code to try to mimic the analyzer's (incorrect) handling of ??. However, it turns out that it doesn't mimic the analyzer perfectly. With that code enabled, the rules for ?? are effectively:

- The expression `e0 ?? e1` is inferred as `m0 ?? m1` of type `T` in
  context K:
  - If `e0` is inferred as `m0` of type `T0` in context `K`
  - And `e1` is inferred as `m1` of type `T1` in context `J`
  - Where `J` is `T0` if `K` is `_` and otherwise `K`
  - Where `T` is `UP(T0, T1)`.

Taking both of these into account explains the error message from the CFE, because it infers [] in context ?, getting <dynamic>[] (of type List<dynamic>). Then it computes the type of ll ?? [] as UP(List<String>, List<dynamic>), which is List<dynamic>. So i1 gets an inferred type of Iterable<List<dynamic>>, which explains why its map function cannot be called with a closure taking parameter type List<String>.

If I disable the code that mimics the analyzer's the analyzer's handling of ??, then the type computed for ll ?? [] is dynamic (the greatest closure of ? with respect to ?). So i1 gets an inferred type of Iterable<dynamic>. This also leads to an error, since it means that the map call on the next line expects to be passed a closure taking parameter type dynamic, and we pass it a closure taking List<String>.

AFAICT, the analyzer's behavior is to consider any context satisfying isDynamic == true to be equivalent to _. The types ? and dynamic both return true for isDynamic. So in effect the analyzer's rule is actually:

- The expression `e0 ?? e1` is inferred as `m0 ?? m1` of type `T` in
  context K:
  - If `e0` is inferred as `m0` of type `T0` in context `K`
  - And `e1` is inferred as `m1` of type `T1` in context `J`
  - Where `J` is `T0` if `K` is `_`, `?`, or `dynamic`; and otherwise `K`
  - Where `T` is `UP(T0, T1)`.

Under these rules, ll ?? [] gets inferred as ll ?? <String>[] of type List<String>, which is why the code works with the analyzer.

As a temporary workaround, I'll see if I can get the front end to mimic the analyzer's behavior even more precisely. But for a long term solution, I think I need clarification from @leafpetersen, @lrhn, or @eernstg about what behavior we really want here.

stereotype441 · 2018-02-26T13:41:37Z

I've uploaded a temporary workaround that causes the front end to treat ? as equivalent to _ when inferring e0 ?? e1 only: https://dart-review.googlesource.com/c/sdk/+/43760. Not sending it out for review yet because (a) it's a hack, and (b) I want to hear @leafpetersen's opinion about how to proceed.

Even though I'm waiting to hear from @leafpetersen, after some discussion with @lrhn and @eernstg, I am becoming more inclined to suspect that the correct solution will be to change the front end type inference behavior so that it treats a context of ? as equivalent to _ in all circumstances. I'll begin putting together a speculative CL to do that now.

stereotype441 · 2018-02-26T15:09:44Z

And here's the speculative CL to treat ? and _ equivalently in all contexts: https://dart-review.googlesource.com/c/sdk/+/43761

I'll wait for further discussion on this bug before sending it out for review.

leafpetersen · 2018-02-27T06:28:50Z

cc @jmesserly

? and _ should be treated equivalently. In all the cases where the downwards context is ? or _, we should use the upwards inferred type of the subterm as the inferred type.

The invariant is that if we infer e0 in context K yielding a term m0 of type T, then T is a subtype of the greatest closure of K. So when K is ?, the greatest closure is Object, and any type is a subtype of it, so we can safely use the more precise type.

This points out a second area where I think the spec draft is just wrong (but the analyzer, and it looks like kernel as well both do the right thing). We should use the more precise upwards type for subsequent inference. For example, the draft spec says:

- The expression `e0 ?? e1` is inferred as `m0 ?? m1` of type `T` in
  context `K`:
  - If `e0` is inferred as `m0` of type `T0` in context `K`
  - And `e1` is inferred as `m1` of type `T1` in context `J`
  - Where `J` is `T0` if `K` is `_` and otherwise `K`
  - Where `T` is the greatest closure of `K` with respect to `?` if `K` is not
    `_` and otherwise `UP(T0, T1)`

which implies that even if T0 is more precise than (the greatest closure of) K, we still use (the greatest closure of) K as the type of m0 && m1. But we should only do so if UP(T0, T1) is not a subtype of the greatest closure of K.

- The expression `e0 ?? e1` is inferred as `m0 ?? m1` of type `T` in
  context K:
  - If `e0` is inferred as `m0` of type `T0` in context `K`
  - And `e1` is inferred as `m1` of type `T1` in context `J`
  - Where `J` is `T0` if `K` is `_` or `?`; and otherwise `K`
  - Where `T` is `UP(T0, T1)` if `UP(T0, T1)` is a subtype of the greatest closure of `K`, and otherwise is the greatest closure of `K`.

Both implementations seem to do the right thing here:

List<S> baz<S, T>(Map<S, T> x) {
  print("S = $S, T = $T");
}
void main() {
  List<dynamic> a0 = baz({3: "hello"});
  List<int> a1 = baz({3: "hello"});
  List<num> a2 = baz({3: "hello"});
  List<num> a3 = baz({3: "hello"} ?? {3: "hello"});
}

produces:

S = dynamic, T = String
S = int, T = String
S = num, T = String
S = num, T = String

on both implementations.

The final question is what to do about a downwards context of dynamic. The analyzer treats this as equivalent to an empty context. I'm torn about this: it's not very consistent, but on the other hand a using a downwards context of dynamic is just not very useful, and it's probably friendlier to the user to use the upwards type there. I'll try to run a presubmit tonight with this turned off in the analyzer to see what it looks like. This is probably fairly niche, but I'm sure it comes up.

I'll work on an update to the draft spec this week.

leafpetersen · 2018-02-27T06:49:28Z

Some examples to contemplate:

T foo<T>(T x) {
  print(T);
  return x;
}
List<T> bar<T>(T x) {
  print(T);
  return [x];
}

List<S> baz<S, T>(Map<S, T> x) {
  print("S = $S, T = $T");
}

void main() {
  var y0 = foo(4);
  dynamic y1 = foo(4);
  Object y2 = foo(4);

  print("Bar");
  var z0 = bar(4);
  List<dynamic> z1 = bar(4);
  List<Object> z2 = bar(4);

  print("[foo]");
  z1 = [foo(4)];
  z2 = [foo(4)];
  List<int> z3 = [foo(4)];

  print("baz");
  List<dynamic> a0 = baz({3: "hello"});
  List<int> a1 = baz({3: "hello"});
  List<num> a2 = baz({3: "hello"});
  List<num> a3 = baz({3: "hello"} ?? {3: "hello"});
}

Currently ddc and ddc -k agree on everything except one place:

int
int
Object
Bar
int
dynamic
Object
[foo]
int // ddc says dynamic, ddc -k says int
Object
int
baz
S = dynamic, T = String
S = int, T = String
S = num, T = String
S = num, T = String

stereotype441 · 2018-02-27T06:59:52Z

@leafpetersen

? and _ should be treated equivalently

Just to clarify: do you mean in all cases, or just for ???. If you mean in all cases, then I can move forward with https://dart-review.googlesource.com/c/sdk/+/43761, and we can address the other issues you've raised in later CLs.

leafpetersen · 2018-02-27T07:03:35Z

In all cases.

lrhn · 2018-02-27T07:23:09Z

I can see the reasoning behind differentiating a context of List<dynamic> from List<Object>.
The former means "List of whatever" and the latter means "List of Object" (and I mean it!).

This probably even generalizes to the top-level, so

Object y2 = foo(4);  // prints "Object"

makes sense in the same way. It doesn't matter as much, since you can't create an object containing the type.
What about:

List<T> foo<T>(T x) { print(T); return <T>[x]; }
Object o1 = foo(42);
dynamic o2 = foo(42);
/// And how does FutureOr fit into this?
FutureOr<Object> o3 = foo(42);
FutureOr<dynamic> o3 = foo(42);

stereotype441 · 2018-02-27T09:25:17Z

Ok, https://dart-review.googlesource.com/c/sdk/+/43761 is now out for review--it should fix the error Vijay saw. I won't close this bug when it lands, since other open questions were raised during the discussion.

stereotype441 · 2018-02-27T12:10:40Z

@leafpetersen

This points out a second area where I think the spec draft is just wrong (but the analyzer, and it looks like kernel as well both do the right thing). We should use the more precise upwards type for subsequent inference. For example, the draft spec says:
- The expression `e0 ?? e1` is inferred as `m0 ?? m1` of type `T` in
  context `K`:
  - If `e0` is inferred as `m0` of type `T0` in context `K`
  - And `e1` is inferred as `m1` of type `T1` in context `J`
  - Where `J` is `T0` if `K` is `_` and otherwise `K`
  - Where `T` is the greatest closure of `K` with respect to `?` if `K` is not
    `_` and otherwise `UP(T0, T1)`
which implies that even if T0 is more precise than (the greatest closure of) K, we still use (the greatest closure of) K as the type of m0 && m1. But we should only do so if UP(T0, T1) is not a subtype of the greatest closure of K.
- The expression `e0 ?? e1` is inferred as `m0 ?? m1` of type `T` in
  context K:
  - If `e0` is inferred as `m0` of type `T0` in context `K`
  - And `e1` is inferred as `m1` of type `T1` in context `J`
  - Where `J` is `T0` if `K` is `_` or `?`; and otherwise `K`
  - Where `T` is `UP(T0, T1)` if `UP(T0, T1)` is a subtype of the greatest closure of `K`, and otherwise is the greatest closure of `K`.
Both implementations seem to do the right thing...

They don't quite implement the above algorithm. Here is an example of where they don't do the right thing:

class I {
  void f() {}
}
class J {}
class C extends I implements J {}
class D extends I implements J {}
void test(C c, D d) {
  I x = (c ?? d)..f();
}

Both the analyzer and the CFE complain that the call to f can't be resolved, because they consider the type of c ?? d to be Object. I think the right way to fix this is as part of fixing #31792. I'll update that bug with a reference to this example.

stereotype441 · 2018-02-27T12:30:06Z

After further reflection, I've filed a new issue for my example above, since it is related to #31792 but not the same. Here it is: #32339

dgrove · 2018-02-28T17:40:38Z

any updates on this?

leafpetersen · 2018-02-28T19:31:48Z

I've filed #32357 to track the question around dynamic. I believe everything else is either addressed by the CL @stereotype441 has out, or is tracked elsewhere, so once the CL lands we can close this.

kmillikin · 2018-03-01T10:40:11Z

? and _ should be treated equivalently.

If that's the case, is there any reason to have a notion of an 'empty (expectation) context' at all?

stereotype441 · 2018-03-01T10:43:33Z

? and _ should be treated equivalently.

If that's the case, is there any reason to have a notion of an 'empty (expectation) context' at all?

My two cents: that notion should go away, and everywhere we're using _ ("empty expectation context") we should just use ? ("unknown type") instead. That's what I've done in https://dart-review.googlesource.com/c/sdk/+/43761.

We do this by requiring that the context argument to inferExpression is non-null (since `_` is represented by `null`). Instead of passing `null` as a type context, we pass `const UnknownType()`, which represents `?`. See #32291. Change-Id: I9a0d0f3bcd74e6226004c85f63cf8be49934388a Reviewed-on: https://dart-review.googlesource.com/43761 Commit-Queue: Paul Berry <paulberry@google.com> Reviewed-by: Kevin Millikin <kmillikin@google.com> Reviewed-by: Dmitry Stefantsov <dmitryas@google.com>

stereotype441 · 2018-03-01T13:25:52Z

Fixed by 90098c6.

leafpetersen · 2018-03-01T17:52:49Z

My two cents: that notion should go away, and everywhere we're using _ ("empty expectation context") we should just use ? ("unknown type") instead.

Agreed.

vsmenon added P0 A serious issue requiring immediate resolution legacy-area-front-end Legacy: Use area-dart-model instead. I/O Beta 2.0 labels Feb 23, 2018

vsmenon assigned kmillikin Feb 23, 2018

JekCharlsonYu added this to the I/O Beta 2 milestone Feb 23, 2018

stereotype441 self-assigned this Feb 26, 2018

JekCharlsonYu removed the I/O Beta 2.0 label Feb 26, 2018

stereotype441 mentioned this issue Feb 27, 2018

Type of an if-null or conditional expression should only be the LUB if it's a subtype of the context #32339

Closed

leafpetersen mentioned this issue Feb 28, 2018

Shou 8000 ld a downwards context of dynamic be treated as empty during inference? #32357

Closed

stereotype441 closed this as completed Mar 1, 2018

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

CFE inference issue on generic method type param? #32291

CFE inference issue on generic method type param? #32291

CFE inference issue on generic method type param? #32291

CFE inference issue on generic method type param? #32291

Comments