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))
277                                if matches!(tail.as_ref(), Term::EmptyList) =>
278                            {
279                                if vars
280                                    .iter()
281                                    .any(|v| !matches!(v, Term::Unit(Unit::Variable(_))))
282                                {
283                                    return Err(format!("Unconstrained variable list should only contain variables, got {:?}", vars));
284                                }
285                                // Case 2: ...{P},[Q1,Q2]. — check if second-to-last is a constrained set
286                                if len >= 2 {
287                                    if let Term::Set(eq_vars) = &literals[len - 2] {
288                                        if eq_vars.iter().any(|eq_var| {
289                                            !matches!(eq_var, Term::Unit(Unit::Variable(_)))
290                                        }) {
291                                            return Err(format!("Incorrectly formatted existentially quantified variables {:?}", eq_vars));
292                                        }
293                                    }
294                                }
295                                // Case 3: ...[Q1,Q2]. — no constrained set, just unconstrained list
296                                true
297                            }
298                            _ => false,
299                        };
300                        if meta_rule {
301                            Ok(Some(TreeClause::MetaRule(literals)))
302                        } else {
303                            Ok(Some(TreeClause::Rule(literals)))
304                        }
305                    }
306                    Some(",") => {
307                        // Could be a MetaFact: Head, {EQVars}.
308                        let meta_data = self.parse_expression()?;
309                        if let Term::Set(eq_vars) = &meta_data {
310                            if eq_vars
311                                .iter()
312                                .any(|eq_var| !matches!(eq_var, Term::Unit(Unit::Variable(_))))
313                            {
314                                return Err(format!(
315                                    "Incorrectly formatted existentially quantified variables {:?}",
316                                    eq_vars
317                                ));
318                            }
319                            self.expect(".")?;
320                            Ok(Some(TreeClause::MetaFact(
321                                literals.pop().unwrap(),
322                                meta_data,
323                            )))
324                        } else {
325                            Err(format!("Expected set of existentially quantified variables after comma in meta-fact, got {:?}", meta_data))
326                        }
327                    }
328                    Some(".") => Ok(Some(TreeClause::Fact(literals[0].clone()))),
329                    Some(token) => Err(format!(
330                        "Expected \".\", \",\", or \":-\", recieved {token}"
331                    )),
332                    None => Err("Unexpected end of file".into()),
333                }
334            }
335        }
336    }
337
338    pub fn parse_all(&mut self) -> Result<Vec<TreeClause>, String> {
339        let mut clauses = Vec::<TreeClause>::new();
340        loop {
341            match self.parse_clause() {
342                Ok(Some(clause)) => clauses.push(clause),
343                Ok(None) => return Ok(clauses),
344                Err(msg) => return Err(format!("Line {}:  {msg}", self.line)),
345            }
346        }
347    }
348}
349
350#[cfg(test)]
351mod tests {
352    use super::{
353        super::tokeniser::tokenise,
354        {Term, TokenStream, TreeClause, Unit},
355    };
356    #[test]
357    fn parse_number_term() {
358        //Positive Integer
359        let text = tokenise("10".into()).unwrap();
360        let term = TokenStream::new(text.clone()).parse_term().unwrap();
361        assert_eq!(term, Term::Unit(Unit::Int(10)));
362        let term = TokenStream::new(text).parse_expression().unwrap();
363        assert_eq!(term, Term::Unit(Unit::Int(10)));
364
365        //Negative Integer
366        let text = tokenise("-10".into()).unwrap();
367        let term = TokenStream::new(text.clone()).parse_term().unwrap();
368        assert_eq!(term, Term::Unit(Unit::Int(-10)));
369        let term = TokenStream::new(text).parse_expression().unwrap();
370        assert_eq!(term, Term::Unit(Unit::Int(-10)));
371
372        //Positive Float
373        let text = tokenise("1.01".into()).unwrap();
374        let term = TokenStream::new(text.clone()).parse_term().unwrap();
375        assert_eq!(term, Term::Unit(Unit::Float(1.01)));
376        let term = TokenStream::new(text).parse_expression().unwrap();
377        assert_eq!(term, Term::Unit(Unit::Float(1.01)));
378
379        //Negative Float
380        let text = tokenise("-1.01".into()).unwrap();
381        let term = TokenStream::new(text.clone()).parse_term().unwrap();
382        assert_eq!(term, Term::Unit(Unit::Float(-1.01)));
383        let term = TokenStream::new(text).parse_expression().unwrap();
384        assert_eq!(term, Term::Unit(Unit::Float(-1.01)));
385    }
386
387    #[test]
388    fn parse_constant_term() {
389        let text = tokenise("constant".into()).unwrap();
390        let term = TokenStream::new(text.clone()).parse_term().unwrap();
391        assert_eq!(term, Term::Unit(Unit::Constant("constant".into())));
392        let term = TokenStream::new(text).parse_expression().unwrap();
393        assert_eq!(term, Term::Unit(Unit::Constant("constant".into())));
394
395        let text = tokenise("constant_1".into()).unwrap();
396        let term = TokenStream::new(text.clone()).parse_term().unwrap();
397        assert_eq!(term, Term::Unit(Unit::Constant("constant_1".into())));
398        let term = TokenStream::new(text).parse_expression().unwrap();
399        assert_eq!(term, Term::Unit(Unit::Constant("constant_1".into())));
400
401        let text = tokenise("'file/path'".into()).unwrap();
402        let term = TokenStream::new(text.clone()).parse_term().unwrap();
403        assert_eq!(term, Term::Unit(Unit::Constant("file/path".into())));
404        let term = TokenStream::new(text).parse_expression().unwrap();
405        assert_eq!(term, Term::Unit(Unit::Constant("file/path".into())));
406
407        let text = tokenise("'c*o/n\"s-t'".into()).unwrap();
408        let term = TokenStream::new(text.clone()).parse_term().unwrap();
409        assert_eq!(term, Term::Unit(Unit::Constant("c*o/n\"s-t".into())));
410        let term = TokenStream::new(text).parse_expression().unwrap();
411        assert_eq!(term, Term::Unit(Unit::Constant("c*o/n\"s-t".into())));
412    }
413
414    #[test]
415    fn parse_variable_term() {
416        let text = tokenise("Var".into()).unwrap();
417        let term = TokenStream::new(text.clone()).parse_term().unwrap();
418        assert_eq!(term, Term::Unit(Unit::Variable("Var".into())));
419        let term = TokenStream::new(text).parse_expression().unwrap();
420        assert_eq!(term, Term::Unit(Unit::Variable("Var".into())));
421
422        let text = tokenise("VAR_Under".into()).unwrap();
423        let term = TokenStream::new(text.clone()).parse_term().unwrap();
424        assert_eq!(term, Term::Unit(Unit::Variable("VAR_Under".into())));
425        let term = TokenStream::new(text).parse_expression().unwrap();
426        assert_eq!(term, Term::Unit(Unit::Variable("VAR_Under".into())));
427
428        let text = tokenise("VAR10".into()).unwrap();
429        let term = TokenStream::new(text.clone()).parse_term().unwrap();
430        assert_eq!(term, Term::Unit(Unit::Variable("VAR10".into())));
431        let term = TokenStream::new(text).parse_expression().unwrap();
432        assert_eq!(term, Term::Unit(Unit::Variable("VAR10".into())));
433
434        let text = tokenise("VAR_Under2".into()).unwrap();
435        let term = TokenStream::new(text.clone()).parse_term().unwrap();
436        assert_eq!(term, Term::Unit(Unit::Variable("VAR_Under2".into())));
437        let term = TokenStream::new(text).parse_expression().unwrap();
438        assert_eq!(term, Term::Unit(Unit::Variable("VAR_Under2".into())));
439    }
440
441    #[test]
442    fn parse_string_term() {
443        let text = tokenise("\"A String\"".into()).unwrap();
444        let term = TokenStream::new(text.clone()).parse_term().unwrap();
445        assert_eq!(term, Term::Unit(Unit::String("\"A String\"".into())));
446        let term = TokenStream::new(text).parse_expression().unwrap();
447        assert_eq!(term, Term::Unit(Unit::String("\"A String\"".into())));
448
449        let text = tokenise("\"A \\\"String\"".into()).unwrap();
450        let term = TokenStream::new(text.clone()).parse_term().unwrap();
451        assert_eq!(term, Term::Unit(Unit::String("\"A \"String\"".into())));
452        let term = TokenStream::new(text).parse_expression().unwrap();
453        assert_eq!(term, Term::Unit(Unit::String("\"A \"String\"".into())));
454
455        let text = tokenise("\"A *+-=: String\"".into()).unwrap();
456        let term = TokenStream::new(text.clone()).parse_term().unwrap();
457        assert_eq!(term, Term::Unit(Unit::String("\"A *+-=: String\"".into())));
458        let term = TokenStream::new(text).parse_expression().unwrap();
459        assert_eq!(term, Term::Unit(Unit::String("\"A *+-=: String\"".into())));
460    }
461
462    #[test]
463    fn parse_atom_term() {
464        let p = Unit::Constant("p".into());
465        let q = Unit::Variable("Q".into());
466        let x = Unit::Variable("X".into());
467        let y = Unit::Variable("Y".into());
468        let a = Unit::Constant("a".into());
469        let b = Unit::Constant("b".into());
470
471        let text = tokenise("p(X,a)".into()).unwrap();
472        let term = TokenStream::new(text.clone()).parse_term().unwrap();
473        assert_eq!(
474            term,
475            Term::Atom(
476                p.clone(),
477                vec![Term::Unit(x.clone()), Term::Unit(a.clone())]
478            )
479        );
480        let term = TokenStream::new(text).parse_expression().unwrap();
481        assert_eq!(
482            term,
483            Term::Atom(
484                p.clone(),
485                vec![Term::Unit(x.clone()), Term::Unit(a.clone())]
486            )
487        );
488
489        let text = tokenise("Q(b,Y)".into()).unwrap();
490        let term = TokenStream::new(text.clone()).parse_term().unwrap();
491        assert_eq!(
492            term,
493            Term::Atom(
494                q.clone(),
495                vec![Term::Unit(b.clone()), Term::Unit(y.clone())]
496            )
497        );
498        let term = TokenStream::new(text).parse_expression().unwrap();
499        assert_eq!(
500            term,
501            Term::Atom(
502                q.clone(),
503                vec![Term::Unit(b.clone()), Term::Unit(y.clone())]
504            )
505        );
506    }
507
508    #[test]
509    fn parse_list_term() {
510        let a = Term::Unit(Unit::Constant("a".into()));
511        let b = Term::Unit(Unit::Constant("b".into()));
512        let c = Term::Unit(Unit::Constant("c".into()));
513        let t = Term::Unit(Unit::Variable("T".into()));
514        let p = Unit::Constant("p".into());
515
516        let text = tokenise("[a,b,c]".into()).unwrap();
517        let term = TokenStream::new(text.clone()).parse_term().unwrap();
518        assert_eq!(
519            term,
520            Term::List(
521                vec![a.clone(), b.clone(), c.clone()],
522                Box::new(Term::EmptyList)
523            )
524        );
525        let term = TokenStream::new(text).parse_expression().unwrap();
526        assert_eq!(
527            term,
528            Term::List(
529                vec![a.clone(), b.clone(), c.clone()],
530                Box::new(Term::EmptyList)
531            )
532        );
533
534        let text = tokenise("[a,b,c|[]]".into()).unwrap();
535        let term = TokenStream::new(text.clone()).parse_term().unwrap();
536        assert_eq!(
537            term,
538            Term::List(
539                vec![a.clone(), b.clone(), c.clone()],
540                Box::new(Term::EmptyList)
541            )
542        );
543        let term = TokenStream::new(text).parse_expression().unwrap();
544        assert_eq!(
545            term,
546            Term::List(
547                vec![a.clone(), b.clone(), c.clone()],
548                Box::new(Term::EmptyList)
549            )
550        );
551
552        let text = tokenise("[a|T]".into()).unwrap();
553        let term = TokenStream::new(text.clone()).parse_term().unwrap();
554        assert_eq!(term, Term::List(vec![a.clone()], Box::new(t.clone())));
555        let term = TokenStream::new(text).parse_expression().unwrap();
556        assert_eq!(term, Term::List(vec![a.clone()], Box::new(t.clone())));
557
558        let text = tokenise("[a,[b,c]]".into()).unwrap();
559        let sub_list = Term::List(vec![b.clone(), c.clone()], Box::new(Term::EmptyList));
560        let term = TokenStream::new(text.clone()).parse_term().unwrap();
561        assert_eq!(
562            term,
563            Term::List(vec![a.clone(), sub_list.clone()], Box::new(Term::EmptyList))
564        );
565        let term = TokenStream::new(text).parse_expression().unwrap();
566        assert_eq!(
567            term,
568            Term::List(vec![a.clone(), sub_list.clone()], Box::new(Term::EmptyList))
569        );
570
571        let text = tokenise("p([a,[b,c|T]])".into()).unwrap();
572        let sub_list = Term::List(vec![b.clone(), c.clone()], Box::new(t.clone()));
573        let list = Term::List(vec![a.clone(), sub_list.clone()], Box::new(Term::EmptyList));
574        let term = TokenStream::new(text.clone()).parse_term().unwrap();
575        assert_eq!(term, Term::Atom(p.clone(), vec![list.clone()]));
576        let term = TokenStream::new(text).parse_expression().unwrap();
577        assert_eq!(term, Term::Atom(p.clone(), vec![list]));
578
579        let text = tokenise("[]".into()).unwrap();
580        let term = TokenStream::new(text.clone()).parse_term().unwrap();
581        assert_eq!(term, Term::EmptyList);
582        let term = TokenStream::new(text).parse_expression().unwrap();
583        assert_eq!(term, Term::EmptyList);
584    }
585
586    #[test]
587    fn parse_set_term() {
588        let a = Term::Unit(Unit::Constant("a".into()));
589        let b = Term::Unit(Unit::Constant("b".into()));
590        let c = Term::Unit(Unit::Constant("c".into()));
591        let p = Unit::Constant("p".into());
592
593        let abc = Term::Set(vec![a.clone(), b.clone(), c.clone()]);
594
595        let text = tokenise("{a,b,c}".into()).unwrap();
596        let term = TokenStream::new(text.clone()).parse_term().unwrap();
597        assert_eq!(term, abc.clone());
598        let term = TokenStream::new(text).parse_expression().unwrap();
599        assert_eq!(term, abc.clone());
600
601        let text = tokenise("p({a,b,c})".into()).unwrap();
602        let term = TokenStream::new(text.clone()).parse_term().unwrap();
603        assert_eq!(term, Term::Atom(p.clone(), vec![abc.clone()]));
604        let term = TokenStream::new(text).parse_expression().unwrap();
605        assert_eq!(term, Term::Atom(p.clone(), vec![abc.clone()]));
606
607        let text = tokenise("{a,{b,c}}".into()).unwrap();
608        let term = TokenStream::new(text.clone()).parse_term().unwrap();
609        assert_eq!(
610            term,
611            Term::Set(vec![a.clone(), Term::Set(vec![b.clone(), c.clone()])])
612        );
613        let term = TokenStream::new(text).parse_expression().unwrap();
614        assert_eq!(
615            term,
616            Term::Set(vec![a.clone(), Term::Set(vec![b.clone(), c.clone()])])
617        );
618
619        let text = tokenise("{a,{}}".into()).unwrap();
620        let term = TokenStream::new(text.clone()).parse_term().unwrap();
621        assert_eq!(term, Term::Set(vec![a.clone(), Term::Set(vec![])]));
622        let term = TokenStream::new(text).parse_expression().unwrap();
623        assert_eq!(term, Term::Set(vec![a.clone(), Term::Set(vec![])]));
624    }
625
626    #[test]
627    fn parse_tuple() {
628        let a = Term::Unit(Unit::Constant("a".into()));
629        let b = Term::Unit(Unit::Constant("b".into()));
630        let c = Term::Unit(Unit::Constant("c".into()));
631        let p = Unit::Constant("p".into());
632
633        let abc = Term::Tuple(vec![a.clone(), b.clone(), c.clone()]);
634        let bc = Term::Tuple(vec![b.clone(), c.clone()]);
635
636        let text = tokenise("(a,b,c)".into()).unwrap();
637        let term = TokenStream::new(text).parse_expression().unwrap();
638        assert_eq!(term, abc.clone());
639
640        let text = tokenise("(a,(b,c))".into()).unwrap();
641        let term = TokenStream::new(text).parse_expression().unwrap();
642        assert_eq!(term, Term::Tuple(vec![a.clone(), bc.clone()]));
643
644        //This test fails
645        let text = tokenise("(a,())".into()).unwrap();
646        let term = TokenStream::new(text).parse_expression().unwrap();
647        assert_eq!(term, Term::Tuple(vec![a.clone(), Term::Tuple(vec![])]));
648
649        let text = tokenise("p((a,b,c))".into()).unwrap();
650        let term = TokenStream::new(text).parse_expression().unwrap();
651        assert_eq!(term, Term::Atom(p, vec![abc.clone()]));
652    }
653
654    // TODO: Improve error messaging for unclosed structures
655    #[test]
656    fn unclosed_atom() {
657        let mut tokens = TokenStream::new(tokenise("p(X,Y".into()).unwrap());
658        match tokens.parse_expression() {
659            Ok(_) => panic!("Should have thrown error"),
660            Err(message) => assert_eq!(message, "Unexpected End of File"),
661        }
662
663        let mut tokens = TokenStream::new(tokenise("p(X,Y.".into()).unwrap());
664        match tokens.parse_expression() {
665            Ok(_) => panic!("Should have thrown error"),
666            Err(message) => assert_eq!(message, "Unexpected token in arguments: ."),
667        }
668
669        let mut tokens = TokenStream::new(tokenise("p(X,(Y)".into()).unwrap());
670        match tokens.parse_expression() {
671            Ok(_) => panic!("Should have thrown error"),
672            Err(message) => assert_eq!(message, "Unexpected End of File"),
673        }
674
675        let mut tokens = TokenStream::new(tokenise("p(X,(Y).".into()).unwrap());
676        match tokens.parse_expression() {
677            Ok(_) => panic!("Should have thrown error"),
678            Err(message) => assert_eq!(message, "Unexpected token in arguments: ."),
679        }
680    }
681
682    #[test]
683    fn unclosed_list() {
684        let mut tokens = TokenStream::new(tokenise("[X,Y".into()).unwrap());
685        match tokens.parse_expression() {
686            Ok(_) => panic!("Should have thrown error"),
687            Err(message) => assert_eq!(message, "Unexpected End of File"),
688        }
689
690        let mut tokens = TokenStream::new(tokenise("[X,Y.".into()).unwrap());
691        match tokens.parse_expression() {
692            Ok(_) => panic!("Should have thrown error"),
693            Err(message) => assert_eq!(message, "Unexpected token in arguments: ."),
694        }
695
696        let mut tokens = TokenStream::new(tokenise("[X,[Y]".into()).unwrap());
697        match tokens.parse_expression() {
698            Ok(_) => panic!("Should have thrown error"),
699            Err(message) => assert_eq!(message, "Unexpected End of File"),
700        }
701
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 token in arguments: ."),
706        }
707    }
708
709    #[test]
710    fn unclosed_set() {
711        let mut tokens = TokenStream::new(tokenise("{X,Y".into()).unwrap());
712        match tokens.parse_expression() {
713            Ok(_) => panic!("Should have thrown error"),
714            Err(message) => assert_eq!(message, "Unexpected End of File"),
715        }
716
717        let mut tokens = TokenStream::new(tokenise("{X,Y.".into()).unwrap());
718        match tokens.parse_expression() {
719            Ok(_) => panic!("Should have thrown error"),
720            Err(message) => assert_eq!(message, "Unexpected token in arguments: ."),
721        }
722
723        let mut tokens = TokenStream::new(tokenise("{X,{Y}".into()).unwrap());
724        match tokens.parse_expression() {
725            Ok(_) => panic!("Should have thrown error"),
726            Err(message) => assert_eq!(message, "Unexpected End of File"),
727        }
728
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 token in arguments: ."),
733        }
734    }
735
736    #[test]
737    fn unclosed_tuple() {
738        let mut tokens = TokenStream::new(tokenise("(X,Y".into()).unwrap());
739        match tokens.parse_expression() {
740            Ok(_) => panic!("Should have thrown error"),
741            Err(message) => assert_eq!(message, "Unexpected End of File"),
742        }
743
744        let mut tokens = TokenStream::new(tokenise("(X,Y.".into()).unwrap());
745        match tokens.parse_expression() {
746            Ok(_) => panic!("Should have thrown error"),
747            Err(message) => assert_eq!(message, "Unexpected token in arguments: ."),
748        }
749
750        let mut tokens = TokenStream::new(tokenise("(X,(Y)".into()).unwrap());
751        match tokens.parse_expression() {
752            Ok(_) => panic!("Should have thrown error"),
753            Err(message) => assert_eq!(message, "Unexpected End of File"),
754        }
755
756        let mut tokens = TokenStream::new(tokenise("(X,(Y).".into()).unwrap());
757        match tokens.parse_expression() {
758            Ok(_) => panic!("Should have thrown error"),
759            Err(message) => assert_eq!(message, "Unexpected token in arguments: ."),
760        }
761    }
762
763    #[test]
764    fn infix_order() {
765        let x = Term::Unit(Unit::Variable("X".into()));
766        let _y = Term::Unit(Unit::Variable("Y".into()));
767        let one = Term::Unit(Unit::Int(1));
768        let two = Term::Unit(Unit::Int(2));
769        let three = Term::Unit(Unit::Int(3));
770        let one_and_half = Term::Unit(Unit::Float(1.5));
771        let plus = Unit::Constant("+".into());
772        let _minus = Unit::Constant("-".into());
773        let divide = Unit::Constant("/".into());
774        let _times = Unit::Constant("*".into());
775        let power = Unit::Constant("**".into());
776        let eqauls = Unit::Constant("=:=".into());
777
778        let text = tokenise("X =:= 1 + 2 / 1.5**3".into()).unwrap();
779        let term = TokenStream::new(text).parse_expression().unwrap();
780        assert_eq!(
781            term,
782            Term::Atom(
783                eqauls,
784                vec![
785                    x.clone(),
786                    Term::Atom(
787                        plus.clone(),
788                        vec![
789                            one.clone(),
790                            Term::Atom(
791                                divide.clone(),
792                                vec![
793                                    two.clone(),
794                                    Term::Atom(
795                                        power.clone(),
796                                        vec![one_and_half.clone(), three.clone()]
797                                    )
798                                ]
799                            )
800                        ]
801                    )
802                ]
803            )
804        );
805    }
806
807    #[test]
808    fn grouped_expression() {
809        let x = Term::Unit(Unit::Variable("X".into()));
810        let _y = Term::Unit(Unit::Variable("Y".into()));
811        let one = Term::Unit(Unit::Int(1));
812        let two = Term::Unit(Unit::Int(2));
813        let three = Term::Unit(Unit::Int(3));
814        let one_and_half = Term::Unit(Unit::Float(1.5));
815        let plus = Unit::Constant("+".into());
816        let _minus = Unit::Constant("-".into());
817        let divide = Unit::Constant("/".into());
818        let _times = Unit::Constant("*".into());
819        let power = Unit::Constant("**".into());
820        let equals = Unit::Constant("=:=".into());
821
822        let text = tokenise("X =:= 1 + (2 / 1.5)**3".into()).unwrap();
823        let term = TokenStream::new(text).parse_expression().unwrap();
824
825        assert_eq!(
826            term,
827            Term::Atom(
828                equals,
829                vec![
830                    x,
831                    Term::Atom(
832                        plus,
833                        vec![
834                            one,
835                            Term::Atom(
836                                power,
837                                vec![Term::Atom(divide, vec![two, one_and_half]), three]
838                            )
839                        ]
840                    )
841                ]
842            )
843        );
844    }
845
846    #[test]
847    fn tuple_or_grouped_expression() {
848        let x = Term::Unit(Unit::Variable("X".into()));
849        let y = Term::Unit(Unit::Variable("Y".into()));
850        let a = Term::Unit(Unit::Constant("a".into()));
851        let one = Term::Unit(Unit::Int(1));
852        let two = Term::Unit(Unit::Int(2));
853        let three = Term::Unit(Unit::Int(3));
854        let one_and_half = Term::Unit(Unit::Float(1.5));
855        let plus = Unit::Constant("+".into());
856        let _minus = Unit::Constant("-".into());
857        let divide = Unit::Constant("/".into());
858        let _times = Unit::Constant("*".into());
859        let power = Unit::Constant("**".into());
860        let equals = Unit::Constant("=:=".into());
861
862        let text = tokenise("(a,X =:= 1 + (2 / 1.5)**(3,Y))".into()).unwrap();
863        let term = TokenStream::new(text).parse_expression().unwrap();
864
865        assert_eq!(
866            term,
867            Term::Tuple(vec![
868                a,
869                Term::Atom(
870                    equals,
871                    vec![
872                        x,
873                        Term::Atom(
874                            plus,
875                            vec![
876                                one,
877                                Term::Atom(
878                                    power,
879                                    vec![
880                                        Term::Atom(divide, vec![two, one_and_half]),
881                                        Term::Tuple(vec![three, y])
882                                    ]
883                                )
884                            ]
885                        )
886                    ]
887                )
888            ])
889        );
890    }
891
892    #[test]
893    fn parse_rule() {
894        let mut token_stream = TokenStream::new(tokenise("gt1(X):-X>1.".into()).unwrap());
895        let clause = token_stream.parse_clause().unwrap().unwrap();
896        let head = Term::Atom(
897            Unit::Constant("gt1".into()),
898            vec![Term::Unit(Unit::Variable("X".into()))],
899        );
900        let body = Term::Atom(
901            Unit::Constant(">".into()),
902            vec![
903                Term::Unit(Unit::Variable("X".into())),
904                Term::Unit(Unit::Int(1)),
905            ],
906        );
907
908        assert_eq!(clause, TreeClause::Rule(vec![head, body]));
909        // assert_eq!(token_stream.parse_clause().unwrap(),None);
910    }
911
912    #[test]
913    fn parse_fact() {
914        let mut token_stream = TokenStream::new(tokenise("man(plato).".into()).unwrap());
915        let clause = token_stream.parse_clause().unwrap().unwrap();
916        let head = Term::Atom(
917            Unit::Constant("man".into()),
918            vec![Term::Unit(Unit::Constant("plato".into()))],
919        );
920
921        assert_eq!(clause, TreeClause::Fact(head));
922        assert_eq!(token_stream.parse_clause().unwrap(), None);
923    }
924
925    #[test]
926    fn parse_meta_rule() {
927        let mut token_stream = TokenStream::new(tokenise("P(X,Y):-Q(X,Y),{P,Q}.".into()).unwrap());
928        let clause = token_stream.parse_clause().unwrap().unwrap();
929        let head = Term::Atom(
930            Unit::Variable("P".into()),
931            vec![
932                Term::Unit(Unit::Variable("X".into())),
933                Term::Unit(Unit::Variable("Y".into())),
934            ],
935        );
936        let body = Term::Atom(
937            Unit::Variable("Q".into()),
938            vec![
939                Term::Unit(Unit::Variable("X".into())),
940                Term::Unit(Unit::Variable("Y".into())),
941            ],
942        );
943        let meta_data = Term::Set(vec![
944            Term::Unit(Unit::Variable("P".into())),
945            Term::Unit(Unit::Variable("Q".into())),
946        ]);
947
948        assert_eq!(clause, TreeClause::MetaRule(vec![head, body, meta_data]));
949        assert_eq!(token_stream.parse_clause().unwrap(), None);
950    }
951
952    #[test]
953    fn parse_meta_rule_with_unconstrained_list() {
954        // {El},[Q1,Q2] — El is constrained, Q1 and Q2 are unconstrained
955        let mut token_stream =
956            TokenStream::new(tokenise("edge(El,Q1,Q2):-q(Q1),q(Q2),{El},[Q1,Q2].".into()).unwrap());
957        let clause = token_stream.parse_clause().unwrap().unwrap();
958        let head = Term::Atom(
959            Unit::Constant("edge".into()),
960            vec![
961                Term::Unit(Unit::Variable("El".into())),
962                Term::Unit(Unit::Variable("Q1".into())),
963                Term::Unit(Unit::Variable("Q2".into())),
964            ],
965        );
966        let body1 = Term::Atom(
967            Unit::Constant("q".into()),
968            vec![Term::Unit(Unit::Variable("Q1".into()))],
969        );
970        let body2 = Term::Atom(
971            Unit::Constant("q".into()),
972            vec![Term::Unit(Unit::Variable("Q2".into()))],
973        );
974        let constrained = Term::Set(vec![Term::Unit(Unit::Variable("El".into()))]);
975        let unconstrained = Term::List(
976            vec![
977                Term::Unit(Unit::Variable("Q1".into())),
978                Term::Unit(Unit::Variable("Q2".into())),
979            ],
980            Box::new(Term::EmptyList),
981        );
982
983        assert_eq!(
984            clause,
985            TreeClause::MetaRule(vec![head, body1, body2, constrained, unconstrained])
986        );
987        assert_eq!(token_stream.parse_clause().unwrap(), None);
988    }
989
990    #[test]
991    fn parse_meta_rule_list_only() {
992        // [Q1,Q2] only — no constrained variables
993        let mut token_stream =
994            TokenStream::new(tokenise("edge(El,Q1,Q2):-q(Q1),q(Q2),[El,Q1,Q2].".into()).unwrap());
995        let clause = token_stream.parse_clause().unwrap().unwrap();
996        let head = Term::Atom(
997            Unit::Constant("edge".into()),
998            vec![
999                Term::Unit(Unit::Variable("El".into())),
1000                Term::Unit(Unit::Variable("Q1".into())),
1001                Term::Unit(Unit::Variable("Q2".into())),
1002            ],
1003        );
1004        let body1 = Term::Atom(
1005            Unit::Constant("q".into()),
1006            vec![Term::Unit(Unit::Variable("Q1".into()))],
1007        );
1008        let body2 = Term::Atom(
1009            Unit::Constant("q".into()),
1010            vec![Term::Unit(Unit::Variable("Q2".into()))],
1011        );
1012        let unconstrained = Term::List(
1013            vec![
1014                Term::Unit(Unit::Variable("El".into())),
1015                Term::Unit(Unit::Variable("Q1".into())),
1016                Term::Unit(Unit::Variable("Q2".into())),
1017            ],
1018            Box::new(Term::EmptyList),
1019        );
1020
1021        assert_eq!(
1022            clause,
1023            TreeClause::MetaRule(vec![head, body1, body2, unconstrained])
1024        );
1025        assert_eq!(token_stream.parse_clause().unwrap(), None);
1026    }
1027
1028    #[test]
1029    fn parse_meta_fact() {
1030        let mut token_stream = TokenStream::new(tokenise("Map([],[],X),{Map}.".into()).unwrap());
1031        let clause = token_stream.parse_clause().unwrap().unwrap();
1032        let head = Term::Atom(
1033            Unit::Variable("Map".into()),
1034            vec![
1035                Term::EmptyList,
1036                Term::EmptyList,
1037                Term::Unit(Unit::Variable("X".into())),
1038            ],
1039        );
1040        let meta_data = Term::Set(vec![Term::Unit(Unit::Variable("Map".into()))]);
1041
1042        assert_eq!(clause, TreeClause::MetaFact(head, meta_data));
1043        assert_eq!(token_stream.parse_clause().unwrap(), None);
1044    }
1045
1046    #[test]
1047    fn parse_directive() {
1048        let mut token_stream =
1049            TokenStream::new(tokenise(":-test(a),['file/path'].".into()).unwrap());
1050        let clause = token_stream.parse_clause().unwrap().unwrap();
1051        let body = Term::Atom(
1052            Unit::Constant("test".into()),
1053            vec![Term::Unit(Unit::Constant("a".into()))],
1054        );
1055        let body2 = Term::List(
1056            vec![Term::Unit(Unit::Constant("file/path".into()))],
1057            Box::new(Term::EmptyList),
1058        );
1059
1060        assert_eq!(clause, TreeClause::Directive(vec![body, body2]));
1061        assert_eq!(token_stream.parse_clause().unwrap(), None);
1062    }
1063
1064    #[test]
1065    fn parse_all_clauses() {
1066        let text =
1067            "gt1(X):-X>1.\nman(plato).\nP(X,Y):-\n\tQ(X,Y),\n\t{P,Q}.\n:-test(a),['file/path']."
1068                .to_string();
1069        let mut token_stream = TokenStream::new(tokenise(text).unwrap());
1070        let clauses = token_stream.parse_all().unwrap();
1071
1072        let head = Term::Atom(
1073            Unit::Constant("gt1".into()),
1074            vec![Term::Unit(Unit::Variable("X".into()))],
1075        );
1076        let body = Term::Atom(
1077            Unit::Constant(">".into()),
1078            vec![
1079                Term::Unit(Unit::Variable("X".into())),
1080                Term::Unit(Unit::Int(1)),
1081            ],
1082        );
1083        assert_eq!(clauses[0], TreeClause::Rule(vec![head, body]));
1084
1085        let head = Term::Atom(
1086            Unit::Constant("man".into()),
1087            vec![Term::Unit(Unit::Constant("plato".into()))],
1088        );
1089        assert_eq!(clauses[1], TreeClause::Fact(head));
1090
1091        let head = Term::Atom(
1092            Unit::Variable("P".into()),
1093            vec![
1094                Term::Unit(Unit::Variable("X".into())),
1095                Term::Unit(Unit::Variable("Y".into())),
1096            ],
1097        );
1098        let body = Term::Atom(
1099            Unit::Variable("Q".into()),
1100            vec![
1101                Term::Unit(Unit::Variable("X".into())),
1102                Term::Unit(Unit::Variable("Y".into())),
1103            ],
1104        );
1105        let meta_data = Term::Set(vec![
1106            Term::Unit(Unit::Variable("P".into())),
1107            Term::Unit(Unit::Variable("Q".into())),
1108        ]);
1109        assert_eq!(
1110            clauses[2],
1111            TreeClause::MetaRule(vec![head, body, meta_data])
1112        );
1113
1114        let body = Term::Atom(
1115            Unit::Constant("test".into()),
1116            vec![Term::Unit(Unit::Constant("a".into()))],
1117        );
1118        let body2 = Term::List(
1119            vec![Term::Unit(Unit::Constant("file/path".into()))],
1120            Box::new(Term::EmptyList),
1121        );
1122        assert_eq!(clauses[3], TreeClause::Directive(vec![body, body2]));
1123    }
1124}
prolog2/parser/build_tree.rs

prolog2/parser/
build_tree.rs
