Does the new pattern proposal allow user defined equality?

[leafpetersen]

[Updated: This was an overly terse summary, which caused some confusion. I've elaborated (hopefully more clearly) here]

The current rules for switches require that constants in switches come from classes that do not override equality. The new pattern proposal adds a relational pattern == constant which is defined to call the equality operator on the receiver (and also relational operators similarly).

• Is == constant intended to work when the receiver overrides operator ==?
• Does the proposal eliminate the current error for existing switches?

cc @lrhn @eernstg @munificent @stereotype441 @natebosch @jakemac53

[munificent]

• Is == constant intended to work when the receiver overrides operator ==?

Yes, I don't see why not.

• Does the proposal eliminate the current error for existing switches?

I think it should, yes. Any reason why not?

[eernstg]

We just had an issue (dart-lang/sdk#49585) about the performance of the current kind of switch statement. Apparently, some backends don't optimize those as much as I would have expected, but the main point I want to make here is that we could make certain switch statements (including the ones we have today) work considerably faster than a linear scan which is capable of running arbitrary code at each case.

Will it be sufficient to just recognize the fast ones and compile them using jump tables and such? Or will developers then have to walk a tightrope in order to make sure that they get the fast translation, and they'll always have to worry about even the tiniest change that might implicitly turn their fast switch into a slow one?

We could make the difference explicit in the code (and thus given developers control) by keeping today's switch unchanged. This kind of switch could then be used when the more powerful matching features are not needed, but high performance is crucial.

They could then use the new syntax when they want to use pattern matching, which is probably going to imply a linear scan (because it's difficult to ensure a predictable semantics otherwise), and they can know for sure that they stick to the highly optimizable kind of switch when they use the current syntax.

Of course, it probably takes a very long discussion to find that new syntax, but I believe that it should be rather easy to disambiguate an arbitrary keyword (it doesn't have to be a reserved word, probably not even a built-in identifier), so we might well be able to use, say, match.

match (<expression>) {
  case ... // Case is a reserved word, so this is not a local function declaration.
}

[munificent]

We just had an issue (dart-lang/sdk#49585) about the performance of the current kind of switch statement.

I'm not surprised that that issue relates to implementing a VM's instruction dispatcher. That seems to disproportionately be the kind of code where switch performance matters. Outside of those and lexers, I don't see switch performance come up very much.

Will it be sufficient to just recognize the fast ones and compile them using jump tables and such?

I think so. In the example, the compiler already knows that it's switching over an integer and what the exact integer values of each case is. That should be enough to know that it can compile the switch to a jump table, or at least a binary search. All of that is equally true if we extend switches to support patterns. The compiler will still be able to tell if a switch is switching on an integer type and if all the cases are literal or named constant cases and what those constant values are.

If you start using more interesting patterns in there, it might be hard to compile them efficiently. In particular, if you use extractor, list, or map patterns then it can call user-defined methods. Or if you switch on a non-sealed type (i.e. not int, string, double, bool). But as long as you switch on primitive types, enums, and/or records containing those, I think the compiler can reliably tell that no side effects can occur and can compile to something faster than a linear scan.

If I'm missing something and that's not the case, I'd definitely like to know. My hope is that switches on primitive and enum types are as optimizable with patterns as they are today and that likewise matching on records should be pretty optimizable by the compiler.

When the compiler does have to resort linear scan (with caching #2107), I think that's no slower than the code users would write if we didn't have pattern matching switches, so that's OK.

so we might well be able to use, say, match.

I did consider that, but I think it's a bad idea to pick a contextual keyword that's the same name as the name of a type in the core library. :-/

[leafpetersen]

When the compiler does have to resort linear scan (with caching #2107), I think that's no slower than the code users would write if we didn't have pattern matching switches, so that's OK.

I don't think the main concern would be with linear scan, but with whether or not switching on a set of constants requires actually calling the (potentially) user defined == operator or not, and whether we can avoid doing so in all of the cases where we currently do not do so (that is, that we can make the generality added here "pay as you go"). Concretely, consider this currently legal program:

class A {
  const A();
}

class B {
  const B();
}

class C {
  bool operator ==(Object other) {
    print("hello");
    return false;
  }
}

const Object a = A();
const Object b = B();
void main() {
  Object o = C();
  switch (o) {
    case a: print("A"); break;
    case b: print("B"); break;
    default: break;
  }
}

This program never calls any equality method (or at least does not need to), since:

• It is an error to switch over constants which override primitive equality.
• The semantics are defined to not call the equality method on the scrutinee (here 'o') but on the case constant (here a and b).

In other words, the semantics are set up such that this can be compiled to simply check identity.

As specified in the proposal, I believe that the following program would behave quite differently:

class A {
  const A();
}

class B {
  const B();
}

class C {
  bool operator ==(Object other) {
    print("hello");
    return false;
  }
}

const Object a = A();
const Object b = B();
void main() {
  Object o = C();
  switch (o) {
    case == a: print("A"); break;
    case == b: print("B"); break;
    default: break;
  }
}

I believe that as specified, this program will print "hello" twice, and then break, since the semantics are defined to call equality in the other order: o == a and o == b. Is that not correct?

So the questions I was trying to get at are:

• Do we intend the two versions of the program listed above to be different?
• If so, are we sure that we can still compile existing switches efficiently?

I think that so long as we are not proposing to change the direction of the equality check for existing constant patterns, the answer to the second question is "yes", but @rakudrama should probably check me on that.

• Does the proposal eliminate the current error for existing switches?

I think it should, yes. Any reason why not?

I have some concern that we are removing a performance rail. Currently, simple switches over constants are ensured to be implementable relatively performantly. Removing this error means that you can fairly radically change the performance profile of a switch by overriding operator == on one of the constants. It is (I believe, see above) still pay as you go, so it's maybe not terrible, but it does worry me slightly.

[munificent]

I believe that as specified, this program will print "hello" twice, and then break, since the semantics are defined to call equality in the other order: o == a and o == b. Is that not correct?

Yeah, that is correct. That's an interesting example!

So the questions I was trying to get at are:

• Do we intend the two versions of the program listed above to be different?

I don't know if I'd say "intend". I didn't wake up one morning and design the proposal specifically around this example. :) But I do think the different behavior naturally falls out of design choices that otherwise make sense, and it doesn't seem particularly problematic to me that the behavior is different, unless there's something I'm missing.

It is technically a breaking change. I would be quite surprised if any significant amount of existing Dart code was affected by the change.

• If so, are we sure that we can still compile existing switches efficiently?

I believe so. I think the existing switches where performance matters are ones where the cases and scrutinee are all the same type and that type is int, String, or an enum (that doesn't override ==). When that's true, we know that the == method being called is one defined by the core library and not overridden by user code, so the compiler can assume it doesn't have side effects and knows how it behaves.

If we were to ever make int non-sealed, then we'd have big problems. Unless I'm missing something, I think patterns still let us compile switches on integer and enum types quickly. If all the cases are ints or enums but the scrutinee is not, then it gets harder because you could be calling a user-defined ==. I'm fairly confident that the switches where performance matters are also ones where the scrutinee and cases have a homogeneous type.

I have some concern that we are removing a performance rail. Currently, simple switches over constants are ensured to be implementable relatively performantly.

I mean, the other way to look at it is that the old language team kneecapped switches—you can't even switch on doubles!—in order to provide that rail... and even then the implementation teams didn't bother to take advantage of it and users didn't care enough to bother them about it. If that rail actually mattered, we'd have been having this discussion in 2012 and not 2022. :)

[leafpetersen]

It is technically a breaking change. I would be quite surprised if any significant amount of existing Dart code was affected by the change.

I don't understand: if the two programs above are different (which you say above that they are), then there's no breaking change, right?

I think the existing switches where performance matters are ones where the cases and scrutinee are all the same type and that type is int, String, or an enum (that doesn't override ==). When that's true, we know that the == method being called is one defined by the core library and not overridden by user code,

This is only true if the equality called is not the one on the scrutinee.

and even then the implementation teams didn't bother to take advantage of it

No, they absolutely do. I do not believe any implementation (probably not even DDC) actually calls the equality method to evaluate switches.

[leafpetersen]

Thinking about this a bit more from the user perspective. We have a choice around how to interpret literal/constant patterns:

• We can interpret them as checking identity
• We can interpret them as calling the equality method on the constant
• We can interpret them as calling the equality method on the scrutinee

Current Dart can be thought of as doing either of the first two, since they are equivalent given the constraint on switches, but if we drop that constraint they become potentially different.

It seems weird to me that you can have a constant pattern like 1 and have it be matched by something completely and arbitrarily different. That pushes me towards one of the first two interpretations. That's inconsistent with the semantics of == 1, but that seems broadly ok to me. It's a different pattern. But... it does mean that there is no way to take a literal pattern like 1 and name the literal while still preserving the existing behavior. So maybe there should be an identity pattern? Or a reverse equality pattern: a == is the pattern which checks a == o for scrutinee o?

[natebosch]

Current Dart can be thought of as doing either of the first two, since they are equivalent given the constraint on switches, but if we drop that constraint they become potentially different.

I don't think that current Dart switch can be thought of as checking identity. I can construct a String instance which is not identical to a constant String, but does match a switch case with that constant String. (At least on the VM, the browser seems to canonicalize some strings at runtime that the VM doesn't)

[leafpetersen]

I don't think that current Dart switch can be thought of as checking identity. I can construct a String instance which is not identical to a constant String, but does match a switch case with that constant String.

Fair enough. I don't think that changes the substance of my question though.

[rakudrama]

and even then the implementation teams didn't bother to take advantage of it

Compiling a Dart switch statement to a JavaScript switch statement is taking advantage of it. Otherwise we would have to generate an if-then-else chain.

dart2js goes further and converts a switch on enums to a switch on the enum index. Some JavaScript VMs can compile switches with integer case values in a compact range to a jump table (example).

So Dart on the web can be said to sometimes implement switch statements on enums using jump tables.

I don't think that current Dart switch can be thought of as checking identity. I can construct a String instance which is not identical to a constant String, but does match a switch case with that constant String. (At least on the VM, the browser seems to canonicalize some strings at runtime that the VM doesn't)

JavaScript defines === and Object.is as returning true for strings that have the same sequence of code units. This makes it impossible to have two Strings that are Dart == but not identical, even if they are separate 'primitive' objects residing in different places in the heap. There is just no way to tell they are separate objects and the JavaScript engine is free to canonicalize them any way it chooses.

In effect, Dart on the web uses identical(caseValue, scrutinee), but identical is expanded to include String objects that have the same contents.

If records are identical by having identical field values, it will feel very strange for the VM to persist in having Strings that are equal but not identical.

[eernstg]

I think we're moving in and out of several topics here, so let me restate the parts that I'm a little bit worried about:

• Some switch statements currently allow for an optimized translation (e.g., jump tables for enums).
• We should preserve the ability to optimize those switch statements, and we should be really careful about introducing breaking changes to the dynamic semantics of existing code.
• Pattern matching is inherently a linear scan (if any steps can have side effects, which is "always" in practice, because there are so many ways to make the matching process run arbitrary code).
• Developers should be in control when they make the choice between fast switch statements and pattern matching, preferably in a way which is visible (as opposed to "you can only know which variant you have in this switch statement/expression if you can ask the analyzer").

I know, Dart is not the language where switch statements are used to implement state machines (e.g., lexers) every day, but I still think that we should preserve the ability to have a performant construct using the switch syntax, and I think it makes sense to use a different syntax to specify the new pattern matching constructs (even the tiniest difference would suffice, we can still see it).

[lrhn]

Current Dart switch case checking is "primitive equality" checking on "the same type", which means identical except for certain known platform types. Because of that we know, for certain, that == is symmetric and without side effects. We can do any number of optimizations to get to the equality, including using identical for all non-platform types.
(Did we remove the requirement that the cases must have the same type as the switched expression? If so, symmetry is no longer promised, because the switch expression value can have a user defined ==.)

With patterns, we allow user-defined == methods in general, so we no longer know that == is symmetric, without side effects, or even consistent over time. Whether case a: and case == a: should be the same or not ... I'd probably make them so, using the == a behavior for both. (That shouldn't matter for any existing switch, if it's guaranteed symmetric and without side effects.)

I can argue for both directions.

• o == a sounds like what you'd do if you are inspecting the value o. Also, it makes it easier to cache results of common pattern subexpressions if all the invocations are on the same object. It's good object orientation to ask an unknown object about itself, instead of asking other objects about it. Low-level, you can optimize calls to o.== by caching the method lookup.
• a == o makes the pattern object a, the object you are in complete control of when writing the switch, be the one to decide which check to make. You know the == implementation at the switch position, and can potentially inline it. (At least when a is constant, which it still needs to be, right?). There is no way the foreign object being switched on can hack its way around the switch by using a cleverly written == method. Puts the developer in charge of which equality checks will be made, so they can control performance.

I prefer the latter, but the == a pattern cannot reasonably be interpreted any other way than as the former, and if we only get to have one strategy for equality, it'll have to be it.

[stereotype441]

I don't really have any facts to add to the arguments presented above, but just for the record here's some opinions 😄:

Personally I'm a fan of @lrhn's o == a approach because I want case a: and case == a: to be equivalent. I think that in the majority of situations it's not going to make any user-visible difference, but in the situations where it does make a difference, I think users are going to assume o == a semantics, so we should follow that.

As for performance, I think there are two separate cases:

• When switching on an int, or an enum that doesn't override operator==, I expect the compiler to create a jump table (or something similar), and I don't think that's a problem, because ints and enums are sealed types, so that's safe for the compiler to do.
• When switching on anything else, I don't expect performance to be any better than a naive desugaring into an if/else chain, in which case I think o == a semantics is fine; if the code is so performance critical that the user needs to do something cleverer than that, they're welcome to manually desugar it and then tweak it to do whatever is best.

As for @eernstg's idea of introducing a new syntax for the new matching construct, I'm not a huge fan. I think that as we're adding new features to Dart, we should strive as much as possible to steer towards the language that we would have wanted if those features had been present from day one. So that new users don't have to understand the history of Dart to make sense of the language design. I personally think that if we had had patterns from day one, we would just have a single common syntax for switch and match.