lib/match/match.x

Pattern matching and transformation utilities for lists.

Primary API

Functions

x2c_match_initialize

void x2c_match_initialize(void)

Registers process-wide Match cleanup exactly once. Repeated calls have no effect. Failure of the native once primitive writes a diagnostic and aborts the process.

Raises: <alloc-fail> or <size-limit> while registering the shutdown hook.

Source: lib/match/sites.x:275

x2c_match_site_match

List x2c_match_site_match(MatchCaptureSite *site, List input, Var pat)

Returns bindings through one compiler-owned site, or nil on a miss. Results follow List.match.

Source: lib/match/sites.x:201

x2c_match_site_match_replace

List x2c_match_site_match_replace( MatchCaptureSite *site, List input, Var pat, Var template)

Returns the List replacement through one compiler-owned site. Results follow List.match_replace.

Source: lib/match/sites.x:244

x2c_match_site_search

List x2c_match_site_search(MatchCaptureSite *site, List input, Var pat)

Returns every matching subtree through one compiler-owned site. Results follow List.search.

Source: lib/match/sites.x:222

x2c_match_site_search_replace

List x2c_match_site_search_replace( MatchCaptureSite *site, List input, Var pat, Var template)

Replaces every match through one compiler-owned site. Results follow List.search_replace.

Source: lib/match/sites.x:255

x2c_match_site_try_match

int x2c_match_site_try_match( MatchCaptureSite *site, List input, Var pat, List *out_bindings)

Matches through one compiler-owned site, writing bindings on success. Results follow List.try_match.

Source: lib/match/sites.x:190

x2c_match_site_try_match_replace

int x2c_match_site_try_match_replace( MatchCaptureSite *site, List input, Var pat, Var template, Var *out)

Match-replaces through one compiler-owned site. Results follow List.try_match_replace.

Source: lib/match/sites.x:233

x2c_match_site_try_search

int x2c_match_site_try_search( MatchCaptureSite *site, List input, Var pat, Var *out_match, List *out_bindings)

Searches through one compiler-owned site, writing the first match. Results follow List.try_search.

Source: lib/match/sites.x:210

List

List.replace

meta native List List.replace(List template, List bindings)

Replaces named binders in template according to bindings. A sequence binder in list-head position splices its captured List; !quote removes itself and leaves its operand literal. Missing binders are retained. A null template returns nil, and null bindings return template unchanged. New structure follows the module pool-chain lifetime above.

Raises: <alloc-fail> while constructing replacement Lists.

Source: lib/match/templates.x:72

List.search

List List.search(List input, Var pat)

Returns every matching subtree of input with its bindings. Each result begins with (* matched) followed by reverse-slot-order binder pairs. Traversal visits a List’s head, then tail, then the List itself; results are prepended and therefore returned in reverse visitation order. Explicit nil values are nodes, but a proper List’s terminal cdr is not. A miss, malformed pattern, or machine error returns nil.

Raises: <size-limit> for an ineligible pattern, or <alloc-fail> while preparing or constructing results.

Source: lib/match/operations.x:78

List.search_replace

List List.search_replace(List input, Var pat, Var template)

Replaces every matching subtree in input from the leaves upward. Children are rewritten before their reconstructed containing List is tested. A miss, malformed pattern, or machine error returns input unchanged. New structure follows the module pool-chain lifetime above.

Raises: <size-limit> for an ineligible pattern, or <alloc-fail> while preparing, traversing, or replacing.

Source: lib/match/operations.x:102

List.try_match

int List.try_match(List input, Var pat, List &?out_bindings)

Matches input against pat, writing bindings on success. Returns 1 on a match and writes a reverse-slot-order association List, or returns 0 and leaves out_bindings unchanged. A successful binder-free match writes nil. A null output pointer returns 0.

Raises: <size-limit> for an ineligible pattern, or <alloc-fail> while preparing, materializing captures, or publishing bindings.

Source: lib/match/operations.x:32

List.try_match_replace

int List.try_match_replace(List input, Var pat, Var template, Var &?out)

Matches input and writes the instantiated template on success. The output may be any Var, including typed nil or a scalar. A template that is one binder the match left unbound, such as the binder of an !or alternative another alternative satisfied, writes that binder. Returns 0 for a miss, malformed pattern, invalid output, or machine error and leaves out unchanged.

Raises: <size-limit> for an ineligible pattern, or <alloc-fail> while preparing, materializing, or replacing.

Source: lib/match/operations.x:54

