# Tailcall

[![CI](https://github.com/alecdotninja/tailcall/actions/workflows/ci.yml/badge.svg)](https://github.com/alecdotninja/tailcall/actions/workflows/ci.yml)
[![Current Crates.io Version](https://img.shields.io/crates/v/tailcall.svg)](https://crates.io/crates/tailcall)
[![Docs](https://docs.rs/tailcall/badge.svg)](https://docs.rs/tailcall)

`tailcall` lets you write deeply recursive functions in Rust without blowing the stack—on stable Rust.

It provides **explicit, stack-safe tail calls** using a lightweight trampoline runtime, with a macro that keeps usage ergonomic.

The runtime crate is `no_std`, so it can be used on targets without the standard library.

If the proposed [`become` keyword](https://internals.rust-lang.org/t/pre-rfc-explicit-proper-tail-calls/3797/16) is ever stabilized, it will likely be the preferred solution for proper tail calls.

---

## Installation

```toml
[dependencies]
tailcall = "~2"
```

---

## Quick Example

```rust
use tailcall::tailcall;

#[tailcall]
fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        a
    } else {
        tailcall::call! { gcd(b, a % b) }
    }
}

assert_eq!(gcd(12, 18), 6);
```

That’s the core API:

* mark the function with `#[tailcall]`
* wrap recursive tail calls with `tailcall::call!`

This runs in constant stack space, even for very large inputs.

---

## When to Use This

`tailcall` is useful when:

* you want to write **naturally recursive code** without risking stack overflow
* converting to loops would make the code harder to read
* you’re working with **mutual recursion** or recursive traversals
* you want stack safety without nightly features

It may not be ideal when:

* a simple loop is clearer
* you need maximum performance (there is some trampoline overhead)

---

## Cost

`tailcall` avoids heap allocation.

That is an important difference from some other stack-safe recursion libraries with a similar
interface, which build the recursive state machine on the heap.

The main runtime cost here is an indirect call at each `Thunk::bounce` step. In favorable cases,
the optimizer may be able to devirtualize that call, but you should still think of the trampoline
as paying for an extra dispatch per bounced step.

---

## How It Works (Briefly)

Rust does not guarantee tail call optimization. Deep recursion can overflow the stack.

`tailcall` avoids this by using a **trampoline**:

* each recursive step returns a deferred computation (`Thunk`)
* the runtime repeatedly executes those steps in a loop
* no additional stack frames are created

The key operation is:

* `Thunk::bounce(...)` — produces the *next step* instead of recursing

This turns recursion into iteration under the hood.

---

## Macro Usage

Most users only need the macro.

### Basic Pattern

```rust
#[tailcall]
fn f(...) -> T {
    if done {
        result
    } else {
        tailcall::call! { f(next_args...) }
    }
}
```

Only calls wrapped in `tailcall::call!` are stack-safe.

---

### Mutual Recursion

```rust
use tailcall::tailcall;

#[tailcall]
fn is_even(x: u128) -> bool {
    if x == 0 {
        true
    } else {
        tailcall::call! { is_odd(x - 1) }
    }
}

#[tailcall]
fn is_odd(x: u128) -> bool {
    if x == 0 {
        false
    } else {
        tailcall::call! { is_even(x - 1) }
    }
}
```

---

### Methods

```rust
use tailcall::tailcall;

struct Parity;

impl Parity {
    #[tailcall]
    fn is_even(&self, x: u128) -> bool {
        if x == 0 {
            true
        } else {
            tailcall::call! { self.is_odd(x - 1) }
        }
    }

    #[tailcall]
    fn is_odd(&self, x: u128) -> bool {
        if x == 0 {
            false
        } else {
            tailcall::call! { self.is_even(x - 1) }
        }
    }
}
```

---

### Mixed Recursion

Only `tailcall::call!` sites are trampoline-backed:

```rust
use tailcall::tailcall;

#[tailcall]
fn sum(n: u64) -> u64 {
    match n {
        0 => 0,
        _ if n % 2 == 0 => {
            let partial = sum(n - 1); // normal recursion
            n + partial
        }
        _ => tailcall::call! { sum(n - 1) },
    }
}
```

---

### Recommended Pattern: Tail-Recursive Helper

```rust
use tailcall::tailcall;

fn factorial(n: u64) -> u64 {
    #[tailcall]
    fn inner(acc: u64, n: u64) -> u64 {
        if n == 0 {
            acc
        } else {
            tailcall::call! { inner(acc * n, n - 1) }
        }
    }

    inner(1, n)
}
```

---

## Using the Runtime Directly

The macro is just a thin layer over `runtime::Thunk`.

A `runtime::Thunk<T>` is a fixed-size deferred value from a computation, so it can live on the
stack. It may contain the value directly or a type-erased closure that will eventually produce the
value.

You build a chain of steps, then execute it with `.call()`.

### Core constructors

* `Thunk::value(x)` — final result
* `Thunk::new(f)` — deferred computation returning a value
* `Thunk::bounce(f)` — deferred computation returning another `Thunk` (**this is what enables stack safety**)

---

### Example

```rust
use tailcall::runtime::Thunk;

fn count_down(n: u64) -> u64 {
    build(n).call()
}

fn build(n: u64) -> Thunk<'static, u64> {
    Thunk::bounce(move || {
        if n == 0 {
            Thunk::value(0)
        } else {
            build(n - 1)
        }
    })
}
```

`Thunk::bounce` ensures each step returns control to the runtime loop instead of growing the call stack.

---

## What the Macro Generates

At a high level, this:

```rust
#[tailcall]
fn f(...) -> T { ... }
```

becomes:

* a wrapper that calls `.call()`
* a hidden builder that returns `Thunk<T>`

So the macro:

* rewrites your function into a trampoline-compatible form
* leaves control flow and logic unchanged

---

## Limitations

### Explicit Tail Calls

Tail-recursive transitions must be written with `tailcall::call!`.

Plain recursive calls are left alone, which means they still use the native Rust call stack.

### Simple Argument Patterns

`#[tailcall]` currently only supports simple identifier arguments.

Patterns in function parameters are not rewritten by the macro.

### `?` Is Not Supported

The `?` operator is not supported inside `#[tailcall]` functions on stable Rust.

Use `match` or explicit early returns instead.

### Trait Methods

Methods in ordinary `impl` blocks are supported.

Trait methods are not supported.

### `async fn` and `const fn`

`#[tailcall]` does not support `async fn` or `const fn`.

### Closure Size Limit

Each deferred closure is stored in a fixed-size inline slot (~48 bytes).

**Closures that exceed that size panic when the `Thunk` is constructed.**

Macro-generated helper thunks are subject to the same limit, so functions with enough arguments or captured state can also exceed it.

---

## Development

For normal development, the main local checks are:

```bash
cargo test
cargo test --doc
cargo +nightly miri test --all
cargo fmt --all -- --check
cargo clippy --all
cargo doc --no-deps
```

If you are changing the public docs or runtime internals, it is also worth doing a quick end-to-end smoke test from a fresh crate that depends on the published version from crates.io.

---

## Publishing

`tailcall` and `tailcall-impl` are released together.

1. Update the shared workspace version in `Cargo.toml`.
   Also update the matching `tailcall` and `tailcall-impl` entries in `[workspace.dependencies]`.
2. Run the release checks:

```bash
cargo test
cargo test --doc
cargo doc --no-deps
```

3. Commit the release version bump.
4. Publish `tailcall-impl` first:

```bash
cargo publish -p tailcall-impl
```

5. Publish `tailcall` after the proc-macro crate is available:

```bash
cargo publish -p tailcall
```

6. Tag the release from `main` and push the commit and tag:

```bash
git tag vX.Y.Z
git push origin main
git push origin vX.Y.Z
```

---

## License

Tailcall is distributed under the terms of both the MIT license and the Apache License (Version
2.0).

See [LICENSE-APACHE](LICENSE-APACHE), [LICENSE-MIT](LICENSE-MIT), and [COPYRIGHT](COPYRIGHT) for
details.
