# vuot

*lea mu? vuot?*

Run recursive functions without overflowing the stack.

## Why?

Many algorithms are most naturally defined with recursion.  Unfortunately,
most programming languages limit you to a small, fixed-size stack, making such
implementations unreliable for larger inputs - even if you have plenty of heap
memory!

vuot takes advantage of Rust's `async` machinery to allocate your stack frames
on the heap, bypassing this issue.  Note that a stack overflow can still occur,
but _only if you run out of heap memory_.  That is, vuot unifies stack overflows
with any other out-of-memory condition, hopefully making them a little less
unpredictable and horrible.

Note that vuot is not all rainbows and sunshine: backtraces are no longer very
useful (since it's only ever polling the topmost future on the stack), and there
is a fair amount of overhead in it all.

## How?

Briefly, use `stack.run(future).await` instead of `Box::pin(future).await`.
Call `vuot::run` with either an `async fn(Stack<'_>) -> T` or something that
implements `vuot::StacklessFn<'_, T>` to get a stack.

There's a type `vuot::Stack<'_>` that references a "virtual" call stack.  Pass
it a future in `Stack::run` to invoke that future without growing the call
stack.

```rust
use vuot::{call, Stack};

async fn fib(stack: Stack<'_>, n: usize) -> usize {
    if n < 2 {
        n
    } else {
        stack.run(fib(stack, n - 1)).await + stack.run(fib(stack, n - 2)).await
    }
}
```

If you want to pass data into the future you will `run`, you have to implement
the `vuot::StacklessFn` trait (at least until async closures stabilize).

```rust
use vuot::StacklessFn;

struct Fib<'local>(&'local usize);
impl<'a> StacklessFn<'a, usize> for Fib<'_> {
    async fn call(self, stack: Stack<'_>) -> usize {
        fib(stack, *self.0)
    }
}
```

Finally, `vuot::run` takes in a `StacklessFn` and hands it a stack.

```rust
use vuot::run;

async fn main() {
    let n = 40;
    println!("fib(40) = {}", run(Fib(&n)));
}
```

## Optional features

By default, this crate uses `Box` to allocate individual stack frames.  Enable
the `bumpalo` feature to use the bump allocator from the
[bumpalo](https://crates.io/crates/bumpalo) crate instead.

```toml
vuot = { version = "0.1", features = ["bumpalo"] }
```

This tends to reduce the overhead of each `stack.run` invocation, though it does
vary how much.  If your program is spending a lot of time allocating and freeing
memory due to `stack.run`s, this may be worth a try.

The `bumpalo` feature uses the unstable `allocator_api` feature, and therefore
requires a nightly compiler.

## Safety

Although the entire public API is safe, the crate does internally use a good
amount of `unsafe` blocks and functions.  I do actively test with Miri, and am
working on reducing and improving this.  That said, I am only human and have
likely made mistakes.  Don't rely on this to be perfect!

## Alternatives

- [stacker](https://crates.io/crates/stacker) lets you grow the actual call
  stack as necessary
- [recursive](https://crates.io/crates/recursive) lets you put a proc-macro on
  recursive functions, using stacker under the hood
- [reblessive](https://crates.io/crates/reblessive) uses the same idea as this
  crate.  In my brief testing, it tends to be a bit faster than vuot, but does
  not support running arbitrary futures inside its virtual stack.