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) => unimplemented!("directive execution not yet supported"),
153        }
154    }
155}
156
157#[cfg(test)]
158mod tests {
159    use crate::{
160        heap::{
161            heap::{Cell, Tag},
162            symbol_db::SymbolDB,
163        },
164        parser::execute_tree::execute_tree,
165        program::predicate_table::{Predicate, PredicateTable},
166    };
167
168    use super::super::{
169        build_tree::{TokenStream},
170        tokeniser::tokenise,
171    };
172
173    #[test]
174    fn facts() {
175        let mut heap = Vec::<Cell>::new();
176        let mut pred_table = PredicateTable::new();
177        let facts = TokenStream::new(tokenise("p(a,b).q(c).".into()).unwrap())
178            .parse_all()
179            .unwrap();
180
181        let [p, q, a, b, c] = ["p", "q", "a", "b", "c"].map(|s| SymbolDB::set_const(s.into()));
182
183        execute_tree(facts, &mut heap, &mut pred_table);
184
185        if let Predicate::Clauses(clauses) = pred_table.get_predicate((p, 2)).unwrap() {
186            let fact = &clauses[0];
187            assert_eq!(
188                &heap[fact[0]..fact[0] + 4],
189                &[(Tag::Func, 3), (Tag::Con, p), (Tag::Con, a), (Tag::Con, b),]
190            );
191        } else {
192            panic!()
193        }
194
195        if let Predicate::Clauses(clauses) = pred_table.get_predicate((q, 1)).unwrap() {
196            let fact = &clauses[0];
197            assert_eq!(
198                &heap[fact[0]..fact[0] + 3],
199                &[(Tag::Func, 2), (Tag::Con, q), (Tag::Con, c),]
200            );
201        } else {
202            panic!()
203        }
204    }
205
206    #[test]
207    fn rules() {
208        let mut heap = Vec::<Cell>::new();
209        let mut pred_table = PredicateTable::new();
210        let facts = TokenStream::new(
211            tokenise("p(X,Y):-q(X,a),q(Y,b). q(X):-r(X). q(X):-p(X).".into()).unwrap(),
212        )
213        .parse_all()
214        .unwrap();
215
216        let [p, q, r, a, b] = ["p", "q", "r", "a", "b"].map(|s| SymbolDB::set_const(s.into()));
217
218        execute_tree(facts, &mut heap, &mut pred_table);
219
220        if let Predicate::Clauses(clauses) = pred_table.get_predicate((p, 2)).unwrap() {
221            let rule = &clauses[0];
222            assert_eq!(
223                &heap[rule[0]..rule[0] + 4],
224                &[(Tag::Func, 3), (Tag::Con, p), (Tag::Arg, 0), (Tag::Arg, 1),]
225            );
226            assert_eq!(
227                &heap[rule[1]..rule[1] + 4],
228                &[(Tag::Func, 3), (Tag::Con, q), (Tag::Arg, 0), (Tag::Con, a),]
229            );
230            assert_eq!(
231                &heap[rule[2]..rule[2] + 4],
232                &[(Tag::Func, 3), (Tag::Con, q), (Tag::Arg, 1), (Tag::Con, b),]
233            );
234        } else {
235            panic!()
236        }
237
238        if let Predicate::Clauses(clauses) = pred_table.get_predicate((q, 1)).unwrap() {
239            let rule = &clauses[0];
240            assert_eq!(
241                &heap[rule[0]..rule[0] + 3],
242                &[(Tag::Func, 2), (Tag::Con, q), (Tag::Arg, 0),]
243            );
244            assert_eq!(
245                &heap[rule[1]..rule[1] + 3],
246                &[(Tag::Func, 2), (Tag::Con, r), (Tag::Arg, 0),]
247            );
248
249            let rule = &clauses[1];
250            assert_eq!(
251                &heap[rule[0]..rule[0] + 3],
252                &[(Tag::Func, 2), (Tag::Con, q), (Tag::Arg, 0),]
253            );
254            assert_eq!(
255                &heap[rule[1]..rule[1] + 3],
256                &[(Tag::Func, 2), (Tag::Con, p), (Tag::Arg, 0),]
257            );
258        } else {
259            panic!()
260        }
261    }
262
263    #[test]
264    fn meta_rules() {
265        let mut heap = Vec::<Cell>::new();
266        let mut pred_table = PredicateTable::new();
267        let facts = TokenStream::new(tokenise("p(X,Y):-Q(X,a),R(Y,b),{Q,R}.".into()).unwrap())
268            .parse_all()
269            .unwrap();
270
271        let [p, _q, _r, a, b] = ["p", "q", "r", "a", "b"].map(|s| SymbolDB::set_const(s.into()));
272
273        execute_tree(facts, &mut heap, &mut pred_table);
274
275        if let Predicate::Clauses(clauses) = pred_table.get_predicate((p, 2)).unwrap() {
276            let meta_rule = &clauses[0];
277            assert_eq!(
278                &heap[meta_rule[0]..meta_rule[0] + 4],
279                &[(Tag::Func, 3), (Tag::Con, p), (Tag::Arg, 0), (Tag::Arg, 1),]
280            );
281            assert_eq!(
282                &heap[meta_rule[1]..meta_rule[1] + 4],
283                &[(Tag::Func, 3), (Tag::Arg, 2), (Tag::Arg, 0), (Tag::Con, a),]
284            );
285            assert_eq!(
286                &heap[meta_rule[2]..meta_rule[2] + 4],
287                &[(Tag::Func, 3), (Tag::Arg, 3), (Tag::Arg, 1), (Tag::Con, b),]
288            );
289            assert!(meta_rule.meta_var(2).unwrap());
290            assert!(meta_rule.meta_var(3).unwrap());
291            // With {Q,R} only, constrained_vars defaults to same as meta_vars
292            assert!(meta_rule.constrained_var(2));
293            assert!(meta_rule.constrained_var(3));
294            assert!(!meta_rule.constrained_var(0));
295            assert!(!meta_rule.constrained_var(1));
296        } else {
297            panic!()
298        }
299    }
300
301    #[test]
302    fn meta_rules_with_unconstrained_list() {
303        // edge(El,Q1,Q2):-q(Q1),q(Q2),{El},[Q1,Q2].
304        // El=Arg0, Q1=Arg1, Q2=Arg2
305        // meta_vars = {El, Q1, Q2} = {0, 1, 2}
306        // constrained_vars = {El} = {0}
307        let mut heap = Vec::<Cell>::new();
308        let mut pred_table = PredicateTable::new();
309        let facts = TokenStream::new(
310            tokenise("edge(El,Q1,Q2):-q(Q1),q(Q2),{El},[Q1,Q2].".into()).unwrap(),
311        )
312        .parse_all()
313        .unwrap();
314
315        let edge = SymbolDB::set_const("edge".into());
316        let _q = SymbolDB::set_const("q".into());
317
318        execute_tree(facts, &mut heap, &mut pred_table);
319
320        if let Predicate::Clauses(clauses) = pred_table.get_predicate((edge, 3)).unwrap() {
321            let meta_rule = &clauses[0];
322            // All three are meta_vars
323            assert!(meta_rule.meta_var(0).unwrap()); // El
324            assert!(meta_rule.meta_var(1).unwrap()); // Q1
325            assert!(meta_rule.meta_var(2).unwrap()); // Q2
326            // Only El is constrained
327            assert!(meta_rule.constrained_var(0));  // El
328            assert!(!meta_rule.constrained_var(1)); // Q1 — not constrained
329            assert!(!meta_rule.constrained_var(2)); // Q2 — not constrained
330        } else {
331            panic!("Expected clauses for edge/3")
332        }
333    }
334
335    #[test]
336    fn meta_rules_list_only() {
337        // edge(El,Q1,Q2):-q(Q1),q(Q2),[El,Q1,Q2].
338        // El=Arg0, Q1=Arg1, Q2=Arg2
339        // meta_vars = {El, Q1, Q2} = {0, 1, 2}
340        // constrained_vars = {} (empty)
341        let mut heap = Vec::<Cell>::new();
342        let mut pred_table = PredicateTable::new();
343        let facts = TokenStream::new(
344            tokenise("edge(El,Q1,Q2):-q(Q1),q(Q2),[El,Q1,Q2].".into()).unwrap(),
345        )
346        .parse_all()
347        .unwrap();
348
349        let edge = SymbolDB::set_const("edge".into());
350        let _q = SymbolDB::set_const("q".into());
351
352        execute_tree(facts, &mut heap, &mut pred_table);
353
354        if let Predicate::Clauses(clauses) = pred_table.get_predicate((edge, 3)).unwrap() {
355            let meta_rule = &clauses[0];
356            // All three are meta_vars
357            assert!(meta_rule.meta_var(0).unwrap()); // El
358            assert!(meta_rule.meta_var(1).unwrap()); // Q1
359            assert!(meta_rule.meta_var(2).unwrap()); // Q2
360            // None are constrained
361            assert!(!meta_rule.constrained_var(0));
362            assert!(!meta_rule.constrained_var(1));
363            assert!(!meta_rule.constrained_var(2));
364        } else {
365            panic!("Expected clauses for edge/3")
366        }
367    }
368
369    #[test]
370    fn meta_facts() {
371        let mut heap = Vec::<Cell>::new();
372        let mut pred_table = PredicateTable::new();
373        let facts = TokenStream::new(tokenise("Map([],[],X),{Map}.".into()).unwrap())
374            .parse_all()
375            .unwrap();
376
377        execute_tree(facts, &mut heap, &mut pred_table);
378
379        // Map is a variable, so we need to check via arity 3
380        // The predicate symbol will be Arg 0 (the Map variable)
381        // We need to find the clause differently since the predicate symbol is a variable
382        
383        // For a meta-fact with variable predicate, it gets indexed differently
384        // Let's check the heap directly
385        assert!(!heap.is_empty());
386        
387        // The head should be: (Func, 4), (Arg, 0), (ELis), (ELis), (Arg, 1)
388        // where Arg 0 is the Map variable and Arg 1 is X
389        assert_eq!(heap[0], (Tag::Func, 4));
390        assert_eq!(heap[1], (Tag::Arg, 0)); // Map variable
391        assert_eq!(heap[2].0, Tag::ELis);   // Empty list
392        assert_eq!(heap[3].0, Tag::ELis);   // Empty list  
393        assert_eq!(heap[4], (Tag::Arg, 1)); // X variable
394    }
395}
prolog2/parser/execute_tree.rs

prolog2/parser/
execute_tree.rs
