rune/core/cons/
iter.rs

Help
1use super::super::object::{List, ListType, Object, ObjectType};
2use super::Cons;
3use crate::core::gc::Rto;
4use anyhow::{Error, Result};
5
6#[derive(Clone)]
7pub(crate) struct ConsIter<'ob> {
8    cons: Option<Result<&'ob Cons, ConsError>>,
9    fast: Option<&'ob Cons>,
10}
11
12/// An iterator over cons cells. This iterator will detect circular lists and
13/// non-nil list terminators.
14impl<'ob> ConsIter<'ob> {
15    fn new(cons: Option<&'ob Cons>) -> Self {
16        Self { cons: cons.map(Ok), fast: cons }
17    }
18
19    pub(crate) fn fallible(self) -> fallible_iterator::Convert<Self> {
20        fallible_iterator::convert(self)
21    }
22}
23
24impl<'ob> Iterator for ConsIter<'ob> {
25    type Item = Result<&'ob Cons, ConsError>;
26
27    fn next(&mut self) -> Option<Self::Item> {
28        let cons = match self.cons? {
29            Ok(c) => c,
30            Err(e) => return Some(Err(e)),
31        };
32        self.cons = match cons.cdr().untag() {
33            ObjectType::Cons(next) => Some(Ok(next)),
34            ObjectType::NIL => None,
35            _ => Some(Err(ConsError::NonNilCdr)),
36        };
37
38        // Floyds cycle detection algorithm
39        self.fast = advance(advance(self.fast));
40        if let (Some(Ok(slow)), Some(fast)) = (self.cons, self.fast) {
41            if std::ptr::eq(slow, fast) {
42                self.cons = Some(Err(ConsError::CircularList));
43            }
44        }
45        Some(Ok(cons))
46    }
47}
48
49fn advance(cons: Option<&Cons>) -> Option<&Cons> {
50    match cons?.cdr().untag() {
51        ObjectType::Cons(next) => Some(next),
52        _ => None,
53    }
54}
55
56/// An iterator over the elements (car's) of a list. This iterator will detect circular
57/// lists and non-nil list terminators.
58#[derive(Clone)]
59pub(crate) struct ElemIter<'ob>(ConsIter<'ob>);
60
61impl ElemIter<'_> {
62    pub(crate) fn len(&self) -> Result<usize, ConsError> {
63        use fallible_iterator::FallibleIterator;
64        self.clone().fallible().count()
65    }
66
67    /// Take the rest of the list as a cons.
68    pub(crate) fn rest(&self) -> Result<Option<&Cons>, ConsError> {
69        self.0.cons.transpose()
70    }
71
72    pub(crate) fn fallible(self) -> fallible_iterator::Convert<Self> {
73        fallible_iterator::convert(self)
74    }
75}
76
77impl<'ob> Iterator for ElemIter<'ob> {
78    type Item = Result<Object<'ob>, ConsError>;
79
80    fn next(&mut self) -> Option<Self::Item> {
81        self.0.next().map(|x| x.map(|x| x.car()))
82    }
83}
84
85#[derive(Copy, Clone, Debug)]
86pub(crate) enum ConsError {
87    NonNilCdr,
88    CircularList,
89}
90
91impl std::fmt::Display for ConsError {
92    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
93        match self {
94            ConsError::NonNilCdr => write!(f, "non-nil cdr at end of list"),
95            ConsError::CircularList => write!(f, "Circular list"),
96        }
97    }
98}
99
100impl std::error::Error for ConsError {}
101
102pub(crate) struct ElemStreamIter<'rt> {
103    elem: Option<&'rt mut Rto<Object<'static>>>,
104    cons: Option<Result<&'rt mut Rto<&'static Cons>, ConsError>>,
105}
106
107impl<'rt> ElemStreamIter<'rt> {
108    pub(crate) fn new(
109        elem: Option<&'rt mut Rto<Object<'static>>>,
110        cons: Option<&'rt mut Rto<&'static Cons>>,
111    ) -> Self {
112        Self { elem, cons: cons.map(Ok) }
113    }
114}
115
116impl fallible_streaming_iterator::FallibleStreamingIterator for ElemStreamIter<'_> {
117    type Item = Rto<Object<'static>>;
118    type Error = ConsError;
119
120    fn advance(&mut self) -> Result<(), ConsError> {
121        if let Some(cons) = &mut self.cons {
122            let cons = match cons {
123                Ok(x) => x,
124                Err(e) => return Err(*e),
125            };
126            let elem = self.elem.as_mut().expect("Element should never be None while Cons is Some");
127            let car = unsafe { cons.bind_unchecked().car() };
128            elem.set(car);
129            match unsafe { cons.bind_unchecked().cdr().untag() } {
130                ObjectType::Cons(next) => {
131                    // dissociate the borrow of cons from cell
132                    let x = unsafe { std::mem::transmute::<&Cons, &Cons>(next) };
133                    cons.set(x);
134                }
135                ObjectType::NIL => self.cons = None,
136                _ => self.cons = Some(Err(ConsError::NonNilCdr)),
137            }
138        } else {
139            self.elem = None;
140        }
141        Ok(())
142    }
143
144    fn get(&self) -> Option<&Self::Item> {
145        self.elem.as_deref()
146    }
147}
148
149impl ElemStreamIter<'_> {
150    pub(crate) fn is_empty(&self) -> bool {
151        self.cons.is_none()
152    }
153}
154
155impl Cons {
156    pub(crate) fn elements(&self) -> ElemIter {
157        ElemIter(self.conses())
158    }
159
160    pub(crate) fn conses(&self) -> ConsIter {
161        ConsIter::new(Some(self))
162    }
163}
164
165impl<'ob> IntoIterator for &'ob Cons {
166    type Item = <ElemIter<'ob> as Iterator>::Item;
167
168    type IntoIter = ElemIter<'ob>;
169
170    fn into_iter(self) -> Self::IntoIter {
171        self.elements()
172    }
173}
174
175impl<'ob> List<'ob> {
176    pub(crate) fn elements(self) -> ElemIter<'ob> {
177        ElemIter(self.conses())
178    }
179
180    pub(crate) fn conses(self) -> ConsIter<'ob> {
181        match self.untag() {
182            ListType::Nil => ConsIter::new(None),
183            ListType::Cons(cons) => ConsIter::new(Some(cons)),
184        }
185    }
186}
187
188impl<'ob> IntoIterator for List<'ob> {
189    type Item = <ElemIter<'ob> as Iterator>::Item;
190
191    type IntoIter = ElemIter<'ob>;
192
193    fn into_iter(self) -> Self::IntoIter {
194        self.elements()
195    }
196}
197
198impl<'ob> Object<'ob> {
199    pub(crate) fn as_list(self) -> Result<ElemIter<'ob>> {
200        let list: List = self.try_into()?;
201        Ok(list.elements())
202    }
203
204    pub(crate) fn into_list(self) -> Result<List<'ob>, crate::core::error::TypeError> {
205        self.try_into()
206    }
207}
208
209use std::result::Result as R;
210
211impl<'ob> TryFrom<Object<'ob>> for R<[Object<'ob>; 1], u16> {
212    type Error = Error;
213
214    fn try_from(value: Object<'ob>) -> R<Self, Self::Error> {
215        let mut value = value.as_list()?;
216        let x = match value.next() {
217            Some(x) => x?,
218            None => return Ok(Err(0)),
219        };
220        match value.next() {
221            Some(_) => Ok(Err(2)),
222            None => Ok(Ok([x])),
223        }
224    }
225}
226
227impl<'ob> TryFrom<Object<'ob>> for R<[Object<'ob>; 2], u16> {
228    type Error = Error;
229
230    fn try_from(value: Object<'ob>) -> R<Self, Self::Error> {
231        let mut value = value.as_list()?;
232        let x1 = match value.next() {
233            Some(x) => x?,
234            None => return Ok(Err(0)),
235        };
236        let x2 = match value.next() {
237            Some(x) => x?,
238            None => return Ok(Err(1)),
239        };
240        match value.next() {
241            Some(_) => Ok(Err(3)),
242            None => Ok(Ok([x1, x2])),
243        }
244    }
245}
246
247pub(crate) trait IntoArray<'ob, const N: usize> {
248    fn into_array(self) -> R<R<[Object<'ob>; N], u16>, Error>;
249}
250
251impl<'ob, const N: usize, T: TryInto<R<[Object<'ob>; N], u16>, Error = Error>> IntoArray<'ob, N>
252    for T
253{
254    fn into_array(self) -> R<R<[Object<'ob>; N], u16>, Error> {
255        self.try_into()
256    }
257}
258
259#[macro_export]
260macro_rules! rooted_iter {
261    ($ident:ident, $value:expr, $cx:ident) => {
262        // Create roots, but don't initialize them
263        let mut elem;
264        let mut cons;
265        let mut root_elem;
266        let mut root_cons;
267        // use match to ensure that $value is not evaled inside the unsafe block
268        let slot = match $value {
269            value => unsafe { $crate::core::gc::IntoRoot::into_root(value) },
270        };
271        let list: $crate::core::object::List = (*slot).try_into()?;
272        #[allow(unused_qualifications, unused_mut)]
273        let mut $ident = if let $crate::core::object::ListType::Cons(head) = list.untag() {
274            use $crate::core::{cons, gc, object};
275            // If the list is not empty, then initialize the roots and put them
276            // in the stack space reserved
277            unsafe {
278                elem = $crate::core::gc::Slot::new(object::NIL);
279                cons = $crate::core::gc::Slot::new(object::WithLifetime::with_lifetime(head));
280                root_elem = gc::__StackRoot::new(&mut elem, $cx.get_root_set());
281                root_cons = gc::__StackRoot::new(&mut cons, $cx.get_root_set());
282                cons::ElemStreamIter::new(Some(root_elem.as_mut()), Some(root_cons.as_mut()))
283            }
284        } else {
285            $crate::core::cons::ElemStreamIter::new(None, None)
286        };
287    };
288}
289
290#[cfg(test)]
291mod test {
292    use fallible_iterator::FallibleIterator;
293    use fallible_streaming_iterator::FallibleStreamingIterator;
294
295    use super::super::super::gc::{Context, RootSet};
296    use rune_core::macros::list;
297
298    use super::*;
299
300    #[test]
301    fn elem_iter() {
302        let roots = &RootSet::default();
303        let cx = &Context::new(roots);
304        let cons = list![1, 2, 3, 4; cx];
305        let iter = cons.as_list().unwrap();
306        let vec: Vec<_> = iter.fallible().collect().unwrap();
307        assert_eq!(vec, vec![1, 2, 3, 4]);
308    }
309
310    #[test]
311    fn circular_list() {
312        let roots = &RootSet::default();
313        let cx = &Context::new(roots);
314        let cons = list![1; cx];
315        cons.as_cons().set_cdr(cons).unwrap();
316        let mut iter = cons.as_list().unwrap();
317        assert!(iter.next().unwrap().is_ok());
318        assert!(iter.next().unwrap().is_err());
319
320        let cons = list![1, 2, 3; cx];
321        cons.as_cons().cdr().as_cons().cdr().as_cons().set_cdr(cons).unwrap();
322        let iter = cons.as_list().unwrap();
323        assert!(iter.fallible().nth(3).is_err());
324
325        let cons = list![1, 2, 3, 4; cx];
326        let middle = cons.as_cons().cdr().as_cons().cdr();
327        middle.as_cons().cdr().as_cons().set_cdr(middle).unwrap();
328        let iter = cons.as_list().unwrap();
329        assert!(iter.fallible().nth(3).is_err());
330    }
331
332    #[test]
333    fn cons_iter() {
334        let roots = &RootSet::default();
335        let cx = &Context::new(roots);
336        let cons = list![1, 2, 3, 4; cx];
337        let list: List = cons.try_into().unwrap();
338        let mut iter = list.conses();
339        for expect in [1, 2, 3, 4] {
340            let actual = iter.next().unwrap().unwrap().car();
341            assert_eq!(actual, expect);
342        }
343    }
344
345    #[test]
346    fn stream_iter() {
347        let func = || -> Result<()> {
348            let roots = &RootSet::default();
349            let cx = &Context::new(roots);
350            let cons = list![1, 2, 3, 4; cx];
351            rooted_iter!(iter, cons, cx);
352            for expect in 1..=4 {
353                let actual = iter.next().unwrap().unwrap().bind(cx);
354                assert_eq!(actual, expect);
355            }
356            assert!(iter.is_empty());
357            Ok(())
358        };
359        func().unwrap();
360    }
361}
rune/core/cons/iter.rs

rune/core/cons/
iter.rs
