navicore/patch-seq

Fork 0

crates/core/src/stack.rs — New primitives: #378

Merged

navicore merged 3 commits from heap-value-pop-push into main

2026-03-28 20:51:15 +00:00

navicore commented

2026-03-28 18:46:04 +00:00

(Migrated from github.com)

heap_value_mut(slot) — get &mut Value from a raw stack slot if sole-owned, without the Arc alloc/dealloc cycle
peek_heap_mut(stack) — convenience for top of stack (sp-1)
peek_heap_mut_second(stack) — convenience for second from top (sp-2)

crates/runtime/src/list_ops.rs — list.push rewritten:

Fast path: uses peek_heap_mut_second to check if the list is sole-owned, then Arc::get_mut on the inner VariantData to mutate in place. Zero Arc alloc/dealloc.
Slow path: falls through to the existing pop/clone/push path for shared lists.
list.push! is now a trivial alias for list.push (kept for v4.x compat).

Results: 944 unit tests pass, 443 integration tests pass, clippy clean, fmt clean.

- heap_value_mut(slot) — get &mut Value from a raw stack slot if sole-owned, without the Arc alloc/dealloc cycle - peek_heap_mut(stack) — convenience for top of stack (sp-1) - peek_heap_mut_second(stack) — convenience for second from top (sp-2) crates/runtime/src/list_ops.rs — list.push rewritten: - Fast path: uses peek_heap_mut_second to check if the list is sole-owned, then Arc::get_mut on the inner VariantData to mutate in place. Zero Arc alloc/dealloc. - Slow path: falls through to the existing pop/clone/push path for shared lists. - list.push! is now a trivial alias for list.push (kept for v4.x compat). Results: 944 unit tests pass, 443 integration tests pass, clippy clean, fmt clean.

claude[bot] commented

2026-03-28 18:48:18 +00:00

(Migrated from github.com)

Code Review — PR #378

Overall this is a clean optimization with good test coverage (944 unit + 443 integration tests passing). A few issues worth addressing before merge, ranging from a soundness concern to minor nits.

1. `'static` lifetime on `heap_value_mut` is unsound (important)

pub unsafe fn heap_value_mut(slot: *mut StackValue) -> Option<&'static mut Value> {

The returned reference is not actually 'static — its true lifetime is bounded by the Arc on the stack (which in turn is bounded by the stack's lifetime). Returning 'static bypasses the borrow checker entirely, which means:

A caller could store the returned &mut Value and use it after the stack has been popped or freed, creating a dangling reference.
Multiple callers could independently call heap_value_mut on the same slot and hold two &'static mut references simultaneously, violating Rust's aliasing rules.

The fast path in list_push happens to be correct (the reference is consumed before any conflicting access), but the API makes it easy to write unsound callers accidentally. A bounded lifetime tied to the raw pointer's provenance would be safer:

pub unsafe fn heap_value_mut<'a>(slot: *mut StackValue) -> Option<&'a mut Value> {
    // ...
    if is_sole { Some(&mut *ptr) } else { None }
}

This keeps the unsafe contract explicit — callers choose 'a and must ensure it doesn't outlive the stack slot.

2. Non-atomic sole-ownership check (correctness note)

heap_value_mut checks sole ownership via:

let arc = Arc::from_raw(ptr as *const Value);
let is_sole = Arc::strong_count(&arc) == 1;
std::mem::forget(arc);
if is_sole { Some(&mut *ptr) } else { None }

Arc::strong_count is explicitly documented as non-atomic. The old push_in_place used Arc::get_mut(&mut outer_arc) which is the proper atomic sole-ownership gate. Although the doc comment notes strands are single-threaded, this divergence from the established pattern (Arc::get_mut) is worth flagging — it's a subtle regression in robustness and will be confusing to future readers expecting Arc::get_mut as the sole-ownership idiom throughout the codebase.

3. Missing sentinel-value coverage in `heap_value_mut`

The inline-value guard currently checks three cases:

if is_tagged_int(sv) || sv == TAG_FALSE || sv == TAG_TRUE {
    return None;
}

