Landin prototype 3 — a generic container library
Current with specification 0.2.5. Its own findings Z1-Z19 are all resolved below.
This one was chosen because it presses on five things at once: parameterised types, concepts, allocator threading, escape rules and specialisation. A driver never instantiates anything and a parser barely does. A container library does nothing else.
D211 separates those semantic instances from optional dispatch specialization. Allocator size/alignment evidence works with specialization off; expected instance metadata alone does not prove the incoming provider. Hidden evidence and aggregate-result ABI positions remain even after a proved entry call becomes direct. A counted failing allocator's attempts, rollback and frees remain observable, as do initialized-prefix publication and retained origins. D187's narrow raw-storage unchecked regions add no optimizer assumptions. D210 reorders only explicitly optimal fields, never a container's natural layout; D209's numeric array loops do not turn arbitrary raw storage into initialized array values. These rules also preserve prototype 2's diagnostic provider and prototype 4's heterogeneous capability chains.
D221 requires static provider-entry selection to name one declaration across the distinct concept closure. A composed map or allocator concept cannot pick an operation by parent order; a shared ancestor contributes its entry only once. The paired static-entry collision/diamond fixtures pin that rule without changing the separate evidence tables or the uniquely named diagnostic and world entries used by prototypes 2 and 4.
[0910]'s field consumption also applies to a later copy of the containing container. Replacing the whole container restores its consumed fields; unrelated fields and known array elements remain live. An inout container must be restored before either success or failure reaches its caller, after applicable cleanup. runtime/r491-consumed-place-restoration exercises those storage paths and cleanup edges; its negative companions pin forbidden reads and exits. The rule also governs containers used by prototypes 2 and 4.
D224's wider integer folding applies to module-known images. Capacity and allocation arithmetic inside these container functions retains its source width and runtime overflow rules [0300]; folding is no exemption for a runtime size calculation.
Four containers, deliberately different in shape:
vec— a growing array: the one that reallocates, so it is where the borrow rule earns its keep or fails tosmall— inline capacity spilling to the heap: a fixed value parameter and a variant holding storagemap— open addressing: a composed concept, and no null to use as an empty markertree— arena-backed, with children as indices: the idiom the language keeps recommending, tested for once
Two conventions this file adopts, because calls could not be written without deciding them, and both follow the tour rather than inventing:
A type parameter that appears in the type of a value parameter is deduced and left out at the call, as sort(values) does at [1300]. An explicit generic call names every static formal in the one call list, as copy(t: u8, n: 4, source: bytes) does; it never mixes an explicit static actual with deduction. Explicit type arguments are therefore always named, never positional, which keeps positional arguments to ordinary runtime values.
Where a spelling had to be invented, the line is marked [Zn] and the question is written out at the end.
core/mem — allocation as a capability
The repository core/mem implements the allocator interface below, plus an explicit monotonic arena and a budgeted failing arena. Its private raw storage raw(t) (D151) supersedes the later slice_from sketch: the public storage(t) alias lets core/vec name that nominal identity without exposing its fields, and a checked one-slot transfer copies initialized values during growth. The initialized slice witness holds exactly that prefix: a complete typed store precedes each extension, and mem.used returns the witness from storage. It never turns capacity into a slice length; mem.replace checks an existing initialized index and declares its inserted value escaping.
For ordinary initialized storage, addr view[index] retains the slice's source origin [0790], as does an address selected through a pointer's .val. The descriptor may be copied into a local binding without making its backing frame-local. This does not permit returning an address into a local array or constructing a view over uninitialized slots. [1910] also checks stores through caller-owned storage: moving a non-escaping reference to another origin is retention, while a same-origin update remains valid. The private transfer transition uses an explicit raw destination address for both first and later slots before publishing the new witness; that boundary is not an exemption for ordinary container or application stores.
D222 strengthens writable from results: mem.used, vec.used and both inline/spilled branches of small.used retain their explicit container source. A helper needing module fallback storage must receive that destination as an argument and name it too. This does not require heap storage to live inside the container object or change the raw allocation boundary. Generic returned items and variant payloads use their instantiated reference permissions; read-only text views shared with prototypes 2 and 4 retain their dependencies.
The scalar side of that distinction is [0840]: lenof and other scalar operators copy no reference into their result. A saved length may survive a later container or descriptor mutation without keeping the old view alive. The reference itself may not. This also leaves prototype 1's DMA buffer escape, prototype 2's retained parser input and prototype 4's borrowed text and erased capability origins intact; no operand evaluation or storage lifetime rule is relaxed.
public out_of_memory: atom
The concept is the one from the tour at [1360], unchanged. Note what it settles for everybody: the error set of alloc is concrete. A concept entry is reached through a table, and [0960] forbids an inferred set where the set must be concrete, so an allocator that wanted an error of its own could not have one. Out of memory is out of memory, so that is the right answer here — but it is a general constraint on concept design that nobody has stated. [Z9]
public allocator: type = concept (provider: type) alloc: (inout a: provider, size: usize, alignment: usize) -> (p: ptr mut u8) ! out_of_memory free: (inout a: provider, p: ptr mut u8, size: usize) -> none end allocator
Three primitives every allocator needs and that the language does not name. They are the system-tool layer of [0490], so belonging to core and nowhere else is defensible — but core has to be able to say them, and that privilege should be written down rather than assumed. [Z3]
public offset: (p: ptr mut u8, n: usize) -> (q: ptr mut u8) = ... end public base_of: (t: type, s: []mut t) -> (p: ptr mut u8) = ... end public slice_from: (t: type, p: ptr mut u8, n: usize) -> (s: []mut t) = ... end
slice_from is where the honesty runs out, and it is worth being plain about it. It hands back a []t over storage holding no t at all. The language has no word for uninitialised memory: bindings must be assigned before use, nothing says that about the elements of a slice, and requiring t to have a zero image would rule out list(ptr node), which is exactly what the tree below needs. So the containers carry the invariant themselves — vec by its len, map by its state array. slice_from is where the promise is made rather than checked, which is [1730] with the check missing. [Z8]
The original relative align_up(used, alignment) sketch was insufficient for caller storage whose base address is not already aligned, and its addition could overflow. The hosted library replaces it with a checked internal operation over the absolute base address and the complete request:
allocation_offset: (base: ptr mut u8, used: usize, extent: usize, size: usize, alignment: usize) -> (offset: usize) ! out_of_memory = ... end
Zero alignment means byte alignment. Zero size is a valid allocation and may advance across alignment padding. Any request whose current address, aligned address, or end cannot be represented, or whose aligned extent does not fit, reports out_of_memory before allocator state changes.
D196 records the sketch's offset and base_of names as unnecessary for the implemented library. The actual allocator uses [0470]'s explicit conversion; [0810] describes its untracked result. This explicit caller-backed pool does not require a lexical arena block. D212 [0820] withdraws that block and its builtin parameter type: this explicit allocator remains ordinary source, with no-from allocation results and manual backing lifetime. Prototype 4 adds explicit bulk cleanup over a supplied provider; it does not make these results borrow the allocator or claim to detect helper-side-effect escapes. The later checked constructors require retainable backing, with explicitly named unchecked constructors for the local-buffer use shown in this sketch.
core/mem — a bump allocator over borrowed storage
The library names this allocator mem.arena and builds it with mem.arena_over(base, size) from a first byte and a length rather than a slice, returning it from base; the current representation is private and the checked constructor refuses tracked frame backing. Prototypes 2 and 4, the tour and core/mem all use that name. The sketch keeps bump and bump_over as its design record.
public bump: type = struct base: ptr mut u8 size: usize used: usize end bump
escaping, for a real reason: the bump keeps the buffer long after this call returns, so the caller has to prove the buffer outlives it. A buffer on the stack of a function that returns the bump is refused, and that is the bug this rule exists for.
public bump_over: (escaping buf: []mut u8) -> (b: bump) = b = (base: base_of(buf), size: lenof buf, used: 0) end bump_over bump_alloc: (inout a: bump, size: usize, alignment: usize) -> (p: ptr mut u8) ! out_of_memory = off := try allocation_offset(a.base, a.used, a.size, size, alignment) p = offset(a.base, off) a.used = off + size end bump_alloc
A bump frees nothing. The signature still takes the size, because the concept says so and a general allocator needs it.
bump_free: (inout a: bump, p: ptr mut u8, size: usize) -> none = ... end bump is allocator (alloc: bump_alloc, free: bump_free)
core/mem — an allocator that fails on purpose
This is the payoff of [1360] that almost nobody gets in C: the out-of-memory path of every container below is reachable from a test, by handing it this instead of the real one.
It is also the first type taking a constrained type parameter. The tour has list: type (t: type) and it has a constrained parameter on a function, but never the two together. [Z2]
public counted: type (provider: type is allocator) = struct inner: ptr provider left: u32 end counted public count_down: (provider: type is allocator, escaping inner: ptr provider, n: u32) -> (c: counted(provider) from inner) = c = (inner: inner, left: n) end count_down counted_alloc: (provider: type is allocator, inout c: counted(provider), size: usize, alignment: usize) -> (p: ptr mut u8) ! out_of_memory = fail out_of_memory when c.left == 0 dec c.left
Passing a pointer target where an inout is wanted. Surely intended, never shown. [Z12]
p = try provider.alloc(c.inner.val, size, alignment) end counted_alloc counted_free: (provider: type is allocator, inout c: counted(provider), p: ptr mut u8, size: usize) -> none = provider.free(c.inner.val, p, size) end counted_free
And here is the hole this file kept walking into. The line means "for any provider satisfying allocator, counted(provider) satisfies allocator", and there is nowhere to put the "for any provider". Written with a prefix binder, which is invented. [Z1]
(provider: type is allocator) counted(provider) is allocator (alloc: counted_alloc, free: counted_free)
core/mem — slices from an allocator
The new_slice/drop_slice sketch below preserves the original pressure, not the hosted library's allocation API. Spare capacity has no typed slice image: the private raw state and used expose only initialized items. mem.new(state, value) stores a complete value before returning its pointer; mem.delete releases that object through the same allocator. The byte-specific mem.new_bytes returns a byte_buffer holding the complete allocation extent, initializes all requested bytes, and exposes a borrowed slice through mem.bytes. mem.drop_bytes clears that owner and releases its original backing, rather than accepting a possibly shortened slice as allocation identity. Absent or disposed backing is a named one-atom pointer union under D206, not ptr(0) or a fabricated non-null allocation; repeated raw disposal reports raw_empty. No generic uninitialized new_slice is supplied. Copied aliases remain the caller's manual-lifetime responsibility. D220 keeps the consuming place at the descriptor binding or field: l.items may be consumed as a whole, while l.items[0] follows a slice's backing reference and is outside the sink-place form. A literal fixed-array element can itself hold a consumable descriptor. The small positive/r491-sink-contained-places derivative pins that distinction. D223 permits reading a container's count in a later argument of a call that sinks the whole container or its descriptor. Consumption waits for call entry; an argument that returns first leaves the pending place live. Entered calls still consume it before recovery. positive/r491-sink-call-entry derives the descriptor case and its early-exit restoration obligation; the overlap negative keeps an allocator passed by inout distinct from any consumed place.
sizeof and alignof applied to a type parameter. Specialised they are constants; compiled once against a table they are not, so the evidence has to carry the size and the alignment of the type as well as the concept's functions. [1310] describes the table as holding the functions and says nothing about layout. Without this no generic container can allocate at all. [Z4]
public new_slice: (t: type, provider: type is allocator, inout a: provider, n: usize) -> (s: []mut t) ! out_of_memory = raw := try provider.alloc(a, n * sizeof t, alignof t) s = slice_from(t: t, p: raw, n: n) end new_slice
sink, and it earns its place: after drop_slice the place the caller named is dead, so the obvious use-after-free is refused and it costs nothing at run time. What it is not is ownership. A slice descriptor is a copyable value: copy it first and the copy is refused nothing, so freeing through both is a double free this does not catch. sink is a use-after-consume check on one place. Affine values would be the other thing, and they are parked with a condition in ROADMAP.md's register. The catch: every caller below passes a struct field rather than a binding, and what sink means for a field is not stated. [Z13]
public drop_slice: (t: type, provider: type is allocator, inout a: provider, sink s: []mut t) -> none = return when lenof s == 0 provider.free(a, base_of(s), lenof s * sizeof t) end drop_slice
core/vec — a growing array
The parser-support core implements the subset with honest raw storage rather than the spare-capacity slice sketched below. It supplies construction, reserve, push, pop, indexed get, length, capacity and release. The hosted library adds used, which exposes only the initialized prefix with its storage-derived origin. The executable pointer-vector case already proves allocation rollback and publication order. Traversal uses for value in vec.used(list); a universal list conformance to [1320] is not supplied.
D194 hardens that implementation: reserve checks the byte product and push checks geometric doubling before provider calls; impossible arithmetic reports out_of_memory and preserves the old list. Copy and drain now use loops, with a real 65,536-item list exercising growth and release. Enabled zero-sized items keep logical slots backed by paired zero-byte allocation/free requests. The earlier spare-capacity slice sketch below remains historical design pressure, not the implemented representation or arithmetic contract.
import core/mem public empty: atom
The capacity is the length of the slice; len is how much of it holds real values. Elements at and above len are the storage that slice_from made a promise about and nobody has written yet.
public list: type (t: type) = struct items: []mut t len: usize end list public new_list: (t: type) -> (l: list(t)) = l = (items: [], len: 0) end new_list grown: (cap: usize) -> (n: usize) = n = if cap == 0 then 8 else cap * 2 end if end grown
The counted-prefix headers below share D219's endpoint context rule with prototype 1's receive loop, prototype 2's stored diagnostics and prototype 4's filter chain. positive/r491-range-endpoint-context pins their 0..<count shape and the tour's 1..<lenof data; the literal takes the usize endpoint's type before the body is checked.
The local type-scope witness positive/r491-local-type-scope derives a small list-element copy from this shape. Its local t: t = source.items[0] uses the enclosing generic type formal before introducing the runtime name (D218). The returned element retains its source under [0790].
The allocator is threaded, not stored, and the reason turned out sharper than the visibility argument that was made for it. If list stored its allocator it would be list(t, provider), so a list in an arena and a list on the heap would be different types and no function could take both. Threading keeps the type parameterised by t alone. The price is one more argument at every mutating call, which is what the code below reads like: judge it there. [Z10]
public reserve: (t: type, provider: type is mem.allocator, inout l: list(t), inout a: provider, want: usize) -> none ! mem.out_of_memory = return when want <= lenof l.items fresh := try mem.new_slice(t: t, provider: provider, a: a, n: want) for k in 0..<l.len do fresh[k] = l.items[k] end for mem.drop_slice(a, l.items) l.items = fresh end reserve
escaping on v reads oddly until t is taken seriously. For t = u32 it says nothing: [0840] already has it that a value holding no references is unconstrained, so the obligation is vacuous and the caller proves nothing. For t = ptr node it is exactly right, since the list keeps what v refers to. One word covers both, because the origin travels with the type. [Z6]
public push: (t: type, provider: type is mem.allocator, inout l: list(t), inout a: provider, escaping v: t) -> none ! mem.out_of_memory = if l.len == lenof l.items then try reserve(l, a, grown(lenof l.items)) end if l.items[l.len] = v inc l.len end push public pop: (t: type, inout l: list(t)) -> (v: t) ! empty = fail empty when l.len == 0 dec l.len v = l.items[l.len] end pop
One accessor, since 0.1.0. It hands out the widest permission the storage has, and a caller who wants less writes 'xs: []i32 = vec.used(l)' and relaxes it by [0440]. The pair of accessors that every language with deep const ends up needing is not needed here. The from clause says the one thing the signature could not otherwise: the list has to hold still while the view is alive.
public used: (t: type, l: list(t)) -> (s: []mut t from l) = s = l.items[0..<l.len] end used public release: (t: type, provider: type is mem.allocator, inout l: list(t), inout a: provider) -> none = mem.drop_slice(a, l.items) l.items = [] l.len = 0 end release
The following original family-conformance sketch remains design pressure [Z1]. Its item signature is source-free, as [1320] requires, whereas a reference-valued element read from vector storage retains from that storage. Those contracts do not match. The library therefore traverses vec.used(list) with the existing slice traversal rules instead of discarding the returned origin or widening iterable. negative/iterable-retained-item-source pins the exact signature refusal. The cursor sketch below is not an implemented conformance.
list_first: (t: type, s: list(t)) -> (c: usize) = 0 end list_at_end: (t: type, s: list(t), c: usize) -> (yes: bool) = c >= s.len end list_item: (t: type, s: list(t), c: usize) -> (v: t) = s.items[c] end list_next: (t: type, s: list(t), c: usize) -> (c2: usize) = c + 1 end (t: type) list(t) is iterable (cur: usize, item_type: t, first: list_first, at_end: list_at_end, item: list_item, next: list_next)
core/small — inline capacity, spilling
import core/mem import core/vec
A fixed value parameter on a type. [1520] gives one on a function and [1350] a type parameter on a type; a small vector is the ordinary shape that wants both. [Z2] Restricted to a t with a zero image, and that restriction is the honest form of [Z8]: the inline slots have to hold something and [0540] gives no honest value for a t without one. So small(ptr node, 4) does not exist in this inline shape [0510]. Raw storage now lets vec(ptr node) exist, but it does not give [capacity]t an initialized image and therefore does not remove this constraint. The current resolution for fixed parameters gives an unconstrained fully applied struct instance the nominal identity (template, normalized actual tuple) and substitutes fixed bounds, nested ordinary structs and existing variants without runtime formals or a synthetic declaration. The checker now checks the is zeroable constraint through its closed compiler conformance family (D143). The executable pointer-vector pressure case derived the raw storage transitions used by the spilled list: capacity is distinct from the initialized prefix, which grows and shrinks one tail slot at a time and must be empty before the allocation is freed. The hosted library composes that list behind the variant rather than exposing a capacity slice; nominal parameterization and constraint lookup are no longer what this sketch waits on.
public small: type (t: type is zeroable, fixed capacity: u32) = struct len: usize store: variant inline: (buf: [capacity]t) | spilled: (items: vec.list(t)) end store end small public new: (t: type is zeroable, fixed capacity: u32) -> (s: small(t, capacity)) = s = (len: 0, store: inline(buf: zeroed)) end new
zeroed is honest now, because t is constrained to have a zero image. What that costs is that the shape does not exist for the t which wanted it most. [Z8]
The match bindings use D85/D121's resolved alias rule. inout names the selected payload storage rather than a whole-array copy, so the final arm change occurs only after the private list no longer reads buf. [Z7]
public push: (t: type is zeroable, fixed capacity: u32, provider: type is mem.allocator, inout s: small(t, capacity), inout a: provider, escaping v: t) -> none ! mem.out_of_memory = match s.store inline (inout buf): if s.len < usize(capacity) then buf[s.len] = v inc s.len return end if fresh := vec.new_list(t: t) try vec.reserve(fresh, a, first_capacity(capacity)) for k in 0..<s.len do try vec.push(fresh, a, buf[k]) end for try vec.push(fresh, a, v) s.store = spilled(items: fresh) inc s.len spilled (inout items): try vec.push(items, a, v) inc s.len end match end push
The inline arm assigns to s.store only after the last read through buf. D85/D121 make the binding an alias and [0830]'s liveness rule permits that final publication while refusing a caller's spill when a used view remains live. Scalar payload aliases obey the same storage lifetime: a later write, derived-address use or pending cleanup still keeps the old payload live. runtime/r491-payload-alias-last-use and its negative companion exercise last-use publication, independent siblings and refused retags. [Z7]
public used: (t: type is zeroable, fixed capacity: u32, inout s: small(t, capacity)) -> (v: []mut t from s) = v = match s.store inline (inout buf): buf[0..<s.len] spilled (items): vec.used(items) end match end used
A match as an expression, from [1080]. Both arms yield []t, and the inline arm yields a slice into the small vector itself — which is exactly what the from clause has to say, or the caller could spill the vector while holding the view. The inout source and payload alias keep that origin exact; no copy or integer conversion erases it. [Z7]
core/map — open addressing, without null
import core/mem public missing: atom public equatable: type = concept (key_type: type) eq: (a: key_type, b: key_type) -> (yes: bool) end equatable
A composed concept, per [1340]. A type conforming to hashable needs its own equatable conformance as well: the composed declaration supplies only what it adds. The tour states that rule and then shows button is widget supplying only focus, with no sign of the drawable and clickable conformances it must also have. [Z11]
public hashable: type = concept (key_type: type) is equatable hash: (k: key_type) -> (h: u64) end hashable
No null, so no key value can mean empty, and a sentinel key would be a lie for key_type = ptr node in any case. A parallel state array is what a good implementation does anyway, for the probe's cache behaviour, so the missing null pushed the design the right way without anybody arguing about it.
slot_free: atom slot_used: atom slot_dead: atom slot: type = slot_free | slot_used | slot_dead public map: type (key_type: type is hashable, value_type: type) = struct state: []slot keys: []key_type vals: []value_type len: usize dead: usize end map public new_map: (key_type: type is hashable, value_type: type) -> (m: map(key_type, value_type)) = m = (state: [], keys: [], vals: [], len: 0, dead: 0) end new_map
hash returns u64 and the index is usize, which is u32 on the small target. usize(key_type.hash(k)) would compile and then trap in the field on any key wider than a byte or two, so the reduction has to happen in u64 first. No implicit conversion caught a portability bug that C would truncate silently and Rust would wrap silently, and it caught it while reading rather than while running.
index_of: (key_type: type is hashable, k: key_type, n: usize) -> (i: usize) = i = usize(key_type.hash(k) % u64(n)) end index_of public get: (key_type: type is hashable, value_type: type, m: map(key_type, value_type), k: key_type) -> (v: value_type) ! missing = n := lenof m.state fail missing when n == 0 mut i := index_of(k, n) loop do s := m.state[i] break when s == slot_free if s == slot_used and key_type.eq(m.keys[i], k) then v = m.vals[i] return end if i = (i + 1) % n end loop fail missing end get
The sketch below counts tombstones toward the three-quarter threshold. The executable map instead reuses available dead or free buckets during churn.
The executable D198 map grows only when a tombstone-free table is crowded. Its growth uses three fallible acquisitions and a publication-last rollback transaction. Its entries() cursor and next_entry operation follow linked live buckets in insertion order rather than the raw dense prefix, which still contains removed values. Reference-bearing entries remain from map; a scalar copy retains no view. Cursors are manual positions: restart after mutation and never resume one on a different map. This supplies the complete derivative's enumeration without making the public map composition opaque or changing prototype 4's retained-reference obligations.
crowded: (key_type: type is hashable, value_type: type, m: map(key_type, value_type)) -> (yes: bool) = yes = (m.len + m.dead + 1) * 4 > lenof m.state * 3 end crowded
place never allocates and never fails, because the caller has already made room. That is why it can be called from inside rehash without the cleanup problem below repeating.
place: (key_type: type is hashable, value_type: type, inout m: map(key_type, value_type), escaping k: key_type, escaping v: value_type) -> none = n := lenof m.state mut i := index_of(k, n) loop do s := m.state[i] if s == slot_used and key_type.eq(m.keys[i], k) then m.vals[i] = v return end if if s <> slot_used then if s == slot_dead then dec m.dead end if m.state[i] = slot_used m.keys[i] = k m.vals[i] = v inc m.len return end if i = (i + 1) % n end loop end place
Three allocations that can each fail, and the cleanup is triangular: the second failing frees one, the third failing frees two. None of that is written here. undo entries are registered where control reaches them, so the triangle comes out of the order rather than out of the text. [Z19]
rehash: (key_type: type is hashable, value_type: type, provider: type is mem.allocator, inout m: map(key_type, value_type), inout a: provider, want: usize) -> none ! mem.out_of_memory = ns := try mem.new_slice(t: slot, provider: provider, a: a, n: want) undo mem.drop_slice(a, ns) nk := try mem.new_slice(t: key_type, provider: provider, a: a, n: want) undo mem.drop_slice(a, nk) nv := try mem.new_slice(t: value_type, provider: provider, a: a, n: want) undo mem.drop_slice(a, nv) old_state := m.state old_keys := m.keys old_vals := m.vals
Committed from here, and nothing fallible follows, which is the discipline undo asks for: an entry cannot be called off, so a failure after the handover would free what m now owns.
m.state = ns m.keys = nk m.vals = nv m.len = 0 m.dead = 0 for k in 0..<want do m.state[k] = slot_free end for for k in 0..<lenof old_state do if old_state[k] == slot_used then place(m, old_keys[k], old_vals[k]) end if end for mem.drop_slice(a, old_state) mem.drop_slice(a, old_keys) mem.drop_slice(a, old_vals) end rehash public insert: (key_type: type is hashable, value_type: type, provider: type is mem.allocator, inout m: map(key_type, value_type), inout a: provider, escaping k: key_type, escaping v: value_type) -> none ! mem.out_of_memory = if crowded(m) then try rehash(m, a, if lenof m.state == 0 then 16 else lenof m.state * 2 end if) end if place(m, k, v) end insert public remove: (key_type: type is hashable, value_type: type, inout m: map(key_type, value_type), k: key_type) -> none ! missing = n := lenof m.state fail missing when n == 0 mut i := index_of(k, n) loop do s := m.state[i] fail missing when s == slot_free if s == slot_used and key_type.eq(m.keys[i], k) then m.state[i] = slot_dead dec m.len inc m.dead return end if i = (i + 1) % n end loop end remove public release_map: (key_type: type is hashable, value_type: type, provider: type is mem.allocator, inout m: map(key_type, value_type), inout a: provider) -> none = mem.drop_slice(a, m.state) mem.drop_slice(a, m.keys) mem.drop_slice(a, m.vals) m = new_map(key_type: key_type, value_type: value_type) end release_map
core/tree — arenas and indices, the idiom under test
import core/mem import core/vec public no_such_node: atom
A handle, not a pointer. u32 rather than usize, because halving the width of every edge is the reason for doing this at all.
public node_id: type = distinct u32
A variant case with no payload, written bare. It is an atom, and [1700] holds that atoms are the same idea wherever they appear, so this ought to need no decision — but every variant in the tour carries a payload, so the spelling has never appeared. [Z14]
public node: type = struct name: utf8 kind: variant leaf | branch: (first: node_id, count: u32) end kind end node
The whole tree is one list. Its edges are indices, but each node's utf8 name still retains text backing. Retained names therefore require escaping inputs, and a borrowed node result derives from the tree. Index edges do not make the node representation serializable: copying a text descriptor does not copy or relocate its backing. [0860]'s shallow reference-field limits still apply to the retained names.
The library uses a widened distinct usize representation rather than the compact historical sketch above for node_id. Construction and extraction are explicit; the id and ordinal convenience functions retain that same boundary. This replaces the earlier one-field nominal workaround. New branches may name only existing contiguous children. Empty branches are allowed, and shared children are counted once per incoming path. Each immutable node stores its checked usize leaf total and a two-word cumulative total, so range sums and queries use constant work and bounded stack space even for deep structures. Overflow is a declared refusal before publication. The recursive code below remains the equivalent counting sketch, not the library's execution strategy.
The hosted library corrects that original representation claim without rewriting the historical sketch: name is a reference-bearing utf8 value. A name produced by text.from_bytes or text.from_c retains its input origin, so storing it in a tree requires the corresponding escaping argument or longer-lived backing. Neither the tree nor the text adapter copies encoded bytes, and a raw flash image cannot serialize those references as offsets by assumption.
public tree: type = struct nodes: vec.list(node) end tree public new_tree: () -> (t: tree) = t = (nodes: vec.new_list(t: node)) end new_tree public add_leaf: (provider: type is mem.allocator, inout t: tree, inout a: provider, escaping name: utf8) -> (id: node_id) ! mem.out_of_memory = id = node_id(u32(t.nodes.len)) try vec.push(t.nodes, a, (name: name, kind: leaf)) end add_leaf
Children are contiguous, so a branch is a first index and a count. That only works if the children were added together, which is the usual discipline for this representation and better said out loud than discovered.
public add_branch: (provider: type is mem.allocator, inout t: tree, inout a: provider, escaping name: utf8, first: node_id, count: u32) -> (id: node_id) ! mem.out_of_memory = id = node_id(u32(t.nodes.len)) try vec.push(t.nodes, a, (name: name, kind: branch(first: first, count: count))) end add_branch public get: (t: tree, id: node_id) -> (n: node from t) ! no_such_node = fail no_such_node when usize(u32(id)) >= t.nodes.len n = t.nodes.items[usize(u32(id))] end get
The original counting sketch recurses over indices. Its numeric result carries no origin; a node or name read along the way still carries the stored text's lifetime. The append-only library caches this same total when adding a branch.
public count_leaves: (t: tree, id: node_id) -> (n: u32) ! no_such_node = this := try get(t, id) n = match this.kind leaf: 1 branch (first, count): begin mut total: u32 = 0 for k in 0..<count do total += try count_leaves(t, node_id(u32(first) + k)) end for total end end match end count_leaves
A match arm whose value takes several statements has to open a bare block to get one. That is [1080] working as designed, and it reads heavily. Worth watching before deciding it needs anything.
app — using all of it
import core/mem import core/vec import core/map import core/tree import core/sort (sort, ordered)
Hashing is one of the few places where wrapping is the point, and the language makes it say so: a plain * would trap here on the first key big enough to overflow the multiply.
hash_u32: (k: u32) -> (h: u64) = u64(k) *% 0x9E37_79B9_7F4A_7C15 end eq_u32: (a: u32, b: u32) -> (yes: bool) = a == b end u32 is map.equatable (eq: eq_u32) u32 is map.hashable (hash: hash_u32) less_i32: (a: i32, b: i32) -> (yes: bool) = a < b end i32 is ordered (less: less_i32)
Sixty-four kilobytes of static storage, one bump allocator over it, and nothing else in this program allocates anywhere. On the small target that is the whole memory story, and it is legible in four lines.
mut pool: [64 * 1024]u8 = zeroed run: () -> none ! mem.out_of_memory = mut a := mem.bump_over(pool[0..<lenof pool])
The bound above is the concrete pressure for D136's closed fixed-expression fold. It is arithmetic over literals, not a hidden call or compile-time user execution, and produces the same canonical count a literal bound would. The same fold can answer zero: D136 accepts both [0]t and an admitted expression that folds to zero, while keeping empty literals and zero-length repetition separate.
A list, filled and sorted with the generic sort from [1290].
mut numbers := vec.new_list(t: i32) for k in 0..<20 do try vec.push(numbers, a, 20 - i32(k)) end for sort(vec.used(numbers))
A map from those to their squares.
mut squares := map.new_map(key_type: u32, value_type: u32) for n in vec.used(numbers) do try map.insert(squares, a, u32(n), u32(n) * u32(n)) end for nine := map.get(squares, 3) else 0
A tree: three leaves under one branch.
mut t := tree.new_tree() first := try tree.add_leaf(t, a, "a") _ = try tree.add_leaf(t, a, "b") _ = try tree.add_leaf(t, a, "c") root := try tree.add_branch(t, a, "root", first, 3) total := tree.count_leaves(t, root) else 0 report(nine, total) end run
What generics cannot do, from [1400]: one list holding values of different types. The list is generic in exactly one type, and that type is the two-word pair. drawable and canvas are the tour's, from [1340].
draw_all: (items: vec.list(any drawable), target: ptr mut canvas) -> none = for w in vec.used(items) do w.draw(target) end for end draw_all
The any C implementation now pins that erased element as D145's direct-concept type and D147's two-word data/table pair. Its object-safe draw entry receives the hidden data pointer first, while the list/slice storage carries the pair and D146's pointee origin rather than copying the hidden object. The hosted library's bounded reference transport fixtures additionally carry pointer and slice fields through generic construction, copy and return, and deduce the same erased concept back from a nominal actual tuple. runtime/fixed-array-reference-shapes adds genuine singleton and larger pointer arrays, nested slices and fixed-array elements through generic normalization, typed pointer stores, copies and slicing. Allocator-backed initialized views are exercised by runtime/core-mem-initialized-prefix and runtime/r420-reference-provider-matrix, which retain the stored pointer and evidence identities across actual container growth.
WHAT THIS ONE FOUND
The resolutions below cite the pre-release revisions this specification passed through, 0.0.1 to 0.0.17, on the way to 0.1.0. They are kept because when one thing was settled relative to another still carries information.
Nineteen, which is more than the first two prototypes together, and that is the expected shape: a driver uses the language's edges and a container library uses its middle. Four of them mattered more than the rest — Z1, which nothing works without; Z5, the borrow rule stopping one step short of where containers need it; Z16, what a parameter convention means for a reference; and Z19, the first concrete evidence in the errdefer argument rather than another opinion about it.
Fourteen went into tour 0.0.8, Z1 among them and Z15 as the one observation that forced nothing. Z5 and Z16 went into 0.0.9 together, having turned out to be one question. Z13 and Z18 went into 0.0.10, both settled by asking what the compiler already knows, and Z19 into 0.0.11 as undo. All nineteen are worked in.
Z1 A conformance for a parameterised type has nowhere to put its quantifier. "counted(A) is allocator" and "list(T) is iterable" mean "for any A" and "for any T", and there is no way to say so. Written here with a prefix binder,
(T: type) list(T) is iterable (Cur: usize, Item: T, ...)
which reads acceptably and puts the binder where every other binder in the language is: left of what it introduces. The functions supplying the entries are themselves generic, and the conformance's instantiation supplies their type argument, leaving a function of exactly the concept's shape — so nothing new is needed beyond the binder itself.
This is the finding of the file. Without it there is no generic container that can be traversed, sorted, or handed to any other generic code, so nothing above works at all.
The hosted library executes the quantified allocator case directly: failing.counted(A) has an ordinary parameterized conformance for every A is mem.allocator, and wraps both the fixed pool and hosted heap.
Z2 A type declaration needs the same parameter kinds a function signature has. map wants a constrained parameter, map: type (K: type is hashable, V: type), and small wants a fixed value parameter, small: type (T: type, fixed N: u32). [1350] shows only a plain type parameter and [1520] shows fixed only on a function. Nothing here suggests a difficulty; it needs saying.
Z3 RESOLVED by [0500], [0510], D151 and D152. The implemented containers do not need a general pointer-to-slice conversion: core/mem performs checked pointer arithmetic inside private raw storage and transfers initialized slots directly. slice_from is declined because it would recreate Z8's false claim. The original finding follows.
Slices and pointers have no stated way between them, and every allocator needs both directions plus pointer arithmetic. Written here as offset, base_of and slice_from in core. A core-only privilege is defensible under [0490], but it should be stated rather than assumed, because the alternative reading is that the language cannot express its own allocator.
Z4 RESOLVED by the generic evidence schema. Evidence begins with the represented type's target usize size and alignment, followed by direct concept functions in declaration order. The semantic positions are target-neutral; Linux x86-64 and the synthetic 32-bit description derive different physical offsets and extents from their own pointer facts. A constrained generic instance receives that table as a hidden argument, so the same schema serves a later shared or any consumer without making a host width part of the language.
The original finding, for the record.
sizeof T and alignof T on a type parameter are constants when the call is specialised and are not when it is compiled against a table. The evidence therefore has to carry the size and alignment of the type as well as the concept's functions. [1310] describes the table as holding the functions and is silent about layout.
Z5 RESOLVED at 0.0.9, together with Z16, which turned out to be the same question from the other side. A returned reference names what it was derived from; the convention on that parameter says whether the view reads or writes, and the caller knows the source must hold still. No clause means an independent result, which is what keeps two live allocations out of one allocator legal — the thing that killed option (a) below. Derivation stops at the three primitives of [0500], so the allocator does not have to claim its storage borrows it. Written rather than inferred, which also removed every carve-out at the edges. Option (c) as set out here, with the polarity kept: say what borrows, not what is fresh.
The original finding, for the record.
The accessor hole, and the one that deserved the most thought.
xs := vec.used(numbers) try vec.push(numbers, a, 5) -- reallocates use(xs) -- stale
[0830] catches this when the view is taken directly, xs := l.items, because the derivation is visible in one expression. Through a function it is not, and reading a container through an accessor is the ordinary way to read one — so the most likely dangling-slice bug in the library sits exactly where the rule stops.
Three ways out, none free:
- (a) Conservative: a reference-typed result borrows every reference-typed argument. Purely local, no annotation. It also marks new_slice(a, n) as borrowing the allocator, which would forbid a second allocation while the first slice is alive. That is not a corner case, that is allocation.
- (b) Leave it, and list it in [0860] with the other holes. Honest, cheap, and leaves the commonest failure unguarded.
- (c) Mark it, as the dual of escaping. escaping says the callee keeps a reference to an argument; the new word says the caller does. One word, local, no interprocedural analysis, symmetric with something already present.
By [1710] this is a candidate, not a decision: the programmer must say it, the compiler cannot work it out locally, and it is the missing half of a mechanism that exists. What it does not do is let two old mechanisms leave, so it should be argued rather than slipped in, and (b) is a legitimate answer.
Z6 RESOLVED at 0.0.8, written into the tour at [0780]: escaping on a generic value parameter says the right thing at both extremes with no special case: vacuous for T = u32, since [0840] already has it that a value holding no references is unconstrained, and exact for T = ptr node. A pleasant result, worth writing down because it looks wrong at first reading.
Z7 A pattern binding needs a stated convention. push_small wants to write into the payload it matched, and whether a binding aliases the payload or copies it is not said. For a [N]T payload the difference is a whole array copy, and for small_used the difference is between a valid slice and a dangling one. The mechanism to reuse is obvious — in, inout and sink are already the parameter conventions — which is [1710]'s first line exactly. Two questions come with it: whether an inout binding borrows the matched value for the arm, and what happens when the arm assigns to the variant field it is bound out of.
Z8 RESOLVED by [0510] and D151. core/mem owns a private raw(T) whose capacity and initialised prefix are distinct. Its public operations admit the next slot, read only that prefix, release only its tail and dispose only at zero; invalid requests are declared outcomes. Transactional growth copies into a private replacement and publishes it only after the old prefix is drained. The caller still owns pointer validity, alignment and the capacity-derived allocator extent.
D198 applies that state machine to the map without the sparse []K and []V claim in the sketch above. Fully initialized bucket records name positions in dense initialized K/V prefixes. A free bucket appends both real values; a reused tombstone replaces both real values at its existing dense position; and rehash transfers only used positions. Neither K nor V acquires a zero-image constraint, and no spare-capacity slice is forged.
The original finding, for the record.
There is no notion of uninitialised storage, and a container cannot avoid having some. slice_from returns []T over memory holding no T. Requiring a zero image would forbid list(ptr node), which the tree needs, so that is not the answer. The containers hold the invariant themselves and it works, but the type []T claims more than is true between the allocation and the write. Either core's privilege covers this too, or there is a separate raw-storage type; one of the two should be said.
Z9 RESOLVED by [1360], D152 and D197. mem.allocator fixes out_of_memory as the concrete declared result of every provider. The arena, fixed pool, hosted heap, generic counted wrapper and pointer vector execute both sides of that contract; the wrapper distinguishes its own deterministic refusal from a delegated provider refusal. The original finding follows.
A concept entry must have a concrete error set, because it is reached through a table and [0960] forbids an inferred set there. So the allocator concept fixes out_of_memory for every allocator that will ever exist. Right for allocation, but it is a general constraint on concept design that nobody has written down.
Z10 RESOLVED by [1360] and D152. The implemented vec.list(T) stores only mem.storage(T); every operation that can allocate receives its provider and state as ordinary arguments. The original finding follows.
Threading the allocator rather than storing it holds up, and for a better reason than visibility. A stored allocator makes the container list(T, A), so a list in an arena and a list on the heap become different types and no function takes both. Threading keeps the type parameterised by T alone. The cost is one more argument at every mutating call.
Z11 [1340] says a conformance is declared explicitly even when the body is empty, then shows button is widget supplying only focus, with no sign of the drawable and clickable conformances it also needs. The rule is right; the example undercuts it.
D198 executes the rule at the map boundary: a concrete K declares both map.equatable and map.hashable, and the map's K is hashable constraint dispatches equality through the separate parent evidence.
Z12 Passing a pointer target where an inout is wanted, A.alloc(c.inner.val, size, align). Ordinary and surely intended, never shown. RESOLVED by [0900] and D149: the target is an ordinary place, one provably identical binding-rooted path cannot be passed twice, and aliasing through distinct pointer paths remains outside the local guarantee. The hosted library executes this exact shape in failing.counted(A): the wrapper retains ptr mut A, dereferences it for allocation and free, and requires a writable actual without requiring a module-global provider.
Z13 RESOLVED at 0.0.10. sink takes a place, and a field of a binding is a place, so every call in this file stands as written. The path must be rooted in a binding with no dereference and no computed index — the line where the analysis is still provable. A sunk place is dead until assigned again, which closes the window between the release and the repointing that a temporary binding would have left open, and a place sunk out of an inout parameter must be assigned again before returning.
The original finding, for the record.
sink on a struct field. drop_slice takes sink s: []T and every caller passes l.items rather than a binding. Killing a binding is well defined; killing a field is not, and every caller here reassigns the field immediately afterwards, which suggests the rule wants to be about the assignment rather than about the field.
Z14 A variant case with no payload, written bare: leaf | branch: (...). It is an atom and [1700] holds that atoms are one idea everywhere, so this ought to need no decision — but every variant in the tour carries a payload, so the spelling has never appeared.
Z15 Not a gap, an observation. Nothing here wanted a label, a break with a value or a complete clause, which is the second prototype in a row to say so — see Y4. The map probes were written with loop, break and a fail after the loop, and read better for it.
Z16 RESOLVED at 0.0.9 with Z5. The conventions read the same for both kinds of parameter — may I write to what you gave me — and on a reference that reaches the viewed storage, not only the binding. const in the type was weighed and declined: it answers only this half, leaves Z5 untouched, and would have been the language's first implicit conversion.
The original finding, for the record.
What a parameter convention means for a reference type is not stated, and it is the same question as whether a pointer is to mutable or immutable storage.
sort at [1290] takes inout data: []T and writes through it, so the convention evidently governs the storage the slice views, not the slice value. But used takes l as in and hands back a []T that sort then writes through — so a read-only parameter produced a writable view of the same bytes, and nothing complained. The same holds for ptr: nothing says whether ptr T may be written through, or whether that depends on how the pointer arrived.
Two coherent answers. Either the convention governs only the binding, and writability lives in the type — which means a second pointer and slice type and is a large change. Or the convention governs the viewed storage, in which case a slice returned from an in parameter must be read-only, and there has to be a way to say which of the two a returned reference is. The second is smaller and fits Z5's option (c), since both want a word about what comes back rather than what goes in.
Z17 [0710] says anonymous struct values take their type from context and then says they never flow into a same-shaped named type — and its own example, here: point = (x: 1.0, y: 2.0), does exactly that. The coherent reading is the one the number literals already use: a struct literal is untyped and takes a named type from context, whereas a value already typed as an anonymous struct, such as a return list, does not convert to a named one. Every constructor above depends on this, so the wording needs fixing.
Z18 RESOLVED at 0.0.10: nothing is written at the call site. A convention belongs to the declaration and appears nowhere else. The marker would have bought legibility rather than safety, since a caller that misuses what it got is told so at its next use, and escaping already puts an obligation on the caller from the signature alone. The three examples were made to agree, and [0780]'s was a bug rather than a third spelling.
The original finding, for the record.
How an inout argument is written at the call site is inconsistent in the tour. [0830] writes push(inout l, v); [0980] writes process(source: src, target: dst, owned: buf) with no marker; and [0780] writes push(addr head, n) where the parameter is inout head: ptr node, which would need the argument to be head, not its address. Three examples, three spellings.
It matters more than it looks. With a marker, sort(vec.used(...)) becomes sort(inout vec.used(...)), which is absurd for a value nobody can observe afterwards — so a marker pushes toward Z16's second answer, where writability belongs to what is returned rather than to the argument. Without one, an ordinary call gives no sign that it changes its argument, which is a strange silence in this language. Decide it, and fix the three examples.
Z19 RESOLVED at 0.0.11 as undo, and the argument moved twice on the way, so both corrections belong here.
The hosted library adds the real hosted-heap pressure the original resolution was waiting for: runtime/hosted-heap-provider observes both old and replacement vector allocations live during growth, then observes their exact extents released. runtime/r420-failing-providers also injects the replacement failure over a two-slot reclaiming pool, proves the old pointer vector remains intact, then permits one retry, observes a successful replacement, and observes eventual exact release of both allocation extents.
D198 supplies Z19's original three-acquisition case. Map rehash allocates its initialized bucket records, key storage and value storage in order. The three injected failure stages release zero, one and two replacements; each retry on the six-slot reclaiming pool succeeds, successful publication releases the three old extents, and final release leaves no live extent.
First, this finding overstated its own case. A flag and a conditional defer is linear, not quadratic — three lines per resource, however many there are. Only the else chain written above was quadratic. So it was never about line count, and the declined-errdefer position held up better than this said.
What survives is the failure mode. Forgetting to set a flag frees storage that is still in use, and under an arena, where free does nothing, that mistake is silent until somebody runs the same container on a real allocator. The workaround is a trap that the usual test environment hides, which is a different and worse thing than being verbose.
Second, the shape. A cancellable defer was considered and dropped: the cancel always sits where the block succeeds, so it is hand-made bookkeeping for a question the block's exit already answers. And defer with an argument was dropped because it reads as a call. What went in is a word of its own — to defer is to do it later, and this may never be done at all.
The original finding, for the record.
rehash makes three allocations that can each fail; the second failing has to free one, the third has to free two.
The prototype's core/tree sketch chose compact u32 edges. The executable core/tree now uses distinct usize IDs, usize branch interval counts and cached leaf totals. A 64-bit tree can therefore name nodes and count shared paths beyond u32; a 32-bit tree keeps 32-bit fields. The sketch above remains as the original design pressure.