Tailcall

tailcall provides stack-safe tail calls on stable Rust.

It does this with an explicit trampoline runtime backed by a small stack-allocated internal thunk slot. The macro API rewrites a function into:

• a public wrapper that calls tailcall::trampoline::run(...)
• a hidden builder function that produces tailcall::trampoline::Action values

This is still a trampoline approach, but it no longer rewrites recursive calls into a local loop. Instead, each tail step is represented as a thunk and executed by the runtime.

Eventually, this crate may be superseded by the become keyword.

Installation

Add this to your Cargo.toml:

[dependencies]
tailcall = "~2"

Usage

Mark a function with #[tailcall], and use tailcall::call! at each recursive tail-call site:

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);

The explicit tailcall::call! is part of the API now. Recursive calls are not rewritten implicitly.

More Macro Examples

The macro also works well for stateful traversals over borrowed input:

use tailcall::tailcall;

#[tailcall]
fn sum_csv_numbers(rest: &[u8], total: u64, current: u64) -> u64 {
    match rest {
        [digit @ b'0'..=b'9', tail @ ..] => {
            let current = current * 10 + u64::from(digit - b'0');
            tailcall::call! { sum_csv_numbers(tail, total, current) }
        }
        [b' ' | b',', tail @ ..] => {
            let total = total + current;
            tailcall::call! { sum_csv_numbers(tail, total, 0) }
        }
        [] => total + current,
        [_other, tail @ ..] => {
            tailcall::call! { sum_csv_numbers(tail, total, current) }
        }
    }
}

assert_eq!(sum_csv_numbers(b"10, 20, 3", 0, 0), 33);

Most users should only need #[tailcall] plus tailcall::call!.

Macro-Based Mutual Recursion

Mutual recursion works through the macro too. Each participating function just needs #[tailcall], and each tail-call site must use tailcall::call!:

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) }
    }
}

assert!(is_even(1000));
assert!(is_odd(1001));

Methods

Methods in impl blocks work too, including recursive calls written with method syntax on self:

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) }
        }
    }
}

let parity = Parity;
assert!(parity.is_even(1000));

Mixed Recursion

Mixed recursion also works in a single #[tailcall] function. Only call sites wrapped in tailcall::call! are trampoline-backed; plain recursive calls stay ordinary Rust calls:

use tailcall::tailcall;

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

assert_eq!(mixed_recursion_sum(6), 12);

If only part of a larger algorithm is tail-recursive, it can still be cleaner to put that part in a helper and annotate the helper:

use tailcall::tailcall;

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

    factorial_inner(1, n)
}

fn weighted_countdown(n: u64) -> u64 {
    if n <= 3 {
        n + factorial(n)
    } else {
        factorial(n / 2)
    }
}

assert_eq!(weighted_countdown(3), 9);
assert_eq!(weighted_countdown(8), 24);

This helper pattern is often the cleanest approach when one inner phase is tail-recursive and the rest of the algorithm is not.

Advanced: Direct Runtime

The public runtime surface is:

• trampoline::Action
• trampoline::call
• trampoline::done
• trampoline::run

The usual pattern is:

1. write an entry-point function that calls trampoline::run(...)
2. write one or more builder functions that return trampoline::Action
3. return trampoline::done(...) for terminal states
4. return another builder function's Action for recursive transitions

For example:

use tailcall::trampoline;

fn is_even(x: u128) -> bool {
    trampoline::run(build_is_even_action(x))
}

#[inline(always)]
fn build_is_even_action(x: u128) -> trampoline::Action<'static, bool> {
    trampoline::call(move || {
        if x > 0 {
            build_is_odd_action(x - 1)
        } else {
            trampoline::done(true)
        }
    })
}

fn is_odd(x: u128) -> bool {
    trampoline::run(build_is_odd_action(x))
}

#[inline(always)]
fn build_is_odd_action(x: u128) -> trampoline::Action<'static, bool> {
    trampoline::call(move || {
        if x > 0 {
            build_is_even_action(x - 1)
        } else {
            trampoline::done(false)
        }
    })
}

The direct runtime is still useful as an escape hatch for advanced manual control. For example, one function can skip separators while another reads digits from the same slice, passing control back and forth by returning trampoline::Action values until trampoline::run produces the final result.

Macro Expansion Shape

At a high level, this:

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

becomes roughly:

fn gcd(a: u64, b: u64) -> u64 {
    tailcall::trampoline::run(__tailcall_build_gcd(a, b))
}

#[inline(always)]
fn __tailcall_build_gcd<'tailcall>(a: u64, b: u64) -> tailcall::trampoline::Action<'tailcall, u64> {
    tailcall::trampoline::call(move || {
        if b == 0 {
            tailcall::trampoline::done(a)
        } else {
            __tailcall_build_gcd(b, a % b)
        }
    })
}

The exact expansion is different in edge cases, but this is the core model.

Limitations

Current macro limitations:

• Tail-call sites must use tailcall::call! { path(args...) } or tailcall::call! { self.method(args...) }.
• Function arguments must use simple identifier patterns.
• ? is not supported inside #[tailcall] functions on stable Rust. Use match or explicit early returns instead.
• Trait methods are not supported yet.
• In mixed recursion, only tailcall::call! sites are trampoline-backed; plain recursive calls still use the native call stack.
• async fn and const fn are not supported.

The runtime itself can be used directly if the macro is too restrictive for a particular use case.

Safety Notes

The thunk runtime uses unsafe code internally to type-erase FnOnce values into a fixed-size stack slot. The current test suite includes:

• ordinary correctness tests
• stack-behavior tests
• destructor-behavior tests
• Miri runs over the runtime-oriented tests

Development

Common commands:

cargo test
cargo +nightly miri test --all
cargo fmt --all
cargo clippy --all

Release Process

This workspace publishes two crates:

• tailcall-impl
• tailcall

Release them together.

1. Update the workspace version in the root Cargo.toml.
2. Update the matching versions in the root workspace.dependencies section.
3. Update the installation snippet in this README if the major version changed.
4. Run:

cargo test
cargo +nightly miri test --all
cargo bench --all --no-run

5. Publish tailcall-impl first:

cargo publish -p tailcall-impl

6. Publish tailcall after tailcall-impl is available on crates.io:

cargo publish -p tailcall

7. Tag the release from main:

git tag -a vX.Y.Z -m "Release vX.Y.Z"
git push origin vX.Y.Z

Contributing

Bug reports and pull requests are welcome on GitHub.

License

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

See LICENSE-APACHE, LICENSE-MIT, and COPYRIGHT for details.