1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

//! This module provides a simple, zero-cost [trampoline]. It is designed to be used by the
//! [`tailcall`] macro, but it can also be used manually.
//!
//! # Usage
//!
//! Express the contents of a recusive function as a step function (`Fn(Input) -> Next<Input, Output>`).
//! To guarantee that only a single stack frame will be used at all levels of optimization, annotate it
//! with `#[inline(always)]` attribute. This step function and an initial input can then be passed to
//! [`run`] which will recusively call it until it resolves to an output.
//!
//! ```
//! // fn gcd(a: u64, b: u64) -> u64 {
//! //     if b == 0 {
//! //         a
//! //     } else {
//! //         gcd(b, a % b)
//! //     }
//! // }
//!
//! #[inline(always)]
//! fn gcd_step((a, b): (u64, u64)) -> tailcall::trampoline::Next<(u64, u64), u64> {
//!     if b == 0 {
//!         tailcall::trampoline::Finish(a)
//!     } else {
//!         tailcall::trampoline::Recurse((b, a % b))
//!     }
//! }
//!
//! fn gcd(a: u64, b: u64) -> u64 {
//!
//!     tailcall::trampoline::run(gcd_step, (a, b))
//! }
//! ```
//!
//! [trampoline]: https://en.wikipedia.org/wiki/Tail_call#Through_trampolining
//! [`tailcall`]: ../tailcall_impl/attr.tailcall.html
//! [`run`]: fn.run.html
//!

/// This is the output of the step function. It indicates to [run] what should happen next.
///
/// [run]: fn.run.html
#[derive(Debug)]
pub enum Next<Input, Output> {
    /// This variant indicates that the step function should be run again with the provided input.
    Recurse(Input),

    /// This variant indicates that there are no more steps to be taken and the provided output should be returned.
    Finish(Output),
}

pub use Next::*;

/// Runs a step function aginast a particular input until it resolves to an output.
#[inline(always)]
pub fn run<StepFn, Input, Output>(step: StepFn, mut input: Input) -> Output
where
    StepFn: Fn(Input) -> Next<Input, Output>,
{
    loop {
        match step(input) {
            Recurse(new_input) => {
                input = new_input;
                continue;
            }
            Finish(output) => {
                break output;
            }
        }
    }
}