Pattern Matching for Java — Runtime and Translation

Background

We’ve proposed several kinds of patterns, such as deconstructor patterns, constant patterns, and type test patterns, and several linguistic contexts in which pattern matching might be supported (match predicate, switch statement). An obvious question is: what bytecode should the compiler generate for a pattern match, or for the implementation of a pattern? (There is also the question of how one might declare a pattern in source code; this is a topic for a separate document.)

def unapply(p : Point) : Option[(int, int)] = Some(p.x, p.y)

Basic strategy

We’ll start with the runtime representation and work our way up to classfile representation (and later, source file representation). Our runtime strategy represents a pattern as a constant bundle of method handles. Let’s cover the simple (common) case and then we’ll add in machinery for the general case.

interface __Pattern {
    int numComponents();
    MethodHandle predicate();      // T -> bool
    MethodHandle component(int i); // T -> Bi
}

To emit pattern-matching code, a compiler has to acquire a reference to the pattern object (likely via indy/condy), ask the pattern for its predicate method handle, invoke the predicate handle on the target, and, if the predicate succeeds, ask the pattern for the component method handles and invoke them on the target. (We can further use indy/condy to cache the individual method handles, moving the “ask the pattern for its handles” code to link time.) If the pattern is statically known to be total, then invoking the predicate can be omitted.

Illustrating deconstructing a Point into its x and y components using Java code (though in reality, this would only be called by compiler-generated code, or via reflection):

__Pattern p = ...;                       // constant
MethodHandle predicate = p.predicate();  // constant
MethodHandle pointX = p.component(0);    // constant
MethodHandle pointY = p.component(1);    // constant
if ((boolean) predicate.invoke(target)) {
    int x = (int) pointX.invoke(target);
    int y = (int) pointY.invoke(target);
    ... use x and y ...
}

interface __Pattern {
    int numComponents();
    MethodHandle preprocess();     // T -> C
    MethodHandle predicate();      // (T,C) -> bool
    MethodHandle component(int i); // (T,C) -> Bi
}

Classfile encoding

Logically, patterns are members of classes, like methods and constructors, though we cannot use the exact encoding of these artifacts for reasons outlined earlier.

Just as executable members include constructors, static methods, and instance methods, each of these cases is potentially sensible for patterns as well. We’ve already enumerated several types of useful patterns; match-everything patterns, type-test patterns, deconstruction patterns, etc. Deconstruction patterns (e.g., Point(var x, var y)) are analogous to constructors — in fact, for well-behaved objects, they are the dual of constructors. And static patterns are the dual of static factories.

Like methods, patterns have names, and it is reasonable to want to overload multiple patterns with the same name but different signatures. For example, suppose we have overloaded constructors:

File(String s) { ... }
File(Path p) { ... }
File(URI u) { ... }

We have these constructors for client convenience — whatever the client has, we can make a File out of that. So similarly, we want deconstructing a File to be equally convenient, and expose overloaded patterns:

case File(String name): ...
-- or --
case File(Path p): ...
-- or --
case File(URI u): ...

static __Pattern DD() { ... }

Deconstructor_attribute {
    u2 name_index;
    u4 length;
    u1 is_total;
    u2 carrier_type;        // UTF8 type descriptor
    u2 generic_signature;   // S (UTF8 signature)
}

Migration compatibility

Because compile-time information is used to condition code generation, we need to be clear about what can change, and can’t, in a binary-compatible way.

Compilers can use pattern total-ness to make exhaustiveness decisions, which is extremely useful. To be able to rely on this, total-ness should be an intrinsic property of the pattern that does not change across maintenance, and changing a total pattern to partial should not be a binary- or source-compatible change.

However, we envision patterns changing their carrier types, either changing from a box object to a value type when practical, or going from a carrier-free to a carrier-ful implementation through ordinary code evolution. Therefore, existing call sites that embed the carrier type must continue to link, which means that if we are changing a carrier from C to D, then C and D should be adaptable to each other via MethodHandles.asType(). Migrating carriers from a reference type LFoo to a value type QFoo would be supported by asType(). (This suggests that carrier-free implementations should use LObject, allowing future implementations to migrate to a subtype of LObject, or to a value type.)

Strawman API

We’ve built a prototype of this approach. It has factories for constant patterns, type test patterns, any patterns, and deconstruction patterns, and combinators for dropping bindings, adapting the target to a supertype of the target, ANDing patterns together, and nesting patterns.

public interface __Pattern<T> {
    /**
     * A method handle used to preprocess a target into an intermediate carrier.
     * The method handle accepts a match target and returns the intermediate
     * carrier.
     *
     * If the carrierFree() method returns true, then this method need not be
     * called, and null can be used for the carrier in other method handle
     * invocations.
     */
    MethodHandle preprocess();

    /**
     * A method handle used to determine if the match succeeds.  It accepts
     * the match target and the intermediate carrier returned by preprocess(),
     * and returns a boolean indicating whether the match was successful.
     *
     * If the pattern is declared to always match, then this method need not be
     * called.
     */
    MethodHandle predicate();

