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    #[cfg(feature = "no-gc")]
68    fn immutable_children(&self) -> bool {
69        true
70    }
71    fn trace(&self, visitor: &mut cljrs_gc::MarkVisitor) {
72        match self {
73            PersistentList::Empty => {}
74            PersistentList::Cons { head, tail, .. } => {
75                head.trace(visitor);
76                // tail is Arc<PersistentList> — not a GcPtr, but we must trace
77                // through it to find any embedded GcPtrs.
78                tail.trace(visitor);
79            }
80        }
81    }
82}
83
84impl std::iter::FromIterator<Value> for PersistentList {
85    fn from_iter<I: IntoIterator<Item = Value>>(iter: I) -> Self {
86        let items: Vec<Value> = iter.into_iter().collect();
87        let mut list = PersistentList::Empty;
88        for item in items.into_iter().rev() {
89            list = PersistentList::cons(item, Arc::new(list));
90        }
91        list
92    }
93}
94
95/// Iterator over `PersistentList`.
96pub struct ListIter<'a> {
97    current: &'a PersistentList,
98}
99
100impl<'a> Iterator for ListIter<'a> {
101    type Item = &'a Value;
102
103    fn next(&mut self) -> Option<Self::Item> {
104        match self.current {
105            PersistentList::Empty => None,
106            PersistentList::Cons { head, tail, .. } => {
107                self.current = tail;
108                Some(head)
109            }
110        }
111    }
112}
113
114impl PartialEq for PersistentList {
115    fn eq(&self, other: &Self) -> bool {
116        if self.count() != other.count() {
117            return false;
118        }
119        self.iter().zip(other.iter()).all(|(a, b)| a == b)
120    }
121}
122
123#[cfg(test)]
124mod tests {
125    use super::*;
126    use crate::Value;
127
128    fn int(n: i64) -> Value {
129        Value::Long(n)
130    }
131
132    #[test]
133    fn test_empty() {
134        let l = PersistentList::empty();
135        assert!(l.is_empty());
136        assert_eq!(l.count(), 0);
137        assert!(l.first().is_none());
138    }
139
140    #[test]
141    fn test_cons_and_first() {
142        let l = PersistentList::cons(int(1), Arc::new(PersistentList::empty()));
143        assert_eq!(l.count(), 1);
144        assert_eq!(l.first(), Some(&int(1)));
145    }
146
147    #[test]
148    fn test_from_iter() {
149        let l = PersistentList::from_iter([int(1), int(2), int(3)]);
150        assert_eq!(l.count(), 3);
151        let items: Vec<_> = l.iter().cloned().collect();
152        assert_eq!(items, vec![int(1), int(2), int(3)]);
153    }
154
155    #[test]
156    fn test_rest() {
157        let l = PersistentList::from_iter([int(1), int(2)]);
158        let rest = l.rest();
159        assert_eq!(rest.count(), 1);
160        assert_eq!(rest.first(), Some(&int(2)));
161    }
162
163    #[test]
164    fn test_equality() {
165        let a = PersistentList::from_iter([int(1), int(2)]);
166        let b = PersistentList::from_iter([int(1), int(2)]);
167        let c = PersistentList::from_iter([int(1), int(3)]);
168        assert_eq!(a, b);
169        assert_ne!(a, c);
170    }
171
172    #[test]
173    fn test_structural_sharing() {
174        let tail = Arc::new(PersistentList::from_iter([int(2), int(3)]));
175        let a = PersistentList::cons(int(1), Arc::clone(&tail));
176        let b = PersistentList::cons(int(10), Arc::clone(&tail));
177        // Both lists share the same tail allocation.
178        assert!(Arc::ptr_eq(&a.rest(), &b.rest()));
179    }
180}
cljrs_value/collections/list.rs

cljrs_value/collections/
list.rs
