Files
prometeu-studio/discussion/lessons/DSC-0097-pbs-sdk-stack-queue/LSN-0095-private-array-stacks-and-circular-queues.md

194 lines
11 KiB
Markdown
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
---
id: LSN-0095
ticket: pbs-sdk-stack-queue
title: Private array stacks and circular queues
created: 2026-10-27
tags: [compiler-pbs, collections, stack, queue, snapshot-cursor, failure-phases]
---
# Private array stacks and circular queues
**Worker:** Lesson Worker. **Owner domain:** `compiler/pbs`.
DSC-0097 executed accepted DEC-0080 through PLN-0158, covering R1–R9 completely.
The durable normative reference is [SDK Stack and Queue](../../../docs/specs/compiler-languages/pbs/25.%20SDK%20Stack%20and%20Queue%20Specification.md).
[Qualification evidence](evidence/README.md) retains commands, fingerprints,
counts, raw logs and coverage after disposal of the workflow control artifacts.
## Original problem and delivered result
PBS had typed arrays, generic source structs, mutable collections and a shared
snapshot Cursor, but none automatically defined Stack/Queue's API, growth, resource
policy or removal order. Wrapping List/Linked would inherit different storage and
allocation costs without resolving those product choices.
The delivered `stack<T>` owns a dense private array and consumes LIFO. `queue<T>`
owns a circular private array and consumes FIFO. Both reuse checked arithmetic,
ordinary typed storage/copy and the exact shared Cursor implementation. Queue
dequeue does not shift the remaining values; insertion does not allocate a collection
node. No runtime change, new ISA, public node or universal Element was required.
## Separate physical capacity from occupied positions
Both collections start empty, with capacity 16 by default or the exact explicit
capacity, including zero. Int capacities promote locally without granting implicit
conversion to element arguments. Contextual/diamond construction still requires
an expected concrete generic type. Aliases/reexports retain original SDK authority.
```pbs
fn example() -> int {
let history = new stack<int>(0);
let pending: queue<int> = new queue<>(2);
history.push(20);
history.push(22);
pending.enqueue(20);
pending.enqueue(22);
// Stack first returns 22; Queue first returns 20.
return (history.pop() else 0) + (pending.dequeue() else 0);
}
```
Explicit capacity is not a maximum size. Growth reuses the checked formula
`min(u32max, max(required, capacity + max(1, ceil(capacity/2))))`, validating the
required size before clamping. From zero the capacities are 1,2,3,5,8,... .
Physical limits and ordinary quotas remain distinct; negative/above-u32 requests
terminate through the trusted SDK check, while actual storage instructions retain
their own failures. Pop/dequeue/clear retain capacity and never expose an indexer.
Stack occupies `[0,size)`. Queue's logical position i is start+i, wrapped into its
backing. Empty Queue normalizes start to zero. Zero-capacity operations do not
perform circular access; the first insertion grows before selecting a destination.
At maximum u32 capacity, start+offset still fits long without narrowing.
## Wrapped growth copies two complete regions
A capacity-four Queue can have physical slots `[4,5,2,3]`, start=2 and logical
contents `[2,3,4,5]`. Enqueueing 6 prepares capacity six with `[2,3,4,5,6,empty]`:
copy the occupied suffix, then the wrapped prefix, then insert privately. Only
afterward install backing, start=0 and size=5 in sequence. Old/candidate arrays
coexist under ordinary quotas; preparation never edits the old array.
Stack similarly prepares its copied dense prefix and new top before installing
the backing. In-capacity push/enqueue write only their inactive destination and
then count. There is no whole-backing reconstruction on ordinary operations.
Complete tuple/native/contract/function/reference groups retain their ownership
and identity; packing costs are still ordinary runtime costs.
## Dense storage still needs an optional result
Pop/dequeue/peek return optional T: none means empty, while zero/false are present.
Type/resource failures never become absence. T directly optional is rejected,
including grouping, consistently with Array/List/Linked. Struct payloads containing
optional fields remain valid, as does an optional collection itself. This avoids
an extra private cell per item merely to circumvent Array's type restriction.
Object insertion preserves shared instance identity and occurrences; snapshots
do not freeze objects. The same object inserted twice remains two positions, and
later object field mutation is visible through aliases. Capacity growth replaces
private storage without replacing the public collection identity.
## Prepare returns before clearing, then document actual writes
Pop prepares its optional return, clears the old top and updates size. Dequeue
prepares return and next start/count, clears the front, assigns start (zero if
empty), then size. Clear visits occupied slots in Stack index/Queue FIFO order
before resetting metadata. Inactive storage must be empty after every success.
An empty removal and all reads/capture perform no collection writes.
This preparation is not a transaction. Before the first write, refusal preserves
the prior collection. After it, earlier stores may remain and invariants can be
incomplete; there is no rollback, safe reuse or recovery promise. Budget/debugger
pauses remain resumable instruction boundaries. Optional carriers, including typed
absence, can allocate and must be prepared before destructive writes.
The actual corpus observes 18 Stack and 12 Queue natural refusals after writes
in each profile, all in clear, by comparing complete original-object states at
each instruction with the successful execution prefix. It therefore does not
mistake partial clear for whole-method rollback. Separate test-only growth probes
demonstrate capacity=3 with appended 42 and old size=2 after a later allocation
fault. Those probes do not ship or describe natural refusal frequency.
## Share traversal protocol, choose each collection's order
Stack captures top → base; Queue captures front → back. For inserted 20,22 the
snapshots are 22,20 and 20,22. Both finish capture before returning and use one
immutable private singly linked non-circular node per occurrence, with no snapshot
array or association to editable source slots. Later growth/removal/clear does
not alter the captured sequence. Capture costs O(n) work and additional nodes.
The existing Cursor state table is unchanged:
| State | current() | hasNext() | next() |
| --- | --- | --- | --- |
| Born empty | none | false | No change |
| Current has successor | some(current value) | true | Follow successor |
| Last, including singleton | some(final value) | false | No change |
Consume current before checking whether to advance. A hasNext-only loop skips
the final item; waiting for current to become absent does not finish a nonempty
snapshot. Prefix nodes can become unreachable, but final current remains retained.
Real provider collections observe 1,200 → 1 → 1 → 0 snapshot nodes/payloads,
with no retained source backing. Removal/clear/reuse fixtures observe
64 → 61 → 0 → 1 → 0 payloads and one live backing until final owner release.
These tests assert advancing GC collection counters, not merely safepoint entry.
Clear retains capacity but not discarded values, and replaced growth arrays
disappear after actual collection. No immediate reclamation is promised.
## Compiler integration stays smaller than the source algorithms
Trusted `SdkStack`/`SdkQueue` metadata selects constructor naming, optional-element
diagnostics and localized capacity conversion. Capacity-constructor handling is
separate from positional indexer eligibility: adding a capacity constructor must
not grant brackets or int-to-long payload conversion. Project homonyms remain
ordinary generic structs, and project code cannot forge the reserved attributes.
The editor exposes the concrete eight-method API, both constructor overloads and
original SDK definition locations, hiding storage/start/length. The English spec
and [executable example](../../../prometeu-compiler/frontends/prometeu-frontend-pbs/src/main/resources/pbs-knowledge/examples/game/1/src/stack-queue.pbs)
ship in installed knowledge. An isolated JVM compiles that actual installed-JAR
example outside the checkout; production VM execution independently observes both
completed snapshots retaining final values 20 and 22. An alias/reexport workspace
fixture proves the same source/SDK authority through module boundaries.
## Qualification and maintenance limits
| Gate | Result |
| --- | --- |
| Standard JUnit reports | 1,091 cases; zero failures/errors; 13 existing skips |
| Installed knowledge | Two passing isolated-JAR tests |
| Mandatory new PBX files | 106, all required in each runtime profile |
| Behavior/expected-fault executions per profile | 58, including both producers |
| Natural quota refusals per profile | 364 total; 30 after visible writes |
| Separate post-write growth probes per profile | Four |
| GC observations per profile | 36, both collections/producers |
| Import/installed source executions per profile | Two |
| Complete production harness | Passed in debug and release |
The selected runtime remains clean at
`dcf6561ea73446e0a3e1cf1c73eda20923b38df0`; no runtime write or commit occurred.
Qualification is local macOS/arm64, not a benchmark, cross-host qualification or
installed game readiness claim. Existing disabled JUnit cases and upstream
LifecycleRole/NonFiniteValue schema gaps remain explicit in the retained evidence.
Avoid these maintenance mistakes:
- Do not equate capacity with count, or use a capacity-zero remainder/access.
- Do not shift a Queue on every dequeue or wrap these collections over List/Linked.
- Do not skip clearing inactive references because later insertion overwrites them.
- Do not flatten optional absence into zero/false or hide storage faults as none.
- Do not confuse a prepared return/candidate with whole-method atomicity.
- Do not grant an indexer while adding capacity-constructor recognition.
- Do not replace the accepted snapshot table with a conventional live iterator.
- Do not count test probes as natural failures or safepoints as actual collections.
## Durable references
- [Stack/Queue spec](../../../docs/specs/compiler-languages/pbs/25.%20SDK%20Stack%20and%20Queue%20Specification.md) and
[shared Cursor](../../../docs/specs/compiler-languages/pbs/21.%20SDK%20List%20and%20Cursor%20Specification.md).
- [SDK algorithms](../../../prometeu-compiler/frontends/prometeu-frontend-pbs/src/main/resources/game/stdlib/1/sdk/collections/main.pbs).
- [Source/PBX corpus](../../../prometeu-architecture-tests/src/test/java/p/studio/compiler/backend/irvm/PbsStackQueueTest.java).
- [Conformance module](../../../tools/pbx-conformance/stack_queue.rs) and
[reproduction instructions](../../../tools/pbx-conformance/README.md).
- [Sequential mutation lessons](../DSC-0096-runtime-storage-isa-consumer-migration/LSN-0092-sequential-collection-mutations-need-explicit-failure-boundaries.md).
- [Evidence and R1–R9 coverage](evidence/README.md).