List.try_search

int List.try_search( List input, Var pat, Var &?out_match, List &?out_bindings)

Searches input for pat, writing the first match and bindings. The depth-first order is head, tail, then containing List, with the same explicit-nil rule as List.search. Returns 1 on success; otherwise returns 0 and leaves both outputs unchanged. Either null output returns 0.

Raises: the same causes as List.search.

Source: lib/match/operations.x:90

MatchPlan

MatchPlan.admits

int MatchPlan.admits(MatchPlan plan, Var input, Var (*view)(Var))

Reports whether input, seen through view when one is given, begins as one of the keys of prepared plan requires. A plan without keys admits every input, and a refused input is one the plan cannot match.

Source: lib/match/execution.x:78

Advanced and interop API

Functions

x2c_match_pattern_retainable

int x2c_match_pattern_retainable(Var pattern)

Reports whether a compiler-owned site can retain pattern. A site borrows its pattern’s values for the life of the process, so only a graph of values that outlives every call qualifies.

Source: lib/match/sites.x:162

x2c_match_site_prepare

MatchPlan x2c_match_site_prepare(MatchCaptureSite *site, Var pattern)

Returns the process-lifetime plan for one compiler-owned site. The first retainable pattern binds the site permanently. A pattern the site cannot retain returns NULL; an ineligible one returns its fenced plan so the caller can name the fence.

Raises: <alloc-fail> while publishing.

Source: lib/match/sites.x:171

x2c_match_site_try_capture

int x2c_match_site_try_capture( MatchCaptureSite *site, List input, Var pattern, MatchCaptureBuffer *captures)

Matches through one compiler-owned static capture site. Its first admissible pattern permanently binds the site; direct C callers must not reuse one site for different patterns. site must be zero-initialized static storage and pattern must contain only values that remain live through Match shutdown. A pattern the site cannot retain takes the ordinary runtime route, with the same result, and the site records that refusal once, so later calls take that route directly. Returns 1 only after atomically committing captures; invalid arguments, malformed patterns, misses, and machine errors return 0 without changing it.

Raises: <size-limit> for an ineligible pattern, or <alloc-fail> while publishing or matching.

Source: lib/match/sites.x:80

x2c_match_try_capture

int x2c_match_try_capture( List input, Var pattern, MatchCaptureBuffer *captures)

Matches a runtime pattern into positional storage. The active default cache prepares the pattern on its first use and reuses that program afterward. Returns 1 on success and 0 on a miss, malformed pattern, invalid buffer, cache pressure, or machine error. A nonnull buffer is written atomically as described by MatchCaptureBuffer; NULL returns 0.

Raises: <size-limit> for an ineligible pattern, or <alloc-fail> while preparing or matching.

Source: lib/match/operations.x:19

List

List.match

List List.match(List input, Var pat)

Returns bindings when input matches pat, or nil on a miss. A binder-free success returns the nonnull %(()) sentinel with no associations. Binding order and failures follow List.try_match.

Source: lib/match/operations.x:39

List.match_replace

meta native List List.match_replace(List input, Var pat, Var template)

Returns the List replacement when input matches pat. A miss returns input unchanged. A successful scalar replacement cannot inhabit the List result and returns nil. Matching and replacement failures follow List.try_match_replace.

Source: lib/match/operations.x:63

Var

Var.is_atom_binder

meta native int Var.is_atom_binder(Var atom)

Reports whether atom is a valid named or anonymous ? binder.

Source: lib/match/layout.x:32

Var.is_binder

meta native int Var.is_binder(Var atom)

Reports whether atom is either valid Match binder form.

Source: lib/match/layout.x:38

Var.is_list_binder

meta native int Var.is_list_binder(Var atom)

Reports whether atom is a valid named or anonymous * binder.

Source: lib/match/layout.x:35

Var.is_match_op

meta native int Var.is_match_op(Var atom)

Reports whether atom is a compact built-in Match guard operator.

Source: lib/match/layout.x:41

Runtime-internal callables

These callables connect runtime translation units. They are documented for source readers but are not supported as user API.

MatchCaptureBuffer

MatchCaptureBuffer.has

int MatchCaptureBuffer.has(MatchCaptureBuffer *m, int index)

Reports whether a committed capture slot is present. A null buffer or an index outside its capacity or Match’s binder limit returns false. Presence is independent of the captured Var value.

Source: lib/match/layout.x:334

MatchCaptureLayout

MatchCaptureLayout.analyze

