Blowing the stack is one of the few ways to kill a Rust program that you can't really recover from. On Unix systems, the area just past the end of the stack is set up as a guard page</a> (either by the host OS or by Rust's own setup code) so that trying to access it will trigger a The reason that this is an abort (which you can't catch and always causes program exit) as opposed to a panic is because it's effectively impossible to guarantee anything about the state of the world. In particular, you might be in the middle of executing some Languages with a runtime (Java, Python, Go, Javascript) can just have the runtime manually check the stack, but we don't have that. The simplest answer is to have a Easy, simple, and basically what I wound up doing when I ran into this problem. But you don't need a blog post to tell you how to pass a parameter, and I wanted to show off. So let's have some fun with it.</p>
If we're going to make this into something reusable, let's define some helpers. For reasons that will become apparent shortly, we define the natural numbers using the standard Peano encoding</a>:</p>
and implement a helper function that automates the recursion:</p>
We can see that this produces the behavior we want by writing a test sum function:</p>
SIGSEGV</code> or SIGBUS</code> signal, and as part of the general setup code Rust adds to every program, it installs a signal handler that checks if the address that caused the signal is a guard page, and if so, aborts your entire program. The code for setting it up</a> is straightforward (and has some fun SAFETY</code> comments too).</p>
unsafe</code> code, an FFI handler, or some other thing where allowing execution to continue would violate safety guarantees. Plus, when the signal handler returns, you're still out of stack space, so you'd have to unwind without allocating any more stack! Even backtrace-on-stack-overflow</a>, which does what the name implies, aborts immediately after printing the backtrace and comes with a note saying that it's "unsuited for being enabled in production".</p>
depth</code> counter and decrement it on every recursive call:</p>
#[test]</span></span>
fn</span> recursive</span>() {</span></span>
fn</span> sum</span>(depth</span>:</span> usize</span>, xs</span>: &</span>[</span>u64</span>])</span> -></span> Option</span><</span>u64</span>> {</span></span>
if</span> xs</span>.</span>is_empty</span>() {</span> return</span> Some</span>(</span>0</span>) }</span></span>
if</span> depth</span> ==</span> 0</span> {</span> return</span> None</span> }</span></span>
Some</span>(xs[</span>0</span>]</span> +</span> sum</span>(depth</span> -</span> 1</span>,</span> &</span>xs[</span>1</span>..</span>])</span>?</span>)</span></span>
}</span></span>
assert_eq!</span>(</span>sum</span>(</span>2</span>,</span> &</span>[</span>3</span>,</span> 4</span>]),</span> Some</span>(</span>7</span>));</span></span>
assert_eq!</span>(</span>sum</span>(</span>0</span>,</span> &</span>[</span>3</span>,</span> 4</span>]),</span> None</span>);</span></span>
}</span></span></code></pre>
enum</span> Nat</span> {</span></span>
Z</span>,</span></span>
S</span>(</span>Box</span><</span>Nat</span>>)</span></span>
}</span></span></code></pre>
impl</span> Nat</span> {</span></span>
fn</span> recurse</span><</span>In</span>,</span> Out</span>>(</span>self</span>,</span> mut</span> f</span>:</span> impl</span> FnMut</span>(</span>Nat</span>,</span> In</span>)</span> -></span> Option</span><</span>Out</span>>, val</span>:</span> In</span>)</span> -></span> Option</span><</span>Out</span>> {</span></span>
match</span> self</span> {</span></span>
Nat</span>::</span>Z</span> =></span> None</span>,</span></span>
Nat</span>::</span>S</span>(nat)</span> =></span> f</span>(</span>*</span>nat, val)</span></span>
}</span></span>
} </span></span>
}</span></span></code></pre>
#[test]</span></span>
fn</span> nat_to_usize</span>() {</span></span>
fn</span> sum</span>(depth</span>:</span> Nat</span>, xs</span>: &</span>[</span>u64</span>])</span> -></span> Option</span><</span>u64</span>> {</span></span>
if</span> xs</span>.</span>is_empty</span>() {</span></span>
Some</span>(</span>0</span>)</span></span>
}</span> else</span> {</span></span>
Some</span>(xs[</span>0</span>]</span> +</span> depth</span>.</span>recurse</span>(sum,</span> &</span>xs[</span>1</span>..</span>])</span>?</span>
gay robot noises - /var/log/ash · May 25, 2025
Type-level Bounded Recursion in Rust
0Sign in to vote or save
This page cannot be shown here. You can still read it on the original site — the toolbar below keeps your place in the directory.
Blowing the stack is one of the few ways to kill a Rust program that you can't really recover from. On Unix systems, the area just past the end of the stack is set up as a guard page (either by the host OS or by Rust's own setup code) so that trying to access it will trigger a SIGSEGV or SIGBUS signal, and as part of the general setup code Rust adds to every program, it installs a signal…