collections: RingList, a List with O(1) at both ends (C7)

orion commented

2026-10-08 13:42:01 +00:00

Collaborator

Goal

RingList<Item>: an implementation of List whose insert(0, x) and removeAt(0) are O(1), as COLLECTIONS.md section 3.4 specifies (a deque is a List implementation, there is no Deque trait). Name settled by the owner (section 6, question 5).

Acceptance criteria

public type RingList<Item> with List<Item>, From<Iterate<Item>> over a ring of slots (the technique of ArrayQueue), O(1) amortised append, insert at index 0 and removeAt(0)/last removal; indexing, iteration, slices, Equals/Hash as the other List implementations.
RingList.of(...), RingList.filled(...) and a literal with a RingList annotation work through From.
Conformance program: grows past the first allocation, wraps around, mixes front and back operations, compares with ArrayList on the same operation sequence.
Benchmark: repeated removeAt(0) against ArrayList.

Seed impact

None. A new public type in std/collections written in plain TorbScript over a List; no syntax change, no new native, no runtime change (runtime/list.c stays the one storage, COLLECTIONS.md section 3.10 point 5), and the compiler looks up none of the new names by string (section 6a). Not breaking: only additions.

Size

One PR, one feat(collections) commit (plus tests and docs in the same commit or a second test/docs one).

Common to the C7 types

Export from std/collections/src/lib.trb (public use ...), doc comments with the cost profile of the implementation, as ArrayQueue has.
A conformance program in tests/conformance/ (.trb + .expected), run natively and in the VM, in the style of queue-grows.trb.
A benchmark in benchmarks/ (one small program plus its C counterpart, see benchmarks/README.md) against the array implementation. It is a measurement, not a gate.
skills/ regenerated when docs change; the worker does not run gates locally, CI does.

Source

COLLECTIONS.md C7, parent #139

## Goal `RingList<Item>`: an implementation of `List` whose `insert(0, x)` and `removeAt(0)` are O(1), as COLLECTIONS.md section 3.4 specifies (a deque is a `List` implementation, there is no `Deque` trait). Name settled by the owner (section 6, question 5). ## Acceptance criteria - [ ] `public type RingList<Item> with List<Item>, From<Iterate<Item>>` over a ring of slots (the technique of `ArrayQueue`), O(1) amortised `append`, `insert` at index 0 and `removeAt(0)`/last removal; indexing, iteration, slices, `Equals`/`Hash` as the other `List` implementations. - [ ] `RingList.of(...)`, `RingList.filled(...)` and a literal with a `RingList` annotation work through `From`. - [ ] Conformance program: grows past the first allocation, wraps around, mixes front and back operations, compares with `ArrayList` on the same operation sequence. - [ ] Benchmark: repeated `removeAt(0)` against `ArrayList`. ## Seed impact None. A new public type in `std/collections` written in plain TorbScript over a `List`; no syntax change, no new native, no runtime change (`runtime/list.c` stays the one storage, COLLECTIONS.md section 3.10 point 5), and the compiler looks up none of the new names by string (section 6a). Not breaking: only additions. ## Size One PR, one `feat(collections)` commit (plus tests and docs in the same commit or a second `test`/`docs` one). ## Common to the C7 types - Export from `std/collections/src/lib.trb` (`public use ...`), doc comments with the cost profile of the implementation, as `ArrayQueue` has. - A conformance program in `tests/conformance/` (`.trb` + `.expected`), run natively and in the VM, in the style of `queue-grows.trb`. - A benchmark in `benchmarks/` (one small program plus its C counterpart, see `benchmarks/README.md`) against the array implementation. It is a measurement, not a gate. - `skills/` regenerated when docs change; the worker does not run gates locally, CI does. ## Source - [COLLECTIONS.md C7](https://git.torb.dev/torbscript/language/blob/main/docs/design/COLLECTIONS.md#L992), parent #139

orion added the

loop

ready

labels

2026-10-08 13:42:01 +00:00

orion referenced this issue

2026-10-08 13:42:17 +00:00

collections: RingList, ConsStack, BankersQueue, Heap (C7) #139

orion referenced this issue

2026-10-08 13:42:17 +00:00

collections: RingList, ConsStack, BankersQueue, Heap (C7) #139

orion commented

2026-10-08 13:46:23 +00:00

Author

Collaborator

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

orion referenced this issue from a commit

2026-10-08 13:52:17 +00:00

fix(checker): build a literal of a concrete list type through its from

orion referenced this issue from a commit

2026-10-08 13:52:17 +00:00

feat(std/collections): add RingList, a List with O(1) at both ends

~~orion referenced this issue 2026-10-08 13:52:25 +00:00~~

feat(std/collections): add RingList, a List with O(1) at both ends #201

orion commented

2026-10-08 14:59:59 +00:00

Author

Collaborator

[loop:torbscript] implement: PR #201 open, CI green, next: review

[loop:torbscript] implement: PR https://git.torb.dev/torbscript/language/pulls/201 open, CI green, next: review

orion referenced this issue

2026-10-08 15:19:43 +00:00

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

orion referenced this issue

2026-10-08 15:19:43 +00:00

checker: list literal annotated with a concrete List implementation (const r: RingList<Int> = [1, 2]) #212

orion referenced this issue from a commit

2026-10-08 15:21:40 +00:00

feat(std/collections): add RingList, a List with O(1) at both ends

orion referenced this issue

2026-10-08 15:21:53 +00:00

feat(std/collections): add RingList, a List with O(1) at both ends #201

orion commented

2026-10-08 15:21:53 +00:00

Author

Collaborator

PR #201 implements everything except the literal criterion (const r: RingList<Int> = [1, 2] through From). That one is tracked in #212, so the PR says Refs #197; this issue stays open for it.

PR https://git.torb.dev/torbscript/language/pulls/201 implements everything except the literal criterion (`const r: RingList<Int> = [1, 2]` through `From`). That one is tracked in #212, so the PR says `Refs #197`; this issue stays open for it.

orion referenced this issue from a commit

2026-10-08 16:08:22 +00:00

feat(std/collections): add RingList, a List with O(1) at both ends