MatchCaptureLayout MatchCaptureLayout.analyze(Var pattern)

Analyzes one Match pattern into its canonical positional layout. Distinct named binders receive slots in lexical preorder. !quote is opaque; alternatives contribute possible binders, while only binders in every alternative are definite. The caller owns the returned layout, including when status is <malformed>.

Raises: <alloc-fail> while normalizing or allocating the layout.

Source: lib/match/layout.x:130

MatchCaptureLayout.definite_list

List MatchCaptureLayout.definite_list(MatchCaptureLayout layout)

Returns definite binders in canonical positional order. A null layout or no definite binders returns nil. The canonical result follows the module pool-chain lifetime above.

Raises: <alloc-fail> while constructing the List.

Source: lib/match/layout.x:304

MatchCaptureLayout.free

void MatchCaptureLayout.free(MatchCaptureLayout layout)

Releases one canonical Match capture layout. A null layout is ignored; every alias is invalid afterward.

Source: lib/match/layout.x:295

MatchCaptureLayout.index

int MatchCaptureLayout.index(MatchCaptureLayout layout, Atom binder)

Returns the canonical slot for binder, or -1 when it is absent. A null layout returns -1. Comparison uses exact Atom identity.

Source: lib/match/layout.x:327

MatchCaptureLayout.possible_list

List MatchCaptureLayout.possible_list(MatchCaptureLayout layout)

Returns possible binders in canonical positional order. A null layout or no possible binders returns nil. The canonical result follows the module pool-chain lifetime above.

Raises: <alloc-fail> while constructing the List.

Source: lib/match/layout.x:312

MatchPlan

MatchPlan.borrowable

int MatchPlan.borrowable(Var pattern, int permanent_lists)

Reports whether a plan may borrow pattern by its canonical identity. permanent_lists requires every List in it to belong to the outermost pool, as a plan kept for the life of the process does. Without it, a List that is canonical now qualifies until its pool level is released.

Source: lib/match/sites.x:49

MatchPlan.execute

int MatchPlan.execute( MatchPlan plan, Var input, List &?out_bindings, MachineStats &?stats)

Executes plan against input and publishes association bindings. Returns 1 and writes out_bindings on a match, 0 on a miss, and -1 for a null or malformed plan, null output, or machine error. Failure leaves the output unchanged. A binder-free success writes nil; other bindings are in reverse canonical slot order. stats, when nonnull, receives increments and is not initialized here.

Raises: <size-limit> for an ineligible plan, or <alloc-fail> while materializing or publishing bindings.

Source: lib/match/execution.x:158

MatchPlan.execute_capture

int MatchPlan.execute_capture( MatchPlan m, Var input, MatchCaptureBuffer &?captures, MachineStats &?stats)

Executes a prepared plan into caller-owned positional storage. Returns 1 on a match, 0 on a miss, and -1 for a null or malformed plan, an invalid buffer, or a machine error. Only success replaces present and the indicated values; all other results leave the buffer unchanged. stats, when nonnull, receives increments and is not initialized here.

Raises: <size-limit> for an ineligible plan, or <alloc-fail> while materializing captures.

Source: lib/match/execution.x:48

MatchPlan.raise_ineligible

void MatchPlan.raise_ineligible(const char *reason, const char *owner)

Raises the fence an ineligible plan crossed, naming owner. This is the one place an ineligible pattern is reported. Such a pattern compiles to no program, so answering “no match” would be wrong and no caller could tell it from a real miss. reason is the plan’s static category string.

Raises: <size-limit> with operation and the fence.

Source: lib/match/execution.x:15

MatchPlan.search

int MatchPlan.search(MatchPlan plan, List input, List &?out_results)

Writes all matches of plan within input to out_results. Each result has the shape documented by List.search and the completed List is in reverse visitation order. Returns 1 after a complete traversal, including when it writes nil for no matches; returns -1 and leaves the output unchanged for an unusable plan, null output, or machine error.

Raises: <size-limit> for an ineligible plan, or <alloc-fail> while constructing results.

Source: lib/match/traversal.x:76

MatchPlan.search_replace

int MatchPlan.search_replace( MatchPlan plan, List input, Var template, List &?out)

Replaces every match of plan from the leaves upward. Returns 1 and writes the completed List even when nothing matched. Returns -1 and leaves out unchanged for an unusable plan, null output, or machine error. Children are replaced before their containing List is tested.

Raises: <size-limit> for an ineligible plan, or <alloc-fail> while traversing or replacing.

