StackSafe

StackSafe enables safe execution of deeply recursive algorithms through intelligent stack management, eliminating the need for manual stack size tuning or complex refactoring to iterative approaches.

Quick Start

Add StackSafe to your Cargo.toml:

[dependencies]
stacksafe = "0.1"

Transform recursive functions with the #[stacksafe] attribute:

use stacksafe::stacksafe;

#[stacksafe]
fn factorial(n: u64) -> u64 {
    if n <= 1 { 1 } else { n * factorial(n - 1) }
}

#[stacksafe]
fn fibonacci(n: u64) -> u64 {
    match n {
        0 | 1 => n,
        _ => fibonacci(n - 1) + fibonacci(n - 2),
    }
}

// Safe for any input size
println!("Large factorial: {}", factorial(10000));

Recursive Data Structures

Use StackSafe<T> to wrap recursive data structures:

use stacksafe::{stacksafe, StackSafe};

#[derive(Debug, Clone)]
enum BinaryTree {
    Leaf(i32),
    Node {
        value: i32,
        left: StackSafe<Box<BinaryTree>>,
        right: StackSafe<Box<BinaryTree>>,
    },
}

#[stacksafe]
fn tree_sum(tree: &BinaryTree) -> i32 {
    match tree {
        BinaryTree::Leaf(value) => *value,
        BinaryTree::Node { value, left, right } => {
            value + tree_sum(left) + tree_sum(right)
        }
    }
}

How It Works

• #[stacksafe] attribute monitors remaining stack space at function entry points. When available space falls below a threshold (default: 128 KiB), it automatically allocates a new stack segment (default: 2 MiB) and continues execution.

• StackSafe<T> is a wrapper type that transparently implement common traits like Clone, Debug, and PartialEq with #[stacksafe] support, allowing you to use it in recursive data structures without losing functionality.

Configuration

Customize stack management behavior:

use stacksafe::{set_minimum_stack_size, set_stack_allocation_size};

// Trigger allocation when < 64 KiB remaining (default: 128 KiB).
set_minimum_stack_size(64 * 1024);

// Allocate 4 MiB stacks for deep recursion (default: 2 MiB).
set_stack_allocation_size(4 * 1024 * 1024);

Feature Flags

StackSafe supports several optional features:

• serde: Enables stack-safe serialization and deserialization for StackSafe<T> wrappers.
• derive-visitor: Provides stack-safe visitor pattern implementations for StackSafe<T>.

Platform Support

StackSafe works on all major platforms supported by the stacker crate, including:

• Linux (x86_64, ARM64, others)
• macOS (Intel, Apple Silicon)
• Windows (MSVC, GNU)
• FreeBSD, NetBSD, OpenBSD
• And more...

License

This project is licensed under the Apache-2.0 license.

Acknowledgments

Inspired by the the excellent recursive by Orson Peters.