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
67
68
69
70

//! This constructs a very long linked list, and recursively traverses it.  Note
//! that we need the custom `Drop` impl for the `List` type: without it, the
//! program will stack overflow when it recursively tries to deallocate the
//! list.

mod dizzy;

use vuot::{run, Stack, StacklessFn};

fn main() {
    let result = dizzy::block_on(async {
        let list = List::new(50_000_000);
        run(Sum(&list)).await
    });

    println!("{result}");
}

struct Sum<'list>(&'list List);
impl<'a> StacklessFn<'a, usize> for Sum<'_> {
    async fn call(self, stack: Stack<'a>) -> usize {
        sum_recursive(stack, self.0).await
    }
}

/// Depth-first traversal using the virtual call stack
async fn sum_recursive(stack: Stack<'_>, list: &List) -> usize {
    let mut sum = list.value;
    if let Some(next) = &list.next {
        sum = stack
            .run(sum_recursive(stack, next))
            .await
            .wrapping_add(sum);
    }
    sum
}

struct List {
    value: usize,
    next: Option<Box<List>>,
}

impl List {
    pub fn new(length: usize) -> Self {
        let mut list = Self {
            value: 0,
            next: None,
        };

        for value in 1..length {
            list = Self {
                value,
                next: Some(Box::new(list)),
            }
        }

        list
    }
}

/// This is necessary to prevent the default drop glue from overflowing the
/// stack.
impl Drop for List {
    fn drop(&mut self) {
        let mut next = self.next.take();
        while let Some(mut list) = next {
            next = list.next.take();
        }
    }
}