rdf_parsers/
list.rs

1use std::rc::Rc;
2
3#[derive(Clone, Default)]
4pub enum Inner<T> {
5    #[default]
6    Nil,
7    Cons(T, List<T>, usize),
8}
9
10/// Iteratively drop a `List<T>` to avoid stack overflow on long lists.
11///
12/// The default recursive drop of `Rc<Inner<T>>` can overflow the stack when
13/// the list has thousands of nodes (e.g., A* parse results for large files).
14/// This function walks the list iteratively, unlinking each node before it is
15/// freed so that no stack frame chains are created.
16pub fn drop_list<T>(list: List<T>) {
17    let mut current = list;
18    loop {
19        // If we're the sole owner, move the inner value out so we can
20        // mutate it before it is freed.
21        match Rc::try_unwrap(current) {
22            Err(_) => break, // Other Rc clones exist; let them handle drop.
23            Ok(inner) => {
24                match inner {
25                    Inner::Nil => break,
26                    Inner::Cons(_item, tail, _) => {
27                        // Continue with the tail.  When this loop iteration
28                        // ends, `_item` is dropped (non-recursive because it's
29                        // a plain `T`, not a `List`), and the old `inner`
30                        // (which now owns only `_item`) is freed — with its
31                        // `tail` field already moved out, so no chain.
32                        current = tail;
33                    }
34                }
35            }
36        }
37    }
38}
39impl<T: PartialEq> PartialEq for Inner<T> {
40    fn eq(&self, other: &Self) -> bool {
41        match (self, other) {
42            (Self::Cons(t1, c1, l1), Self::Cons(t2, c2, l2)) => {
43                if l1 != l2 || t1 != t2 {
44                    return false;
45                }
46                if Rc::ptr_eq(c1, c2) {
47                    return true;
48                }
49                c1 == c2
50            }
51            (Inner::Nil, Inner::Nil) => true,
52            _ => false,
53        }
54    }
55}
56impl<T: Eq> Eq for Inner<T> {}
57impl<T: std::fmt::Debug> std::fmt::Debug for Inner<T> {
58    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
59        match self {
60            Self::Nil => write!(f, "[ ]"),
61            Self::Cons(item, cons, _) => {
62                write!(f, "[ {:?}", item)?;
63                for x in cons.iter() {
64                    write!(f, ", {:?}", x)?;
65                }
66                write!(f, " ]")?;
67                Ok(())
68            }
69        }
70    }
71}
72
73pub type List<T> = Rc<Inner<T>>;
74
75impl<T> Inner<T> {
76    pub fn new() -> Rc<Self> {
77        Rc::new(Inner::Nil)
78    }
79
80    pub fn len(&self) -> usize {
81        match self {
82            Inner::Nil => 0,
83            Inner::Cons(_, _, x) => *x,
84        }
85    }
86
87    pub fn prepend(self: &List<T>, value: T) -> List<T> {
88        let at = match self.as_ref() {
89            Inner::Nil => 1,
90            Inner::Cons(_, _, at) => at + 1,
91        };
92        Rc::new(Inner::Cons(value, self.clone(), at))
93    }
94
95    pub fn head(&self) -> Option<&T> {
96        match self {
97            Inner::Nil => None,
98            Inner::Cons(h, _, _) => Some(h),
99        }
100    }
101
102    pub fn tail(&self) -> Option<&List<T>> {
103        match &self {
104            Inner::Nil => None,
105            Inner::Cons(_, t, _) => Some(t),
106        }
107    }
108    pub fn slice(&self) -> Option<(&T, &List<T>)> {
109        match &self {
110            Inner::Nil => None,
111            Inner::Cons(r, t, _) => Some((r, t)),
112        }
113    }
114
115    pub fn same(self: &List<T>, other: &List<T>) -> bool {
116        Rc::ptr_eq(self, other)
117    }
118
119    pub fn iter<'a>(self: &'a List<T>) -> impl Iterator<Item = &'a T> {
120        let mut list = self;
121        std::iter::from_fn(move || match list.as_ref() {
122            Inner::Nil => None,
123            Inner::Cons(i, r, _) => {
124                list = r;
125                Some(i)
126            }
127        })
128    }
129}
rdf_parsers/list.rs

rdf_parsers/
list.rs
