Record pattern promotes fields from `void` to `Object?`

[lrhn]

Example:

void main() {
  var s = ("a", "b", "c") as (Object?, void, Object?);
  switch (s) {
    case var x when x.l("1.x") || s.l("1.s"): // void
    case var x when x.l("2.x") || s.l("2.s"): // void
    case (_, _, _) && var x when x.l("3.x") || s.l("3.s"): // Object?
    case var x when x.l("4.x") || s.l("4.s"): // Object?
  }
}

extension <T> on T {
  bool l(String name) {
    print("$name: $this:$runtimeType @ $T"); // value, runtime and static type
    return false;
  }
}

The case (_, _, _), which should be a no-op for a matched value type of (Object?, void, Object?)
"promotes" the middle record field's static type to Object?.

That loses void protection.
If it's not an implementation bug, then it's a spec bug, but it should still be fixed.

[johnniwinther]

cc @stereotype441

[lrhn]

The promotion also happens even if the pattern is not guaranteed to match, like:

case (42, _, _):

The matched value type of the next pattern is (Object?, Object?, Object?) in that case too.
(Even in the same match pattern

case (42, _, _) || var _ when s.l("3.s"): // Object?

where the first case doesn't match, it still promotes s to (Object?, Object?, Object?).

A larger example:

void main() {
  var s = ("a", "b", "c") as (Object?, void, Object?);
  switch (s) {
    case var x when x.l("x") || s.l("s"): // void
    case Record x when x.l("r.x") || s.l("r.s"): // Record/void
    case var x when x.l("x") || s.l("s"): // void
    case Triple<dynamic> x when x.l("t.x") || s.l("t.s"): // dynamic
    case var x when x.l("x") || s.l("s"): // dynamic
    case Triple<Object> x when x.l("t.x") || s.l("t.s"): // Object
    case var x when x.l("x") || s.l("s"): // dynamic
    case Triple<void> x when x.l("t.x") || s.l("t.s"): // void/dynamic
    case var x when x.l("x") || s.l("s"): // void/dynamic
    case (42, _, _) || _ when s.l("42.s"): // Object?
    case var x when x.l("x") || s.l("s"): // Object?
  }
}

typedef Triple<T> = (Object?, T, Object?);

extension <T> on T {
  bool l(String name) {
    print("$name: $this:$runtimeType @ $T"); // value, runtime and static type
    return false;
  }
}

It seems like a record pattern can perform some kind of promotion on the matched value and the matched variable, even if the pattern match fails due to a when clause. Also when the pattern doesn't even match.

It's not consistent. The Triple<dynamic> promotes the matched value and s variable's middle field to dynamic, but the Triple<void> only promoted the matched value, not the variable.
I'm guessing some kind of join/LUB is going on, and we're seeing MORETOP in some cases, but not all?

[stereotype441]

Ok, I've finally tracked down what's happening in the larger example from @lrhn's last comment. Repeating it here:

void main() {
  var s = ("a", "b", "c") as (Object?, void, Object?);
  switch (s) {
    case var x when x.l("x") || s.l("s"): // void
    case Record x when x.l("r.x") || s.l("r.s"): // Record/void
    case var x when x.l("x") || s.l("s"): // void
    case Triple<dynamic> x when x.l("t.x") || s.l("t.s"): // dynamic
    case var x when x.l("x") || s.l("s"): // dynamic
    case Triple<Object> x when x.l("t.x") || s.l("t.s"): // Object
    case var x when x.l("x") || s.l("s"): // dynamic
    case Triple<void> x when x.l("t.x") || s.l("t.s"): // void/dynamic
    case var x when x.l("x") || s.l("s"): // void/dynamic
    case (42, _, _) || _ when s.l("42.s"): // Object?
    case var x when x.l("x") || s.l("s"): // Object?
  }
}

typedef Triple<T> = (Object?, T, Object?);

extension <T> on T {
  bool l(String name) {
    print("$name: $this:$runtimeType @ $T"); // value, runtime and static type
    return false;
  }
}

It turns out it has nothing to do with LUB or MORETOP. The weird behavior here is caused by two things:

• The bug that led to Inconsistent switch promotion. #60496, namely the fact that when deciding whether a pattern match should cause a switch scrutinee to be promoted, flow analysis momentarily forgets about previous scrutinee promotions, and bases the decision on the type that the scrutinee had at the top of the switch statement. Note that this bug only applies to promotion of the scrutinee, not to the promotion of the matched value type.
• The coincidental fact that Triple<void> happens to be the same type as the type the scrutinee had at the top of the switch statement (Object?, void, Object?).

Here's how it all plays out in painstaking detail:

• When analyzing case var x when x.l("x") || s.l("s"):, no promotion occurs since there is no type test.
• When analyzing case Record x when x.l("r.x") || s.l("r.s"):, there is a type test checking whether the matched value (and hence the scrutinee) is Record. Since the tested type is not a subtype of the matched value type ((Object?, void, Object?)), the matched value is not promoted. Similarly, since the tested type is not a subtype of the current type of s ((Object?, void, Object?)), s is not promoted.
• When analyzing case var x when x.l("x") || s.l("s"):, again, no promotion occurs since there is no type test.
• When analyzing case Triple<dynamic> x when x.l("t.x") || s.l("t.s"):, there is a type test checking whether the matched value (and hence the scrutinee) is Triple<dynamic>. Since the tested type is a subtype of the matched value type ((Object?, void, Object?)), and it's a subtype of the current type of s (also (Object?, void, Object?)), both are promoted to Triple<dynamic>.
  • At the end of analyzing this case, flow analysis joins together the flow models for all the ways in which case Triple<dynamic> x when x.l("t.x") || s.l("t.s"): might fail to match. There are two flow models to join: (1) the flow model if the matched value doesn't match Triple<dynamic>, and (2) the flow model if the expression x.l("t.x") || s.l("t.s") evaluates to false. Flow analysis knows that (1) is unreachable (since the matched value type of (Object?, void, Object?) is a subtype of Triple<dynamic>), so it discards it, and keeps the flow model from (2). In this flow model, both the matched value type and s remain promoted to Triple<dynamic>.
• When analyzing case var x when x.l("x") || s.l("s"), no further promotion occurs, but the matched value type and s remain promoted to Triple<dynamic>.
• When analyzing case Triple<Object> x when x.l("t.x") || s.l("t.s"):, this is handled similarly to Triple<dynamic>, with two differences:
  • When deciding whether to promote s further, due to Inconsistent switch promotion. #60496, flow analysis gets confused and compares the tested type (Triple<Object>) against the type that s had at the top of the switch statement ((Object?, void, Object?)), instead of comparing it to the type that s has been promoted to (Triple<dynamic>). But this is of no consequence since Triple<Object> is a subtype of both, so s gets promoted to Triple<Object>.
  • At the end of analyzing this case, when joining together the flow models for all the ways in which case Triple<Object> x when x.l("t.x") || s.l("t.s"): might fail to match, both flow models are live (since the matched value type of Triple<dynamic> is not a subtype of Triple<Object>. So the join causes the promotions to Triple<Object> to be dropped, and the matched value type and the promoted type of s both go back to Triple<dynamic>.
• When analyzing case var x when x.l("x") || s.l("s"):, no further promotion occurs, but the matched value type and s remain promoted to Triple<dynamic>.
• When analyzing case Triple<void> x when x.l("t.x") || s.l("t.s"):, things get interesting:
  • The decision of whether to promote the matched value type is based on comparing the currently promoted matched value type (Triple<dynamic>) against the tested type (Triple<void>). Since the latter is a subtype of the former, the matched value type is promoted.
  • But, due to Inconsistent switch promotion. #60496, the decision of whether to promote s is based on comparing the old type of s from the top of the switch statement ((Object?, void, Object?)) against the tested type (Triple<void>). Coincidentally, these are the same type, so no promotion occurs.
  • And that's how we get into the bizarre situation where x has type Triple<void>, but s has type Trible<dynamic>.
  • And again, at the end of analyzing this case, when joining together the flow models for all the ways in which case Triple<void> x when x.l("t.x") || s.l("t.s"): might not match, the first part of the join is discarded, and so the promotion of the matched value type to Triple<void> is kept.
• When analyzing case var x when x.l("x") || s.l("s"):, the matched value type remains promoted to Triple<void>, and s remains promoted to Triple<dynamic>.
• When analyzing case (42, _, _) || _ when s.l("42.s"):, we have some more interesting behaviors:
  • The record pattern match consists of 3 steps:
    • First the shape of the record is checked. This amounts to a type check against (Object?, Object?, Object?). So both the matched value type and s get promoted to (Object?, Object?, Object?). This type check can't fail.
    • Second, the fields of the record are checked. This doesn't do any type checking. But it can cause the match to fail.
    • Third, the type of the record is checked against the so-called "demonstrated type", which is computed based on the types that the fields can reasonably be assumed to have assuming they all matched. This isn't a real type check; it's an artifical type check that flow analysis inserts to ensure that a pattern like (int _, double _) promotes to the type (int, double). It's always known to succeed. In this case, the demonstrated type happens to be (Object?, void, Object?). So the matched value type gets promoted back to (Object?, void, Object?). But s retains its promotion to (Object?, Object?, Object?) (again due to Inconsistent switch promotion. #60496).
  • Now, the remainder of the pattern (|| _) is considered. This causes the success and failure control paths from the match of (42, _, _) to be joined. In the success path, the matched value type was promoted to (Object?, Object?, Object?) and then to (Object, void, Object?), but in the failure path, it was just promoted to (Object?, Object?, Object?). So the promotion to (Object, void, Object?) is dropped, and the matched value type and the type of s are now both promoted to (Object?, Object?, Object?).
  • At the end of analyzing this case, when joining together the flow models for all the ways in which case (42, _, _) || _ when s.l("42.s"): might not match, the only part of the join that is live is the code path where s.l("42.s") evaluates to false. In this code path, the matched value type and the type of s remain promoted to (Object?, Object?, Object?).
• When analyzing case var x when x.l("x") || s.l("s"):, the matched value type and the type of s remain promoted to (Object?, Object?, Object?).

Phew! Ok, I'm going to come back to this tomorrow and try to come up with a suggestion for how we might improve this messy situation.

[eernstg]

Amazing analysis, @stereotype441, as always!

It sounds like it is all about #60496. However, one little thing is surprising to me: I would expect promotion to occur when the given variable (including a pseudo-variable known as 'the matched value') has a type which is a proper supertype of the type that we're promoting it with. But all these top types are subtypes of each other, which means that they shouldn't even be eligible for promotion in the first place.

Does the promotion machinery actually use the more fine-grained subtype hierarchy which is defined in terms of MORETOP, or something similar? If so, is that then a useful choice? (We would be able to promote from void to dynamic to Object?, but not in the opposite direction; this might be exactly what we want, but I'm not sure any such thing will be true in all cases...

[stereotype441]

@eernstg

It sounds like it is all about #60496. However, one little thing is surprising to me: I would expect promotion to occur when the given variable (including a pseudo-variable known as 'the matched value') has a type which is a proper supertype of the type that we're promoting it with. But all these top types are subtypes of each other, which means that they shouldn't even be eligible for promotion in the first place.

Yeah, I suspect that would be a better rule.

Does the promotion machinery actually use the more fine-grained subtype hierarchy which is defined in terms of MORETOP, or something similar? If so, is that then a useful choice? (We would be able to promote from void to dynamic to Object?, but not in the opposite direction; this might be exactly what we want, but I'm not sure any such thing will be true in all cases...

It doesn't currently use the more fine-grained subtype hierarchy of MORETOP. We could change it to work that way, but it would be significantly more effort to do so, since that machinery isn't currently plumbed into the subtype testing logic at all. Personally, I'm more inclined to go with your earlier suggestion (only promoting when we have a proper subtype), since the implementation of that would be fairly straightforward.

[lrhn]

My main confusion comes from a rejected case causing promotion.

If we only promote to proper subtypes, then the type check itself cannot be both trivially satisfied and promoting, and I think that would avoid that confusion.

[stereotype441]

@lrhn

My main confusion comes from a rejected case causing promotion.

If we only promote to proper subtypes, then the type check itself cannot be both trivially satisfied and promoting, and I think that would avoid that confusion.

Agreed. This is a really nice, principled justification for the idea that flow analysis should only promote to proper subtypes. I'll add it to my list and try to get to it as part of the sound-flow-analysis feature.