carta_core/
stack.rs

1//! Running recursion-heavy work on a large, dedicated stack.
2//!
3//! Some conversions recurse as deeply as their input nests (walking a document tree, decoding a
4//! deeply nested markup fragment), so a legitimately deep input can exhaust a small caller stack.
5//! [`on_deep_stack`] runs such work on a worker thread that reserves a generous stack for it.
6
7/// Virtual stack reserved for work whose recursion depth tracks input nesting. Large enough that
8/// even adversarially deep input cannot exhaust it; on demand-paged systems the reservation stays
9/// uncommitted until touched, so the cost is address space rather than resident memory.
10pub const DEEP_STACK: usize = 256 * 1024 * 1024;
11
12/// The outcome of running work on a dedicated large stack.
13#[derive(Debug)]
14pub enum DeepStack<T> {
15    /// The work ran to completion, yielding its value.
16    Completed(T),
17    /// A worker thread started but the work panicked while running on it.
18    Panicked,
19    /// No worker thread could be spawned, so the work never ran.
20    NotSpawned,
21}
22
23/// Runs `work` on a dedicated thread with a large reserved stack ([`DEEP_STACK`]), so deeply nested
24/// input cannot overflow the caller's stack.
25///
26/// The closure is consumed whether or not a worker starts, so a caller that wants to retry on the
27/// current stack expresses the work as a re-callable expression and rebuilds it in the
28/// [`DeepStack::NotSpawned`] arm.
29pub fn on_deep_stack<T, F>(work: F) -> DeepStack<T>
30where
31    T: Send,
32    F: FnOnce() -> T + Send,
33{
34    let joined = std::thread::scope(|scope| {
35        std::thread::Builder::new()
36            .stack_size(DEEP_STACK)
37            .spawn_scoped(scope, work)
38            .map(std::thread::ScopedJoinHandle::join)
39    });
40    match joined {
41        Ok(Ok(value)) => DeepStack::Completed(value),
42        Ok(Err(_)) => DeepStack::Panicked,
43        Err(_) => DeepStack::NotSpawned,
44    }
45}
46
47#[cfg(test)]
48mod tests {
49    use super::{DeepStack, on_deep_stack};
50
51    #[test]
52    fn completed_work_returns_its_value() {
53        match on_deep_stack(|| 2 + 3) {
54            DeepStack::Completed(value) => assert_eq!(value, 5),
55            _ => panic!("work should complete"),
56        }
57    }
58
59    #[test]
60    fn deep_recursion_does_not_overflow_a_small_caller_stack() {
61        fn descend(depth: usize) -> usize {
62            if depth == 0 {
63                0
64            } else {
65                1 + descend(depth - 1)
66            }
67        }
68        let outcome = std::thread::Builder::new()
69            .stack_size(64 * 1024)
70            .spawn(|| match on_deep_stack(|| descend(200_000)) {
71                DeepStack::Completed(value) => value,
72                _ => 0,
73            })
74            .expect("spawn shallow caller")
75            .join()
76            .expect("shallow caller finished");
77        assert_eq!(outcome, 200_000);
78    }
79}
carta_core/stack.rs

carta_core/
stack.rs
