lib/match.x

Pattern matching and transformation utilities for lists.

Primary API

Functions

x2c_match_thread_release

void x2c_match_thread_release(void)

Disposes this thread’s default Match plan cache. x2c_thread_state_release calls it before Scope releases the Scope that holds that cache; a thread that never matched has no cache and nothing happens. All default-cache leases and Context states must already be closed.

Raises: <bad-state> when a lease remains active.

Source: lib/match.x:2258

List

List.replace

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.x:641

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, cache pressure, or machine error returns nil.

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

Source: lib/match.x:807

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, cache pressure, 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.x:832

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.x:600

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. Returns 0 for a miss, malformed pattern, invalid output, cache pressure, 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.x:697

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.x:820

Advanced and interop API

Functions

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. Returns 1 only after atomically committing captures; invalid arguments, malformed or inadmissible 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.x:154

x2c_match_try_capture

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

Matches through the active default cache into positional storage. 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.x:128

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 %(()) compatibility sentinel with no associations. Binding order and failures follow List.try_match.

Source: lib/match.x:607

List.match_replace

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.x:707

Var

Var.is_atom_binder

int Var.is_atom_binder(Var atom)

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

Raises: <alloc-fail> while decoding a compact Atom.

Source: lib/match.x:263

Var.is_binder

int Var.is_binder(Var atom)

Reports whether atom is either valid Match binder form.

Raises: <alloc-fail> while decoding a compact Atom.

Source: lib/match.x:273

Var.is_list_binder

int Var.is_list_binder(Var atom)

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

Raises: <alloc-fail> while decoding a compact Atom.

Source: lib/match.x:268

Var.is_match_op

int Var.is_match_op(Var atom)

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

Source: lib/match.x:276

Runtime-internal callables

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

MatchCache

MatchCache.acquire

int MatchCache.acquire(MatchCache m, Var pattern, MatchLease *lease)

Acquires a lease for a cached prepared pattern. cache and lease must be nonnull. The lease is initialized on every returning path. An admitted pattern reuses or creates an LRU entry; an inadmissible pattern gets a transient plan owned by the lease. Returns the plan’s MachinePrepare status, or MATCH_CACHE_PRESSURE when every entry is pinned. Release the lease after any returned status; releasing the inactive pressure lease is a no-op.

Raises: <size-limit> when pattern exceeds a lowering limit. Such a pattern compiles to no program, so it is never cached and never leased. <alloc-fail> may also be raised while preparing or growing storage.

Source: lib/match.x:1964

MatchCache.context_close

void MatchCache.context_close(void *token)

Disposes and removes the top Context’s default Match cache. A null token is ignored. Successful close restores the previous default; the token storage remains owned by its Context Scope.

Raises: <bad-state> when token is not the top state or its cache has an active lease. The failure leaves the state installed.

Source: lib/match.x:2294

MatchCache.context_open

void *MatchCache.context_open(void)

Opens one Context-local default Match-cache state. The returned opaque token becomes the top of a thread-local LIFO stack; its cache is created only on first use. The token is allocated in the active Scope and must be passed to MatchCache.context_close before that Scope ends.

Raises: <alloc-fail> when the state cannot be allocated.

Source: lib/match.x:2280

MatchCache.dispose

void MatchCache.dispose(MatchCache cache)

Destroys a Match cache with no active leases. A null cache is ignored. Disposal frees all plans and cache storage and invalidates every alias.

Raises: <bad-state> when a lease remains active. The failure leaves the cache intact.

Source: lib/match.x:2076

MatchCache.flush_default

void MatchCache.flush_default(void)

Destroys the active Context-local or thread-local Match cache. A missing cache is ignored; the next Match recreates it lazily. Static compiler capture sites are unaffected.

Raises: <bad-state> when a lease remains active. The failure leaves the cache installed.

Source: lib/match.x:2387

MatchCache.initialize

void MatchCache.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.x:2322

MatchCache.new

MatchCache MatchCache.new(int capacity)

Creates a MatchCache retaining up to capacity prepared patterns. The returned cache owns a named Scope and is not synchronized. It borrows admitted pattern identities, so dispose it before their owning canonical pools. MatchCache.dispose is required after every lease is released.

Raises: <bad-arg> when capacity is not positive, <size-limit> when its storage dimensions cannot be represented, and <alloc-fail> when cache storage cannot be allocated.

Source: lib/match.x:1853

MatchCache.search

int MatchCache.search( MatchCache cache, List input, Var pattern, List *out_results)

Searches through cache, writing every match. out_results must be nonnull. It receives the reverse-visitation result List, or nil when there are no matches, the pattern is malformed, cache pressure prevents execution, or the machine fails. Returns 1 exactly when that List is nonempty.

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

Source: lib/match.x:2155

MatchCache.search_replace

int MatchCache.search_replace( MatchCache cache, List input, Var pattern, Var template, List *out)

Replaces every match through cache from the leaves upward. out must be nonnull. A completed prepared traversal returns 1 and writes its result even when nothing matched. A malformed pattern, cache pressure, or machine error returns 0 and writes input unchanged.

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

Source: lib/match.x:2191

MatchCache.try_capture