If the tagged-value encoding has any additional sentinel (e.g., a nil/null tag, a unit tag, or anything else that isn't a heap pointer), it would fall through to Arc::from_raw, which would be UB. It would be worth either adding an explicit assertion, a TAG_NIL check if one exists, or a comment that these three are exhaustive.

4. Subtle borrow-across-`pop` in the fast path

if let Some(Value::Variant(variant_arc)) = peek_heap_mut_second(stack)
    && let Some(data) = Arc::get_mut(variant_arc)
{
    let (stack, value) = pop(stack);  // <-- modifies sp while `data` is live
    data.fields.push(value);
    return stack;
}

data is a &mut VariantData derived from the Value at sp-2. pop decrements sp and reads/clears sp-1, so it doesn't actually touch sp-2's memory — the fast path is correct. But this relies on a non-obvious invariant about the stack layout, and the 'static lifetime on data means the compiler won't catch it if that invariant is ever broken by refactoring. A comment here explaining why pop is safe while data is live would help maintainability.

5. Migration doc references a non-existent function

docs/design/PEEK_HEAP_MUT_MIGRATION.md line 45 shows:

if let Some(Value::Map(map)) = peek_heap_mut_third(stack)

peek_heap_mut_third doesn't exist yet (it would be added when map.set is migrated). The example is a forward-looking sketch, but it could be confusing. Marking it as pseudocode or adding a note like // peek_heap_mut_third would be added alongside map.set would clarify intent.

Minor / Positive notes

The push_to_variant refactor from "main COW helper" to "slow-path helper" is clean; the naming in the updated doc comment accurately reflects its new role.
Reducing push_in_place to a thin alias rather than duplicating the logic is the right call for the v4.x compat shim.
The doc comment on heap_value_mut clearly calls out the "MUST NOT move or replace" invariant — that's good.
Test counts are solid; if there's a micro-benchmark for append-heavy loops it'd be nice to see the perf delta, but not a blocker.

Summary: Items 1 and 2 are the most important to address before merge — specifically the 'static lifetime (soundness) and the regression from Arc::get_mut to strong_count (correctness robustness). Items 3–5 are lower priority but worth fixing in the same pass since the code is already under review.

## Code Review — PR #378 Overall this is a clean optimization with good test coverage (944 unit + 443 integration tests passing). A few issues worth addressing before merge, ranging from a soundness concern to minor nits. --- ### 1. `'static` lifetime on `heap_value_mut` is unsound (important) ```rust pub unsafe fn heap_value_mut(slot: *mut StackValue) -> Option<&'static mut Value> { ``` The returned reference is not actually `'static` — its true lifetime is bounded by the Arc on the stack (which in turn is bounded by the stack's lifetime). Returning `'static` bypasses the borrow checker entirely, which means: - A caller could store the returned `&mut Value` and use it after the stack has been popped or freed, creating a dangling reference. - Multiple callers could independently call `heap_value_mut` on the same slot and hold two `&'static mut` references simultaneously, violating Rust's aliasing rules. The fast path in `list_push` happens to be correct (the reference is consumed before any conflicting access), but the API makes it easy to write unsound callers accidentally. A bounded lifetime tied to the raw pointer's provenance would be safer: ```rust pub unsafe fn heap_value_mut<'a>(slot: *mut StackValue) -> Option<&'a mut Value> { // ... if is_sole { Some(&mut *ptr) } else { None } } ``` This keeps the unsafe contract explicit — callers choose `'a` and must ensure it doesn't outlive the stack slot. --- ### 2. Non-atomic sole-ownership check (correctness note) `heap_value_mut` checks sole ownership via: ```rust let arc = Arc::from_raw(ptr as *const Value); let is_sole = Arc::strong_count(&arc) == 1; std::mem::forget(arc); if is_sole { Some(&mut *ptr) } else { None } ``` `Arc::strong_count` is explicitly documented as non-atomic. The old `push_in_place` used `Arc::get_mut(&mut outer_arc)` which *is* the proper atomic sole-ownership gate. Although the doc comment notes strands are single-threaded, this divergence from the established pattern (`Arc::get_mut`) is worth flagging — it's a subtle regression in robustness and will be confusing to future readers expecting `Arc::get_mut` as the sole-ownership idiom throughout the codebase. --- ### 3. Missing sentinel-value coverage in `heap_value_mut` The inline-value guard currently checks three cases: ```rust if is_tagged_int(sv) || sv == TAG_FALSE || sv == TAG_TRUE { return None; } ``` If the tagged-value encoding has any additional sentinel (e.g., a nil/null tag, a unit tag, or anything else that isn't a heap pointer), it would fall through to `Arc::from_raw`, which would be UB. It would be worth either adding an explicit assertion, a `TAG_NIL` check if one exists, or a comment that these three are exhaustive. --- ### 4. Subtle borrow-across-`pop` in the fast path ```rust if let Some(Value::Variant(variant_arc)) = peek_heap_mut_second(stack) && let Some(data) = Arc::get_mut(variant_arc) { let (stack, value) = pop(stack); // <-- modifies sp while `data` is live data.fields.push(value); return stack; } ``` `data` is a `&mut VariantData` derived from the `Value` at sp-2. `pop` decrements sp and reads/clears sp-1, so it doesn't actually touch sp-2's memory — the fast path is correct. But this relies on a non-obvious invariant about the stack layout, and the `'static` lifetime on `data` means the compiler won't catch it if that invariant is ever broken by refactoring. A comment here explaining why `pop` is safe while `data` is live would help maintainability. --- ### 5. Migration doc references a non-existent function `docs/design/PEEK_HEAP_MUT_MIGRATION.md` line 45 shows: ```rust if let Some(Value::Map(map)) = peek_heap_mut_third(stack) ``` `peek_heap_mut_third` doesn't exist yet (it would be added when `map.set` is migrated). The example is a forward-looking sketch, but it could be confusing. Marking it as pseudocode or adding a note like `// peek_heap_mut_third would be added alongside map.set` would clarify intent. --- ### Minor / Positive notes - The `push_to_variant` refactor from "main COW helper" to "slow-path helper" is clean; the naming in the updated doc comment accurately reflects its new role. - Reducing `push_in_place` to a thin alias rather than duplicating the logic is the right call for the v4.x compat shim. - The doc comment on `heap_value_mut` clearly calls out the "MUST NOT move or replace" invariant — that's good. - Test counts are solid; if there's a micro-benchmark for append-heavy loops it'd be nice to see the perf delta, but not a blocker. --- **Summary**: Items 1 and 2 are the most important to address before merge — specifically the `'static` lifetime (soundness) and the regression from `Arc::get_mut` to `strong_count` (correctness robustness). Items 3–5 are lower priority but worth fixing in the same pass since the code is already under review.

claude[bot] commented

2026-03-28 19:20:48 +00:00

(Migrated from github.com)

Code Review - PR #378: heap_value_mut stack primitives + list.push fast path

Overall this is a well-motivated optimization with good documentation. The core idea - avoid the Arc alloc/dealloc round-trip for sole-owned values via Arc::get_mut - is sound. A few items worth addressing before merge:

Potential Soundness Issue - Mutable reference across pop call

crates/runtime/src/list_ops.rs - fast path

data is a &mut VariantData derived from the Arc at sp-2 at the moment peek_heap_mut_second was called. After pop(stack), the stack pointer advances and what was sp-2 is now sp-1. The reference remains valid only because pop does not zero/free the underlying memory - it only decrements sp.

This is a load-bearing implicit invariant. It should be made explicit with a SAFETY comment in the calling code: "pop only decrements sp and does not overwrite sp-2; the Value at the old sp-2 slot remains live and unaliased."

Without this documentation, a future refactor to pop (e.g., zeroing slots for GC-friendliness) could silently introduce a use-after-free.

Missing SAFETY comments at call sites

The three new functions in stack.rs have excellent doc comments explaining the invariants they require. However, the call sites in list_ops.rs should have matching SAFETY annotations explaining why those invariants hold at each call site. This is standard practice for unsafe calls in Rust and is what clippy::undocumented_unsafe_blocks enforces.

Bounds checking in peek_heap_mut / peek_heap_mut_second

stack.sub(N) is unconditional pointer arithmetic. If the stack has fewer than N items, this is immediate UB. The Option return only discriminates between heap and inline values - it does not protect against an empty/shallow stack.

The callers are responsible for ensuring sufficient stack depth (which patch_seq_list_push presumably guarantees by contract), but this precondition is not documented on the functions. Either add a safety precondition note, or consider a debug-mode depth assertion.

let-chain syntax - MSRV check

The let ... && let ... chain syntax was stabilized in Rust 1.88 (May 2025). Please confirm this is at or below the project MSRV. If not, a nested if let is needed.

mem::forget in heap_value_mut - fragility note

The Arc::from_raw to mem::forget dance is correct but fragile: any early return between those two lines would drop the Arc and corrupt the stack refcount. Consider a comment block clearly marking the "do not drop this Arc" region, or a ManuallyDrop wrapper.

Missing benchmark numbers

The PR claims "Zero Arc alloc/dealloc" for the fast path. Including at least one microbenchmark result (before/after) would validate the claim and give future readers a baseline. The design doc already mentions "benchmark verification" as a checkpoint.

Minor: patch_seq_list_push_in_place deprecation

The doc comment labels this "to be removed in v5.0." Adding a #[deprecated] attribute or a tracking issue link would make it easier to find at cleanup time.

What looks good

The three-level abstraction (heap_value_mut -> peek_heap_mut -> peek_heap_mut_second) is clean and well-layered.
The fast path correctly short-circuits on Arc::get_mut returning None for shared lists - no silent data corruption possible.
PEEK_HEAP_MUT_MIGRATION.md is a useful artifact for reviewers and future contributors.
The list.push! alias reduction is the right call; a 55-line duplicate was a maintenance hazard.

Summary: The core optimization is sound. The main asks before merge are: (1) SAFETY comments at the list_ops.rs call sites, (2) explicit documentation of the "pop does not invalidate sp-2" invariant, and (3) MSRV/let-chain verification. The bounds-checking and benchmark gaps are lower priority but worth noting.

## Code Review - PR #378: heap_value_mut stack primitives + list.push fast path Overall this is a well-motivated optimization with good documentation. The core idea - avoid the Arc alloc/dealloc round-trip for sole-owned values via Arc::get_mut - is sound. A few items worth addressing before merge: --- ### Potential Soundness Issue - Mutable reference across pop call **crates/runtime/src/list_ops.rs - fast path** `data` is a `&mut VariantData` derived from the Arc at `sp-2` at the moment `peek_heap_mut_second` was called. After `pop(stack)`, the stack pointer advances and what was `sp-2` is now `sp-1`. The reference remains valid only because `pop` does not zero/free the underlying memory - it only decrements `sp`. This is a load-bearing implicit invariant. It should be made explicit with a `SAFETY` comment in the calling code: "pop only decrements sp and does not overwrite sp-2; the Value at the old sp-2 slot remains live and unaliased." Without this documentation, a future refactor to `pop` (e.g., zeroing slots for GC-friendliness) could silently introduce a use-after-free. --- ### Missing SAFETY comments at call sites The three new functions in `stack.rs` have excellent doc comments explaining the invariants they require. However, the call sites in `list_ops.rs` should have matching `SAFETY` annotations explaining why those invariants hold at each call site. This is standard practice for `unsafe` calls in Rust and is what `clippy::undocumented_unsafe_blocks` enforces. --- ### Bounds checking in peek_heap_mut / peek_heap_mut_second `stack.sub(N)` is unconditional pointer arithmetic. If the stack has fewer than `N` items, this is immediate UB. The `Option` return only discriminates between heap and inline values - it does **not** protect against an empty/shallow stack. The callers are responsible for ensuring sufficient stack depth (which `patch_seq_list_push` presumably guarantees by contract), but this precondition is not documented on the functions. Either add a safety precondition note, or consider a debug-mode depth assertion. --- ### let-chain syntax - MSRV check The `let ... && let ...` chain syntax was stabilized in Rust 1.88 (May 2025). Please confirm this is at or below the project MSRV. If not, a nested `if let` is needed. --- ### mem::forget in heap_value_mut - fragility note The `Arc::from_raw` to `mem::forget` dance is correct but fragile: any early return between those two lines would drop the Arc and corrupt the stack refcount. Consider a comment block clearly marking the "do not drop this Arc" region, or a ManuallyDrop wrapper. --- ### Missing benchmark numbers The PR claims "Zero Arc alloc/dealloc" for the fast path. Including at least one microbenchmark result (before/after) would validate the claim and give future readers a baseline. The design doc already mentions "benchmark verification" as a checkpoint. --- ### Minor: patch_seq_list_push_in_place deprecation The doc comment labels this "to be removed in v5.0." Adding a `#[deprecated]` attribute or a tracking issue link would make it easier to find at cleanup time. --- ### What looks good - The three-level abstraction (`heap_value_mut` -> `peek_heap_mut` -> `peek_heap_mut_second`) is clean and well-layered. - The fast path correctly short-circuits on `Arc::get_mut` returning `None` for shared lists - no silent data corruption possible. - `PEEK_HEAP_MUT_MIGRATION.md` is a useful artifact for reviewers and future contributors. - The `list.push!` alias reduction is the right call; a 55-line duplicate was a maintenance hazard. --- **Summary:** The core optimization is sound. The main asks before merge are: (1) `SAFETY` comments at the `list_ops.rs` call sites, (2) explicit documentation of the "pop does not invalidate sp-2" invariant, and (3) MSRV/let-chain verification. The bounds-checking and benchmark gaps are lower priority but worth noting.

claude[bot] commented

2026-03-28 20:25:13 +00:00

(Migrated from github.com)

Code Review — PR #378 (stack.rs + list_ops.rs)

Note: A previous automated review on this PR contained some inaccurate claims about the code (citing a 'static lifetime and Arc::strong_count that don't appear in the actual diff). This review is based on the actual diff.

What's good

heap_value_mut correctly uses Arc::get_mut (the atomic sole-ownership gate) rather than Arc::strong_count. This matches the established COW idiom in the codebase.
The 'a lifetime annotation is present, and the doc comment explicitly states the caller must ensure the reference doesn't outlive the stack slot — correct contract for an unsafe fn.
push_in_place reduced to a thin alias is the right call for a compat shim; no logic duplication.
The push_to_variant doc comment update ("slow-path helper") accurately reflects its new role.
944 unit + 443 integration tests passing is solid coverage.

Issues worth addressing

1. Double Arc::get_mut overhead in the fast path (minor perf note)

if let Some(Value::Variant(variant_arc)) = peek_heap_mut_second(stack)
    && let Some(data) = Arc::get_mut(variant_arc)

peek_heap_mut_second already calls Arc::get_mut on the outer Arc<Value> to produce &mut Value. Then the fast path calls Arc::get_mut again on the inner Arc<VariantData>. Two atomic refcount checks for one mutation. This is unavoidable given the two-level Arc structure (Arc<Value> → Value::Variant(Arc<VariantData>)), but it's worth a comment so future readers don't wonder if the second check is redundant.

2. Borrow-across-pop relies on non-obvious stack invariant

if let Some(Value::Variant(variant_arc)) = peek_heap_mut_second(stack)
    && let Some(data) = Arc::get_mut(variant_arc)
{
    let (stack, value) = pop(stack);  // data is live across this call
    data.fields.push(value);
    return stack;
}

data: &'a mut VariantData borrows from the Arc at sp-2. pop modifies sp-1 and decrements sp — it does not touch sp-2's memory, so the borrow is valid. But this relies on pop's internal implementation not touching sp-2. The 'a lifetime is unconstrained (chosen by the caller), so the compiler cannot catch a regression here if pop is ever changed to clear or reuse stack slots beyond sp-1. A single comment explaining why pop is safe while data is live would make this easier to audit in the future.

3. Inline-value exhaustiveness comment

if is_tagged_int(sv) || sv == TAG_FALSE || sv == TAG_TRUE {
    return None;
}

The comment says "all non-heap encodings … exhaustively" — this is a load-bearing claim. If the encoding ever gains a new sentinel (unit, nil, etc.), the Arc::from_raw call below would be UB. A debug_assert or a reference to where the encoding is formally defined (a single source of truth) would make this guard more resilient than the comment alone.

Migration doc (docs/design/PEEK_HEAP_MUT_MIGRATION.md)

The pseudocode for map.set correctly uses heap_value_mut(stack.sub(3)) (not a new peek_heap_mut_third — the generic fn already handles arbitrary depths). The candidate table and ordering look reasonable. One suggestion: add a note that the fast path for map.set will need Arc::get_mut on the inner map structure as well (same two-level pattern as list), in case a future contributor misses that and only checks the outer Arc.

Summary

The core optimization is sound — Arc::get_mut is the right atomic guard, the fast/slow path fallback is correct, and the compat alias is clean. The main actionable items are:

Add a comment explaining why pop is safe while data is live (borrow-across-pop).
Add a comment or debug_assert backing the "exhaustive" inline-value claim.
(Optional) Note the two-level Arc::get_mut pattern in the fast path for future readers.

None of these are blockers, but items 1 and 2 would meaningfully improve future auditability of this unsafe code.

## Code Review — PR #378 (stack.rs + list_ops.rs) > Note: A previous automated review on this PR contained some inaccurate claims about the code (citing a `'static` lifetime and `Arc::strong_count` that don't appear in the actual diff). This review is based on the actual diff. --- ### What's good - `heap_value_mut` correctly uses `Arc::get_mut` (the atomic sole-ownership gate) rather than `Arc::strong_count`. This matches the established COW idiom in the codebase. - The `'a` lifetime annotation is present, and the doc comment explicitly states the caller must ensure the reference doesn't outlive the stack slot — correct contract for an `unsafe` fn. - `push_in_place` reduced to a thin alias is the right call for a compat shim; no logic duplication. - The `push_to_variant` doc comment update ("slow-path helper") accurately reflects its new role. - 944 unit + 443 integration tests passing is solid coverage. --- ### Issues worth addressing **1. Double `Arc::get_mut` overhead in the fast path (minor perf note)** ```rust if let Some(Value::Variant(variant_arc)) = peek_heap_mut_second(stack) && let Some(data) = Arc::get_mut(variant_arc) ``` `peek_heap_mut_second` already calls `Arc::get_mut` on the outer `Arc<Value>` to produce `&mut Value`. Then the fast path calls `Arc::get_mut` again on the inner `Arc<VariantData>`. Two atomic refcount checks for one mutation. This is unavoidable given the two-level Arc structure (`Arc<Value>` → `Value::Variant(Arc<VariantData>)`), but it's worth a comment so future readers don't wonder if the second check is redundant. **2. Borrow-across-`pop` relies on non-obvious stack invariant** ```rust if let Some(Value::Variant(variant_arc)) = peek_heap_mut_second(stack) && let Some(data) = Arc::get_mut(variant_arc) { let (stack, value) = pop(stack); // data is live across this call data.fields.push(value); return stack; } ``` `data: &'a mut VariantData` borrows from the Arc at sp-2. `pop` modifies sp-1 and decrements sp — it does not touch sp-2's memory, so the borrow is valid. But this relies on `pop`'s internal implementation not touching sp-2. The `'a` lifetime is unconstrained (chosen by the caller), so the compiler cannot catch a regression here if `pop` is ever changed to clear or reuse stack slots beyond sp-1. A single comment explaining why `pop` is safe while `data` is live would make this easier to audit in the future. **3. Inline-value exhaustiveness comment** ```rust if is_tagged_int(sv) || sv == TAG_FALSE || sv == TAG_TRUE { return None; } ``` The comment says "all non-heap encodings … exhaustively" — this is a load-bearing claim. If the encoding ever gains a new sentinel (unit, nil, etc.), the `Arc::from_raw` call below would be UB. A `debug_assert` or a reference to where the encoding is formally defined (a single source of truth) would make this guard more resilient than the comment alone. --- ### Migration doc (docs/design/PEEK_HEAP_MUT_MIGRATION.md) The pseudocode for `map.set` correctly uses `heap_value_mut(stack.sub(3))` (not a new `peek_heap_mut_third` — the generic fn already handles arbitrary depths). The candidate table and ordering look reasonable. One suggestion: add a note that the fast path for `map.set` will need `Arc::get_mut` on the *inner* map structure as well (same two-level pattern as list), in case a future contributor misses that and only checks the outer Arc. --- ### Summary The core optimization is sound — `Arc::get_mut` is the right atomic guard, the fast/slow path fallback is correct, and the compat alias is clean. The main actionable items are: 1. Add a comment explaining why `pop` is safe while `data` is live (borrow-across-pop). 2. Add a comment or `debug_assert` backing the "exhaustive" inline-value claim. 3. (Optional) Note the two-level `Arc::get_mut` pattern in the fast path for future readers. None of these are blockers, but items 1 and 2 would meaningfully improve future auditability of this unsafe code.