lib/list.x

Linked list with Var elements.

Primary API

Functions

car

inline Var car(List x)

Returns the head of x, or void when x is nil.

Source: lib/list.x:263

cdr

inline List cdr(List x)

Returns the tail of x, or nil when x is nil. Nil-safe like car. The tail is the same canonical structure the cell was built from.

Source: lib/list.x:269

cons

List cons(Var head, List tail)

Returns the canonical cons cell for head and tail. Repeating the call with the same head bits and canonical tail returns the same cell from the active pool chain. An ancestor hit remains owned there; a miss belongs to the active pool. The tail is shared, and nil is the null pointer.

Raises: <void-op> when head is void, or <alloc-fail>, <size-limit>, or <invariant> when a new canonical cell cannot be installed.

Source: lib/list.x:243

Array

Array.list

List Array.list(Array arr)

Returns a new List holding the elements of arr in order. Cells are built from the end backwards through cons, so the result is canonical and shares whatever tail it already has in common with another List. arr is neither consumed nor freed.

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

Source: lib/list.x:555

Array.list_free

List Array.list_free(Array arr)

Returns arr.list() and frees arr. The conversion is Array.list, so the result copies the elements into fresh cells rather than adopting the Array’s storage. arr is released on success and when the conversion transfers an Error.

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

Source: lib/list.x:564

Iter

Iter.list

List Iter.list(Iter iter)

Drains iter into a new List. The iterator is consumed to exhaustion, so this is meaningful once and never returns for an infinite source. Elements appear in iteration order.

Raises: whatever the iterator’s source raises, or <alloc-fail> while constructing the result.

Source: lib/list.x:1073

List

List.all

int List.all(List lst, Func pred)

True when every element satisfies pred by ordinary Var truthiness. Stops at the first rejection. Nil is true; a null pred is false for a nonempty List.

Any cause raised by pred or its result’s truth operation propagates.

Source: lib/list.x:522

List.any

int List.any(List lst, Func pred)

True when at least one element satisfies pred by ordinary Var truthiness. Stops at the first accepted element. Nil and a null pred are false.

Any cause raised by pred or its result’s truth operation propagates.

Source: lib/list.x:507

List.append

Self List.append(Self a, Self b)

Returns the concatenation of a and b. Neither input is modified. b becomes the shared tail of the result, so only a’s cells are rebuilt, O(len(a)) of them. When either side is nil the other side is returned as it stands.

Raises: <alloc-fail> or <size-limit> while constructing the copied prefix.

Source: lib/list.x:320

List.array

Array List.array(List lst)

Returns a new Array holding the elements of lst in order. The Array is a fresh mutable container the caller owns and should free; the elements are shared, since they are only Vars. Convert when you need indexed access or in-place mutation.

Raises: <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list.x:576

List.concat_n

List List.concat_n(unsigned list_count, ...)

Returns the concatenation of exactly list_count List arguments. Nil is a valid argument, no sentinel is read, and the final nonempty List becomes the shared tail of the result.

Raises: <size-limit> when list_count exceeds the supported index range, or <alloc-fail> while constructing the result.

Source: lib/list.x:356

List.contains

int List.contains(List lst, Var key)

Reports whether lst contains key by Var equality.

Source: lib/list.x:420

List.filter

Self List.filter(Self lst, Func pred)

Returns the elements pred accepts by ordinary Var truthiness. Elements are passed as values, and filtering nil gives nil without invoking or checking pred.

Raises: whatever Func.apply, pred, or result truthiness raises, or <alloc-fail> or <size-limit> while constructing the result. A null pred on nonempty input raises <bad-arg> from Func.apply.

Source: lib/list.x:1088

List.find

Var List.find(List lst, Func pred)

Returns the first element pred accepts by ordinary Var truthiness, or void.

Any cause raised by pred or its result’s truth operation propagates. A null pred returns void.

Source: lib/list.x:492

List.foldl

Var List.foldl(List lst, Var seed, Func fn)

