Pattern Matching for Java

Patterns

Rather than reach for ad-hoc solutions to the test-and-extract problem, we believe it is time for Java to embrace pattern matching. Pattern matching is a technique that has been adapted to many different styles of programming languages going back to the 1960s, including text-oriented languages like SNOBOL4 and AWK, functional languages like Haskell and ML, and more recently extended to object-oriented languages like Scala (and most recently, C#).

A pattern is a combination of a match predicate that determines if the pattern matches a target, along with a set of pattern variables that are conditionally extracted if the pattern matches the target. Many language constructs that test an input, such as instanceof and switch, can be generalized to accept patterns that are matched against the input.

One form of pattern is a type pattern, which consists of a type name and the name of a variable to bind the result to, illustrated below in a generalization of instanceof:

if (x instanceof Integer i) {
    // can use i here, of type Integer
}

Here, x is being matched against the type pattern Integer i. First x is tested to see if it is an instance of Integer. If so, it is cast to Integer, and the result assigned to i. The name i is not a reuse of an existing variable, but instead a declaration of a pattern variable. (The resemblance to a variable declaration is not accidental.)

Using patterns with instanceof simplifies commonly messy operations, such as implementation of equals() methods. For a class Point, we might implement equals() as follows:

public boolean equals(Object o) {
    if (!(o instanceof Point))
        return false;
    Point other = (Point) o;
    return x == other.x
        && y == other.y;
}

Using a pattern match instead, we can combine this into a single expression, eliminating the repetition and simplifying the control flow:

public boolean equals(Object o) {
    return (o instanceof Point other)
        && x == other.x
        && y == other.y;
}

Similarly, we could simplify the if..else chain above with type patterns, eliminating the casting and binding boilerplate:

String formatted = "unknown";
if (obj instanceof Integer i) {
    formatted = String.format("int %d", i);
}
else if (obj instanceof Byte b) {
    formatted = String.format("byte %d", b);
}
else if (obj instanceof Long l) {
    formatted = String.format("long %d", l);
}
else if (obj instanceof Double d) {
    formatted = String.format(“double %f", d);
}
else if (obj instanceof String s) {
    formatted = String.format("String %s", s);
}
...

This is already a big improvement — the business logic pops out much more clearly — but we can do better.

Patterns in multi-way conditionals

The chain of if...else still has some redundancy we’d like to squeeze out, both because it gives bugs a place to hide, and makes readers work harder to understand what the code does. Specifically, the if (obj instanceof ...) part is repeated. We’d like to say “choose the block which best describes the target object”, and be guaranteed that exactly one of them will execute.

We already have a mechanism for a multi-armed equality test in the language — switch. But switch is currently very limited. You can only switch on a small set of types — numbers, strings, and enums — and you can only test for exact equality against constants. But these limitations are mostly accidents of history; the switch statement is a perfect “match” for pattern matching. Just as the type operand of instanceof can be generalized to patterns, so can case labels. Using a switch expression with pattern cases, we can express our formatting example as:

String formatted =
    switch (obj) {
        case Integer i -> String.format("int %d", i);
        case Byte b    -> String.format("byte %d", b);
        case Long l    -> String.format("long %d", l);
        case Double d  -> String.format("double %f", d);
        case String s  -> String.format("String %s, s);
        default        -> String.format("Object %s", obj);
    };
...

Now, the intent of the code is far clearer, because we’re using the right control construct — we’re saying “the expression obj matches at most one of the following conditions, figure it out and evaluate the corresponding expression”. This is more concise, but more importantly it is also safer — we’ve enlisted the language’s aid in ensuring that formatted is always assigned, and the compiler can verify that the supplied cases are exhaustive. As a bonus, it is more optimizable too; in this case we are more likely to be able to do the dispatch in O(1) time.

Constant patterns

We’re already familiar with a kind of pattern, namely, the constant case labels in today’s switch statement. Currently, case labels can only be numeric, string, or enum constants; going forward, these constant case labels are just constant patterns. Matching a target to a constant pattern means the obvious thing: test for equality against the constant. Previously, a constant case label could only be used to match a target of the same type as the case label; going forward, we can use constant pattern to combine type tests and equality tests, allowing us to match Object against specific constants.

The Visitor pattern

The standard trick for separately specifying a hierarchy from its operations is the visitor pattern, which separate traversal of a data structure from the definition of the data structure itself. For example, if the data structure is a tree that represents a design in a CAD application, nearly every operation requires traversing at least some part of the tree — saving, printing, searching for text in element labels, computing weight or cost, validating design rules, etc. While we might start out by representing each of these operations as a virtual method on the root type, this quickly becomes unwieldy, and the visitor pattern enables us to decouple the code for any given traversal (say, searching for text in element labels) from the code that defines the data structure itself, which is often a superior way of organizing the code.

But, the visitor pattern has costs. To use it, a hierarchy has to be designed for visitation. This involves giving every node an accept(Visitor) method, and defining a Visitor interface:

interface NodeVisitor<T> {
    T visit(IntNode node);
    T visit(NegNode node);
    T visit(MulNode node);
    T visit(AddNode node);
}

If we wanted to define our evaluation method as a visitor over Node, we would do so like this:

class EvalVisitor implements NodeVisitor<Integer> {
    Integer visit(IntNode node) {
        return node.value;
    }

    Integer visit(NegNode node) {
        return -node.accept(this);
    }

    Integer visit(MulNode node) {
        return node.left.accept(this) * node.right.accept(this);
    }

    Integer visit(AddNode node) {
        return node.left.accept(this) + node.right.accept(this);
    }
}

For a simple hierarchy and a simple traversal, this isn’t too bad. We suffer some constant code overhead for being visitor-ready (every node class needs an accept method, and a single visitor interface), and thereafter we write one visitor per traversing operation. (As an added penality, we have to box primitives returned by visitors.) But, visitors rightly have a reputation for being verbose and rigid; as visitors get more complicated, it is common to have multiple levels of visitors involved in a single traversal.

Visitor has the right idea — separating the operations over a hierarchy from the hierarchy definition itself — but the result is less than ideal. And, if the hierarchy was not designed for visitation — or worse, the elements you are traversing do not even have a common supertype — you are out of luck. In the next section, we’ll see how pattern matching gets us the type-driven traversal that Visitor offers, without its verbosity, intrusiveness, or restrictions.

Sidebar: Data-driven polymorphism with patterns

The promise of the Visitor pattern is that operations on stable hierarchies can be specified separately from the hierarchy. But, this comes at a cost — visitor-based code is bulky, easy to get wrong, annoying to write, and annoying to read. Pattern matching allows you to achieve the same result without the machinery of Visitors interposing themselves, resulting in cleaner, simpler, more transparent, and more flexible code. And, pattern matching doesn’t even have the “stable hierarchy” requirement — or indeed, any hierarchy requirement — that Visitor does.

Supporting ad-hoc polymorphism with pattern matching doesn’t mean that inheritance hierarchies and virtual methods are wrong — it’s just that this is not the only useful way to attack a problem. As we saw with the eval() method, sometimes an operation is an ideal candidate for including in the hierarchy. But sometimes this isn’t the right choice, or even possible — such as when an endpoint listens for a variety of messages, and not all message types have a common supertype (or even come from the same library.) In these cases, pattern matching offers clean and simple data-driven polymorphism.

It is sometimes said that many “design patterns” are workarounds for features missing from the language. While this claim may be too facile, it is reasonably accurate in the case of Visitor — if your language has sufficiently powerful pattern matching, the Visitor pattern is almost completely unnecessary.

Exhaustiveness

In the expression form of switch, we evaluate exactly one arm of the switch, which becomes the value of the switch expression itself. This means that there must be at least one arm that applies to any input — otherwise the value of the switch expression might be undefined. If the switch has a default arm, there’s no problem. For switches over enum, where all enum constants are handled, it is often irritating to have to write a default clause that we expect will never be taken; worse, if we write this default clause, we lose the ability to have the compiler verify that we have exhaustively enumerated the cases.

Similarly, for many hierarchies where we might apply pattern matching, such as our Node classes, we would be annoyed to have to include a never-taken default arm when we know we’ve listed all the subtypes. If we could express that the only subtypes of Node are IntNode, AddNode, MulNode, and NegNode, the compiler could use this information to verify that a switch over these types is exhaustive.

There’s an age-old technique we can apply here: hierarchy sealing. Suppose we declare our Node type to be sealed; this means that only the subtypes that are co-compiled with it (often from a single compilation unit) can extend it:

sealed interface Node { }

Sealing is a generalization of finality; where a final type has no subtypes, a sealed type can have no subtypes beyond a fixed set of co-declared subtypes. The details of sealing will be discussed separately.

Patterns and type inference

Just as we sometimes want to let the compiler infer the type of a local variable for us using var rather than spell the type out explicitly, we may wish to do the same thing with type patterns. While it might be useful to explicitly use type patterns in our AddNode example (and the compiler can optimize them away based on static type information, as we’ve seen), we could also use a nested var pattern instead of the nested type patterns. A var pattern uses type inference to map to an equivalent type pattern (effectively matching anything), and binds its target to a pattern variable of the inferred type. A pattern that matches anything may sound silly — and it is silly in itself — but is very useful as a nested pattern. We can transform our eval method into:

int eval(Node n) {
    return switch(n) {
        case IntNode(var i) -> i;
        case NegNode(var n) -> -eval(n);
        case AddNode(var left, var right) -> eval(left) + eval(right);
        case MulNode(var left, var right) -> eval(left) * eval(right);
    };
}

This version is equivalent to the manifestly typed version — as with the use of var in local variable declarations, the compiler merely infers the correct type for us. As with local variables, the choice of whether to use a nested type pattern or a nested var pattern is solely one of whether the manifest type adds to or distracts from readability and maintainability.

Nesting constant patterns

Constant patterns are useful on their own (all existing switch statements today use the equivalent of constant patterns), but they are also useful as nested patterns. For example, suppose we want to optimize some special cases in our evaluator, such as “zero times anything is zero”. In this case, we don’t even need to evaluate the other subtree.

If IntNode(var i) matches any IntNode, the nested pattern IntNode(0) matches an IntNode that holds a zero value. (The 0 here is a constant pattern.) In this case, we first test the target to see if it is an IntNode, and if so, we extract its numeric payload, and then further try to match that against the constant pattern 0. We can go as deep as we like; we can match against a MulNode whose left component is an IntNode containing zero, and we could optimize away evaluation of both subtrees in this case:

int eval(Node n) {
    return switch(n) {
        case IntNode(var i) -> i;
        case NegNode(var n) -> -eval(n);
        case AddNode(var left, var right) -> eval(left) + eval(right);
        case MulNode(IntNode(0), var right),
             MulNode(var left, IntNode(0)) -> 0;
        case MulNode(var left, var right) -> eval(left) * eval(right);
    };
}

The first MulNode pattern is nested three deep, and it only matches if all the levels match: first we test if the matchee is a MulNode, then we test if the MulNode’s left component is an IntNode; then we test whether that IntNode’s integer component is zero. If our target matches this complex pattern, we know we can simplify the MulNode to zero. Otherwise, we proceed to the next case, which matches any MulNode, which recursively evaluates the left and right subnodes as before.

Expressing this with visitors would be circuitous and much harder to read; even though a visitor will handle the outermost layer easily, we would then have to handle the inner layers either with explicit conditional logic, or with more layers of visitors. The ability to compose patterns in this way allows us to specify complicated matching conditions clearly and concisely, making the code easier to read and less error-prone.

Any patterns

Just as the var pattern matches anything and binds its target to that, the _ pattern matches anything — and binds nothing. Again, this is not terribly useful as a standalone pattern, but is useful as a way of saying “I don’t care about this component.” If a subcomponent is not relevant to the matching, we can make this explicit (and prevent ourselves from accidentally accessing it) by using a _ pattern. For example, we can further rewrite the “multiply by zero” case from the above example using a _ pattern:

case MulNode(IntNode(0), _), MulNode(_, IntNode(0)) -> 0;

Which says that the other component is irrelevant to the matching logic, and doesn’t need to be given a name — or even be extracted.

Static patterns

Deconstruction patterns are implemented by class members that are analogous to constructors, but which run in reverse, taking an instance and destructuring it into a sequence of components. Just as classes can have static factories as well as constructors, it is also reasonable to have static patterns. And just as static factories are an alternate way to create objects, static patterns can perform the equivalent of deconstruction patterns for types that do not expose their constructors.

For example, Optional is constructed with factory methods Optional.of(v) and Optional.empty(). We can expose static patterns accordingly that operate on Optional values, and extract the relevant state:

switch (opt) {
    case Optional.empty(): ...
    case Optional.of(var v): ...
}

The syntactic similarly between how the object is constructed and how it is destructured is again not accidental. (An obvious question is whether instance patterns make sense as well; they do, and they provide API designers with some better choices than we currently have. Static and instance patterns will be covered in greater depth in a separate document.)

Summary of patterns and control flow constructs

We’ve now seen several kinds of patterns:

• Constant patterns, which test their target for equality with a constant;
• Type patterns, which perform an instanceof test, cast the target, and bind it to a pattern variable;
• Deconstruction patterns, which perform an instanceof test, cast the target, destructure the target, and recursively match the components to subpatterns;
• Method patterns, which are more general than deconstruction patterns;
• Var patterns, which match anything and bind their target;
• The any pattern _, which matches anything and binds nothing.

We’ve also seen several contexts in which patterns can be used:

• A switch statement or expresion;
• A instanceof predicate;
• A match statement.

Other possible kinds of patterns, such as collection patterns, could be added later. Similarly, other linguistic constructs, such as catch, could potentially support pattern matching in the future.