prolog2/parser/
build_tree.rs

1//! Syntax tree construction: parses a token stream into an AST of clauses and terms.
2
3// TODO: Handle sets
4
5use super::term::{Term, Unit};
6
7const INFIX_ORDER: &[&[&str]] = &[
8    &["**"],
9    &["*", "/"],
10    &["+", "-"],
11    &["==", "=/=", "/=", "=:=", "is", ">", ">=", "<", "<="],
12];
13
14#[derive(Debug, PartialEq, Clone)]
15pub enum TreeClause {
16    Fact(Term),
17    Rule(Vec<Term>),
18    MetaRule(Vec<Term>),
19    MetaFact(Term, Term), // head and set of existentially quantified variables
20    Directive(Vec<Term>),
21}
22
23pub struct TokenStream {
24    tokens: Vec<String>,
25    index: usize,
26    line: usize,
27}
28
29impl TokenStream {
30    pub fn new(tokens: Vec<String>) -> Self {
31        TokenStream {
32            tokens,
33            index: 0,
34            line: 0,
35        }
36    }
37
38    pub fn next(&mut self) -> Option<&str> {
39        loop {
40            if self.index == self.tokens.len() {
41                return None;
42            }
43            match self.tokens[self.index].as_str() {
44                "\n" => {
45                    self.index += 1;
46                    self.line += 1
47                }
48                token => {
49                    self.index += 1;
50                    return Some(token);
51                }
52            }
53        }
54    }
55
56    pub fn peek(&self) -> Option<&str> {
57        let mut index = self.index;
58        loop {
59            if index == self.tokens.len() {
60                return None;
61            }
62            match self.tokens[index].as_str() {
63                "\n" => {
64                    index += 1;
65                }
66                token => {
67                    return Some(token);
68                }
69            }
70        }
71    }
72}
73
74fn is_operator(token: &str) -> bool {
75    INFIX_ORDER.iter().any(|group| group.contains(&token))
76}
77
78fn infix_order(operator: &str) -> usize {
79    INFIX_ORDER
80        .iter()
81        .position(|ops| ops.contains(&operator))
82        .unwrap()
83}
84
85fn resolve_infix(term_stack: &mut Vec<Term>, op_stack: &mut Vec<String>, max_prescendence: usize) {
86    while let Some(p) = op_stack.last().map(|operator| infix_order(&operator)) {
87        if p > max_prescendence {
88            break;
89        }
90        let op = op_stack.pop().unwrap();
91        let right = term_stack.pop().unwrap();
92        let left = term_stack.pop().unwrap();
93        term_stack.push(Term::Atom(Unit::Constant(op), vec![left, right]));
94    }
95}
96
97impl TokenStream {
98    fn expect(&mut self, value: &str) -> Result<(), String> {
99        match self.next() {
100            Some(token) if token == value => Ok(()),
101            Some(token) => Err(format!("Expected \"{value}\" recieved \"{token}\"")),
102            None => Err(format!("Unexpected end of file in expect {value}")),
103        }
104    }
105
106    fn consume_args(&mut self) -> Result<Vec<Term>, String> {
107        let mut args = Vec::new();
108        loop {
109            args.push(self.parse_expression()?);
110            match self.peek() {
111                Some(")" | "|" | "]" | "}") => return Ok(args), // TODO: end consuming args based on certain conditions, don't accept all end tokens
112                Some(",") => {
113                    self.next();
114                }
115                Some(token) => return Err(format!("Unexpected token in arguments: {token}")),
116                None => return Err("Unexpected End of File".into()),
117            }
118        }
119    }
120
121    /**
122     *
123     */
124    pub(super) fn parse_term(&mut self) -> Result<Term, String> {
125        match self.peek().ok_or("Unexpected end of file")? {
126            "{" => {
127                self.next();
128                let args = self.consume_args()?;
129                if self.next() == Some("}") {
130                    Ok(Term::Set(args))
131                } else {
132                    Err("Incorrectly formatted set".into())
133                }
134            }
135            "[" => {
136                self.next();
137                let head = self.consume_args()?;
138                match self.next().ok_or("Unexpected end of file")? {
139                    "|" => {
140                        let tail = Box::new(self.parse_expression()?);
141                        self.expect("]")?;
142                        Ok(Term::List(head, tail))
143                    }
144                    "]" => Ok(Term::List(head, Box::new(Term::EmptyList))),
145                    token => return Err(format!("Unexpected token in list: {token}")),
146                }
147            }
148            "[]" => {
149                self.next();
150                Ok(Term::EmptyList)
151            }
152            "{}" => {
153                self.next();
154                Ok(Term::Set(vec![]))
155            }
156            "()" => {
157                self.next();
158                Ok(Term::Tuple(vec![]))
159            }
160            "(" => {
161                // Grouped expression or tuple
162                self.next();
163                let mut args = self.consume_args()?;
164                self.expect(")")?;
165                if args.len() == 1 {
166                    Ok(args.pop().unwrap())
167                } else {
168                    Ok(Term::Tuple(args))
169                }
170            }
171            token if is_operator(token) => {
172                // Handle prefix operators (unary minus, unary plus)
173                let op = self.next().unwrap().to_string();
174                let operand = self.parse_term()?;
175                Ok(Term::Atom(Unit::Constant(op), vec![operand]))
176            }
177            token => {
178                let token = token.to_string();
179                match Unit::parse_unit(self.next().unwrap()) {
180                    Some(unit @ (Unit::Constant(_) | Unit::Variable(_))) => {
181                        if self.peek() == Some("(") {
182                            self.next();
183                            let args = self.consume_args()?;
184                            self.expect(")")?;
185                            Ok(Term::Atom(unit, args))
186                        } else {
187                            Ok(Term::Unit(unit))
188                        }
189                    }
190                    Some(num @ (Unit::Float(_) | Unit::Int(_))) => Ok(Term::Unit(num)),
191                    Some(unit @ Unit::String(_)) => Ok(Term::Unit(unit)),
192                    None => unimplemented!("parse_expression: unhandled token '{token}'"),
193                }
194            }
195        }
196    }
197
198    pub(super) fn parse_expression(&mut self) -> Result<Term, String> {
199        let mut op_stack = Vec::<String>::new();
200        let mut term_stack = Vec::<Term>::new();
201        loop {
202            //Consume a term
203            if self.peek() == Some("(") {
204                //Grouped Expression with brackets or tuple
205                self.next();
206                let mut args = self.consume_args()?;
207                self.expect(")")?;
208                if args.len() == 1 {
209                    term_stack.push(args.pop().unwrap());
210                } else {
211                    term_stack.push(Term::Tuple(args));
212                }
213            } else {
214                term_stack.push(self.parse_term()?);
215            }
216
217            //Is next token an operator
218            match self.peek() {
219                Some(operator) if is_operator(operator) => {
220                    resolve_infix(&mut term_stack, &mut op_stack, infix_order(operator));
221                    op_stack.push(operator.into());
222                    self.next();
223                }
224                // Some(token) => {println!("Token: {token}");break;}
225                _ => break,
226            }
227        }
228
229        resolve_infix(&mut term_stack, &mut op_stack, INFIX_ORDER.len());
230        term_stack.pop().ok_or("Empty expression".into())
231    }
232
233    fn parse_body_literals(&mut self) -> Result<Vec<Term>, String> {
234        let mut body = Vec::new();
235        loop {
236            body.push(self.parse_expression()?);
237            match self.next() {
238                Some(",") => continue,
239                Some(".") => break,
240                Some(token) => {
241                    return Err(format!(
242                        "Unexpected token ({token}) after literal, expected either ',' or '.'"
243                    ))
244                }
245                None => return Err("Unexpected end of file".into()),
246            }
247        }
248        Ok(body)
249    }
250
251    pub fn parse_clause(&mut self) -> Result<Option<TreeClause>, String> {
252        match self.peek() {
253            None => return Ok(None),
254            Some(":-") => {
255                self.next();
256                return Ok(Some(TreeClause::Directive(self.parse_body_literals()?)));
257            }
258            Some(_) => {
259                let mut literals = vec![self.parse_expression()?];
260                match self.next() {
261                    Some(":-") => {
262                        literals.append(&mut self.parse_body_literals()?);
263                        let len = literals.len();
264                        let meta_rule = match literals.last() {
265                            // Case 1: ...{P,Q,R}. — all constrained
266                            Some(Term::Set(eq_vars)) => {
267                                if eq_vars
268                                    .iter()
269                                    .any(|eq_var| !matches!(eq_var, Term::Unit(Unit::Variable(_))))
270                                {
271                                    return Err(format!("Incorrectly formatted existentially quantified variables  {:?}", eq_vars));
272                                }
273                                true
274                            }
275                            // Case 2 or 3: last is [Q1,Q2] — unconstrained vars list
276                            Some(Term::List(vars, tail)) if matches!(tail.as_ref(), Term::EmptyList) => {
277                                if vars
278                                    .iter()
279                                    .any(|v| !matches!(v, Term::Unit(Unit::Variable(_))))
280                                {
281                                    return Err(format!("Unconstrained variable list should only contain variables, got {:?}", vars));
282                                }
283                                // Case 2: ...{P},[Q1,Q2]. — check if second-to-last is a constrained set
284                                if len >= 2 {
285                                    if let Term::Set(eq_vars) = &literals[len - 2] {
286                                        if eq_vars
287                                            .iter()
288                                            .any(|eq_var| !matches!(eq_var, Term::Unit(Unit::Variable(_))))
289                                        {
290                                            return Err(format!("Incorrectly formatted existentially quantified variables {:?}", eq_vars));
291                                        }
292                                    }
293                                }
294                                // Case 3: ...[Q1,Q2]. — no constrained set, just unconstrained list
295                                true
296                            }
297                            _ => false,
298                        };
299                        if meta_rule {
300                            Ok(Some(TreeClause::MetaRule(literals)))
301                        } else {
302                            Ok(Some(TreeClause::Rule(literals)))
303                        }
304                    }
305                    Some(",") => {
306                        // Could be a MetaFact: Head, {EQVars}.
307                        let meta_data = self.parse_expression()?;
308                        if let Term::Set(eq_vars) = &meta_data {
309                            if eq_vars
310                                .iter()
311                                .any(|eq_var| !matches!(eq_var, Term::Unit(Unit::Variable(_))))
312                            {
313                                return Err(format!("Incorrectly formatted existentially quantified variables {:?}", eq_vars));
314                            }
315                            self.expect(".")?;
316                            Ok(Some(TreeClause::MetaFact(literals.pop().unwrap(), meta_data)))
317                        } else {
318                            Err(format!("Expected set of existentially quantified variables after comma in meta-fact, got {:?}", meta_data))
319                        }
320                    }
321                    Some(".") => Ok(Some(TreeClause::Fact(literals[0].clone()))),
322                    Some(token) => Err(format!("Expected \".\", \",\", or \":-\", recieved {token}")),
323                    None => Err("Unexpected end of file".into()),
324                }
325            }
326        }
327    }
328
329    pub fn parse_all(&mut self) -> Result<Vec<TreeClause>, String> {
330        let mut clauses = Vec::<TreeClause>::new();
331        loop {
332            match self.parse_clause() {
333                Ok(Some(clause)) => clauses.push(clause),
334                Ok(None) => return Ok(clauses),
335                Err(msg) => return Err(format!("Line {}:  {msg}", self.line)),
336            }
337        }
338    }
339}
340
341#[cfg(test)]
342mod tests {
343    use super::{
344        super::tokeniser::tokenise,
345        {Term, TokenStream, TreeClause, Unit},
346    };
347    #[test]
348    fn parse_number_term() {
349        //Positive Integer
350        let text = tokenise("10".into()).unwrap();
351        let term = TokenStream::new(text.clone()).parse_term().unwrap();
352        assert_eq!(term, Term::Unit(Unit::Int(10)));
353        let term = TokenStream::new(text).parse_expression().unwrap();
354        assert_eq!(term, Term::Unit(Unit::Int(10)));
355
356        //Negative Integer
357        let text = tokenise("-10".into()).unwrap();
358        let term = TokenStream::new(text.clone()).parse_term().unwrap();
359        assert_eq!(term, Term::Unit(Unit::Int(-10)));
360        let term = TokenStream::new(text).parse_expression().unwrap();
361        assert_eq!(term, Term::Unit(Unit::Int(-10)));
362
363        //Positive Float
364        let text = tokenise("1.01".into()).unwrap();
365        let term = TokenStream::new(text.clone()).parse_term().unwrap();
366        assert_eq!(term, Term::Unit(Unit::Float(1.01)));
367        let term = TokenStream::new(text).parse_expression().unwrap();
368        assert_eq!(term, Term::Unit(Unit::Float(1.01)));
369
370        //Negative Float
371        let text = tokenise("-1.01".into()).unwrap();
372        let term = TokenStream::new(text.clone()).parse_term().unwrap();
373        assert_eq!(term, Term::Unit(Unit::Float(-1.01)));
374        let term = TokenStream::new(text).parse_expression().unwrap();
375        assert_eq!(term, Term::Unit(Unit::Float(-1.01)));
376    }
377
378    #[test]
379    fn parse_constant_term() {
380        let text = tokenise("constant".into()).unwrap();
381        let term = TokenStream::new(text.clone()).parse_term().unwrap();
382        assert_eq!(term, Term::Unit(Unit::Constant("constant".into())));
383        let term = TokenStream::new(text).parse_expression().unwrap();
384        assert_eq!(term, Term::Unit(Unit::Constant("constant".into())));
385
386        let text = tokenise("constant_1".into()).unwrap();
387        let term = TokenStream::new(text.clone()).parse_term().unwrap();
388        assert_eq!(term, Term::Unit(Unit::Constant("constant_1".into())));
389        let term = TokenStream::new(text).parse_expression().unwrap();
390        assert_eq!(term, Term::Unit(Unit::Constant("constant_1".into())));
391
392        let text = tokenise("'file/path'".into()).unwrap();
393        let term = TokenStream::new(text.clone()).parse_term().unwrap();
394        assert_eq!(term, Term::Unit(Unit::Constant("file/path".into())));
395        let term = TokenStream::new(text).parse_expression().unwrap();
396        assert_eq!(term, Term::Unit(Unit::Constant("file/path".into())));
397
398        let text = tokenise("'c*o/n\"s-t'".into()).unwrap();
399        let term = TokenStream::new(text.clone()).parse_term().unwrap();
400        assert_eq!(term, Term::Unit(Unit::Constant("c*o/n\"s-t".into())));
401        let term = TokenStream::new(text).parse_expression().unwrap();
402        assert_eq!(term, Term::Unit(Unit::Constant("c*o/n\"s-t".into())));
403    }
404
405    #[test]
406    fn parse_variable_term() {
407        let text = tokenise("Var".into()).unwrap();
408        let term = TokenStream::new(text.clone()).parse_term().unwrap();
409        assert_eq!(term, Term::Unit(Unit::Variable("Var".into())));
410        let term = TokenStream::new(text).parse_expression().unwrap();
411        assert_eq!(term, Term::Unit(Unit::Variable("Var".into())));
412
413        let text = tokenise("VAR_Under".into()).unwrap();
414        let term = TokenStream::new(text.clone()).parse_term().unwrap();
415        assert_eq!(term, Term::Unit(Unit::Variable("VAR_Under".into())));
416        let term = TokenStream::new(text).parse_expression().unwrap();
417        assert_eq!(term, Term::Unit(Unit::Variable("VAR_Under".into())));
418
419        let text = tokenise("VAR10".into()).unwrap();
420        let term = TokenStream::new(text.clone()).parse_term().unwrap();
421        assert_eq!(term, Term::Unit(Unit::Variable("VAR10".into())));
422        let term = TokenStream::new(text).parse_expression().unwrap();
423        assert_eq!(term, Term::Unit(Unit::Variable("VAR10".into())));
424
425        let text = tokenise("VAR_Under2".into()).unwrap();
426        let term = TokenStream::new(text.clone()).parse_term().unwrap();
427        assert_eq!(term, Term::Unit(Unit::Variable("VAR_Under2".into())));
428        let term = TokenStream::new(text).parse_expression().unwrap();
429        assert_eq!(term, Term::Unit(Unit::Variable("VAR_Under2".into())));
430    }
431
432    #[test]
433    fn parse_string_term() {
434        let text = tokenise("\"A String\"".into()).unwrap();
435        let term = TokenStream::new(text.clone()).parse_term().unwrap();
436        assert_eq!(term, Term::Unit(Unit::String("\"A String\"".into())));
437        let term = TokenStream::new(text).parse_expression().unwrap();
438        assert_eq!(term, Term::Unit(Unit::String("\"A String\"".into())));
439
440        let text = tokenise("\"A \\\"String\"".into()).unwrap();
441        let term = TokenStream::new(text.clone()).parse_term().unwrap();
442        assert_eq!(term, Term::Unit(Unit::String("\"A \"String\"".into())));
443        let term = TokenStream::new(text).parse_expression().unwrap();
444        assert_eq!(term, Term::Unit(Unit::String("\"A \"String\"".into())));
445
446        let text = tokenise("\"A *+-=: String\"".into()).unwrap();
447        let term = TokenStream::new(text.clone()).parse_term().unwrap();
448        assert_eq!(term, Term::Unit(Unit::String("\"A *+-=: String\"".into())));
449        let term = TokenStream::new(text).parse_expression().unwrap();
450        assert_eq!(term, Term::Unit(Unit::String("\"A *+-=: String\"".into())));
451    }
452
453    #[test]
454    fn parse_atom_term() {
455        let p = Unit::Constant("p".into());
456        let q = Unit::Variable("Q".into());
457        let x = Unit::Variable("X".into());
458        let y = Unit::Variable("Y".into());
459        let a = Unit::Constant("a".into());
460        let b = Unit::Constant("b".into());
461
462        let text = tokenise("p(X,a)".into()).unwrap();
463        let term = TokenStream::new(text.clone()).parse_term().unwrap();
464        assert_eq!(
465            term,
466            Term::Atom(
467                p.clone(),
468                vec![Term::Unit(x.clone()), Term::Unit(a.clone())]
469            )
470        );
471        let term = TokenStream::new(text).parse_expression().unwrap();
472        assert_eq!(
473            term,
474            Term::Atom(
475                p.clone(),
476                vec![Term::Unit(x.clone()), Term::Unit(a.clone())]
477            )
478        );
479
480        let text = tokenise("Q(b,Y)".into()).unwrap();
481        let term = TokenStream::new(text.clone()).parse_term().unwrap();
482        assert_eq!(
483            term,
484            Term::Atom(
485                q.clone(),
486                vec![Term::Unit(b.clone()), Term::Unit(y.clone())]
487            )
488        );
489        let term = TokenStream::new(text).parse_expression().unwrap();
490        assert_eq!(
491            term,
492            Term::Atom(
493                q.clone(),
494                vec![Term::Unit(b.clone()), Term::Unit(y.clone())]
495            )
496        );
497    }
498
499    #[test]
500    fn parse_list_term() {
501        let a = Term::Unit(Unit::Constant("a".into()));
502        let b = Term::Unit(Unit::Constant("b".into()));
503        let c = Term::Unit(Unit::Constant("c".into()));
504        let t = Term::Unit(Unit::Variable("T".into()));
505        let p = Unit::Constant("p".into());
506
507        let text = tokenise("[a,b,c]".into()).unwrap();
508        let term = TokenStream::new(text.clone()).parse_term().unwrap();
509        assert_eq!(
510            term,
511            Term::List(
512                vec![a.clone(), b.clone(), c.clone()],
513                Box::new(Term::EmptyList)
514            )
515        );
516        let term = TokenStream::new(text).parse_expression().unwrap();
517        assert_eq!(
518            term,
519            Term::List(
520                vec![a.clone(), b.clone(), c.clone()],
521                Box::new(Term::EmptyList)
522            )
523        );
524
525        let text = tokenise("[a,b,c|[]]".into()).unwrap();
526        let term = TokenStream::new(text.clone()).parse_term().unwrap();
527        assert_eq!(
528            term,
529            Term::List(
530                vec![a.clone(), b.clone(), c.clone()],
531                Box::new(Term::EmptyList)
532            )
533        );
534        let term = TokenStream::new(text).parse_expression().unwrap();
535        assert_eq!(
536            term,
537            Term::List(
538                vec![a.clone(), b.clone(), c.clone()],
539                Box::new(Term::EmptyList)
540            )
541        );
542
543        let text = tokenise("[a|T]".into()).unwrap();
544        let term = TokenStream::new(text.clone()).parse_term().unwrap();
545        assert_eq!(term, Term::List(vec![a.clone()], Box::new(t.clone())));
546        let term = TokenStream::new(text).parse_expression().unwrap();
547        assert_eq!(term, Term::List(vec![a.clone()], Box::new(t.clone())));
548
549        let text = tokenise("[a,[b,c]]".into()).unwrap();
550        let sub_list = Term::List(vec![b.clone(), c.clone()], Box::new(Term::EmptyList));
551        let term = TokenStream::new(text.clone()).parse_term().unwrap();
552        assert_eq!(
553            term,
554            Term::List(vec![a.clone(), sub_list.clone()], Box::new(Term::EmptyList))
555        );
556        let term = TokenStream::new(text).parse_expression().unwrap();
557        assert_eq!(
558            term,
559            Term::List(vec![a.clone(), sub_list.clone()], Box::new(Term::EmptyList))
560        );
561
562        let text = tokenise("p([a,[b,c|T]])".into()).unwrap();
563        let sub_list = Term::List(vec![b.clone(), c.clone()], Box::new(t.clone()));
564        let list = Term::List(vec![a.clone(), sub_list.clone()], Box::new(Term::EmptyList));
565        let term = TokenStream::new(text.clone()).parse_term().unwrap();
566        assert_eq!(term, Term::Atom(p.clone(), vec![list.clone()]));
567        let term = TokenStream::new(text).parse_expression().unwrap();
568        assert_eq!(term, Term::Atom(p.clone(), vec![list]));
569
570        let text = tokenise("[]".into()).unwrap();
571        let term = TokenStream::new(text.clone()).parse_term().unwrap();
572        assert_eq!(term, Term::EmptyList);
573        let term = TokenStream::new(text).parse_expression().unwrap();
574        assert_eq!(term, Term::EmptyList);
575    }
576
577    #[test]
578    fn parse_set_term() {
579        let a = Term::Unit(Unit::Constant("a".into()));
580        let b = Term::Unit(Unit::Constant("b".into()));
581        let c = Term::Unit(Unit::Constant("c".into()));
582        let p = Unit::Constant("p".into());
583
584        let abc = Term::Set(vec![a.clone(), b.clone(), c.clone()]);
585
586        let text = tokenise("{a,b,c}".into()).unwrap();
587        let term = TokenStream::new(text.clone()).parse_term().unwrap();
588        assert_eq!(term, abc.clone());
589        let term = TokenStream::new(text).parse_expression().unwrap();
590        assert_eq!(term, abc.clone());
591
592        let text = tokenise("p({a,b,c})".into()).unwrap();
593        let term = TokenStream::new(text.clone()).parse_term().unwrap();
594        assert_eq!(term, Term::Atom(p.clone(), vec![abc.clone()]));
595        let term = TokenStream::new(text).parse_expression().unwrap();
596        assert_eq!(term, Term::Atom(p.clone(), vec![abc.clone()]));
597
598        let text = tokenise("{a,{b,c}}".into()).unwrap();
599        let term = TokenStream::new(text.clone()).parse_term().unwrap();
600        assert_eq!(
601            term,
602            Term::Set(vec![a.clone(), Term::Set(vec![b.clone(), c.clone()])])
603        );
604        let term = TokenStream::new(text).parse_expression().unwrap();
605        assert_eq!(
606            term,
607            Term::Set(vec![a.clone(), Term::Set(vec![b.clone(), c.clone()])])
608        );
609
610        let text = tokenise("{a,{}}".into()).unwrap();
611        let term = TokenStream::new(text.clone()).parse_term().unwrap();
612        assert_eq!(term, Term::Set(vec![a.clone(), Term::Set(vec![])]));
613        let term = TokenStream::new(text).parse_expression().unwrap();
614        assert_eq!(term, Term::Set(vec![a.clone(), Term::Set(vec![])]));
615    }
616
617    #[test]
618    fn parse_tuple() {
619        let a = Term::Unit(Unit::Constant("a".into()));
620        let b = Term::Unit(Unit::Constant("b".into()));
621        let c = Term::Unit(Unit::Constant("c".into()));
622        let p = Unit::Constant("p".into());
623
624        let abc = Term::Tuple(vec![a.clone(), b.clone(), c.clone()]);
625        let bc = Term::Tuple(vec![b.clone(), c.clone()]);
626
627        let text = tokenise("(a,b,c)".into()).unwrap();
628        let term = TokenStream::new(text).parse_expression().unwrap();
629        assert_eq!(term, abc.clone());
630
631        let text = tokenise("(a,(b,c))".into()).unwrap();
632        let term = TokenStream::new(text).parse_expression().unwrap();
633        assert_eq!(term, Term::Tuple(vec![a.clone(), bc.clone()]));
634
635        //This test fails
636        let text = tokenise("(a,())".into()).unwrap();
637        let term = TokenStream::new(text).parse_expression().unwrap();
638        assert_eq!(term, Term::Tuple(vec![a.clone(), Term::Tuple(vec![])]));
639
640        let text = tokenise("p((a,b,c))".into()).unwrap();
641        let term = TokenStream::new(text).parse_expression().unwrap();
642        assert_eq!(term, Term::Atom(p, vec![abc.clone()]));
643    }
644
645    // TODO: Improve error messaging for unclosed structures
646    #[test]
647    fn unclosed_atom() {
648        let mut tokens = TokenStream::new(tokenise("p(X,Y".into()).unwrap());
649        match tokens.parse_expression() {
650            Ok(_) => panic!("Should have thrown error"),
651            Err(message) => assert_eq!(message, "Unexpected End of File"),
652        }
653
654        let mut tokens = TokenStream::new(tokenise("p(X,Y.".into()).unwrap());
655        match tokens.parse_expression() {
656            Ok(_) => panic!("Should have thrown error"),
657            Err(message) => assert_eq!(message, "Unexpected token in arguments: ."),
658        }
659
660        let mut tokens = TokenStream::new(tokenise("p(X,(Y)".into()).unwrap());
661        match tokens.parse_expression() {
662            Ok(_) => panic!("Should have thrown error"),
663            Err(message) => assert_eq!(message, "Unexpected End of File"),
664        }
665
666        let mut tokens = TokenStream::new(tokenise("p(X,(Y).".into()).unwrap());
667        match tokens.parse_expression() {
668            Ok(_) => panic!("Should have thrown error"),
669            Err(message) => assert_eq!(message, "Unexpected token in arguments: ."),
670        }
671    }
672
673    #[test]
674    fn unclosed_list() {
675        let mut tokens = TokenStream::new(tokenise("[X,Y".into()).unwrap());
676        match tokens.parse_expression() {
677            Ok(_) => panic!("Should have thrown error"),
678            Err(message) => assert_eq!(message, "Unexpected End of File"),
679        }
680
681        let mut tokens = TokenStream::new(tokenise("[X,Y.".into()).unwrap());
682        match tokens.parse_expression() {
683            Ok(_) => panic!("Should have thrown error"),
684            Err(message) => assert_eq!(message, "Unexpected token in arguments: ."),
685        }
686
687        let mut tokens = TokenStream::new(tokenise("[X,[Y]".into()).unwrap());
688        match tokens.parse_expression() {
689            Ok(_) => panic!("Should have thrown error"),
690            Err(message) => assert_eq!(message, "Unexpected End of File"),
691        }
692
693        let mut tokens = TokenStream::new(tokenise("[X,[Y].".into()).unwrap());
694        match tokens.parse_expression() {
695            Ok(_) => panic!("Should have thrown error"),
696            Err(message) => assert_eq!(message, "Unexpected token in arguments: ."),
697        }
698    }
699
700    #[test]
701    fn unclosed_set() {
702        let mut tokens = TokenStream::new(tokenise("{X,Y".into()).unwrap());
703        match tokens.parse_expression() {
704            Ok(_) => panic!("Should have thrown error"),
705            Err(message) => assert_eq!(message, "Unexpected End of File"),
706        }
707
708        let mut tokens = TokenStream::new(tokenise("{X,Y.".into()).unwrap());
709        match tokens.parse_expression() {
710            Ok(_) => panic!("Should have thrown error"),
711            Err(message) => assert_eq!(message, "Unexpected token in arguments: ."),
712        }
713
714        let mut tokens = TokenStream::new(tokenise("{X,{Y}".into()).unwrap());
715        match tokens.parse_expression() {
716            Ok(_) => panic!("Should have thrown error"),
717            Err(message) => assert_eq!(message, "Unexpected End of File"),
718        }
719
720        let mut tokens = TokenStream::new(tokenise("{X,{Y}.".into()).unwrap());
721        match tokens.parse_expression() {
722            Ok(_) => panic!("Should have thrown error"),
723            Err(message) => assert_eq!(message, "Unexpected token in arguments: ."),
724        }
725    }
726
727    #[test]
728    fn unclosed_tuple() {
729        let mut tokens = TokenStream::new(tokenise("(X,Y".into()).unwrap());
730        match tokens.parse_expression() {
731            Ok(_) => panic!("Should have thrown error"),
732            Err(message) => assert_eq!(message, "Unexpected End of File"),
733        }
734
735        let mut tokens = TokenStream::new(tokenise("(X,Y.".into()).unwrap());
736        match tokens.parse_expression() {
737            Ok(_) => panic!("Should have thrown error"),
738            Err(message) => assert_eq!(message, "Unexpected token in arguments: ."),
739        }
740
741        let mut tokens = TokenStream::new(tokenise("(X,(Y)".into()).unwrap());
742        match tokens.parse_expression() {
743            Ok(_) => panic!("Should have thrown error"),
744            Err(message) => assert_eq!(message, "Unexpected End of File"),
745        }
746
747        let mut tokens = TokenStream::new(tokenise("(X,(Y).".into()).unwrap());
748        match tokens.parse_expression() {
749            Ok(_) => panic!("Should have thrown error"),
750            Err(message) => assert_eq!(message, "Unexpected token in arguments: ."),
751        }
752    }
753
754    #[test]
755    fn infix_order() {
756        let x = Term::Unit(Unit::Variable("X".into()));
757        let _y = Term::Unit(Unit::Variable("Y".into()));
758        let one = Term::Unit(Unit::Int(1));
759        let two = Term::Unit(Unit::Int(2));
760        let three = Term::Unit(Unit::Int(3));
761        let one_and_half = Term::Unit(Unit::Float(1.5));
762        let plus = Unit::Constant("+".into());
763        let _minus = Unit::Constant("-".into());
764        let divide = Unit::Constant("/".into());
765        let _times = Unit::Constant("*".into());
766        let power = Unit::Constant("**".into());
767        let eqauls = Unit::Constant("=:=".into());
768
769        let text = tokenise("X =:= 1 + 2 / 1.5**3".into()).unwrap();
770        let term = TokenStream::new(text).parse_expression().unwrap();
771        assert_eq!(
772            term,
773            Term::Atom(
774                eqauls,
775                vec![
776                    x.clone(),
777                    Term::Atom(
778                        plus.clone(),
779                        vec![
780                            one.clone(),
781                            Term::Atom(
782                                divide.clone(),
783                                vec![
784                                    two.clone(),
785                                    Term::Atom(
786                                        power.clone(),
787                                        vec![one_and_half.clone(), three.clone()]
788                                    )
789                                ]
790                            )
791                        ]
792                    )
793                ]
794            )
795        );
796    }
797
798    #[test]
799    fn grouped_expression() {
800        let x = Term::Unit(Unit::Variable("X".into()));
801        let _y = Term::Unit(Unit::Variable("Y".into()));
802        let one = Term::Unit(Unit::Int(1));
803        let two = Term::Unit(Unit::Int(2));
804        let three = Term::Unit(Unit::Int(3));
805        let one_and_half = Term::Unit(Unit::Float(1.5));
806        let plus = Unit::Constant("+".into());
807        let _minus = Unit::Constant("-".into());
808        let divide = Unit::Constant("/".into());
809        let _times = Unit::Constant("*".into());
810        let power = Unit::Constant("**".into());
811        let equals = Unit::Constant("=:=".into());
812
813        let text = tokenise("X =:= 1 + (2 / 1.5)**3".into()).unwrap();
814        let term = TokenStream::new(text).parse_expression().unwrap();
815
816        assert_eq!(
817            term,
818            Term::Atom(
819                equals,
820                vec![
821                    x,
822                    Term::Atom(
823                        plus,
824                        vec![
825                            one,
826                            Term::Atom(
827                                power,
828                                vec![Term::Atom(divide, vec![two, one_and_half]), three]
829                            )
830                        ]
831                    )
832                ]
833            )
834        );
835    }
836
837    #[test]
838    fn tuple_or_grouped_expression() {
839        let x = Term::Unit(Unit::Variable("X".into()));
840        let y = Term::Unit(Unit::Variable("Y".into()));
841        let a = Term::Unit(Unit::Constant("a".into()));
842        let one = Term::Unit(Unit::Int(1));
843        let two = Term::Unit(Unit::Int(2));
844        let three = Term::Unit(Unit::Int(3));
845        let one_and_half = Term::Unit(Unit::Float(1.5));
846        let plus = Unit::Constant("+".into());
847        let _minus = Unit::Constant("-".into());
848        let divide = Unit::Constant("/".into());
849        let _times = Unit::Constant("*".into());
850        let power = Unit::Constant("**".into());
851        let equals = Unit::Constant("=:=".into());
852
853        let text = tokenise("(a,X =:= 1 + (2 / 1.5)**(3,Y))".into()).unwrap();
854        let term = TokenStream::new(text).parse_expression().unwrap();
855
856        assert_eq!(
857            term,
858            Term::Tuple(vec![
859                a,
860                Term::Atom(
861                    equals,
862                    vec![
863                        x,
864                        Term::Atom(
865                            plus,
866                            vec![
867                                one,
868                                Term::Atom(
869                                    power,
870                                    vec![
871                                        Term::Atom(divide, vec![two, one_and_half]),
872                                        Term::Tuple(vec![three, y])
873                                    ]
874                                )
875                            ]
876                        )
877                    ]
878                )
879            ])
880        );
881    }
882
883    #[test]
884    fn parse_rule() {
885        let mut token_stream = TokenStream::new(tokenise("gt1(X):-X>1.".into()).unwrap());
886        let clause = token_stream.parse_clause().unwrap().unwrap();
887        let head = Term::Atom(
888            Unit::Constant("gt1".into()),
889            vec![Term::Unit(Unit::Variable("X".into()))],
890        );
891        let body = Term::Atom(
892            Unit::Constant(">".into()),
893            vec![
894                Term::Unit(Unit::Variable("X".into())),
895                Term::Unit(Unit::Int(1)),
896            ],
897        );
898
899        assert_eq!(clause, TreeClause::Rule(vec![head, body]));
900        // assert_eq!(token_stream.parse_clause().unwrap(),None);
901    }
902
903    #[test]
904    fn parse_fact() {
905        let mut token_stream = TokenStream::new(tokenise("man(plato).".into()).unwrap());
906        let clause = token_stream.parse_clause().unwrap().unwrap();
907        let head = Term::Atom(
908            Unit::Constant("man".into()),
909            vec![Term::Unit(Unit::Constant("plato".into()))],
910        );
911
912        assert_eq!(clause, TreeClause::Fact(head));
913        assert_eq!(token_stream.parse_clause().unwrap(), None);
914    }
915
916    #[test]
917    fn parse_meta_rule() {
918        let mut token_stream = TokenStream::new(tokenise("P(X,Y):-Q(X,Y),{P,Q}.".into()).unwrap());
919        let clause = token_stream.parse_clause().unwrap().unwrap();
920        let head = Term::Atom(
921            Unit::Variable("P".into()),
922            vec![
923                Term::Unit(Unit::Variable("X".into())),
924                Term::Unit(Unit::Variable("Y".into())),
925            ],
926        );
927        let body = Term::Atom(
928            Unit::Variable("Q".into()),
929            vec![
930                Term::Unit(Unit::Variable("X".into())),
931                Term::Unit(Unit::Variable("Y".into())),
932            ],
933        );
934        let meta_data = Term::Set(vec![
935            Term::Unit(Unit::Variable("P".into())),
936            Term::Unit(Unit::Variable("Q".into())),
937        ]);
938
939        assert_eq!(clause, TreeClause::MetaRule(vec![head, body, meta_data]));
940        assert_eq!(token_stream.parse_clause().unwrap(), None);
941    }
942
943    #[test]
944    fn parse_meta_rule_with_unconstrained_list() {
945        // {El},[Q1,Q2] — El is constrained, Q1 and Q2 are unconstrained
946        let mut token_stream = TokenStream::new(tokenise("edge(El,Q1,Q2):-q(Q1),q(Q2),{El},[Q1,Q2].".into()).unwrap());
947        let clause = token_stream.parse_clause().unwrap().unwrap();
948        let head = Term::Atom(
949            Unit::Constant("edge".into()),
950            vec![
951                Term::Unit(Unit::Variable("El".into())),
952                Term::Unit(Unit::Variable("Q1".into())),
953                Term::Unit(Unit::Variable("Q2".into())),
954            ],
955        );
956        let body1 = Term::Atom(
957            Unit::Constant("q".into()),
958            vec![Term::Unit(Unit::Variable("Q1".into()))],
959        );
960        let body2 = Term::Atom(
961            Unit::Constant("q".into()),
962            vec![Term::Unit(Unit::Variable("Q2".into()))],
963        );
964        let constrained = Term::Set(vec![
965            Term::Unit(Unit::Variable("El".into())),
966        ]);
967        let unconstrained = Term::List(
968            vec![
969                Term::Unit(Unit::Variable("Q1".into())),
970                Term::Unit(Unit::Variable("Q2".into())),
971            ],
972            Box::new(Term::EmptyList),
973        );
974
975        assert_eq!(clause, TreeClause::MetaRule(vec![head, body1, body2, constrained, unconstrained]));
976        assert_eq!(token_stream.parse_clause().unwrap(), None);
977    }
978
979    #[test]
980    fn parse_meta_rule_list_only() {
981        // [Q1,Q2] only — no constrained variables
982        let mut token_stream = TokenStream::new(tokenise("edge(El,Q1,Q2):-q(Q1),q(Q2),[El,Q1,Q2].".into()).unwrap());
983        let clause = token_stream.parse_clause().unwrap().unwrap();
984        let head = Term::Atom(
985            Unit::Constant("edge".into()),
986            vec![
987                Term::Unit(Unit::Variable("El".into())),
988                Term::Unit(Unit::Variable("Q1".into())),
989                Term::Unit(Unit::Variable("Q2".into())),
990            ],
991        );
992        let body1 = Term::Atom(
993            Unit::Constant("q".into()),
994            vec![Term::Unit(Unit::Variable("Q1".into()))],
995        );
996        let body2 = Term::Atom(
997            Unit::Constant("q".into()),
998            vec![Term::Unit(Unit::Variable("Q2".into()))],
999        );
1000        let unconstrained = Term::List(
1001            vec![
1002                Term::Unit(Unit::Variable("El".into())),
1003                Term::Unit(Unit::Variable("Q1".into())),
1004                Term::Unit(Unit::Variable("Q2".into())),
1005            ],
1006            Box::new(Term::EmptyList),
1007        );
1008
1009        assert_eq!(clause, TreeClause::MetaRule(vec![head, body1, body2, unconstrained]));
1010        assert_eq!(token_stream.parse_clause().unwrap(), None);
1011    }
1012
1013    #[test]
1014    fn parse_meta_fact() {
1015        let mut token_stream = TokenStream::new(tokenise("Map([],[],X),{Map}.".into()).unwrap());
1016        let clause = token_stream.parse_clause().unwrap().unwrap();
1017        let head = Term::Atom(
1018            Unit::Variable("Map".into()),
1019            vec![
1020                Term::EmptyList,
1021                Term::EmptyList,
1022                Term::Unit(Unit::Variable("X".into())),
1023            ],
1024        );
1025        let meta_data = Term::Set(vec![
1026            Term::Unit(Unit::Variable("Map".into())),
1027        ]);
1028
1029        assert_eq!(clause, TreeClause::MetaFact(head, meta_data));
1030        assert_eq!(token_stream.parse_clause().unwrap(), None);
1031    }
1032
1033    #[test]
1034    fn parse_directive() {
1035        let mut token_stream =
1036            TokenStream::new(tokenise(":-test(a),['file/path'].".into()).unwrap());
1037        let clause = token_stream.parse_clause().unwrap().unwrap();
1038        let body = Term::Atom(
1039            Unit::Constant("test".into()),
1040            vec![Term::Unit(Unit::Constant("a".into()))],
1041        );
1042        let body2 = Term::List(
1043            vec![Term::Unit(Unit::Constant("file/path".into()))],
1044            Box::new(Term::EmptyList),
1045        );
1046
1047        assert_eq!(clause, TreeClause::Directive(vec![body, body2]));
1048        assert_eq!(token_stream.parse_clause().unwrap(), None);
1049    }
1050
1051    #[test]
1052    fn parse_all_clauses() {
1053        let text =
1054            "gt1(X):-X>1.\nman(plato).\nP(X,Y):-\n\tQ(X,Y),\n\t{P,Q}.\n:-test(a),['file/path']."
1055                .to_string();
1056        let mut token_stream = TokenStream::new(tokenise(text).unwrap());
1057        let clauses = token_stream.parse_all().unwrap();
1058
1059        let head = Term::Atom(
1060            Unit::Constant("gt1".into()),
1061            vec![Term::Unit(Unit::Variable("X".into()))],
1062        );
1063        let body = Term::Atom(
1064            Unit::Constant(">".into()),
1065            vec![
1066                Term::Unit(Unit::Variable("X".into())),
1067                Term::Unit(Unit::Int(1)),
1068            ],
1069        );
1070        assert_eq!(clauses[0], TreeClause::Rule(vec![head, body]));
1071
1072        let head = Term::Atom(
1073            Unit::Constant("man".into()),
1074            vec![Term::Unit(Unit::Constant("plato".into()))],
1075        );
1076        assert_eq!(clauses[1], TreeClause::Fact(head));
1077
1078        let head = Term::Atom(
1079            Unit::Variable("P".into()),
1080            vec![
1081                Term::Unit(Unit::Variable("X".into())),
1082                Term::Unit(Unit::Variable("Y".into())),
1083            ],
1084        );
1085        let body = Term::Atom(
1086            Unit::Variable("Q".into()),
1087            vec![
1088                Term::Unit(Unit::Variable("X".into())),
1089                Term::Unit(Unit::Variable("Y".into())),
1090            ],
1091        );
1092        let meta_data = Term::Set(vec![
1093            Term::Unit(Unit::Variable("P".into())),
1094            Term::Unit(Unit::Variable("Q".into())),
1095        ]);
1096        assert_eq!(
1097            clauses[2],
1098            TreeClause::MetaRule(vec![head, body, meta_data])
1099        );
1100
1101        let body = Term::Atom(
1102            Unit::Constant("test".into()),
1103            vec![Term::Unit(Unit::Constant("a".into()))],
1104        );
1105        let body2 = Term::List(
1106            vec![Term::Unit(Unit::Constant("file/path".into()))],
1107            Box::new(Term::EmptyList),
1108        );
1109        assert_eq!(clauses[3], TreeClause::Directive(vec![body, body2]));
1110    }
1111}
prolog2/parser/build_tree.rs

prolog2/parser/
build_tree.rs
