vuot 0.0.1

Run recursive async functions without overflowing the stack
Documentation 
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

use std::future::Future;

use crate::Stack;

/// A `StacklessFn<'stack, T>` is used to represent an asynchronous closure.
/// The "entry point" of a recursive function should implement this.  The
/// parameter `stack` of type [`Stack`] can be used to run deeply recursive
/// functions without blowing up the stack.
///
/// This trait is needed because the future returned by [`StacklessFn::call`] is
/// expected to capture the stack `Stack<'stack>`, for an arbitrary lifetime
/// `'stack` determined by the function [`run`].  This is currently not
/// something that can be expressed using closures, although if async closures
/// or lending functions are stabilized, those can be used instead.
///
/// # Examples
///
/// Reference local data in the stackless function:
///
/// ```
/// # pollster::block_on(async {
/// use std::future::Future;
/// use vuot::{run, Stack, StacklessFn};
///
/// /// Recursively sum up the elements of a slice
/// async fn sum(stack: Stack<'_>, values: &[i64]) -> i64 {
///     match values {
///         [] => 0,
///         [value, rest @ ..] => *value + stack.run(sum(stack, rest)).await,
///     }
/// }
///
/// struct Sum<'local>(&'local [i64]);
///
/// // Note that these impl's must always be generic over a lifetime 'a,
/// // otherwise the implementation will not be generic enough for `run`
/// impl<'a> StacklessFn<'a, i64> for Sum<'_> {
///     fn call(self, stack: Stack<'a>) -> impl Future<Output = i64> {
///         sum(stack, self.0)
///     }
/// }
///
/// let data = vec![3; 100];
/// let result = run(Sum(&data)).await;
/// assert_eq!(300, result);
/// # });
/// ```
pub trait StacklessFn<'a, T> {
    /// The entry point for the virtual call stack.
    fn call(self, stack: Stack<'a>) -> impl Future<Output = T>;
}

/// Implements [`StacklessFn`] for async functions.  Note that this `impl`
/// generally does not work very well for closures, due to lifetime capturing
/// issues.  In that case, the solution is to manually construct a type to hold
/// the captured variables.
#[allow(refining_impl_trait)]
impl<'a, F, Fut, T> StacklessFn<'a, T> for F
where
    F: FnOnce(Stack<'a>) -> Fut,
    Fut: Future<Output = T>,
{
    fn call(self, stack: Stack<'a>) -> Fut {
        self(stack)
    }
}