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: &[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) => self[addr].1 = args.iter().position(|i| value == *i).unwrap(),
196            _ => (),
197        }
198    }
199
200    fn _copy_complex(&mut self, other: &impl Heap, mut addr: usize, update_addr: &mut usize) {
201        addr = other.deref_addr(addr);
202        match other[addr] {
203            (Tag::Str, pointer) => *update_addr = self._copy_term(other, pointer),
204            (Tag::Lis, _) => *update_addr = self._copy_term(other, addr),
205            _ => (),
206        }
207    }
208
209    fn _copy_simple(&mut self, other: &impl Heap, mut addr: usize, update_addr: &usize) {
210        addr = other.deref_addr(addr);
211        match other[addr] {
212            (Tag::Lis, _) => self.heap_push((Tag::Lis, *update_addr)),
213            (Tag::Str, _) => self.heap_push((Tag::Str, *update_addr)),
214            (Tag::Ref, _) => self.heap_push((Tag::Ref, self.heap_len())),
215            (_, _) => self.heap_push(other[addr]),
216        };
217    }
218
219    fn _copy_term(&mut self, other: &impl Heap, addr: usize) -> usize {
220        //Assume common static heap
221        let addr = other.deref_addr(addr);
222        match other[addr] {
223            (Tag::Str, mut pointer) => {
224                pointer = self._copy_term(other, pointer);
225                self.heap_push((Tag::Str, pointer));
226                self.heap_len() - 1
227            }
228            (Tag::Func, arity) => {
229                let mut update_addr: Vec<usize> = vec![0; arity];
230                for (i, a) in other.str_iterator(addr).enumerate() {
231                    self._copy_complex(other, a, &mut update_addr[i])
232                }
233                let h = self.heap_len();
234                self.heap_push((Tag::Func, arity));
235                for (i, a) in other.str_iterator(addr).enumerate() {
236                    self._copy_simple(other, a, &update_addr[i]);
237                }
238                h
239            }
240            (Tag::Lis, pointer) => {
241                let mut update_addr: Vec<usize> = vec![0; 2];
242                self._copy_complex(other, pointer, &mut update_addr[0]);
243                self._copy_complex(other, pointer + 1, &mut update_addr[1]);
244
245                let h = self.heap_len();
246                self._copy_simple(other, pointer, &mut update_addr[0]);
247                self._copy_simple(other, pointer + 1, &mut update_addr[1]);
248                h
249            }
250            (Tag::Tup, _len) => unimplemented!("_copy_term for Tup"),
251            (Tag::Set, _len) => unimplemented!("_copy_term for Set"),
252            (Tag::Ref, _pointer) => panic!(),
253            (Tag::Arg | Tag::Con | Tag::Int | Tag::Flt | Tag::Stri | Tag::ELis, _) => {
254                self.heap_push(other[addr]);
255                self.heap_len() - 1
256            }
257        }
258    }
259
260    /// Copy a term from `other` heap into `self`, tracking variable identity
261    /// via `ref_map`. Unbound Ref cells in `other` are mapped to fresh Ref
262    /// cells in `self`; the same source Ref always maps to the same target Ref.
263    /// Call with a shared `ref_map` across multiple terms to preserve variable
264    /// sharing (e.g. across literals in a clause).
265    fn copy_term_with_ref_map(
266        &mut self,
267        other: &impl Heap,
268        addr: usize,
269        ref_map: &mut HashMap<usize, usize>,
270    ) -> usize {
271        let addr = other.deref_addr(addr);
272        match other[addr] {
273            (Tag::Str, pointer) => {
274                let new_ptr = self.copy_term_with_ref_map(other, pointer, ref_map);
275                self.heap_push((Tag::Str, new_ptr));
276                self.heap_len() - 1
277            }
278            (Tag::Func | Tag::Tup | Tag::Set, length) => {
279                // Pre-pass: recursively copy complex sub-terms
280                let mut pre: Vec<Option<Cell>> = Vec::with_capacity(length);
281                for i in 1..=length {
282                    pre.push(self._copy_ref_map_complex(other, addr + i, ref_map));
283                }
284                // Lay down structure header + sub-terms
285                let h = self.heap_len();
286                self.heap_push((other[addr].0, length));
287                for (i, pre_cell) in pre.into_iter().enumerate() {
288                    match pre_cell {
289                        Some(cell) => { self.heap_push(cell); }
290                        None => self._copy_ref_map_simple(other, addr + 1 + i, ref_map),
291                    }
292                }
293                h
294            }
295            (Tag::Lis, pointer) => {
296                let head = self._copy_ref_map_complex(other, pointer, ref_map);
297                let tail = self._copy_ref_map_complex(other, pointer + 1, ref_map);
298                let h = self.heap_len();
299                match head {
300                    Some(cell) => { self.heap_push(cell); }
301                    None => self._copy_ref_map_simple(other, pointer, ref_map),
302                }
303                match tail {
304                    Some(cell) => { self.heap_push(cell); }
305                    None => self._copy_ref_map_simple(other, pointer + 1, ref_map),
306                }
307                h
308            }
309            (Tag::Ref, r) if r == addr => {
310                // Unbound ref — use or create mapping
311                if let Some(&mapped) = ref_map.get(&addr) {
312                    mapped
313                } else {
314                    let new_addr = self.heap_len();
315                    self.heap_push((Tag::Ref, new_addr));
316                    ref_map.insert(addr, new_addr);
317                    new_addr
318                }
319            }
320            (Tag::Arg | Tag::Con | Tag::Int | Tag::Flt | Tag::Stri | Tag::ELis, _) => {
321                self.heap_push(other[addr]);
322                self.heap_len() - 1
323            }
324            (tag, val) => panic!("copy_term_with_ref_map: unhandled ({tag:?}, {val})"),
325        }
326    }
327
328    /// Pre-pass helper for copy_term_with_ref_map: recursively copy complex
329    /// sub-terms and return the Cell to later insert, or None for simple cells.
330    fn _copy_ref_map_complex(
331        &mut self,
332        other: &impl Heap,
333        addr: usize,
334        ref_map: &mut HashMap<usize, usize>,
335    ) -> Option<Cell> {
336        let addr = other.deref_addr(addr);
337        match other[addr] {
338            (Tag::Func | Tag::Tup | Tag::Set, _) => {
339                Some((Tag::Str, self.copy_term_with_ref_map(other, addr, ref_map)))
340            }
341            (Tag::Str, ptr) => {
342                Some((Tag::Str, self.copy_term_with_ref_map(other, ptr, ref_map)))
343            }
344            (Tag::Lis, _) => {
345                Some((Tag::Lis, self.copy_term_with_ref_map(other, addr, ref_map)))
346            }
347            _ => None,
348        }
349    }
350
351    /// Post-pass helper for copy_term_with_ref_map: push a simple cell,
352    /// handling Ref identity via ref_map.
353    fn _copy_ref_map_simple(
354        &mut self,
355        other: &impl Heap,
356        addr: usize,
357        ref_map: &mut HashMap<usize, usize>,
358    ) {
359        let addr = other.deref_addr(addr);
360        match other[addr] {
361            (Tag::Ref, r) if r == addr => {
362                if let Some(&mapped) = ref_map.get(&addr) {
363                    self.heap_push((Tag::Ref, mapped));
364                } else {
365                    let new_addr = self.heap_len();
366                    self.heap_push((Tag::Ref, new_addr));
367                    ref_map.insert(addr, new_addr);
368                }
369            }
370            cell => { self.heap_push(cell); }
371        }
372    }
373
374    fn _term_equal(&self, mut addr1: usize, mut addr2: usize) -> bool {
375        addr1 = self.deref_addr(addr1);
376        addr2 = self.deref_addr(addr2);
377        match (self[addr1], self[addr2]) {
378            (EMPTY_LIS, EMPTY_LIS) => true,
379            (EMPTY_LIS, _) => false,
380            (_, EMPTY_LIS) => false,
381            ((Tag::Func, a1), (Tag::Func, a2)) if a1 == a2 => self
382                .str_iterator(addr1)
383                .zip(self.str_iterator(addr2))
384                .all(|(addr1, addr2)| self._term_equal(addr1, addr2)),
385            ((Tag::Lis, p1), (Tag::Lis, p2)) => {
386                self._term_equal(p1, p2) && self._term_equal(p1 + 1, p2 + 1)
387            }
388            ((Tag::Str, p1), (Tag::Str, p2)) => self._term_equal(p1, p2),
389            ((Tag::Tup, _len1), (Tag::Tup, _len2)) => unimplemented!("_term_equal for Tup"),
390            ((Tag::Set, _len1), (Tag::Set, _len2)) => unimplemented!("_term_equal for Set"),
391            ((Tag::Stri, i1), (Tag::Stri, i2)) => {
392                SymbolDB::get_string(i1) == SymbolDB::get_string(i2)
393            }
394
395            _ => self[addr1] == self[addr2],
396        }
397    }
398
399    fn contains_args(&self, mut addr: usize) -> bool {
400        addr = self.deref_addr(addr);
401        match self[addr] {
402            (Tag::Arg, _) => true,
403            (Tag::Lis, ptr) => self.contains_args(ptr) || self.contains_args(ptr + 1),
404            (Tag::Str, ptr) => self.contains_args(ptr),
405            (Tag::Func | Tag::Set | Tag::Tup, length) => {
406                (addr + 1..addr + 1 + length).any(|addr| self.contains_args(addr))
407            }
408            _ => false,
409        }
410    }
411
412    /**Debug function for printing formatted string of current heap state */
413    fn _print_heap(&self) {
414        let w = 6;
415        for i in 0..self.heap_len() {
416            let (tag, value) = self[i];
417            match tag {
418                Tag::Con => {
419                    println!("[{i:3}]|{tag:w$}|{:w$}|", SymbolDB::get_const(value))
420                }
421                Tag::Lis => {
422                    if value == _CON_PTR {
423                        println!("[{i:3}]|{tag:w$}|{:w$}|", "[]")
424                    } else {
425                        println!("[{i:3}]|{tag:w$}|{value:w$}|")
426                    }
427                }
428                Tag::Ref | Tag::Arg => {
429                    println!("[{i:3}]|{tag:w$?}|{value:w$}|:({})", self.term_string(i))
430                }
431                Tag::Int => {
432                    let value: isize = unsafe { mem::transmute_copy(&value) };
433                    println!("[{i:3}]|{tag:w$?}|{value:w$}|")
434                }
435                Tag::Flt => {
436                    let value: fsize = unsafe { mem::transmute_copy(&value) };
437                    println!("[{i:3}]|{tag:w$?}|{value:w$}|")
438                }
439                Tag::Tup => unimplemented!("_print_heap for Tup"),
440                Tag::Set => unimplemented!("_print_heap for Set"),
441                Tag::Stri => unimplemented!("_print_heap for Stri"),
442                _ => println!("[{i:3}]|{tag:w$?}|{value:w$}|"),
443            };
444            println!("{:-<w$}--------{:-<w$}", "", "");
445        }
446    }
447
448    /**Create a string from a list */
449    fn list_string(&self, addr: usize) -> String {
450        let mut buffer = "[".to_string();
451        let mut pointer = self[addr].1;
452
453        loop {
454            buffer += &self.term_string(pointer);
455
456            match self[pointer + 1].0 {
457                Tag::Lis => {
458                    buffer += ",";
459                    pointer = self[pointer + 1].1
460                }
461                Tag::ELis => break,
462                _ => {
463                    buffer += "|";
464                    buffer += &self.term_string(pointer + 1);
465                    break;
466                }
467            }
468        }
469        buffer += "]";
470        buffer
471    }
472
473    /**Create a string for a functor structure */
474    fn func_string(&self, addr: usize) -> String {
475        let mut buf = "".to_string();
476        let mut first = true;
477        for i in self.str_iterator(addr) {
478            buf += &self.term_string(i);
479            buf += if first { "(" } else { "," };
480            if first {
481                first = false
482            }
483        }
484        buf.pop();
485        buf += ")";
486        buf
487    }
488
489    /**Create a string for a tuple*/
490    fn tuple_string(&self, addr: usize) -> String {
491        let mut buf = String::from("(");
492        for i in 1..self[addr].1 + 1 {
493            buf += &self.term_string(addr + i);
494            buf += ",";
495        }
496        buf.pop();
497        buf += ")";
498        buf
499    }
500
501    /**Create a string for a set*/
502    fn set_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 String to represent cell, can be recursively used to format complex structures or list */
514    fn term_string(&self, addr: usize) -> String {
515        // println!("[{addr}]:{:?}", self[addr]);
516        let addr = self.deref_addr(addr);
517        match self[addr].0 {
518            Tag::Con => SymbolDB::get_const(self[addr].1).to_string(),
519            Tag::Func => self.func_string(addr),
520            Tag::Lis => self.list_string(addr),
521            Tag::ELis => "[]".into(),
522            Tag::Arg => match SymbolDB::get_var(addr, self.get_id()) {
523                Some(symbol) => symbol.to_string(),
524                None => format!("Arg_{}", self[addr].1),
525            },
526            Tag::Ref => match SymbolDB::get_var(self.deref_addr(addr), self.get_id()).to_owned() {
527                Some(symbol) => symbol.to_string(),
528                None => format!("Ref_{}", self[addr].1),
529            },
530            Tag::Int => {
531                let value: isize = unsafe { mem::transmute_copy(&self[addr].1) };
532                format!("{value}")
533            }
534            Tag::Flt => {
535                let value: fsize = unsafe { mem::transmute_copy(&self[addr].1) };
536                format!("{value}")
537            }
538            Tag::Tup => self.tuple_string(addr),
539            Tag::Set => self.set_string(addr),
540            Tag::Str => self.term_string(self[addr].1),
541            Tag::Stri => SymbolDB::get_string(self[addr].1).to_string(),
542        }
543    }
544}
545
546impl Heap for Vec<Cell> {
547    fn heap_push(&mut self, cell: Cell) -> usize {
548        let i = self.len();
549        self.push(cell);
550        i
551    }
552
553    fn heap_len(&self) -> usize {
554        self.len()
555    }
556    
557    fn truncate(&mut self, len: usize) {
558        self.resize(len, (Tag::Ref,0));
559    }
560}
561
562#[cfg(test)]
563mod tests {
564    use std::sync::Arc;
565
566    use crate::heap::query_heap::QueryHeap;
567
568    use super::{
569        super::symbol_db::SymbolDB,
570        {Cell, Heap, Tag, EMPTY_LIS},
571    };
572
573    #[test]
574    fn encode_argument_variable() {
575        let prog_cells = Arc::new(Vec::<Cell>::new());
576        let mut heap = QueryHeap::new(prog_cells, None);
577
578        let addr1 = heap._set_arg(0);
579        let addr2 = heap._set_arg(1);
580
581        assert_eq!(heap.term_string(addr1), "Arg_0");
582        assert_eq!(heap.term_string(addr2), "Arg_1");
583    }
584
585    #[test]
586    fn encode_ref_variable() {
587        let prog_cells = Arc::new(Vec::<Cell>::new());
588        let mut heap = QueryHeap::new(prog_cells, None);
589
590        let addr1 = heap.set_ref(None);
591        let addr2 = heap.set_ref(Some(addr1));
592
593        assert_eq!(heap.term_string(addr1), "Ref_0");
594        assert_eq!(heap.term_string(addr2), "Ref_0");
595    }
596
597    #[test]
598    fn encode_constant() {
599        let prog_cells = Arc::new(Vec::<Cell>::new());
600        let mut heap = QueryHeap::new(prog_cells, None);
601
602        let a = SymbolDB::set_const("a".into());
603        let b = SymbolDB::set_const("b".into());
604
605        let addr1 = heap.set_const(a);
606        let addr2 = heap.set_const(b);
607
608        assert_eq!(heap.term_string(addr1), "a");
609        assert_eq!(heap.term_string(addr2), "b");
610    }
611
612    #[test]
613    fn encode_functor() {
614        let p = SymbolDB::set_const("p".into());
615        let f = SymbolDB::set_const("f".into());
616        let a = SymbolDB::set_const("a".into());
617
618        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
619        heap.cells.extend(vec![
620            (Tag::Str, 1),
621            (Tag::Func, 3),
622            (Tag::Con, p),
623            (Tag::Arg, 0),
624            (Tag::Con, a),
625        ]);
626
627        assert_eq!(heap.term_string(0), "p(Arg_0,a)");
628
629        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
630        heap.cells.extend(vec![
631            (Tag::Str, 1),
632            (Tag::Func, 3),
633            (Tag::Con, p),
634            (Tag::Str, 5),
635            (Tag::Con, a),
636            (Tag::Func, 2),
637            (Tag::Con, f),
638            (Tag::Ref, 7),
639        ]);
640        assert_eq!(heap.term_string(0), "p(f(Ref_7),a)");
641
642        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
643        heap.cells.extend(vec![
644            (Tag::Str, 1),
645            (Tag::Func, 3),
646            (Tag::Con, p),
647            (Tag::Str, 5),
648            (Tag::Con, a),
649            (Tag::Tup, 2),
650            (Tag::Con, f),
651            (Tag::Ref, 7),
652        ]);
653        assert_eq!(heap.term_string(0), "p((f,Ref_7),a)");
654
655        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
656        heap.cells.extend(vec![
657            (Tag::Str, 1),
658            (Tag::Func, 3),
659            (Tag::Con, p),
660            (Tag::Str, 5),
661            (Tag::Con, a),
662            (Tag::Set, 2),
663            (Tag::Con, f),
664            (Tag::Ref, 7),
665        ]);
666        
667        assert_eq!(heap.term_string(0), "p({f,Ref_7},a)");
668
669        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
670        heap.cells.extend(vec![
671            (Tag::Str, 1),
672            (Tag::Func, 3),
673            (Tag::Con, p),
674            (Tag::Lis, 5),
675            (Tag::Con, a),
676            (Tag::Con, f),
677            (Tag::Lis, 7),
678            (Tag::Ref, 7),
679            EMPTY_LIS,
680        ]);
681        assert_eq!(heap.term_string(0), "p([f,Ref_7],a)");
682    }
683
684    #[test]
685    fn encode_tuple() {
686        let f = SymbolDB::set_const("f".into());
687        let a = SymbolDB::set_const("a".into());
688
689        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
690        heap.cells.extend(vec![(Tag::Str, 1), (Tag::Tup, 2), (Tag::Arg, 0), (Tag::Con, a)]);
691        assert_eq!(heap.term_string(0), "(Arg_0,a)");
692
693        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
694        heap.cells.extend(vec![
695            (Tag::Str, 1),
696            (Tag::Tup, 2),
697            (Tag::Str, 4),
698            (Tag::Con, a),
699            (Tag::Func, 2),
700            (Tag::Con, f),
701            (Tag::Ref, 6),
702        ]);
703        assert_eq!(heap.term_string(0), "(f(Ref_6),a)");
704
705        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
706        heap.cells.extend(vec![
707            (Tag::Str, 1),
708            (Tag::Tup, 2),
709            (Tag::Str, 4),
710            (Tag::Con, a),
711            (Tag::Tup, 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(Arc::new(vec![]), None);
718        heap.cells.extend(vec![
719            (Tag::Str, 1),
720            (Tag::Tup, 2),
721            (Tag::Str, 4),
722            (Tag::Con, a),
723            (Tag::Set, 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(Arc::new(vec![]), None);
730        heap.cells.extend(vec![
731            (Tag::Str, 1),
732            (Tag::Tup, 2),
733            (Tag::Lis, 4),
734            (Tag::Con, a),
735            (Tag::Con, f),
736            (Tag::Lis, 6),
737            (Tag::Ref, 6),
738            EMPTY_LIS,
739        ]);
740        assert_eq!(heap.term_string(0), "([f,Ref_6],a)");
741    }
742
743    #[test]
744    fn encode_list() {
745        let f = SymbolDB::set_const("f".into());
746        let a = SymbolDB::set_const("a".into());
747
748        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
749        heap.cells.extend(vec![
750            (Tag::Lis, 1),
751            (Tag::Arg, 0),
752            (Tag::Lis, 3),
753            (Tag::Con, a),
754            EMPTY_LIS,
755        ]);
756        assert_eq!(heap.term_string(0), "[Arg_0,a]");
757
758        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
759        heap.cells.extend(vec![
760            (Tag::Lis, 1),
761            (Tag::Str, 5),
762            (Tag::Lis, 3),
763            (Tag::Con, a),
764            EMPTY_LIS,
765            (Tag::Func, 2),
766            (Tag::Con, f),
767            (Tag::Ref, 7),
768        ]);
769        assert_eq!(heap.term_string(0), "[f(Ref_7),a]");
770
771        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
772        heap.cells.extend(vec![
773            (Tag::Lis, 1),
774            (Tag::Str, 5),
775            (Tag::Lis, 3),
776            (Tag::Con, a),
777            EMPTY_LIS,
778            (Tag::Tup, 2),
779            (Tag::Con, f),
780            (Tag::Ref, 7),
781        ]);
782        assert_eq!(heap.term_string(0), "[(f,Ref_7),a]");
783
784        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
785        heap.cells.extend(vec![
786            (Tag::Lis, 1),
787            (Tag::Str, 5),
788            (Tag::Lis, 3),
789            (Tag::Con, a),
790            EMPTY_LIS,
791            (Tag::Set, 2),
792            (Tag::Con, f),
793            (Tag::Ref, 7),
794        ]);
795        assert_eq!(heap.term_string(0), "[{f,Ref_7},a]");
796
797        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
798        heap.cells.extend(vec![
799            (Tag::Lis, 1),
800            (Tag::Lis, 5),
801            (Tag::Lis, 3),
802            (Tag::Con, a),
803            EMPTY_LIS,
804            (Tag::Con, f),
805            (Tag::Lis, 7),
806            (Tag::Ref, 7),
807            EMPTY_LIS,
808        ]);
809        assert_eq!(heap.term_string(0), "[[f,Ref_7],a]");
810    }
811
812    #[test]
813    fn encode_set() {
814        let f = SymbolDB::set_const("f".into());
815        let a = SymbolDB::set_const("a".into());
816
817        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
818        heap.cells.extend(vec![(Tag::Str, 1), (Tag::Set, 2), (Tag::Arg, 0), (Tag::Con, a)]);
819        assert_eq!(heap.term_string(0), "{Arg_0,a}");
820
821        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
822        heap.cells.extend(vec![
823            (Tag::Str, 1),
824            (Tag::Set, 2),
825            (Tag::Str, 4),
826            (Tag::Con, a),
827            (Tag::Func, 2),
828            (Tag::Con, f),
829            (Tag::Ref, 6),
830        ]);
831        assert_eq!(heap.term_string(0), "{f(Ref_6),a}");
832
833        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
834        heap.cells.extend(vec![
835            (Tag::Str, 1),
836            (Tag::Set, 2),
837            (Tag::Str, 4),
838            (Tag::Con, a),
839            (Tag::Tup, 2),
840            (Tag::Con, f),
841            (Tag::Ref, 6),
842        ]);
843        assert_eq!(heap.term_string(0), "{(f,Ref_6),a}");
844
845        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
846        heap.cells.extend(vec![
847            (Tag::Str, 1),
848            (Tag::Set, 2),
849            (Tag::Str, 4),
850            (Tag::Con, a),
851            (Tag::Set, 2),
852            (Tag::Con, f),
853            (Tag::Ref, 6),
854        ]);
855        assert_eq!(heap.term_string(0), "{{f,Ref_6},a}");
856
857        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
858        heap.cells.extend(vec![
859            (Tag::Str, 1),
860            (Tag::Set, 2),
861            (Tag::Lis, 4),
862            (Tag::Con, a),
863            (Tag::Con, f),
864            (Tag::Lis, 6),
865            (Tag::Ref, 6),
866            EMPTY_LIS,
867        ]);
868        assert_eq!(heap.term_string(0), "{[f,Ref_6],a}");
869    }
870
871    #[test]
872    fn dereference() {
873        let f = SymbolDB::set_const("f".into());
874        let a = SymbolDB::set_const("a".into());
875
876        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
877        heap.cells.extend(vec![(Tag::Ref, 1), (Tag::Ref, 2), (Tag::Ref, 3), (Tag::Ref, 3)]);
878        assert_eq!(heap.term_string(0), "Ref_3");
879
880        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
881        heap.cells.extend(vec![(Tag::Ref, 1), (Tag::Ref, 2), (Tag::Ref, 3), (Tag::Arg, 0)]);
882        assert_eq!(heap.term_string(0), "Arg_0");
883
884        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
885        heap.cells.extend(vec![(Tag::Ref, 1), (Tag::Ref, 2), (Tag::Ref, 3), (Tag::Con, a)]);
886        assert_eq!(heap.term_string(0), "a");
887
888        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
889        heap.cells.extend(vec![
890            (Tag::Ref, 1),
891            (Tag::Ref, 2),
892            (Tag::Ref, 3),
893            (Tag::Str, 4),
894            (Tag::Func, 3),
895            (Tag::Con, f),
896            (Tag::Con, a),
897            (Tag::Ref, 7),
898        ]);
899        assert_eq!(heap.term_string(0), "f(a,Ref_7)");
900
901        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
902        heap.cells.extend(vec![
903            (Tag::Ref, 1),
904            (Tag::Ref, 2),
905            (Tag::Ref, 3),
906            (Tag::Str, 4),
907            (Tag::Tup, 2),
908            (Tag::Con, a),
909            (Tag::Ref, 6),
910        ]);
911        assert_eq!(heap.term_string(0), "(a,Ref_6)");
912
913        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
914        heap.cells.extend(vec![
915            (Tag::Ref, 1),
916            (Tag::Ref, 2),
917            (Tag::Ref, 3),
918            (Tag::Str, 4),
919            (Tag::Set, 2),
920            (Tag::Con, a),
921            (Tag::Ref, 6),
922        ]);
923        assert_eq!(heap.term_string(0), "{a,Ref_6}");
924
925        let mut heap = QueryHeap::new(Arc::new(vec![]), None);
926        heap.cells.extend(vec![
927            (Tag::Ref, 1),
928            (Tag::Ref, 2),
929            (Tag::Ref, 3),
930            (Tag::Lis, 4),
931            (Tag::Con, a),
932            (Tag::Lis, 6),
933            (Tag::Ref, 6),
934            EMPTY_LIS,
935        ]);
936        assert_eq!(heap.term_string(0), "[a,Ref_6]");
937    }
938}
prolog2/heap/heap.rs

prolog2/heap/
heap.rs
