rust_lisp/model/
list.rs

1use std::cell::RefCell;
2use std::fmt::Debug;
3use std::fmt::Display;
4use std::iter::FromIterator;
5use std::rc::Rc;
6
7use super::{RuntimeError, Value};
8
9/**
10 * A Lisp list, implemented as a linked-list
11 */
12#[derive(Debug, PartialEq, Eq, Clone)]
13pub struct List {
14    head: Option<Rc<RefCell<ConsCell>>>,
15}
16
17impl List {
18    pub const NIL: List = List { head: None };
19
20    pub fn car(&self) -> Result<Value, RuntimeError> {
21        self.head
22            .as_ref()
23            .map(|rc| rc.borrow().car.clone())
24            .ok_or_else(|| RuntimeError {
25                msg: String::from("Attempted to apply car on nil"),
26            })
27    }
28    #[must_use]
29    pub fn cdr(&self) -> List {
30        List {
31            head: self
32                .head
33                .as_ref()
34                .and_then(|rc| rc.borrow().cdr.as_ref().cloned()),
35        }
36    }
37
38    #[must_use]
39    pub fn cons(&self, val: Value) -> List {
40        List {
41            head: Some(Rc::new(RefCell::new(ConsCell {
42                car: val,
43                cdr: self.head.clone(),
44            }))),
45        }
46    }
47}
48
49impl<'a> List {
50    pub fn into_iter(list: &'a List) -> ConsIterator {
51        ConsIterator(list.head.clone())
52    }
53}
54
55/// A `ConsCell` is effectively a linked-list node, where the value in each node
56/// is a lisp `Value`. To be used as a true "list", the ConsCell must be wrapped
57/// in Value::List().
58#[derive(Debug, PartialEq, Eq)]
59struct ConsCell {
60    pub car: Value,
61    pub cdr: Option<Rc<RefCell<ConsCell>>>,
62}
63
64impl std::hash::Hash for ConsCell {
65    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
66        self.car.hash(state);
67        self.cdr.as_ref().map(|rc| rc.as_ptr()).hash(state);
68    }
69}
70
71impl Display for List {
72    fn fmt(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
73        if let Some(head) = &self.head {
74            write!(formatter, "({})", head.as_ref().borrow())
75        } else {
76            write!(formatter, "NIL")
77        }
78    }
79}
80
81impl Display for ConsCell {
82    fn fmt(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
83        match self.cdr.as_ref() {
84            Some(cdr) => write!(formatter, "{} {}", self.car, cdr.borrow()),
85            None => write!(formatter, "{}", self.car),
86        }
87    }
88}
89
90impl std::hash::Hash for List {
91    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
92        self.head.as_ref().map(|rc| rc.as_ptr()).hash(state);
93    }
94}
95
96impl<'a> IntoIterator for &'a List {
97    type Item = Value;
98    type IntoIter = ConsIterator;
99
100    fn into_iter(self) -> Self::IntoIter {
101        ConsIterator(self.head.clone())
102    }
103}
104
105#[derive(Clone)]
106pub struct ConsIterator(Option<Rc<RefCell<ConsCell>>>);
107
108impl Iterator for ConsIterator {
109    type Item = Value;
110
111    fn next(&mut self) -> Option<Self::Item> {
112        self.0.clone().map(|cons| {
113            let val = cons.borrow().car.clone();
114
115            self.0 = cons.borrow().cdr.clone();
116
117            val
118        })
119    }
120}
121
122impl ExactSizeIterator for ConsIterator {
123    fn len(&self) -> usize {
124        let mut length: usize = 0;
125
126        self.clone().for_each(|_| length += 1);
127
128        length
129    }
130}
131
132impl FromIterator<Value> for List {
133    fn from_iter<I: IntoIterator<Item = Value>>(iter: I) -> Self {
134        let mut new_list = List { head: None };
135        let mut tail: Option<Rc<RefCell<ConsCell>>> = None;
136
137        for val in iter {
138            // The cons cell for the current value
139            let new_cons = Rc::new(RefCell::new(ConsCell {
140                car: val,
141                cdr: None,
142            }));
143
144            // if this is the first cell, put it in the List
145            if new_list.head.is_none() {
146                new_list.head = Some(new_cons.clone());
147            // otherwise, put it in the current tail cell
148            } else if let Some(tail_cons) = tail {
149                tail_cons.as_ref().borrow_mut().cdr = Some(new_cons.clone());
150            }
151
152            // the current cell is the new tail
153            tail = Some(new_cons);
154        }
155
156        new_list
157    }
158}
159
160impl<'a> FromIterator<&'a Value> for List {
161    fn from_iter<I: IntoIterator<Item = &'a Value>>(iter: I) -> Self {
162        iter.into_iter().cloned().collect()
163    }
164}
rust_lisp/model/list.rs

rust_lisp/model/
list.rs
