Module `imm/vec`

imm/vec

Stability: unstable — `plans/STD_API_STABILIZATION.md` §5 has an OPEN maintainer decision on exactly this type: implement real structural sharing (an RRB tree, which would make shared mutation O(log n)) or keep the flat copy-on-write array and stand behind the O(n). Either answer is compatible with these signatures, but the second is also an argument for renaming the mutators or dropping `own(self)`, so the surface cannot be frozen before the decision. The related `imm` question — the shape of `remove` across these containers — is open in the same section. — stable modules only change additively; this one may still change.

Immutable vector with O(1) indexed access — a flat copy-on-write array, NOT a structurally-shared trie.

Vec(T) is an immutable vector: every mutation returns a new vector and leaves the original unchanged. All elements must implement Send, which is what makes a vector safe to hand to another thread. The sharing is whole-buffer: when the receiver is the ONLY owner the buffer is updated in place, and when anyone else still holds it the whole array is copied, so a mutation on a shared vector is O(n) rather than the O(log n) an RRB- or HAMT-backed persistent vector would give. Read imm.List for real structural sharing (O(1) prepend, shared tails) and imm.Map for a HAMT.

The mutating methods take own(self), so the RECEIVER IS MOVED:

bigger := v.push(x);          // `v` is gone; `bigger` is the new vector
kept := v; bigger := v.push(x);   // keeping the old version needs this...

and the extra binding is also what pushes the refcount above one and sends push down its COPYING path.

What "immutable" costs here, exactly

The backing store is ONE flat array behind an atomic refcount. So:

operation	refcount 1 (unshared)	refcount > 1 (shared)
`get` / `len`	O(1)	O(1)
`push` / `pop` / `set`	O(1) amortized, in place	O(n) — the whole array is copied

That is a real trade and it is deliberate: indexed access is a single pointer offset, and a linear chain of mutations on an unshared vector costs what a mutable array would. It is NOT the O(log n)-everywhere behaviour of im::Vector's RRB tree, and this module does not claim it — an earlier version of this doc said "structural sharing", which was wrong about the implementation and is the reason this section exists.

Decision (2026-09-11, plans/STD_API_STABILIZATION.md §5): stay flat COW and document it, rather than implement RRB. Two reasons. The ergonomics push callers toward the fast path anyway — push takes own(self), so the receiver is MOVED and keeping the earlier version requires an extra binding (kept := v; bigger := v.push(x)), which is also exactly what pushes the refcount above one and sends push down the copying path. And a flat array is what makes Vec the right choice for the case it is actually reached for: build once, then read and share. Reach for imm.List when you need cheap prepend on a shared value, and for ArrayList when you want mutation.

If a workload needs shared-mutation to be sublinear, that is an RRB implementation behind this same API, and the API will not have to change.

Cycle safety

Vec uses ATOMIC reference counting, and the cycle collector does not scan atomic objects (the Arc pattern) — so, like Arc(V), element types must be Acyclic (plans/archive/STD_API_AUDIT.md O7, landed 2026-08-27). Structurally-acyclic types satisfy the bound automatically; a self-referential type is rejected at instantiation.

Examples

{ Vec } :: import "std/imm/vec";

v := Vec(i32).new();
v = v.push(i32(1)).push(i32(2)).push(i32(3));
assert((v(usize(0)) == i32(1)), "first element");
assert((v.len() == usize(3)), "length is 3");

Stability

unstable — plans/STD_API_STABILIZATION.md §5 has an OPEN maintainer decision on exactly this type: implement real structural sharing (an RRB tree, which would make shared mutation O(log n)) or keep the flat copy-on-write array and stand behind the O(n). Either answer is compatible with these signatures, but the second is also an argument for renaming the mutators or dropping own(self), so the surface cannot be frozen before the decision. The related imm question — the shape of remove across these containers — is open in the same section.

Types

Vec type-function

fn(T : Type) -> Type

Immutable vector: a flat copy-on-write array behind an atomic refcount.

