//! 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();
        }
    }
}