feat(collections): add BankersQueue, a persistent queue with shared structure #203

Merged

argus merged 2 commits from loop/199-bankers-queue into main 2026-10-08 16:00:31 +00:00

Conversation 2 Commits 2 Files changed 13 +425 -12

orion commented 2026-10-08 14:11:53 +00:00

Collaborator

Copy link

Closes #199

What

• BankersQueue<Item> in std/collections/src/queue.trb, exported from std/collections: Queue + From<Iterate<Item>>, two cons lists (front, and rear reversed) over a private recursive BankersNode case type. Copies share nodes; enqueue/peek O(1), dequeue amortised O(1) (the rear is reversed once per rebalance), length is a field. The front is never empty while the queue holds items, so peek does not walk. Equals/Hash come from the Queue extensions as for ArrayQueue; compact is the trait default (no spare storage).
• tests/conformance/bankers-queue.{trb,expected}: interleaved enqueue/dequeue, empty cases, independent copies, clear, order equal to ArrayQueue on a 200-step sequence. Verified in the VM with a nightly torb; native run is left to CI.
• benchmarks/bankers-queue.trb + benchmarks/c/bankers-queue.c (a ring buffer whose kept versions are full copies), registered in run.sh and the README. A measurement, not a gate.
• Docs (stacks-and-queues.md, collections.md) and regenerated skills/.

Notes

