core: Buffer<Item> as the heap storage primitive #54

Closed
opened 2026-10-05 21:07:14 +00:00 by orion · 11 comments
Collaborator

Context

Buffer<Item> joins Array in std/core: a growable heap sequence with an in-place promise and swapRemove. ECS columns (#92), the rebuilt collections (#55) and tensors stand on it. This issue is commit 2 of 2: the std/core type, its prelude export, its conformance programs and its docs. The compiler side is #299 (commit 1) and has to be merged and in a published seed first.

Source

Decisions (made in refinement; the design record stays the specification)

  • Where: std/core/src/buffer.trb, re-exported from std/core/src/lib.trb and std/prelude like Array (public use Array, ... from "std/core"). std/core cannot depend on std/collections, so Buffer implements only what core owns: Iterate<Item>, Length, MutableIndex<Int, Item>, MutableSlice, plus Equals, Show, Hash as extends (items in brackets, ordered hash with combineHashes), written like the ones at the end of array.trb. Joining the List/Collection family and Bytes becoming Buffer<UInt8> is the follow-up #300, not this issue.
  • Representation: public native type Buffer<Item> over the same runtime list as ArrayList (RuntimeKind.ListStorage; #299 registers it). No new C, no new torb_ symbol, nothing in the VM beyond the shared table.
  • The in-place promise is the existing runtime behaviour made a documented contract: buffer[i] = x, set, append, insert, removeAt, swapRemove, replace, reverse, clear change the storage in place whenever it has one owner; they copy once (copy on write) only when the Buffer value has been copied (const b = a, passed or captured by value) and is then written. The doc comment states exactly this and nothing stronger.
  • slice copies. ArrayList.slice shares storage, so a live slice silently turns the next write into a copy - the trap a frame budget cannot have. Buffer.slice is TorbScript (withCapacity, then get/append over the checked range) and the result owns its own storage. Hence no sliceBetween native for Buffer. Borrowed views are Window's job.
  • swapRemove is TorbScript over the natives, O(1), no new native.

API (exact; doc comments with # Examples like Array)

Member Kind Behaviour
static fn withCapacity(capacity: Int): Self native empty; the capacity is a hint (as ArrayList)
static fn from(items: Iterate<Item>): Self TorbScript with From<Iterate<Item>>; so Buffer.of-style construction needs nothing else
fn length(): Int native
fn get(index: Int): Item? native None out of range, negative included
fn at(index: Int): Item TorbScript panics with the ArrayList.at message (index <i> is out of bounds for a length of <n>)
var fn set(index: Int, value: Item) native in place when unique; panics out of range like ArrayList.set
var fn update(index: Int, change: (var element: Item) => Void) TorbScript change self[index], same line as ArrayList.update
var fn append(value: Item) native
var fn insert(index: Int, value: Item) native shifts the tail
var fn removeAt(index: Int): Item? native shifts the tail; None out of range
var fn swapRemove(index: Int): Item? TorbScript answers the item at index, moves the last item into its slot, shrinks by one; order is not kept; None (and no change) out of range; on the last index it is removeAt(last). Never shifts.
fn slice(range: Bounds<Int>): Self TorbScript copy, see above; panics like ArrayList.slice for a bad range
var fn replace(range: Bounds<Int>, values: Self) TorbScript over private native replaceBetween as ArrayList.replace
var fn reverse(), var fn clear() native
fn iterate(): Iterator<Item>, fn keys(): Iterate<Int> TorbScript BufferIterator holds the buffer by value (as ArrayIterator); keys is 0..length()

Not on Buffer in this issue: compact (moves to Collection, COLLECTIONS 3.2), list-literal adaptation (const b: Buffer<Int> = [1, 2]), windows (stays on ArrayList until #55), capacity()/reserve.

Acceptance criteria

  • std/core/src/buffer.trb declares Buffer<Item> with exactly the API above; natives are only those of the "native" rows; exported from std/core and std/prelude; torb check on std clean.
  • swapRemove removes in O(1): on [10, 20, 30, 40], swapRemove(1) answers Some(20) and leaves [10, 40, 30]; swapRemove(3) on that three-item buffer answers None and changes nothing; the last index just drops the last item.
  • Value semantics: var a: Buffer<Int> = ...; const b = a; a[0] = 9 leaves b unchanged; the same through a field, a var parameter and a closure capture.
  • In place when unique, shown by cost and not by a hook: a program writes buffer[i] for 200 000 indices of a 200 000-item Buffer<Int> and a loop of swapRemove/append over the same size, and finishes within the suite's per-program time; the PR states the measured time and the time of the same program with const keep = buffer held (every write copying) so the margin is on record. Plus a micro-benchmark under benchmarks/ (same shape, ArrayList beside it) with the numbers in the PR description.
  • No leak: a Buffer<String> and a Buffer<Buffer<String>> through append, set, removeAt, swapRemove, replace, clear and going out of scope pass the zero-live-blocks gate.
  • Both back ends: every conformance program below runs under the native build and under the VM (the conformance runner already does both) with identical .expected.
  • Conformance programs in tests/conformance/ (each with .expected, .exit): buffer-basics (append/get/at/set/insert/removeAt/length/iterate/keys, out-of-range get/removeAt/swapRemove answer None), buffer-swap-remove, buffer-value-semantics, buffer-slice-copies (a slice taken, the original then written, neither sees the other), buffer-equality-show-hash, buffer-index-panics (.exit 101 style as array-index-bounds, with .stderr), buffer-in-place-scale, buffer-strings-leaks.
  • Docs: the COLLECTIONS.md table row and gap 6 lose "(planned)" and say Built , the standard-library page for std/core lists Buffer; then build/release/torb.exe docs skill docs skills run and both committed (--check is a tier A gate).
  • Tier A green. No change to ArrayList, Bytes, std/parallel or the compiler (that is #299).

Dependencies

  • Depends on #299 (compiler natives for Buffer, commit 1 of 2), merged and its commit in a published seed (seeds.txt on the seeds release lists a seed at or after the #299 merge commit; the forge's Actions -> seed -> Run workflow publishes one at once). Without it CI cannot bootstrap std/core.
  • Blocks #55, #92 and #300.

Notes

Not ready until the seed condition above holds. Commit 2 of the two-commit rule (CLAUDE.md "Seed and breaking changes"): after #299, no further compiler change is needed.

Moved from the planning lists of the docs; the design record stays the specification.

## Context `Buffer<Item>` joins `Array` in `std/core`: a growable heap sequence with an in-place promise and `swapRemove`. ECS columns (#92), the rebuilt collections (#55) and tensors stand on it. This issue is **commit 2 of 2**: the `std/core` type, its prelude export, its conformance programs and its docs. The compiler side is #299 (commit 1) and has to be merged **and in a published seed** first. ## Source - [COLLECTIONS.md gap 6](https://git.torb.dev/torbscript/language/src/commit/393ef2608e4a60b8ff76d8b6b408951b822d887d/docs/design/COLLECTIONS.md#L925) - [COLLECTIONS.md table](https://git.torb.dev/torbscript/language/src/commit/393ef2608e4a60b8ff76d8b6b408951b822d887d/docs/design/COLLECTIONS.md#L646) - [ECS.md "What the design needs from `Buffer<Item>`"](https://git.torb.dev/torbscript/language/src/branch/main/docs/design/ECS.md#what-the-design-needs-from-bufferitem) (promises 1 and 3; promise 2, the windows, is `std/parallel`'s `Window`, already built over `ArrayList` and out of scope here) ## Decisions (made in refinement; the design record stays the specification) - **Where:** `std/core/src/buffer.trb`, re-exported from `std/core/src/lib.trb` and `std/prelude` like `Array` (`public use Array, ... from "std/core"`). `std/core` cannot depend on `std/collections`, so `Buffer` implements only what core owns: `Iterate<Item>`, `Length`, `MutableIndex<Int, Item>`, `MutableSlice`, plus `Equals`, `Show`, `Hash` as `extend`s (items in brackets, ordered hash with `combineHashes`), written like the ones at the end of `array.trb`. Joining the `List`/`Collection` family and `Bytes` becoming `Buffer<UInt8>` is the follow-up #300, not this issue. - **Representation:** `public native type Buffer<Item>` over the **same runtime list** as `ArrayList` (`RuntimeKind.ListStorage`; #299 registers it). No new C, no new `torb_` symbol, nothing in the VM beyond the shared table. - **The in-place promise** is the existing runtime behaviour made a documented contract: `buffer[i] = x`, `set`, `append`, `insert`, `removeAt`, `swapRemove`, `replace`, `reverse`, `clear` change the storage in place whenever it has one owner; they copy once (copy on write) only when the `Buffer` value has been copied (`const b = a`, passed or captured by value) and is then written. The doc comment states exactly this and nothing stronger. - **`slice` copies.** `ArrayList.slice` shares storage, so a live slice silently turns the next write into a copy - the trap a frame budget cannot have. `Buffer.slice` is TorbScript (`withCapacity`, then `get`/`append` over the checked range) and the result owns its own storage. Hence no `sliceBetween` native for `Buffer`. Borrowed views are `Window`'s job. - **`swapRemove` is TorbScript over the natives, O(1), no new native.** ## API (exact; doc comments with `# Examples` like `Array`) | Member | Kind | Behaviour | |---|---|---| | `static fn withCapacity(capacity: Int): Self` | native | empty; the capacity is a hint (as `ArrayList`) | | `static fn from(items: Iterate<Item>): Self` | TorbScript | `with From<Iterate<Item>>`; so `Buffer.of`-style construction needs nothing else | | `fn length(): Int` | native | | | `fn get(index: Int): Item?` | native | `None` out of range, negative included | | `fn at(index: Int): Item` | TorbScript | panics with the `ArrayList.at` message (`index <i> is out of bounds for a length of <n>`) | | `var fn set(index: Int, value: Item)` | native | in place when unique; panics out of range like `ArrayList.set` | | `var fn update(index: Int, change: (var element: Item) => Void)` | TorbScript | `change self[index]`, same line as `ArrayList.update` | | `var fn append(value: Item)` | native | | | `var fn insert(index: Int, value: Item)` | native | shifts the tail | | `var fn removeAt(index: Int): Item?` | native | shifts the tail; `None` out of range | | **`var fn swapRemove(index: Int): Item?`** | TorbScript | answers the item at `index`, moves the **last** item into its slot, shrinks by one; order is not kept; `None` (and no change) out of range; on the last index it is `removeAt(last)`. Never shifts. | | `fn slice(range: Bounds<Int>): Self` | TorbScript | copy, see above; panics like `ArrayList.slice` for a bad range | | `var fn replace(range: Bounds<Int>, values: Self)` | TorbScript over private native `replaceBetween` | as `ArrayList.replace` | | `var fn reverse()`, `var fn clear()` | native | | | `fn iterate(): Iterator<Item>`, `fn keys(): Iterate<Int>` | TorbScript | `BufferIterator` holds the buffer by value (as `ArrayIterator`); `keys` is `0..length()` | Not on `Buffer` in this issue: `compact` (moves to `Collection`, COLLECTIONS 3.2), list-literal adaptation (`const b: Buffer<Int> = [1, 2]`), `windows` (stays on `ArrayList` until #55), `capacity()`/`reserve`. ## Acceptance criteria - [ ] `std/core/src/buffer.trb` declares `Buffer<Item>` with exactly the API above; natives are only those of the "native" rows; exported from `std/core` and `std/prelude`; `torb check` on `std` clean. - [ ] `swapRemove` removes in O(1): on `[10, 20, 30, 40]`, `swapRemove(1)` answers `Some(20)` and leaves `[10, 40, 30]`; `swapRemove(3)` on that three-item buffer answers `None` and changes nothing; the last index just drops the last item. - [ ] Value semantics: `var a: Buffer<Int> = ...; const b = a; a[0] = 9` leaves `b` unchanged; the same through a field, a `var` parameter and a closure capture. - [ ] In place when unique, shown by cost and not by a hook: a program writes `buffer[i]` for 200 000 indices of a 200 000-item `Buffer<Int>` and a loop of `swapRemove`/`append` over the same size, and finishes within the suite's per-program time; the PR states the measured time and the time of the same program with `const keep = buffer` held (every write copying) so the margin is on record. Plus a micro-benchmark under `benchmarks/` (same shape, `ArrayList` beside it) with the numbers in the PR description. - [ ] No leak: a `Buffer<String>` and a `Buffer<Buffer<String>>` through `append`, `set`, `removeAt`, `swapRemove`, `replace`, `clear` and going out of scope pass the zero-live-blocks gate. - [ ] Both back ends: every conformance program below runs under the native build and under the VM (the conformance runner already does both) with identical `.expected`. - [ ] Conformance programs in `tests/conformance/` (each with `.expected`, `.exit`): `buffer-basics` (append/get/at/set/insert/removeAt/length/iterate/keys, out-of-range `get`/`removeAt`/`swapRemove` answer `None`), `buffer-swap-remove`, `buffer-value-semantics`, `buffer-slice-copies` (a slice taken, the original then written, neither sees the other), `buffer-equality-show-hash`, `buffer-index-panics` (`.exit` 101 style as `array-index-bounds`, with `.stderr`), `buffer-in-place-scale`, `buffer-strings-leaks`. - [ ] Docs: the COLLECTIONS.md table row and gap 6 lose "(planned)" and say *Built <date>*, the standard-library page for `std/core` lists `Buffer`; then `build/release/torb.exe docs skill docs skills` run and both committed (`--check` is a tier A gate). - [ ] Tier A green. No change to `ArrayList`, `Bytes`, `std/parallel` or the compiler (that is #299). ## Dependencies - Depends on #299 (compiler natives for `Buffer`, commit 1 of 2), **merged and its commit in a published seed** (`seeds.txt` on the `seeds` release lists a seed at or after the #299 merge commit; the forge's Actions -> `seed` -> Run workflow publishes one at once). Without it CI cannot bootstrap `std/core`. - Blocks #55, #92 and #300. ## Notes Not `ready` until the seed condition above holds. Commit 2 of the two-commit rule (`CLAUDE.md` "Seed and breaking changes"): after #299, no further compiler change is needed. _Moved from the planning lists of the docs; the design record stays the specification._
orion added this to the Kernel of natives milestone 2026-10-05 21:07:14 +00:00
Author
Collaborator

[loop:torbscript] intake: in scope (author orion, label loop), not a duplicate, no collision with a design record (COLLECTIONS.md gap 6 is the source). Likely adds a native, so it follows the two-commit rule; refine decides. next: waiting (ready buffer full: #4, #49, #163, #164, #223 are ready) until 2026-10-09T10:00:00Z

[loop:torbscript] intake: in scope (author orion, label loop), not a duplicate, no collision with a design record (COLLECTIONS.md gap 6 is the source). Likely adds a native, so it follows the two-commit rule; refine decides. next: waiting (ready buffer full: #4, #49, #163, #164, #223 are ready) until 2026-10-09T10:00:00Z
Author
Collaborator

[loop:torbscript] claim refine by session:loop-torbscript-20261010 until 2026-10-10T03:48Z

[loop:torbscript] claim refine by session:loop-torbscript-20261010 until 2026-10-10T03:48Z
Author
Collaborator

[loop:torbscript] refine: split into #299 (compiler natives for Buffer, commit 1 of 2, ready) and this issue (the std/core type with exact API, swapRemove in TorbScript, slice copies, conformance programs; commit 2), plus follow-up #300 (List family and Bytes), next: waiting (needs a published seed containing the #299 merge; not ready until then; #299 goes first)

[loop:torbscript] refine: split into #299 (compiler natives for `Buffer`, commit 1 of 2, `ready`) and this issue (the `std/core` type with exact API, swapRemove in TorbScript, `slice` copies, conformance programs; commit 2), plus follow-up #300 (`List` family and `Bytes`), next: waiting (needs a published seed containing the #299 merge; not `ready` until then; #299 goes first)
Author
Collaborator

[loop:torbscript] refine: unblocked, the published seed torb-seed-1724b82c2d87 (seeds release) contains the #299 merge; ready, next: implement

[loop:torbscript] refine: unblocked, the published seed torb-seed-1724b82c2d87 (seeds release) contains the #299 merge; `ready`, next: implement
Author
Collaborator

[loop:torbscript] claim implement by session:loop-torbscript-20261010 until 2026-10-10T19:50Z

[loop:torbscript] claim implement by session:loop-torbscript-20261010 until 2026-10-10T19:50Z
Author
Collaborator

[loop:torbscript] release implement: the claim of session:loop-torbscript-20261010 expired without a result (no branch, no PR, no live worker).

[loop:torbscript] release implement: the claim of session:loop-torbscript-20261010 expired without a result (no branch, no PR, no live worker).
Author
Collaborator

[loop:torbscript] claim implement by session:loop-torbscript-20261012 until 2026-10-12T12:53Z

[loop:torbscript] claim implement by session:loop-torbscript-20261012 until 2026-10-12T12:53Z
Author
Collaborator

[loop:torbscript] release: the worker on anthropic:theorben died on its weekly limit before its first reply; respawning on the next profile.

[loop:torbscript] release: the worker on anthropic:theorben died on its weekly limit before its first reply; respawning on the next profile.
Author
Collaborator

[loop:torbscript] claim implement by session:loop-torbscript-20261012 until 2026-10-12T12:58Z

[loop:torbscript] claim implement by session:loop-torbscript-20261012 until 2026-10-12T12:58Z
Author
Collaborator

[loop:torbscript] implement: Buffer<Item> in std/core (natives plus TorbScript from/at/update/swapRemove/slice copy/replace/iterate/keys, Equals/Show/Hash), 10 conformance programs with allocation budgets, ArrayList benchmark twins, docs and skill regenerated. CI run 865 green on e65fc831 (tier A, gates, bootstrap, same-C; tier B skipped by path filter, the buffer programs pass native + VM locally against nightly-20261011). PR #310, next: review (merge gate argus). Tokens: ~230k.

[loop:torbscript] implement: `Buffer<Item>` in std/core (natives plus TorbScript `from`/`at`/`update`/`swapRemove`/`slice` copy/`replace`/`iterate`/`keys`, Equals/Show/Hash), 10 conformance programs with allocation budgets, ArrayList benchmark twins, docs and skill regenerated. CI run 865 green on e65fc831 (tier A, gates, bootstrap, same-C; tier B skipped by path filter, the buffer programs pass native + VM locally against nightly-20261011). PR https://git.torb.dev/torbscript/language/pulls/310, next: review (merge gate argus). Tokens: ~230k.
Author
Collaborator

[loop:torbscript] implement: a second worker was driving the same branch; both pushes landed on loop/54-buffer-std-core (mine: the format fixes, native markers in the std/core page, the swapRemove Panics section, pdisc stamps), CI green on e65fc831 (run 865), PR #310, next: review (merge gate argus). The benchmark margin numbers for the PR are still open (benchmarks are not a gate). Tokens: ~330k.

[loop:torbscript] implement: a second worker was driving the same branch; both pushes landed on loop/54-buffer-std-core (mine: the format fixes, native markers in the std/core page, the swapRemove Panics section, pdisc stamps), CI green on e65fc831 (run 865), PR https://git.torb.dev/torbscript/language/pulls/310, next: review (merge gate argus). The benchmark margin numbers for the PR are still open (benchmarks are not a gate). Tokens: ~330k.
argus closed this issue 2026-10-12 08:04:53 +00:00
Sign in to join this conversation.
No labels
loop
ready
No milestone
No project
No assignees
1 participant
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set

Reference
torbscript/language#54
No description provided.