cljrs_value/collections/
list.rs

1use std::sync::Arc;
2
3use crate::Value;
4
5/// An immutable singly-linked list.  Structural sharing via `Arc`-backed tails.
6///
7/// Clojure's `PersistentList` is the primary `seq` type; it supports O(1) `cons`,
8/// `first`, and `rest`.  `count` is cached on each node so it is also O(1).
9#[derive(Debug, Clone)]
10pub enum PersistentList {
11    Empty,
12    Cons {
13        head: Value,
14        tail: Arc<PersistentList>,
15        count: usize,
16    },
17}
18
19impl PersistentList {
20    /// The canonical empty list.
21    pub fn empty() -> Self {
22        PersistentList::Empty
23    }
24
25    /// Prepend `head` to `tail`.  O(1).
26    pub fn cons(head: Value, tail: Arc<PersistentList>) -> Self {
27        let count = tail.count() + 1;
28        PersistentList::Cons { head, tail, count }
29    }
30
31    /// Number of elements.  O(1).
32    pub fn count(&self) -> usize {
33        match self {
34            PersistentList::Empty => 0,
35            PersistentList::Cons { count, .. } => *count,
36        }
37    }
38
39    pub fn is_empty(&self) -> bool {
40        matches!(self, PersistentList::Empty)
41    }
42
43    /// First element, or `None` if empty.
44    pub fn first(&self) -> Option<&Value> {
45        match self {
46            PersistentList::Empty => None,
47            PersistentList::Cons { head, .. } => Some(head),
48        }
49    }
50
51    /// The rest of the list after the first element.  Returns an empty list
52    /// if called on an empty or single-element list.
53    pub fn rest(&self) -> Arc<PersistentList> {
54        match self {
55            PersistentList::Empty => Arc::new(PersistentList::Empty),
56            PersistentList::Cons { tail, .. } => Arc::clone(tail),
57        }
58    }
59
60    /// Iterate over elements from head to tail.
61    pub fn iter(&self) -> ListIter<'_> {
62        ListIter { current: self }
63    }
64}
65
66impl cljrs_gc::Trace for PersistentList {
67    fn trace(&self, visitor: &mut cljrs_gc::MarkVisitor) {
68        match self {
69            PersistentList::Empty => {}
70            PersistentList::Cons { head, tail, .. } => {
71                head.trace(visitor);
72                // tail is Arc<PersistentList> — not a GcPtr, but we must trace
73                // through it to find any embedded GcPtrs.
74                tail.trace(visitor);
75            }
76        }
77    }
78}
79
80impl std::iter::FromIterator<Value> for PersistentList {
81    fn from_iter<I: IntoIterator<Item = Value>>(iter: I) -> Self {
82        let items: Vec<Value> = iter.into_iter().collect();
83        let mut list = PersistentList::Empty;
84        for item in items.into_iter().rev() {
85            list = PersistentList::cons(item, Arc::new(list));
86        }
87        list
88    }
89}
90
91/// Iterator over `PersistentList`.
92pub struct ListIter<'a> {
93    current: &'a PersistentList,
94}
95
96impl<'a> Iterator for ListIter<'a> {
97    type Item = &'a Value;
98
99    fn next(&mut self) -> Option<Self::Item> {
100        match self.current {
101            PersistentList::Empty => None,
102            PersistentList::Cons { head, tail, .. } => {
103                self.current = tail;
104                Some(head)
105            }
106        }
107    }
108}
109
110impl PartialEq for PersistentList {
111    fn eq(&self, other: &Self) -> bool {
112        if self.count() != other.count() {
113            return false;
114        }
115        self.iter().zip(other.iter()).all(|(a, b)| a == b)
116    }
117}
118
119#[cfg(test)]
120mod tests {
121    use super::*;
122    use crate::Value;
123
124    fn int(n: i64) -> Value {
125        Value::Long(n)
126    }
127
128    #[test]
129    fn test_empty() {
130        let l = PersistentList::empty();
131        assert!(l.is_empty());
132        assert_eq!(l.count(), 0);
133        assert!(l.first().is_none());
134    }
135
136    #[test]
137    fn test_cons_and_first() {
138        let l = PersistentList::cons(int(1), Arc::new(PersistentList::empty()));
139        assert_eq!(l.count(), 1);
140        assert_eq!(l.first(), Some(&int(1)));
141    }
142
143    #[test]
144    fn test_from_iter() {
145        let l = PersistentList::from_iter([int(1), int(2), int(3)]);
146        assert_eq!(l.count(), 3);
147        let items: Vec<_> = l.iter().cloned().collect();
148        assert_eq!(items, vec![int(1), int(2), int(3)]);
149    }
150
151    #[test]
152    fn test_rest() {
153        let l = PersistentList::from_iter([int(1), int(2)]);
154        let rest = l.rest();
155        assert_eq!(rest.count(), 1);
156        assert_eq!(rest.first(), Some(&int(2)));
157    }
158
159    #[test]
160    fn test_equality() {
161        let a = PersistentList::from_iter([int(1), int(2)]);
162        let b = PersistentList::from_iter([int(1), int(2)]);
163        let c = PersistentList::from_iter([int(1), int(3)]);
164        assert_eq!(a, b);
165        assert_ne!(a, c);
166    }
167
168    #[test]
169    fn test_structural_sharing() {
170        let tail = Arc::new(PersistentList::from_iter([int(2), int(3)]));
171        let a = PersistentList::cons(int(1), Arc::clone(&tail));
172        let b = PersistentList::cons(int(10), Arc::clone(&tail));
173        // Both lists share the same tail allocation.
174        assert!(Arc::ptr_eq(&a.rest(), &b.rest()));
175    }
176}
cljrs_value/collections/list.rs

cljrs_value/collections/
list.rs
