prolog2/parser/
execute_tree.rs

1//! AST execution: encodes parsed terms onto the heap and populates the predicate table.
2
3use std::collections::HashMap;
4
5use super::{
6    build_tree::TreeClause,
7    term::{Term, Unit},
8};
9use crate::{
10    heap::heap::Heap,
11    program::{clause::Clause, predicate_table::PredicateTable},
12};
13
14pub fn build_clause(
15    literals: Vec<Term>,
16    meta_vars: Option<Vec<String>>,
17    constrained_vars: Option<Vec<String>>,
18    heap: &mut impl Heap,
19    query: bool,
20) -> Clause {
21    let mut var_values = HashMap::new();
22
23    let literals: Vec<usize> = literals
24        .into_iter()
25        .map(|term| term.encode(heap, &mut var_values, query))
26        .collect();
27
28    let meta_vars = meta_vars.map(|vars| {
29        vars.into_iter()
30            .map(|var| *var_values.get(&var).unwrap())
31            .collect::<Vec<usize>>()
32    });
33
34    let constrained_vars = constrained_vars.map(|vars| {
35        vars.into_iter()
36            .map(|var| *var_values.get(&var).unwrap())
37            .collect::<Vec<usize>>()
38    });
39
40    Clause::new(literals, meta_vars, constrained_vars)
41}
42
43/// Extract variable names from a Term::Set
44fn extract_var_names_from_set(term: Term) -> Vec<String> {
45    if let Term::Set(set_terms) = term {
46        set_terms
47            .into_iter()
48            .map(|t| {
49                if let Term::Unit(Unit::Variable(symbol)) = t {
50                    symbol
51                } else {
52                    panic!("meta variable set should only contain variables")
53                }
54            })
55            .collect()
56    } else {
57        panic!("Expected a Set term")
58    }
59}
60
61/// Extract variable names from a Term::List (must be a flat list with EmptyList tail)
62fn extract_var_names_from_list(term: Term) -> Vec<String> {
63    if let Term::List(list_terms, tail) = term {
64        assert!(
65            matches!(*tail, Term::EmptyList),
66            "Unconstrained variable list must not have a tail"
67        );
68        list_terms
69            .into_iter()
70            .map(|t| {
71                if let Term::Unit(Unit::Variable(symbol)) = t {
72                    symbol
73                } else {
74                    panic!("unconstrained variable list should only contain variables")
75                }
76            })
77            .collect()
78    } else {
79        panic!("Expected a List term")
80    }
81}
82
83/// Extract meta_vars and constrained_vars from a MetaRule's trailing terms.
84///
85/// Handles three cases:
86/// - `...{P,Q,R}.` → meta_vars = {P,Q,R}, constrained_vars = None (defaults to all)
87/// - `...{P},[Q1,Q2].` → meta_vars = {P,Q1,Q2}, constrained_vars = Some({P})
88/// - `...[Q1,Q2].` → meta_vars = {Q1,Q2}, constrained_vars = Some({}) (empty)
89fn extract_meta_rule_vars(terms: &mut Vec<Term>) -> (Vec<String>, Option<Vec<String>>) {
90    let last = terms.pop().unwrap();
91    match last {
92        // Case 1: last is {P,Q,R} — all constrained (original behaviour)
93        Term::Set(_) => {
94            let meta_vars = extract_var_names_from_set(last);
95            (meta_vars, None)
96        }
97        // Case 2 or 3: last is [Q1,Q2]
98        Term::List(_, _) => {
99            let unconstrained = extract_var_names_from_list(last);
100            // Check if the new last element is a Set (Case 2: {P},[Q1,Q2])
101            let constrained = if matches!(terms.last(), Some(Term::Set(_))) {
102                extract_var_names_from_set(terms.pop().unwrap())
103            } else {
104                // Case 3: [Q1,Q2] only — no constrained vars
105                Vec::new()
106            };
107            let mut meta_vars = constrained.clone();
108            meta_vars.extend(unconstrained);
109            (meta_vars, Some(constrained))
110        }
111        _ => panic!("Last literal in meta_rule wasn't a set or list"),
112    }
113}
114
115pub(crate) fn execute_tree(
116    syntax_tree: Vec<TreeClause>,
117    heap: &mut impl Heap,
118    pred_table: &mut PredicateTable,
119) {
120    for clause in syntax_tree {
121        match clause {
122            TreeClause::Fact(term) => {
123                let clause = build_clause(vec![term], None, None, heap, false);
124                let symbol_arity = heap.str_symbol_arity(clause[0]);
125                pred_table
126                    .add_clause_to_predicate(clause, symbol_arity)
127                    .unwrap();
128            }
129            TreeClause::Rule(terms) => {
130                let clause = build_clause(terms, None, None, heap, false);
131                let symbol_arity = heap.str_symbol_arity(clause[0]);
132                pred_table
133                    .add_clause_to_predicate(clause, symbol_arity)
134                    .unwrap();
135            }
136            TreeClause::MetaRule(mut terms) => {
137                let (meta_vars, constrained_vars) = extract_meta_rule_vars(&mut terms);
138                let clause = build_clause(terms, Some(meta_vars), constrained_vars, heap, false);
139                let symbol_arity = heap.str_symbol_arity(clause[0]);
140                pred_table
141                    .add_clause_to_predicate(clause, symbol_arity)
142                    .unwrap();
143            }
144            TreeClause::MetaFact(head, meta_data) => {
145                let meta_vars = extract_var_names_from_set(meta_data);
146                let clause = build_clause(vec![head], Some(meta_vars), None, heap, false);
147                let symbol_arity = heap.str_symbol_arity(clause[0]);
148                pred_table
149                    .add_clause_to_predicate(clause, symbol_arity)
150                    .unwrap();
151            }
152            TreeClause::Directive(_terms) => {
153                unimplemented!("directive execution not yet supported")
154            }
155        }
156    }
157}
158
159#[cfg(test)]
160mod tests {
161    use crate::{
162        heap::{
163            heap::{Cell, Tag},
164            symbol_db::SymbolDB,
165        },
166        parser::execute_tree::execute_tree,
167        program::predicate_table::{Predicate, PredicateTable},
168    };
169
170    use super::super::{build_tree::TokenStream, tokeniser::tokenise};
171
172    #[test]
173    fn facts() {
174        let mut heap = Vec::<Cell>::new();
175        let mut pred_table = PredicateTable::new();
176        let facts = TokenStream::new(tokenise("p(a,b).q(c).".into()).unwrap())
177            .parse_all()
178            .unwrap();
179
180        let [p, q, a, b, c] = ["p", "q", "a", "b", "c"].map(|s| SymbolDB::set_const(s.into()));
181
182        execute_tree(facts, &mut heap, &mut pred_table);
183
184        if let Predicate::Clauses(clauses) = pred_table.get_predicate((p, 2)).unwrap() {
185            let fact = &clauses[0];
186            assert_eq!(
187                &heap[fact[0]..fact[0] + 4],
188                &[(Tag::Func, 3), (Tag::Con, p), (Tag::Con, a), (Tag::Con, b),]
189            );
190        } else {
191            panic!()
192        }
193
194        if let Predicate::Clauses(clauses) = pred_table.get_predicate((q, 1)).unwrap() {
195            let fact = &clauses[0];
196            assert_eq!(
197                &heap[fact[0]..fact[0] + 3],
198                &[(Tag::Func, 2), (Tag::Con, q), (Tag::Con, c),]
199            );
200        } else {
201            panic!()
202        }
203    }
204
205    #[test]
206    fn rules() {
207        let mut heap = Vec::<Cell>::new();
208        let mut pred_table = PredicateTable::new();
209        let facts = TokenStream::new(
210            tokenise("p(X,Y):-q(X,a),q(Y,b). q(X):-r(X). q(X):-p(X).".into()).unwrap(),
211        )
212        .parse_all()
213        .unwrap();
214
215        let [p, q, r, a, b] = ["p", "q", "r", "a", "b"].map(|s| SymbolDB::set_const(s.into()));
216
217        execute_tree(facts, &mut heap, &mut pred_table);
218
219        if let Predicate::Clauses(clauses) = pred_table.get_predicate((p, 2)).unwrap() {
220            let rule = &clauses[0];
221            assert_eq!(
222                &heap[rule[0]..rule[0] + 4],
223                &[(Tag::Func, 3), (Tag::Con, p), (Tag::Arg, 0), (Tag::Arg, 1),]
224            );
225            assert_eq!(
226                &heap[rule[1]..rule[1] + 4],
227                &[(Tag::Func, 3), (Tag::Con, q), (Tag::Arg, 0), (Tag::Con, a),]
228            );
229            assert_eq!(
230                &heap[rule[2]..rule[2] + 4],
231                &[(Tag::Func, 3), (Tag::Con, q), (Tag::Arg, 1), (Tag::Con, b),]
232            );
233        } else {
234            panic!()
235        }
236
237        if let Predicate::Clauses(clauses) = pred_table.get_predicate((q, 1)).unwrap() {
238            let rule = &clauses[0];
239            assert_eq!(
240                &heap[rule[0]..rule[0] + 3],
241                &[(Tag::Func, 2), (Tag::Con, q), (Tag::Arg, 0),]
242            );
243            assert_eq!(
244                &heap[rule[1]..rule[1] + 3],
245                &[(Tag::Func, 2), (Tag::Con, r), (Tag::Arg, 0),]
246            );
247
248            let rule = &clauses[1];
249            assert_eq!(
250                &heap[rule[0]..rule[0] + 3],
251                &[(Tag::Func, 2), (Tag::Con, q), (Tag::Arg, 0),]
252            );
253            assert_eq!(
254                &heap[rule[1]..rule[1] + 3],
255                &[(Tag::Func, 2), (Tag::Con, p), (Tag::Arg, 0),]
256            );
257        } else {
258            panic!()
259        }
260    }
261
262    #[test]
263    fn meta_rules() {
264        let mut heap = Vec::<Cell>::new();
265        let mut pred_table = PredicateTable::new();
266        let facts = TokenStream::new(tokenise("p(X,Y):-Q(X,a),R(Y,b),{Q,R}.".into()).unwrap())
267            .parse_all()
268            .unwrap();
269
270        let [p, _q, _r, a, b] = ["p", "q", "r", "a", "b"].map(|s| SymbolDB::set_const(s.into()));
271
272        execute_tree(facts, &mut heap, &mut pred_table);
273
274        if let Predicate::Clauses(clauses) = pred_table.get_predicate((p, 2)).unwrap() {
275            let meta_rule = &clauses[0];
276            assert_eq!(
277                &heap[meta_rule[0]..meta_rule[0] + 4],
278                &[(Tag::Func, 3), (Tag::Con, p), (Tag::Arg, 0), (Tag::Arg, 1),]
279            );
280            assert_eq!(
281                &heap[meta_rule[1]..meta_rule[1] + 4],
282                &[(Tag::Func, 3), (Tag::Arg, 2), (Tag::Arg, 0), (Tag::Con, a),]
283            );
284            assert_eq!(
285                &heap[meta_rule[2]..meta_rule[2] + 4],
286                &[(Tag::Func, 3), (Tag::Arg, 3), (Tag::Arg, 1), (Tag::Con, b),]
287            );
288            assert!(meta_rule.meta_var(2).unwrap());
289            assert!(meta_rule.meta_var(3).unwrap());
290            // With {Q,R} only, constrained_vars defaults to same as meta_vars
291            assert!(meta_rule.constrained_var(2));
292            assert!(meta_rule.constrained_var(3));
293            assert!(!meta_rule.constrained_var(0));
294            assert!(!meta_rule.constrained_var(1));
295        } else {
296            panic!()
297        }
298    }
299
300    #[test]
301    fn meta_rules_with_unconstrained_list() {
302        // edge(El,Q1,Q2):-q(Q1),q(Q2),{El},[Q1,Q2].
303        // El=Arg0, Q1=Arg1, Q2=Arg2
304        // meta_vars = {El, Q1, Q2} = {0, 1, 2}
305        // constrained_vars = {El} = {0}
306        let mut heap = Vec::<Cell>::new();
307        let mut pred_table = PredicateTable::new();
308        let facts =
309            TokenStream::new(tokenise("edge(El,Q1,Q2):-q(Q1),q(Q2),{El},[Q1,Q2].".into()).unwrap())
310                .parse_all()
311                .unwrap();
312
313        let edge = SymbolDB::set_const("edge".into());
314        let _q = SymbolDB::set_const("q".into());
315
316        execute_tree(facts, &mut heap, &mut pred_table);
317
318        if let Predicate::Clauses(clauses) = pred_table.get_predicate((edge, 3)).unwrap() {
319            let meta_rule = &clauses[0];
320            // All three are meta_vars
321            assert!(meta_rule.meta_var(0).unwrap()); // El
322            assert!(meta_rule.meta_var(1).unwrap()); // Q1
323            assert!(meta_rule.meta_var(2).unwrap()); // Q2
324                                                     // Only El is constrained
325            assert!(meta_rule.constrained_var(0)); // El
326            assert!(!meta_rule.constrained_var(1)); // Q1 — not constrained
327            assert!(!meta_rule.constrained_var(2)); // Q2 — not constrained
328        } else {
329            panic!("Expected clauses for edge/3")
330        }
331    }
332
333    #[test]
334    fn meta_rules_list_only() {
335        // edge(El,Q1,Q2):-q(Q1),q(Q2),[El,Q1,Q2].
336        // El=Arg0, Q1=Arg1, Q2=Arg2
337        // meta_vars = {El, Q1, Q2} = {0, 1, 2}
338        // constrained_vars = {} (empty)
339        let mut heap = Vec::<Cell>::new();
340        let mut pred_table = PredicateTable::new();
341        let facts =
342            TokenStream::new(tokenise("edge(El,Q1,Q2):-q(Q1),q(Q2),[El,Q1,Q2].".into()).unwrap())
343                .parse_all()
344                .unwrap();
345
346        let edge = SymbolDB::set_const("edge".into());
347        let _q = SymbolDB::set_const("q".into());
348
349        execute_tree(facts, &mut heap, &mut pred_table);
350
351        if let Predicate::Clauses(clauses) = pred_table.get_predicate((edge, 3)).unwrap() {
352            let meta_rule = &clauses[0];
353            // All three are meta_vars
354            assert!(meta_rule.meta_var(0).unwrap()); // El
355            assert!(meta_rule.meta_var(1).unwrap()); // Q1
356            assert!(meta_rule.meta_var(2).unwrap()); // Q2
357                                                     // None are constrained
358            assert!(!meta_rule.constrained_var(0));
359            assert!(!meta_rule.constrained_var(1));
360            assert!(!meta_rule.constrained_var(2));
361        } else {
362            panic!("Expected clauses for edge/3")
363        }
364    }
365
366    #[test]
367    fn meta_facts() {
368        let mut heap = Vec::<Cell>::new();
369        let mut pred_table = PredicateTable::new();
370        let facts = TokenStream::new(tokenise("Map([],[],X),{Map}.".into()).unwrap())
371            .parse_all()
372            .unwrap();
373
374        execute_tree(facts, &mut heap, &mut pred_table);
375
376        // Map is a variable, so we need to check via arity 3
377        // The predicate symbol will be Arg 0 (the Map variable)
378        // We need to find the clause differently since the predicate symbol is a variable
379
380        // For a meta-fact with variable predicate, it gets indexed differently
381        // Let's check the heap directly
382        assert!(!heap.is_empty());
383
384        // The head should be: (Func, 4), (Arg, 0), (ELis), (ELis), (Arg, 1)
385        // where Arg 0 is the Map variable and Arg 1 is X
386        assert_eq!(heap[0], (Tag::Func, 4));
387        assert_eq!(heap[1], (Tag::Arg, 0)); // Map variable
388        assert_eq!(heap[2].0, Tag::ELis); // Empty list
389        assert_eq!(heap[3].0, Tag::ELis); // Empty list
390        assert_eq!(heap[4], (Tag::Arg, 1)); // X variable
391    }
392}
prolog2/parser/execute_tree.rs

prolog2/parser/
execute_tree.rs