get is a pointer offset. A mutation on an UNSHARED vector (refcount 1) happens in place and is O(1) amortized; a mutation on a SHARED one copies the whole array and is O(n) — there is no per-node sharing. See the module header for why that trade was kept rather than replaced with a structurally-shared trie. Elements must be Send (the buffer crosses threads) and Acyclic (the cycle collector does not scan atomic objects).

Type Parameters

Name	Type	Notes
`T`	Type	comptime

Trait Implementations

Acyclic Dispose Eq Index IntoIterator Default

impl(generic(T : Type), where(T <: (Send, Acyclic)), Vec(T), Acyclic())

impl(generic(T : Type), where(T <: (Send, Acyclic)), Vec(T), Dispose(...))

dispose : (fn(self : Self) -> unit)

Release the resources self owns — a file descriptor, a socket, a lock, a buffer the allocator handed out. Called automatically when the last reference to the value goes away, so an implementor never calls it directly and must tolerate being the only one who ever does.

It must be safe to run exactly once: the runtime calls it at refcount zero, and a type that also exposes an explicit close/release is responsible for making the second call a no-op.

Returns: unit

impl(generic(T : Type), where(T <: (Send, Acyclic)), Vec(T), ...)

_raw_alloc : (fn(cap : usize) -> *T)

Allocate raw buffer without creating an intermediate atomic object.

Returns: *T

_copy_elems :

(
    fn(
      dst : *T,
      src : *T,
      dst_offset : usize,
      src_offset : usize,
      count : usize
    ) -> unit
  )

Copy elements element-by-element so RC-backed values duplicate correctly.

Returns: unit

_move_elems : (fn(dst : *T, src : *T, count : usize) -> unit)

MOVE count elements from src into the fresh buffer dst as raw bytes: ownership of every reference transfers with the bytes, so nothing is dup'd and nothing needs dropping — the old buffer is then just freed. This is the unique-owner grow path; _copy_elems (dup per element) is for a buffer the source keeps sharing. Copying with _copy_elems and then freeing the old buffer leaked one reference per element per grow (issues/fixed/imm-vec-leaks-on-grow-and-drops-uninitialized-memory.md).

Returns: unit

new : (fn() -> Self)

Create a new empty vector.

Returns: Self

with_capacity : (fn(cap : usize) -> Self)

Create a new empty vector with the given initial capacity.

Returns: Self

len : (fn(self : Self) -> usize)

Number of elements in the vector.

Returns: usize

is_empty : (fn(self : Self) -> bool)

Check if the vector is empty.

Returns: bool

get : (fn(self : Self, idx : usize) -> Option(T))

Get the element at idx, or .None if out of bounds.

Returns: Option(T)

set : (fn(own(self) : Self, idx : usize, val : T) -> Self)

New vector with the element at idx replaced by val. PANICS when idx >= len().

Takes own(self): the receiver is MOVED, and when it is the only owner the element is overwritten in place (O(1)). If any other handle exists the whole buffer is copied first — O(n).

Returns: Self

push : (fn(own(self) : Self, val : T) -> Self)

New vector with val appended.

Takes own(self): the receiver is MOVED, so v.push(x) consumes v. The uniquely-owned path appends in place (amortized O(1), doubling the buffer when full); a SHARED vector copies its whole array first, which is O(n) per push. Keeping the old version — kept := v; bigger := v.push(x) — is what makes it shared, so building a vector by pushing while holding every intermediate is quadratic.

Returns: Self

first : (fn(self : Self) -> Option(T))

Return the first element, or .None if empty.

Returns: Option(T)

last : (fn(self : Self) -> Option(T))

Return the last element, or .None if empty.

Returns: Option(T)

pop : (fn(own(self) : Self) -> PopResult(T))

The vector without its last element, alongside that element — both in one PopResult, since Yo has no multiple returns. .value is .None on an empty vector.

Takes own(self): uniquely owned, it just shortens in place; shared, it copies the remaining elements — O(n).

Returns: PopResult(T)

slice : (fn(self : Self, start : usize, end : usize) -> Self)

Return a new vector containing only elements in range [start, end).

Returns: Self

concat : (fn(own(self) : Self, other : Self) -> Self)