    /**
     * A method handle to return the i'th component of a successful match.  It
     * accepts the match target and the intermediate carrier returned by
     * preprocess(), and returns the component.
     */
    MethodHandle component(int i);

    /**
     * Indicates that this pattern does not make use of an intermediate carrier,
     * and that the tryExact() method handle is a no-op.
     * Combinators exploit carrier freedom to reduce unnecessary allocation.
     */
    boolean isCarrierFree();

    /**
     * Returns the pattern descriptor, which is a MethodType whose return type
     * is the match target, and whose parameter types are the components of the
     * match.
     */
    MethodType descriptor();

    /**
     * Returns the match target type
     */
    default Class<?> targetType() {
        return descriptor().returnType();
    }

    /**
     * Return the intermediate carrier type
     */
    default Class<?> carrierType() {
        return preprocess().type().returnType();
    }

    // -- Combinators --

    /**
     * Return a __Pattern that is identical to this one, but with fewer
     * binding components
     * @param positions indices of the binding components to drop
     */
    default __Pattern<T> dropBindings(int... positions) {
        return __Patterns.dropBindings(this, positions);
    }

    // -- Factories --

    /**
     * Return a pattern handle that matches a constant
     */
    static <T> __Pattern<T> ofConstant(Class<T> targetType, T constant) {
        return __Patterns.ofConstant(targetType, constant);
    }

    /**
     * Return a pattern handle that matches null
     */
    static <T> __Pattern<Object> ofNull() {
        return __Patterns.ofNull();
    }

    /**
     * Return a pattern handle that matches a non-null reference
     */
    static<T> __Pattern<T> ofNonNull(Class<T> targetType) {
        return __Patterns.ofNonNull(targetType);
    }

    /**
     * Return a pattern handle that matches targets of the type testType, and
     * produces its target as a binding component.  If
     * testType == targetType, this pattern will always succeed.
     */
    static <T, U extends T> __Pattern<T> ofType(Class<T> targetType, Class<U> testType) {
        return __Patterns.ofType(targetType, testType);
    }

    /**
     * Return a pattern handle for a given target type that always succeeds, and
     * produces its target as a binding component.
     *
     * To accept a broader range of target types, use {@link __Pattern::ofType(Class,Class)}
     * or {@link __Pattern::adaptTarget}
     */
    static <T> __Pattern<T> ofType(Class<T> targetType) {
        return __Patterns.ofType(targetType, targetType);
    }

    /**
     * Return a pattern handle that always succeeds
     */
    static <T> __Pattern<T> ofAny(Class<T> targetType) {
        return __Patterns.ofAny(targetType);
    }

    /**
     * Return a pattern handle that tests its target against testType, and, if
     * successful, extracts components from it according to the {@code components}
     * array of method handles, which each accept a single argument of {@code typeTest}
     */
    static <T, U extends T> __Pattern<T> ofComponents(Class<T> targetType,
                                                          Class<U> testType,
                                                          MethodHandle... components) {
        return __Patterns.ofComponents(targetType, testType, components);
    }

    /**
     * Adapt a pattern handle to a broader target type.
     */
    static<T, U extends T> __Pattern<T> adaptTarget(Class<T> targetType,
                                                        __Pattern<U> pattern) {
        return __Patterns.adaptTarget(pattern, targetType);
    }

    /**
     * Return a pattern handle that is the AND of the two patterns provided.
     * The binding components will be the union of the binding components
     * of the two patterns.
     */
    static<T> __Pattern<T> and(Class<T> targetType,
                                   __Pattern<? extends T> left,
                                   __Pattern<? extends T> right) {
        return __Patterns.and(targetType, left, right);
    }

    /**
     * Returns a pattern handle that matches the outer pattern and then
     * matches its binding components to the nested patterns.  The binding
     * components are the binding components of the outer pattern, followed
     * by the binding components of each nested pattern.
     */
    static<T> __Pattern<T> nested(__Pattern<T> outer, __Pattern... nested) {
        return __Patterns.nest(outer, nested);
    }

Future work

This document focuses mostly on the compilation target, and on analysis of compatibility requirements. Deliberately left out topics include:

• Language syntax. While this is a very interesting topic, we prefer to lay a solid groundwork that captures runtime description, translation strategy, and migration compatibility before moving on to the far more subjective subject of defining a language syntax for describing patterns.

• Switch classifiers. While some languages translate pattern switches into chains of if-else, it is often possible to do better, by performing a pre-computation (e.g., hashing) on the target, and strength-reducing to a traditional switch. (This generally must be tolerant of changes induced by recompilation, such as changed class hierarchies, so indy is likely called for here.) We anticipate being able to use class hierarchy information to optimize switches over subtypes of sealed hierarchies, and avoid redundant tests based on known type relationships. This problem will be addressed in a separate document.