prolog2/heap/
query_heap.rs

1use crate::heap::{heap::Tag, symbol_db::SymbolDB};
2use fsize::fsize;
3use std::{
4    mem,
5    ops::{Index, IndexMut, Range},
6    sync::{
7        atomic::{AtomicUsize, Ordering::Acquire},
8        Arc,
9    },
10};
11
12use super::heap::{Cell, Heap};
13
14static HEAP_ID_COUNTER: AtomicUsize = AtomicUsize::new(1);
15
16/// Working heap for proof search.
17///
18/// Wraps a shared read-only program heap (`Arc<Vec<Cell>>`) and an
19/// owned mutable cell buffer for query-time allocations. Supports
20/// branching via an optional parent pointer for backtracking.
21pub struct QueryHeap {
22    id: usize,
23    pub(crate) cells: Vec<Cell>,
24    prog_cells: Arc<Vec<Cell>>,
25    // TODO: handle branching query heap multi-threading
26    root: Option<*const QueryHeap>,
27}
28
29impl QueryHeap {
30    pub fn new(prog_cells: Arc<Vec<Cell>>, root: Option<*const QueryHeap>) -> QueryHeap {
31        let id = HEAP_ID_COUNTER.fetch_add(1, Acquire);
32        QueryHeap {
33            id,
34            cells: Vec::new(),
35            prog_cells,
36            root,
37        }
38    }
39
40    pub fn branch(&self, count: usize) -> Vec<QueryHeap> {
41        let mut branch_heap = Vec::with_capacity(count);
42        for _ in 0..count {
43            branch_heap.push(QueryHeap::new(self.prog_cells.clone(), Some(self)));
44        }
45        branch_heap
46    }
47
48    fn get_symbol_db_id(&self, addr: usize) -> usize {
49        if addr < self.prog_cells.len() {
50            0
51        } else {
52            self.id
53        }
54    }
55}
56
57impl Heap for QueryHeap {
58    fn heap_push(&mut self, cell: Cell) -> usize {
59        let i = self.heap_len();
60        self.cells.push(cell);
61        i
62    }
63
64    fn heap_len(&self) -> usize {
65        match self.root {
66            Some(root) => unsafe { &*root }.heap_len() + self.cells.len(),
67            None => self.prog_cells.len() + self.cells.len(),
68        }
69    }
70
71    fn get_id(&self) -> usize {
72        self.id
73    }
74
75    /** Create String to represent cell, can be recursively used to format complex structures or list */
76    fn term_string(&self, addr: usize) -> String {
77        // println!("[{addr}]:{:?}", self[addr]);
78        let addr = self.deref_addr(addr);
79        match self[addr].0 {
80            Tag::Con => SymbolDB::get_const(self[addr].1).to_string(),
81            Tag::Func => self.func_string(addr),
82            Tag::Lis => self.list_string(addr),
83            Tag::ELis => "[]".into(),
84            Tag::Arg => match SymbolDB::get_var(addr, self.get_symbol_db_id(addr)) {
85                Some(symbol) => symbol.to_string(),
86                None => format!("Arg_{}", self[addr].1),
87            },
88            Tag::Ref => match SymbolDB::get_var(self.deref_addr(addr), self.get_symbol_db_id(addr))
89                .to_owned()
90            {
91                Some(symbol) => symbol.to_string(),
92                None => format!("Ref_{}", self[addr].1),
93            },
94            Tag::Int => {
95                let value: isize = unsafe { mem::transmute_copy(&self[addr].1) };
96                format!("{value}")
97            }
98            Tag::Flt => {
99                let value: fsize = unsafe { mem::transmute_copy(&self[addr].1) };
100                format!("{value}")
101            }
102            Tag::Tup => self.tuple_string(addr),
103            Tag::Set => self.set_string(addr),
104            Tag::Str => self.term_string(self[addr].1),
105            Tag::Stri => SymbolDB::get_string(self[addr].1).to_string(),
106        }
107    }
108    
109    fn truncate(&mut self, mut len: usize) {
110        if len < self.prog_cells.len(){
111            panic!("Can't truncate to prog cells")
112        }
113        len -= self.prog_cells.len();
114        self.cells.resize(len, (Tag::Ref,0));
115    }
116}
117
118impl Index<usize> for QueryHeap {
119    type Output = Cell;
120
121    fn index(&self, index: usize) -> &Self::Output {
122        if index < self.prog_cells.len() {
123            &self.prog_cells[index]
124        } else {
125            if let Some(root) = self.root {
126                let root = unsafe { &*root };
127                if index < root.heap_len() {
128                    // Index is in root's query cells
129                    &root[index]
130                } else {
131                    // Index is in our own cells
132                    &self.cells[index - root.heap_len()]
133                }
134            } else {
135                &self.cells[index - self.prog_cells.len()]
136            }
137        }
138    }
139}
140
141impl IndexMut<usize> for QueryHeap {
142    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
143        if index < self.prog_cells.len() {
144            panic!("Can't get mutable reference to program heap cell");
145        } else {
146            if let Some(root) = self.root {
147                let root = unsafe { &*root };
148                let root_heap_len = root.heap_len(); // prog_cells.len() + root.cells.len()
149                if index < root_heap_len {
150                    // Index is in root's query cells - deny mutable access
151                    panic!("Can't get mutable reference to root heap cell");
152                } else {
153                    // Index is in our own cells
154                    &mut self.cells[index - root_heap_len]
155                }
156            } else {
157                &mut self.cells[index - self.prog_cells.len()]
158            }
159        }
160    }
161}
162
163impl Index<Range<usize>> for QueryHeap {
164    type Output = [Cell];
165
166    fn index(&self, index: Range<usize>) -> &Self::Output {
167        let len = self.prog_cells.len();
168
169        if index.start < len && index.end < len {
170            &self.prog_cells[index]
171        } else if index.start >= len && self.root.is_none() {
172            &self.cells[index.start - len..index.end - len]
173        } else {
174            panic!("Range splits static and mutable heap")
175        }
176    }
177}
prolog2/heap/query_heap.rs

prolog2/heap/
query_heap.rs
