[0.33][Runtime] Add bounded allocation-backed value collections and deterministic Map/Set #47

Alpha closure disposition — 2026-10-28

The implementation is included in v0.33.0-alpha.1. The maintainer explicitly authorized publication after integration tests, without CI or additional peripheral review. This issue is closed for that alpha implementation scope; public APIs may still change.

The original stable-admission checklist below is retained. Its unexecuted full-gate and stable-freeze conditions are deferred for this alpha, not recorded as passed. See the alpha validation record and the Chinese closure comment for completed evidence and remaining boundaries.

Outcome and version

Planned for 0.33, following the maintainer's October 5 request. Implement bounded, verifier-local allocation-backed value collections so aggregation and deduplication do not depend on the current fixed stack buffer or ad hoc handwritten arrays. This is general language/runtime work, not a finance-specific feature.

Priority within this program: 3 — after the concrete Cell-set and nested-data requirements are established. Design exploration can run earlier. Record implementation ownership and review disposition before executable admission. A milestone assignment is not a release or deployment claim.

Motivation and duplicate check

Use cases: aggregate amounts by asset identity, detect duplicate identifiers, and maintain bounded temporary lookup tables while checking a transaction. These collections are invocation-local memory, not persistent account storage or a database spanning Cells.

Reviewed all 41 existing open/closed issues on October 5. No issue owns this runtime collection contract. #23 owns accepted value generics; #7/#8 own Cell lifecycle operations and explicitly exclude allocator-backed collections; #38/#39 address witness ownership and scalar/scratch optimizations, not a general allocator. #43 is a potential consumer, but its protocol acceptance remains there. Do not move existing 0.32 obligations into this issue.

Baseline: the collections matrix already supports a bounded stack-backed local Vec for fixed-width values. Allocation-backed helpers and general Map/Set operations remain fail-closed. Preserve that accepted stack-backed contract or provide an explicit versioned migration; do not silently change its capacity semantics.

flowchart TD
    Use["Asset totals and identifier deduplication"] --> Contract["Value types, operations and numeric budgets"]
    Contract --> Memory["Bounded invocation-local allocator or arena"]
    Memory --> Vec["Allocation-backed value Vec"]
    Memory --> Maps["Deterministic Map and Set"]
    Vec --> Evidence["Typed IR, checker and VM evidence"]
    Maps --> Evidence
    Evidence --> Admit["Admit only the measured supported shapes"]
    Contract --> Exclude["Cell ownership and persistent state stay outside"]

Required decisions and scope

1. Freeze an initial API for Vec, Map and Set, including construction, capacity, insertion/update, lookup, removal, length and iteration. Choose an explicit allocator/arena model, total heap-byte budget, element/count limits, growth behavior and deterministic exhaustion errors before positive lowering.
2. Start with admitted fixed-width, non-Cell values and explicit key equality/hash or ordering semantics. Reject hidden resources, unsupported references and recursive ownership. Nested dynamic owned elements require the separate nested-data contract; this issue must not imply they work automatically.
3. Define moves, copies, drops, borrowing, relocation and pointer invalidation through growth/removal. Prevent use-after-free, double-free, uninitialized reads, aliasing across mutation and stack/heap overlap. Runtime pointers must never become serialized identities.
4. Define deterministic iteration/serialization rules and adversarial collision behavior. Freeze worst-case operation limits rather than assuming average constant-time hashing. If a sorted map is chosen, expose and measure that contract explicitly; do not claim an unimplemented HashMap API.
5. Implement in stages: allocator and Vec, then deterministic Map/Set with asset-total and identifier-deduplication examples. Record exact supported type/operation combinations and stable rejection of all others.

Authoring direction — 2026-10-19

The maintainer adopted this authoring direction on 2026-10-19. Existing experimental lowerings and tests remain reusable evidence; they do not freeze the final public API. Exact declaration grammar remains to be selected against complete programs. This adds acceptance work within #47–#49 and preserves every existing runtime, checker, builder, resource, gate and review requirement; it is not a release claim or review waiver.

Keep explicit borrow root as view { ... } for a useful lexical read-only region, without requiring a borrow block for every ordinary permitted field read. Distinguish semantic prohibitions from current proof/implementation limitations. Checked, bounded, non-escaping read-only helper composition must preserve each view's root, source, bounds, lifetime and authority. Current call/escape restrictions stay enforced until those proofs exist; this does not authorize general mutable borrowing, escaping borrowed values or foreign lifecycle authority.

Use familiar Vec and deterministic ordered Map/Set operations. Declare the allocator/arena and named byte/element budgets at construction or scope entry, rather than repeating memory controls on each lookup or insertion. Freeze observable capacity, growth, deterministic exhaustion, duplicate handling and iteration order there. Do not silently change the accepted stack-backed Vec contract or present ordered behavior as an unimplemented HashMap.

Evaluate complete asset-total aggregation and identifier-deduplication programs, including extraction of read-only helpers. Allocated element views must retain their owner and reject stale aliases across growth, removal and drop. Keep runtime pointers out of serialization and identity. Select one canonical authoring form before stable API freeze; the implementation strategy alone must not dictate repetitive user syntax.

Acceptance

• Review complete asset-aggregation and identifier-deduplication programs with declarations, business predicates and helper extraction together; record the chosen authoring API and decision before stable freeze.
• Construction/scope declarations expose named memory and element budgets, capacity, deterministic failures and ordered iteration; use sites do not repeat allocator plumbing, and old stack-backed Vec behavior remains unchanged or explicitly migrated.
• Checked read-only helper examples and negative stale/escaping-view cases preserve allocation ownership and invalidation rules, with formatter, editor, cross-package, browser and independent-checker coverage for the final API.
• The versioned API, memory/ownership contract and numeric limits are fixed; admitted Vec, Map and Set operations execute in CKB-VM.
• Empty, single, maximum and one-over-limit cases; repeated insert/remove/grow sequences; allocation exhaustion; arithmetic overflow; duplicate keys and adversarial key distributions have deterministic tested outcomes.
• Independent reference models agree with operation sequences and canonical iteration/encoding. Compile-time and runtime negative cases cover stale aliases and forbidden resource containment.
• The independent checker binds allocation, initialization, bounds and lifecycle claims it advertises; rebound-hash mutations remove or alter those checks and reject.
• Source/type checking, IR, metadata, formatter/LSP, generated builders and browser metadata agree wherever the surface changes. Cross-package value-generic behavior is tested without reopening [Language design] Choose a stable surface for value generics and public API signatures #23.
• Frozen per-case cycles, observed stack/heap measurements or explicitly unavailable fields, ELF and encoded-byte budgets are published. Compare equivalent bounded array/stack implementations without relaxing existing cost budgets.
• Appropriate dev, backend and ci gates pass on identified source, and the scope-specific review disposition is recorded before stable admission.

Unbounded allocation, automatic persistence, generic Cell-backed containers, arbitrary Rust library compatibility and replacing all existing stack-backed collections are outside scope. A design-only result cannot be reported as implemented collection support.

Related 0.33 work

#49 owns Cell selection/correspondence and #48 owns nested dynamic codecs. Their bounded selection and read-only decoding can proceed without this allocator. Owned nested collection values require an explicitly admitted combination of this memory contract and #48's codec/ownership rules.