Folds fn over the elements of lst from the left, starting at seed. fn receives the accumulator and then the next element, and returns the next accumulator. A void seed means “no seed”: the first element becomes the initial accumulator and the fold starts at the second, and folding nil that way returns void. A null fn returns the accumulator untouched, which for a void seed is the head.

Any cause raised by fn propagates.

Source: lib/list.x:460

List.get

Var List.get(List list, Var key)

Looks up an integer index or association key in list. Integer keys use List.getindex, including negative indexes; every other key uses List.assoc. Either absent form returns void.

Source: lib/list.x:752

List.getindex

Var List.getindex(List list, int index)

Returns list[index], or void when out of range. A negative index counts from the end and is found without a length pass.

Source: lib/list.x:716

List.getslice

Self List.getslice(Self list, int start, int stop, int step)

Returns list[start:stop:step]. stop is exclusive, negative bounds count from the end, and a negative step walks backwards. A full forward slice preserves list only when its identity is canonical in the active pool chain; otherwise it rebuilds the cells there so a detached pool cannot escape through the shortcut.

Raises: <bad-arg> when step is zero, or <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list.x:825

List.head

Self List.head(Self list, unsigned count)

Returns the first count elements of list. When count reaches or exceeds the length, list itself comes back, the same pointer. Lists are immutable, so sharing it is safe. Otherwise fresh canonical cells are built for the prefix.

Raises: <alloc-fail> or <size-limit> while constructing that prefix.

Source: lib/list.x:781

List.index

int List.index(List lst, Var key)

Returns the first index of key, or -1 when absent.

Source: lib/list.x:413

List.iter

Iter List.iter(List lst, Iter dest)

Initializes caller-owned dest as a forward iterator over lst. The iterator borrows the immutable cells and yields their stored Var bits without retaining them, so the owning pool must outlive iteration. A null dest returns NULL; nil produces an exhausted iterator.

Source: lib/list.x:1062

List.last

Var List.last(List lst)

Returns the last value in lst, or void when it is empty.

Source: lib/list.x:405

List.len

int List.len(List lst)

Returns the number of cells in lst in O(n) time.

Source: lib/list.x:423

List.list_n

List List.list_n(unsigned element_count, ...)

Builds a List from exactly element_count Var arguments. Every argument is data, so void raises instead of being read as a terminator. A zero count returns nil.

Raises: <void-op> when an argument is void, or <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list.x:382

List.map

List List.map(List lst, Func fn)

Returns a canonical List holding fn applied front to back. Elements are passed as values, and mapping nil gives nil without invoking or checking fn. A null fn on nonempty input raises <bad-arg>, and a callback result of void raises <void-op> when the result List is built.

Raises: those causes, whatever Func.apply or fn raises, or <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list.x:438

List.map2

List List.map2(List a, List b, Func fn)

Maps fn over aligned pairs from a and b. A null callback returns nil without examining either List; otherwise this has the length, order, ownership, and failures of List.zip_with.

Source: lib/list.x:630

List.reduce

Var List.reduce(List lst, Func fn)

Folds fn over lst using its first element as the seed. A one-element List returns its head and nil returns void. A null fn returns the first element without visiting the rest.

Any cause raised by fn propagates.

Source: lib/list.x:484

List.reverse

Self List.reverse(Self lst)

Returns a new List holding the elements of lst in reverse order. Fresh cells are built through cons, so the result is canonical and lst is untouched. Reversing nil gives nil.

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

Source: lib/list.x:395

List.sort

Self List.sort(Self lst)

Returns a copy of lst ordered by Var.compare. lst is unchanged. There is no comparator parameter. Var.compare orders the element tags involved, so a mixed-kind List still sorts. A List of fewer than two cells is returned as it stands.

Raises: whatever element comparison raises, or <alloc-fail> while constructing the result.

Source: lib/list.x:539

List.tail

Self List.tail(Self list, unsigned count)

Returns the last count elements of list. The result is an existing tail of list, so nothing is allocated. When count reaches or exceeds the length, the whole list comes back.

Source: lib/list.x:761

List.unique

Self List.unique(Self lst)