int MatchCache.try_capture( MatchCache cache, List input, Var pattern, MatchCaptureBuffer *captures)

Matches through cache into caller-owned positional storage. Returns 1 only after atomically committing a valid buffer. A miss, malformed pattern, invalid buffer, cache pressure, or machine error returns 0 and leaves it unchanged.

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

Source: lib/match.x:2100

MatchCache.try_match

int MatchCache.try_match( MatchCache cache, List input, Var pattern, List *out_bindings)

Matches through cache, writing bindings on success. out_bindings must be nonnull. Returns 0 and leaves it unchanged for a miss, malformed pattern, cache pressure, or machine error. Successful binding shape and order follow MatchPlan.execute.

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

Source: lib/match.x:2117

MatchCache.try_match_replace

int MatchCache.try_match_replace( MatchCache cache, List input, Var pattern, Var template, Var *out)

Match-replaces through cache, writing the replacement on success. out must be nonnull. Returns 0 and leaves it unchanged on a miss, malformed pattern, cache pressure, or machine error. The successful result may be any Var.

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

Source: lib/match.x:2173

MatchCache.try_search

int MatchCache.try_search( MatchCache cache, List input, Var pattern, Var *out_match, List *out_bindings)

Searches through cache, writing the first match and bindings. Both outputs must be nonnull. Returns 0 and leaves them unchanged on a miss, malformed pattern, cache pressure, or machine error. Traversal order follows MatchPlan.try_search.

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

Source: lib/match.x:2135

MatchCaptureBuffer

MatchCaptureBuffer.has

int MatchCaptureBuffer.has(MatchCaptureBuffer *captures, 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.x:534

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 MACHINE_MALFORMED.

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

Source: lib/match.x:490

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.x:513

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.x:496

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.x:527

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.x:521

MatchLease

MatchLease.release

void MatchLease.release(MatchLease *lease)

Releases the prepared program held by lease. Releasing an inactive lease has no effect. A successful release destroys a transient plan or unpins its cached entry and makes the lease inactive.

Raises: <bad-arg> when lease is NULL and <bad-state> when its cache or entry state is inconsistent. The failure leaves the lease active.

Source: lib/match.x:2047

MatchPlan

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.x:1639

MatchPlan.execute_capture

int MatchPlan.execute_capture( MatchPlan plan, 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.x:1613

MatchPlan.free

void MatchPlan.free(MatchPlan plan)

Releases resources owned by plan. A null plan is ignored; the plan, layout, program, and all aliases to them are invalid afterward. Borrowed pattern constants are not released.

Source: lib/match.x:1543

MatchPlan.prepare

MatchPlan MatchPlan.prepare(Var pattern)

Compiles pattern into a reusable immutable MatchPlan. The caller owns the returned plan in the active Scope. Preparation reports MACHINE_PREPARED, MACHINE_MALFORMED, or MACHINE_INELIGIBLE in the plan rather than raising for those outcomes; only a prepared plan has a program. reason is a borrowed static category string. The plan borrows pattern constants, which must outlive it.

Raises: <alloc-fail> while analyzing, lowering, or freezing.

Source: lib/match.x:1501

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.x:1706

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.x:1754

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.x:1626

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.x:1653

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.x:1728

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.x:1678

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.x:63

MatchCaptureLayout

typedef struct MatchCaptureLayout { Atom *binders; Var normalized; unsigned long definite, possible; int binder_count, MachinePrepare 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.x:50

MatchCaptureSite

typedef struct MatchCaptureSite { MatchPlan plan; } 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.x:87

MatchPlan

typedef struct MatchPlan { MachineProgram program; MatchCaptureLayout layout; MachinePrepare status, const char *reason; } *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. Pattern constants are borrowed, so the caller must free the plan before their canonical pools or other owners expire.

Source: lib/match.x:75

Design notes

Every guard except !quote accepts an optional leading binder. Nil is typed List data: it may be matched at the root or stored as an explicit searchable element. A proper List’s implicit terminal cdr is traversal structure and is not reported as an extra search node.

try_* output pointers are required, remain unchanged on failure, and write nil bindings for a successful match with no user binders.

MatchPlan is the runtime-internal prepared form of one pattern: a single analysis pass normalizes, categorizes, and lowers the pattern to shared wordcode from machine.x; the internal match-machine.x decoder executes it, and freeze publishes an exact-sized immutable program. Preparation returns PREPARED, INELIGIBLE(reason), or MALFORMED(reason). Invalid sigil-leading Atom names report MALFORMED(“binder-name”); a raw leading list binder inside a guard retains its categorized malformed result; more than MACHINE_BINDER_MAX distinct binders reports MALFORMED(“binder-capacity”). Preparation reports every status, but no entry point can answer for an INELIGIBLE plan, so each one raises <size-limit> naming the fence instead of reporting no match. Core matching executes only compiled plans; match-recursive.x is the optional reference implementation used by the differential tests. A MatchPlan owns an immutable layout and program but borrows the canonical values embedded in its pattern. MatchCaptureSite owns its plan until Match shutdown. Each invocation uses caller-owned capture storage and publishes it only after the complete match succeeds. Public 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).