sexprs_data_structures/
cell.rs

1#![allow(unused)]
2use std::borrow::Cow;
3use std::fmt::{Debug, Display, Formatter};
4use std::hash::{Hash, Hasher};
5use std::iter::{Extend, IntoIterator, Iterator};
6use std::ops::Deref;
7
8use unique_pointer::{RefCounter, UniquePointer};
9
10use crate::{AsSymbol, AsValue, Quotable, Symbol, Value};
11pub trait ListIterator<'c, T: AsCell<'c>>: IntoIterator<Item = T> + Debug + Quotable {
12    fn iter_cells(&self) -> Cell<'c>;
13}
14
15pub trait AsCell<'c>: Quotable {
16    //: ListValue {
17    fn as_cell(&self) -> Cell<'c>;
18}
19
20#[derive(Eq, PartialOrd, Ord)]
21pub struct Cell<'c> {
22    pub(crate) head: UniquePointer<Value<'c>>,
23    pub(crate) tail: UniquePointer<Cell<'c>>,
24    pub(crate) refs: RefCounter,
25    pub(crate) quoted: bool,
26}
27
28impl<'c> Cell<'c> {
29    pub fn nil() -> Cell<'c> {
30        Cell::quoted(Option::<Value<'c>>::None, false)
31    }
32
33    pub fn quoted<T: AsValue<'c>>(item: Option<T>, quoted: bool) -> Cell<'c> {
34        let mut cell = Cell {
35            head: UniquePointer::<Value<'c>>::null(),
36            tail: UniquePointer::<Cell<'c>>::null(),
37            refs: RefCounter::new(),
38            quoted,
39        };
40        cell.incr_ref();
41        if let Some(item) = item {
42            cell.write(item.as_value());
43        }
44        cell
45    }
46
47    pub fn is_nil(&self) -> bool {
48        self.head.is_null() && self.tail.is_null()
49    }
50
51    pub fn unwrap_value(&self) -> Value<'c> {
52        if self.tail.is_null() {
53            match self.head() {
54                Some(head) => head.unwrap_list(),
55                None => Value::Nil,
56            }
57        } else if self.quoted {
58            Value::QuotedList(self.as_cell())
59        } else {
60            Value::List(self.as_cell())
61        }
62    }
63
64    pub fn new<T: AsValue<'c>>(item: T) -> Cell<'c> {
65        let value = item.as_value();
66        let is_quoted = value.is_quoted();
67        Cell::quoted(Some(value), is_quoted)
68        // let mut cell = Cell::nil();
69        // cell.write(item.as_value());
70        // cell
71    }
72
73    pub fn head(&self) -> Option<Value<'c>> {
74        self.head.try_read()
75    }
76
77    pub fn push_value(&mut self, value: Value<'c>) {
78        let is_quoted = value.is_quoted();
79        let mut cell = Cell::quoted(Some(value), is_quoted);
80        let cell = if is_quoted { cell.quote() } else { cell };
81        self.add(&cell);
82    }
83
84    pub fn add(&mut self, new: &Cell<'c>) {
85        if new.is_nil() {
86            return;
87        }
88        let mut new = new.clone();
89        self.incr_ref();
90
91        if self.head.is_null() {
92            // when self.head *IS* null:
93            // and `new.head` *IS NOT* null
94            if !new.head.is_null() {
95                // swap heads
96                self.swap_head(&mut new);
97            }
98
99            // and new.tail *IS NOT* null
100            if new.tail.is_not_null() {
101                let tail = new.tail.inner_mut();
102                // if new.tail.head *IS NOT* null
103                if new.head.is_not_null() {
104                    // write new.tail.head in tail.head
105                    tail.head.write_ref(new.head.inner_ref());
106
107                    // TODO:
108                    // try new.swap_head(tail);
109                }
110            }
111            self.tail = UniquePointer::from(new);
112        } else {
113            // when self.head *IS NOT* null
114            if self.tail.is_null() {
115                // when self.tail *IS* null
116                self.tail = UniquePointer::from(new);
117            } else {
118                //  self.tail *IS NOT* null
119                self.tail.inner_mut().add(&new);
120            }
121        }
122    }
123
124    pub fn pop(&mut self) -> bool {
125        if !self.tail.is_null() {
126            self.tail.drop_in_place();
127            self.tail = UniquePointer::null();
128            true
129        } else if !self.head.is_null() {
130            self.head.drop_in_place();
131            self.head = UniquePointer::null();
132            true
133        } else {
134            false
135        }
136    }
137
138    pub fn is_empty(&self) -> bool {
139        self.len() == 0
140    }
141
142    /// `O(n)`
143    pub fn len(&self) -> usize {
144        let mut len = 0;
145        if !self.head.is_null() {
146            len += 1
147        }
148        if let Some(tail) = self.tail() {
149            len += tail.len();
150        }
151        len
152    }
153
154    pub fn tail(&self) -> Option<&'c Cell<'c>> {
155        self.tail.as_ref()
156    }
157
158    pub fn values(&self) -> Vec<Value<'c>> {
159        let mut values = Vec::<Value>::new();
160        if let Some(head) = self.head() {
161            // dbg!(&head);
162            values.push(head.clone());
163        }
164        if let Some(tail) = self.tail() {
165            // dbg!(&tail);
166            values.extend(tail.values());
167        }
168        values
169    }
170
171    pub(crate) fn write(&mut self, value: Value<'c>) {
172        self.head.write(value);
173        self.incr_ref();
174    }
175
176    pub(crate) fn swap_head(&mut self, other: &mut Self) {
177        // self.incr_ref();
178        // other.incr_ref();
179        self.head = unsafe {
180            let head = other.head.propagate();
181            other.head = self.head.propagate();
182            head
183        };
184    }
185
186    pub(crate) fn swap_tail(&mut self, other: &mut Self) {
187        self.tail = unsafe {
188            let tail = other.tail.propagate();
189            other.tail = self.tail.propagate();
190            tail
191        };
192    }
193
194    pub(crate) fn swap_refs(&mut self, other: &mut Self) {
195        self.refs = {
196            let refs = other.refs.clone();
197            other.refs = self.refs.clone();
198            refs
199        };
200    }
201
202    pub fn to_vec(&self) -> Vec<Value<'c>> {
203        Vec::<Value<'c>>::from_iter(self.clone().into_iter())
204    }
205
206    fn incr_ref(&mut self) {
207        self.refs.incr();
208        if !self.tail.is_null() {
209            if let Some(tail) = self.tail.as_mut() {
210                tail.incr_ref();
211            }
212        }
213    }
214
215    fn decr_ref(&mut self) {
216        self.refs.decr();
217        if !self.tail.is_null() {
218            if let Some(tail) = self.tail.as_mut() {
219                tail.decr_ref();
220            }
221        }
222    }
223
224    fn dealloc(&mut self) {
225        if self.refs > 0 {
226            self.decr_ref();
227        } else {
228            self.head.drop_in_place();
229            self.tail.drop_in_place();
230        }
231    }
232
233    fn repr(&self) -> String {
234        [
235            "Cell".to_string(),
236            format!(
237                "[{}]",
238                if self.is_nil() {
239                    format!("null")
240                } else {
241                    [
242                        if self.head.is_null() {
243                            format!("head: {}", "null")
244                        } else {
245                            format!("head={:#?}", self.head().unwrap_or_default())
246                        },
247                        if self.tail.is_null() {
248                            format!("tail: {}", "null")
249                        } else {
250                            format!(
251                                "tail={:#?}",
252                                self.tail().map(Clone::clone).unwrap_or_default()
253                            )
254                        },
255                    ]
256                    .join(" | ")
257                }
258            ),
259        ]
260        .join("")
261    }
262}
263impl<'c> Quotable for Cell<'c> {
264    fn is_quoted(&self) -> bool {
265        self.quoted
266    }
267
268    fn set_quoted(&mut self, quoted: bool) {
269        self.quoted = quoted;
270    }
271}
272
273impl<'c, T: Quotable + AsCell<'c>, const N: usize> AsCell<'c> for [T; N] {
274    fn as_cell(&self) -> Cell<'c> {
275        let mut cell = Cell::nil();
276        for item in self {
277            cell.add(&item.as_cell());
278        }
279        cell
280    }
281}
282
283// impl<'c> AsList<'c> for Cell<'c> {
284//     fn as_cell(&self) -> List<'c> {
285//         if self.is_nil() {
286//             List::Empty(self.is_quoted())
287//         } else {
288//             List::Linked(self.clone(), self.is_quoted())
289//         }
290//     }
291// }
292
293impl<'c, T: AsCell<'c>, const N: usize> ListIterator<'c, T> for [T; N] {
294    fn iter_cells(&self) -> Cell<'c> {
295        let mut cell = Cell::nil();
296        for item in self {
297            cell.add(&item.as_cell());
298        }
299        cell
300    }
301}
302impl<'c> ListIterator<'c, Value<'c>> for Cell<'c> {
303    fn iter_cells(&self) -> Cell<'c> {
304        self.clone()
305    }
306}
307impl<'c> AsCell<'c> for Cell<'c> {
308    fn as_cell(&self) -> Cell<'c> {
309        self.clone()
310    }
311}
312impl<'c> AsCell<'c> for &Cell<'c> {
313    fn as_cell(&self) -> Cell<'c> {
314        UniquePointer::read_only(*self).read()
315    }
316}
317
318impl<'c> AsCell<'c> for &'c str {
319    fn as_cell(&self) -> Cell<'c> {
320        Cell::new(Value::symbol(self.to_string()))
321    }
322}
323impl<'c> AsCell<'c> for String {
324    fn as_cell(&self) -> Cell<'c> {
325        Cell::new(Value::string(self))
326    }
327}
328
329impl<'c> From<Value<'c>> for Cell<'c> {
330    fn from(value: Value<'c>) -> Cell<'c> {
331        Cell::quoted(Some(value.clone()), value.is_quoted())
332    }
333}
334impl<'c> From<&Value<'c>> for Cell<'c> {
335    fn from(value: &Value<'c>) -> Cell<'c> {
336        Cell::quoted(Some(value.clone()), value.is_quoted())
337    }
338}
339
340impl<'c> From<u8> for Cell<'c> {
341    fn from(value: u8) -> Cell<'c> {
342        Cell::new(Value::Byte(value))
343    }
344}
345impl<'c> From<u32> for Cell<'c> {
346    fn from(value: u32) -> Cell<'c> {
347        if value <= u8::MAX.into() {
348            Cell::new(Value::Byte(value as u8))
349        } else {
350            Cell::new(Value::UnsignedInteger(value.into()))
351        }
352    }
353}
354impl<'c> From<f64> for Cell<'c> {
355    fn from(value: f64) -> Cell<'c> {
356        Cell::new(Value::float(value))
357    }
358}
359impl<'c> From<u64> for Cell<'c> {
360    fn from(value: u64) -> Cell<'c> {
361        if value <= u32::MAX.into() {
362            Cell::from(value as u32)
363        } else {
364            Cell::new(Value::UnsignedInteger(value.into()))
365        }
366    }
367}
368impl<'c> From<i32> for Cell<'c> {
369    fn from(value: i32) -> Cell<'c> {
370        if let Ok(value) = TryInto::<u32>::try_into(value) {
371            Cell::new(Value::unsigned_integer(value))
372        } else {
373            Cell::new(Value::integer(value))
374        }
375    }
376}
377impl<'c> From<i64> for Cell<'c> {
378    fn from(value: i64) -> Cell<'c> {
379        Cell::new(Value::from(value))
380    }
381}
382impl<'c> From<&str> for Cell<'c> {
383    fn from(value: &str) -> Cell<'c> {
384        Cell::new(Value::symbol(value))
385    }
386}
387impl<'c> From<String> for Cell<'c> {
388    fn from(value: String) -> Cell<'c> {
389        Cell::new(Value::string(value))
390    }
391}
392impl<'c> From<Cow<'c, str>> for Cell<'c> {
393    fn from(value: Cow<'c, str>) -> Cell<'c> {
394        Cell::new(Value::string(&value))
395    }
396}
397
398impl<'c> PartialEq<Cell<'c>> for Cell<'c> {
399    fn eq(&self, other: &Cell<'c>) -> bool {
400        if self.is_nil() && other.is_nil() {
401            return true;
402        }
403        let slen = self.len();
404        let olen = other.len();
405        if slen != olen {
406            return false;
407        }
408
409        let max_len = std::cmp::max(slen, olen);
410        let mut current = 0;
411
412        let mut iter = self.clone().into_iter().zip(other.clone().into_iter());
413        loop {
414            current += 1;
415            match iter.next() {
416                Some((lhs, rhs)) => {
417                    if lhs != rhs {
418                        return false;
419                    }
420                }
421                None => return current < max_len,
422            }
423            if current == max_len {
424                break true;
425            }
426        }
427    }
428}
429
430impl<'c> Default for Cell<'c> {
431    fn default() -> Cell<'c> {
432        Cell::nil()
433    }
434}
435
436/// [`Clone`] implementation for [`Cell`] clones the internal
437/// pointers.
438impl<'c> Clone for Cell<'c> {
439    fn clone(&self) -> Cell<'c> {
440        let mut cell = Cell::nil();
441        cell.refs = self.refs.clone();
442        cell.incr_ref();
443        if let Some(head) = self.head() {
444            cell.head.write(head)
445        }
446        if let Some(tail) = self.tail().map(Clone::clone) {
447            cell.tail.write(tail)
448        }
449        cell
450    }
451}
452impl<'c> Hash for Cell<'c> {
453    fn hash<H: Hasher>(&self, state: &mut H) {
454        self.head().hash(state);
455        self.tail().hash(state);
456        self.refs.hash(state);
457        self.quoted.hash(state);
458    }
459}
460impl<'c> Drop for Cell<'c> {
461    fn drop(&mut self) {
462        self.dealloc();
463    }
464}
465
466// impl std::fmt::Debug for Cell<'_> {
467//     fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
468//         if self.is_nil() {
469//             return write!(f, "nil");
470//         }
471//         write!(
472//             f,
473//             "Cell[{}]",
474//             if self.is_nil() {
475//                 "".to_string()
476//             } else {
477//                 let mut parts = Vec::<String>::new();
478//                 if self.head.is_not_null() {
479//                     parts.push(
480//                         self.head()
481//                             .map(|value| format!("{:#?}", value))
482//                             .unwrap_or_default(),
483//                     )
484//                 }
485//
486//                 if self.tail.is_not_null() {
487//                     if let Some(tail) = self.tail() {
488//                         parts.push(format!("{:#?}", tail));
489//                     }
490//                 }
491//                 parts.join(" . ").trim().to_string()
492//             }
493//         )
494//     }
495// }
496
497impl Debug for Cell<'_> {
498    fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
499        write!(f, "{}", self)
500    }
501}
502
503impl std::fmt::Display for Cell<'_> {
504    fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
505        write!(
506            f,
507            "{}",
508            if self.is_nil() {
509                "".to_string()
510            } else {
511                let mut parts = Vec::<String>::new();
512                if self.head.is_not_null() {
513                    parts.push(
514                        self.head()
515                            .map(|value| value.to_string())
516                            .unwrap_or_default(),
517                    )
518                }
519
520                if self.tail.is_not_null() {
521                    if let Some(tail) = self.tail() {
522                        parts.push(tail.to_string());
523                    }
524                }
525                parts.join(" ").trim().to_string()
526            }
527        )
528    }
529}
530
531impl<'c> AsValue<'c> for Cell<'c> {
532    fn as_value(&self) -> Value<'c> {
533        if self.tail.is_null() {
534            match self.head() {
535                Some(head) => {
536                    let is_quoted = head.is_quoted();
537                    let value = head.unwrap_list();
538                    if is_quoted {
539                        value.quote()
540                    } else {
541                        value
542                    }
543                }
544                None => Value::Nil,
545            }
546        } else if self.quoted {
547            Value::QuotedList(self.clone())
548        } else {
549            Value::List(self.clone())
550        }
551    }
552}
553
554pub struct CellIterator<'c> {
555    cell: UniquePointer<Cell<'c>>,
556}
557
558impl<'c> CellIterator<'c> {
559    pub fn new(cell: Cell<'c>) -> CellIterator<'c> {
560        CellIterator {
561            cell: UniquePointer::from_ref(&cell),
562        }
563    }
564
565    pub fn item(&self) -> Option<&Cell<'c>> {
566        self.cell.as_ref()
567    }
568
569    pub fn tail(&self) -> Option<&Cell<'c>> {
570        if let Some(cell) = self.cell.as_ref() {
571            cell.tail()
572        } else {
573            None
574        }
575    }
576}
577impl<'c> Iterator for CellIterator<'c> {
578    type Item = Value<'c>;
579
580    fn next(&mut self) -> Option<Self::Item> {
581        if self.cell.is_not_null() {
582            let value = self.cell.inner_ref().head();
583            let next_tail = self.cell.inner_ref().tail.clone();
584            self.cell = next_tail;
585            value
586        } else {
587            None
588        }
589    }
590}
591
592impl<'c> IntoIterator for Cell<'c> {
593    type IntoIter = CellIterator<'c>;
594    type Item = Value<'c>;
595
596    fn into_iter(self) -> Self::IntoIter {
597        CellIterator::new(self)
598    }
599}
600
601impl<'c> FromIterator<Value<'c>> for Cell<'c> {
602    fn from_iter<I: IntoIterator<Item = Value<'c>>>(iter: I) -> Cell<'c> {
603        let mut cell = Cell::nil();
604        for value in iter {
605            cell.push_value(value);
606        }
607        cell
608    }
609}
610// impl<'c> Extend<Value<'c>> for Value<'c> {
611//     fn extend<T: IntoIterator<Item = Value<'c>>>(&mut self, iter: T) {
612//         if let Value::List(ref mut cell) = self {
613//             for value in iter {
614//                 cell.push_value(value);
615//             }
616//         } else if let Value::QuotedList(ref mut cell) = self {
617//             for value in iter {
618//                 cell.push_value(value);
619//             }
620//         } else {
621//             match self.clone() {
622//                 Value::EmptyList => {
623//                     let mut cell = Cell::nil();
624//                     for value in iter {
625//                         cell.push_value(value)
626//                     }
627//                     *self = Value::List(cell)
628//                 },
629//                 Value::EmptyQuotedList => {
630//                     let mut cell = Cell::nil();
631//                     for value in iter {
632//                         cell.push_value(value)
633//                     }
634//                     *self = Value::QuotedList(cell)
635//                 },
636//                 value => {
637//                     let mut cell = Cell::nil();
638//                     for value in iter {
639//                         cell.push_value(value)
640//                     }
641//                     *self = Value::List(cell)
642//                 },
643//             }
644//         }
645//     }
646// }
sexprs_data_structures/cell.rs

sexprs_data_structures/
cell.rs
