Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

x2c

Pattern Matching

A match statement takes a List apart by its shape. You write a pattern that looks like the data and name the pieces you need. The names become ordinary local variables. One pattern replaces a chain of List_car, List_cdr, length checks, and tag tests.

The match statement and the runtime matcher share one pattern language. The exhaustive rules are in the language reference.

The match statement

A match has a subject in parentheses and a sequence of arms. Each arm is case pattern: followed by one statement, and an optional final default: arm runs when nothing matched.

List reply = %(status ok 200);
match (reply) {
  case %(status ok ?code):
    printf("ok with code %d\n", code);
  case %(status ?state ?code):
    printf("%s with code %d\n", state, code);
  default:
    printf("not a status reply\n");
}

The subject is evaluated once. Arms are then tried in source order, and the first one that matches runs. The second arm above would also have matched, but it is never tried. If no arm matches and there is no default, the whole statement does nothing.

An arm’s body is a single statement, so use braces when you want several. Ordinary structural patterns use %(...) List literals. Compile-time matching can also use Macro values to recognize the code a macro constructs.

For a single arm you may drop the outer braces, the same way you can with if:

List value = %(one);
match (value)
  case %(one):
    printf("no braces needed for a single arm\n");

Arm order is also cost order, so put cheap, common shapes first.

Typed captures and expression guards