Returns a copy of lst with later duplicates removed. The first occurrence of each value is kept and the original order is preserved. Duplicate detection runs through Iter.unique, whose state is held inside a Scope bracket that is released before returning. A List of fewer than two cells is returned as it stands.

Raises: causes from Map hashing or equality, or <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list.x:591

List.unpack_n

int List.unpack_n(List src, unsigned destination_count, ...)

Writes at most destination_count elements through List pointers. Returns the number written. Extra source cells are left unread, and a short source leaves remaining destinations untouched. Each source value is decoded as a List, so another tag writes nil; a null destination is skipped but still counted.

Raises: <size-limit> when destination_count exceeds INT_MAX. The failure occurs before any destination is written.

Source: lib/list.x:872

List.unpack_vars_n

int List.unpack_vars_n(List src, unsigned destination_count, ...)

Writes at most destination_count elements through Var pointers. Returns the number written. Extra source cells are left unread, and a short source leaves remaining destinations untouched. A null destination is skipped but still counted.

Raises: <size-limit> when destination_count exceeds INT_MAX. The failure occurs before any destination is written.

Source: lib/list.x:887

List.write_str

Buffer List.write_str(List lst, Buffer out)

Appends the List display text to out, using each element’s write_str. List.str calls this to build its result. The display form has one space inside each parenthesis, as in ( a b ), including when nested in another container. This method temporarily sets the destination Buffer’s padding to one and restores it afterward.

Source: lib/list.x:1018

List.zip_with

List List.zip_with(List a, List b, Func fn)

Combines aligned values from two Lists with fn. A null fn produces two-element pair Lists. The shorter input determines the result length, and an empty input does not inspect the callback. A callback receives the left and right values and is invoked front to back.

Raises: whatever Func.apply, fn, or result canonicalization raises.

Source: lib/list.x:607

Advanced and interop API

List

List.assoc

Var List.assoc(List list, Var key)

Returns the second value of the first association whose key equals key. Nil entries are skipped. A missing association and a missing second value both return void, so the two cases look the same here.

Source: lib/list.x:739

List.caar

inline Var List.caar(List lst)

Returns car(car(lst)). Compound accessors read from right to left: a applies car and d applies cdr. Every step is nil-safe.

Source: lib/list.x:279

List.caddr

inline Var List.caddr(List lst)

Returns the third element, or void.

Source: lib/list.x:285

List.cadr

inline Var List.cadr(List lst)

Returns car(cdr(lst)), or void when there is no second element.

Source: lib/list.x:281

List.car

inline Var List.car(List lst)

Method form of car: the head of lst, or void when lst is nil.

Source: lib/list.x:272

List.cddr

inline Self List.cddr(Self lst)

Returns the tail after two cells, or nil.

Source: lib/list.x:283

List.cdr

inline Self List.cdr(Self lst)

Method form of cdr: the tail of lst, or nil when lst is nil.

Source: lib/list.x:274

List.compare

int List.compare(List a, List b)

Compares a and b lexicographically through Var.compare. Element comparison causes propagate.

Source: lib/list.x:922

List.cons

List List.cons(Var head, List tail)

Method form of cons, with the same identity, lifetime, and failures.

Source: lib/list.x:258

List.cons_in

List List.cons_in(Pool pool, Var head, List tail)

Returns the canonical cell for head and tail in pool’s chain. An ancestor hit keeps that ancestor’s ownership; a miss is owned by pool. A null pool or void head returns nil without allocating. Any pool-managed graph reachable through head or tail is borrowed and must remain live for at least as long as the result.

Raises: <alloc-fail>, <size-limit>, or <invariant> while installing a new cell.

Source: lib/list.x:49

List.equal

int List.equal(List a, List b)

Reports equality of canonical chains by exact head and tail identity. Referenced mutable objects therefore compare by identity here rather than by their current contents.

Source: lib/list.x:913

List.flatten

Self List.flatten(Self lst)

Flattens one level of nested Lists into a canonical result. A nested nil contributes no element, non-List values retain their identity, and nil returns nil.

