fibonacci.rs

#![feature(generators, generator_trait)]

use std::{
    cell::Cell,
    future::Future,
    ops::Generator,
    pin::Pin,
    rc::Rc,
    task::{Context, Poll, RawWaker, RawWakerVTable, Waker},
};

fn fibonacci_iterative_gen(n: i64) -> i64 {
    let mut stack = vec![];

    let frame = || {
        |n: i64| {
            if n <= 1 {
                n
            } else {
                let a = yield n - 2;
                let b = yield n - 1;

                a + b
            }
        }
    };

    stack.push(frame());

    let mut data = n;

    while let Some(fr) = stack.last_mut() {
        match Pin::new(fr).resume(data) {
            std::ops::GeneratorState::Yielded(rec) => {
                data = rec;
                stack.push(frame());
            }
            std::ops::GeneratorState::Complete(res) => {
                data = res;
                stack.pop();
            }
        }
    }

    data
}

fn fibonacci_iterative_async(n: i64) -> i64 {
    enum Recurse {
        Pending,
        Done,
    }
    impl Future for Recurse {
        type Output = ();

        fn poll(
            mut self: Pin<&mut Self>,
            _cx: &mut std::task::Context<'_>,
        ) -> std::task::Poll<Self::Output> {
            match *self {
                Recurse::Pending => {
                    *self = Recurse::Done;
                    Poll::Pending
                }
                Recurse::Done => Poll::Ready(()),
            }
        }
    }

    let data = Rc::new(Cell::new(0));

    let recurse_data = data.clone();
    let recurse = |n: i64| async move {
        recurse_data.set(n);
        Recurse::Pending.await;
        recurse_data.get()
    };

    macro_rules! recurse {
        ($expr:expr) => {
            recurse.clone()($expr).await
        };
    }

    let frame = |n: i64| async move {
        if n <= 1 {
            n
        } else {
            let a = recurse!(n - 2);
            let b = recurse!(n - 1);

            a + b
        }
    };

    let mut stack = vec![Box::pin(frame.clone()(n))];

    static VTABLE: RawWakerVTable = RawWakerVTable::new(
        |_| unimplemented!(),
        |_| unimplemented!(),
        |_| unimplemented!(),
        |_| unimplemented!(),
    );
    let raw_waker = RawWaker::new(std::ptr::null(), &VTABLE);
    let waker = unsafe { Waker::from_raw(raw_waker) };
    let mut cx = Context::from_waker(&waker);

    while let Some(top) = stack.last_mut() {
        match top.as_mut().poll(&mut cx) {
            Poll::Ready(n) => {
                data.set(n);
                stack.pop();
            }
            Poll::Pending => {
                stack.push(Box::pin(frame.clone()(data.get())));
            }
        }
    }

    data.get()
}

fn main() {
    println!("{}", fibonacci_iterative_gen(10));
    println!("{}", fibonacci_iterative_async(10));
}