Write ?(typename name) to capture a value as a native typed local. The pattern tests the value’s Var tag; a different tag fails the pattern without converting the value. The tag test precedes the native local declaration. The supported types are the same as for value is typename. The ?( opener must be adjacent; ? (String text) remains a wildcard followed by a sublist pattern.

Inside ?(, typename uses ordinary source type syntax, so write ?(String text) or ?(List payload). This is an exception to the pattern’s bare-spelling rule. The compiler represents a named type such as String with the type List %("String"); %(String) instead contains an Atom. See type syntax in macro values.

Typedefs use their underlying Var tag. Since Type is a typedef for List, ?(Type type) tests for a List payload. It does not check whether the List contains valid type syntax.

List reply = %(message "ready");
match (reply) {
  case %(message ?(String text)) if (text.len() > 3):
    printf("long message: %s\n", text.str());
  case %(message ?(String text)):
    printf("short message: %s\n", text.str());
}

An optional if (expression) before the colon runs after the pattern matches, with its captures in scope. A false guard tries the next arm; errors propagate normally. The guard uses ordinary expression truth rules.

A typed name has the same type throughout its arm, including other occurrences written as ?name and occurrences in alternative patterns. Repeated names still require equal values. !quote remains opaque, and the existing rule that each binder must be assigned in every alternative still applies. Explicit (!is ?name type string) keeps name as a Var.

The shorthand lowers to the existing !is pattern predicate and ordinary typed local declarations. An expression guard lowers to an ordinary if; both forms match exactly as the explicit patterns do.

The pattern vocabulary

Patterns are written in List-literal notation, which is described in strings, lists, arrays, and maps.

Literals

A bare spelling in a pattern is an exact Atom that must appear in that position. Strings compare by value. A number matches only a number of the same type and value, so %(3) matches 3 but not 3L, 3.0, or 3u, and %(?x ?x) does not match %(3 3L). This differs from == on two numbers, which follows C and calls 3 and 3L equal. $name or ${expression} unquotes a value to compare against by the same rule. A pattern can require a match with something computed at run time.

Wildcards

? matches exactly one element and discards it. * matches any number of elements and discards them.

Binders

?name matches one element and binds it; *name matches a run of elements and binds them as a List.

List command = %(move 10 20 fast quiet);
match (command) {
  case %(move ?x ?y *flags):
    printf("to %d,%d with %d flag(s)\n",
           x, y, flags.len());
}
match (command) {
  case %(move ? ? *): printf("some move\n");
}

A ?name binder is a Var; a *name binder is a List. A *name takes the leftmost split that lets the rest of the pattern succeed, and matching a *name against typed nil binds an empty List rather than failing.

Repeating a binder name in one pattern means “these must be equal”: %(?x ?x) matches %(same same) and rejects %(other same).

Binder names follow the C identifier grammar, [A-Za-z_][A-Za-z0-9_]*. A sigil followed by anything else is a mistake, and the compiler reports it with a position. %(node ?bad-name) reports invalid match binder name.

Nested shapes

A parenthesized group inside a pattern is a sublist, so nesting states nested structure without any index arithmetic:

List tree = %(tree (node 3 4) leaf);
match (tree) {
  case %(tree (node ?a ?b) ?rest):
    printf("%d\n", a * b);
}
Symbol wanted = <leaf>;
match (tree) {
  case %(tree ? $wanted): printf("ends with the wanted tag\n");
}

Guards

Six guard operators turn a position in a pattern into a test. Each is written as a sublist headed by the operator.

(!or a b ...) succeeds when any alternative matches, (!and a b ...) when all of them do, and (!not a b ...) when none of them do:

List reply = %(status created 201);
match (reply) {
  case %(status (!or ok created) ?code):
    printf("success %d\n", code);
  case %(status (!not ok) ?code):
    printf("failure %d\n", code);
}
match (%(color green)) {
  case %(color (!and (!not red) (!not blue))):
    printf("neither red nor blue\n");
}

(!set PATTERN ...) is membership: it succeeds when any member matches. (!quote PATTERN) compares the input to the pattern as literal data, with no binder interpretation inside it. (!is ...) is the type and category predicate: (!is type string) checks a Var tag, and (!is atom), (!is binder), (!is op), (!is var binder), and (!is list binder) check the named category.

Every guard except !quote accepts an optional leading binder, which captures the slice of input the guard checked. A leading binder needs at least one operand after it, so (!not ?y) tests ?y rather than capturing it, and (!set ?w a b) captures the a-or-b membership:

match (%(node 7 8)) {
  case %(!set ?whole (node ?a ?b)):
    printf("%s holds %d and %d\n",
           whole, a, b);
}
match (%(key "abc")) {
  case %(key (!is type string)):
    printf("a String payload\n");
}
match (%(key 42)) {
  case %(key (!is ?found atom)):
    printf("an atom: %s\n", found);
}
match (%(tag (a b))) {
  case %(tag (!quote (a b))):
    printf("literally (a b)\n");
}

Runtime-built patterns may put an interned operator Symbol in the head position. List.match(input, %($op ...)) applies the same operator semantics as its literal spelling, and the runtime operator suite checks !or, !not, !quote, !is, and nested dynamic forms. Source match arms should spell operators literally so the compiler can determine which named binders are available to the arm body.

The ?binder?, *binder?, and !op? spellings are reserved in !is operand positions. They are not named binders and do not execute a predicate. Use the (!is ...) forms above.

Where binders live

Each arm declares its binders as local variables before its body is parsed. A ?name has type Var, a *name has type List, and either works with method syntax. A binder is visible only inside the arm that introduced it, and it shadows any outer name for the length of that arm:

Var value = 99;
List input = %(pair 1 2);
match (input) {
  case %(pair ?value ?other):
    printf("inside the arm value is %d\n", value);
}
printf("outside the match value is still %d\n", value);

The same binder name can appear in two different arms, and a binder does not exist after the match statement ends. There is no “result of the match” to read afterwards; assign to a variable you declared outside if you need to carry something out.

Method syntax follows those types:

match (%(node (a b))) {
  case %(node ?child):
    printf("%d\n", child.list().len());
}

Named binders must also be definitely assigned whenever their arm matches. Binders inside the operands of !not are never available, though its leading binder is, and a binder under !or or membership-style !set must occur in every alternative. !quote is opaque literal data. The compiler diagnoses a maybe-bound name at the pattern.

Lists, Var, and nil

The subject of a match is a List, so the shapes you can match are List shapes. Arrays, Maps, and Strings are not match subjects.

A Var subject works because the compiler inserts the conversion to List for you. A Var whose tag is not <list> is not a List: it matches no List pattern, not even %() or %(*rest), and reaches the default arm when there is one. A Var holding an empty List still matches %(). See values and Var for the tag rules and symbols and atoms for what a bare pattern spelling means.

Nil is typed List data, not the absence of a List. A null List is a legal subject, %(*rest) matches it and binds an empty List, and an explicitly stored empty List inside a larger structure is a visible node that search can find. What is not a node is the implicit terminal cdr of a proper List.

A match statement binds captured values to arm-local variables. Captured values keep their ordinary lifetime rules. A pattern built from literals, nested Lists, unique ? binders, typed or not, and a final * or *name is tested in place: the compiler emits direct checks and captures. Other patterns use the runtime matcher with the same semantics.

break and continue inside an arm

break in an arm body exits the match, not any enclosing loop. continue skips to the next iteration of the enclosing loop:

List items = %((skip) (keep) (skip));
int seen = 0, kept = 0;
foreach(Var item, items) {
  seen++;
  match (item) {
    case %(skip): continue;
    case %(keep): break;
  }
  kept++;
}
printf("seen %d, kept %d\n", seen, kept);

That prints seen 3, kept 1: the two skip items jump past kept++, while the keep item leaves the match and falls through to it.

The runtime matcher

The runtime matcher exposes the same pattern language as List methods. Use it when the pattern is data, when you need the bindings as a value, or when you are rewriting rather than dispatching.

try_match reports success separately from the bindings, and leaves its output pointer untouched on failure. match_replace matches once and expands a template from the bindings:

List input = %(define x 10);
List bindings = NULL;
if (input.try_match(%(define ?name ?value), bindings))
  printf("%s = %d\n",
         bindings.assoc(<?name>),
         bindings.assoc(<?value>));
List rewritten = input.match_replace(%(define ?name ?value),
                                     %(assign ?name ?value));
printf("%s\n", rewritten.str());

Bindings are an association List keyed by the binder Atom, so you read them with assoc and the same spelling you wrote in the pattern: <?name> for a ? binder and <*rest> for a * binder. These are standalone Symbol literals, outside the List syntax that accepts bare Atoms.

The search family walks a whole structure instead of matching at the root. try_search returns the first depth-first hit, search collects every hit, and search_replace rewrites all of them:

List tree = %(root (item 1) (wrapper (item 2)));
Var node = void;
List bindings = NULL;
if (tree.try_search(%(item ?id), node, bindings))
  printf("first id %d\n", bindings.assoc(<?id>));
printf("%d matches in all\n", tree.search(%(item ?id)).len());
printf("%s\n", tree.search_replace(%(item ?id),
                                    %(entry ?id)).str());

The try_ forms report success separately from their results. match returns bindings, %(()) for a binder-free success, or nil on a miss. match_replace returns the original input on a miss and nil for a successful scalar replacement. search returns its results in reverse visitation order, so do not read the list as document order. The standard library overview has the full API list.

Each of these operations runs a pattern program rather than the pattern value. When the pattern argument is a literal written at the call, the compiler gives that call its own program, prepared once for the life of the process. A pattern computed at run time – built with cons, interpolated with $, or received as a parameter – goes through a plan cache instead: the first call prepares its program and later calls with the same pattern reuse it, so a loop over one computed pattern pays a single preparation. The cache is local to the enclosing Context and holds a bounded number of recent patterns, so a loop that alternates between more distinct patterns than it holds prepares them again; hoist the pattern out of the loop when that matters. The arms of a filtered catch get their own per-site program, like a literal.

Use match when the data’s structure determines what to do. Literal elements specify what must be present; ?name and *tail name the parts you will use. Nested patterns describe sublists, and default handles the remaining cases. A pattern made entirely of wildcards often calls for iteration instead.

A loop can find candidate values, then match each candidate:

List program = %((set x 1) (call print x) (set y 2));
int assignments = 0;
foreach(Var node, program) {
  match (node) {
    case %(set ?name ?value):
      assignments++;
    case %(call ?fn *args):
      printf("call to %s\n", fn);
  }
}
printf("%d assignment(s)\n", assignments);

Use a plain if chain instead when there is no shape to state: one tag test, one length check, one comparison. A match with a single arm whose pattern is %(?x) is no clearer than the test it replaces. Use iteration when order, accumulated state, or early exit matters. A loop and a pattern can each do part of the work.

A plain binder does not check the captured value’s type. ?value captures whatever is in that position. When the arm’s body depends on the type, use a typed capture such as ?(String value), which fails the arm on a tag mismatch.

Limitations

default must be the last arm. The compiler diagnoses a later arm. A final default runs only when every earlier case failed. Each branch of a conditional group may end with its own default, as long as no arm follows the group.

A case pattern must be a %(...) List literal. The runtime matcher accepts a standalone Symbol pattern such as <?whole>, but the statement form does not. The compiler rejects any other case pattern with a positioned x2c diagnostic before generating C.

Source guard operators must be literal. Runtime-built patterns may interpolate an interned operator Symbol, but a source arm needs a literal operator so definite binder assignment can be checked. The ?binder? family is reserved and is not a working predicate.

The generated Match reference lists the runtime operations by API tier.