Raises: <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list.x:670

List.flatten_all

Self List.flatten_all(Self lst)

Recursively flattens every nested List into a canonical result. Nested nil contributes no element and nil returns nil.

Raises: <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list.x:696

List.hash

unsigned List.hash(List lst)

Returns the stable hash of List’s exact head bits and tail identity. Mutating an object referenced by the head does not change this hash.

Source: lib/list.x:900

List.nth_cdr

Self List.nth_cdr(Self list, int n)

Returns the shared tail beginning n cells in. Returns nil past the end and list itself when n is nonpositive.

Source: lib/list.x:708

List.promote

Self List.promote(Self lst)

Moves lst out of the innermost interning pool into its parent. Cells, nested Lists, interned String cars, and long Atom payloads all move together, so a promoted List keeps its complete identity graph across the matching List.pool_release. Pointers never change and ancestor-owned structure is left where it is; the return value is lst itself.

Cells are immutable, so an ancestor-owned cell can only reference ancestor-owned cars and tails. The walk stops at the first cell the innermost pool does not own. Promoting an already-promoted List is therefore cheap. Var kinds other than String, Atom, and List are Scope-managed and outside pool jurisdiction.

A null lst returns itself unchanged.

Source: lib/list.x:206

List.repr

String List.repr(List lst)

Returns the re-readable rendering of lst. This is the %(...) spelling of the same data. Elements are rendered with their own repr, so Strings come back quoted and Atoms print as bare names, and nil renders as (). Long nested structure wraps at about 80 columns. The canonical result follows the active String pool chain, may already be owned by an ancestor, and remains live until that owner is released.

Raises: <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list.x:1035

List.str

String List.str(List lst)

Returns the human-readable rendering of lst. Elements are rendered with their own str, so a String element appears unquoted. The writer pads inside parentheses and breaks nested structure across lines at about 80 columns. Nil renders as (). The canonical result follows the active String pool chain, may already be owned by an ancestor, and remains live until its owning pool is released. Use List.repr when the text has to read back in.

Raises: <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list.x:1006

List.sublis

List List.sublis(List alist, List tree)

Recursively substitutes non-List nodes in tree from alist. Each association is a List whose first value is the key and whose second value is the replacement. Unmatched leaves are shared; List structure is rebuilt canonically, and nil returns nil.

Raises: a cause from key equality, or <alloc-fail> or <size-limit> while constructing the result.

Source: lib/list.x:659

List.subseq

Self List.subseq(Self list, int start, int stop, int step)

Returns every stepth element from start up to exclusive stop. Negative bounds count from the end. step must be positive.

Raises: <bad-arg> when step is less than 1, or <alloc-fail> while constructing the result.

Source: lib/list.x:811

List.write_repr

Buffer List.write_repr(List lst, Buffer out)

Appends the readable representation of List to a Buffer.

Source: lib/list.x:1043

Var

Var.caar

inline Var Var.caar(Var var)

Applies the caar selector chain to Var.

Source: lib/list.x:292

Var.caddr

inline Var Var.caddr(Var var)

Applies the caddr selector chain to Var.

Source: lib/list.x:298

Var.cadr

inline Var Var.cadr(Var var)

Applies the cadr selector chain to Var.

Source: lib/list.x:294

Var.car

Var Var.car(Var var)

Treats var as a List and returns its first element.

Source: lib/list.x:288

Var.cddr

inline List Var.cddr(Var var)

Applies the cddr selector chain to Var.

Source: lib/list.x:296

Var.cdr

List Var.cdr(Var var)

Treats var as a List and returns its tail.

Source: lib/list.x:290

Var.cons

List Var.cons(Var head, List tail)

Returns cons(head, tail), with the same identity and failures.

Source: lib/list.x:260

Runtime-internal callables

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

List

List.initialize

void List.initialize(void)

Initializes the shared process-wide String and List pool root.

Raises: <alloc-fail> if the root cannot be constructed. Native mutex initialization failure aborts.

Source: lib/list.x:91

List.pool_current