New vector holding self's elements followed by other's — O(n + m), always: there is no shared spine to splice, so the result is a fresh array. Takes own(self), so the left operand is MOVED.

Returns: Self

reverse : (fn(own(self) : Self) -> Self)

New vector with the elements in reverse order — O(n). Takes own(self), so the receiver is MOVED.

Returns: Self

map : (fn(generic(U : Type), self : Self, f : Impl(Fn(a : T) -> U), where(U <: (Send, Acyclic))) -> Vec(U))

Apply a function to each element, producing a new vector.

Returns: Vec(U)

filter : (fn(self : Self, f : Impl(Fn(a : T) -> bool)) -> Self)

Filter elements by a predicate, returning a new vector.

Returns: Self

fold : (fn(generic(U : Type), self : Self, init : U, f : Impl(Fn(acc : U, elem : T) -> U)) -> U)

Left fold over elements.

Returns: U

any : (fn(self : Self, f : Impl(Fn(a : T) -> bool)) -> bool)

Check if any element satisfies the predicate.

Returns: bool

all : (fn(self : Self, f : Impl(Fn(a : T) -> bool)) -> bool)

Check if all elements satisfy the predicate.

Returns: bool

find : (fn(self : Self, f : Impl(Fn(a : T) -> bool)) -> Option(T))

Find the first element satisfying the predicate.

Returns: Option(T)

index_of : (fn(self : Self, val : T, where(T <: Eq(T))) -> Option(usize))

Return the index of the first element equal to val, or .None.

Returns: Option(usize)

contains : (fn(self : Self, val : T, where(T <: Eq(T))) -> bool)

Check if the vector contains val.

Returns: bool

dedup : (fn(own(self) : Self, where(T <: Eq(T))) -> Self)

New vector with duplicates removed, keeping the FIRST occurrence of each — unlike ArrayList.dedup, which only collapses ADJACENT equals.

O(n²): every candidate is compared against the elements already kept. Takes own(self), so the receiver is MOVED.

Returns: Self

zip_with :

(fn(generic(U : Type, V : Type), self : Self, other : Vec(U), f : Impl(Fn(a : T, b : U) -> V), where(U <: (Send, Acyclic), V <: (Send, Acyclic))) -> Vec(V))

Zip two vectors together using a combining function.

Returns: Vec(V)

from_list : (fn(l : ArrayList(T)) -> Self)

Create a vector from a slice, copying all elements.

Returns: Self

impl(generic(T : Type), where(T <: (Send, Acyclic, Eq(T))), Vec(T), Eq(Vec(T))(...))

impl(generic(T : Type), where(T <: (Send, Acyclic)), Vec(T), Index(usize)(...))

Output : T

index : (fn(inout(self) : Self, idx : usize) -> *Self.Output)

Parameters

Name	Type	Notes
`idx`	usize

Returns: *Self.Output

impl(generic(T : Type), where(T <: (Send, Acyclic)), Vec(T), IntoIterator(...))

Item : T

IntoIter : VecIter(T)

into_iter : (fn(self : Self) -> VecIter(T))

Returns: VecIter(T)

impl(generic(T : Type), where(T <: (Send, Acyclic)), Vec(T), Default(...))

default : (fn() -> Self)

The default value of the type.

Returns: Self

PopResult type-function

fn(T : Type) -> Type

Result of a pop operation.

Type Parameters

Name	Type	Notes
`T`	Type	comptime

VecIter type-function

fn(T : Type) -> Type

Iterator over a Vec's elements, front to back.

The backing store is a flat array, so this is an index walk: O(1) per step and no allocation.

Type Parameters

Name	Type	Notes
`T`	Type	comptime

Trait Implementations

Iterator

impl(generic(T : Type), where(T <: (Send, Acyclic)), VecIter(T), Iterator(...))

Item : T

next : (fn(inout(self) : Self) -> Option(T))

Advance the iterator and return the next value, or None when exhausted.

Returns: Option(T)

Module imm/vec

What "immutable" costs here, exactly

Cycle safety

Examples

Stability

Types

Type Parameters

Trait Implementations

Parameters

Type Parameters

Type Parameters

Trait Implementations

Module `imm/vec`