From 081db5a38c7f8fa483b1d9a7c03eb4bd62c2f1c6 Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Fri, 27 Jan 2017 22:06:19 -0700 Subject: [PATCH] transition to l1 --- README.md | 57 +- src/l1/ast.rs | 112 +++ src/l1/codegen.rs | 303 ++++++++ src/l1/iterators.rs | 175 +++++ src/l1/l1_parser.lalrpop | 32 + src/l1/l1_parser.rs | 1595 ++++++++++++++++++++++++++++++++++++++ src/l1/machine.rs | 290 +++++++ src/l1/mod.rs | 5 + src/main.rs | 76 +- 9 files changed, 2573 insertions(+), 72 deletions(-) create mode 100644 src/l1/ast.rs create mode 100644 src/l1/codegen.rs create mode 100644 src/l1/iterators.rs create mode 100644 src/l1/l1_parser.lalrpop create mode 100644 src/l1/l1_parser.rs create mode 100644 src/l1/machine.rs create mode 100644 src/l1/mod.rs diff --git a/README.md b/README.md index fff321ec..9c84f6cb 100644 --- a/README.md +++ b/README.md @@ -1,13 +1,14 @@ # rusty-wam -The beginnings of the Warren Abstract Machine in Rust, according to -the progression of languages in [Warren's Abstract Machine: A Tutorial +An implementation of the Warren Abstract Machine in Rust, done +according to the progression of languages in [Warren's Abstract +Machine: A Tutorial Reconstruction](http://wambook.sourceforge.net/wambook.pdf), ending in pure Prolog. ## Progress -The language L0 is implemented as a simple REPL. It supports +The language L1 is implemented as a simple REPL. It supports unification on facts and queries without backtracking and rules without clauses, in the familiar Prolog syntax. No data types apart from atoms are currently supported. @@ -15,45 +16,44 @@ from atoms are currently supported. An example of the level of interaction currently supported is: ``` -l0> p(Z, Z). -Program stored. -l0> ?- p(Z, Z). +l1> p(Z, Z). +l1> ?- p(Z, Z). yes -l0> ?- p(Z, z). +l1> ?- p(Z, z). yes -l0> ?- p(Z, w). +l1> ?- p(Z, w). yes -l0> ?- p(z, w). +l1> clouds(are, nice). +l1> ?- p(z, w). no -l0> ?- p(w, w). +l1> ?- p(w, w). yes -l0> clouds(are, nice). -Program stored. -l0> ?- clouds(Z, Z). +l1> ?- clouds(Z, Z). no -l0> ?- clouds(Z, W). +l1> ?- clouds(Z, W). yes -l0> ?- clouds(are, W). +l1> ?- clouds(are, W). yes -l0> ?- clouds(W, nice). +l1> ?- clouds(W, nice). yes -l0> ?- clouds(nice, are). +l1> ?- clouds(nice, are). no -l0> ?- p(Z, h(Z, W), f(W)). +l1> ?- p(Z, h(Z, W), f(W)). no -l0> p(Z, h(Z, W), f(W)). -Program stored. -l0> ?- p(z, h(z, z), f(w)). +l1> p(Z, h(Z, W), f(W)). +l1> ?- p(z, h(z, z), f(w)). no -l0> ?- p(z, h(z, w), f(w)). +l1> ?- p(z, h(z, w), f(w)). yes -l0> ?- p(Z, h(z, W), f(w)). +l1> ?- p(Z, h(z, W), f(w)). yes -l0> ?- p(z, h(Z, w), f(w)). +l1> ?- p(z, h(Z, w), f(w)). yes -l0> ?- p(z, h(Z, w), f(Z)). +l1> ?- p(Z, h(Z, w), f(Z)). +yes +l1> ?- p(z, h(Z, w), f(Z)). no -l0> quit +l1> quit ``` ## Occurs check @@ -61,8 +61,7 @@ l0> quit There's no occurs check, so cyclic terms do unify: ``` -l0> p(W, W). -Program stored. -l0> ?- p(f(f(W)), W). +l1> p(W, W). +l1> ?- p(f(f(W)), W). yes ``` \ No newline at end of file diff --git a/src/l1/ast.rs b/src/l1/ast.rs new file mode 100644 index 00000000..74c50915 --- /dev/null +++ b/src/l1/ast.rs @@ -0,0 +1,112 @@ +use std::cell::Cell; +use std::fmt; +use std::vec::Vec; + +pub type Var = String; + +pub type Atom = String; + +pub enum TopLevel { + Fact(Term), + Query(Term) +} + +#[derive(Clone, Copy)] +pub enum Level { + Shallow, Deep +} + +impl fmt::Display for Level { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match self { + &Level::Shallow => write!(f, "A"), + &Level::Deep => write!(f, "X") + } + } +} + +#[derive(Clone, Copy)] +pub enum Reg { + ArgAndNorm(usize, usize), + Norm(usize) +} + +impl Reg { + pub fn has_arg(&self) -> bool { + match self { + &Reg::ArgAndNorm(_, _) => true, + _ => false + } + } + + pub fn norm(&self) -> usize { + match self { + &Reg::ArgAndNorm(_, norm) | &Reg::Norm(norm) => norm + } + } +} + +pub enum Term { + Atom(Cell, Atom), + Clause(Cell, Atom, Vec>), + Var(Cell, Var) +} + +pub enum TermRef<'a> { + Atom(Level, &'a Cell, &'a Atom), + Clause(Level, &'a Cell, &'a Atom, &'a Vec>), + Var(Level, &'a Cell, &'a Var) +} + +#[derive(Clone)] +pub enum FactInstruction { + GetStructure(Level, Atom, usize, usize), + GetValue(usize, usize), + GetVariable(usize, usize), + Proceed, + UnifyVariable(usize), + UnifyValue(usize) +} + +pub enum QueryInstruction { + Call(Atom, usize), + PutStructure(Level, Atom, usize, usize), + PutValue(usize, usize), + PutVariable(usize, usize), + SetVariable(usize), + SetValue(usize), +} + +pub type CompiledFact = Vec; + +pub type CompiledQuery = Vec; + +#[derive(Clone, Copy, PartialEq)] +pub enum Addr { + HeapCell(usize), + RegNum(usize) +} + +impl Term { + pub fn subterms(&self) -> usize { + match self { + &Term::Clause(_, _, ref terms) => terms.len(), + _ => 1 + } + } + + pub fn name(&self) -> &Atom { + match self { + &Term::Atom(_, ref atom) + | &Term::Var(_, ref atom) + | &Term::Clause(_, ref atom, _) => atom + } + } + + pub fn arity(&self) -> usize { + match self { + &Term::Atom(_, _) | &Term::Var(_, _) => 0, + &Term::Clause(_, _, ref child_terms) => child_terms.len() + } + } +} diff --git a/src/l1/codegen.rs b/src/l1/codegen.rs new file mode 100644 index 00000000..b0027d9e --- /dev/null +++ b/src/l1/codegen.rs @@ -0,0 +1,303 @@ +use l1::ast::{Atom, CompiledFact, CompiledQuery, FactInstruction, + Level, QueryInstruction, Reg, Term, TermRef, Var}; +use l1::iterators::{FactIterator, QueryIterator}; + +use std::cell::Cell; +use std::collections::HashMap; +use std::fmt; +use std::vec::Vec; + +impl fmt::Display for QueryInstruction { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match self { + &QueryInstruction::Call(ref name, ref arity) => + write!(f, "call {}/{}", name, arity), + &QueryInstruction::PutStructure(ref lvl, ref a, ref s, ref r) => + write!(f, "put_structure {}/{}, {}{}", a, s, lvl, r), + &QueryInstruction::PutValue(ref a, ref x) => + write!(f, "put_value X{}, A{}", x, a), + &QueryInstruction::PutVariable(ref a, ref x) => + write!(f, "put_variable X{}, A{}", x, a), + &QueryInstruction::SetVariable(ref r) => + write!(f, "set_variable X{}", r), + &QueryInstruction::SetValue(ref r) => + write!(f, "set_value X{}", r), + } + } +} + +impl fmt::Display for FactInstruction { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match self { + &FactInstruction::GetStructure(ref lvl, ref a, ref s, ref r) => + write!(f, "get_structure {}/{}, {}{}", a, s, lvl, r), + &FactInstruction::GetValue(ref a, ref x) => + write!(f, "get_value X{}, A{}", x, a), + &FactInstruction::GetVariable(ref a, ref x) => + write!(f, "get_variable X{}, A{}", x, a), + &FactInstruction::Proceed => + write!(f, "proceed"), + &FactInstruction::UnifyVariable(ref r) => + write!(f, "unify_variable X{}", r), + &FactInstruction::UnifyValue(ref r) => + write!(f, "unify_value X{}", r) + } + } +} + +struct TermMarker<'a> { + bindings: HashMap<&'a Var, Reg>, + arg_c: usize, + norm_c: usize +} + +impl<'a> TermMarker<'a> { + fn new(term: &'a Term) -> TermMarker<'a> { + TermMarker { bindings: HashMap::new(), + arg_c: 1, + norm_c: term.subterms() + 1 } + } + + fn contains_var(&self, var: &'a Var) -> bool { + self.bindings.contains_key(var) + } + + fn get(&self, var: &'a Var) -> Reg { + *self.bindings.get(var).unwrap() + } + + fn insert(&mut self, var: &'a Var, r: Reg) { + self.bindings.insert(var, r); + } + + fn mark_non_var(&mut self, lvl: Level, cell: &Cell) { + if cell.get() == 0 { + match lvl { + Level::Deep => { + let norm = self.norm_c; + self.norm_c += 1; + cell.set(norm); + }, + Level::Shallow => { + let arg = self.arg_c; + self.arg_c += 1; + cell.set(arg); + } + }; + } + } + + fn mark_var(&mut self, lvl: Level, var: &'a Var) -> Reg { + if self.contains_var(var) { + let reg = self.get(var); + + match lvl { + Level::Deep => Reg::Norm(reg.norm()), + Level::Shallow if reg.has_arg() => { + let arg = self.arg_c; + self.arg_c += 1; + + Reg::ArgAndNorm(arg, reg.norm()) + }, + Level::Shallow => { + let norm = reg.norm(); + let reg = Reg::ArgAndNorm(self.arg_c, norm); + + self.arg_c += 1; + self.insert(var, reg); + + reg + } + } + } else { + let reg = match lvl { + Level::Deep => Reg::Norm(self.norm_c), + Level::Shallow => { + let reg = Reg::ArgAndNorm(self.arg_c, self.norm_c); + self.arg_c += 1; + reg + } + }; + + self.norm_c += 1; + self.insert(var, reg); + reg + } + } +} + +trait CompilationTarget<'a> { + type Iterator : Iterator>; + + fn iter(&'a Term) -> Self::Iterator; + + fn to_structure(Level, Atom, usize, usize) -> Self; + + fn argument_to_variable(usize, usize) -> Self; + fn argument_to_value(usize, usize) -> Self; + fn subterm_to_variable(usize) -> Self; + fn subterm_to_value(usize) -> Self; +} + +impl<'a> CompilationTarget<'a> for FactInstruction { + type Iterator = FactIterator<'a>; + + fn iter(term: &'a Term) -> Self::Iterator { + term.breadth_first_iter() + } + + fn to_structure(lvl: Level, atom: Atom, arity: usize, cell_num: usize) -> Self { + FactInstruction::GetStructure(lvl, atom, arity, cell_num) + } + + fn argument_to_variable(arg: usize, val: usize) -> Self { + FactInstruction::GetVariable(arg, val) + } + + fn argument_to_value(arg: usize, val: usize) -> Self { + FactInstruction::GetValue(arg, val) + } + + fn subterm_to_variable(val: usize) -> Self { + FactInstruction::UnifyVariable(val) + } + + fn subterm_to_value(val: usize) -> Self { + FactInstruction::UnifyValue(val) + } +} + +impl<'a> CompilationTarget<'a> for QueryInstruction { + type Iterator = QueryIterator<'a>; + + fn iter(term: &'a Term) -> Self::Iterator { + term.post_order_iter() + } + + fn to_structure(lvl: Level, atom: Atom, arity: usize, cell_num: usize) -> Self { + QueryInstruction::PutStructure(lvl, atom, arity, cell_num) + } + + fn argument_to_variable(arg: usize, val: usize) -> Self { + QueryInstruction::PutVariable(arg, val) + } + + fn argument_to_value(arg: usize, val: usize) -> Self { + QueryInstruction::PutValue(arg, val) + } + + fn subterm_to_variable(val: usize) -> Self { + QueryInstruction::SetVariable(val) + } + + fn subterm_to_value(val: usize) -> Self { + QueryInstruction::SetValue(val) + } +} + +fn to_structure<'a, Target>(tm: &mut TermMarker<'a>, + lvl: Level, + name: &'a Atom, + cell: &'a Cell, + arity: usize) + -> Target + where Target: CompilationTarget<'a> +{ + tm.mark_non_var(lvl, cell); + Target::to_structure(lvl, name.clone(), arity, cell.get()) +} + +fn non_var_subterm<'a, Target>(tm: &mut TermMarker<'a>, cell: &'a Cell) + -> Target + where Target: CompilationTarget<'a> +{ + tm.mark_non_var(Level::Deep, cell); + Target::subterm_to_value(cell.get()) // should be to_value?? +} + +fn var_term<'a, Target>(tm: &mut TermMarker<'a>, + lvl: Level, + cell: &'a Cell, + var: &'a Var) + -> Target + where Target: CompilationTarget<'a> +{ + if !tm.contains_var(var) { + let reg = tm.mark_var(lvl, var); + cell.set(reg); + + match reg { + Reg::ArgAndNorm(arg, norm) => + Target::argument_to_variable(arg, norm), + Reg::Norm(norm) => + Target::subterm_to_variable(norm) + } + } else { + let reg = tm.mark_var(lvl, var); + cell.set(reg); + + match reg { + Reg::ArgAndNorm(arg, norm) => + Target::argument_to_value(arg, norm), + Reg::Norm(norm) => + Target::subterm_to_value(norm) + } + } +} + +fn subterm_to_instr<'a, Target>(tm: &mut TermMarker<'a>, + subterm: &'a Term) + -> Target + where Target: CompilationTarget<'a> +{ + match subterm { + &Term::Atom(ref cell, _) | &Term::Clause(ref cell, _, _) => + non_var_subterm(tm, cell), + &Term::Var(ref cell, ref var) => + var_term(tm, Level::Deep, cell, var) + } +} + +fn compile_target<'a, Target>(term: &'a Term) -> Vec + where Target: CompilationTarget<'a> +{ + let iter = Target::iter(term); + let mut target = Vec::::new(); + let mut marker = TermMarker::new(term); + + for term in iter { + match term { + TermRef::Atom(lvl, term, atom) => + target.push(to_structure(&mut marker, lvl, atom, term, 0)), + TermRef::Clause(lvl, term, atom, terms) => { + target.push(to_structure(&mut marker, lvl, atom, term, terms.len())); + + for subterm in terms { + target.push(subterm_to_instr(&mut marker, subterm.as_ref())); + } + }, + TermRef::Var(lvl @ Level::Shallow, ref cell, ref var) => + target.push(var_term(&mut marker, lvl, cell, var)), + _ => {} + }; + } + + target +} + +pub fn compile_fact(term: &Term) -> CompiledFact { + let mut compiled_fact = compile_target(term); + + compiled_fact.push(FactInstruction::Proceed); + compiled_fact +} + +pub fn compile_query(term: &Term) -> CompiledQuery { + let mut compiled_query = compile_target(term); + + if let &Term::Clause(_, ref atom, ref terms) = term { + compiled_query.push(QueryInstruction::Call(atom.clone(), terms.len())); + } + + compiled_query +} diff --git a/src/l1/iterators.rs b/src/l1/iterators.rs new file mode 100644 index 00000000..87c7bd40 --- /dev/null +++ b/src/l1/iterators.rs @@ -0,0 +1,175 @@ +use l1::ast::{Atom, Level, Reg, Term, TermRef, Var}; + +use std::cell::Cell; +use std::collections::VecDeque; +use std::vec::Vec; + +enum IteratorState<'a> { + Atom(Level, &'a Cell, &'a Atom), + Clause(Level, usize, &'a Cell, &'a Atom, &'a Vec>), + IsolatedAtom(&'a Cell, &'a Atom), + IsolatedVar(&'a Cell, &'a Var), + RootClause(usize, &'a Vec>), + Var(Level, &'a Cell, &'a Var) +} + +impl<'a> IteratorState<'a> { + fn to_state(lvl: Level, term: &'a Term) -> IteratorState<'a> + { + match term { + &Term::Atom(ref cell, ref atom) => + IteratorState::Atom(lvl, cell, atom), + &Term::Clause(ref cell, ref atom, ref child_terms) => + IteratorState::Clause(lvl, 0, cell, atom, child_terms), + &Term::Var(ref cell, ref var) => + IteratorState::Var(lvl, cell, var) + } + } +} + +pub struct QueryIterator<'a> { + state_stack: Vec> +} + +impl<'a> QueryIterator<'a> { + fn push_clause(&mut self, + lvl: Level, + child_num: usize, + cell: &'a Cell, + name: &'a Atom, + child_terms: &'a Vec>) + { + self.state_stack.push(IteratorState::Clause(lvl, + child_num, + cell, + name, + child_terms)); + } + + fn push_root_clause(&mut self, + child_num: usize, + child_terms: &'a Vec>) + { + self.state_stack.push(IteratorState::RootClause(child_num, child_terms)); + } + + fn push_subterm(&mut self, lvl: Level, term: &'a Term) { + self.state_stack.push(IteratorState::to_state(lvl, term)); + } + + fn new(term: &'a Term) -> QueryIterator<'a> { + let state = match term { + &Term::Atom(ref cell, ref atom) => + IteratorState::IsolatedAtom(cell, atom), + &Term::Clause(_, _, ref terms) => + IteratorState::RootClause(0, terms), + &Term::Var(ref cell, ref var) => + IteratorState::IsolatedVar(cell, var) + }; + + QueryIterator { state_stack: vec![state] } + } +} + +impl<'a> Iterator for QueryIterator<'a> { + type Item = TermRef<'a>; + + fn next(&mut self) -> Option { + while let Some(iter_state) = self.state_stack.pop() { + match iter_state { + IteratorState::Atom(lvl, cell, atom) => + return Some(TermRef::Atom(lvl, cell, atom)), + IteratorState::Clause(lvl, child_num, cell, atom, child_terms) => { + if child_num == child_terms.len() { + return Some(TermRef::Clause(lvl, cell, atom, child_terms)); + } else { + self.push_clause(lvl, child_num + 1, cell, atom, child_terms); + self.push_subterm(Level::Deep, child_terms[child_num].as_ref()); + } + }, + IteratorState::IsolatedAtom(cell, atom) => + return Some(TermRef::Atom(Level::Shallow, cell, atom)), + IteratorState::IsolatedVar(cell, var) => + return Some(TermRef::Var(Level::Shallow, cell, var)), + IteratorState::RootClause(child_num, child_terms) => { + if child_num == child_terms.len() { + return None; + } else { + self.push_root_clause(child_num + 1, child_terms); + self.push_subterm(Level::Shallow, child_terms[child_num].as_ref()); + } + }, + IteratorState::Var(lvl, cell, var) => + return Some(TermRef::Var(lvl, cell, var)) + }; + } + + None + } +} + +pub struct FactIterator<'a> { + state_queue: VecDeque>, +} + +impl<'a> FactIterator<'a> { + fn push_subterm(&mut self, lvl: Level, term: &'a Term) { + self.state_queue.push_back(IteratorState::to_state(lvl, term)); + } + + fn new(term: &'a Term) -> FactIterator<'a> { + let states = match term { + &Term::Atom(ref cell, ref atom) => + vec![IteratorState::IsolatedAtom(cell, atom)], + &Term::Clause(_, _, ref terms) => + vec![IteratorState::RootClause(0, terms)], + &Term::Var(ref cell, ref var) => + vec![IteratorState::IsolatedVar(cell, var)] + }; + + FactIterator { state_queue: VecDeque::from(states) } + } +} + +impl<'a> Iterator for FactIterator<'a> { + type Item = TermRef<'a>; + + fn next(&mut self) -> Option { + while let Some(state) = self.state_queue.pop_front() { + match state { + IteratorState::Atom(lvl, cell, atom) => + return Some(TermRef::Atom(lvl, cell, atom)), + IteratorState::Clause(lvl, _, cell, atom, child_terms) => { + for child_term in child_terms { + self.push_subterm(Level::Deep, child_term); + } + + return Some(TermRef::Clause(lvl, cell, atom, child_terms)); + }, + IteratorState::IsolatedAtom(cell, atom) => + return Some(TermRef::Atom(Level::Shallow, cell, atom)), + IteratorState::IsolatedVar(cell, var) => + return Some(TermRef::Var(Level::Shallow, cell, var)), + IteratorState::RootClause(_, child_terms) => { + for child_term in child_terms { + self.push_subterm(Level::Shallow, child_term); + } + }, + IteratorState::Var(lvl, cell, var) => + return Some(TermRef::Var(lvl, cell, var)) + } + } + + None + } +} + +impl Term { + pub fn post_order_iter(&self) -> QueryIterator { + QueryIterator::new(self) + } + + pub fn breadth_first_iter(&self) -> FactIterator { + FactIterator::new(self) + } +} diff --git a/src/l1/l1_parser.lalrpop b/src/l1/l1_parser.lalrpop new file mode 100644 index 00000000..7fc5f556 --- /dev/null +++ b/src/l1/l1_parser.lalrpop @@ -0,0 +1,32 @@ +use std::cell::Cell; + +use l1::ast::{Atom, Reg, Term, TopLevel, Var}; + +grammar; + +pub TopLevel: TopLevel = { + "?-" "." => TopLevel::Query(t), + "." => TopLevel::Fact(t), +}; + +Atom : Atom = { + r"[a-z][a-z0-9_]*" => <>.trim().to_string(), +}; + +Var : Var = { + r"[A-Z][a-z0-9_]*" => <>.trim().to_string(), +}; + +BoxedTerm : Box = { + => Box::new(t), +}; + +Term : Term = { + "(" ",")*> ")" => { + let mut ts = ts; + ts.push(t); + Term::Clause(Cell::new(0), a, ts) + }, + => Term::Atom(Cell::new(0), <>), + => Term::Var(Cell::new(Reg::Norm(0)), <>) +}; diff --git a/src/l1/l1_parser.rs b/src/l1/l1_parser.rs new file mode 100644 index 00000000..5edea879 --- /dev/null +++ b/src/l1/l1_parser.rs @@ -0,0 +1,1595 @@ +use std::cell::Cell; +use l1::ast::{Atom, Reg, Term, TopLevel, Var}; +extern crate lalrpop_util as __lalrpop_util; + +mod __parse__TopLevel { + #![allow(non_snake_case, non_camel_case_types, unused_mut, unused_variables, unused_imports)] + + use std::cell::Cell; + use l1::ast::{Atom, Reg, Term, TopLevel, Var}; + extern crate lalrpop_util as __lalrpop_util; + #[allow(dead_code)] + pub enum __Symbol<'input> { + Term_22_28_22(&'input str), + Term_22_29_22(&'input str), + Term_22_2c_22(&'input str), + Term_22_2e_22(&'input str), + Term_22_3f_2d_22(&'input str), + Termr_23_22_5bA_2dZ_5d_5ba_2dz0_2d9___5d_2a_22_23(&'input str), + Termr_23_22_5ba_2dz_5d_5ba_2dz0_2d9___5d_2a_22_23(&'input str), + Nt_28_3cBoxedTerm_3e_20_22_2c_22_29(Box), + Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2a(::std::vec::Vec>), + Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2b(::std::vec::Vec>), + NtAtom(Atom), + NtBoxedTerm(Box), + NtTerm(Term), + NtTopLevel(TopLevel), + NtVar(Var), + Nt____TopLevel(TopLevel), + } + const __ACTION: &'static [i32] = &[ + // State 0 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 6, // on "?-", goto 5 + 7, // on r#"[A-Z][a-z0-9_]*"#, goto 6 + 8, // on r#"[a-z][a-z0-9_]*"#, goto 7 + // State 1 + 9, // on "(", goto 8 + 0, // on ")", error + 0, // on ",", error + -10, // on ".", reduce `Term = Atom => ActionFn(7);` + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 2 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 10, // on ".", goto 9 + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 3 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 4 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + -11, // on ".", reduce `Term = Var => ActionFn(8);` + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 5 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + 7, // on r#"[A-Z][a-z0-9_]*"#, goto 6 + 8, // on r#"[a-z][a-z0-9_]*"#, goto 7 + // State 6 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + -14, // on ".", reduce `Var = r#"[A-Z][a-z0-9_]*"# => ActionFn(4);` + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 7 + -6, // on "(", reduce `Atom = r#"[a-z][a-z0-9_]*"# => ActionFn(3);` + 0, // on ")", error + 0, // on ",", error + -6, // on ".", reduce `Atom = r#"[a-z][a-z0-9_]*"# => ActionFn(3);` + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 8 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + 17, // on r#"[A-Z][a-z0-9_]*"#, goto 16 + 18, // on r#"[a-z][a-z0-9_]*"#, goto 17 + // State 9 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 10 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 19, // on ".", goto 18 + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 11 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + 17, // on r#"[A-Z][a-z0-9_]*"#, goto 16 + 18, // on r#"[a-z][a-z0-9_]*"#, goto 17 + // State 12 + 21, // on "(", goto 20 + -10, // on ")", reduce `Term = Atom => ActionFn(7);` + -10, // on ",", reduce `Term = Atom => ActionFn(7);` + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 13 + 0, // on "(", error + 22, // on ")", goto 21 + 23, // on ",", goto 22 + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 14 + 0, // on "(", error + -7, // on ")", reduce `BoxedTerm = Term => ActionFn(5);` + -7, // on ",", reduce `BoxedTerm = Term => ActionFn(5);` + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 15 + 0, // on "(", error + -11, // on ")", reduce `Term = Var => ActionFn(8);` + -11, // on ",", reduce `Term = Var => ActionFn(8);` + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 16 + 0, // on "(", error + -14, // on ")", reduce `Var = r#"[A-Z][a-z0-9_]*"# => ActionFn(4);` + -14, // on ",", reduce `Var = r#"[A-Z][a-z0-9_]*"# => ActionFn(4);` + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 17 + -6, // on "(", reduce `Atom = r#"[a-z][a-z0-9_]*"# => ActionFn(3);` + -6, // on ")", reduce `Atom = r#"[a-z][a-z0-9_]*"# => ActionFn(3);` + -6, // on ",", reduce `Atom = r#"[a-z][a-z0-9_]*"# => ActionFn(3);` + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 18 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 19 + 0, // on "(", error + 24, // on ")", goto 23 + 25, // on ",", goto 24 + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 20 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + 17, // on r#"[A-Z][a-z0-9_]*"#, goto 16 + 18, // on r#"[a-z][a-z0-9_]*"#, goto 17 + // State 21 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + -8, // on ".", reduce `Term = Atom, "(", BoxedTerm, ")" => ActionFn(16);` + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 22 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + -4, // on r#"[A-Z][a-z0-9_]*"#, reduce `( ",")+ = BoxedTerm, "," => ActionFn(14);` + -4, // on r#"[a-z][a-z0-9_]*"#, reduce `( ",")+ = BoxedTerm, "," => ActionFn(14);` + // State 23 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + -9, // on ".", reduce `Term = Atom, "(", ( ",")+, BoxedTerm, ")" => ActionFn(17);` + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 24 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + -5, // on r#"[A-Z][a-z0-9_]*"#, reduce `( ",")+ = ( ",")+, BoxedTerm, "," => ActionFn(15);` + -5, // on r#"[a-z][a-z0-9_]*"#, reduce `( ",")+ = ( ",")+, BoxedTerm, "," => ActionFn(15);` + // State 25 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + 17, // on r#"[A-Z][a-z0-9_]*"#, goto 16 + 18, // on r#"[a-z][a-z0-9_]*"#, goto 17 + // State 26 + 0, // on "(", error + 29, // on ")", goto 28 + 23, // on ",", goto 22 + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 27 + 0, // on "(", error + 30, // on ")", goto 29 + 25, // on ",", goto 24 + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 28 + 0, // on "(", error + -8, // on ")", reduce `Term = Atom, "(", BoxedTerm, ")" => ActionFn(16);` + -8, // on ",", reduce `Term = Atom, "(", BoxedTerm, ")" => ActionFn(16);` + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 29 + 0, // on "(", error + -9, // on ")", reduce `Term = Atom, "(", ( ",")+, BoxedTerm, ")" => ActionFn(17);` + -9, // on ",", reduce `Term = Atom, "(", ( ",")+, BoxedTerm, ")" => ActionFn(17);` + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + ]; + const __EOF_ACTION: &'static [i32] = &[ + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + -15, // on EOF, reduce `__TopLevel = TopLevel => ActionFn(0);` + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + -13, // on EOF, reduce `TopLevel = Term, "." => ActionFn(2);` + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + -12, // on EOF, reduce `TopLevel = "?-", Term, "." => ActionFn(1);` + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + ]; + const __GOTO: &'static [i32] = &[ + // State 0 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 2, // on Atom, goto 1 + 0, // on BoxedTerm, error + 3, // on Term, goto 2 + 4, // on TopLevel, goto 3 + 5, // on Var, goto 4 + 0, // on __TopLevel, error + // State 1 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 2 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 3 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 4 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 5 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 2, // on Atom, goto 1 + 0, // on BoxedTerm, error + 11, // on Term, goto 10 + 0, // on TopLevel, error + 5, // on Var, goto 4 + 0, // on __TopLevel, error + // State 6 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 7 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 8 + 0, // on ( ","), error + 0, // on ( ",")*, error + 12, // on ( ",")+, goto 11 + 13, // on Atom, goto 12 + 14, // on BoxedTerm, goto 13 + 15, // on Term, goto 14 + 0, // on TopLevel, error + 16, // on Var, goto 15 + 0, // on __TopLevel, error + // State 9 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 10 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 11 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 13, // on Atom, goto 12 + 20, // on BoxedTerm, goto 19 + 15, // on Term, goto 14 + 0, // on TopLevel, error + 16, // on Var, goto 15 + 0, // on __TopLevel, error + // State 12 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 13 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 14 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 15 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 16 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 17 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 18 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 19 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 20 + 0, // on ( ","), error + 0, // on ( ",")*, error + 26, // on ( ",")+, goto 25 + 13, // on Atom, goto 12 + 27, // on BoxedTerm, goto 26 + 15, // on Term, goto 14 + 0, // on TopLevel, error + 16, // on Var, goto 15 + 0, // on __TopLevel, error + // State 21 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 22 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 23 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 24 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 25 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 13, // on Atom, goto 12 + 28, // on BoxedTerm, goto 27 + 15, // on Term, goto 14 + 0, // on TopLevel, error + 16, // on Var, goto 15 + 0, // on __TopLevel, error + // State 26 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 27 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 28 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 29 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + ]; + pub fn parse_TopLevel< + 'input, + >( + input: &'input str, + ) -> Result> + { + let mut __tokens = super::__intern_token::__Matcher::new(input); + let mut __states = vec![0_i32]; + let mut __symbols = vec![]; + '__shift: loop { + let __lookahead = match __tokens.next() { + Some(Ok(v)) => v, + None => break '__shift, + Some(Err(e)) => return Err(e), + }; + let __integer = match __lookahead { + (_, (0, _), _) if true => 0, + (_, (1, _), _) if true => 1, + (_, (2, _), _) if true => 2, + (_, (3, _), _) if true => 3, + (_, (4, _), _) if true => 4, + (_, (5, _), _) if true => 5, + (_, (6, _), _) if true => 6, + _ => { + return Err(__lalrpop_util::ParseError::UnrecognizedToken { + token: Some(__lookahead), + expected: vec![], + }); + } + }; + loop { + let __state = *__states.last().unwrap() as usize; + let __action = __ACTION[__state * 7 + __integer]; + if __action > 0 { + let __symbol = match __integer { + 0 => match __lookahead.1 { + (0, __tok0) => __Symbol::Term_22_28_22(__tok0), + _ => unreachable!(), + }, + 1 => match __lookahead.1 { + (1, __tok0) => __Symbol::Term_22_29_22(__tok0), + _ => unreachable!(), + }, + 2 => match __lookahead.1 { + (2, __tok0) => __Symbol::Term_22_2c_22(__tok0), + _ => unreachable!(), + }, + 3 => match __lookahead.1 { + (3, __tok0) => __Symbol::Term_22_2e_22(__tok0), + _ => unreachable!(), + }, + 4 => match __lookahead.1 { + (4, __tok0) => __Symbol::Term_22_3f_2d_22(__tok0), + _ => unreachable!(), + }, + 5 => match __lookahead.1 { + (5, __tok0) => __Symbol::Termr_23_22_5bA_2dZ_5d_5ba_2dz0_2d9___5d_2a_22_23(__tok0), + _ => unreachable!(), + }, + 6 => match __lookahead.1 { + (6, __tok0) => __Symbol::Termr_23_22_5ba_2dz_5d_5ba_2dz0_2d9___5d_2a_22_23(__tok0), + _ => unreachable!(), + }, + _ => unreachable!(), + }; + __states.push(__action - 1); + __symbols.push((__lookahead.0, __symbol, __lookahead.2)); + continue '__shift; + } else if __action < 0 { + if let Some(r) = __reduce(input, __action, Some(&__lookahead.0), &mut __states, &mut __symbols) { + return r; + } + } else { + return Err(__lalrpop_util::ParseError::UnrecognizedToken { + token: Some(__lookahead), + expected: vec![], + }); + } + } + } + loop { + let __state = *__states.last().unwrap() as usize; + let __action = __EOF_ACTION[__state]; + if __action < 0 { + if let Some(r) = __reduce(input, __action, None, &mut __states, &mut __symbols) { + return r; + } + } else { + return Err(__lalrpop_util::ParseError::UnrecognizedToken { + token: None, + expected: vec![], + }); + } + } + } + pub fn __reduce< + 'input, + >( + input: &'input str, + __action: i32, + __lookahead_start: Option<&usize>, + __states: &mut ::std::vec::Vec, + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)>, + ) -> Option>> + { + let __nonterminal = match -__action { + 1 => { + // ( ",") = BoxedTerm, "," => ActionFn(11); + let __sym1 = __pop_Term_22_2c_22(__symbols); + let __sym0 = __pop_NtBoxedTerm(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym1.2.clone(); + let __nt = super::__action11(input, __sym0, __sym1); + let __states_len = __states.len(); + __states.truncate(__states_len - 2); + __symbols.push((__start, __Symbol::Nt_28_3cBoxedTerm_3e_20_22_2c_22_29(__nt), __end)); + 0 + } + 2 => { + // ( ",")* = => ActionFn(9); + let __start = __symbols.last().map(|s| s.2.clone()).unwrap_or_default(); + let __end = __lookahead_start.cloned().unwrap_or_else(|| __start.clone()); + let __nt = super::__action9(input, &__start, &__end); + let __states_len = __states.len(); + __states.truncate(__states_len - 0); + __symbols.push((__start, __Symbol::Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2a(__nt), __end)); + 1 + } + 3 => { + // ( ",")* = ( ",")+ => ActionFn(10); + let __sym0 = __pop_Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2b(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action10(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2a(__nt), __end)); + 1 + } + 4 => { + // ( ",")+ = BoxedTerm, "," => ActionFn(14); + let __sym1 = __pop_Term_22_2c_22(__symbols); + let __sym0 = __pop_NtBoxedTerm(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym1.2.clone(); + let __nt = super::__action14(input, __sym0, __sym1); + let __states_len = __states.len(); + __states.truncate(__states_len - 2); + __symbols.push((__start, __Symbol::Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2b(__nt), __end)); + 2 + } + 5 => { + // ( ",")+ = ( ",")+, BoxedTerm, "," => ActionFn(15); + let __sym2 = __pop_Term_22_2c_22(__symbols); + let __sym1 = __pop_NtBoxedTerm(__symbols); + let __sym0 = __pop_Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2b(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym2.2.clone(); + let __nt = super::__action15(input, __sym0, __sym1, __sym2); + let __states_len = __states.len(); + __states.truncate(__states_len - 3); + __symbols.push((__start, __Symbol::Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2b(__nt), __end)); + 2 + } + 6 => { + // Atom = r#"[a-z][a-z0-9_]*"# => ActionFn(3); + let __sym0 = __pop_Termr_23_22_5ba_2dz_5d_5ba_2dz0_2d9___5d_2a_22_23(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action3(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtAtom(__nt), __end)); + 3 + } + 7 => { + // BoxedTerm = Term => ActionFn(5); + let __sym0 = __pop_NtTerm(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action5(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtBoxedTerm(__nt), __end)); + 4 + } + 8 => { + // Term = Atom, "(", BoxedTerm, ")" => ActionFn(16); + let __sym3 = __pop_Term_22_29_22(__symbols); + let __sym2 = __pop_NtBoxedTerm(__symbols); + let __sym1 = __pop_Term_22_28_22(__symbols); + let __sym0 = __pop_NtAtom(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym3.2.clone(); + let __nt = super::__action16(input, __sym0, __sym1, __sym2, __sym3); + let __states_len = __states.len(); + __states.truncate(__states_len - 4); + __symbols.push((__start, __Symbol::NtTerm(__nt), __end)); + 5 + } + 9 => { + // Term = Atom, "(", ( ",")+, BoxedTerm, ")" => ActionFn(17); + let __sym4 = __pop_Term_22_29_22(__symbols); + let __sym3 = __pop_NtBoxedTerm(__symbols); + let __sym2 = __pop_Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2b(__symbols); + let __sym1 = __pop_Term_22_28_22(__symbols); + let __sym0 = __pop_NtAtom(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym4.2.clone(); + let __nt = super::__action17(input, __sym0, __sym1, __sym2, __sym3, __sym4); + let __states_len = __states.len(); + __states.truncate(__states_len - 5); + __symbols.push((__start, __Symbol::NtTerm(__nt), __end)); + 5 + } + 10 => { + // Term = Atom => ActionFn(7); + let __sym0 = __pop_NtAtom(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action7(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtTerm(__nt), __end)); + 5 + } + 11 => { + // Term = Var => ActionFn(8); + let __sym0 = __pop_NtVar(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action8(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtTerm(__nt), __end)); + 5 + } + 12 => { + // TopLevel = "?-", Term, "." => ActionFn(1); + let __sym2 = __pop_Term_22_2e_22(__symbols); + let __sym1 = __pop_NtTerm(__symbols); + let __sym0 = __pop_Term_22_3f_2d_22(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym2.2.clone(); + let __nt = super::__action1(input, __sym0, __sym1, __sym2); + let __states_len = __states.len(); + __states.truncate(__states_len - 3); + __symbols.push((__start, __Symbol::NtTopLevel(__nt), __end)); + 6 + } + 13 => { + // TopLevel = Term, "." => ActionFn(2); + let __sym1 = __pop_Term_22_2e_22(__symbols); + let __sym0 = __pop_NtTerm(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym1.2.clone(); + let __nt = super::__action2(input, __sym0, __sym1); + let __states_len = __states.len(); + __states.truncate(__states_len - 2); + __symbols.push((__start, __Symbol::NtTopLevel(__nt), __end)); + 6 + } + 14 => { + // Var = r#"[A-Z][a-z0-9_]*"# => ActionFn(4); + let __sym0 = __pop_Termr_23_22_5bA_2dZ_5d_5ba_2dz0_2d9___5d_2a_22_23(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action4(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtVar(__nt), __end)); + 7 + } + 15 => { + // __TopLevel = TopLevel => ActionFn(0); + let __sym0 = __pop_NtTopLevel(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action0(input, __sym0); + return Some(Ok(__nt)); + } + _ => panic!("invalid action code {}", __action) + }; + let __state = *__states.last().unwrap() as usize; + let __next_state = __GOTO[__state * 9 + __nonterminal] - 1; + __states.push(__next_state); + None + } + fn __pop_Term_22_28_22< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Term_22_28_22(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Term_22_29_22< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Term_22_29_22(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Term_22_2c_22< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Term_22_2c_22(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Term_22_2e_22< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Term_22_2e_22(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Term_22_3f_2d_22< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Term_22_3f_2d_22(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Termr_23_22_5bA_2dZ_5d_5ba_2dz0_2d9___5d_2a_22_23< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Termr_23_22_5bA_2dZ_5d_5ba_2dz0_2d9___5d_2a_22_23(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Termr_23_22_5ba_2dz_5d_5ba_2dz0_2d9___5d_2a_22_23< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Termr_23_22_5ba_2dz_5d_5ba_2dz0_2d9___5d_2a_22_23(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Nt_28_3cBoxedTerm_3e_20_22_2c_22_29< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, Box, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Nt_28_3cBoxedTerm_3e_20_22_2c_22_29(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2a< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, ::std::vec::Vec>, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2a(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2b< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, ::std::vec::Vec>, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2b(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_NtAtom< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, Atom, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::NtAtom(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_NtBoxedTerm< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, Box, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::NtBoxedTerm(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_NtTerm< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, Term, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::NtTerm(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_NtTopLevel< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, TopLevel, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::NtTopLevel(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_NtVar< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, Var, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::NtVar(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Nt____TopLevel< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, TopLevel, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Nt____TopLevel(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } +} +pub use self::__parse__TopLevel::parse_TopLevel; +mod __intern_token { + extern crate lalrpop_util as __lalrpop_util; + pub struct __Matcher<'input> { + text: &'input str, + consumed: usize, + } + + fn __tokenize(text: &str) -> Option<(usize, usize)> { + let mut __chars = text.char_indices(); + let mut __current_match: Option<(usize, usize)> = None; + let mut __current_state: usize = 0; + loop { + match __current_state { + 0 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 40 => /* '(' */ { + __current_match = Some((0, __index + 1)); + __current_state = 1; + continue; + } + 41 => /* ')' */ { + __current_match = Some((1, __index + 1)); + __current_state = 2; + continue; + } + 44 => /* ',' */ { + __current_match = Some((2, __index + 1)); + __current_state = 3; + continue; + } + 46 => /* '.' */ { + __current_match = Some((3, __index + 1)); + __current_state = 4; + continue; + } + 63 => /* '?' */ { + __current_state = 5; + continue; + } + 65 ... 90 => { + __current_match = Some((5, __index + __ch.len_utf8())); + __current_state = 6; + continue; + } + 97 ... 122 => { + __current_match = Some((6, __index + __ch.len_utf8())); + __current_state = 7; + continue; + } + _ => { + return __current_match; + } + } + } + 1 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + _ => { + return __current_match; + } + } + } + 2 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + _ => { + return __current_match; + } + } + } + 3 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + _ => { + return __current_match; + } + } + } + 4 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + _ => { + return __current_match; + } + } + } + 5 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 45 => /* '-' */ { + __current_match = Some((4, __index + 1)); + __current_state = 9; + continue; + } + _ => { + return __current_match; + } + } + } + 6 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 48 ... 57 => { + __current_match = Some((5, __index + __ch.len_utf8())); + __current_state = 10; + continue; + } + 95 => /* '_' */ { + __current_match = Some((5, __index + 1)); + __current_state = 10; + continue; + } + 97 ... 122 => { + __current_match = Some((5, __index + __ch.len_utf8())); + __current_state = 10; + continue; + } + _ => { + return __current_match; + } + } + } + 7 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 48 ... 57 => { + __current_match = Some((6, __index + __ch.len_utf8())); + __current_state = 11; + continue; + } + 95 => /* '_' */ { + __current_match = Some((6, __index + 1)); + __current_state = 11; + continue; + } + 97 ... 122 => { + __current_match = Some((6, __index + __ch.len_utf8())); + __current_state = 11; + continue; + } + _ => { + return __current_match; + } + } + } + 8 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + _ => { + return __current_match; + } + } + } + 9 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + _ => { + return __current_match; + } + } + } + 10 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 48 ... 57 => { + __current_match = Some((5, __index + __ch.len_utf8())); + __current_state = 10; + continue; + } + 95 => /* '_' */ { + __current_match = Some((5, __index + 1)); + __current_state = 10; + continue; + } + 97 ... 122 => { + __current_match = Some((5, __index + __ch.len_utf8())); + __current_state = 10; + continue; + } + _ => { + return __current_match; + } + } + } + 11 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 48 ... 57 => { + __current_match = Some((6, __index + __ch.len_utf8())); + __current_state = 11; + continue; + } + 95 => /* '_' */ { + __current_match = Some((6, __index + 1)); + __current_state = 11; + continue; + } + 97 ... 122 => { + __current_match = Some((6, __index + __ch.len_utf8())); + __current_state = 11; + continue; + } + _ => { + return __current_match; + } + } + } + _ => { panic!("invalid state {}", __current_state); } + } + } + } + + impl<'input> __Matcher<'input> { + pub fn new(s: &'input str) -> __Matcher<'input> { + __Matcher { text: s, consumed: 0 } + } + } + + impl<'input> Iterator for __Matcher<'input> { + type Item = Result<(usize, (usize, &'input str), usize), __lalrpop_util::ParseError>; + + fn next(&mut self) -> Option { + let __text = self.text.trim_left(); + let __whitespace = self.text.len() - __text.len(); + let __start_offset = self.consumed + __whitespace; + if __text.is_empty() { + self.text = __text; + self.consumed = __start_offset; + None + } else { + match __tokenize(__text) { + Some((__index, __length)) => { + let __result = &__text[..__length]; + let __remaining = &__text[__length..]; + let __end_offset = __start_offset + __length; + self.text = __remaining; + self.consumed = __end_offset; + Some(Ok((__start_offset, (__index, __result), __end_offset))) + } + None => { + Some(Err(__lalrpop_util::ParseError::InvalidToken { location: __start_offset })) + } + } + } + } + } +} + +#[allow(unused_variables)] +pub fn __action0< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, TopLevel, usize), +) -> TopLevel +{ + (__0) +} + +#[allow(unused_variables)] +pub fn __action1< + 'input, +>( + input: &'input str, + (_, _, _): (usize, &'input str, usize), + (_, t, _): (usize, Term, usize), + (_, _, _): (usize, &'input str, usize), +) -> TopLevel +{ + TopLevel::Query(t) +} + +#[allow(unused_variables)] +pub fn __action2< + 'input, +>( + input: &'input str, + (_, t, _): (usize, Term, usize), + (_, _, _): (usize, &'input str, usize), +) -> TopLevel +{ + TopLevel::Fact(t) +} + +#[allow(unused_variables)] +pub fn __action3< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, &'input str, usize), +) -> Atom +{ + __0.trim().to_string() +} + +#[allow(unused_variables)] +pub fn __action4< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, &'input str, usize), +) -> Var +{ + __0.trim().to_string() +} + +#[allow(unused_variables)] +pub fn __action5< + 'input, +>( + input: &'input str, + (_, t, _): (usize, Term, usize), +) -> Box +{ + Box::new(t) +} + +#[allow(unused_variables)] +pub fn __action6< + 'input, +>( + input: &'input str, + (_, a, _): (usize, Atom, usize), + (_, _, _): (usize, &'input str, usize), + (_, ts, _): (usize, ::std::vec::Vec>, usize), + (_, t, _): (usize, Box, usize), + (_, _, _): (usize, &'input str, usize), +) -> Term +{ + { + let mut ts = ts; + ts.push(t); + Term::Clause(Cell::new(0), a, ts) + } +} + +#[allow(unused_variables)] +pub fn __action7< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Atom, usize), +) -> Term +{ + Term::Atom(Cell::new(0), __0) +} + +#[allow(unused_variables)] +pub fn __action8< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Var, usize), +) -> Term +{ + Term::Var(Cell::new(Reg::Norm(0)), __0) +} + +#[allow(unused_variables)] +pub fn __action9< + 'input, +>( + input: &'input str, + __lookbehind: &usize, + __lookahead: &usize, +) -> ::std::vec::Vec> +{ + vec![] +} + +#[allow(unused_variables)] +pub fn __action10< + 'input, +>( + input: &'input str, + (_, v, _): (usize, ::std::vec::Vec>, usize), +) -> ::std::vec::Vec> +{ + v +} + +#[allow(unused_variables)] +pub fn __action11< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Box, usize), + (_, _, _): (usize, &'input str, usize), +) -> Box +{ + (__0) +} + +#[allow(unused_variables)] +pub fn __action12< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Box, usize), +) -> ::std::vec::Vec> +{ + vec![__0] +} + +#[allow(unused_variables)] +pub fn __action13< + 'input, +>( + input: &'input str, + (_, v, _): (usize, ::std::vec::Vec>, usize), + (_, e, _): (usize, Box, usize), +) -> ::std::vec::Vec> +{ + { let mut v = v; v.push(e); v } +} + +#[allow(unused_variables)] +pub fn __action14< + 'input, +>( + input: &'input str, + __0: (usize, Box, usize), + __1: (usize, &'input str, usize), +) -> ::std::vec::Vec> +{ + let __start0 = __0.0.clone(); + let __end0 = __1.2.clone(); + let __temp0 = __action11( + input, + __0, + __1, + ); + let __temp0 = (__start0, __temp0, __end0); + __action12( + input, + __temp0, + ) +} + +#[allow(unused_variables)] +pub fn __action15< + 'input, +>( + input: &'input str, + __0: (usize, ::std::vec::Vec>, usize), + __1: (usize, Box, usize), + __2: (usize, &'input str, usize), +) -> ::std::vec::Vec> +{ + let __start0 = __1.0.clone(); + let __end0 = __2.2.clone(); + let __temp0 = __action11( + input, + __1, + __2, + ); + let __temp0 = (__start0, __temp0, __end0); + __action13( + input, + __0, + __temp0, + ) +} + +#[allow(unused_variables)] +pub fn __action16< + 'input, +>( + input: &'input str, + __0: (usize, Atom, usize), + __1: (usize, &'input str, usize), + __2: (usize, Box, usize), + __3: (usize, &'input str, usize), +) -> Term +{ + let __start0 = __1.2.clone(); + let __end0 = __2.0.clone(); + let __temp0 = __action9( + input, + &__start0, + &__end0, + ); + let __temp0 = (__start0, __temp0, __end0); + __action6( + input, + __0, + __1, + __temp0, + __2, + __3, + ) +} + +#[allow(unused_variables)] +pub fn __action17< + 'input, +>( + input: &'input str, + __0: (usize, Atom, usize), + __1: (usize, &'input str, usize), + __2: (usize, ::std::vec::Vec>, usize), + __3: (usize, Box, usize), + __4: (usize, &'input str, usize), +) -> Term +{ + let __start0 = __2.0.clone(); + let __end0 = __2.2.clone(); + let __temp0 = __action10( + input, + __2, + ); + let __temp0 = (__start0, __temp0, __end0); + __action6( + input, + __0, + __1, + __temp0, + __3, + __4, + ) +} + +pub trait __ToTriple<'input, > { + type Error; + fn to_triple(value: Self) -> Result<(usize,(usize, &'input str),usize),Self::Error>; +} + +impl<'input, > __ToTriple<'input, > for (usize, (usize, &'input str), usize) { + type Error = (); + fn to_triple(value: Self) -> Result<(usize,(usize, &'input str),usize),()> { + Ok(value) + } +} +impl<'input, > __ToTriple<'input, > for Result<(usize, (usize, &'input str), usize),()> { + type Error = (); + fn to_triple(value: Self) -> Result<(usize,(usize, &'input str),usize),()> { + value + } +} diff --git a/src/l1/machine.rs b/src/l1/machine.rs new file mode 100644 index 00000000..5bf0a5ef --- /dev/null +++ b/src/l1/machine.rs @@ -0,0 +1,290 @@ +use l1::ast::{Addr, Atom, FactInstruction, QueryInstruction}; + +use std::collections::HashMap; +use std::vec::Vec; + +#[derive(Clone)] +enum HeapCell { + NamedStr(usize, Atom), + Ref(usize), + Str(usize), +} + +#[derive(Clone, Copy)] +enum MachineMode { + Read, + Write +} + +type Heap = Vec; + +type Registers = Vec; + +pub struct Machine { + h : usize, + s : usize, + p : usize, + pub fail : bool, + heap : Heap, + mode : MachineMode, + pub code_dir : HashMap<(Atom, usize), usize>, + pub code : Vec, + registers : Registers +} + +impl Machine { + pub fn new() -> Machine { + Machine { h : 0, + s : 0, + p : 0, + fail : false, + heap : Vec::with_capacity(256), + mode : MachineMode::Write, + code_dir : HashMap::new(), + code : Vec::new(), + registers : vec![HeapCell::Ref(0); 32] } + } + + fn lookup(&self, a: Addr) -> &HeapCell { + match a { + Addr::HeapCell(hc) => &self.heap[hc], + Addr::RegNum(reg) => &self.registers[reg] + } + } + + fn deref(&self, a: Addr) -> Addr { + let mut a = a; + + loop { + if let &HeapCell::Ref(value) = self.lookup(a) { + if let Addr::HeapCell(av) = a { + if value != av { + a = Addr::HeapCell(value); + continue; + } + } + } + + return a; + }; + } + + fn is_unbound(hc: &HeapCell, index: usize) -> bool { + match hc { + &HeapCell::Ref(r) => r == index, + _ => false + } + } + + //TODO: try to compress this function. currently it is dog shit. + fn bind(&mut self, a: Addr, val: usize) { + let mut a = a; + + loop { + match a { + Addr::RegNum(reg) => { + if let HeapCell::Ref(hc) = self.registers[reg] { + a = Addr::HeapCell(hc); + } else if Machine::is_unbound(&self.heap[val], val) { + self.heap[val] = self.registers[reg].clone(); + break; + } else { + self.fail = true; + break; + } + }, + Addr::HeapCell(hc) if Machine::is_unbound(&self.heap[hc], hc) => { + self.heap[hc] = HeapCell::Ref(val); + break; + }, + Addr::HeapCell(hc) if Machine::is_unbound(&self.heap[val], val) => { + self.heap[val] = HeapCell::Ref(hc); + break; + }, + _ => { + self.fail = true; + break; + } + }; + } + } + + fn unify(&mut self, a1: Addr, a2: Addr) { + let mut pdl : Vec = vec![a1, a2]; + + self.fail = false; + + while !(pdl.is_empty() || self.fail) { + let d1 = self.deref(pdl.pop().unwrap()); + let d2 = self.deref(pdl.pop().unwrap()); + + if d1 != d2 { + match (self.lookup(d1), self.lookup(d2)) { + (&HeapCell::Ref(hc), _) => + self.bind(d2, hc), + (_, &HeapCell::Ref(hc)) => + self.bind(d1, hc), + (&HeapCell::Str(a1), &HeapCell::Str(a2)) => { + let r1 = &self.heap[a1]; + let r2 = &self.heap[a2]; + + if let &HeapCell::NamedStr(n1, ref f1) = r1 { + if let &HeapCell::NamedStr(n2, ref f2) = r2 { + if n1 == n2 && *f1 == *f2 { + for i in 1 .. n1 { + pdl.push(Addr::HeapCell(a1 + i)); + pdl.push(Addr::HeapCell(a2 + i)); + } + + continue; + } + } + } + + self.fail = true; + }, + _ => self.fail = true, + }; + } + } + } + + pub fn execute_fact(&mut self) { + loop { + if let &FactInstruction::Proceed = &self.code[self.p] { + break; + } else if self.fail { + break; + } + + let fact_instr = self.code[self.p].clone(); + self.execute_fact_instr(fact_instr); + } + } + + pub fn execute_query_instr<'a, 'b: 'a>(&'a mut self, instr: &'b QueryInstruction) { + match instr { + &QueryInstruction::Call(ref name, arity) => { + // why is Option<&T> not Deref?!?!? + let compiled_fact_index = + self.code_dir.get(&(name.clone(), arity)).map(|index| *index); + + match compiled_fact_index { + Some(compiled_fact_index) => { + self.p = compiled_fact_index; + self.execute_fact(); + }, + None => self.fail = true, + }; + } + &QueryInstruction::PutStructure(_, ref name, arity, reg) => { + self.heap.push(HeapCell::Str(self.h + 1)); + self.heap.push(HeapCell::NamedStr(arity, name.clone())); + + self.registers[reg] = self.heap[self.h].clone(); + + self.h += 2; + }, + &QueryInstruction::PutValue(arg, norm) => + self.registers[arg] = self.registers[norm].clone(), + &QueryInstruction::PutVariable(arg, norm) => { + self.heap.push(HeapCell::Ref(self.h)); + + self.registers[norm] = self.heap[self.h].clone(); + self.registers[arg] = self.heap[self.h].clone(); + + self.h += 1; + }, + &QueryInstruction::SetVariable(reg) => { + self.heap.push(HeapCell::Ref(self.h)); + self.registers[reg] = self.heap[self.h].clone(); + + self.h += 1; + }, + &QueryInstruction::SetValue(reg) => { + self.heap.push(self.registers[reg].clone()); + self.h += 1; + }, + } + } + + fn execute_fact_instr(&mut self, instr: FactInstruction) { + match instr { + FactInstruction::Proceed => return, + FactInstruction::GetStructure(_, name, arity, reg) => { + let addr = self.deref(Addr::RegNum(reg)); + + match self.lookup(addr) { + &HeapCell::Str(a) => { + let result = &self.heap[a]; + + if let &HeapCell::NamedStr(named_arity, ref named_str) = result { + if arity == named_arity && *name == *named_str { + self.s = a + 1; + self.mode = MachineMode::Read; + } else { + self.fail = true; + } + } + }, + &HeapCell::Ref(r) => { + self.heap.push(HeapCell::Str(self.h + 1)); + self.heap.push(HeapCell::NamedStr(arity, name)); + + let h = self.h; + + self.bind(Addr::HeapCell(r), h); + + self.h += 2; + self.mode = MachineMode::Write; + }, + _ => { + self.fail = true; + } + }; + }, + FactInstruction::GetVariable(arg, norm) => + self.registers[norm] = self.registers[arg].clone(), + FactInstruction::GetValue(arg, norm) => + self.unify(Addr::RegNum(norm), Addr::RegNum(arg)), + FactInstruction::UnifyVariable(reg) => { + match self.mode { + MachineMode::Read => self.registers[reg] = self.heap[self.s].clone(), + MachineMode::Write => { + self.heap.push(HeapCell::Ref(self.h)); + self.registers[reg] = self.heap[self.h].clone(); + self.h += 1; + } + }; + + self.s += 1; + }, + FactInstruction::UnifyValue(reg) => { + let s = self.s; + + match self.mode { + MachineMode::Read => self.unify(Addr::RegNum(reg), Addr::HeapCell(s)), + MachineMode::Write => { + self.heap.push(self.registers[reg].clone()); + self.h += 1; + } + }; + + self.s += 1; + } + } + + self.p += 1; + } + + pub fn reset_machine_state(&mut self) { + self.h = 0; + self.s = 0; + self.p = 0; + + self.fail = false; + self.heap = Vec::with_capacity(256); + self.mode = MachineMode::Write; + self.registers = vec![HeapCell::Ref(0); 32]; + } +} diff --git a/src/l1/mod.rs b/src/l1/mod.rs new file mode 100644 index 00000000..4269de3d --- /dev/null +++ b/src/l1/mod.rs @@ -0,0 +1,5 @@ +pub mod ast; +pub mod iterators; +pub mod l1_parser; +pub mod codegen; +pub mod machine; diff --git a/src/main.rs b/src/main.rs index f9006ac7..f221409d 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,72 +1,62 @@ -mod l0; +mod l1; -use l0::ast::{TopLevel}; -use l0::codegen::{compile_target}; -use l0::machine::{Machine}; +use l1::ast::TopLevel; +use l1::codegen::{compile_fact, compile_query}; +use l1::machine::Machine; use std::io::{self, Write}; -fn l0_repl() { +fn l1_repl() { let mut ms = Machine::new(); - + loop { - print!("l0> "); - + print!("l1> "); + let _ = io::stdout().flush(); let mut buffer = String::new(); - + io::stdin().read_line(&mut buffer).unwrap(); - - let result = l0::parser::parse_top_level(&*buffer); + + let result = l1::l1_parser::parse_TopLevel(&*buffer); if &*buffer == "quit\n" { break; } else if &*buffer == "clear\n" { ms = Machine::new(); - } - - match result { - Ok(TopLevel::Fact(fact)) => { - let program = compile_target(&fact); - - ms = Machine::new(); - ms.program = Some(program); + } + + match result { + Ok(TopLevel::Fact(fact)) => { + let mut compiled_fact = compile_fact(&fact); + let index = ms.code.len(); - println!("Program stored."); + ms.code.append(&mut compiled_fact); + ms.code_dir.insert((fact.name().clone(), fact.arity()), index); }, Ok(TopLevel::Query(query)) => { - if let Some(program) = ms.program.take() { - let query = compile_target(&query); - - for instruction in &query { - ms.execute_query_instr(instruction); - } + let compiled_query = compile_query(&query); - for instruction in &program { - ms.execute_fact_instr(instruction); + for instruction in &compiled_query { + ms.execute_query_instr(instruction); - if ms.fail { - break; - } - } - if ms.fail { - println!("no"); - } else { - println!("yes"); + break; } - - ms.reset_heap(); - ms.program = Some(program); + } + + if ms.fail { + println!("no"); } else { - println!("No program to speak of."); + println!("yes"); } - }, + + ms.reset_machine_state(); + }, Err(_) => println!("Grammatical error of some kind!"), - }; + }; } } fn main() { - l0_repl(); + l1_repl(); } -- 2.54.0