Pool List.pool_current(void)

Returns this thread’s borrowed active canonical-value pool. The call lazily installs the process root when this thread has none; the caller must not release the returned pool.

Raises: <alloc-fail> if the root cannot be initialized. Native mutex initialization failure aborts.

Source: lib/list.x:85

List.pool_detach

Pool List.pool_detach(void)

Removes the active nested pool without destroying it and returns it. The parent becomes active. Thread keeps the detached pool sealed until join copies its survivors. The caller must eventually pass it to Pool.release before destroying its parent.

Raises: <bad-state> when no nested pool is active. The active pool is unchanged.

Source: lib/list.x:163

List.pool_release

void List.pool_release(void)

Pops the innermost shared interning pool, discarding everything in it. Cells that List.promote moved to the parent pool survive with their pointers unchanged; everything else is reclaimed and drops out of the interning tables. Strings, long Atom payloads, and Lists move through the same pool chain.

Raises: <bad-state> when no nested pool is open. The failure leaves the active pool unchanged.

See: List.pool_retain, List.promote, String.pool_release

Source: lib/list.x:149

List.pool_retain

Pool List.pool_retain(void)

Pushes a nested interning pool that new Strings and cons cells use. New canonical identities between this call and the matching List.pool_release are placed in the new pool. A lookup that finds an equal ancestor-owned value returns that identity with its longer lifetime. Promote anything that must outlive the bracket first: unpromoted cells are discarded and their identities no longer resolve, so a later cons of the same head and tail allocates a fresh cell instead of finding the old one. Brackets nest. List.pool_retain_named is the same operation with a label for diagnostics. String.pool_retain is another name for the same operation; callers open one bracket, not one through each name.

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

See: List.pool_release, List.promote, List.pool_retain_named, String.pool_retain

Source: lib/list.x:137

List.pool_retain_named

Pool List.pool_retain_named(const char *name)

Pushes a named child onto the shared String and List pool stack. New canonical misses belong to the child, while hits retain the lifetime of the ancestor that already owns them. The returned pool is the new active pool and must be matched by List.pool_release or detached and released. name is copied into the child’s diagnostic Scope.

Raises: <alloc-fail> while constructing the child. The failure leaves the active pool unchanged. Native mutex failure aborts.

Source: lib/list.x:120

List.shutdown

void List.shutdown(void)

Releases every active nested pool and then the process root at shutdown. No worker or canonical value may remain in use afterward. Repeated calls after the root is gone do nothing.

Source: lib/list.x:106

List.thread_initialize

void List.thread_initialize(void)

Installs the existing process pool root in a newly created worker thread. The root must already be initialized; otherwise the process aborts.

Source: lib/list.x:98

List.try_own

int List.try_own(List lst)

Proves lst and its canonical children safe beyond every active pool. Returns 1 when the complete value is nil, already permanent, or can be promoted to the outermost List and String pools. Returns 0 when an active pool does not own part of the value. A zero result may follow successful promotion of an earlier cell or child.

Raises: <alloc-fail> when promotion metadata cannot be allocated.

Source: lib/list.x:231

Public types

List

typedef struct List { Var car; struct List *cdr; } *List

Names an immutable canonical cons cell, or nil as NULL. A nonnull cell is borrowed from the pool that owns its exact car and tail identity; callers neither mutate nor free it. The car is never void, and the tail is nil or another live canonical List.

Source: lib/list.x:32

Design notes

List is an immutable, interned cons chain. A car may hold any non-void Var; a cdr is nil or another List. Canonical identity is the car’s exact Var bits plus the canonical tail identity, so mutating an Array or Map stored in a car does not change the identity of the cell that contains it.

Construction searches the requested pool and its ancestors. An existing cell keeps its ancestor’s lifetime; a miss belongs to the requested pool. Releasing a nested pool invalidates its unpromoted cells, while promotion preserves complete canonical List, String, and long-Atom structure without changing pointers. void is a terminal sentinel, not List data.

Tests and examples

make verify (unittest/test-list.x) and make examples (docs-tour).