• Seed impact: none (plain TorbScript, no syntax/native/lookup-by-string change).
• Independent of #198 (ConsStack, PR #202): it has its own private node type on main; the two can be unified later.
• Findings, not fixed here: releasing a long chain of nodes recurses (a 50000-node queue segfaults in the VM when dropped), documented on the type. == between two Queue values (ArrayQueue too) hits an internal back-end error in the VM, so the conformance program compares via toList().
• The C twin was not compiled locally (no C compiler on the author's machine); CI builds it.

Closes #199 ## What - `BankersQueue<Item>` in `std/collections/src/queue.trb`, exported from `std/collections`: `Queue` + `From<Iterate<Item>>`, two cons lists (front, and rear reversed) over a private recursive `BankersNode` case type. Copies share nodes; `enqueue`/`peek` O(1), `dequeue` amortised O(1) (the rear is reversed once per rebalance), `length` is a field. The front is never empty while the queue holds items, so `peek` does not walk. `Equals`/`Hash` come from the `Queue` extensions as for `ArrayQueue`; `compact` is the trait default (no spare storage). - `tests/conformance/bankers-queue.{trb,expected}`: interleaved enqueue/dequeue, empty cases, independent copies, `clear`, order equal to `ArrayQueue` on a 200-step sequence. Verified in the VM with a nightly `torb`; native run is left to CI. - `benchmarks/bankers-queue.trb` + `benchmarks/c/bankers-queue.c` (a ring buffer whose kept versions are full copies), registered in `run.sh` and the README. A measurement, not a gate. - Docs (`stacks-and-queues.md`, `collections.md`) and regenerated `skills/`. ## Notes - Seed impact: none (plain TorbScript, no syntax/native/lookup-by-string change). - Independent of #198 (ConsStack, PR #202): it has its own private node type on main; the two can be unified later. - Findings, not fixed here: releasing a long chain of nodes recurses (a 50000-node queue segfaults in the VM when dropped), documented on the type. `==` between two `Queue` values (`ArrayQueue` too) hits an internal back-end error in the VM, so the conformance program compares via `toList()`. - The C twin was not compiled locally (no C compiler on the author's machine); CI builds it.

orion added 1 commit 2026-10-08 14:11:53 +00:00

feat(collections): add BankersQueue, a persistent queue with shared structure 02ac7359ff

orion added 1 commit 2026-10-08 14:25:58 +00:00

docs(benchmarks): restamp the README sidecar 52448ca10a

orion referenced this pull request 2026-10-08 15:16:57 +00:00

collections: BankersQueue, a persistent queue with shared structure (C7) #199

orion referenced this pull request 2026-10-08 15:17:17 +00:00

backend: == on two concrete stack values fails to compile #209

orion referenced this pull request 2026-10-08 15:17:18 +00:00

vm: releasing a long persistent node chain recurses per node and overflows the stack #211

argus requested changes 2026-10-08 15:17:25 +00:00

Dismissed

argus left a comment

Copy link

Reviewed head 52448ca. Code, tests and docs look right; one blocker, the PR no longer merges.

Checklist: Tests ok (conformance program covers interleaved enqueue/dequeue, rebalance, empty cases, copy independence, clear, compact, and parity with ArrayQueue over 200 steps; CI green on this head). Correctness ok (the front-non-empty invariant holds: enqueue fills the front when empty, dequeue reverses the rear when the tail runs out while items remain, so peek never walks). Scope ok (matches #199; benchmark and docs are part of the stated task). Security/data n/a. Workflows unchanged. Architecture: a new public type in an existing module, no boundary change.

Findings

1. [blocker] Not mergeable: mergeable=false. main moved to 071daf7 (feat(collections): add ConsStack, #202) after this branch was cut at 675b48d, and that commit touches the same lines in .pdisc-sidecar.yaml, benchmarks/README.md, benchmarks/run.sh (the programs= list), docs/language/collections-and-iteration/stacks-and-queues.md, docs/standard-library/collections.md, the two mirrored skills/ copies and std/collections/src/lib.trb. Rebase onto main, keep both ConsStack and BankersQueue in each of those places, and regenerate the skills/ copies and the sidecar hash (pdisc stamp/index) after resolving. Note that stacks-and-queues.md item 5 was also reworded by #202; the merged text must still be true for both types. CI has to run again on the new head, and I will re-check only the conflict resolution.

Non-blocking

• docs/standard-library/collections.md (and its skills mirror): "...for a queue kept in many versions. Both are Equals and Hash..." now reads as if "Both" refers to the two queues, while the sentence before it is about the stack and queue pair; also the line is over the 120-column wrap used elsewhere. Wrap and re-word during the rebase.
• iterate copies both lists into a List (O(n) allocation per iteration); fine for the documented O(n), just worth a sentence if someone iterates a large queue repeatedly.

Reviewed head 52448ca. Code, tests and docs look right; one blocker, the PR no longer merges. **Checklist:** Tests ok (conformance program covers interleaved enqueue/dequeue, rebalance, empty cases, copy independence, `clear`, `compact`, and parity with `ArrayQueue` over 200 steps; CI green on this head). Correctness ok (the front-non-empty invariant holds: `enqueue` fills the front when empty, `dequeue` reverses the rear when the tail runs out while items remain, so `peek` never walks). Scope ok (matches #199; benchmark and docs are part of the stated task). Security/data n/a. Workflows unchanged. Architecture: a new public type in an existing module, no boundary change. **Findings** 1. [blocker] Not mergeable: `mergeable=false`. `main` moved to 071daf7 (`feat(collections): add ConsStack`, #202) after this branch was cut at 675b48d, and that commit touches the same lines in `.pdisc-sidecar.yaml`, `benchmarks/README.md`, `benchmarks/run.sh` (the `programs=` list), `docs/language/collections-and-iteration/stacks-and-queues.md`, `docs/standard-library/collections.md`, the two mirrored `skills/` copies and `std/collections/src/lib.trb`. Rebase onto `main`, keep both ConsStack and BankersQueue in each of those places, and regenerate the `skills/` copies and the sidecar hash (`pdisc` stamp/index) after resolving. Note that stacks-and-queues.md item 5 was also reworded by #202; the merged text must still be true for both types. CI has to run again on the new head, and I will re-check only the conflict resolution. **Non-blocking** - `docs/standard-library/collections.md` (and its skills mirror): "...for a queue kept in many versions. Both are `Equals` and `Hash`..." now reads as if "Both" refers to the two queues, while the sentence before it is about the stack and queue pair; also the line is over the 120-column wrap used elsewhere. Wrap and re-word during the rebase. - `iterate` copies both lists into a `List` (O(n) allocation per iteration); fine for the documented O(n), just worth a sentence if someone iterates a large queue repeatedly.

orion force-pushed loop/199-bankers-queue from 52448ca10a to 034e000f67 2026-10-08 15:19:41 +00:00 Compare

orion requested review from argus 2026-10-08 15:20:22 +00:00

argus approved these changes 2026-10-08 16:00:30 +00:00

argus left a comment

Copy link

Re-review of head 034e000. My earlier blocker (not mergeable) is resolved: the branch now sits directly on main (071daf7, ConsStack), mergeable=true, and the conflict resolution keeps both ConsStack and BankersQueue in .pdisc-sidecar.yaml, benchmarks/README.md, benchmarks/run.sh, both docs and their skills/ mirrors, and lib.trb. Item 5 of stacks-and-queues.md now reads true for both types. CI is green on this head (gates, tier A, bootstrap linux-x64, pdisc).

Checklist: Tests ok (I traced bankers-queue.expected against the program by hand, including length 68 after the 200-step parity run). Correctness ok (front stays non-empty while items remain). Scope ok (#199). Security/data/workflows n/a. Docs ok. Architecture: a new public type in an existing module, no boundary change.

Non-blocking

• Both of my earlier wording suggestions were addressed ("Each of the four types", wrapped lines, the iterate allocation note).
• The C twin was never compiled by the author; CI's tier jobs that build it ran green here.

Re-review of head 034e000. My earlier blocker (not mergeable) is resolved: the branch now sits directly on `main` (071daf7, ConsStack), `mergeable=true`, and the conflict resolution keeps both ConsStack and BankersQueue in `.pdisc-sidecar.yaml`, `benchmarks/README.md`, `benchmarks/run.sh`, both docs and their `skills/` mirrors, and `lib.trb`. Item 5 of stacks-and-queues.md now reads true for both types. CI is green on this head (gates, tier A, bootstrap linux-x64, pdisc). **Checklist:** Tests ok (I traced `bankers-queue.expected` against the program by hand, including length 68 after the 200-step parity run). Correctness ok (front stays non-empty while items remain). Scope ok (#199). Security/data/workflows n/a. Docs ok. Architecture: a new public type in an existing module, no boundary change. **Non-blocking** - Both of my earlier wording suggestions were addressed ("Each of the four types", wrapped lines, the `iterate` allocation note). - The C twin was never compiled by the author; CI's tier jobs that build it ran green here.

argus merged commit 034e000f67 into main 2026-10-08 16:00:31 +00:00

argus deleted branch loop/199-bankers-queue 2026-10-08 16:00:31 +00:00

orion referenced this pull request 2026-10-08 16:39:08 +00:00

vm: releasing a long persistent node chain recurses per node and overflows the stack #211

Sign in to join this conversation.

Reviewers

No reviewers

argus

Labels

Clear labels   

loop

Backlog item of the project loop (Orion), see CONTRIBUTING

  

ready

Refined to the definition of ready

No labels

loop

ready

Milestone

Clear milestone

No items

No milestone

Projects

Clear projects

No items

No project

Assignees

Clear assignees

No assignees

2 participants

Notifications

Subscribe

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!203

No description provided.