proto_vulcan/
lterm.rs

1use crate::compound::CompoundObject;
2use crate::engine::{DefaultEngine, Engine};
3use crate::user::{DefaultUser, User};
4use std::borrow::Borrow;
5use std::fmt;
6use std::hash::{Hash, Hasher};
7use std::iter::FromIterator;
8use std::ops::{Index, IndexMut};
9use std::rc::Rc;
10use std::sync::atomic::{AtomicUsize, Ordering};
11use std::vec::Vec;
12
13pub use crate::lvalue::LValue;
14
15static UNIQUE_ID_COUNTER: AtomicUsize = AtomicUsize::new(0);
16
17#[derive(Copy, Clone, Hash, PartialEq, Eq, Debug)]
18pub struct VarID(usize);
19
20impl VarID {
21    pub fn new() -> VarID {
22        let id = UNIQUE_ID_COUNTER.fetch_add(1, Ordering::SeqCst);
23        VarID(id)
24    }
25}
26
27impl fmt::Display for VarID {
28    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
29        write!(f, "{}", self.0)
30    }
31}
32
33/// Logic Term.
34#[derive(Derivative, Debug)]
35#[derivative(Clone(bound = "U: User"))]
36pub enum LTermInner<U, E>
37where
38    U: User,
39    E: Engine<U>,
40{
41    /// Literal value
42    Val(LValue),
43
44    /// Variable (uid, name)
45    Var(VarID, &'static str),
46
47    // User defined item
48    User(<U as User>::UserTerm),
49
50    // Empty list
51    Empty,
52
53    /// Non-empty list
54    Cons(LTerm<U, E>, LTerm<U, E>),
55
56    // Projection variable. A Projection variable will cause panic if it is tested for equality
57    // or a hash is computed. To use in substitutions, it must be projected first to non-Projection
58    // kind LTerm.
59    Projection(LTerm<U, E>),
60
61    // Compound object
62    Compound(Rc<dyn CompoundObject<U, E>>),
63}
64
65#[derive(Derivative)]
66#[derivative(Clone(bound = "U: User"))]
67pub struct LTerm<U = DefaultUser, E = DefaultEngine<U>>
68where
69    U: User,
70    E: Engine<U>,
71{
72    inner: Rc<LTermInner<U, E>>,
73}
74
75impl<U, E> LTerm<U, E>
76where
77    U: User,
78    E: Engine<U>,
79{
80    pub fn ptr_eq(this: &LTerm<U, E>, other: &LTerm<U, E>) -> bool {
81        Rc::ptr_eq(&this.inner, &other.inner)
82    }
83
84    pub fn var(name: &'static str) -> LTerm<U, E> {
85        if name == "_" {
86            panic!("Error: Invalid variable name. Name \"_\" is reserved for any-variables.")
87        }
88
89        LTerm {
90            inner: Rc::new(LTermInner::Var(VarID::new(), name)),
91        }
92    }
93
94    pub fn any() -> LTerm<U, E> {
95        LTerm {
96            inner: Rc::new(LTermInner::Var(VarID::new(), "_")),
97        }
98    }
99
100    pub fn user(u: U::UserTerm) -> LTerm<U, E> {
101        LTerm {
102            inner: Rc::new(LTermInner::User(u)),
103        }
104    }
105
106    /// Constructs an empty list
107    ///
108    pub fn empty_list() -> LTerm<U, E> {
109        LTerm {
110            inner: Rc::new(LTermInner::Empty),
111        }
112    }
113
114    /// Constructs a LTerm list with a single element
115    ///
116    pub fn singleton(u: LTerm<U, E>) -> LTerm<U, E> {
117        LTerm {
118            inner: Rc::new(LTermInner::Cons(u, LTerm::empty_list())),
119        }
120    }
121
122    pub fn projection(u: LTerm<U, E>) -> LTerm<U, E> {
123        match u.as_ref() {
124            LTermInner::Var(_, _) => LTerm {
125                inner: Rc::new(LTermInner::Projection(u)),
126            },
127            _ => unreachable!(),
128        }
129    }
130
131    /// Convert LTerm::Projection into non-Projection kind LTerm using the projection function `f`
132    /// that is applied to the projection variable.
133    pub fn project<F>(&self, f: F)
134    where
135        F: FnOnce(&LTerm<U, E>) -> LTerm<U, E>,
136    {
137        match self.as_ref() {
138            LTermInner::Projection(p) => {
139                let ptr: *const LTermInner<U, E> = self.inner.as_ref();
140                let projected = f(p).into_inner();
141                let _ = unsafe {
142                    let mut_ptr = ptr as *mut LTermInner<U, E>;
143                    std::ptr::replace(mut_ptr, projected.as_ref().clone())
144                };
145            }
146            _ => panic!("Cannot project non-Projection LTerm."),
147        }
148    }
149
150    pub fn into_inner(self) -> Rc<LTermInner<U, E>> {
151        self.inner
152    }
153
154    /// Construct a list cell
155    pub fn cons(head: LTerm<U, E>, tail: LTerm<U, E>) -> LTerm<U, E> {
156        LTerm {
157            inner: Rc::new(LTermInner::Cons(head, tail)),
158        }
159    }
160
161    pub fn from_vec(l: Vec<LTerm<U, E>>) -> LTerm<U, E> {
162        if l.is_empty() {
163            LTerm::empty_list()
164        } else {
165            let mut c = LTerm::empty_list();
166            for t in l.into_iter().rev() {
167                c = LTerm::cons(t, c);
168            }
169            c
170        }
171    }
172
173    pub fn from_array(a: &[LTerm<U, E>]) -> LTerm<U, E> {
174        if a.is_empty() {
175            LTerm::empty_list()
176        } else {
177            let mut c = LTerm::empty_list();
178            for t in a.to_vec().into_iter().rev() {
179                c = LTerm::cons(t, c);
180            }
181            c
182        }
183    }
184
185    pub fn improper_from_vec(mut h: Vec<LTerm<U, E>>) -> LTerm<U, E> {
186        if h.is_empty() {
187            panic!("Improper list must have at least one element");
188        } else {
189            let mut c = h.pop().unwrap();
190            for s in h.into_iter().rev() {
191                c = LTerm::cons(s, c);
192            }
193            c
194        }
195    }
196
197    pub fn improper_from_array(h: &[LTerm<U, E>]) -> LTerm<U, E> {
198        let mut h = h.to_vec();
199        if h.is_empty() {
200            panic!("Improper list must have at least one element");
201        } else {
202            let mut c = h.pop().unwrap();
203            for s in h.into_iter().rev() {
204                c = LTerm::cons(s, c);
205            }
206            c
207        }
208    }
209
210    pub fn contains<T: Borrow<LTerm<U, E>>>(&self, v: &T) -> bool {
211        let v = v.borrow();
212        self.iter().any(|u| u == v)
213    }
214
215    pub fn is_val(&self) -> bool {
216        match self.as_ref() {
217            LTermInner::Val(_) => true,
218            _ => false,
219        }
220    }
221
222    pub fn is_bool(&self) -> bool {
223        match self.as_ref() {
224            LTermInner::Val(LValue::Bool(_)) => true,
225            _ => false,
226        }
227    }
228
229    pub fn get_bool(&self) -> Option<bool> {
230        match self.as_ref() {
231            LTermInner::Val(LValue::Bool(u)) => Some(*u),
232            _ => None,
233        }
234    }
235
236    pub fn get_name(&self) -> Option<&str> {
237        match self.as_ref() {
238            LTermInner::Var(_, name) => Some(name),
239            _ => None,
240        }
241    }
242
243    pub fn is_number(&self) -> bool {
244        match self.as_ref() {
245            LTermInner::Val(LValue::Number(_)) => true,
246            _ => false,
247        }
248    }
249
250    pub fn get_number(&self) -> Option<isize> {
251        match self.as_ref() {
252            LTermInner::Val(LValue::Number(u)) => Some(*u),
253            _ => None,
254        }
255    }
256
257    pub fn is_var(&self) -> bool {
258        match self.as_ref() {
259            LTermInner::<U, E>::Var(_, _) => true,
260            _ => false,
261        }
262    }
263
264    pub fn is_any(&self) -> bool {
265        match self.as_ref() {
266            LTermInner::Var(_, "_") => true,
267            _ => false,
268        }
269    }
270
271    pub fn is_user(&self) -> bool {
272        match self.as_ref() {
273            LTermInner::User(_) => true,
274            _ => false,
275        }
276    }
277
278    pub fn get_user(&self) -> Option<&U::UserTerm> {
279        match self.as_ref() {
280            LTermInner::User(u) => Some(u),
281            _ => None,
282        }
283    }
284
285    pub fn is_projection(&self) -> bool {
286        match self.as_ref() {
287            LTermInner::Projection(_) => true,
288            _ => false,
289        }
290    }
291
292    pub fn get_projection(&self) -> Option<&LTerm<U, E>> {
293        match self.as_ref() {
294            LTermInner::Projection(p) => Some(p),
295            _ => None,
296        }
297    }
298
299    pub fn is_list(&self) -> bool {
300        match self.as_ref() {
301            LTermInner::Empty => true,
302            LTermInner::Cons(_, _) => true,
303            _ => false,
304        }
305    }
306
307    pub fn is_improper(&self) -> bool {
308        match self.as_ref() {
309            LTermInner::Empty => false,
310            LTermInner::Cons(_, tail) => {
311                if tail.is_empty() {
312                    false
313                } else {
314                    if tail.is_list() {
315                        tail.is_improper()
316                    } else {
317                        true
318                    }
319                }
320            }
321            _ => false,
322        }
323    }
324
325    pub fn is_empty(&self) -> bool {
326        match self.as_ref() {
327            LTermInner::Empty => true,
328            _ => false,
329        }
330    }
331
332    pub fn is_non_empty_list(&self) -> bool {
333        match self.as_ref() {
334            LTermInner::Cons(_, _) => true,
335            _ => false,
336        }
337    }
338
339    pub fn head(&self) -> Option<&LTerm<U, E>> {
340        match self.as_ref() {
341            LTermInner::Cons(head, _) => Some(head),
342            _ => None,
343        }
344    }
345
346    pub fn tail(&self) -> Option<&LTerm<U, E>> {
347        match self.as_ref() {
348            LTermInner::Cons(_, tail) => Some(tail),
349            _ => None,
350        }
351    }
352
353    pub fn head_mut(&mut self) -> Option<&mut LTerm<U, E>> {
354        match self.as_mut() {
355            LTermInner::Cons(head, _) => Some(head),
356            _ => None,
357        }
358    }
359
360    pub fn tail_mut(&mut self) -> Option<&mut LTerm<U, E>> {
361        match self.as_mut() {
362            LTermInner::Cons(_, tail) => Some(tail),
363            _ => None,
364        }
365    }
366
367    pub fn iter(&self) -> LTermIter<'_, U, E> {
368        LTermIter::new(self)
369    }
370
371    pub fn iter_mut(&mut self) -> LTermIterMut<'_, U, E> {
372        LTermIterMut::new(self)
373    }
374
375    /// Recursively find all `any` variables referenced by the LTerm.
376    pub fn anyvars(self: &LTerm<U, E>) -> Vec<LTerm<U, E>> {
377        match self.as_ref() {
378            LTermInner::Cons(head, tail) => {
379                let mut vars = head.anyvars();
380                for t in tail.iter() {
381                    let tvars = t.anyvars();
382                    vars.extend(tvars);
383                }
384                vars
385            }
386            _ => {
387                if self.is_any() {
388                    vec![self.clone()]
389                } else {
390                    vec![]
391                }
392            }
393        }
394    }
395}
396
397impl<U, E> From<Rc<dyn CompoundObject<U, E>>> for LTerm<U, E>
398where
399    U: User,
400    E: Engine<U>,
401{
402    fn from(u: Rc<dyn CompoundObject<U, E>>) -> LTerm<U, E> {
403        LTerm::from(LTermInner::Compound(u))
404    }
405}
406
407impl<U, E> From<&LTerm<U, E>> for LTerm<U, E>
408where
409    U: User,
410    E: Engine<U>,
411{
412    fn from(reference: &LTerm<U, E>) -> LTerm<U, E> {
413        reference.clone()
414    }
415}
416
417impl<U, E> From<LTermInner<U, E>> for LTerm<U, E>
418where
419    U: User,
420    E: Engine<U>,
421{
422    fn from(inner: LTermInner<U, E>) -> LTerm<U, E> {
423        LTerm {
424            inner: Rc::new(inner),
425        }
426    }
427}
428
429impl<U, E> From<isize> for LTerm<U, E>
430where
431    U: User,
432    E: Engine<U>,
433{
434    fn from(u: isize) -> LTerm<U, E> {
435        LTerm::from(LTermInner::Val(LValue::Number(u)))
436    }
437}
438
439impl<U, E> From<bool> for LTerm<U, E>
440where
441    U: User,
442    E: Engine<U>,
443{
444    fn from(u: bool) -> LTerm<U, E> {
445        LTerm::from(LTermInner::Val(LValue::Bool(u)))
446    }
447}
448
449impl<U, E> From<&str> for LTerm<U, E>
450where
451    U: User,
452    E: Engine<U>,
453{
454    fn from(u: &str) -> LTerm<U, E> {
455        LTerm::from(LTermInner::Val(LValue::String(String::from(u))))
456    }
457}
458
459impl<U, E> From<String> for LTerm<U, E>
460where
461    U: User,
462    E: Engine<U>,
463{
464    fn from(u: String) -> LTerm<U, E> {
465        LTerm::from(LTermInner::Val(LValue::String(u)))
466    }
467}
468
469impl<U, E> From<char> for LTerm<U, E>
470where
471    U: User,
472    E: Engine<U>,
473{
474    fn from(u: char) -> LTerm<U, E> {
475        LTerm::from(LTermInner::Val(LValue::Char(u)))
476    }
477}
478
479impl<U, E> AsRef<LTermInner<U, E>> for LTerm<U, E>
480where
481    U: User,
482    E: Engine<U>,
483{
484    fn as_ref(&self) -> &LTermInner<U, E> {
485        &self.inner
486    }
487}
488
489impl<U, E> AsRef<LTerm<U, E>> for LTerm<U, E>
490where
491    U: User,
492    E: Engine<U>,
493{
494    fn as_ref(&self) -> &LTerm<U, E> {
495        self
496    }
497}
498
499impl<U, E> AsMut<LTermInner<U, E>> for LTerm<U, E>
500where
501    U: User,
502    E: Engine<U>,
503{
504    fn as_mut(&mut self) -> &mut LTermInner<U, E> {
505        Rc::make_mut(&mut self.inner)
506    }
507}
508
509impl<U, E> fmt::Debug for LTerm<U, E>
510where
511    U: User,
512    E: Engine<U>,
513{
514    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
515        match self.as_ref() {
516            LTermInner::Val(val) => write!(f, "{:?}", val),
517            LTermInner::Var(uid, name) => write!(f, "Var({:?}, {:?})", uid, name),
518            LTermInner::User(user) => write!(f, "User({:?})", user),
519            LTermInner::Projection(p) => write!(f, "Projection({:?})", p),
520            LTermInner::Empty => write!(f, "Empty"),
521            LTermInner::Cons(head, tail) => write!(f, "({:?}, {:?})", head, tail),
522            LTermInner::Compound(cf) => write!(f, "{:?}", cf),
523        }
524    }
525}
526
527impl<U, E> fmt::Display for LTerm<U, E>
528where
529    U: User,
530    E: Engine<U>,
531{
532    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
533        match self.as_ref() {
534            LTermInner::Val(val) => write!(f, "{}", val),
535            LTermInner::Var(uid, name) => {
536                if self.is_any() {
537                    write!(f, "{}.{}", name, uid)
538                } else {
539                    write!(f, "{}", name)
540                }
541            }
542            LTermInner::User(user) => write!(f, "User({:?})", user),
543            LTermInner::Projection(p) => write!(f, "Projection({})", p),
544            LTermInner::Empty => write!(f, "[]"),
545            LTermInner::Cons(_, _) => {
546                if self.is_improper() {
547                    let len = self.iter().count();
548                    write!(f, "[")?;
549                    for (count, v) in self.iter().enumerate() {
550                        if count == 0 {
551                            ()
552                        } else if count > 0 && count < len - 1 {
553                            write!(f, ", ")?;
554                        } else {
555                            write!(f, " | ")?;
556                        }
557                        write!(f, "{}", v)?;
558                    }
559                    write!(f, "]")
560                } else {
561                    write!(f, "[")?;
562                    for (count, v) in self.iter().enumerate() {
563                        if count != 0 {
564                            write!(f, ", ")?;
565                        }
566                        write!(f, "{}", v)?;
567                    }
568                    write!(f, "]")
569                }
570            }
571            LTermInner::Compound(compound_term) => write!(f, "{:?}", compound_term),
572        }
573    }
574}
575
576impl<U, E> Hash for LTerm<U, E>
577where
578    U: User,
579    E: Engine<U>,
580{
581    fn hash<H: Hasher>(&self, state: &mut H) {
582        match self.as_ref() {
583            LTermInner::Val(val) => val.hash(state),
584            LTermInner::Var(uid, _) => uid.hash(state),
585            LTermInner::User(user) => user.hash(state),
586            LTermInner::Projection(_) => panic!("Cannot compute hash for LTerm::Projection."),
587            LTermInner::Empty => ().hash(state),
588            LTermInner::Cons(head, tail) => {
589                head.hash(state);
590                tail.hash(state);
591            }
592            LTermInner::Compound(cf) => cf.compound_hash(state),
593        }
594    }
595}
596
597impl<U, E> PartialEq<LTerm<U, E>> for LTerm<U, E>
598where
599    U: User,
600    E: Engine<U>,
601{
602    fn eq(&self, other: &Self) -> bool {
603        match (self.as_ref(), other.as_ref()) {
604            (LTermInner::Var(self_uid, _), LTermInner::Var(other_uid, _)) => self_uid == other_uid,
605            (LTermInner::Val(self_val), LTermInner::Val(other_val)) => self_val == other_val,
606            (LTermInner::User(self_user), LTermInner::User(other_user)) => self_user == other_user,
607            (LTermInner::Projection(_), _) => panic!("Cannot compare LTerm::Projection."),
608            (_, LTermInner::Projection(_)) => panic!("Cannot compare LTerm::Projection."),
609            (LTermInner::Empty, LTermInner::Empty) => true,
610            (LTermInner::Cons(self_head, self_tail), LTermInner::Cons(other_head, other_tail)) => {
611                (self_head == other_head) & (self_tail == other_tail)
612            }
613            (LTermInner::Compound(self_cf), LTermInner::Compound(other_cf)) => {
614                self_cf.compound_eq(other_cf.as_object())
615            }
616            _ => false,
617        }
618    }
619}
620
621impl<U, E> PartialEq<LValue> for LTerm<U, E>
622where
623    U: User,
624    E: Engine<U>,
625{
626    fn eq(&self, other: &LValue) -> bool {
627        match self.as_ref() {
628            LTermInner::Val(v) => v == other,
629            _ => false,
630        }
631    }
632}
633
634impl<U, E> PartialEq<LTerm<U, E>> for LValue
635where
636    U: User,
637    E: Engine<U>,
638{
639    fn eq(&self, other: &LTerm<U, E>) -> bool {
640        match other.as_ref() {
641            LTermInner::Val(v) => v == self,
642            _ => false,
643        }
644    }
645}
646
647impl<U, E> PartialEq<bool> for LTerm<U, E>
648where
649    U: User,
650    E: Engine<U>,
651{
652    fn eq(&self, other: &bool) -> bool {
653        match self.as_ref() {
654            LTermInner::Val(LValue::Bool(x)) => x == other,
655            _ => false,
656        }
657    }
658}
659
660impl<U, E> PartialEq<LTerm<U, E>> for bool
661where
662    U: User,
663    E: Engine<U>,
664{
665    fn eq(&self, other: &LTerm<U, E>) -> bool {
666        match other.as_ref() {
667            LTermInner::Val(LValue::Bool(x)) => x == self,
668            _ => false,
669        }
670    }
671}
672
673impl<U, E> PartialEq<isize> for LTerm<U, E>
674where
675    U: User,
676    E: Engine<U>,
677{
678    fn eq(&self, other: &isize) -> bool {
679        match self.as_ref() {
680            LTermInner::Val(LValue::Number(x)) => x == other,
681            _ => false,
682        }
683    }
684}
685
686impl<U, E> PartialEq<LTerm<U, E>> for isize
687where
688    U: User,
689    E: Engine<U>,
690{
691    fn eq(&self, other: &LTerm<U, E>) -> bool {
692        match other.as_ref() {
693            LTermInner::Val(LValue::Number(x)) => x == self,
694            _ => false,
695        }
696    }
697}
698
699impl<U, E> PartialEq<char> for LTerm<U, E>
700where
701    U: User,
702    E: Engine<U>,
703{
704    fn eq(&self, other: &char) -> bool {
705        match self.as_ref() {
706            LTermInner::Val(LValue::Char(x)) => x == other,
707            _ => false,
708        }
709    }
710}
711
712impl<U, E> PartialEq<LTerm<U, E>> for char
713where
714    U: User,
715    E: Engine<U>,
716{
717    fn eq(&self, other: &LTerm<U, E>) -> bool {
718        match other.as_ref() {
719            LTermInner::Val(LValue::Char(x)) => x == self,
720            _ => false,
721        }
722    }
723}
724
725impl<U, E> PartialEq<String> for LTerm<U, E>
726where
727    U: User,
728    E: Engine<U>,
729{
730    fn eq(&self, other: &String) -> bool {
731        match self.as_ref() {
732            LTermInner::Val(LValue::String(x)) => x == other,
733            _ => false,
734        }
735    }
736}
737
738impl<U, E> PartialEq<LTerm<U, E>> for String
739where
740    U: User,
741    E: Engine<U>,
742{
743    fn eq(&self, other: &LTerm<U, E>) -> bool {
744        match other.as_ref() {
745            LTermInner::Val(LValue::String(x)) => x == self,
746            _ => false,
747        }
748    }
749}
750
751impl<U, E> PartialEq<str> for LTerm<U, E>
752where
753    U: User,
754    E: Engine<U>,
755{
756    fn eq(&self, other: &str) -> bool {
757        match self.as_ref() {
758            LTermInner::Val(LValue::String(x)) => x == other,
759            _ => false,
760        }
761    }
762}
763
764impl<U, E> PartialEq<LTerm<U, E>> for str
765where
766    U: User,
767    E: Engine<U>,
768{
769    fn eq(&self, other: &LTerm<U, E>) -> bool {
770        match other.as_ref() {
771            LTermInner::Val(LValue::String(x)) => x == self,
772            _ => false,
773        }
774    }
775}
776
777impl<U, E> PartialEq<&str> for LTerm<U, E>
778where
779    U: User,
780    E: Engine<U>,
781{
782    fn eq(&self, other: &&str) -> bool {
783        match self.as_ref() {
784            LTermInner::Val(LValue::String(x)) => x == other,
785            _ => false,
786        }
787    }
788}
789
790impl<U, E> PartialEq<LTerm<U, E>> for &str
791where
792    U: User,
793    E: Engine<U>,
794{
795    fn eq(&self, other: &LTerm<U, E>) -> bool {
796        match other.as_ref() {
797            LTermInner::Val(LValue::String(x)) => x == self,
798            _ => false,
799        }
800    }
801}
802
803impl<U, E> Eq for LTerm<U, E>
804where
805    U: User,
806    E: Engine<U>,
807{
808}
809
810impl<U, E> Default for LTerm<U, E>
811where
812    U: User,
813    E: Engine<U>,
814{
815    fn default() -> Self {
816        LTerm::from(LTermInner::Empty)
817    }
818}
819
820impl<U, E> FromIterator<LTerm<U, E>> for LTerm<U, E>
821where
822    U: User,
823    E: Engine<U>,
824{
825    fn from_iter<T: IntoIterator<Item = LTerm<U, E>>>(iter: T) -> Self {
826        let mut list_head = LTerm::empty_list();
827        let mut list_tail = &mut list_head;
828        for elem in iter {
829            let _ = std::mem::replace(
830                list_tail.as_mut(),
831                LTermInner::Cons(elem, LTerm::empty_list()),
832            );
833            list_tail = list_tail.tail_mut().unwrap();
834        }
835        list_head
836    }
837}
838
839impl<U, E> Extend<LTerm<U, E>> for LTerm<U, E>
840where
841    U: User,
842    E: Engine<U>,
843{
844    fn extend<T: IntoIterator<Item = LTerm<U, E>>>(&mut self, coll: T) {
845        if !self.is_list() {
846            panic!("Only list type (Empty or Cons) LTerms can be extended.");
847        }
848
849        // Find tail of the list
850        let mut tail = self;
851        loop {
852            if tail.is_empty() {
853                break;
854            } else {
855                tail = tail.tail_mut().unwrap();
856            }
857        }
858
859        // Swap in extension as new tail.
860        let mut extension: LTerm<U, E> = coll.into_iter().collect();
861        std::mem::swap(tail.as_mut(), extension.as_mut());
862    }
863}
864
865#[derive(Clone, Debug)]
866pub struct LTermIter<'a, U, E>
867where
868    U: User,
869    E: Engine<U>,
870{
871    maybe_next: Option<&'a LTerm<U, E>>,
872}
873
874impl<'a, U, E> LTermIter<'a, U, E>
875where
876    U: User,
877    E: Engine<U>,
878{
879    pub fn new(u: &'a LTerm<U, E>) -> LTermIter<'a, U, E> {
880        LTermIter {
881            maybe_next: Some(u),
882        }
883    }
884}
885
886impl<'a, U, E> Iterator for LTermIter<'a, U, E>
887where
888    U: User,
889    E: Engine<U>,
890{
891    type Item = &'a LTerm<U, E>;
892
893    fn next(&mut self) -> Option<Self::Item> {
894        // Replace maybe_next in iterator with its tail and return head
895        match self.maybe_next.map(|x| x.as_ref()) {
896            Some(LTermInner::Cons(head, tail)) => {
897                if tail.is_empty() {
898                    // The iterator has finished the list after this one
899                    self.maybe_next = None;
900                } else {
901                    let _ = self.maybe_next.replace(tail);
902                }
903
904                Some(head)
905            }
906            Some(LTermInner::Empty) => {
907                self.maybe_next = None;
908                None
909            }
910            Some(_) => {
911                // If the list is improper, it ends in non-cons term.
912                self.maybe_next.take()
913            }
914            _ => None, // Iterator is finished
915        }
916    }
917}
918
919impl<'a, U, E> std::iter::FusedIterator for LTermIter<'a, U, E>
920where
921    U: User,
922    E: Engine<U>,
923{
924}
925
926impl<'a, U, E> IntoIterator for &'a LTerm<U, E>
927where
928    U: User,
929    E: Engine<U>,
930{
931    type Item = &'a LTerm<U, E>;
932    type IntoIter = LTermIter<'a, U, E>;
933
934    fn into_iter(self) -> LTermIter<'a, U, E> {
935        LTermIter::new(self)
936    }
937}
938
939#[derive(Debug)]
940pub struct LTermIterMut<'a, U, E>
941where
942    U: User,
943    E: Engine<U>,
944{
945    maybe_next: Option<&'a mut LTerm<U, E>>,
946}
947
948impl<'a, U, E> LTermIterMut<'a, U, E>
949where
950    U: User,
951    E: Engine<U>,
952{
953    pub fn new(u: &'a mut LTerm<U, E>) -> LTermIterMut<'a, U, E> {
954        LTermIterMut {
955            maybe_next: Some(u),
956        }
957    }
958}
959
960impl<'a, U, E> Iterator for LTermIterMut<'a, U, E>
961where
962    U: User,
963    E: Engine<U>,
964{
965    type Item = &'a mut LTerm<U, E>;
966
967    fn next(&mut self) -> Option<Self::Item> {
968        // Replace maybe_next in iterator with its tail and return head
969        match self.maybe_next.take().map(|x| x.as_mut()) {
970            Some(LTermInner::Cons(head, tail)) => {
971                if tail.is_empty() {
972                    // The iterator has finished the list after this one
973                    self.maybe_next = None;
974                } else {
975                    let _ = self.maybe_next.replace(tail);
976                }
977
978                Some(head)
979            }
980            Some(LTermInner::Empty) => {
981                self.maybe_next = None;
982                None
983            }
984            Some(_) => {
985                // If the list is improper, it ends in non-cons term.
986                self.maybe_next.take()
987            }
988            _ => None, // Iterator is finished
989        }
990    }
991}
992
993impl<'a, U, E> IntoIterator for &'a mut LTerm<U, E>
994where
995    U: User,
996    E: Engine<U>,
997{
998    type Item = &'a mut LTerm<U, E>;
999    type IntoIter = LTermIterMut<'a, U, E>;
1000
1001    fn into_iter(self) -> LTermIterMut<'a, U, E> {
1002        LTermIterMut::new(self)
1003    }
1004}
1005
1006impl<'a, U, E> std::iter::FusedIterator for LTermIterMut<'a, U, E>
1007where
1008    U: User,
1009    E: Engine<U>,
1010{
1011}
1012
1013impl<U, E> Index<usize> for LTerm<U, E>
1014where
1015    U: User,
1016    E: Engine<U>,
1017{
1018    type Output = LTerm<U, E>;
1019
1020    fn index(&self, index: usize) -> &Self::Output {
1021        self.iter().nth(index).unwrap()
1022    }
1023}
1024
1025impl<U, E> IndexMut<usize> for LTerm<U, E>
1026where
1027    U: User,
1028    E: Engine<U>,
1029{
1030    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
1031        self.iter_mut().nth(index).unwrap()
1032    }
1033}
1034
1035#[cfg(test)]
1036mod test {
1037    use super::*;
1038    use std::collections::HashMap;
1039
1040    #[test]
1041    fn test_lterm_var_1() {
1042        let mut u = LTerm::<DefaultUser>::var("x");
1043        assert!(u.is_var());
1044        assert!(!u.is_val());
1045        assert!(!u.is_bool());
1046        assert!(!u.is_list());
1047        assert!(!u.is_empty());
1048        assert!(!u.is_non_empty_list());
1049        assert!(!u.is_user());
1050        assert!(!u.is_projection());
1051        assert!(u.tail().is_none());
1052        assert!(u.head().is_none());
1053        assert!(u.tail_mut().is_none());
1054        assert!(u.head_mut().is_none());
1055    }
1056
1057    #[test]
1058    #[should_panic]
1059    fn test_lterm_var_2() {
1060        let _ = LTerm::<DefaultUser>::var("_");
1061    }
1062
1063    #[test]
1064    fn test_lterm_val_1() {
1065        let mut u: LTerm<DefaultUser, DefaultEngine<DefaultUser>> = lterm!(1);
1066        assert!(u.is_val());
1067        assert!(!u.is_var());
1068        assert!(!u.is_bool());
1069        assert!(!u.is_list());
1070        assert!(!u.is_empty());
1071        assert!(!u.is_non_empty_list());
1072        assert!(!u.is_user());
1073        assert!(!u.is_projection());
1074        assert!(u.tail().is_none());
1075        assert!(u.head().is_none());
1076        assert!(u.tail_mut().is_none());
1077        assert!(u.head_mut().is_none());
1078    }
1079
1080    #[test]
1081    fn test_lterm_val_2() {
1082        let mut u: LTerm<DefaultUser> = lterm!(true);
1083        assert!(u.is_val());
1084        assert!(!u.is_var());
1085        assert!(u.is_bool());
1086        assert!(!u.is_list());
1087        assert!(!u.is_empty());
1088        assert!(!u.is_non_empty_list());
1089        assert!(!u.is_user());
1090        assert!(!u.is_projection());
1091        assert!(u.tail().is_none());
1092        assert!(u.head().is_none());
1093        assert!(u.tail_mut().is_none());
1094        assert!(u.head_mut().is_none());
1095    }
1096
1097    #[test]
1098    fn test_lterm_iter_1() {
1099        let u: LTerm<DefaultUser> = lterm!([]);
1100        let mut iter = u.iter();
1101        assert!(iter.next().is_none());
1102    }
1103
1104    #[test]
1105    fn test_lterm_iter_2() {
1106        let u: LTerm<DefaultUser> = lterm!([1]);
1107        let mut iter = u.iter();
1108        assert_eq!(iter.next().unwrap(), &1);
1109        assert!(iter.next().is_none());
1110    }
1111
1112    #[test]
1113    fn test_lterm_iter_3() {
1114        let u: LTerm<DefaultUser> = lterm!([1, 2, 3]);
1115        let mut iter = u.iter();
1116        assert_eq!(iter.next().unwrap(), &1);
1117        assert_eq!(iter.next().unwrap(), &2);
1118        assert_eq!(iter.next().unwrap(), &3);
1119        assert!(iter.next().is_none());
1120    }
1121
1122    #[test]
1123    fn test_lterm_iter_4() {
1124        let u: LTerm<DefaultUser> = lterm!([1, 2 | 3]);
1125        let mut iter = u.iter();
1126        assert_eq!(iter.next().unwrap(), &1);
1127        assert_eq!(iter.next().unwrap(), &2);
1128        assert_eq!(iter.next().unwrap(), &3);
1129        assert!(iter.next().is_none());
1130    }
1131
1132    #[test]
1133    fn test_lterm_iter_5() {
1134        let u: LTerm<DefaultUser> = lterm!([1, 2, 3]);
1135        let mut iter = IntoIterator::into_iter(&u);
1136        assert_eq!(iter.next().unwrap(), &1);
1137        assert_eq!(iter.next().unwrap(), &2);
1138        assert_eq!(iter.next().unwrap(), &3);
1139        assert!(iter.next().is_none());
1140    }
1141
1142    #[test]
1143    fn test_lterm_iter_mut_1() {
1144        let mut u: LTerm<DefaultUser> = lterm!([1, 2, 3]);
1145        let iter = u.iter_mut();
1146        for x in iter {
1147            *x = lterm!(4);
1148        }
1149        let mut iter = u.iter();
1150        assert_eq!(iter.next().unwrap(), &4);
1151        assert_eq!(iter.next().unwrap(), &4);
1152        assert_eq!(iter.next().unwrap(), &4);
1153        assert!(iter.next().is_none());
1154    }
1155
1156    #[test]
1157    fn test_lterm_iter_mut_2() {
1158        let mut u: LTerm<DefaultUser> = lterm!([1, 2, 3]);
1159        for term in &mut u {
1160            *term = lterm!(5);
1161        }
1162        let mut iter = u.iter();
1163        assert_eq!(iter.next().unwrap(), &5);
1164        assert_eq!(iter.next().unwrap(), &5);
1165        assert_eq!(iter.next().unwrap(), &5);
1166        assert!(iter.next().is_none());
1167    }
1168
1169    #[test]
1170    fn test_lterm_from_iter_1() {
1171        let v: Vec<LTerm<DefaultUser>> = vec![lterm!(1), lterm!(2), lterm!(3)];
1172        let u: LTerm<DefaultUser> = LTerm::from_iter(v);
1173        assert!(u == lterm!([1, 2, 3]));
1174    }
1175
1176    #[test]
1177    fn test_lterm_extend_1() {
1178        let v = vec![lterm!(1), lterm!(2), lterm!(3)];
1179        let mut u: LTerm<DefaultUser> = lterm!([]);
1180        u.extend(v);
1181        assert!(u == lterm!([1, 2, 3]));
1182    }
1183
1184    #[test]
1185    fn test_lterm_extend_2() {
1186        let v = vec![lterm!(1), lterm!(2), lterm!(3)];
1187        let mut u: LTerm<DefaultUser> = lterm!([4, 5, 6]);
1188        u.extend(v);
1189        assert!(u == lterm!([4, 5, 6, 1, 2, 3]));
1190    }
1191
1192    #[test]
1193    fn test_lterm_eq_1() {
1194        // LTerm vs. LTerm
1195        assert_eq!(lterm!(1) as LTerm<DefaultUser>, lterm!(1));
1196        assert_eq!(lterm!(true) as LTerm<DefaultUser>, lterm!(true));
1197        assert_eq!(lterm!("foo") as LTerm<DefaultUser>, lterm!("foo"));
1198        assert_eq!(lterm!('a') as LTerm<DefaultUser>, lterm!('a'));
1199        assert_eq!(lterm!([1, 2, 3]) as LTerm<DefaultUser>, lterm!([1, 2, 3]));
1200        assert_ne!(lterm!(1) as LTerm<DefaultUser>, lterm!(2));
1201        assert_ne!(lterm!(1) as LTerm<DefaultUser>, lterm!(true));
1202        assert_ne!(lterm!(1) as LTerm<DefaultUser>, lterm!('a'));
1203        assert_ne!(lterm!(1) as LTerm<DefaultUser>, lterm!([]));
1204        assert_ne!(lterm!(1) as LTerm<DefaultUser>, lterm!([1]));
1205        assert_ne!(lterm!(1) as LTerm<DefaultUser>, lterm!("true"));
1206        let u: LTerm<DefaultUser> = LTerm::var("x");
1207        let v: LTerm<DefaultUser> = LTerm::var("x");
1208        assert_eq!(u, u);
1209        assert_ne!(u, v);
1210    }
1211
1212    #[test]
1213    fn test_lterm_eq_2() {
1214        // LTerm vs. Rust constant
1215        assert_eq!(lterm!(1) as LTerm<DefaultUser>, 1);
1216        assert_ne!(lterm!(1) as LTerm<DefaultUser>, 2);
1217        assert_ne!(lterm!(1) as LTerm<DefaultUser>, true);
1218        assert_eq!(1, lterm!(1) as LTerm<DefaultUser>);
1219        assert_ne!(2, lterm!(1) as LTerm<DefaultUser>);
1220        assert_ne!(true, lterm!(1) as LTerm<DefaultUser>);
1221        assert_eq!(lterm!("proto-vulcan") as LTerm<DefaultUser>, "proto-vulcan");
1222        assert_ne!(
1223            lterm!(["proto-vulcan"]) as LTerm<DefaultUser>,
1224            "proto-vulcan"
1225        );
1226        assert_eq!("proto-vulcan", lterm!("proto-vulcan") as LTerm<DefaultUser>);
1227        assert_ne!(
1228            "proto-vulcan",
1229            lterm!(["proto-vulcan"]) as LTerm<DefaultUser>
1230        );
1231        assert_eq!(
1232            lterm!("proto-vulcan") as LTerm<DefaultUser>,
1233            "proto-vulcan"[0..]
1234        );
1235        assert_ne!(
1236            lterm!(["proto-vulcan"]) as LTerm<DefaultUser>,
1237            "proto-vulcan"[0..]
1238        );
1239        assert_eq!(
1240            "proto-vulcan"[0..],
1241            lterm!("proto-vulcan") as LTerm<DefaultUser>
1242        );
1243        assert_ne!(
1244            "proto-vulcan"[0..],
1245            lterm!(["proto-vulcan"]) as LTerm<DefaultUser>
1246        );
1247        assert_eq!(
1248            lterm!("proto-vulcan") as LTerm<DefaultUser>,
1249            String::from("proto-vulcan")
1250        );
1251        assert_ne!(
1252            lterm!(["proto-vulcan"]) as LTerm<DefaultUser>,
1253            String::from("proto-vulcan")
1254        );
1255        assert_eq!(
1256            String::from("proto-vulcan"),
1257            lterm!("proto-vulcan") as LTerm<DefaultUser>
1258        );
1259        assert_ne!(
1260            String::from("proto-vulcan"),
1261            lterm!(["proto-vulcan"]) as LTerm<DefaultUser>
1262        );
1263        assert_eq!(lterm!('a') as LTerm<DefaultUser>, 'a');
1264        assert_ne!('b', lterm!('a') as LTerm<DefaultUser>);
1265        assert_ne!(lterm!(['a']) as LTerm<DefaultUser>, 'a');
1266        assert_ne!('a', lterm!(['a']) as LTerm<DefaultUser>);
1267        assert_ne!(lterm!(1) as LTerm<DefaultUser>, lterm!([1]));
1268        assert_ne!(lterm!([1]), lterm!(1) as LTerm<DefaultUser>);
1269    }
1270
1271    #[test]
1272    fn test_lterm_eq_3() {
1273        // LTerm vs. LValue
1274        assert_eq!(lterm!(1) as LTerm<DefaultUser>, LValue::from(1));
1275        assert_ne!(lterm!(1) as LTerm<DefaultUser>, LValue::from(2));
1276        assert_eq!(LValue::from(1), lterm!(1) as LTerm<DefaultUser>);
1277        assert_ne!(LValue::from(2), lterm!(1) as LTerm<DefaultUser>);
1278        assert_ne!(LValue::from(1), lterm!([1]) as LTerm<DefaultUser>);
1279        assert_ne!(lterm!([1]) as LTerm<DefaultUser>, LValue::from(1));
1280    }
1281
1282    #[test]
1283    #[should_panic]
1284    fn test_lterm_projection_1() {
1285        // Comparison with projection panics
1286        let u: LTerm<DefaultUser> = LTerm::var("x");
1287        let v = LTerm::projection(u.clone());
1288        assert_eq!(u, v);
1289    }
1290
1291    #[test]
1292    #[should_panic]
1293    fn test_lterm_projection_2() {
1294        // Comparison with projection panics
1295        let u: LTerm<DefaultUser> = LTerm::var("x");
1296        let v = LTerm::projection(u.clone());
1297        assert_eq!(v, u);
1298    }
1299
1300    #[test]
1301    #[should_panic]
1302    fn test_lterm_projection_3() {
1303        // Hash of projection panics
1304        let mut t = HashMap::new();
1305        let u: LTerm<DefaultUser> = LTerm::var("x");
1306        let v = LTerm::projection(u.clone());
1307        t.insert(v, lterm!(1) as LTerm<DefaultUser>);
1308    }
1309
1310    #[test]
1311    fn test_lterm_index_1() {
1312        let u: LTerm<DefaultUser> = lterm!([1, [2], false]);
1313        assert_eq!(u[0], 1);
1314        assert_eq!(u[1], lterm!([2]));
1315        assert_eq!(u[2], false);
1316    }
1317
1318    #[test]
1319    fn test_lterm_index_mut_1() {
1320        let mut u: LTerm<DefaultUser> = lterm!([0, 0, 0]);
1321        u[0] = lterm!(1);
1322        u[1] = lterm!([2]);
1323        u[2] = lterm!(false);
1324        assert_eq!(u[0], 1);
1325        assert_eq!(u[1], lterm!([2]));
1326        assert_eq!(u[2], false);
1327    }
1328
1329    #[test]
1330    fn test_lterm_display() {
1331        assert_eq!(format!("{}", lterm!(1234) as LTerm<DefaultUser>), "1234");
1332        assert_eq!(format!("{}", lterm!(-1234) as LTerm<DefaultUser>), "-1234");
1333        assert_eq!(format!("{}", lterm!(true) as LTerm<DefaultUser>), "true");
1334        assert_eq!(format!("{}", lterm!(false) as LTerm<DefaultUser>), "false");
1335        assert_eq!(format!("{}", LTerm::var("x") as LTerm<DefaultUser>), "x");
1336        assert_eq!(format!("{}", lterm!([]) as LTerm<DefaultUser>), "[]");
1337        assert_eq!(
1338            format!("{}", lterm!([1, [2], true, 'a']) as LTerm<DefaultUser>),
1339            "[1, [2], true, 'a']"
1340        );
1341        assert_eq!(
1342            format!("{}", lterm!([1, 2 | 3]) as LTerm<DefaultUser>),
1343            "[1, 2 | 3]"
1344        );
1345        let u = LTerm::var("x");
1346        assert_eq!(
1347            format!("{}", LTerm::projection(u) as LTerm<DefaultUser>),
1348            "Projection(x)"
1349        );
1350    }
1351}
proto_vulcan/lterm.rs

proto_vulcan/
lterm.rs
