jaq_interpret/
rc_lazy_list.rs

1use alloc::boxed::Box;
2use alloc::rc::Rc;
3use once_cell::unsync::Lazy;
4
5#[derive(Clone)]
6pub struct List<'a, T>(Rc<Lazy<Node<'a, T>, Eval<'a, T>>>);
7struct Node<'a, T>(Option<(T, List<'a, T>)>);
8type Eval<'a, T> = Box<dyn FnOnce() -> Node<'a, T> + 'a>;
9
10impl<'a, T> Drop for List<'a, T> {
11    fn drop(&mut self) {
12        while let Some((_head, tail)) = Rc::get_mut(&mut self.0)
13            .and_then(Lazy::get_mut)
14            .and_then(|node| node.0.take())
15        {
16            *self = tail;
17        }
18    }
19}
20
21impl<'a, T> Node<'a, T> {
22    fn from_iter(mut iter: impl Iterator<Item = T> + 'a) -> Self {
23        Self(iter.next().map(|x| (x, List::from_iter(iter))))
24    }
25}
26
27impl<'a, T> List<'a, T> {
28    pub fn from_iter(iter: impl Iterator<Item = T> + 'a) -> Self {
29        Self(Rc::new(Lazy::new(Box::new(|| Node::from_iter(iter)))))
30    }
31}
32
33impl<'a, T: Clone + 'a> Iterator for List<'a, T> {
34    type Item = T;
35
36    fn next(&mut self) -> Option<T> {
37        match &Lazy::force(&self.0).0 {
38            None => None,
39            Some((x, xs)) => {
40                let x = x.clone();
41                *self = xs.clone();
42                Some(x)
43            }
44        }
45    }
46}
47
48#[test]
49fn drop() {
50    let list = List::from_iter(0..100_000);
51    // clone() ensures that we keep a copy of the whole list around
52    // sum() then evaluates the whole list
53    assert_eq!(list.clone().sum::<u64>(), 4999950000);
54    // at the end, a long, fully evaluated list is dropped,
55    // which would result in a stack overflow without the custom `Drop` impl
56    std::mem::drop(list);
57}
jaq_interpret/rc_lazy_list.rs

jaq_interpret/
rc_lazy_list.rs
