Record pattern, the runtime side

[Remi Forax]

Following the discussions we had, i've implemented a prototype of what can be the runtime part of the pattern matching that supports record pattern.

It works in 3 steps:
Step 1, at compile time, the compiler takes all the patterns and creates a tree of pattern from the list of patterns,
pattern that starts with the same prefix are merged together.
In the end, the tree of patterns is encoded in the bytecode as a tree of constant dynamic (each Pattern is created only from constant and patterns).

  sealed interface Pattern {}
  record NullPattern() implements Pattern {}
  record ConstantPattern(Object constant) implements Pattern {}
  record TypePattern(Class<?> type) implements Pattern {}
  record RecordPattern(Class<?> recordClass, Pattern... patterns) implements Pattern {}
  
  record OrPattern(Pattern pattern1, Pattern pattern2) implements Pattern {}
  record ResultPattern(int index, Pattern pattern) implements Pattern {} 

The last two patterns are less obvious, the OrPattern allows to create the tree by saying that a pattern should be executed before another one.
Because the patterns are organized as a tree and not a list, we need a way to associate which branch of the tree correspond to which pattern from the use POV, the ResultPattern encodes in the carrier the index (the first pattern is 0, the second one is 1, etc) inside the first component of the carrier.

I've chosen to not represent the bindings (and their corresponding the component index in the carrier) and to use the fact that binding slot are numbered in the order of the tree traversal.
This is maybe too brittle because the compiler and the runtime has to agree on the order of the traversal. But this avoids to encode too many information in the bytecode.

Step 2, 
at runtime, the first call to invokedynamic with the pattern tree as arguments, creates a tree of method handles that will match the pattern.
During that phase, the runtime environment can be checked to see if the pattern tree is invalid with the runtime classes, in that case a linkage error is thrown.
In the prototype the method is called toMatcher and takes a Lookup (to find the accessors of the record of the RecordPattern), a receiverClass the type of the variable switch upon,
the carrier type (a method type as a tuple of the type of the binding in the tree traversal order), the index of the first binding (in case of a switch the first component in the matching index so the binding slots starts at 1) and method handle (the null matcher) to call if a null is found (the two possible semantics are doNotMatch/return null or throw a NPE).

  pattern.toMatcher(lookup, receiverClass, carrierType, firstBinding (0 or 1), nullMatcher);

Step 3,
during the execution,
- if it's an instanceof a carrier which is null means no match otherwise the carrier contains the value of the bindings,
- if it's a switch, a carrier which is null means "default" otherwise the component 0 or the carrier contains the index of the pattern matched and the binding values
- if it's an assignment, the carrier can not be null because the nullMatcher throws a NPE earlier, so the carrier contains the binding values

An example of instanceof
https://github.com/forax/switch-carrier/blob/master/src/main/java/com/github/forax/carrier/java/lang/runtime/InstanceOfExamples.java#L15

An example of switch
https://github.com/forax/switch-carrier/blob/master/src/main/java/com/github/forax/carrier/java/lang/runtime/SwitchExamples.java#L17

An example of assignment
https://github.com/forax/switch-carrier/blob/master/src/main/java/com/github/forax/carrier/java/lang/runtime/AssignmentExamples.java#L14

regards,
Rémi