prolog2/heap/
heap.rs

1use std::{
2    collections::HashMap,
3    mem,
4    ops::{Index, IndexMut, Range, RangeInclusive},
5};
6
7use super::symbol_db::SymbolDB;
8
9/// Tag discriminant for heap cells.
10///
11/// Each cell on the heap is a `(Tag, usize)` pair. The tag determines how
12/// the `usize` value is interpreted.
13#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
14#[repr(u8)]
15pub enum Tag {
16    /// Query variable (self-referencing = unbound).
17    Ref,
18    /// Clause variable (index into substitution).
19    Arg,
20    /// Functor: value is the arity (following cells are symbol + arguments).
21    Func,
22    /// Tuple.
23    Tup,
24    /// Set.
25    Set,
26    /// List cons cell: value points to head, next cell is tail.
27    Lis,
28    /// Empty list.
29    ELis,
30    /// Constant: value is a symbol ID from the [`super::symbol_db::SymbolDB`].
31    Con,
32    /// Integer: value is the raw bits of an `isize`.
33    Int,
34    /// Float: value is the raw bits of an `fsize`.
35    Flt,
36    /// Indirection to a structure: value is the heap address of the Func cell.
37    Str,
38    /// String literal: value is an index into [`super::symbol_db::SymbolDB`] strings.
39    Stri,
40}
41
42impl std::fmt::Display for Tag {
43    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
44        write!(f, "{self:?}")
45    }
46}
47
48/// A single heap cell: a `(Tag, value)` pair.
49pub type Cell = (Tag, usize);
50
51use fsize::fsize;
52pub const _CON_PTR: usize = isize::MAX as usize;
53pub const _FALSE: Cell = (Tag::Con, _CON_PTR);
54pub const _TRUE: Cell = (Tag::Con, _CON_PTR + 1);
55pub const EMPTY_LIS: Cell = (Tag::ELis, 0);
56
57/// Core trait for heap storage.
58///
59/// Implemented by both the static program heap (`Vec<Cell>`) and the
60/// query-time [`super::query_heap::QueryHeap`]. Provides cell access,
61/// term construction, dereferencing, and display.
62pub trait Heap: IndexMut<usize, Output = Cell> + Index<Range<usize>, Output = [Cell]> {
63    fn heap_push(&mut self, cell: Cell) -> usize;
64
65    fn heap_len(&self) -> usize;
66
67    fn truncate(&mut self, len: usize);
68
69    fn get_id(&self) -> usize {
70        0
71    }
72
73    fn _set_arg(&mut self, value: usize) -> usize {
74        //If no address provided set addr to current heap len
75        self.heap_push((Tag::Arg, value));
76        return self.heap_len() - 1;
77    }
78
79    fn set_const(&mut self, id: usize) -> usize {
80        let h = self.heap_len();
81        self.heap_push((Tag::Con, id));
82        h
83    }
84
85    fn set_ref(&mut self, ref_addr: Option<usize>) -> usize {
86        //If no address provided set addr to current heap len
87        let addr = match ref_addr {
88            Some(a) => a,
89            None => self.heap_len(),
90        };
91        self.heap_push((Tag::Ref, addr));
92        return self.heap_len() - 1;
93    }
94
95    fn deref_addr(&self, mut addr: usize) -> usize {
96        loop {
97            match self[addr] {
98                (Tag::Ref, pointer) if addr == pointer => return pointer,
99                (Tag::Ref, pointer) => addr = pointer,
100                // (Tag::Str, pointer) => return pointer,
101                _ => return addr,
102            }
103        }
104    }
105
106    /** Update address value of ref cells affected by binding
107     * @binding: List of (usize, usize) tuples representing heap indexes, left -> right
108     */
109    fn bind(&mut self, binding: &[(usize, usize)]) {
110        for (src, target) in binding {
111            // println!("{}", self.term_string(*src));
112            let pointer = &mut self[*src].1;
113            if *pointer != *src {
114                panic!("Tried to reset bound ref: {} \n Binding: {binding:?}", src)
115            }
116            *pointer = *target;
117        }
118    }
119
120    /** Reset Ref cells affected by binding to self references
121     * @binding: List of (usize, usize) tuples representing heap indexes, left -> right
122     */
123    fn unbind(&mut self, binding: &[(usize, usize)]) {
124        for (src, _target) in binding {
125            if let (Tag::Ref, pointer) = &mut self[*src] {
126                *pointer = *src;
127            }
128        }
129    }
130
131    /**Get the symbol id and arity of functor structure */
132    fn str_symbol_arity(&self, mut addr: usize) -> (usize, usize) {
133        addr = self.deref_addr(addr);
134        if let (Tag::Str, pointer) = self[addr] {
135            addr = pointer
136        }
137        if let (Tag::Func, arity) = self[addr] {
138            match self[self.deref_addr(addr + 1)] {
139                (Tag::Arg | Tag::Ref, _) => (0, arity - 1),
140                (Tag::Con, id) => (id, arity - 1),
141                _ => panic!("Functor of structure not constant of variable"),
142            }
143        } else if let (Tag::Con, symbol) = self[addr] {
144            (symbol, 0)
145        } else {
146            panic!(
147                "No str arity for {}, {:?}",
148                self.term_string(addr),
149                self[addr]
150            )
151        }
152    }
153
154    /**Collect all REF, cells in structure or referenced by structure
155     * If cell at addr is a reference return that cell  
156     */
157    fn term_vars(&self, mut addr: usize, args: bool) -> Vec<usize> {
158        addr = self.deref_addr(addr);
159        match self[addr].0 {
160            Tag::Arg if args => vec![addr],
161            Tag::Ref if !args => vec![addr],
162            Tag::Lis => [
163                self.term_vars(self[addr].1, args),
164                self.term_vars(self[addr].1 + 1, args),
165            ]
166            .concat(),
167            Tag::Func => self
168                .str_iterator(addr)
169                .map(|addr| self.term_vars(addr, args))
170                .collect::<Vec<Vec<usize>>>()
171                .concat(),
172            _ => vec![],
173        }
174    }
175
176    /** Given address to a str cell create an operator over the sub terms addresses, including functor/predicate */
177    fn str_iterator(&self, addr: usize) -> RangeInclusive<usize> {
178        addr + 1..=addr + self[addr].1
179    }
180
181    fn normalise_args(&mut self, addr: usize, args: &mut Vec<usize>) {
182        match self[addr] {
183            (Tag::Str, pointer) => self.normalise_args(pointer, args),
184            (Tag::Func, _) => {
185                for i in self.str_iterator(addr) {
186                    self.normalise_args(i, args)
187                }
188            }
189            (Tag::Tup, _) => unimplemented!("_normalise_args for Tup"),
190            (Tag::Set, _) => unimplemented!("_normalise_args for Set"),
191            (Tag::Lis, pointer) => {
192                self.normalise_args(pointer, args);
193                self.normalise_args(pointer + 1, args);
194            }
195            (Tag::Arg, value) => {
196                if let Some(pos) = args.iter().position(|i| value == *i) {
197                    self[addr].1 = pos;
198                } else {
199                    let pos = args.len();
200                    args.push(value);
201                    self[addr].1 = pos;
202                }
203            }
204            _ => (),
205        }
206    }
207
208    fn _copy_complex(&mut self, other: &impl Heap, mut addr: usize, update_addr: &mut usize) {
209        addr = other.deref_addr(addr);
210        match other[addr] {
211            (Tag::Str, pointer) => *update_addr = self._copy_term(other, pointer),
212            (Tag::Lis, _) => *update_addr = self._copy_term(other, addr),
213            _ => (),
214        }
215    }
216
217    fn _copy_simple(&mut self, other: &impl Heap, mut addr: usize, update_addr: &usize) {
218        addr = other.deref_addr(addr);
219        match other[addr] {
220            (Tag::Lis, _) => self.heap_push((Tag::Lis, *update_addr)),
221            (Tag::Str, _) => self.heap_push((Tag::Str, *update_addr)),
222            (Tag::Ref, _) => self.heap_push((Tag::Ref, self.heap_len())),
223            (_, _) => self.heap_push(other[addr]),
224        };
225    }
226
227    fn _copy_term(&mut self, other: &impl Heap, addr: usize) -> usize {
228        //Assume common static heap
229        let addr = other.deref_addr(addr);
230        match other[addr] {
231            (Tag::Str, mut pointer) => {
232                pointer = self._copy_term(other, pointer);
233                self.heap_push((Tag::Str, pointer));
234                self.heap_len() - 1
235            }
236            (Tag::Func, arity) => {
237                let mut update_addr: Vec<usize> = vec![0; arity];
238                for (i, a) in other.str_iterator(addr).enumerate() {
239                    self._copy_complex(other, a, &mut update_addr[i])
240                }
241                let h = self.heap_len();
242                self.heap_push((Tag::Func, arity));
243                for (i, a) in other.str_iterator(addr).enumerate() {
244                    self._copy_simple(other, a, &update_addr[i]);
245                }
246                h
247            }
248            (Tag::Lis, pointer) => {
249                let mut update_addr: Vec<usize> = vec![0; 2];
250                self._copy_complex(other, pointer, &mut update_addr[0]);
251                self._copy_complex(other, pointer + 1, &mut update_addr[1]);
252
253                let h = self.heap_len();
254                self._copy_simple(other, pointer, &mut update_addr[0]);
255                self._copy_simple(other, pointer + 1, &mut update_addr[1]);
256                h
257            }
258            (Tag::Tup, _len) => unimplemented!("_copy_term for Tup"),
259            (Tag::Set, _len) => unimplemented!("_copy_term for Set"),
260            (Tag::Ref, _pointer) => panic!(),
261            (Tag::Arg | Tag::Con | Tag::Int | Tag::Flt | Tag::Stri | Tag::ELis, _) => {
262                self.heap_push(other[addr]);
263                self.heap_len() - 1
264            }
265        }
266    }
267
268    /// Copy a term from `other` heap into `self`, tracking variable identity
269    /// via `ref_map`. Unbound Ref cells in `other` are mapped to fresh Ref
270    /// cells in `self`; the same source Ref always maps to the same target Ref.
271    /// Call with a shared `ref_map` across multiple terms to preserve variable
272    /// sharing (e.g. across literals in a clause).
273    fn copy_term_with_ref_map(
274        &mut self,
275        other: &impl Heap,
276        addr: usize,
277        ref_map: &mut HashMap<usize, usize>,
278    ) -> usize {
279        let addr = other.deref_addr(addr);
280        match other[addr] {
281            (Tag::Str, pointer) => {
282                let new_ptr = self.copy_term_with_ref_map(other, pointer, ref_map);
283                self.heap_push((Tag::Str, new_ptr));
284                self.heap_len() - 1
285            }
286            (Tag::Func | Tag::Tup | Tag::Set, length) => {
287                // Pre-pass: recursively copy complex sub-terms
288                let mut pre: Vec<Option<Cell>> = Vec::with_capacity(length);
289                for i in 1..=length {
290                    pre.push(self._copy_ref_map_complex(other, addr + i, ref_map));
291                }
292                // Lay down structure header + sub-terms
293                let h = self.heap_len();
294                self.heap_push((other[addr].0, length));
295                for (i, pre_cell) in pre.into_iter().enumerate() {
296                    match pre_cell {
297                        Some(cell) => {
298                            self.heap_push(cell);
299                        }
300                        None => self._copy_ref_map_simple(other, addr + 1 + i, ref_map),
301                    }
302                }
303                h
304            }
305            (Tag::Lis, pointer) => {
306                let head = self._copy_ref_map_complex(other, pointer, ref_map);
307                let tail = self._copy_ref_map_complex(other, pointer + 1, ref_map);
308                let h = self.heap_len();
309                match head {
310                    Some(cell) => {
311                        self.heap_push(cell);
312                    }
313                    None => self._copy_ref_map_simple(other, pointer, ref_map),
314                }
315                match tail {
316                    Some(cell) => {
317                        self.heap_push(cell);
318                    }
319                    None => self._copy_ref_map_simple(other, pointer + 1, ref_map),
320                }
321                h
322            }
323            (Tag::Ref, r) if r == addr => {
324                // Unbound ref — use or create mapping
325                if let Some(&mapped) = ref_map.get(&addr) {
326                    mapped
327                } else {
328                    let new_addr = self.heap_len();
329                    self.heap_push((Tag::Ref, new_addr));
330                    ref_map.insert(addr, new_addr);
331                    new_addr
332                }
333            }
334            (Tag::Arg | Tag::Con | Tag::Int | Tag::Flt | Tag::Stri | Tag::ELis, _) => {
335                self.heap_push(other[addr]);
336                self.heap_len() - 1
337            }
338            (tag, val) => panic!("copy_term_with_ref_map: unhandled ({tag:?}, {val})"),
339        }
340    }
341
342    /// Pre-pass helper for copy_term_with_ref_map: recursively copy complex
343    /// sub-terms and return the Cell to later insert, or None for simple cells.
344    fn _copy_ref_map_complex(
345        &mut self,
346        other: &impl Heap,
347        addr: usize,
348        ref_map: &mut HashMap<usize, usize>,
349    ) -> Option<Cell> {
350        let addr = other.deref_addr(addr);
351        match other[addr] {
352            (Tag::Func | Tag::Tup | Tag::Set, _) => {
353                Some((Tag::Str, self.copy_term_with_ref_map(other, addr, ref_map)))
354            }
355            (Tag::Str, ptr) => Some((Tag::Str, self.copy_term_with_ref_map(other, ptr, ref_map))),
356            (Tag::Lis, _) => Some((Tag::Lis, self.copy_term_with_ref_map(other, addr, ref_map))),
357            _ => None,
358        }
359    }
360
361    /// Post-pass helper for copy_term_with_ref_map: push a simple cell,
362    /// handling Ref identity via ref_map.
363    fn _copy_ref_map_simple(
364        &mut self,
365        other: &impl Heap,
366        addr: usize,
367        ref_map: &mut HashMap<usize, usize>,
368    ) {
369        let addr = other.deref_addr(addr);
370        match other[addr] {
371            (Tag::Ref, r) if r == addr => {
372                if let Some(&mapped) = ref_map.get(&addr) {
373                    self.heap_push((Tag::Ref, mapped));
374                } else {
375                    let new_addr = self.heap_len();
376                    self.heap_push((Tag::Ref, new_addr));
377                    ref_map.insert(addr, new_addr);
378                }
379            }
380            cell => {
381                self.heap_push(cell);
382            }
383        }
384    }
385
386    fn _term_equal(&self, mut addr1: usize, mut addr2: usize) -> bool {
387        addr1 = self.deref_addr(addr1);
388        addr2 = self.deref_addr(addr2);
389        match (self[addr1], self[addr2]) {
390            (EMPTY_LIS, EMPTY_LIS) => true,
391            (EMPTY_LIS, _) => false,
392            (_, EMPTY_LIS) => false,
393            ((Tag::Func, a1), (Tag::Func, a2)) if a1 == a2 => self
394                .str_iterator(addr1)
395                .zip(self.str_iterator(addr2))
396                .all(|(addr1, addr2)| self._term_equal(addr1, addr2)),
397            ((Tag::Lis, p1), (Tag::Lis, p2)) => {
398                self._term_equal(p1, p2) && self._term_equal(p1 + 1, p2 + 1)
399            }
400            ((Tag::Str, p1), (Tag::Str, p2)) => self._term_equal(p1, p2),
401            ((Tag::Tup, _len1), (Tag::Tup, _len2)) => unimplemented!("_term_equal for Tup"),
402            ((Tag::Set, _len1), (Tag::Set, _len2)) => unimplemented!("_term_equal for Set"),
403            ((Tag::Stri, i1), (Tag::Stri, i2)) => {
404                SymbolDB::get_string(i1) == SymbolDB::get_string(i2)
405            }
406
407            _ => self[addr1] == self[addr2],
408        }
409    }
410
411    fn contains_args(&self, mut addr: usize) -> bool {
412        addr = self.deref_addr(addr);
413        match self[addr] {
414            (Tag::Arg, _) => true,
415            (Tag::Lis, ptr) => self.contains_args(ptr) || self.contains_args(ptr + 1),
416            (Tag::Str, ptr) => self.contains_args(ptr),
417            (Tag::Func | Tag::Set | Tag::Tup, length) => {
418                (addr + 1..addr + 1 + length).any(|addr| self.contains_args(addr))
419            }
420            _ => false,
421        }
422    }
423
424    /**Debug function for printing formatted string of current heap state */
425    fn _print_heap(&self) {
426        let w = 6;
427        for i in 0..self.heap_len() {
428            let (tag, value) = self[i];
429            match tag {
430                Tag::Con => {
431                    println!("[{i:3}]|{tag:w$}|{:w$}|", SymbolDB::get_const(value))
432                }
433                Tag::Lis => {
434                    if value == _CON_PTR {
435                        println!("[{i:3}]|{tag:w$}|{:w$}|", "[]")
436                    } else {
437                        println!("[{i:3}]|{tag:w$}|{value:w$}|")
438                    }
439                }
440                Tag::Ref | Tag::Arg => {
441                    println!("[{i:3}]|{tag:w$?}|{value:w$}|:({})", self.term_string(i))
442                }
443                Tag::Int => {
444                    let value: isize = unsafe { mem::transmute_copy(&value) };
445                    println!("[{i:3}]|{tag:w$?}|{value:w$}|")
446                }
447                Tag::Flt => {
448                    let value: fsize = unsafe { mem::transmute_copy(&value) };
449                    println!("[{i:3}]|{tag:w$?}|{value:w$}|")
450                }
451                Tag::Tup => unimplemented!("_print_heap for Tup"),
452                Tag::Set => unimplemented!("_print_heap for Set"),
453                Tag::Stri => unimplemented!("_print_heap for Stri"),
454                _ => println!("[{i:3}]|{tag:w$?}|{value:w$}|"),
455            };
456            println!("{:-<w$}--------{:-<w$}", "", "");
457        }
458    }
459
460    /**Create a string from a list */
461    fn list_string(&self, addr: usize) -> String {
462        let mut buffer = "[".to_string();
463        let mut pointer = self[addr].1;
464
465        loop {
466            buffer += &self.term_string(pointer);
467
468            match self[pointer + 1].0 {
469                Tag::Lis => {
470                    buffer += ",";
471                    pointer = self[pointer + 1].1
472                }
473                Tag::ELis => break,
474                _ => {
475                    buffer += "|";
476                    buffer += &self.term_string(pointer + 1);
477                    break;
478                }
479            }
480        }
481        buffer += "]";
482        buffer
483    }
484
485    /**Create a string for a functor structure */
486    fn func_string(&self, addr: usize) -> String {
487        let mut buf = "".to_string();
488        let mut first = true;
489        for i in self.str_iterator(addr) {
490            buf += &self.term_string(i);
491            buf += if first { "(" } else { "," };
492            if first {
493                first = false
494            }
495        }
496        buf.pop();
497        buf += ")";
498        buf
499    }
500
501    /**Create a string for a tuple*/
502    fn tuple_string(&self, addr: usize) -> String {
503        let mut buf = String::from("(");
504        for i in 1..self[addr].1 + 1 {
505            buf += &self.term_string(addr + i);
506            buf += ",";
507        }
508        buf.pop();
509        buf += ")";
510        buf
511    }
512
513    /**Create a string for a set*/
514    fn set_string(&self, addr: usize) -> String {
515        let mut buf = String::from("{");
516        for i in 1..self[addr].1 + 1 {
517            buf += &self.term_string(addr + i);
518            buf += ",";
519        }
520        buf.pop();
521        buf += "}";
522        buf
523    }
524
525    /** Create String to represent cell, can be recursively used to format complex structures or list */
526    fn term_string(&self, addr: usize) -> String {
527        // println!("[{addr}]:{:?}", self[addr]);
528        let addr = self.deref_addr(addr);
529        match self[addr].0 {
530            Tag::Con => SymbolDB::get_const(self[addr].1).to_string(),
531            Tag::Func => self.func_string(addr),
532            Tag::Lis => self.list_string(addr),
533            Tag::ELis => "[]".into(),
534            Tag::Arg => match SymbolDB::get_var(addr, self.get_id()) {
535                Some(symbol) => symbol.to_string(),
536                None => format!("Arg_{}", self[addr].1),
537            },
538            Tag::Ref => match SymbolDB::get_var(self.deref_addr(addr), self.get_id()).to_owned() {
539                Some(symbol) => symbol.to_string(),
540                None => format!("Ref_{}", self[addr].1),
541            },
542            Tag::Int => {
543                let value: isize = unsafe { mem::transmute_copy(&self[addr].1) };
544                format!("{value}")
545            }
546            Tag::Flt => {
547                let value: fsize = unsafe { mem::transmute_copy(&self[addr].1) };
548                format!("{value}")
549            }
550            Tag::Tup => self.tuple_string(addr),
551            Tag::Set => self.set_string(addr),
552            Tag::Str => self.term_string(self[addr].1),
553            Tag::Stri => SymbolDB::get_string(self[addr].1).to_string(),
554        }
555    }
556}
557
558impl Heap for Vec<Cell> {
559    fn heap_push(&mut self, cell: Cell) -> usize {
560        let i = self.len();
561        self.push(cell);
562        i
563    }
564
565    fn heap_len(&self) -> usize {
566        self.len()
567    }
568
569    fn truncate(&mut self, len: usize) {
570        self.resize(len, (Tag::Ref, 0));
571    }
572}
573
574#[cfg(test)]
575mod tests {
576    use crate::heap::query_heap::QueryHeap;
577
578    use super::{
579        super::symbol_db::SymbolDB,
580        {Cell, Heap, Tag, EMPTY_LIS},
581    };
582
583    #[test]
584    fn encode_argument_variable() {
585        let mut heap = QueryHeap::new(&[], None);
586
587        let addr1 = heap._set_arg(0);
588        let addr2 = heap._set_arg(1);
589
590        assert_eq!(heap.term_string(addr1), "Arg_0");
591        assert_eq!(heap.term_string(addr2), "Arg_1");
592    }
593
594    #[test]
595    fn encode_ref_variable() {
596        let mut heap = QueryHeap::new(&[], None);
597
598        let addr1 = heap.set_ref(None);
599        let addr2 = heap.set_ref(Some(addr1));
600
601        assert_eq!(heap.term_string(addr1), "Ref_0");
602        assert_eq!(heap.term_string(addr2), "Ref_0");
603    }
604
605    #[test]
606    fn encode_constant() {
607        let mut heap = QueryHeap::new(&[], None);
608
609        let a = SymbolDB::set_const("a".into());
610        let b = SymbolDB::set_const("b".into());
611
612        let addr1 = heap.set_const(a);
613        let addr2 = heap.set_const(b);
614
615        assert_eq!(heap.term_string(addr1), "a");
616        assert_eq!(heap.term_string(addr2), "b");
617    }
618
619    #[test]
620    fn encode_functor() {
621        let p = SymbolDB::set_const("p".into());
622        let f = SymbolDB::set_const("f".into());
623        let a = SymbolDB::set_const("a".into());
624
625        let mut heap = QueryHeap::new(&[], None);
626        heap.cells.extend(vec![
627            (Tag::Str, 1),
628            (Tag::Func, 3),
629            (Tag::Con, p),
630            (Tag::Arg, 0),
631            (Tag::Con, a),
632        ]);
633
634        assert_eq!(heap.term_string(0), "p(Arg_0,a)");
635
636        let mut heap = QueryHeap::new(&[], None);
637        heap.cells.extend(vec![
638            (Tag::Str, 1),
639            (Tag::Func, 3),
640            (Tag::Con, p),
641            (Tag::Str, 5),
642            (Tag::Con, a),
643            (Tag::Func, 2),
644            (Tag::Con, f),
645            (Tag::Ref, 7),
646        ]);
647        assert_eq!(heap.term_string(0), "p(f(Ref_7),a)");
648
649        let mut heap = QueryHeap::new(&[], None);
650        heap.cells.extend(vec![
651            (Tag::Str, 1),
652            (Tag::Func, 3),
653            (Tag::Con, p),
654            (Tag::Str, 5),
655            (Tag::Con, a),
656            (Tag::Tup, 2),
657            (Tag::Con, f),
658            (Tag::Ref, 7),
659        ]);
660        assert_eq!(heap.term_string(0), "p((f,Ref_7),a)");
661
662        let mut heap = QueryHeap::new(&[], None);
663        heap.cells.extend(vec![
664            (Tag::Str, 1),
665            (Tag::Func, 3),
666            (Tag::Con, p),
667            (Tag::Str, 5),
668            (Tag::Con, a),
669            (Tag::Set, 2),
670            (Tag::Con, f),
671            (Tag::Ref, 7),
672        ]);
673
674        assert_eq!(heap.term_string(0), "p({f,Ref_7},a)");
675
676        let mut heap = QueryHeap::new(&[], None);
677        heap.cells.extend(vec![
678            (Tag::Str, 1),
679            (Tag::Func, 3),
680            (Tag::Con, p),
681            (Tag::Lis, 5),
682            (Tag::Con, a),
683            (Tag::Con, f),
684            (Tag::Lis, 7),
685            (Tag::Ref, 7),
686            EMPTY_LIS,
687        ]);
688        assert_eq!(heap.term_string(0), "p([f,Ref_7],a)");
689    }
690
691    #[test]
692    fn encode_tuple() {
693        let f = SymbolDB::set_const("f".into());
694        let a = SymbolDB::set_const("a".into());
695
696        let mut heap = QueryHeap::new(&[], None);
697        heap.cells.extend(vec![
698            (Tag::Str, 1),
699            (Tag::Tup, 2),
700            (Tag::Arg, 0),
701            (Tag::Con, a),
702        ]);
703        assert_eq!(heap.term_string(0), "(Arg_0,a)");
704
705        let mut heap = QueryHeap::new(&[], None);
706        heap.cells.extend(vec![
707            (Tag::Str, 1),
708            (Tag::Tup, 2),
709            (Tag::Str, 4),
710            (Tag::Con, a),
711            (Tag::Func, 2),
712            (Tag::Con, f),
713            (Tag::Ref, 6),
714        ]);
715        assert_eq!(heap.term_string(0), "(f(Ref_6),a)");
716
717        let mut heap = QueryHeap::new(&[], None);
718        heap.cells.extend(vec![
719            (Tag::Str, 1),
720            (Tag::Tup, 2),
721            (Tag::Str, 4),
722            (Tag::Con, a),
723            (Tag::Tup, 2),
724            (Tag::Con, f),
725            (Tag::Ref, 6),
726        ]);
727        assert_eq!(heap.term_string(0), "((f,Ref_6),a)");
728
729        let mut heap = QueryHeap::new(&[], None);
730        heap.cells.extend(vec![
731            (Tag::Str, 1),
732            (Tag::Tup, 2),
733            (Tag::Str, 4),
734            (Tag::Con, a),
735            (Tag::Set, 2),
736            (Tag::Con, f),
737            (Tag::Ref, 6),
738        ]);
739        assert_eq!(heap.term_string(0), "({f,Ref_6},a)");
740
741        let mut heap = QueryHeap::new(&[], None);
742        heap.cells.extend(vec![
743            (Tag::Str, 1),
744            (Tag::Tup, 2),
745            (Tag::Lis, 4),
746            (Tag::Con, a),
747            (Tag::Con, f),
748            (Tag::Lis, 6),
749            (Tag::Ref, 6),
750            EMPTY_LIS,
751        ]);
752        assert_eq!(heap.term_string(0), "([f,Ref_6],a)");
753    }
754
755    #[test]
756    fn encode_list() {
757        let f = SymbolDB::set_const("f".into());
758        let a = SymbolDB::set_const("a".into());
759
760        let mut heap = QueryHeap::new(&[], None);
761        heap.cells.extend(vec![
762            (Tag::Lis, 1),
763            (Tag::Arg, 0),
764            (Tag::Lis, 3),
765            (Tag::Con, a),
766            EMPTY_LIS,
767        ]);
768        assert_eq!(heap.term_string(0), "[Arg_0,a]");
769
770        let mut heap = QueryHeap::new(&[], None);
771        heap.cells.extend(vec![
772            (Tag::Lis, 1),
773            (Tag::Str, 5),
774            (Tag::Lis, 3),
775            (Tag::Con, a),
776            EMPTY_LIS,
777            (Tag::Func, 2),
778            (Tag::Con, f),
779            (Tag::Ref, 7),
780        ]);
781        assert_eq!(heap.term_string(0), "[f(Ref_7),a]");
782
783        let mut heap = QueryHeap::new(&[], None);
784        heap.cells.extend(vec![
785            (Tag::Lis, 1),
786            (Tag::Str, 5),
787            (Tag::Lis, 3),
788            (Tag::Con, a),
789            EMPTY_LIS,
790            (Tag::Tup, 2),
791            (Tag::Con, f),
792            (Tag::Ref, 7),
793        ]);
794        assert_eq!(heap.term_string(0), "[(f,Ref_7),a]");
795
796        let mut heap = QueryHeap::new(&[], None);
797        heap.cells.extend(vec![
798            (Tag::Lis, 1),
799            (Tag::Str, 5),
800            (Tag::Lis, 3),
801            (Tag::Con, a),
802            EMPTY_LIS,
803            (Tag::Set, 2),
804            (Tag::Con, f),
805            (Tag::Ref, 7),
806        ]);
807        assert_eq!(heap.term_string(0), "[{f,Ref_7},a]");
808
809        let mut heap = QueryHeap::new(&[], None);
810        heap.cells.extend(vec![
811            (Tag::Lis, 1),
812            (Tag::Lis, 5),
813            (Tag::Lis, 3),
814            (Tag::Con, a),
815            EMPTY_LIS,
816            (Tag::Con, f),
817            (Tag::Lis, 7),
818            (Tag::Ref, 7),
819            EMPTY_LIS,
820        ]);
821        assert_eq!(heap.term_string(0), "[[f,Ref_7],a]");
822    }
823
824    #[test]
825    fn encode_set() {
826        let f = SymbolDB::set_const("f".into());
827        let a = SymbolDB::set_const("a".into());
828
829        let mut heap = QueryHeap::new(&[], None);
830        heap.cells.extend(vec![
831            (Tag::Str, 1),
832            (Tag::Set, 2),
833            (Tag::Arg, 0),
834            (Tag::Con, a),
835        ]);
836        assert_eq!(heap.term_string(0), "{Arg_0,a}");
837
838        let mut heap = QueryHeap::new(&[], None);
839        heap.cells.extend(vec![
840            (Tag::Str, 1),
841            (Tag::Set, 2),
842            (Tag::Str, 4),
843            (Tag::Con, a),
844            (Tag::Func, 2),
845            (Tag::Con, f),
846            (Tag::Ref, 6),
847        ]);
848        assert_eq!(heap.term_string(0), "{f(Ref_6),a}");
849
850        let mut heap = QueryHeap::new(&[], None);
851        heap.cells.extend(vec![
852            (Tag::Str, 1),
853            (Tag::Set, 2),
854            (Tag::Str, 4),
855            (Tag::Con, a),
856            (Tag::Tup, 2),
857            (Tag::Con, f),
858            (Tag::Ref, 6),
859        ]);
860        assert_eq!(heap.term_string(0), "{(f,Ref_6),a}");
861
862        let mut heap = QueryHeap::new(&[], None);
863        heap.cells.extend(vec![
864            (Tag::Str, 1),
865            (Tag::Set, 2),
866            (Tag::Str, 4),
867            (Tag::Con, a),
868            (Tag::Set, 2),
869            (Tag::Con, f),
870            (Tag::Ref, 6),
871        ]);
872        assert_eq!(heap.term_string(0), "{{f,Ref_6},a}");
873
874        let mut heap = QueryHeap::new(&[], None);
875        heap.cells.extend(vec![
876            (Tag::Str, 1),
877            (Tag::Set, 2),
878            (Tag::Lis, 4),
879            (Tag::Con, a),
880            (Tag::Con, f),
881            (Tag::Lis, 6),
882            (Tag::Ref, 6),
883            EMPTY_LIS,
884        ]);
885        assert_eq!(heap.term_string(0), "{[f,Ref_6],a}");
886    }
887
888    #[test]
889    fn dereference() {
890        let f = SymbolDB::set_const("f".into());
891        let a = SymbolDB::set_const("a".into());
892
893        let mut heap = QueryHeap::new(&[], None);
894        heap.cells.extend(vec![
895            (Tag::Ref, 1),
896            (Tag::Ref, 2),
897            (Tag::Ref, 3),
898            (Tag::Ref, 3),
899        ]);
900        assert_eq!(heap.term_string(0), "Ref_3");
901
902        let mut heap = QueryHeap::new(&[], None);
903        heap.cells.extend(vec![
904            (Tag::Ref, 1),
905            (Tag::Ref, 2),
906            (Tag::Ref, 3),
907            (Tag::Arg, 0),
908        ]);
909        assert_eq!(heap.term_string(0), "Arg_0");
910
911        let mut heap = QueryHeap::new(&[], None);
912        heap.cells.extend(vec![
913            (Tag::Ref, 1),
914            (Tag::Ref, 2),
915            (Tag::Ref, 3),
916            (Tag::Con, a),
917        ]);
918        assert_eq!(heap.term_string(0), "a");
919
920        let mut heap = QueryHeap::new(&[], None);
921        heap.cells.extend(vec![
922            (Tag::Ref, 1),
923            (Tag::Ref, 2),
924            (Tag::Ref, 3),
925            (Tag::Str, 4),
926            (Tag::Func, 3),
927            (Tag::Con, f),
928            (Tag::Con, a),
929            (Tag::Ref, 7),
930        ]);
931        assert_eq!(heap.term_string(0), "f(a,Ref_7)");
932
933        let mut heap = QueryHeap::new(&[], None);
934        heap.cells.extend(vec![
935            (Tag::Ref, 1),
936            (Tag::Ref, 2),
937            (Tag::Ref, 3),
938            (Tag::Str, 4),
939            (Tag::Tup, 2),
940            (Tag::Con, a),
941            (Tag::Ref, 6),
942        ]);
943        assert_eq!(heap.term_string(0), "(a,Ref_6)");
944
945        let mut heap = QueryHeap::new(&[], None);
946        heap.cells.extend(vec![
947            (Tag::Ref, 1),
948            (Tag::Ref, 2),
949            (Tag::Ref, 3),
950            (Tag::Str, 4),
951            (Tag::Set, 2),
952            (Tag::Con, a),
953            (Tag::Ref, 6),
954        ]);
955        assert_eq!(heap.term_string(0), "{a,Ref_6}");
956
957        let mut heap = QueryHeap::new(&[], None);
958        heap.cells.extend(vec![
959            (Tag::Ref, 1),
960            (Tag::Ref, 2),
961            (Tag::Ref, 3),
962            (Tag::Lis, 4),
963            (Tag::Con, a),
964            (Tag::Lis, 6),
965            (Tag::Ref, 6),
966            EMPTY_LIS,
967        ]);
968        assert_eq!(heap.term_string(0), "[a,Ref_6]");
969    }
970}
prolog2/heap/heap.rs

prolog2/heap/
heap.rs
