Skip to main content

purrdf_stack/
lib.rs

1// SPDX-FileCopyrightText: 2026 Blackcat Informatics® Inc. <paudley@blackcatinformatics.ca>
2// SPDX-License-Identifier: MIT OR Apache-2.0 OR MulanPSL-2.0
3
4//! `purrdf-stack` — how much stack the running thread has left.
5//!
6//! Exhausting the stack is not an error anywhere: natively the process aborts, and on
7//! `wasm32-unknown-unknown` the shadow stack runs below its floor and traps with the
8//! instance's memory in an unknown state. A bound on how deeply a request may nest does
9//! not bound the stack handling it needs — a level of one construct can cost a hundred
10//! times a level of another, and the thread it runs on may be small — so the SPARQL
11//! evaluator (`purrdf-sparql-eval`) measures the stack actually left at every recursive
12//! entry and refuses, typed, when less than [`MARGIN_BYTES`] remain. (The SPARQL parser,
13//! `purrdf-sparql-algebra`, keeps a request's nesting on heap-allocated stacks and does
14//! not recurse on it.) This crate is that measurement, in one place: one floor per
15//! thread, one margin, the walk scopes that let a recursion with no error channel refuse
16//! too ([`walk`], [`walk_is_low`]), the stack a computation keeps out of reach of its
17//! own checks for walks it knows it will make ([`reserve`], [`widen`]), and the functions
18//! hosts call to install the floor of a stack they switch onto ([`replace_floor`]) or to
19//! switch whole contexts ([`replace_context`]). It also runs a computation on a stack of
20//! a stated size ([`on_stack`]), which is how a guard that refuses on a small stack is
21//! exercised on one.
22//!
23//! # The floor
24//!
25//! "Stack left" is the current stack pointer minus the lowest address the stack may
26//! reach — the *floor* — for the stack the thread is running on. Every target PurRDF
27//! ships on has a downward-growing stack.
28//!
29//! * **`wasm32`**: the stack is the shadow stack in linear memory, and its pointer is the
30//!   address of any address-taken local ([`stack_pointer`]). The floor is a thread-local
31//!   whose default is the low end of the module's own shadow stack. Every `wasm32` target
32//!   rustc ships links with `--stack-first`, which makes the shadow stack the first region
33//!   of linear memory, so that low end is address 0 — running below it wraps the pointer
34//!   and traps. The linker records it as the symbol `__stack_low`; this crate has no
35//!   `unsafe` code on `wasm32` and cannot name a linker symbol, so a host that can (the
36//!   PurRDF wasm package, when its instance starts) installs the symbol's value with
37//!   [`replace_floor`], which also covers a module linked with the stack elsewhere.
38//!   Neither `__data_end` nor `__heap_base` says where the stack *ends*, and the first
39//!   pointer observed is the stack's top, not its floor. A host that runs work on a
40//!   stack of its own — the wasm package's asynchronous lane runs each job on a
41//!   heap-allocated region — installs that stack's context with [`replace_context`]
42//!   whenever it switches onto it and puts the previous context back whenever it switches
43//!   away (see [Switching contexts](#switching-contexts)).
44//! * **native**: the floor is the current thread's stack limit, as the operating system
45//!   reports it — `platform::stack_floor` reads `pthread_getattr_np`,
46//!   `pthread_attr_get_np`, `pthread_stackseg_np`, `pthread_get_stackaddr_np` /
47//!   `pthread_get_stacksize_np`, or `GetCurrentThreadStackLimits`, per platform; see that
48//!   module for which targets read which call, and which read nothing. It is read once per
49//!   thread and cached in the same thread-local, so a check costs one thread-local load
50//!   and one comparison. A pointer found *below* the cached floor means the thread is
51//!   running on a different stack than the one the floor was read for (a host that switched
52//!   onto a stack of its own, say), so the floor is read again rather than refusing: a
53//!   stack switch never turns into a refusal. (A stack a host switched to *above* the
54//!   cached floor is measured against the old floor, which overstates what is left: such a
55//!   host installs its own floor with [`replace_floor`], as the wasm asynchronous lane
56//!   does.) On a platform whose limit cannot be read at all the measurement is inactive —
57//!   there is nothing to measure against — and [`remaining`] reports the whole address
58//!   range below the frame, so nothing refuses.
59//!
60//! # The margin
61//!
62//! A check refuses when less than [`MARGIN_BYTES`] remain, so the margin must hold the
63//! deepest chain of frames any guarded path can push *between two checks*, plus the
64//! non-recursive work that runs after the last one. See [`MARGIN_BYTES`] for the measured
65//! figures.
66//!
67//! # Walk scopes
68//!
69//! A recursion that has an error channel refuses by returning an error when [`is_low`]
70//! says so. One that has none — an infallible analysis, substitution or copy over a tree
71//! whose height nothing but the stack bounds — runs inside a [`walk`] scope instead: each
72//! level asks [`walk_is_low`], the first that finds the margin gone latches the refusal in
73//! the scope and installs [`EXHAUSTED`] so every later check refuses at once, and the
74//! scope discards whatever the walk built and reports the refusal. Which scope is open,
75//! and what it latched, is per-context state kept beside the floor.
76//!
77//! # Switching contexts
78//!
79//! The floor and the walk-scope state together are a [`Context`]: everything this crate
80//! keeps for the computation running on the thread. A host that runs several
81//! computations on one thread and switches between them *before any has returned* — the
82//! PurRDF wasm package's asynchronous lane suspends a job in the middle of an evaluation
83//! and runs the synchronous lane, or another job, until it resumes — swaps the whole
84//! context with [`replace_context`] at every switch. Swapping the floor alone is not
85//! enough: a job suspended inside a walk scope would leave that scope open for whatever
86//! ran next, whose own walks would latch their refusals in it — handing a placeholder to a
87//! caller with no scope to discard it, and leaving [`EXHAUSTED`] installed on a context
88//! that never refused — and two jobs closing their scopes in the order they happen to be
89//! resumed, rather than the reverse of the order they opened them, would leave each
90//! other's scope state behind.
91
92#![deny(unsafe_code)]
93
94use core::cell::Cell;
95use core::marker::PhantomData;
96use std::rc::Rc;
97
98#[cfg(not(target_arch = "wasm32"))]
99#[allow(
100    unsafe_code,
101    reason = "reading the current thread's stack bounds from the operating system; each \
102              block carries its own safety argument, and none of it compiles on wasm32, \
103              where the crate stays unsafe-free"
104)]
105mod platform;
106
107/// The stack a check requires to be left, in bytes: 128 KiB natively.
108///
109/// # Derivation
110///
111/// The margin has to hold the deepest chain of frames any guarded path pushes between
112/// two checks, together with the work that runs past the last check before a leaf
113/// returns.
114///
115/// **The evaluator** checks at every recursive entry, so what is left between two checks
116/// is one level of one recursion plus the leaf under it. It was measured by lowering the
117/// margin and sweeping the size of the thread a request runs on (x86_64, the workspace's
118/// opt-level-3 profile), over 26 request shapes that include every nesting and sibling
119/// form the parser admits at its limits:
120///
121/// * with a 4 or 8 KiB margin (threads of 96 to 704 KiB in 4 KiB steps) some thread
122///   sizes abort — the widest interval is a basic graph pattern's first use of a lazily
123///   built index, whose sort needs between 8 and 16 KiB;
124/// * with a 16 KiB margin (threads of 32 to 736 KiB in 8 KiB steps, 2 314 runs) every
125///   request answers or is the refusal, except on a 32 KiB thread, too small for the
126///   walks that run once before a plan's first operator. The same sweep over whole
127///   requests, governed ones, updates and in-process `SERVICE` calls found no other abort
128///   in the evaluator.
129///
130/// 128 KiB is eight times the evaluator's widest interval. The rest is room for what the sweeps cannot see: host code a leaf calls (a registered
131/// function, relation or aggregate, a `SERVICE` transport), and the derived copy and
132/// comparison of terms up to 128 triple-term levels deep (a computation walking deeper
133/// ones keeps what they take out of reach with [`reserve`]). It
134/// costs a thread little it could have used: a default 2 MiB thread keeps 94% of its
135/// stack, and a request refused here needed nearly all of it anyway.
136#[cfg(not(target_arch = "wasm32"))]
137pub const MARGIN_BYTES: usize = 128 * 1024;
138
139/// The stack a check requires to be left, in bytes: 64 KiB on `wasm32`.
140///
141/// # Derivation
142///
143/// As for the native margin. **The evaluator's** was measured with the margin lowered to
144/// 16 KiB, on the shipped npm artifact's synchronous lane with its shadow stack painted:
145/// 565 requests mixing two nesting forms at a time (`NOT EXISTS`, `EXISTS`, `OPTIONAL`,
146/// `LATERAL`, `MINUS`, sub-`SELECT`) over four innermost shapes (a triple, a 200-operator
147/// chain, a 121-step path, a nested `EXISTS` over a 100-term conjunction), so the refusal
148/// falls at every phase of every level. None trapped; the deepest frame any of them
149/// reached was 11 064 bytes above the floor — 5 320 bytes past the point the check
150/// refuses at. Only address-taken locals live on the shadow stack, so its levels are
151/// smaller than their native twins, and host code (a JavaScript function or resolver)
152/// runs on the engine's own stack, not on this one.
153///
154/// 64 KiB is twelve times the measured interval. It leaves the synchronous lane 960 KiB
155/// of its 1 MiB — 63 nested `FILTER EXISTS`, which reached 96% of the stack before the
156/// evaluator's guard existed, is refused, where 63 nested `FILTER NOT EXISTS` used to
157/// trap and corrupt the instance — and an asynchronous job, which runs on a heap region
158/// exactly as large as that shadow stack with the region's base installed as its floor,
159/// is refused here with the same typed error; compiler frame sizes can make the two
160/// lanes reach that refusal at different depths. The host engine's own
161/// call stack, which this crate cannot read, the SPARQL evaluator bounds with a budget of
162/// its own.
163#[cfg(target_arch = "wasm32")]
164pub const MARGIN_BYTES: usize = 64 * 1024;
165
166/// A floor that leaves no stack at all: while it is installed, [`remaining`] reports `0`
167/// and [`is_low`] is `true` on this thread, whatever the stack pointer.
168///
169/// For a guard that must stop every further check on the thread at once — a [`walk`]
170/// scope latches a refusal this way so the rest of the walk unwinds without computing
171/// over the placeholder it left — installed with [`replace_floor`], and replaced by the
172/// floor [`replace_floor`] returned once the refusal has been reported.
173pub const EXHAUSTED: usize = usize::MAX - 1;
174
175/// The floor's value before anything has been read or installed on this thread.
176const UNKNOWN: usize = usize::MAX;
177
178/// Where the running context stands with respect to [`walk`] scopes.
179#[derive(Clone, Copy, Debug, PartialEq, Eq)]
180enum WalkState {
181    /// No scope is open: a walk that runs low has nobody to hand a refusal to, so it
182    /// carries on exactly as it would with no guard at all.
183    Unscoped,
184    /// A scope is open and nothing has refused yet.
185    Scoped,
186    /// A walk inside the open scope refused at `construct`; the floor it replaced with
187    /// [`EXHAUSTED`] is `floor`.
188    Refused {
189        /// What refused.
190        construct: &'static str,
191        /// The floor to put back when the scope closes.
192        floor: usize,
193    },
194}
195
196thread_local! {
197    /// The floor of the stack this thread is running on; [`UNKNOWN`] until the first
198    /// measurement reads it (or a host installs one with [`replace_floor`]).
199    static FLOOR: Cell<usize> = const { Cell::new(UNKNOWN) };
200    /// The running context's [`WalkState`].
201    static WALK: Cell<WalkState> = const { Cell::new(WalkState::Unscoped) };
202    /// The bytes the open [`reserve`] scopes keep above the stack's real floor: `FLOOR`
203    /// is the real floor raised by this much, and a floor read again is raised by it too.
204    /// [`WIDENED`] is part of it.
205    static RESERVED: Cell<usize> = const { Cell::new(0) };
206    /// How many [`reserve`] scopes are open in the running context.
207    static SCOPES: Cell<usize> = const { Cell::new(0) };
208    /// The bytes [`widen`] added to the open scopes, given back when the outermost of
209    /// them closes.
210    static WIDENED: Cell<usize> = const { Cell::new(0) };
211}
212
213/// The current stack pointer, as the address of a local of the calling frame.
214///
215/// On `wasm32` an address-taken local lives on the shadow stack, so this is the shadow
216/// stack's depth, not the (inaccessible) value stack's; natively it is within one frame
217/// of the machine stack pointer. `black_box` keeps the local a real, addressed slot.
218/// Whether or not the call is inlined, the address is within this function's own small
219/// frame of the caller's, which the margin absorbs.
220#[inline]
221#[must_use]
222pub fn stack_pointer() -> usize {
223    let marker = 0u8;
224    core::hint::black_box(&raw const marker) as usize
225}
226
227/// The bytes of stack left below the calling frame before the floor, or `0` when the
228/// frame is already below it or [`EXHAUSTED`] is installed.
229#[must_use]
230pub fn remaining() -> usize {
231    let sp = stack_pointer();
232    match FLOOR.with(Cell::get) {
233        EXHAUSTED => 0,
234        floor => sp.checked_sub(floor).unwrap_or_else(|| refresh(sp)),
235    }
236}
237
238/// Install `floor` as the floor of the stack this thread now runs on, returning the
239/// floor it replaces (which the caller puts back when it switches away again).
240///
241/// Only a host that switches the stack pointer onto a stack of its own needs this, or a
242/// guard latching a refusal with [`EXHAUSTED`]; see the [crate documentation](crate).
243/// The value returned may be the "not yet read" marker, which is a valid value to put
244/// back: the next measurement reads the floor again.
245pub fn replace_floor(floor: usize) -> usize {
246    FLOOR.with(|cell| cell.replace(floor))
247}
248
249/// Everything this crate keeps for the computation running on the thread: the floor of
250/// its stack and the state of its [`walk`] scopes.
251///
252/// A host that switches between computations before they return swaps the whole of it
253/// with [`replace_context`]; see [Switching contexts](crate#switching-contexts). The
254/// value is opaque: a host only ever puts back what [`replace_context`] handed it, or
255/// installs a fresh one with [`Context::on_floor`].
256#[derive(Clone, Copy, Debug, PartialEq, Eq)]
257pub struct Context {
258    /// The floor [`replace_floor`] would install.
259    floor: usize,
260    /// The walk-scope state.
261    walk: WalkState,
262    /// The bytes the context's open [`reserve`] scopes keep above its real floor.
263    reserved: usize,
264    /// How many [`reserve`] scopes the context has open.
265    scopes: usize,
266    /// The bytes [`widen`] added to the context's open scopes.
267    widened: usize,
268}
269
270impl Context {
271    /// The context of a stack whose floor is `floor`, with no walk scope open — what a
272    /// host installs when it switches onto a stack of its own for a computation that has
273    /// not started yet.
274    #[must_use]
275    pub const fn on_floor(floor: usize) -> Self {
276        Self {
277            floor,
278            walk: WalkState::Unscoped,
279            reserved: 0,
280            scopes: 0,
281            widened: 0,
282        }
283    }
284}
285
286/// Install `context` as the running computation's, returning the context it replaces
287/// (which the caller puts back when it switches away again).
288///
289/// The floor, the walk-scope state and the open [`reserve`] scopes are swapped together,
290/// so a walk scope a suspended computation left open — and a refusal it latched there,
291/// with [`EXHAUSTED`] installed — stays with that computation, as does the stack it
292/// reserved, and whatever runs while it waits sees only its own. See
293/// [Switching contexts](crate#switching-contexts).
294pub fn replace_context(context: Context) -> Context {
295    Context {
296        floor: replace_floor(context.floor),
297        walk: WALK.with(|state| state.replace(context.walk)),
298        reserved: RESERVED.with(|reserved| reserved.replace(context.reserved)),
299        scopes: SCOPES.with(|scopes| scopes.replace(context.scopes)),
300        widened: WIDENED.with(|widened| widened.replace(context.widened)),
301    }
302}
303
304/// Keep `bytes` of stack, beyond [`MARGIN_BYTES`], out of reach of every check on this
305/// thread until the returned [`Reserve`] is dropped.
306///
307/// For a computation whose leaves run a recursion of known depth with no check of its
308/// own — the SPARQL evaluator copies, compares and matches the triple terms a request
309/// writes wherever its evaluation stands, and a term nested `n` deep takes those walks
310/// `n` levels down — reserving what that recursion needs up front makes every check the
311/// computation passes leave room for it: [`is_low`], [`remaining`] and [`walk_is_low`]
312/// all measure against the floor raised by `bytes`, so a frame that passed a check has
313/// the margin *and* the reserve below it. It is the floor that moves, so a check costs
314/// what it always did.
315///
316/// Reserves nest, and add up. A floor read again while one is open (a native thread
317/// that finds its frame below the cached floor) is raised by what is reserved, and a
318/// host's [`replace_context`] carries the reserve with the computation that made it. On
319/// a platform whose stack bound cannot be read, where every guard of this crate is
320/// inactive, nothing is reserved either.
321///
322/// A reserve is also a *scope* — even one of zero bytes — that [`widen`] can add to while
323/// the computation runs: whatever it adds is given back when the outermost open scope
324/// closes, not the innermost, because what the computation built with it may reach every
325/// frame up to where the computation started.
326pub fn reserve(bytes: usize) -> Reserve {
327    // Read the floor first, so what is raised is a real floor rather than the "not yet
328    // read" marker.
329    let _ = remaining();
330    let floor = FLOOR.with(Cell::get);
331    if floor == EXHAUSTED || inactive(floor) {
332        return Reserve {
333            bytes: 0,
334            scoped: false,
335            thread_bound: PhantomData,
336        };
337    }
338    FLOOR.with(|cell| cell.set(floor.saturating_add(bytes)));
339    RESERVED.with(|reserved| reserved.set(reserved.get() + bytes));
340    SCOPES.with(|scopes| scopes.set(scopes.get() + 1));
341    Reserve {
342        bytes,
343        scoped: true,
344        thread_bound: PhantomData,
345    }
346}
347
348/// Whether `floor` is the "no readable bound" floor of a native platform, where every
349/// guard of this crate is inactive.
350const fn inactive(floor: usize) -> bool {
351    cfg!(not(target_arch = "wasm32")) && floor == 0
352}
353
354/// Keep `bytes` more stack out of reach of every check in the running computation, for
355/// as long as its outermost open [`reserve`] scope lives — when the computation finds, as
356/// it runs, that it needs more than it reserved when it started (the SPARQL evaluator
357/// admitting a triple term it built, deeper than any the request wrote).
358///
359/// Returns whether the bytes are kept. They are not, and nothing changes, when no scope
360/// is open (nothing would give them back), when a refusal is latched ([`EXHAUSTED`] is
361/// installed), or when the calling frame would be left with less than [`MARGIN_BYTES`]
362/// above the raised floor — the caller refuses then, typed. On a platform whose stack
363/// bound cannot be read nothing is measured, so nothing is kept and `true` is returned.
364///
365/// The bytes are given back when the outermost scope closes rather than the innermost,
366/// because what the computation built with them may be walked in any frame up to the
367/// one that opened the outermost scope: that frame is above the one that widened, so it
368/// has at least the margin and every widened byte above the real floor.
369#[must_use]
370pub fn widen(bytes: usize) -> bool {
371    let _ = remaining();
372    let floor = FLOOR.with(Cell::get);
373    if inactive(floor) || bytes == 0 {
374        return true;
375    }
376    if floor == EXHAUSTED || SCOPES.with(Cell::get) == 0 {
377        return false;
378    }
379    let raised = floor.saturating_add(bytes);
380    let sp = stack_pointer();
381    if sp
382        .checked_sub(raised)
383        .is_none_or(|left| left < MARGIN_BYTES)
384    {
385        return false;
386    }
387    FLOOR.with(|cell| cell.set(raised));
388    RESERVED.with(|reserved| reserved.set(reserved.get() + bytes));
389    WIDENED.with(|widened| widened.set(widened.get() + bytes));
390    true
391}
392
393/// The bytes the running computation's open [`reserve`] scopes keep above its stack's
394/// real floor, [`widen`]ed bytes included: `0` when none is open.
395#[must_use]
396pub fn reserved() -> usize {
397    RESERVED.with(Cell::get)
398}
399
400/// Whether the running computation has a [`reserve`] scope open — whether [`widen`] has
401/// anywhere to keep its bytes.
402#[must_use]
403pub fn scoped() -> bool {
404    SCOPES.with(Cell::get) > 0
405}
406
407/// Stack kept out of reach of every check while it lives; see [`reserve`]. Dropping it
408/// gives the bytes back. The guard belongs to the creating thread, whose context it
409/// updates when dropped; it cannot move to another thread or be shared across threads.
410///
411/// ```compile_fail,E0277
412/// let guard = purrdf_stack::reserve(4096);
413/// std::thread::spawn(move || drop(guard));
414/// ```
415///
416/// ```compile_fail,E0277
417/// fn requires_sync<T: Sync>() {}
418/// requires_sync::<purrdf_stack::Reserve>();
419/// ```
420#[derive(Debug)]
421#[must_use = "the stack is reserved only while the `Reserve` lives"]
422pub struct Reserve {
423    /// What this reserve raised the floor by.
424    bytes: usize,
425    /// Whether it opened a scope (see [`reserve`]).
426    scoped: bool,
427    /// Dropping a reservation updates the creating thread's state.
428    thread_bound: PhantomData<Rc<()>>,
429}
430
431impl Reserve {
432    /// The bytes this reserve keeps: what was asked for, or `0` where nothing could be
433    /// reserved (no readable stack bound, or a refusal already latched).
434    #[must_use]
435    pub const fn bytes(&self) -> usize {
436        self.bytes
437    }
438}
439
440impl Drop for Reserve {
441    fn drop(&mut self) {
442        if !self.scoped {
443            return;
444        }
445        // The outermost scope gives back what `widen` added while any scope was open.
446        let outermost = SCOPES.with(|scopes| {
447            let open = scopes.get().saturating_sub(1);
448            scopes.set(open);
449            open == 0
450        });
451        let bytes = if outermost {
452            self.bytes + WIDENED.with(|widened| widened.replace(0))
453        } else {
454            self.bytes
455        };
456        if bytes == 0 {
457            return;
458        }
459        RESERVED.with(|reserved| reserved.set(reserved.get().saturating_sub(bytes)));
460        match FLOOR.with(Cell::get) {
461            // A walk scope inside this reserve refused and has not closed: it put
462            // EXHAUSTED in place of the raised floor and puts that floor back when it
463            // closes, so that is the floor to lower.
464            EXHAUSTED => WALK.with(|state| {
465                if let WalkState::Refused { construct, floor } = state.get() {
466                    state.set(WalkState::Refused {
467                        construct,
468                        floor: floor.saturating_sub(bytes),
469                    });
470                }
471            }),
472            UNKNOWN => {}
473            floor => FLOOR.with(|cell| cell.set(floor.saturating_sub(bytes))),
474        }
475    }
476}
477
478/// Run `body` — an infallible recursive walk over a tree whose height nothing but the
479/// stack bounds (an analysis, a substitution, a copy) — so that it can refuse when the stack
480/// runs low.
481///
482/// Such a walk has no error channel, so a level of it that finds less than
483/// [`MARGIN_BYTES`] left calls [`walk_is_low`], which latches the refusal in this scope
484/// and tells the walk to stop descending and return a placeholder. The scope then
485/// discards whatever `body` produced and returns `Err` with the construct that refused:
486/// a placeholder never escapes, because the only way to reach `body`'s value is through
487/// the `Ok` this returns only when nothing refused. Anything the walk wrote through a
488/// reference must be discarded with it, which is why a caller hands its walk state it owns
489/// (a fresh table, a fresh map) and drops it on the error.
490///
491/// Once a level has refused, the rest of the walk must not go on computing over the
492/// placeholder it left — a later level could trip an internal consistency assertion on a
493/// tree it half-built — so the refusal also replaces the running context's floor with
494/// [`EXHAUSTED`]: every check in that context, in every walk, then refuses at once, and the walk unwinds to this scope level by level
495/// without doing any more work. The real floor is put back when the scope closes.
496///
497/// Scopes nest: the enclosing scope's state (and, after a refusal, the floor) is put back
498/// when this one closes, even when `body` unwinds. They nest *per context*: a host that
499/// suspends a computation inside a scope swaps its [`Context`] out with
500/// [`replace_context`], so the scope is closed in the context that opened it.
501///
502/// # Errors
503///
504/// The `construct` a level of the walk named when it refused.
505pub fn walk<T>(body: impl FnOnce() -> T) -> Result<T, &'static str> {
506    /// Closes the scope when the walk returns or unwinds: puts the real floor back if a
507    /// level refused, then the enclosing scope's state.
508    struct Close(WalkState);
509    impl Drop for Close {
510        fn drop(&mut self) {
511            let inner = WALK.with(|state| state.replace(self.0));
512            if let WalkState::Refused { floor, .. } = inner {
513                replace_floor(floor);
514            }
515        }
516    }
517    let close = Close(WALK.with(|state| state.replace(WalkState::Scoped)));
518    let value = body();
519    let outcome = WALK.with(Cell::get);
520    drop(close);
521    match outcome {
522        WalkState::Refused { construct, .. } => Err(construct),
523        WalkState::Unscoped | WalkState::Scoped => Ok(value),
524    }
525}
526
527/// Whether a level of an infallible walk must stop descending: inside a [`walk`] scope,
528/// less than [`MARGIN_BYTES`] of stack are left (the refusal is latched for the scope to
529/// report), or a level of the same walk already refused. Outside any scope this is always
530/// `false`. `construct` names the walk, for the scope's error.
531///
532/// The hot path is [`is_low`]'s; the scope is consulted only once the margin is gone.
533#[inline]
534#[must_use]
535pub fn walk_is_low(construct: &'static str) -> bool {
536    if !is_low() {
537        return false;
538    }
539    walk_refuse(construct)
540}
541
542/// The cold half of [`walk_is_low`]: latch the refusal in the open scope, if any.
543#[cold]
544#[inline(never)]
545fn walk_refuse(construct: &'static str) -> bool {
546    WALK.with(|state| match state.get() {
547        WalkState::Unscoped => false,
548        WalkState::Scoped => {
549            let floor = replace_floor(EXHAUSTED);
550            state.set(WalkState::Refused { construct, floor });
551            true
552        }
553        WalkState::Refused { .. } => true,
554    })
555}
556
557/// Whether less than [`MARGIN_BYTES`] of stack are left.
558///
559/// The hot path is one thread-local load, one subtraction and one comparison; the floor
560/// is read (or re-read) only on the cold path.
561#[inline]
562#[must_use]
563pub fn is_low() -> bool {
564    let sp = stack_pointer();
565    sp.checked_sub(FLOOR.with(Cell::get))
566        .is_none_or(|left| left < MARGIN_BYTES)
567        && is_low_cold(sp)
568}
569
570/// The cold half of [`is_low`]: the floor was never read on this thread, the frame is
571/// below it, [`EXHAUSTED`] is installed, or the margin really is gone.
572#[cold]
573#[inline(never)]
574fn is_low_cold(sp: usize) -> bool {
575    let left = match FLOOR.with(Cell::get) {
576        EXHAUSTED => return true,
577        floor => sp.checked_sub(floor).unwrap_or_else(|| refresh(sp)),
578    };
579    left < MARGIN_BYTES
580}
581
582/// Read the floor of the stack `sp` is on, cache it, and return the bytes left above it.
583#[cfg(not(target_arch = "wasm32"))]
584fn refresh(sp: usize) -> usize {
585    // `platform::stack_floor` reads the thread's bounds directly from the operating
586    // system rather than from any particular frame, so — unlike a floor derived from a
587    // "bytes left" figure measured a few frames down — this is the thread's exact floor,
588    // not an approximation of it.
589    let floor = match platform::stack_floor() {
590        // What the open reserves keep is above the real floor.
591        Some(floor) => floor.saturating_add(RESERVED.with(Cell::get)),
592        None => 0,
593    };
594    FLOOR.with(|cell| cell.set(floor));
595    sp.saturating_sub(floor)
596}
597
598/// The floor of the synchronous shadow stack when no host has installed one: address 0.
599///
600/// Every `wasm32` target rustc ships links with `wasm-ld --stack-first`, which places the
601/// shadow stack as the first region of linear memory: `[0, stack size)`, the stack
602/// pointer starting at its top (1 MiB by default) and growing down toward address 0,
603/// with static data and the heap above it. The linker records that low end as the symbol
604/// `__stack_low`; this crate forbids `unsafe` code, so it cannot name a linker symbol
605/// itself, and takes the value the layout fixes instead. A host that links otherwise
606/// (`--no-stack-first` puts the stack above the static data) or that can read the
607/// symbol installs the real floor with [`replace_floor`] — the PurRDF wasm package does
608/// exactly that, from `__stack_low`, when its instance starts.
609#[cfg(target_arch = "wasm32")]
610const DEFAULT_FLOOR: usize = 0;
611
612/// Read the floor of the stack `sp` is on, cache it, and return the bytes left above it.
613///
614/// Only the first measurement on an instance with no installed floor reads anything: it
615/// takes [`DEFAULT_FLOOR`]. A frame below an installed floor has already run past the
616/// stack that floor belongs to, so nothing is left — the one case a native thread
617/// re-reads (a host that switched stacks under it) cannot arise here, where every stack
618/// switch installs its floor.
619#[cfg(target_arch = "wasm32")]
620fn refresh(sp: usize) -> usize {
621    if FLOOR.with(Cell::get) == UNKNOWN {
622        let floor = DEFAULT_FLOOR + RESERVED.with(Cell::get);
623        FLOOR.with(|cell| cell.set(floor));
624        return sp.saturating_sub(floor);
625    }
626    0
627}
628
629/// Why [`on_stack`] did not run its computation.
630#[derive(Debug)]
631#[non_exhaustive]
632pub enum StackError {
633    /// The computation asked for more stack than is left above the running stack's floor.
634    ///
635    /// `wasm32` has one shadow stack per instance and no second thread to give a
636    /// computation a stack of its own, so [`on_stack`] runs it inline on what is left of
637    /// the running stack: a request larger than that cannot be honoured, and is refused
638    /// here rather than trapping below the floor part-way through the computation.
639    ExceedsFloor {
640        /// The bytes asked for.
641        requested: usize,
642        /// The bytes left above the floor when the request was made.
643        available: usize,
644    },
645    /// The operating system would not start a thread with the requested stack.
646    Spawn(purrdf_hash::error::IoFailure),
647}
648
649impl purrdf_hash::error::StructuredError for StackError {
650    purrdf_hash::error_visit! {
651        ExceedsFloor { requested, available } => "stack-exceeds-floor" {
652            "requested" => ByteCount(*requested as u128),
653            "available" => ByteCount(*available as u128)
654        },
655        Spawn(cause) => "stack-spawn" { "cause" => Cause(cause) },
656    }
657}
658
659impl core::fmt::Display for StackError {
660    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
661        match self {
662            Self::ExceedsFloor {
663                requested,
664                available,
665            } => write!(
666                f,
667                "a {requested}-byte stack was requested, but only {available} bytes are left \
668                 above the running stack's floor"
669            ),
670            Self::Spawn(error) => write!(f, "could not start a thread for the stack: {error}"),
671        }
672    }
673}
674
675impl std::error::Error for StackError {
676    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
677        match self {
678            Self::ExceedsFloor { .. } => None,
679            Self::Spawn(error) => Some(error),
680        }
681    }
682}
683
684/// Run `f` on a stack of `bytes` and return what it returns.
685///
686/// A guard that refuses before the stack runs out is only shown to work by running it on
687/// a stack small enough to run out, so every such test needs "this computation, on a
688/// stack this big". This is the one implementation of that, because what a stack of a
689/// given size *is* differs by target and only this crate knows both:
690///
691/// * **native**: a fresh thread whose stack is `bytes` (the operating system may round
692///   it up to its minimum or its page size, never down). A fresh thread starts with a
693///   fresh [`Context`] — its own floor, no walk scope, no reserve — so `f` is measured
694///   against exactly the stack it was given. A panic in `f` resumes on the calling thread
695///   with its original payload, so an assertion inside `f` fails the caller with its own
696///   message.
697/// * **`wasm32`**: there is no second thread, so `f` runs inline, under a fresh
698///   [`Context`] whose floor is `bytes` below the calling frame: every check `f` makes
699///   sees a stack of `bytes`, as it would on a native thread of that size, and the
700///   caller's context is put back when `f` returns. The request is checked against the
701///   stack actually left above the running floor first, and one larger than that is
702///   refused with [`StackError::ExceedsFloor`] instead of running `f` into a trap.
703///
704/// # Errors
705///
706/// [`StackError::ExceedsFloor`] on `wasm32` when `bytes` exceeds what is left above the
707/// floor; [`StackError::Spawn`] natively when the thread cannot be started.
708pub fn on_stack<R: Send + 'static>(
709    bytes: usize,
710    f: impl FnOnce() -> R + Send + 'static,
711) -> Result<R, StackError> {
712    on_stack_scoped(bytes, f)
713}
714
715/// [`on_stack`] for a computation that borrows from the caller: `f` need not be
716/// `'static`, because the stack it runs on is gone before this returns.
717///
718/// Natively `f` runs on a scoped thread of `bytes` that is joined before the
719/// scope closes, so its borrows of the caller's locals are sound; on `wasm32` it
720/// runs inline under the same fresh [`Context`] as [`on_stack`], and a request
721/// over the floor is refused in the same way. Every other property — the fresh
722/// context, a panic resuming on the caller with its payload — is [`on_stack`]'s,
723/// which is this function with a `'static` computation.
724///
725/// # Errors
726///
727/// [`StackError::ExceedsFloor`] on `wasm32` when `bytes` exceeds what is left above the
728/// floor; [`StackError::Spawn`] natively when the thread cannot be started.
729pub fn on_stack_scoped<'env, R: Send + 'env>(
730    bytes: usize,
731    f: impl FnOnce() -> R + Send + 'env,
732) -> Result<R, StackError> {
733    #[cfg(not(target_arch = "wasm32"))]
734    {
735        on_thread(bytes, f)
736    }
737    #[cfg(target_arch = "wasm32")]
738    {
739        on_current_stack(bytes, f)
740    }
741}
742
743/// [`on_stack_scoped`] natively: `f` on a scoped thread of `bytes`, joined before
744/// the scope closes.
745#[cfg(not(target_arch = "wasm32"))]
746fn on_thread<'env, R: Send + 'env>(
747    bytes: usize,
748    f: impl FnOnce() -> R + Send + 'env,
749) -> Result<R, StackError> {
750    std::thread::scope(|scope| {
751        let handle = std::thread::Builder::new()
752            .stack_size(bytes)
753            .spawn_scoped(scope, f)
754            .map_err(|cause| StackError::Spawn(cause.into()))?;
755        match handle.join() {
756            Ok(value) => Ok(value),
757            Err(payload) => std::panic::resume_unwind(payload),
758        }
759    })
760}
761
762/// [`on_stack`] on `wasm32`: `f` inline, under a fresh [`Context`] whose floor is `bytes`
763/// below the calling frame, after checking that much stack is left above the running
764/// floor. Compiled natively too, so its refusal and its accepted neighbour are tested on
765/// every target.
766#[cfg_attr(
767    not(any(target_arch = "wasm32", test)),
768    expect(
769        dead_code,
770        reason = "the inline path is `on_stack_scoped` on wasm32 only"
771    )
772)]
773fn on_current_stack<R>(bytes: usize, f: impl FnOnce() -> R) -> Result<R, StackError> {
774    /// Puts the caller's context back when `f` returns or unwinds.
775    struct Restore(Context);
776    impl Drop for Restore {
777        fn drop(&mut self) {
778            replace_context(self.0);
779        }
780    }
781    let available = remaining();
782    if bytes > available {
783        return Err(StackError::ExceedsFloor {
784            requested: bytes,
785            available,
786        });
787    }
788    // `remaining` measured from a frame at or below this one, so the frame here has at
789    // least `bytes` above the running floor and the new floor does not pass under it.
790    let floor = stack_pointer().saturating_sub(bytes);
791    let restore = Restore(replace_context(Context::on_floor(floor)));
792    let value = f();
793    drop(restore);
794    Ok(value)
795}
796
797#[cfg(test)]
798mod tests {
799    use super::*;
800
801    /// `levels` frames of 4 KiB below the caller, then `at_bottom`.
802    fn deeper<T>(levels: usize, at_bottom: &dyn Fn() -> T) -> T {
803        if levels == 0 {
804            return at_bottom();
805        }
806        let frame = core::hint::black_box([0u8; 4096]);
807        let value = deeper(levels - 1, at_bottom);
808        core::hint::black_box(&frame);
809        value
810    }
811
812    /// The first measurement on a thread reads its floor, and what it reports is that
813    /// thread's own stack, and tracks the stack pointer: sixteen 4 KiB frames deeper, it
814    /// reports at least 64 KiB less.
815    #[test]
816    fn remaining_measures_the_thread_s_own_stack() {
817        const BYTES: usize = 4 * 1024 * 1024;
818        let (top, below) =
819            on_stack(BYTES, || (remaining(), deeper(16, &remaining))).expect("spawn");
820        // At least what was asked for, less the frames already live. (The C library may
821        // hand a thread more than it asked for, never less.)
822        assert!(
823            top > BYTES - 64 * 1024,
824            "{top} bytes left of at least {BYTES}"
825        );
826        let used = top - below;
827        assert!(
828            (16 * 4096..16 * 4096 + 32 * 1024).contains(&used),
829            "sixteen 4 KiB frames used {used} bytes"
830        );
831    }
832
833    /// On a small thread, `remaining` falls as frames are pushed, `is_low` turns true
834    /// once the margin is eaten into — and not before — and both recover as the frames
835    /// unwind.
836    #[test]
837    fn a_small_thread_runs_low_as_its_stack_is_consumed() {
838        let (top, low_at_top, reports) = on_stack(512 * 1024, || {
839            let top = remaining();
840            let low_at_top = is_low();
841            let mut reports = Vec::new();
842            let mut levels = 0;
843            loop {
844                let (left, low) = deeper(levels, &|| (remaining(), is_low()));
845                reports.push((left, low));
846                if low {
847                    break;
848                }
849                levels += 4;
850            }
851            (top, low_at_top, reports)
852        })
853        .expect("spawn");
854        assert!(
855            !low_at_top,
856            "{top} bytes left at the top of a 512 KiB thread"
857        );
858        assert!(
859            reports.windows(2).all(|pair| pair[1].0 < pair[0].0),
860            "remaining falls with every four frames: {reports:?}"
861        );
862        // `remaining` and `is_low` read the stack pointer in two different frames, a few
863        // hundred bytes apart at most; the kilobyte of slack below is that, not the step.
864        const FRAME_SLACK: usize = 1024;
865        let (last_left, last_low) = *reports.last().expect("at least one report");
866        assert!(
867            last_low && last_left < MARGIN_BYTES + FRAME_SLACK,
868            "{reports:?}"
869        );
870        assert!(
871            reports[..reports.len() - 1]
872                .iter()
873                .all(|&(left, low)| !low && left + FRAME_SLACK > MARGIN_BYTES),
874            "nothing is low while the margin is whole: {reports:?}"
875        );
876        assert!(
877            reports.len() > 2,
878            "the thread had room for several steps before the margin: {reports:?}"
879        );
880        assert!(
881            on_stack(512 * 1024, || !is_low()).expect("spawn"),
882            "a fresh thread is not low"
883        );
884    }
885
886    /// A floor installed above the running frame (a host that switched away without
887    /// putting the previous floor back) is read again rather than reporting nothing left.
888    #[test]
889    fn a_floor_above_the_frame_is_read_again() {
890        let (low, left) = on_stack(1024 * 1024, || {
891            let previous = replace_floor(stack_pointer() + 4096);
892            let low = is_low();
893            let left = remaining();
894            replace_floor(previous);
895            (low, left)
896        })
897        .expect("spawn");
898        assert!(!low);
899        assert!(left > MARGIN_BYTES, "{left} bytes left");
900    }
901
902    /// `replace_floor` hands back what it replaced, so a host can nest switches, and an
903    /// installed floor is the one measured against.
904    #[test]
905    fn replace_floor_sets_and_returns_the_floor() {
906        on_stack(256 * 1024, || {
907            let original = replace_floor(1);
908            assert_eq!(replace_floor(2), 1);
909            let sp = stack_pointer();
910            replace_floor(sp - 8192);
911            let left = remaining();
912            assert!(
913                (8192 - 1024..8192 + 1024).contains(&left),
914                "{left} bytes left above a floor 8 KiB down"
915            );
916            assert!(is_low(), "8 KiB is inside the margin");
917            assert_eq!(replace_floor(original), sp - 8192);
918            assert!(!is_low(), "the thread's own floor is back");
919        })
920        .expect("spawn");
921    }
922
923    /// While [`EXHAUSTED`] is installed nothing is left, whatever the stack pointer, and
924    /// putting the previous floor back restores the measurement.
925    #[test]
926    fn the_exhausted_floor_leaves_nothing() {
927        on_stack(1024 * 1024, || {
928            assert!(!is_low());
929            let previous = replace_floor(EXHAUSTED);
930            assert_eq!(remaining(), 0);
931            assert!(is_low());
932            assert_eq!(replace_floor(previous), EXHAUSTED);
933            assert!(!is_low());
934            assert!(remaining() > MARGIN_BYTES);
935        })
936        .expect("spawn");
937    }
938
939    /// A floor 1 KiB below the calling frame: inside the margin, so [`is_low`] is `true`.
940    fn low_floor() -> usize {
941        stack_pointer() - 1024
942    }
943
944    /// A walk that runs low inside a scope is refused with the construct it named, the
945    /// rest of the walk sees [`EXHAUSTED`], and closing the scope puts the real floor back.
946    /// Outside any scope the same low stack is not a refusal, and nothing is latched.
947    #[test]
948    fn a_scope_latches_a_low_walk_and_an_unscoped_walk_carries_on() {
949        on_stack(1024 * 1024, || {
950            assert!(!is_low(), "the thread's own floor, read");
951            let real = FLOOR.with(Cell::get);
952            let low = low_floor();
953            replace_floor(low);
954            assert!(!walk_is_low("unscoped walk"), "no scope, no refusal");
955            assert_eq!(replace_floor(real), low, "nothing latched");
956
957            let mut observed = None;
958            let refused = walk(|| {
959                replace_floor(low_floor());
960                let first = walk_is_low("scoped walk");
961                // The low floor is swapped for EXHAUSTED, so every later level stops too.
962                let latched = FLOOR.with(Cell::get);
963                observed = Some((first, latched, walk_is_low("a later level")));
964            });
965            assert_eq!(observed, Some((true, EXHAUSTED, true)));
966            assert_eq!(refused, Err("scoped walk"), "the first refusal is reported");
967            // The scope put back the floor it replaced — the low one this test installed.
968            assert!(is_low());
969            replace_floor(real);
970            assert!(!is_low(), "the thread's own floor is back");
971            assert_eq!(walk(|| walk_is_low("roomy walk")), Ok(false));
972        })
973        .expect("spawn");
974    }
975
976    /// A computation suspended inside a scope takes the scope with it: the context that
977    /// runs while it waits has none, so a walk there that runs low carries on and latches
978    /// nothing, and the suspended scope is still open — and still able to refuse — when
979    /// the computation resumes. The neighbouring control swaps the floor alone, as a host
980    /// that knew nothing of walk scopes would: the waiting context's walk then latches its
981    /// refusal in the suspended scope, leaves [`EXHAUSTED`] as the waiting context's floor,
982    /// and the suspended computation is refused for a walk it never ran.
983    #[test]
984    fn a_suspended_scope_stays_with_its_context() {
985        on_stack(1024 * 1024, || {
986            assert!(!is_low(), "the thread's own floor, read");
987            let real = FLOOR.with(Cell::get);
988            let mut observed = None;
989            let suspended = walk(|| {
990                // Suspend: the waiting context runs on its own, nearly exhausted, stack.
991                let waiting_floor = low_floor();
992                let job = replace_context(Context::on_floor(waiting_floor));
993                let waiting_low = walk_is_low("waiting walk");
994                let waiting = replace_context(job);
995                // Resume: the job's scope is open, and refuses a walk that runs low.
996                replace_floor(low_floor());
997                let job_low = walk_is_low("resumed walk");
998                observed = Some((
999                    waiting_low,
1000                    waiting == Context::on_floor(waiting_floor),
1001                    job_low,
1002                ));
1003            });
1004            assert_eq!(observed, Some((false, true, true)));
1005            assert_eq!(
1006                suspended,
1007                Err("resumed walk"),
1008                "the job's own refusal, no other"
1009            );
1010            // Closing the refusing scope put back the floor the job's walk replaced.
1011            assert!(is_low());
1012            replace_floor(real);
1013
1014            let waiting = walk(|| {
1015                let waiting_floor = low_floor();
1016                let job = replace_context(Context::on_floor(waiting_floor));
1017                let low = walk_is_low("waiting walk");
1018                let after = replace_context(job);
1019                (low, after == Context::on_floor(waiting_floor))
1020            });
1021            assert_eq!(
1022                waiting,
1023                Ok((false, true)),
1024                "the waiting walk had no scope and latched nothing; the job was not refused"
1025            );
1026            assert!(!is_low());
1027
1028            let mut observed = None;
1029            let floor_only = walk(|| {
1030                let job_floor = replace_floor(low_floor());
1031                let low = walk_is_low("waiting walk");
1032                observed = Some((low, replace_floor(job_floor)));
1033            });
1034            assert_eq!(
1035                observed,
1036                Some((true, EXHAUSTED)),
1037                "swapping the floor alone latches the waiting walk in the job's scope, and \
1038                 leaves the waiting context exhausted"
1039            );
1040            assert_eq!(
1041                floor_only,
1042                Err("waiting walk"),
1043                "and refuses the job for the waiting context's walk"
1044            );
1045            replace_floor(real);
1046        })
1047        .expect("spawn");
1048    }
1049
1050    /// A reserve takes its bytes off what every check sees, and gives them back when it
1051    /// is dropped; reserves add up. The neighbouring control: a reserve that leaves more
1052    /// than the margin is not low, one that eats into the margin is.
1053    #[test]
1054    fn a_reserve_is_kept_out_of_reach_until_dropped() {
1055        on_stack(4 * 1024 * 1024, || {
1056            let before = remaining();
1057            let outer = reserve(512 * 1024);
1058            assert_eq!(outer.bytes(), 512 * 1024);
1059            let within = remaining();
1060            assert!(
1061                (before - 512 * 1024 - 1024..before - 512 * 1024 + 1024).contains(&within),
1062                "{before} bytes before a 512 KiB reserve, {within} within it"
1063            );
1064            assert!(
1065                !is_low(),
1066                "a reserve that leaves more than the margin is not low"
1067            );
1068            let inner = reserve(within - MARGIN_BYTES / 2);
1069            assert!(is_low(), "a reserve that eats into the margin is low");
1070            drop(inner);
1071            assert!(!is_low());
1072            drop(outer);
1073            let after = remaining();
1074            assert!(
1075                (before - 1024..before + 1024).contains(&after),
1076                "{before} bytes before, {after} after the reserve is dropped"
1077            );
1078        })
1079        .expect("spawn");
1080    }
1081
1082    /// A floor read again inside a reserve — a native thread whose frame is found below
1083    /// the cached floor — is raised by what is reserved, so the reserve survives it.
1084    #[test]
1085    fn a_floor_read_again_keeps_the_reserve() {
1086        on_stack(4 * 1024 * 1024, || {
1087            let before = remaining();
1088            let kept = reserve(1024 * 1024);
1089            let raised = FLOOR.with(Cell::get);
1090            // As if the thread had switched stacks: the cached floor is above the frame.
1091            replace_floor(stack_pointer() + 4096);
1092            let within = remaining();
1093            assert_eq!(
1094                FLOOR.with(Cell::get),
1095                raised,
1096                "the floor read again is raised"
1097            );
1098            assert!(
1099                within + 1024 * 1024 <= before + 1024,
1100                "{within} bytes left inside a 1 MiB reserve of {before}"
1101            );
1102            drop(kept);
1103            assert!(remaining() + 1024 > before);
1104        })
1105        .expect("spawn");
1106    }
1107
1108    /// A reserve travels with its context: the computation that runs while it waits sees
1109    /// its own stack whole, and the reserve is still in force when it resumes.
1110    #[test]
1111    fn a_reserve_stays_with_its_context() {
1112        on_stack(4 * 1024 * 1024, || {
1113            let before = remaining();
1114            let kept = reserve(1024 * 1024);
1115            let real = FLOOR.with(Cell::get) - 1024 * 1024;
1116            let job = replace_context(Context::on_floor(real));
1117            let waiting = remaining();
1118            let back = replace_context(job);
1119            assert_eq!(
1120                back,
1121                Context::on_floor(real),
1122                "the waiting context reserved nothing"
1123            );
1124            assert!(
1125                waiting + 1024 > before,
1126                "{waiting} of {before} bytes for the waiting context"
1127            );
1128            assert!(
1129                remaining() + 1024 * 1024 <= before + 1024,
1130                "the reserve is back in force"
1131            );
1132            drop(kept);
1133            assert!(remaining() + 1024 > before);
1134        })
1135        .expect("spawn");
1136    }
1137
1138    /// Widening needs an open scope, keeps its bytes until the OUTERMOST scope closes
1139    /// (an inner scope closing gives back only its own), and refuses — changing nothing —
1140    /// a widening that would leave the calling frame less than the margin, while the
1141    /// neighbouring widening that leaves more is kept.
1142    #[test]
1143    fn a_widening_lasts_until_the_outermost_scope_closes() {
1144        on_stack(4 * 1024 * 1024, || {
1145            let before = remaining();
1146            assert!(!scoped());
1147            assert!(!widen(4096), "no scope: nothing would give the bytes back");
1148            assert_eq!(reserved(), 0);
1149            let outer = reserve(0);
1150            assert!(scoped());
1151            assert_eq!(outer.bytes(), 0);
1152            let inner = reserve(64 * 1024);
1153            assert!(
1154                widen(256 * 1024),
1155                "a widening that leaves the margin is kept"
1156            );
1157            assert_eq!(reserved(), 320 * 1024);
1158            let left = remaining();
1159            assert!(
1160                !widen(left - MARGIN_BYTES / 2),
1161                "a widening into the margin is refused"
1162            );
1163            assert_eq!(reserved(), 320 * 1024, "and changes nothing");
1164            assert!(widen(left - MARGIN_BYTES - 8192), "its neighbour is kept");
1165            let widened = 256 * 1024 + (left - MARGIN_BYTES - 8192);
1166            drop(inner);
1167            assert_eq!(
1168                reserved(),
1169                widened,
1170                "the inner scope gives back its own only"
1171            );
1172            assert!(scoped());
1173            drop(outer);
1174            assert_eq!(
1175                reserved(),
1176                0,
1177                "the outermost scope gives back every widening"
1178            );
1179            assert!(!scoped());
1180            let after = remaining();
1181            assert!(
1182                (before - 1024..before + 1024).contains(&after),
1183                "{before} bytes before, {after} after"
1184            );
1185        })
1186        .expect("spawn");
1187    }
1188
1189    /// A widening travels with its context, like the scope it belongs to.
1190    #[test]
1191    fn a_widening_stays_with_its_context() {
1192        on_stack(4 * 1024 * 1024, || {
1193            let before = remaining();
1194            let scope = reserve(0);
1195            assert!(widen(1024 * 1024));
1196            let real = FLOOR.with(Cell::get) - 1024 * 1024;
1197            let job = replace_context(Context::on_floor(real));
1198            assert!(!scoped(), "the waiting context has no scope");
1199            assert!(!widen(4096));
1200            assert!(remaining() + 1024 > before);
1201            let back = replace_context(job);
1202            assert_eq!(back, Context::on_floor(real));
1203            assert!(scoped());
1204            assert!(remaining() + 1024 * 1024 <= before + 1024);
1205            drop(scope);
1206            assert!(remaining() + 1024 > before);
1207            assert_eq!(reserved(), 0);
1208        })
1209        .expect("spawn");
1210    }
1211
1212    /// A walk scope that refuses inside a reserve and closes after the reserve is dropped
1213    /// puts back the real floor, not the raised one.
1214    #[test]
1215    fn a_refusal_latched_inside_a_reserve_restores_the_real_floor() {
1216        on_stack(4 * 1024 * 1024, || {
1217            let _ = remaining();
1218            let real = FLOOR.with(Cell::get);
1219            let refused = walk(|| {
1220                let kept = reserve(remaining() - MARGIN_BYTES / 2);
1221                assert!(
1222                    walk_is_low("reserved walk"),
1223                    "the reserve eats into the margin"
1224                );
1225                assert_eq!(FLOOR.with(Cell::get), EXHAUSTED);
1226                drop(kept);
1227                assert_eq!(
1228                    FLOOR.with(Cell::get),
1229                    EXHAUSTED,
1230                    "the refusal stays latched"
1231                );
1232            });
1233            assert_eq!(refused, Err("reserved walk"));
1234            assert_eq!(FLOOR.with(Cell::get), real, "the real floor is back");
1235            assert!(!is_low());
1236        })
1237        .expect("spawn");
1238    }
1239
1240    /// `on_stack` runs its computation on a stack of its own, at least the size asked
1241    /// for: what the computation measures is that stack, not the caller's, and its value
1242    /// comes back.
1243    #[test]
1244    fn on_stack_runs_the_computation_on_a_stack_of_the_requested_size() {
1245        const BYTES: usize = 512 * 1024;
1246        let caller_sp = stack_pointer();
1247        let caller_floor = caller_sp - remaining();
1248        let (sp, left) =
1249            on_stack(BYTES, || (stack_pointer(), remaining())).expect("a 512 KiB thread starts");
1250        // The operating system may round a thread's stack up to a page or its minimum, and
1251        // the C library may hand a thread a cached stack several times the request, never
1252        // less; 64 KiB covers the frames already live.
1253        assert!(
1254            left >= BYTES - 64 * 1024,
1255            "{left} bytes left on a {BYTES}-byte stack"
1256        );
1257        assert!(
1258            !(caller_floor..=caller_sp).contains(&sp),
1259            "the computation ran on the caller's stack ({sp:#x} in {caller_floor:#x}..={caller_sp:#x})"
1260        );
1261        assert_eq!(on_stack(BYTES, || 7_u8).expect("runs"), 7);
1262    }
1263
1264    /// A panic inside `on_stack`'s computation resumes on the caller with the original
1265    /// payload, so an assertion inside it fails the caller with its own message.
1266    #[test]
1267    fn on_stack_resumes_a_panic_with_its_own_payload() {
1268        let caught = std::panic::catch_unwind(|| {
1269            on_stack(256 * 1024, || -> () {
1270                panic!("the inner assertion's message")
1271            })
1272        })
1273        .expect_err("the panic reaches the caller");
1274        let message = caught
1275            .downcast_ref::<&str>()
1276            .copied()
1277            .expect("a string payload");
1278        assert_eq!(message, "the inner assertion's message");
1279    }
1280
1281    /// The inline path refuses a request larger than the stack left above the running
1282    /// floor, typed, and runs its neighbour just inside it — the boundary drawn from a
1283    /// floor installed a known distance below the frame.
1284    #[test]
1285    fn an_over_floor_request_is_refused_and_an_in_floor_request_runs() {
1286        on_stack(2 * 1024 * 1024, || {
1287            let previous = replace_floor(stack_pointer() - 512 * 1024);
1288            let available = remaining();
1289
1290            let over = on_current_stack(available + 4096, || unreachable!("not run"));
1291            match over {
1292                Err(StackError::ExceedsFloor {
1293                    requested,
1294                    available: reported,
1295                }) => {
1296                    assert_eq!(requested, available + 4096);
1297                    assert!(reported <= available, "{reported} of {available}");
1298                }
1299                other => panic!("an over-floor request is refused, got {other:?}"),
1300            }
1301            assert!(
1302                matches!(
1303                    on_current_stack(usize::MAX, || ()),
1304                    Err(StackError::ExceedsFloor { .. })
1305                ),
1306                "the largest request is refused"
1307            );
1308
1309            let inside = on_current_stack(available - 4096, remaining)
1310                .expect("a request inside the floor runs");
1311            assert!(inside <= available - 4096, "{inside} of {available}");
1312
1313            replace_floor(previous);
1314        })
1315        .expect("spawn");
1316    }
1317
1318    /// The inline path gives its computation a fresh context of the requested size — a
1319    /// small request is inside the margin, a large one is not, no reserve scope of the
1320    /// caller's is visible — and puts the caller's context back afterwards.
1321    #[test]
1322    fn the_inline_path_runs_under_a_fresh_context_and_restores_the_caller_s() {
1323        on_stack(4 * 1024 * 1024, || {
1324            let _ = remaining();
1325            let kept = reserve(0);
1326            let floor = FLOOR.with(Cell::get);
1327            assert!(scoped());
1328
1329            let (low, inner_scoped) =
1330                on_current_stack(MARGIN_BYTES / 2, || (is_low(), scoped())).expect("runs");
1331            assert!(low, "half the margin is inside it");
1332            assert!(
1333                !inner_scoped,
1334                "the caller's reserve scope stays with the caller"
1335            );
1336            assert!(
1337                !on_current_stack(4 * MARGIN_BYTES, is_low).expect("runs"),
1338                "four margins are not low"
1339            );
1340
1341            assert!(scoped(), "the caller's scope is back");
1342            assert_eq!(FLOOR.with(Cell::get), floor, "the caller's floor is back");
1343            drop(kept);
1344        })
1345        .expect("spawn");
1346    }
1347
1348    /// The typed refusal says what was asked for and what was left.
1349    #[test]
1350    fn the_refusal_names_the_request_and_what_was_left() {
1351        let error = StackError::ExceedsFloor {
1352            requested: 2048,
1353            available: 1024,
1354        };
1355        assert_eq!(
1356            error.to_string(),
1357            "a 2048-byte stack was requested, but only 1024 bytes are left above the \
1358             running stack's floor"
1359        );
1360        assert!(std::error::Error::source(&error).is_none());
1361    }
1362}