Module collections/array_list

Number of elements. O(1) — the length is stored, never counted.

True when the list holds no elements — len() == 0.

Elements the current buffer can hold before push has to reallocate.

SIZE_MAX for a zero-sized element type, which never grows — see _zst_anchor. Rust's Vec::capacity reports usize::MAX for the same reason.

The allocator the buffer belongs to: the one given to new_in / with_capacity_in, or .None for a list on the global allocator.

Raw pointer to the element buffer, or .None when nothing is allocated yet — Rust's Vec::as_ptr, minus the dangling-pointer guarantee.

The pointer is only valid until the next reallocation (push past capacity, reserve, ensure_total_capacity, shrink_to_fit), and it borrows: it does not keep the list alive.

A pointer to the first uninitialized slot, ptr() + len(): the start of the capacity() - len() slots a reader fills before assume_init commits them. .None when nothing is allocated yet (reserve first).

The result is a raw pointer VALUE, so the safe-mode gate keeps it out of safe code exactly as it keeps out ptr(). Claiming memory initialized needs this token, which safe code cannot obtain (ATS's view of the region; issues/fixed/safe-code-reaches-freed-memory-through-arraylist-set-len.md). A struct that merely CONTAINS a pointer, such as RawSlice(T), would not be gated: safe code may hold String.raw_bytes(). The pointer is valid until the next reallocation, like ptr().

Commit the first n spare slots (spare is the token from spare_capacity) as live elements: the length grows by n. Nothing is initialized or dropped; the caller has written those n slots. PANICS unless spare is this list's current end and n <= capacity() - len().

Empty list on the global allocator. Allocates nothing — the first push buys the buffer (four elements), as Rust's Vec::new does. new_in(a) places the buffer in a instead.

Owned copy of the elements in [r.start, r.end) — JS-style range slicing with value semantics (plans/archive/SLICE_REWORK.md: list(a..b) lowers to this).

The end is CLAMPED to the length rather than checked, so an over-long range yields a short list instead of panicking; slice is the checked, Result-returning spelling. Elements are copied (dup'd for a refcounted T), so the result is independent of the source.

Inclusive-range companion of slice_copy (list(a..=b)).

Consuming constructor from a fixed-size array — Rust's Vec::from([T; N]): ArrayList(i32).from([i32(1), i32(2), i32(3)]).

The array is taken by sink, so the caller's binding ends at the call and its elements are now the list's. A caller that keeps the array passes a copy: ArrayList(T).from(arr.clone()). N comes from the array's type, so the exact capacity is reserved up front and no growth happens.

Empty list whose buffer already holds cap elements, on the global allocator — Rust's Vec::with_capacity.

PANICS on "capacity overflow" when sizeof(T) * cap would wrap (Rust panics with the same message), and on allocation failure. A zero-sized element type takes the one-byte anchor buffer instead of allocating cap of nothing.

Empty list whose buffer lives in alloc — Rust's Vec::new_in.

Every growth, shrink and the final release go through alloc, wherever and on whichever thread the last reference dies. Unlike new, this takes one allocation right away: a block holding only alloc's 16-byte owner prefix, which is how the list remembers its allocator (the list object itself stays the size of a plain one). PANICS when that allocation fails.

Empty list with room for cap elements, its buffer in alloc — Rust's Vec::with_capacity_in. PANICS on capacity overflow and on allocation failure, like with_capacity.

The one buffer an ArrayList of a ZERO-SIZED element type ever has.

sizeof(T) == 0 (unit, an all-unit aggregate, Array(unit, N)) means the elements occupy no bytes: a store writes nothing, a read reads nothing, and the byte size of every buffer is 0. Rust's Vec<()> never allocates and reports capacity() == usize::MAX. Yo cannot conjure a non-null dangling pointer, so the stand-in is ONE one-byte block, allocated once and never resized: the capacity is the largest untagged value (capacity() reports SIZE_MAX), so push never reaches the grow path, and shrink_to_fit is a no-op. Going through the allocator with sizeof(T) * cap == 0 instead would malloc(0) and then realloc(p, 0) — which frees p and returns NULL on glibc and the Windows CRT — and the list would report "allocation failed" on its second growth.

Append an element, reporting allocation failure as .Err(.AllocError(.OutOfMemory)) instead of panicking.

The allocator-aware form (D9); push is the one to reach for. Amortized O(1) — the buffer doubles (4 elements first), so a growth INVALIDATES every pointer previously handed out by ptr(), iter() or the Index impl.

Append an element — amortized O(1).

PANICS on allocation failure: Rust's Vec::push aborts, and so do this list's own ensure_total_capacity / with_capacity. Before D9 this returned a Result that every one of its callers discarded, usually via a throwaway _p := binding — a Result nobody checks is strictly worse than a panic, because it reads as if the failure were handled. Use try_push when the caller genuinely handles OOM.

A growth reallocates, so any pointer into the buffer (ptr(), iter(), self(i)) is invalid afterwards.

Remove and return the last element, or .None when empty — O(1), and the capacity is kept.

Copy of the element at index, or .None when index >= len().

The bounds-checked reader. self(index) (the Index impl) reads the element in place and panics out of range instead; get_cloned(i) clones an element that is not copied implicitly, and with(i, body) writes one in place (plans/VALUES_BY_DEFAULT.md decision 20).

Give the unused tail of the buffer back to the allocator so that capacity() == len() — Rust's Vec::shrink_to_fit.

Reallocates (an empty list frees its buffer outright), so every pointer into the buffer is invalid afterwards and the next push grows again. .Err(.AllocError(.OutOfMemory)) when the shrinking realloc fails — the list is left untouched and usable. A zero-sized element type is a no-op: its anchor buffer cannot shrink.

Remove the elements in [r.start, r.end) and return them, in order, as a fresh list — Rust's Vec::drain, collected eagerly rather than lazily (Yo has no borrowing iterator to hold the source open).

O(n): the tail shifts left to close the gap. PANICS on an inverted range or an end past the length — the old remove(start, count) silently clamped the count, which hid caller bugs.

Insert value at idx, shifting the tail right — O(n). idx == len appends, as in Rust.

Move every element of other onto the end of self, leaving other EMPTY — Rust's append. extend copies instead.

First element, or .None when empty.

Last element, or .None when empty.

Reserve room for additional MORE elements.

Rust's spelling. ensure_total_capacity takes a TOTAL, which is the same call with a different meaning and an easy one to get wrong at a call site.

Run body on the element at index, borrowed in place, and return its result — decision 20's non-copying access (plans/VALUES_BY_DEFAULT.md): the element is neither copied out nor written back. Panics when index >= len().

{ ArrayList } :: import("std/collections/array_list");
{ String } :: import("std/string");
(mut(names) : ArrayList(String)) = ArrayList(String).new();
names.push(`ada`);
n := names.with(usize(0), s => {
  s.push_str(" lovelace");
  s.len()
});
assert((n == usize(12)) && (names(usize(0)) == `ada lovelace`), "written in place");

Move the element at index out and leave T's default in its slot — std/mem's take(&mut xs(i)). Nothing is copied, so a move-only T works. Panics when index >= len().

{ ArrayList } :: import("std/collections/array_list");
{ String } :: import("std/string");
(mut(names) : ArrayList(String)) = ArrayList(String).new();
names.push(`ada`);
s := names.take(usize(0));
assert((s == `ada`) && (names(usize(0)) == ``), "the slot keeps the default");

Exchange the elements at i and j.

Moves the raw slots, like reverse — no dup/drop, so this is RC-neutral however the element type is refcounted.

Remove the element at idx and return it, moving the LAST element into the hole — O(1), and it does not preserve order. Rust's swap_remove.

Shorten to new_len, dropping the elements past it. Longer new_len is a no-op, as in Rust.

Resize to exactly new_len, dropping the tail when shrinking and appending copies of value when growing. Rust's resize.

Distinct from resize_with_byte, which memsets raw storage and is only meaningful for a plain-old-data element type.

Overwrite every element with value, keeping the length. Rust's fill.

Split off [at, len) into a new list, leaving [0, at) here.

Remove the element at idx and return it, shifting the tail left — O(n), order preserved. Rust's Vec::remove.

PANICS when idx >= len(). swap_remove is the O(1) alternative when order does not matter.

Owned copy of [start, end), or an .IndexOutOfBounds error — the CHECKED counterpart of slice_copy, which clamps instead.

An inverted range reports .IndexOutOfBounds(index : start, length : end). O(end - start), one allocation of the exact size.

Grow the buffer so it holds at least min_cap elements in TOTAL, doubling as it goes; a request under the current capacity does nothing.

reserve(additional) is the Rust spelling and takes a COUNT TO ADD — the same call with a different meaning, and the easy one to get right at a call site. PANICS on capacity overflow and on allocation failure (try_push is the only allocator-aware entry point). Reallocates, so pointers into the buffer do not survive it.

Append count elements from a raw buffer with one memcpy.

The caller guarantees src holds count initialized, correctly aligned Ts that do not alias this list's buffer. The bytes are copied WITHOUT per-element dup, so for a refcounted T this MOVES the source elements: the caller must not also release them. Reaching for it on a plain-data element type is the point — that is where it beats a push loop.

Drop every element and set the length to 0, KEEPING the capacity — Rust's Vec::clear. Use shrink_to_fit afterwards to release the buffer too.

Overwrite the live len() elements with a repeated byte via memset — the fast way to zero a bool / integer list.

Writes over the elements without dropping them, so it is only sound for a plain-data T: on a refcounted element type it strands every handle it overwrites. fill(value) is the type-safe form.

Set the length to exactly new_len, memsetting any newly exposed slots to a repeated byte.

Shrinking does NOT run destructors and growing does not construct anything, so — like fill_with_byte — this is for a plain-data T only; resize(new_len, value) is the type-safe form. Growing may reallocate and can panic on allocation failure.

The element at idx, read (a read projection). Panics if the index is out of bounds.

The element at idx, written (a mutable projection). Panics if the index is out of bounds.

index minus the length test. Codegen calls this only at a subscript the verifier proved in bounds (plans/backlog/SAFE_MODE_5B_CONTAINER_BOUNDS_ELISION.md).

index_mut minus the length test, on the same terms as index_unchecked.

Drops every live element and frees the buffer. Runs when the last reference to the list goes away, not at the end of the binding's scope.

Cycle-GC tracing. The elements live in a malloc'd buffer the compiler's auto-derived field walk cannot reach, so trace each element's buffer slot. tracer.visit takes the slot POINTER and reads it WITHOUT touching the element's reference count — a by-value managed handle would be dup'd then dropped, freeing a live element mid-collection.

Raw walk over the buffer: yields a *(T) into the list's buffer and leaves the list intact — for(list.iter(), ptr => ...), where into_iter consumes the list and yields values (D14; the iter / into_iter split every other std collection already had). Safe code reads elements with for(&list, x => ...); this is the pragma(Pragma.AllowUnsafe) form (decision 39).

The iterator holds the buffer pointer and the current length, not the list (B7b), so the list must outlive the walk, and must not grow or shrink during it: a reallocation invalidates the pointers already yielded.

The positions 0 .. len(), a Range(usize) that holds no handle to the list: the index cursor of decision 39 (plans/VALUES_BY_DEFAULT.md). Read each element through the list, xs(i), so every step re-derives it from the current buffer: a push during the walk is seen at the next step, and an index past a shrink is the out-of-bounds panic, never a read of a freed buffer. The range is fixed when it is made.

The first position (equal to the end for an empty collection).

Whether cur names an element.

The element at cur, read in place (a read projection). Panics if cur names no element.

The position after cur.

The element at cur, written in place (a mutable projection). Panics if cur names no element.

Remove CONSECUTIVE duplicates, keeping the first of each run — Rust's dedup. Only adjacent equals collapse, so [1,2,1] is unchanged; sort first if you want set semantics.

Whether self begins with prefix — Rust's starts_with.

Whether self ends with suffix — Rust's ends_with.

Whether any element equals value — a linear scan, O(n), stopping at the first match. Rust's Vec::contains.

Index of the FIRST element equal to value, or .None — a linear scan, O(n). Rust spells this iter().position(...); on a sorted list reach for binary_search instead.

Reverse the elements in place, O(n).

Exchanges raw slots bitwise, like swap, so no element is copied or dropped: RC-neutral however T is refcounted, and a move-only T reverses too.

Sort ascending by Ord. STABLE (D17): equal elements keep their input order, as sort does in Rust, Python, Java and Go.

O(n log n) with one usize index array plus scratch allocated for the merge — sort_unstable is the allocation-free heapsort for when order among equals does not matter.

Sort ascending by Ord WITHOUT preserving the order of equal elements — Rust's sort_unstable. Heapsort: O(n log n) worst case, in place, no allocation, no recursion (see _heapsort_by).

The default value of the type.

Create an independent clone of self.

The empty collection collect starts from.

Add one element to a partially-built collection and return it.

Sort by a caller-supplied strict "less" — less(a, b) is true when a must come before b. STABLE: equal elements keep their input order, matching Rust's sort_by. Use sort_unstable_by for the allocation-free heapsort.

Sort ascending by a KEY extracted from each element — Rust's sort_by_key. Stable, like sort_by, which it delegates to.

The key type is a method-level generic(K : Type), which the clause order requires to come BEFORE self; it is inferred from the closure at the call site, so xs.sort_by_key(p => p.age) needs no annotation.

Binary search over a list ordered by cmp — Rust's binary_search_by.

cmp reports how each ELEMENT orders against the target (.Less when the element comes first), so searching does not require constructing a T to compare against — which is the whole reason to reach for this over binary_search. .Ok(index) of a match (any one of an equal run), or .Err(insertion_index).

Non-overlapping chunks of size, in order — Rust's chunks. The final chunk is SHORT when the length is not a multiple of size.

PANICS on size == 0, as Rust does. Consumes the list (D20).

Overlapping windows of EXACTLY size, advancing one element at a time — Rust's windows. Yields nothing when the list is shorter than size.

PANICS on size == 0, as Rust does. Consumes the list (D20).

Sort by a caller-supplied strict "less" WITHOUT preserving the order of equal elements (heapsort). Rust's sort_unstable_by.

Keep only the elements pred accepts, in place and in order; the rejected elements are dropped. One pass: the survivors are collected into a fresh list, clear releases every original, extend moves the survivors back — O(n) with a single allocation, and every RC step is one of the module's proven public operations (push / clear / extend). The first cut compacted through raw pointers and double-released RC elements (the Linux-ASan heap-use-after-free on PR #313's first run; local ASan is non-functional, so CI was the first to see it); the second walked backwards over drain, which was O(n²) with an allocation per rejection (issues/fixed/array-list-retain-is-quadratic.md).

Append every element of other, consuming it — Rust's Vec::extend(other). extend_cloned(&other) appends clones and keeps other.

When other is the only handle to its list, the elements MOVE: one memcpy, and the emptied list is freed. While ArrayList is still a shared handle (until plans/VALUES_BY_DEFAULT.md's B8), another handle may share the list; the elements are then copied, so the other handle keeps them (lookahead D21's rule for the consuming iterators). That copy is decision 20's check, so a move-only T is E0901 here until B8.

Append a clone of every element of other, which is left as it was. Each element is cloned in place through other(i).

A clone of the element at index, or .None when index >= len() — get for an element that is not copied implicitly (decision 20). The element is cloned in place, never copied out first.

{ ArrayList } :: import("std/collections/array_list");
{ String } :: import("std/string");
(mut(names) : ArrayList(String)) = ArrayList(String).new();
names.push(`ada`);
assert(names.get_cloned(usize(0)) == .Some(`ada`), "a clone of the element");

A clone of the first element, or .None when empty.

A clone of the last element, or .None when empty.

Binary search over a SORTED list (ascending, sort's order): .Ok(index) of a matching element (any one of an equal run), or .Err(insertion_index) where the value would keep the order.

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

Advance the iterator from the back and return the previous value, or None when the two ends have met.

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

Advance the iterator from the back and return the previous value, or None when the two ends have met.

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

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