Source: lib/match/traversal.x:100

MatchPlan.try_capture

int MatchPlan.try_capture( MatchPlan plan, List input, MatchCaptureBuffer &?captures)

Executes a prepared List match into caller-owned positional storage. This is MatchPlan.execute_capture without statistics and has the same results, atomicity, and failures.

Source: lib/match/execution.x:61

MatchPlan.try_match

int MatchPlan.try_match(MatchPlan plan, List input, List &?out_bindings)

Executes prepared plan against input, writing bindings on success. This is MatchPlan.execute without statistics and has the same status, output atomicity, ordering, and failures.

Source: lib/match/execution.x:174

MatchPlan.try_match_replace

int MatchPlan.try_match_replace( MatchPlan plan, List input, Var template, Var &?out)

Executes plan and writes the instantiated template on success. Returns 1 after writing any Var result, 0 on a miss, and -1 for an unusable plan, null output, or machine error. Non-success leaves out unchanged.

Raises: <size-limit> for an ineligible plan, or <alloc-fail> while materializing captures or replacing.

Source: lib/match/templates.x:30

MatchPlan.try_search

int MatchPlan.try_search( MatchPlan plan, List input, Var &?out_match, List &?out_bindings)

Searches input with plan, writing the first match and bindings. Traversal is depth-first head, tail, then containing List. Returns 1 on a match, 0 on a miss, and -1 for an unusable plan, invalid outputs, or a machine error. Unless it returns 1, both outputs remain unchanged.

Raises: <size-limit> for an ineligible plan, or <alloc-fail> while materializing or publishing bindings.

Source: lib/match/traversal.x:45

Public types

MatchCaptureBuffer

typedef struct MatchCaptureBuffer { Var *values; unsigned long present; int capacity; } MatchCaptureBuffer

Supplies caller-owned positional storage for one Match invocation. values has capacity elements. On success present identifies the elements Match wrote; presence is separate from a captured void value. A miss or error leaves values and present unchanged. Captured values are borrowed and keep their ordinary Var, List, and pool lifetimes.

Source: lib/match/match.x:42

MatchCaptureLayout

typedef struct MatchCaptureLayout { Atom *binders; Var normalized; unsigned long definite, possible; int binder_count, Symbol status, const char *reason; } *MatchCaptureLayout

Describes the canonical binder slots and preparation status of a pattern. binders points into the layout allocation and lists each distinct named binder in lexical preorder. definite and possible select those slots. normalized and the binder Atoms are borrowed canonical values. The caller owns the layout returned by MatchCaptureLayout.analyze and must free it before those values or its allocating Scope expire.

Source: lib/match/match.x:29

MatchCaptureSite

typedef struct MatchCaptureSite { MatchPlan plan; int refused; } MatchCaptureSite

Stores the process-lifetime plan for one compiler-emitted Match site. The object must be zero-initialized static storage. Its first admissible pattern binds it permanently; Match shutdown frees the plan and clears the site. Direct callers must not reuse a site for another pattern.

Source: lib/match/match.x:81

MatchKey

typedef struct MatchKey { Var head, inner; int index, nested; } MatchKey

Describes one way an input a plan matches can begin: its first element equals head and, when index is nonzero, its element at index equals inner, or is a List whose first element does when nested is set. Both values are borrowed pattern constants.

Source: lib/match/match.x:53

MatchPlan

typedef struct MatchPlan { MachineProgram program; MatchCaptureLayout layout; Symbol status, const char *reason; int key_count, key_bits; MatchKey keys[MATCH_KEY_MAX]; } *MatchPlan

Holds one reusable immutable compiled Match pattern. A prepared plan owns program and layout; malformed and ineligible plans have no executable program and retain their categorized status and static reason. A prepared plan whose pattern fixes how a matching input begins lists the keys it may begin with; key_bits says that raw bits compare them. Pattern constants are borrowed, so the caller must free the plan before their canonical pools or other owners expire.

Source: lib/match/match.x:68

Design notes

Match owns the pattern vocabulary, capture layouts, and the execution of plans that match-plan.x prepares and match-cache.x retains. Core matching runs only prepared plans; unittest/match-recursive.x is the reference matcher of the differential tests. An invocation commits captures to caller-owned storage only after the whole match succeeds.

Association-List results are published from committed captures. New Lists canonicalize through the active pool chain; a result may belong to an ancestor and lives until its owning pool is released.

Tests and examples

make verify (unittest/test-match.x) and make examples (match-nested).