From fcb3cc1287afa60844ceda083b1824a69a765cc2 Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Fri, 10 Mar 2017 23:50:26 -0700 Subject: [PATCH] transition to prolog --- Cargo.lock | 2 +- Cargo.toml | 2 +- README.md | 51 +- src/main.rs | 60 +- src/prolog/and_stack.rs | 80 + src/prolog/ast.rs | 342 ++++ src/prolog/codegen.rs | 546 ++++++ src/prolog/heapview.rs | 184 ++ src/prolog/io.rs | 290 +++ src/prolog/iterators.rs | 209 +++ src/prolog/machine.rs | 784 +++++++++ src/prolog/mod.rs | 9 + src/prolog/or_stack.rs | 112 ++ src/prolog/prolog_parser.lalrpop | 77 + src/prolog/prolog_parser.rs | 2815 ++++++++++++++++++++++++++++++ 15 files changed, 5540 insertions(+), 23 deletions(-) create mode 100644 src/prolog/and_stack.rs create mode 100644 src/prolog/ast.rs create mode 100644 src/prolog/codegen.rs create mode 100644 src/prolog/heapview.rs create mode 100644 src/prolog/io.rs create mode 100644 src/prolog/iterators.rs create mode 100644 src/prolog/machine.rs create mode 100644 src/prolog/mod.rs create mode 100644 src/prolog/or_stack.rs create mode 100644 src/prolog/prolog_parser.lalrpop create mode 100644 src/prolog/prolog_parser.rs diff --git a/Cargo.lock b/Cargo.lock index bac78161..99f64f8e 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -1,6 +1,6 @@ [root] name = "rusty-wam" -version = "0.4.0" +version = "0.5.0" dependencies = [ "lalrpop 0.12.5 (registry+https://github.com/rust-lang/crates.io-index)", "lalrpop-util 0.12.5 (registry+https://github.com/rust-lang/crates.io-index)", diff --git a/Cargo.toml b/Cargo.toml index 30fe64b1..8017f46b 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -1,6 +1,6 @@ [package] name = "rusty-wam" -version = "0.4.0" +version = "0.5.0" authors = ["Mark Thom"] build = "build.rs" diff --git a/README.md b/README.md index 06b9341e..09139089 100644 --- a/README.md +++ b/README.md @@ -8,9 +8,11 @@ pure Prolog. ## Progress -The language L3 is implemented as a simple REPL. L3 is pure Prolog -- -Prolog without cut, meta- or extra-logical operators, or side effects -of any kind. No data types apart from atoms are currently supported. +Pure Prolog is implemented as a simple REPL. "Pure Prolog" is Prolog +without cut, meta- or extra-logical operators, or side effects of any +kind. In terms of the tutorial pacing, the work has progressed to the +middle of section 5.2. Atoms and lists are the only two data types +currently supported. ## Tutorial To enter a multi-clause predicate, the brackets ":{" and "}:" are used @@ -18,11 +20,11 @@ as delimiters. They must be entirely contained with their own lines. For example, ``` -l3> :{ +prolog> :{ p(f(f(X)), h(W), Y) :- g(W), h(W), f(X). p(X, Y, Z) :- h(Y), z(Z). }: -l3> :{ +prolog> :{ h(x). h(y). h(z). @@ -31,28 +33,49 @@ h(z). Single clause predicates can be entered without brackets, as in ``` -l3> p(X) :- q(X). -l3> f(s). -l3> z(Z). +prolog> p(X) :- q(X). +prolog> f(s). +prolog> z(Z). ``` Queries are issued as ``` -l3> ?- p(X, Y, Z). +prolog> ?- p(X, Y, Z). ``` Given the above work, the result of the query will be ``` -l3> ?- p(X, Y, Z). +prolog> ?- p(X, Y, Z). yes X = _0 Y = x Z = _2 -Press ; to continue or A to abort. +Press ; to continue or . to abort. ``` Pressing ; will backtrack through other possible answers, if any exist. -Pressing A will abort the search and return to the prompt. +Pressing . will abort the search and return to the prompt. + +Wildcards work as well: + +``` +prolog> prolog> :{ +member(X, [X|_]). +member(X, [_|Xs]) :- member(X, Xs). +}: +prolog> ?- member(X, [a, b, c]). +yes +X = a +Press ; to continue or . to abort. +; +X = b +Press ; to continue or . to abort. +; +X = c +Press ; to continue or . to abort. +; +no +``` Note that the values of variables belonging to successful queries are printed out, on one line each. Uninstantiated variables are denoted by @@ -66,8 +89,8 @@ unification on a cyclic term succeeds, and the attempt to write the term to a string results in an infinite loop, ie. ``` -l3> p(W, W). -l3> ?- p(f(f(W)), W). +prolog> p(W, W). +prolog> ?- p(f(f(W)), W). yes *loops to infinity* ``` \ No newline at end of file diff --git a/src/main.rs b/src/main.rs index 8cbe432f..1c94c7bd 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,13 +1,13 @@ extern crate termion; -mod l3; +mod prolog; -use l3::io::*; -use l3::machine::*; +use prolog::io::*; +use prolog::machine::*; #[cfg(test)] mod tests { use super::*; - use l3::ast::*; + use prolog::ast::*; fn submit(wam: &mut Machine, buffer: &str) -> EvalResult { let result = eval(wam, buffer); @@ -174,13 +174,59 @@ mod tests { assert_eq!(submit(&mut wam, "?- p(X, Y, X).").failed_query(), false); assert_eq!(submit(&mut wam, "?- p(f(f(X)), h(f(X)), Y).").failed_query(), true); } + + #[test] + fn test_queries_on_lists() { + let mut wam = Machine::new(); + + submit(&mut wam, "p([Z, W])."); + + assert_eq!(submit(&mut wam, "?- p([Z, Z]).").failed_query(), false); + assert_eq!(submit(&mut wam, "?- p([Z, W, Y]).").failed_query(), true); + assert_eq!(submit(&mut wam, "?- p([Z | W]).").failed_query(), false); + assert_eq!(submit(&mut wam, "?- p([Z | [Z]]).").failed_query(), false); + assert_eq!(submit(&mut wam, "?- p([Z | [W]]).").failed_query(), false); + assert_eq!(submit(&mut wam, "?- p([Z | []]).").failed_query(), true); + + submit(&mut wam, "p([Z, Z])."); + + assert_eq!(submit(&mut wam, "?- p([Z, Z]).").failed_query(), false); + assert_eq!(submit(&mut wam, "?- p([Z, W, Y]).").failed_query(), true); + assert_eq!(submit(&mut wam, "?- p([Z | W]).").failed_query(), false); + assert_eq!(submit(&mut wam, "?- p([Z | [Z]]).").failed_query(), false); + assert_eq!(submit(&mut wam, "?- p([Z | [W]]).").failed_query(), false); + assert_eq!(submit(&mut wam, "?- p([Z | []]).").failed_query(), true); + + submit(&mut wam, "p([Z])."); + + assert_eq!(submit(&mut wam, "?- p([Z, Z]).").failed_query(), true); + assert_eq!(submit(&mut wam, "?- p([Z, W, Y]).").failed_query(), true); + assert_eq!(submit(&mut wam, "?- p([Z | W]).").failed_query(), false); + assert_eq!(submit(&mut wam, "?- p([Z | [Z]]).").failed_query(), true); + assert_eq!(submit(&mut wam, "?- p([Z | [W]]).").failed_query(), true); + assert_eq!(submit(&mut wam, "?- p([Z | []]).").failed_query(), false); + + submit(&mut wam, "member(X, [X|Xs]). + member(X, [Y|Xs]) :- member(X, Xs)."); + + assert_eq!(submit(&mut wam, "?- member(a, [c, [X, Y]]).").failed_query(), true); + assert_eq!(submit(&mut wam, "?- member(c, [a, [X, Y]]).").failed_query(), true); + assert_eq!(submit(&mut wam, "?- member(a, [a, [X, Y]]).").failed_query(), false); + assert_eq!(submit(&mut wam, "?- member(a, [X, Y, Z]).").failed_query(), false); + assert_eq!(submit(&mut wam, "?- member([X, X], [a, [X, Y]]).").failed_query(), false); + assert_eq!(submit(&mut wam, "?- member([X, X], [a, [b, c], [b, b], [Z, x], [d, f]]).").failed_query(), false); + assert_eq!(submit(&mut wam, "?- member([X, X], [a, [b, c], [b, d], [foo, x], [d, f]]).").failed_query(), true); + assert_eq!(submit(&mut wam, "?- member([X, Y], [a, [b, c], [b, b], [Z, x], [d, f]]).").failed_query(), false); + assert_eq!(submit(&mut wam, "?- member([X, Y, Y], [a, [b, c], [b, b], [Z, x], [d, f]]).").failed_query(), true); + assert_eq!(submit(&mut wam, "?- member([X, Y, Z], [a, [b, c], [b, b], [Z, x], [d, f]]).").failed_query(), true); + } } -fn l3_repl() { +fn prolog_repl() { let mut wam = Machine::new(); loop { - print!("l3> "); + print!("prolog> "); let buffer = read(); @@ -199,5 +245,5 @@ fn l3_repl() { } fn main() { - l3_repl(); + prolog_repl(); } diff --git a/src/prolog/and_stack.rs b/src/prolog/and_stack.rs new file mode 100644 index 00000000..ebeb3b02 --- /dev/null +++ b/src/prolog/and_stack.rs @@ -0,0 +1,80 @@ +use prolog::ast::*; + +use std::ops::{Index, IndexMut}; +use std::vec::Vec; + +pub struct Frame { + pub global_index: usize, + pub e: usize, + pub cp: CodePtr, + perms: Vec +} + +impl Frame { + fn new(global_index: usize, e: usize, cp: CodePtr, n: usize) -> Self { + Frame { + global_index: global_index, + e: e, + cp: cp, + perms: vec![Addr::HeapCell(0); n] + } + } +} + +pub struct AndStack(Vec); + +impl AndStack { + pub fn new() -> Self { + AndStack(Vec::new()) + } + + pub fn push(&mut self, global_index: usize, e: usize, cp: CodePtr, n: usize) { + self.0.push(Frame::new(global_index, e, cp, n)); + } + + pub fn top(&self) -> Option<&Frame> { + self.0.last() + } + + pub fn len(&self) -> usize { + self.0.len() + } + + pub fn clear(&mut self) { + self.0.clear() + } + + // drop the last n frames. + pub fn drop_frames(&mut self, n: usize) { + let len = self.0.len(); + self.0.truncate(len - n); + } +} + +impl Index for AndStack { + type Output = Frame; + + fn index(&self, index: usize) -> &Self::Output { + self.0.index(index) + } +} + +impl IndexMut for AndStack { + fn index_mut(&mut self, index: usize) -> &mut Self::Output { + self.0.index_mut(index) + } +} + +impl Index for Frame { + type Output = Addr; + + fn index(&self, index: usize) -> &Self::Output { + self.perms.index(index - 1) + } +} + +impl IndexMut for Frame { + fn index_mut(&mut self, index: usize) -> &mut Self::Output { + self.perms.index_mut(index - 1) + } +} diff --git a/src/prolog/ast.rs b/src/prolog/ast.rs new file mode 100644 index 00000000..4f42990e --- /dev/null +++ b/src/prolog/ast.rs @@ -0,0 +1,342 @@ +use std::cell::Cell; +use std::collections::HashMap; +use std::ops::{Add, AddAssign}; +use std::vec::Vec; + +pub type Var = String; + +pub type Atom = String; + +pub enum PredicateClause { + Fact(Term), + Rule(Rule) +} + +impl PredicateClause { + pub fn name(&self) -> &Atom { + match self { + &PredicateClause::Fact(ref t) => t.name().unwrap(), + &PredicateClause::Rule(ref rule) => rule.head.0.name().unwrap() + } + } + + pub fn arity(&self) -> usize { + match self { + &PredicateClause::Fact(ref t) => t.arity(), + &PredicateClause::Rule(ref rule) => rule.head.0.arity() + } + } +} + +pub enum TopLevel { + Fact(Term), + Predicate(Vec), + Query(Term), + Rule(Rule) +} + +#[derive(Clone, Copy)] +pub enum Level { + Deep, Shallow +} + +#[derive(Clone, Copy)] +pub enum RegType { + Perm(usize), + Temp(usize) +} + +impl Default for RegType { + fn default() -> Self { + RegType::Temp(0) + } +} + +impl RegType { + pub fn reg_num(self) -> usize { + match self { + RegType::Perm(reg_num) | RegType::Temp(reg_num) => reg_num + } + } + + pub fn is_perm(self) -> bool { + match self { + RegType::Perm(_) => true, + _ => false + } + } +} + +#[derive(Clone, Copy)] +pub enum VarReg { + ArgAndNorm(RegType, usize), + Norm(RegType) +} + +impl VarReg { + pub fn norm(self) -> RegType { + match self { + VarReg::ArgAndNorm(reg, _) | VarReg::Norm(reg) => reg + } + } + + pub fn root_register(self) -> usize { + match self { + VarReg::ArgAndNorm(_, root) => root, + VarReg::Norm(root) => root.reg_num() + } + } +} + +impl Default for VarReg { + fn default() -> Self { + VarReg::Norm(RegType::default()) + } +} + +#[derive(Clone, PartialEq)] +pub enum Constant { + Atom(Atom), + EmptyList +} + +pub enum Term { + AnonVar, + Clause(Cell, Atom, Vec>), + Cons(Cell, Box, Box), + Constant(Cell, Constant), + Var(Cell, Var) +} + +pub struct Rule { + pub head: (Term, Term), + pub clauses: Vec +} + +pub enum TermRef<'a> { + AnonVar(Level), + Cons(Level, &'a Cell, &'a Term, &'a Term), + Constant(Level, &'a Cell, &'a Constant), + Clause(Level, &'a Cell, &'a Atom, &'a Vec>), + Var(Level, &'a Cell, &'a Var) +} + +pub enum FactInstruction { + GetConstant(Level, Constant, RegType), + GetList(Level, RegType), + GetStructure(Level, Atom, usize, RegType), + GetValue(RegType, usize), + GetVariable(RegType, usize), + UnifyConstant(Constant), + UnifyVariable(RegType), + UnifyValue(RegType) +} + +pub enum QueryInstruction { + PutConstant(Level, Constant, RegType), + PutList(Level, RegType), + PutStructure(Level, Atom, usize, RegType), + PutValue(RegType, usize), + PutVariable(RegType, usize), + SetConstant(Constant), + SetVariable(RegType), + SetValue(RegType) +} + +pub enum ChoiceInstruction { + RetryMeElse(usize), + TrustMe, + TryMeElse(usize) +} + +pub enum ControlInstruction { + Allocate(usize), + Call(Atom, usize), + Deallocate, + Proceed +} + +pub type CompiledFact = Vec; + +pub type CompiledQuery = Vec; + +pub enum Line { + Choice(ChoiceInstruction), + Control(ControlInstruction), + Fact(CompiledFact), + Query(CompiledQuery) +} + +pub enum LineOrCodeOffset<'a> { + Instruction(&'a Line), + Offset(usize) +} + +impl<'a> From<&'a Line> for LineOrCodeOffset<'a> { + fn from(line: &'a Line) -> Self { + LineOrCodeOffset::Instruction(line) + } +} + +pub type Code = Vec; + +#[derive(Clone, PartialEq)] +pub enum Addr { + Con(Constant), + Lis(usize), + HeapCell(usize), + StackCell(usize, usize), + Str(usize) +} + +impl Addr { + pub fn is_ref(&self) -> bool { + match self { + &Addr::HeapCell(_) | &Addr::StackCell(_, _) => true, + _ => false + } + } + + pub fn as_ref(&self) -> Option { + match self { + &Addr::HeapCell(hc) => Some(Ref::HeapCell(hc)), + &Addr::StackCell(fr, sc) => Some(Ref::StackCell(fr, sc)), + _ => None + } + } +} + +impl From for Addr { + fn from(r: Ref) -> Self { + match r { + Ref::HeapCell(hc) => Addr::HeapCell(hc), + Ref::StackCell(fr, sc) => Addr::StackCell(fr, sc) + } + } +} + +#[derive(Clone, Copy, PartialEq)] +pub enum Ref { + HeapCell(usize), + StackCell(usize, usize) +} + +#[derive(Clone, PartialEq)] +pub enum HeapCellValue { + Con(Constant), + Lis(usize), + NamedStr(usize, Atom), + Ref(Ref), + Str(usize) +} + +impl From for HeapCellValue { + fn from(addr: Addr) -> HeapCellValue { + match addr { + Addr::Con(constant) => + HeapCellValue::Con(constant), + Addr::HeapCell(hc) => + HeapCellValue::Ref(Ref::HeapCell(hc)), + Addr::Lis(a) => + HeapCellValue::Lis(a), + Addr::StackCell(fr, sc) => + HeapCellValue::Ref(Ref::StackCell(fr, sc)), + Addr::Str(hc) => + HeapCellValue::Str(hc) + } + } +} + +impl HeapCellValue { + pub fn as_addr(&self, focus: usize) -> Addr { + match self { + &HeapCellValue::Con(ref c) => Addr::Con(c.clone()), + &HeapCellValue::Lis(a) => Addr::Lis(a), + &HeapCellValue::Ref(r) => Addr::from(r), + &HeapCellValue::Str(s) => Addr::Str(s), + &HeapCellValue::NamedStr(_, _) => Addr::Str(focus) + } + } +} + +#[derive(Clone, Copy)] +pub enum CodePtr { + DirEntry(usize), + TopLevel +} + +impl Default for CodePtr { + fn default() -> Self { + CodePtr::TopLevel + } +} + +impl Add for CodePtr { + type Output = CodePtr; + + fn add(self, rhs: usize) -> Self::Output { + match self { + CodePtr::DirEntry(p) => CodePtr::DirEntry(p + rhs), + CodePtr::TopLevel => CodePtr::TopLevel + } + } +} + +impl AddAssign for CodePtr { + fn add_assign(&mut self, rhs: usize) { + match self { + &mut CodePtr::DirEntry(ref mut p) => *p += rhs, + _ => {} + } + } +} + +pub type Heap = Vec; + +pub type Registers = Vec; + +impl Term { + pub fn subterms(&self) -> usize { + match self { + &Term::Clause(_, _, ref terms) => terms.len(), + _ => 1 + } + } + + pub fn name(&self) -> Option<&Atom> { + match self { + &Term::Constant(_, Constant::Atom(ref atom)) + | &Term::Var(_, ref atom) + | &Term::Clause(_, ref atom, _) => Some(atom), + _ => None + } + } + + pub fn arity(&self) -> usize { + match self { + &Term::Clause(_, _, ref child_terms) => child_terms.len(), + _ => 0 + } + } +} + +pub type HeapVarDict = HashMap; + +pub enum EvalResult { + EntryFailure, + EntrySuccess, + InitialQuerySuccess(HeapVarDict), + QueryFailure, + SubsequentQuerySuccess, +} + +impl EvalResult { + #[allow(dead_code)] + pub fn failed_query(&self) -> bool { + if let &EvalResult::QueryFailure = self { + true + } else { + false + } + } +} diff --git a/src/prolog/codegen.rs b/src/prolog/codegen.rs new file mode 100644 index 00000000..c8af1746 --- /dev/null +++ b/src/prolog/codegen.rs @@ -0,0 +1,546 @@ +use prolog::ast::*; +use prolog::iterators::{FactIterator, QueryIterator}; + +use std::cell::Cell; +use std::cmp::max; +use std::collections::HashMap; +use std::vec::Vec; + +trait CompilationTarget<'a> { + type Iterator : Iterator>; + + fn iter(&'a Term) -> Self::Iterator; + + fn to_structure(Level, Atom, usize, RegType) -> Self; + fn to_constant(Level, Constant, RegType) -> Self; + fn to_list(Level, RegType) -> Self; + + fn constant_subterm(Constant) -> Self; + + fn argument_to_variable(RegType, usize) -> Self; + fn argument_to_value(RegType, usize) -> Self; + + fn subterm_to_variable(RegType) -> Self; + fn subterm_to_value(RegType) -> Self; + + fn clause_arg_to_instr(RegType) -> 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, reg: RegType) -> Self { + FactInstruction::GetStructure(lvl, atom, arity, reg) + } + + fn to_constant(lvl: Level, constant: Constant, reg: RegType) -> Self { + FactInstruction::GetConstant(lvl, constant, reg) + } + + fn to_list(lvl: Level, reg: RegType) -> Self { + FactInstruction::GetList(lvl, reg) + } + + fn constant_subterm(constant: Constant) -> Self { + FactInstruction::UnifyConstant(constant) + } + + fn argument_to_variable(arg: RegType, val: usize) -> Self { + FactInstruction::GetVariable(arg, val) + } + + fn argument_to_value(arg: RegType, val: usize) -> Self { + FactInstruction::GetValue(arg, val) + } + + fn subterm_to_variable(val: RegType) -> Self { + FactInstruction::UnifyVariable(val) + } + + fn subterm_to_value(val: RegType) -> Self { + FactInstruction::UnifyValue(val) + } + + fn clause_arg_to_instr(val: RegType) -> Self { + FactInstruction::UnifyVariable(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, reg: RegType) -> Self { + QueryInstruction::PutStructure(lvl, atom, arity, reg) + } + + fn to_constant(lvl: Level, constant: Constant, reg: RegType) -> Self { + QueryInstruction::PutConstant(lvl, constant, reg) + } + + fn to_list(lvl: Level, reg: RegType) -> Self { + QueryInstruction::PutList(lvl, reg) + } + + fn constant_subterm(constant: Constant) -> Self { + QueryInstruction::SetConstant(constant) + } + + fn argument_to_variable(arg: RegType, val: usize) -> Self { + QueryInstruction::PutVariable(arg, val) + } + + fn argument_to_value(arg: RegType, val: usize) -> Self { + QueryInstruction::PutValue(arg, val) + } + + fn subterm_to_variable(val: RegType) -> Self { + QueryInstruction::SetVariable(val) + } + + fn subterm_to_value(val: RegType) -> Self { + QueryInstruction::SetValue(val) + } + + fn clause_arg_to_instr(val: RegType) -> Self { + QueryInstruction::SetValue(val) + } +} + +struct TermMarker<'a> { + bindings: HashMap<&'a Var, VarReg>, + arg_c: usize, + perm_c: usize, + temp_c: usize +} + +impl<'a> TermMarker<'a> { + fn new() -> TermMarker<'a> { + TermMarker { bindings: HashMap::new(), + arg_c: 1, + perm_c: 1, + temp_c: 1 } + } + + fn reset(&mut self) { + self.bindings.clear(); + self.perm_c = 1; + } + + fn contains_var(&self, var: &'a Var) -> bool { + self.bindings.contains_key(var) + } + + fn get(&self, var: &'a Var) -> VarReg { + *self.bindings.get(var).unwrap() + } + + fn insert(&mut self, var: &'a Var, r: VarReg) { + self.bindings.insert(var, r); + } + + fn mark_non_var(&mut self, lvl: Level, cell: &Cell) { + let reg_type = cell.get(); + + if reg_type.reg_num() == 0 { + match lvl { + Level::Deep if reg_type.is_perm() => { + let perm = self.perm_c; + self.perm_c += 1; + cell.set(RegType::Perm(perm)); + }, + Level::Deep => { + let temp = self.temp_c; + self.temp_c += 1; + cell.set(RegType::Temp(temp)); + }, + Level::Shallow if reg_type.is_perm() => { + let arg = self.arg_c; + self.arg_c += 1; + cell.set(RegType::Perm(arg)); + }, + Level::Shallow => { + let arg = self.arg_c; + self.arg_c += 1; + cell.set(RegType::Temp(arg)); + } + }; + } + } + + fn mark_old_var(&mut self, lvl: Level, var: &'a Var) -> VarReg + { + let reg = self.get(var); + + match lvl { + Level::Deep => VarReg::Norm(reg.norm()), + Level::Shallow => { + let reg = VarReg::ArgAndNorm(reg.norm(), self.arg_c); + + self.arg_c += 1; + self.insert(var, reg); + + reg + } + } + } + + fn mark_new_var(&mut self, lvl: Level, var: &'a Var, reg: RegType) -> VarReg + { + let inner_reg = if reg.is_perm() { + let perm = self.perm_c; + self.perm_c += 1; + RegType::Perm(perm) + } else { + let temp = self.temp_c; + self.temp_c += 1; + RegType::Temp(temp) + }; + + let reg = match lvl { + Level::Deep => VarReg::Norm(inner_reg), + Level::Shallow => { + let reg = VarReg::ArgAndNorm(inner_reg, self.arg_c); + self.arg_c += 1; + reg + } + }; + + self.insert(var, reg); + reg + } + + fn mark_anon_var(&mut self, lvl: Level) -> VarReg { + let inner_reg = { + let temp = self.temp_c; + self.temp_c += 1; + RegType::Temp(temp) + }; + + match lvl { + Level::Deep => VarReg::Norm(inner_reg), + Level::Shallow => { + let reg = VarReg::ArgAndNorm(inner_reg, self.arg_c); + self.arg_c += 1; + reg + } + } + } + + fn advance_at_head(&mut self, term: &'a Term) { + self.arg_c = 1; + self.temp_c = max(term.subterms(), self.temp_c) + 1; + } + + fn advance(&mut self, term: &'a Term) { + self.arg_c = 1; + self.temp_c = term.subterms() + 1; + } +} + +#[derive(Copy, Clone)] +enum TermStatus { + New, Old, Recurrent +} + +pub struct CodeGenerator<'a> { + marker: TermMarker<'a> +} + +type VariableFixture<'a> = (TermStatus, Vec<&'a Cell>); +type VariableFixtures<'a> = HashMap<&'a Var, VariableFixture<'a>>; + +impl<'a> CodeGenerator<'a> { + pub fn new() -> Self { + CodeGenerator { marker: TermMarker::new() } + } + + pub fn vars(&self) -> &HashMap<&Var, VarReg> { + &self.marker.bindings + } + + fn to_structure(&mut self, + lvl: Level, + cell: &'a Cell, + name: &'a Atom, + arity: usize) + -> Target + where Target: CompilationTarget<'a> + { + self.marker.mark_non_var(lvl, cell); + Target::to_structure(lvl, name.clone(), arity, cell.get()) + } + + fn to_constant(&mut self, + lvl: Level, + cell: &'a Cell, + constant: &'a Constant) + -> Target + where Target: CompilationTarget<'a> + { + self.marker.mark_non_var(lvl, cell); + Target::to_constant(lvl, constant.clone(), cell.get()) + } + + fn to_list(&mut self, lvl: Level, cell: &'a Cell) -> Target + where Target: CompilationTarget<'a> + { + self.marker.mark_non_var(lvl, cell); + Target::to_list(lvl, cell.get()) + } + + fn constant_subterm(&mut self, + cell: &'a Cell, + constant: &'a Constant) + -> Target + where Target: CompilationTarget<'a> + { + self.marker.mark_non_var(Level::Deep, cell); + Target::constant_subterm(constant.clone()) + } + + fn anon_var_term(&mut self, lvl: Level) -> Target + where Target: CompilationTarget<'a> + { + let reg = self.marker.mark_anon_var(lvl); + + match reg { + VarReg::ArgAndNorm(arg, norm) => + Target::argument_to_variable(arg, norm), + VarReg::Norm(norm) => + Target::subterm_to_variable(norm) + } + } + + fn var_term(&mut self, + lvl: Level, + cell: &'a Cell, + var: &'a Var) + -> Target + where Target: CompilationTarget<'a> + { + if !self.marker.contains_var(var) { + let reg = self.marker.mark_new_var(lvl, var, cell.get().norm()); + cell.set(reg); + + match reg { + VarReg::ArgAndNorm(arg, norm) => + Target::argument_to_variable(arg, norm), + VarReg::Norm(norm) => + Target::subterm_to_variable(norm) + } + } else { + let reg = self.marker.mark_old_var(lvl, var); + cell.set(reg); + + match reg { + VarReg::ArgAndNorm(arg, norm) => + Target::argument_to_value(arg, norm), + VarReg::Norm(norm) => + Target::subterm_to_value(norm) + } + } + } + + fn non_var_subterm(&mut self, cell: &'a Cell) -> Target + where Target: CompilationTarget<'a> + { + self.marker.mark_non_var(Level::Deep, cell); + Target::clause_arg_to_instr(cell.get()) + } + + fn subterm_to_instr(&mut self, subterm: &'a Term) -> Target + where Target: CompilationTarget<'a> + { + match subterm { + &Term::AnonVar => + self.anon_var_term(Level::Deep), + &Term::Cons(ref cell, _, _) | &Term::Clause(ref cell, _, _) => + self.non_var_subterm(cell), + &Term::Constant(ref cell, ref constant) => + self.constant_subterm(cell, constant), + &Term::Var(ref cell, ref var) => + self.var_term(Level::Deep, cell, var) + } + } + + fn compile_target(&mut self, term: &'a Term) -> Vec + where Target: CompilationTarget<'a> + { + let iter = Target::iter(term); + let mut target = Vec::new(); + + for term in iter { + match term { + TermRef::Clause(lvl, cell, atom, terms) => { + target.push(self.to_structure(lvl, cell, atom, terms.len())); + + for subterm in terms { + target.push(self.subterm_to_instr(subterm.as_ref())); + } + }, + TermRef::Cons(lvl, cell, head, tail) => { + target.push(self.to_list(lvl, cell)); + + target.push(self.subterm_to_instr(head)); + target.push(self.subterm_to_instr(tail)); + }, + TermRef::Constant(lvl @ Level::Shallow, cell, constant) => + target.push(self.to_constant(lvl, cell, constant)), + TermRef::AnonVar(lvl @ Level::Shallow) => + target.push(self.anon_var_term(lvl)), + TermRef::Var(lvl @ Level::Shallow, ref cell, ref var) => + target.push(self.var_term(lvl, cell, var)), + _ => {} + }; + } + + target + } + + fn mark_vars_in_term(iter: Iter, vs: &mut VariableFixtures<'a>) + where Iter : Iterator> + { + for term in iter { + if let TermRef::Var(_, reg_cell, var) = term { + let mut status = vs.entry(var) + .or_insert((TermStatus::New, Vec::new())); + + status.1.push(reg_cell); + + match status.0 { + TermStatus::Old => status.0 = TermStatus::Recurrent, + _ => {} + }; + } + } + + for &mut (ref mut term_status, ref mut cb) in vs.values_mut() { + match *term_status { + TermStatus::New => *term_status = TermStatus::Old, + TermStatus::Recurrent => { + for cell_reg in cb.drain(0..) { + cell_reg.set(VarReg::Norm(RegType::Perm(0))); + } + }, + _ => {} + } + } + } + + fn mark_perm_vars(rule: &'a Rule) -> VariableFixtures { + let &Rule { head: (ref p0, ref p1), ref clauses } = rule; + let mut vfs = HashMap::new(); + + let iter = p0.breadth_first_iter().chain(p1.breadth_first_iter()); + + Self::mark_vars_in_term(iter, &mut vfs); + + for term in clauses { + Self::mark_vars_in_term(term.breadth_first_iter(), &mut vfs); + } + + vfs + } + + fn add_conditional_call(compiled_query: &mut Code, term: &Term) { + match term { + &Term::Constant(_, Constant::Atom(ref atom)) => { + let call = ControlInstruction::Call(atom.clone(), 0); + compiled_query.push(Line::Control(call)); + }, + &Term::Clause(_, ref atom, ref terms) => { + let call = ControlInstruction::Call(atom.clone(), terms.len()); + compiled_query.push(Line::Control(call)); + }, + _ => {} + } + } + + pub fn compile_rule(&mut self, rule: &'a Rule) -> Code { + let vfs = Self::mark_perm_vars(&rule); + let &Rule { head: (ref p0, ref p1), ref clauses } = rule; + let mut perm_vars = 0; + + for &(term_status, _) in vfs.values() { + if let TermStatus::Recurrent = term_status { + perm_vars += 1; + } + } + + let mut body = Vec::new(); + + body.push(Line::Control(ControlInstruction::Allocate(perm_vars))); + + self.marker.advance(p0); + body.push(Line::Fact(self.compile_target(p0))); + + self.marker.advance_at_head(p1); + body.push(Line::Query(self.compile_target(p1))); + + Self::add_conditional_call(&mut body, p1); + + body = clauses.iter() + .map(|ref term| self.compile_query(term)) + .fold(body, |mut body, ref mut cqs| { + body.append(cqs); + body + }); + + body.push(Line::Control(ControlInstruction::Deallocate)); + body + } + + pub fn compile_fact(&mut self, term: &'a Term) -> Code { + self.marker.advance(term); + + let mut compiled_fact = vec![Line::Fact(self.compile_target(term))]; + let proceed = Line::Control(ControlInstruction::Proceed); + + compiled_fact.push(proceed); + compiled_fact + } + + pub fn compile_query(&mut self, term: &'a Term) -> Code { + self.marker.advance(term); + + let mut compiled_query = vec![Line::Query(self.compile_target(term))]; + Self::add_conditional_call(&mut compiled_query, term); + + compiled_query + } + + pub fn compile_predicate(&mut self, clauses: &'a Vec) -> Code + { + let mut code = Vec::new(); + + for (i, clause) in clauses.iter().enumerate() { + self.marker.reset(); + + let mut clause_code = match clause { + &PredicateClause::Fact(ref fact) => + self.compile_fact(fact), + &PredicateClause::Rule(ref rule) => + self.compile_rule(rule) + }; + + let choice = match i { + 0 => ChoiceInstruction::TryMeElse(clause_code.len() + 1), + _ if i == clauses.len() - 1 => ChoiceInstruction::TrustMe, + _ => ChoiceInstruction::RetryMeElse(clause_code.len() + 1) + }; + + code.push(Line::Choice(choice)); + code.append(&mut clause_code); + } + + code + } +} diff --git a/src/prolog/heapview.rs b/src/prolog/heapview.rs new file mode 100644 index 00000000..b1a11e21 --- /dev/null +++ b/src/prolog/heapview.rs @@ -0,0 +1,184 @@ +use prolog::and_stack::*; +use prolog::ast::*; + +use std::vec::Vec; + +#[derive(Clone, Copy)] +pub enum TToken { + Bar, + Comma, + LRBracket, + LSBracket(usize), + Nothing, + RRBracket, + RSBracket +} + +impl TToken { + pub fn as_str(self) -> &'static str { + match self { + TToken::Bar => " | ", + TToken::Comma => ", ", + TToken::LRBracket => "(", + TToken::LSBracket(_) => "[", + TToken::Nothing => "", + TToken::RRBracket => ")", + TToken::RSBracket => "]" + } + } +} + +#[derive(Clone, Copy)] +enum CellRef<'a> { + View(CellView<'a>), + Redirect(usize), + TToken(TToken) +} + +#[derive(Clone, Copy)] +pub enum CellView<'a> { + Con(&'a Constant), + HeapVar(usize), + StackVar(usize, usize), + Str(usize, &'a Atom), + TToken(TToken), +} + +pub struct HeapCellViewer<'a> { + and_stack: &'a AndStack, + heap: &'a Heap, + state_stack: Vec> +} + +impl<'a> HeapCellViewer<'a> { + fn cell_ref_from_addr(&self, mut focus: &'a Addr) -> CellRef<'a> { + loop { + match focus { + &Addr::Con(ref c) => + return CellRef::View(CellView::Con(c)), + &Addr::Lis(hc) | &Addr::HeapCell(hc) | &Addr::Str(hc) => + return CellRef::Redirect(hc), + &Addr::StackCell(fr, sc) => { + match &self.and_stack[fr][sc] { + &Addr::StackCell(fr1, sc1) => { + if fr1 == fr && sc1 == sc { + return CellRef::View(CellView::StackVar(fr, sc)); + } + }, + _ => focus = &self.and_stack[fr][sc] + } + } + } + } + } + + pub fn new(heap: &'a Heap, and_stack: &'a AndStack, addr: &'a Addr) -> Self + { + let mut viewer = HeapCellViewer { + heap: heap, + and_stack: and_stack, + state_stack: vec![] + }; + + let cell_ref = viewer.cell_ref_from_addr(addr); + let view = viewer.follow(cell_ref); + + viewer.state_stack.push(CellRef::View(view)); + + viewer + } + + pub fn remove_token(&mut self, loc: usize) { + self.state_stack[loc] = CellRef::TToken(TToken::Nothing); + } + + pub fn peek(&mut self) -> Option> { + let len = self.state_stack.len(); + + if len > 0 { + let last_elt = self.state_stack.pop().unwrap(); + let cell_view = self.follow(last_elt); + + self.state_stack.truncate(len - 1); + self.state_stack.push(last_elt); + + Some(cell_view) + } else { + None + } + } + + fn from_heap(&mut self, mut focus: usize) -> CellView<'a> { + loop { + match &self.heap[focus] { + &HeapCellValue::Con(ref c) => + return CellView::Con(c), + &HeapCellValue::Lis(a) => { + self.state_stack.push(CellRef::TToken(TToken::RSBracket)); + + self.state_stack.push(CellRef::Redirect(a + 1)); + self.state_stack.push(CellRef::TToken(TToken::Bar)); + self.state_stack.push(CellRef::Redirect(a)); + + let len = self.state_stack.len() - 4; + + return CellView::TToken(TToken::LSBracket(len)); + }, + &HeapCellValue::NamedStr(arity, ref name) => { + self.state_stack.push(CellRef::TToken(TToken::RRBracket)); + + for i in (2 .. arity + 1).rev() { + self.state_stack.push(CellRef::Redirect(focus + i)); + self.state_stack.push(CellRef::TToken(TToken::Comma)); + } + + self.state_stack.push(CellRef::Redirect(focus + 1)); + self.state_stack.push(CellRef::TToken(TToken::LRBracket)); + + return CellView::Str(arity, name); + }, + &HeapCellValue::Ref(Ref::HeapCell(hc)) => { + if focus == hc { + return CellView::HeapVar(hc); + } else { + focus = hc; + } + }, + &HeapCellValue::Ref(Ref::StackCell(fr, sc)) => { + match self.cell_ref_from_addr(&self.and_stack[fr][sc]) { + CellRef::View(cell_view) => return cell_view, + CellRef::Redirect(hc) => focus = hc, + CellRef::TToken(token) => return CellView::TToken(token) + }; + }, + &HeapCellValue::Str(cell_num) => + focus = cell_num, + } + } + } + + fn follow(&mut self, cell_ref: CellRef<'a>) -> CellView<'a> + { + match cell_ref { + CellRef::Redirect(hc) => + self.from_heap(hc), + CellRef::View(cell_view) => + cell_view, + CellRef::TToken(term_token) => + CellView::TToken(term_token) + } + } +} + + +impl<'a> Iterator for HeapCellViewer<'a> { + type Item = CellView<'a>; + + fn next(&mut self) -> Option { + if let Some(cell_ref) = self.state_stack.pop() { + Some(self.follow(cell_ref)) + } else { + None + } + } +} diff --git a/src/prolog/io.rs b/src/prolog/io.rs new file mode 100644 index 00000000..6fbf3134 --- /dev/null +++ b/src/prolog/io.rs @@ -0,0 +1,290 @@ +use prolog::ast::*; +use prolog::codegen::*; +use prolog::prolog_parser::*; +use prolog::machine::*; + +use termion::raw::IntoRawMode; +use termion::input::TermRead; +use termion::event::Key; + +use std::io::{Write, stdin, stdout}; +use std::fmt; + +impl fmt::Display for Constant { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match self { + &Constant::Atom(ref atom) => + write!(f, "{}", atom), + &Constant::EmptyList => + write!(f, "[]") + } + } +} + +impl fmt::Display for FactInstruction { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match self { + &FactInstruction::GetConstant(Level::Shallow, ref constant, ref r) => + write!(f, "get_constant {}, A{}", constant, r.reg_num()), + &FactInstruction::GetConstant(Level::Deep, ref constant, ref r) => + write!(f, "get_constant {}, {}", constant, r), + &FactInstruction::GetList(Level::Shallow, ref r) => + write!(f, "get_list A{}", r.reg_num()), + &FactInstruction::GetList(Level::Deep, ref r) => + write!(f, "get_list {}", r), + &FactInstruction::GetStructure(Level::Deep, ref name, ref arity, ref r) => + write!(f, "get_structure {}/{}, {}", name, arity, r), + &FactInstruction::GetStructure(Level::Shallow, ref name, ref arity, ref r) => + write!(f, "get_structure {}/{}, A{}", name, arity, r.reg_num()), + &FactInstruction::GetValue(ref x, ref a) => + write!(f, "get_value {}, A{}", x, a), + &FactInstruction::GetVariable(ref x, ref a) => + write!(f, "get_variable {}, A{}", x, a), + &FactInstruction::UnifyConstant(ref constant) => + write!(f, "unify_constant {}", constant), + &FactInstruction::UnifyVariable(ref r) => + write!(f, "unify_variable {}", r), + &FactInstruction::UnifyValue(ref r) => + write!(f, "unify_value {}", r) + } + } +} + +impl fmt::Display for QueryInstruction { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match self { + &QueryInstruction::PutConstant(Level::Shallow, ref constant, ref r) => + write!(f, "put_constant {}, A{}", constant, r.reg_num()), + &QueryInstruction::PutConstant(Level::Deep, ref constant, ref r) => + write!(f, "put_constant {}, {}", constant, r), + &QueryInstruction::PutList(Level::Shallow, ref r) => + write!(f, "put_list A{}", r.reg_num()), + &QueryInstruction::PutList(Level::Deep, ref r) => + write!(f, "put_list {}", r), + &QueryInstruction::PutStructure(Level::Deep, ref name, ref arity, ref r) => + write!(f, "put_structure {}/{}, {}", name, arity, r), + &QueryInstruction::PutStructure(Level::Shallow, ref name, ref arity, ref r) => + write!(f, "put_structure {}/{}, A{}", name, arity, r.reg_num()), + &QueryInstruction::PutValue(ref x, ref a) => + write!(f, "put_value {}, A{}", x, a), + &QueryInstruction::PutVariable(ref x, ref a) => + write!(f, "put_variable {}, A{}", x, a), + &QueryInstruction::SetConstant(ref constant) => + write!(f, "set_constant {}", constant), + &QueryInstruction::SetVariable(ref r) => + write!(f, "set_variable {}", r), + &QueryInstruction::SetValue(ref r) => + write!(f, "set_value {}", r) + } + } +} + +impl fmt::Display for ControlInstruction { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match self { + &ControlInstruction::Allocate(num_cells) => + write!(f, "allocate {}", num_cells), + &ControlInstruction::Call(ref name, ref arity) => + write!(f, "call {}/{}", name, arity), + &ControlInstruction::Deallocate => + write!(f, "deallocate"), + &ControlInstruction::Proceed => + write!(f, "proceed") + } + } +} + +impl fmt::Display for ChoiceInstruction { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match self { + &ChoiceInstruction::TryMeElse(offset) => + write!(f, "try_me_else {}", offset), + &ChoiceInstruction::RetryMeElse(offset) => + write!(f, "retry_me_else {}", offset), + &ChoiceInstruction::TrustMe => + write!(f, "trust_me") + } + } +} + +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") + } + } +} + +impl fmt::Display for VarReg { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match self { + &VarReg::Norm(RegType::Perm(reg)) => write!(f, "Y{}", reg), + &VarReg::Norm(RegType::Temp(reg)) => write!(f, "X{}", reg), + &VarReg::ArgAndNorm(RegType::Perm(reg), arg) => + write!(f, "Y{} A{}", reg, arg), + &VarReg::ArgAndNorm(RegType::Temp(reg), arg) => + write!(f, "X{} A{}", reg, arg) + } + } +} + +impl fmt::Display for RegType { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match self { + &RegType::Perm(val) => write!(f, "Y{}", val), + &RegType::Temp(val) => write!(f, "X{}", val) + } + } +} + + +fn is_consistent(predicate: &Vec) -> bool { + let name = predicate.first().unwrap().name(); + let arity = predicate.first().unwrap().arity(); + + for clause in predicate.iter().skip(1) { + if !(name == clause.name() && arity == clause.arity()) { + return false; + } + } + + true +} + +#[allow(dead_code)] +pub fn print_code(code: &Code) { + for clause in code { + match clause { + &Line::Fact(ref fact) => + for fact_instr in fact { + println!("{}", fact_instr); + }, + &Line::Choice(ref choice) => + println!("{}", choice), + &Line::Control(ref control) => + println!("{}", control), + &Line::Query(ref query) => + for query_instr in query { + println!("{}", query_instr); + } + } + } +} + +pub fn read() -> String { + let _ = stdout().flush(); + + let mut buffer = String::new(); + let mut result = String::new(); + + let stdin = stdin(); + stdin.read_line(&mut buffer).unwrap(); + + if &*buffer.trim() == ":{" { + buffer.clear(); + + stdin.read_line(&mut buffer).unwrap(); + + while &*buffer.trim() != "}:" { + result += buffer.as_str(); + buffer.clear(); + stdin.read_line(&mut buffer).unwrap(); + } + } else { + result = buffer; + } + + result +} + +pub fn eval(wam: &mut Machine, buffer: &str) -> EvalResult +{ + let result = parse_TopLevel(buffer); + let mut cg = CodeGenerator::new(); + + match &result { + &Ok(TopLevel::Predicate(ref clauses)) => { + if is_consistent(clauses) { + let compiled_pred = cg.compile_predicate(clauses); + wam.add_predicate(clauses, compiled_pred); + + EvalResult::EntrySuccess + } else { + let msg = r"Error: predicate is inconsistent. +Each predicate must have the same name and arity."; + + println!("{}", msg); + EvalResult::EntryFailure + } + }, + &Ok(TopLevel::Fact(ref fact)) => { + let compiled_fact = cg.compile_fact(&fact); + wam.add_fact(fact, compiled_fact); + EvalResult::EntrySuccess + }, + &Ok(TopLevel::Rule(ref rule)) => { + let compiled_rule = cg.compile_rule(&rule); + wam.add_rule(rule, compiled_rule); + EvalResult::EntrySuccess + }, + &Ok(TopLevel::Query(ref query)) => { + let compiled_query = cg.compile_query(&query); + wam.run_query(compiled_query, &cg) + }, + &Err(_) => { + println!("Grammatical error of some kind!"); + EvalResult::EntryFailure + } + } +} + +pub fn print(wam: &mut Machine, result: EvalResult) { + match result { + EvalResult::InitialQuerySuccess(heap_locs) => { + println!("yes"); + + if heap_locs.is_empty() { + return; + } + + 'outer: loop { + let mut result = EvalResult::QueryFailure; + let bindings = wam.heap_view(&heap_locs); + + let stdin = stdin(); + let mut stdout = stdout().into_raw_mode().unwrap(); + + write!(stdout, "{}\n\r", bindings).unwrap(); + stdout.flush().unwrap(); + + if !wam.or_stack_is_empty() { + write!(stdout, "Press ; to continue or . to abort.\n\r").unwrap(); + stdout.flush().unwrap(); + + for c in stdin.keys() { + match c.unwrap() { + Key::Char(';') => { + result = wam.continue_query(); + break; + }, + Key::Char('.') => + break 'outer, + _ => {} + } + }; + + if let &EvalResult::QueryFailure = &result { + write!(stdout, "no\n\r").unwrap(); + stdout.flush().unwrap(); + break; + } + } else { + break; + } + } + }, + EvalResult::QueryFailure => println!("no"), + _ => {} + }; +} diff --git a/src/prolog/iterators.rs b/src/prolog/iterators.rs new file mode 100644 index 00000000..a33382e1 --- /dev/null +++ b/src/prolog/iterators.rs @@ -0,0 +1,209 @@ +use prolog::ast::*; + +use std::cell::Cell; +use std::collections::VecDeque; +use std::vec::Vec; + +enum IteratorState<'a> { + AnonVar(Level), + Clause(Level, usize, &'a Cell, &'a Atom, &'a Vec>), + Constant(Level, &'a Cell, &'a Constant), + InitialCons(Level, &'a Cell, &'a Term, &'a Term), + FinalCons(Level, &'a Cell, &'a Term, &'a Term), + 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::AnonVar => + IteratorState::AnonVar(lvl), + &Term::Clause(ref cell, ref atom, ref child_terms) => + IteratorState::Clause(lvl, 0, cell, atom, child_terms), + &Term::Cons(ref cell, ref head, ref tail) => + IteratorState::InitialCons(lvl, cell, head.as_ref(), tail.as_ref()), + &Term::Constant(ref cell, ref constant) => + IteratorState::Constant(lvl, cell, constant), + &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 push_final_cons(&mut self, + lvl: Level, + cell: &'a Cell, + head: &'a Term, + tail: &'a Term) + { + self.state_stack.push(IteratorState::FinalCons(lvl, cell, head, tail)); + } + + fn new(term: &'a Term) -> QueryIterator<'a> { + let state = match term { + &Term::AnonVar => + IteratorState::AnonVar(Level::Shallow), + &Term::Clause(_, _, ref terms) => + IteratorState::RootClause(0, terms), + &Term::Cons(ref cell, ref head, ref tail) => + IteratorState::InitialCons(Level::Shallow, cell, head.as_ref(), tail.as_ref()), + &Term::Constant(ref cell, ref constant) => + IteratorState::Constant(Level::Shallow, cell, constant), + &Term::Var(ref cell, ref var) => + IteratorState::Var(Level::Shallow, 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::AnonVar(lvl) => + return Some(TermRef::AnonVar(lvl)), + 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::InitialCons(lvl, cell, head, tail) => { + self.push_final_cons(lvl, cell, head, tail); + self.push_subterm(Level::Deep, head); + self.push_subterm(Level::Deep, tail); + }, + IteratorState::FinalCons(lvl, cell, head, tail) => + return Some(TermRef::Cons(lvl, cell, head, tail)), + IteratorState::Constant(lvl, cell, constant) => + return Some(TermRef::Constant(lvl, cell, constant)), + 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::AnonVar => + vec![IteratorState::AnonVar(Level::Shallow)], + &Term::Clause(_, _, ref terms) => + vec![IteratorState::RootClause(0, terms)], + &Term::Cons(ref cell, ref head, ref tail) => + vec![IteratorState::InitialCons(Level::Shallow, + cell, + head.as_ref(), + tail.as_ref())], + &Term::Constant(ref cell, ref constant) => + vec![IteratorState::Constant(Level::Shallow, cell, constant)], + &Term::Var(ref cell, ref var) => + vec![IteratorState::Var(Level::Shallow, 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::AnonVar(lvl) => + return Some(TermRef::AnonVar(lvl)), + 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::InitialCons(lvl, cell, head, tail) => { + self.push_subterm(Level::Deep, head); + self.push_subterm(Level::Deep, tail); + + return Some(TermRef::Cons(lvl, cell, head, tail)); + }, + IteratorState::Constant(lvl, cell, constant) => + return Some(TermRef::Constant(lvl, cell, constant)), + 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/prolog/machine.rs b/src/prolog/machine.rs new file mode 100644 index 00000000..3e8f3fd3 --- /dev/null +++ b/src/prolog/machine.rs @@ -0,0 +1,784 @@ +use prolog::ast::*; +use prolog::codegen::*; +use prolog::heapview::*; +use prolog::and_stack::*; +use prolog::or_stack::*; + +use std::collections::HashMap; +use std::ops::{Index, IndexMut}; +use std::vec::Vec; + +#[derive(Clone, Copy)] +enum MachineMode { + Read, + Write +} + +struct MachineState { + h: usize, + s: usize, + p: CodePtr, + b: usize, + e: usize, + num_of_args: usize, + cp: CodePtr, + fail: bool, + heap: Heap, + mode: MachineMode, + and_stack: AndStack, + or_stack: OrStack, + registers: Registers, + trail: Vec, + tr: usize, + hb: usize +} + +type CodeDir = HashMap<(Atom, usize), usize>; + +pub struct Machine { + ms: MachineState, + code: Code, + code_dir: CodeDir +} + +impl Index for MachineState { + type Output = Addr; + + fn index(&self, reg: RegType) -> &Self::Output { + match reg { + RegType::Temp(temp) => &self.registers[temp], + RegType::Perm(perm) => { + let e = self.e; + &self.and_stack[e][perm] + } + } + } +} + +impl IndexMut for MachineState { + fn index_mut(&mut self, reg: RegType) -> &mut Self::Output { + match reg { + RegType::Temp(temp) => &mut self.registers[temp], + RegType::Perm(perm) => { + let e = self.e; + &mut self.and_stack[e][perm] + } + } + } +} + +impl Machine { + pub fn new() -> Self { + Machine { + ms: MachineState::new(), + code: Vec::new(), + code_dir: HashMap::new() + } + } + + pub fn failed(&self) -> bool { + self.ms.fail + } + + pub fn add_fact(&mut self, fact: &Term, mut code: Code) { + if fact.name().is_some() { + let p = self.code.len(); + let name = fact.name().unwrap().clone(); + let arity = fact.arity(); + + self.code.append(&mut code); + self.code_dir.insert((name, arity), p); + } + } + + pub fn add_rule(&mut self, rule: &Rule, mut code: Code) { + if rule.head.0.name().is_some() { + let p = self.code.len(); + let name = rule.head.0.name().unwrap().clone(); + let arity = rule.head.0.arity(); + + self.code.append(&mut code); + self.code_dir.insert((name, arity), p); + } + } + + pub fn add_predicate(&mut self, pred: &Vec, mut code: Code) + { + let p = self.code.len(); + let name = pred.first().unwrap().name().clone(); + let arity = pred.first().unwrap().arity(); + + self.code.append(&mut code); + self.code_dir.insert((name, arity), p); + } + + fn execute_instr<'a>(&mut self, instr_src: LineOrCodeOffset<'a>) -> bool + { + let mut instr = match instr_src { + LineOrCodeOffset::Instruction(instr) => instr, + LineOrCodeOffset::Offset(p) => &self.code[p] + }; + + loop { + match instr { + &Line::Choice(ref choice_instr) => + self.ms.execute_choice_instr(choice_instr), + &Line::Fact(ref fact) => { + for fact_instr in fact { + if self.failed() { + break; + } + + self.ms.execute_fact_instr(&fact_instr); + } + self.ms.p += 1; + }, + &Line::Query(ref query) => { + for query_instr in query { + if self.failed() { + break; + } + + self.ms.execute_query_instr(&query_instr); + } + self.ms.p += 1; + }, + &Line::Control(ref control_instr) => + self.ms.execute_ctrl_instr(&self.code_dir, control_instr), + } + + if self.failed() { + let p = self.ms + .or_stack + .top() + .map(|fr| fr.bp) + .unwrap_or_default(); + + if let CodePtr::TopLevel = p { + return false; + } else { + self.ms.fail = false; + self.ms.p = p; + } + } + + match self.ms.p { + CodePtr::DirEntry(p) if p < self.code.len() => + instr = &self.code[p], + _ => break + } + } + + true + } + + pub fn heap_view(&self, var_dir: &HeapVarDict) -> String { + let mut result = String::new(); + + for (var, addr) in var_dir { + let mut viewer = HeapCellViewer::new(&self.ms.heap, + &self.ms.and_stack, + addr); + + if result != "" { + result += "\n\r"; + } + + result += var.as_str(); + result += " = "; + + while let Some(view) = viewer.next() { + match view { + CellView::Con(&Constant::EmptyList) => + result += "[]", + CellView::Con(&Constant::Atom(ref atom)) => + result += atom.as_str(), + CellView::HeapVar(cell_num) => { + result += "_"; + result += cell_num.to_string().as_str(); + }, + CellView::StackVar(fr, sc) => { + result += "_"; + result += fr.to_string().as_str(); + result += "_"; + result += sc.to_string().as_str(); + }, + CellView::Str(_, ref name) => + result += name.as_str(), + CellView::TToken(TToken::Bar) => { + match viewer.peek() { + Some(CellView::Con(&Constant::EmptyList)) => { + viewer.next(); + }, + Some(CellView::TToken(TToken::LSBracket(loc))) => { + result += ", "; + + viewer.next(); + viewer.remove_token(loc); + }, + _ => result += " | " + }; + }, + CellView::TToken(token) => + result += token.as_str() + }; + } + } + + result + } + + pub fn run_query(&mut self, code: Code, cg: &CodeGenerator) -> EvalResult + { + let mut succeeded = true; + let mut heap_locs = HashMap::new(); + + for instr in code.iter().take(1) { + succeeded = self.execute_instr(LineOrCodeOffset::from(instr)); + } + + if succeeded { + for (var, vr) in cg.vars() { + let addr = self.ms.registers[vr.root_register()].clone(); + heap_locs.insert((*var).clone(), addr); + } + + for instr in code.iter().skip(1) { + succeeded = self.execute_instr(LineOrCodeOffset::from(instr)); + if !succeeded { + break; + } + } + } + + if succeeded { + EvalResult::InitialQuerySuccess(heap_locs) + } else { + EvalResult::QueryFailure + } + } + + pub fn or_stack_is_empty(&self) -> bool { + self.ms.or_stack.is_empty() + } + + pub fn continue_query(&mut self) -> EvalResult + { + if !self.or_stack_is_empty() { + let b = self.ms.b; + self.ms.p = self.ms.or_stack[b].bp; + + let succeeded = if let CodePtr::DirEntry(p) = self.ms.p { + self.execute_instr(LineOrCodeOffset::Offset(p)) + } else { + false + }; + + if succeeded { + EvalResult::SubsequentQuerySuccess + } else { + EvalResult::QueryFailure + } + } else { + EvalResult::QueryFailure + } + } + + pub fn reset(&mut self) { + self.ms.reset(); + } +} + +impl MachineState { + fn new() -> MachineState { + MachineState { h: 0, + s: 0, + p: CodePtr::TopLevel, + b: 0, + e: 0, + num_of_args: 0, + cp: CodePtr::TopLevel, + fail: false, + heap: Vec::with_capacity(256), + mode: MachineMode::Write, + and_stack: AndStack::new(), + or_stack: OrStack::new(), + registers: vec![Addr::HeapCell(0); 64], + trail: Vec::new(), + tr: 0, + hb: 0 + } + } + + fn num_frames(&self) -> usize { + self.and_stack.len() + self.or_stack.len() + } + + fn store(&self, a: Addr) -> Addr { + match a { + Addr::HeapCell(r) => self.heap[r].as_addr(r), + Addr::StackCell(fr, sc) => self.and_stack[fr][sc].clone(), + addr => addr + } + } + + fn deref(&self, a: Addr) -> Addr { + let mut a = a; + + loop { + let value = self.store(a.clone()); + + if value.is_ref() && value != a { + a = value; + continue; + } + + return a; + }; + } + + fn bind(&mut self, r1: Ref, a2: Addr) { + let t2 = self.store(a2); + + match r1 { + Ref::StackCell(fr, sc) => + self.and_stack[fr][sc] = t2, + Ref::HeapCell(hc) => + self.heap[hc] = HeapCellValue::from(t2) + }; + + self.trail(r1); + } + + fn unify(&mut self, a1: Addr, a2: Addr) { + let mut pdl = 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.store(d1.clone()), self.store(d2.clone())) { + (Addr::HeapCell(hc), _) => + self.bind(Ref::HeapCell(hc), d2), + (_, Addr::HeapCell(hc)) => + self.bind(Ref::HeapCell(hc), d1), + (Addr::StackCell(fr, sc), _) => + self.bind(Ref::StackCell(fr, sc), d2), + (_, Addr::StackCell(fr, sc)) => + self.bind(Ref::StackCell(fr, sc), d1), + (Addr::Lis(a1), Addr::Lis(a2)) => { + pdl.push(Addr::HeapCell(a1)); + pdl.push(Addr::HeapCell(a2)); + + pdl.push(Addr::HeapCell(a1 + 1)); + pdl.push(Addr::HeapCell(a2 + 1)); + }, + (Addr::Con(c1), Addr::Con(c2)) => { + if c1 != c2 { + self.fail = true; + } + }, + (Addr::Str(a1), Addr::Str(a2)) => { + let r1 = &self.heap[a1]; + let r2 = &self.heap[a2]; + + if let &HeapCellValue::NamedStr(n1, ref f1) = r1 { + if let &HeapCellValue::NamedStr(n2, ref f2) = r2 { + if n1 == n2 && *f1 == *f2 { + for i in 1 .. n1 + 1 { + pdl.push(Addr::HeapCell(a1 + i)); + pdl.push(Addr::HeapCell(a2 + i)); + } + + continue; + } + } + } + + self.fail = true; + }, + _ => self.fail = true + }; + } + } + } + + fn trail(&mut self, r: Ref) { + match r { + Ref::HeapCell(hc) => { + if hc < self.hb { + self.trail.push(r); + self.tr += 1; + } + }, + Ref::StackCell(fr, _) => { + let fr_gi = self.and_stack[fr].global_index; + let b_gi = if !self.or_stack.is_empty() { + self.or_stack[self.b].global_index + } else { + 0 + }; + + if fr_gi < b_gi { + self.trail.push(r); + self.tr += 1; + } + } + } + } + + fn unwind_trail(&mut self, a1: usize, a2: usize) { + for i in a1 .. a2 { + match self.trail[i] { + Ref::HeapCell(r) => + self.heap[r] = HeapCellValue::Ref(Ref::HeapCell(r)), + Ref::StackCell(fr, sc) => + self.and_stack[fr][sc] = Addr::StackCell(fr, sc) + } + } + } + + fn execute_fact_instr(&mut self, instr: &FactInstruction) { + match instr { + &FactInstruction::GetConstant(_, ref constant, reg) => { + let addr = self.deref(self[reg].clone()); + + match self.store(addr) { + Addr::HeapCell(hc) => { + self.heap[hc] = HeapCellValue::Con(constant.clone()); + self.trail(Ref::HeapCell(hc)); + }, + Addr::StackCell(fr, sc) => { + self.and_stack[fr][sc] = Addr::Con(constant.clone()); + self.trail(Ref::StackCell(fr, sc)); + }, + Addr::Con(c) => { + if c != *constant { + self.fail = true; + } + }, + _ => self.fail = true + }; + }, + &FactInstruction::GetList(_, reg) => { + let addr = self.deref(self[reg].clone()); + + match self.store(addr.clone()) { + Addr::HeapCell(hc) => { + let h = self.h; + + self.heap.push(HeapCellValue::Lis(h+1)); + self.bind(Ref::HeapCell(hc), Addr::HeapCell(h)); + + self.h += 1; + self.mode = MachineMode::Write; + }, + Addr::StackCell(fr, sc) => { + let h = self.h; + + self.heap.push(HeapCellValue::Lis(h+1)); + self.bind(Ref::StackCell(fr, sc), Addr::HeapCell(h)); + + self.h += 1; + self.mode = MachineMode::Write; + }, + Addr::Lis(a) => { + self.s = a; + self.mode = MachineMode::Read; + }, + _ => self.fail = true + }; + }, + &FactInstruction::GetStructure(_, ref name, arity, reg) => { + let addr = self.deref(self[reg].clone()); + + match self.store(addr.clone()) { + Addr::Str(a) => { + let result = &self.heap[a]; + + if let &HeapCellValue::NamedStr(narity, ref str) = result { + if narity == arity && *name == *str { + self.s = a + 1; + self.mode = MachineMode::Read; + } else { + self.fail = true; + } + } + }, + Addr::HeapCell(_) | Addr::StackCell(_, _) => { + self.heap.push(HeapCellValue::Str(self.h + 1)); + self.heap.push(HeapCellValue::NamedStr(arity, name.clone())); + + let h = self.h; + + self.bind(addr.as_ref().unwrap(), Addr::HeapCell(h)); + + self.h += 2; + self.mode = MachineMode::Write; + }, + _ => self.fail = true + }; + }, + &FactInstruction::GetVariable(norm, arg) => + self[norm] = self.registers[arg].clone(), + &FactInstruction::GetValue(norm, arg) => { + let norm_addr = self[norm].clone(); + let reg_addr = self.registers[arg].clone(); + + self.unify(norm_addr, reg_addr); + }, + &FactInstruction::UnifyConstant(ref c) => { + match self.mode { + MachineMode::Read => { + let addr = self.deref(Addr::HeapCell(self.s)); + + match self.store(addr) { + Addr::HeapCell(hc) => + self.heap[hc] = HeapCellValue::Con(c.clone()), + Addr::StackCell(fr, sc) => + self.and_stack[fr][sc] = Addr::Con(c.clone()), + Addr::Con(c1) => { + if c1 != *c { + self.fail = true; + } + }, + _ => self.fail = true + }; + }, + MachineMode::Write => { + self.heap.push(HeapCellValue::Con(c.clone())); + self.h += 1; + } + }; + }, + &FactInstruction::UnifyVariable(reg) => { + match self.mode { + MachineMode::Read => + self[reg] = self.heap[self.s].as_addr(self.s), + MachineMode::Write => { + let h = self.h; + + self.heap.push(HeapCellValue::Ref(Ref::HeapCell(h))); + self[reg] = Addr::HeapCell(self.h); + self.h += 1; + } + }; + + self.s += 1; + }, + &FactInstruction::UnifyValue(reg) => { + let s = self.s; + + match self.mode { + MachineMode::Read => { + let reg_addr = self[reg].clone(); + self.unify(reg_addr, Addr::HeapCell(s)); + }, + MachineMode::Write => { + let heap_val = self.store(self[reg].clone()); + self.heap.push(HeapCellValue::from(heap_val)); + self.h += 1; + } + }; + + self.s += 1; + } + }; + } + + fn execute_query_instr(&mut self, instr: &QueryInstruction) { + match instr { + &QueryInstruction::PutConstant(_, ref constant, reg) => + self[reg] = Addr::Con(constant.clone()), + &QueryInstruction::PutList(_, reg) => + self[reg] = Addr::Lis(self.h), + &QueryInstruction::PutStructure(_, ref name, arity, reg) => { + self.heap.push(HeapCellValue::NamedStr(arity, name.clone())); + self[reg] = Addr::Str(self.h); + self.h += 1; + }, + &QueryInstruction::PutValue(norm, arg) => + self.registers[arg] = self[norm].clone(), + &QueryInstruction::PutVariable(norm, arg) => { + let h = self.h; + self.heap.push(HeapCellValue::Ref(Ref::HeapCell(h))); + + self[norm] = Addr::HeapCell(h); + self.registers[arg] = Addr::HeapCell(h); + + self.h += 1; + }, + &QueryInstruction::SetConstant(ref constant) => { + self.heap.push(HeapCellValue::Con(constant.clone())); + self.h += 1; + }, + &QueryInstruction::SetVariable(reg) => { + let h = self.h; + self.heap.push(HeapCellValue::Ref(Ref::HeapCell(h))); + self[reg] = Addr::HeapCell(h); + + self.h += 1; + }, + &QueryInstruction::SetValue(reg) => { + let heap_val = self[reg].clone(); + self.heap.push(HeapCellValue::from(heap_val)); + + self.h += 1; + }, + } + } + + fn execute_ctrl_instr(&mut self, code_dir: &CodeDir, instr: &ControlInstruction) + { + match instr { + &ControlInstruction::Allocate(num_cells) => { + let num_frames = self.num_frames(); + + self.and_stack.push(num_frames + 1, self.e, self.cp, num_cells); + + self.e = self.and_stack.len() - 1; + self.p += 1; + }, + &ControlInstruction::Call(ref name, arity) => { + let compiled_tl_index = code_dir.get(&(name.clone(), arity)) + .map(|index| *index); + + match compiled_tl_index { + Some(compiled_tl_index) => { + self.cp = self.p + 1; + self.num_of_args = arity; + self.p = CodePtr::DirEntry(compiled_tl_index); + }, + None => self.fail = true + }; + }, + &ControlInstruction::Deallocate => { + let e = self.e; + + let num_frame_e = self.and_stack.top().unwrap().global_index; + let num_frame_b = self.or_stack + .top() + .map(|fr| fr.global_index) + .unwrap_or(0); + + self.p = self.and_stack[e].cp; + self.e = self.and_stack[e].e; + + if num_frame_e > num_frame_b { + let top_e = self.and_stack.top().unwrap().e; + self.and_stack.drop_frames(top_e - self.e + 1); + } + }, + &ControlInstruction::Proceed => + self.p = self.cp, + }; + } + + fn execute_choice_instr(&mut self, instr: &ChoiceInstruction) + { + match instr { + &ChoiceInstruction::TryMeElse(offset) => { + let n = self.num_of_args; + let num_frames = self.num_frames(); + + self.or_stack.push(num_frames + 1, + self.e, + self.cp, + self.b, + self.p + offset, + self.tr, + self.h, + self.num_of_args); + + self.b = self.or_stack.len() - 1; + let b = self.b; + + for i in 1 .. n + 1 { + self.or_stack[b][i] = self.registers[i].clone(); + } + + self.hb = self.h; + self.p += 1; + }, + &ChoiceInstruction::RetryMeElse(offset) => { + let b = self.b; + let n = self.or_stack[b].num_args(); + + for i in 1 .. n + 1 { + self.registers[i] = self.or_stack[b][i].clone(); + } + + self.e = self.or_stack[b].e; + self.cp = self.or_stack[b].cp; + + self.or_stack[b].bp = self.p + offset; + + let old_tr = self.or_stack[b].tr; + let curr_tr = self.tr; + + self.unwind_trail(old_tr, curr_tr); + self.tr = self.or_stack[b].tr; + + self.trail.truncate(self.tr); + self.heap.truncate(self.or_stack[b].h); + + self.h = self.or_stack[b].h; + self.hb = self.h; + + self.p += 1; + }, + &ChoiceInstruction::TrustMe => { + let b = self.b; + let n = self.or_stack[b].num_args(); + + for i in 1 .. n + 1 { + self.registers[i] = self.or_stack[b][i].clone(); + } + + self.e = self.or_stack[b].e; + self.cp = self.or_stack[b].cp; + + let old_tr = self.or_stack[b].tr; + let curr_tr = self.tr; + + self.unwind_trail(old_tr, curr_tr); + + self.tr = self.or_stack[b].tr; + self.trail.truncate(self.tr); + + self.h = self.or_stack[b].h; + self.heap.truncate(self.h); + + self.b = self.or_stack[b].b; + + self.or_stack.pop(); + + self.hb = self.h; + self.p += 1; + } + } + } + + fn reset(&mut self) { + self.h = 0; + self.hb = 0; + self.e = 0; + self.b = 0; + self.s = 0; + self.tr = 0; + self.p = CodePtr::TopLevel; + self.cp = CodePtr::TopLevel; + self.num_of_args = 0; + + self.fail = false; + self.trail.clear(); + self.heap.clear(); + self.mode = MachineMode::Write; + self.and_stack.clear(); + self.or_stack.clear(); + self.registers = vec![Addr::HeapCell(0); 64]; + } +} diff --git a/src/prolog/mod.rs b/src/prolog/mod.rs new file mode 100644 index 00000000..7eb95ba3 --- /dev/null +++ b/src/prolog/mod.rs @@ -0,0 +1,9 @@ +pub mod and_stack; +pub mod ast; +pub mod codegen; +pub mod heapview; +pub mod io; +pub mod iterators; +pub mod prolog_parser; +pub mod machine; +pub mod or_stack; diff --git a/src/prolog/or_stack.rs b/src/prolog/or_stack.rs new file mode 100644 index 00000000..80252575 --- /dev/null +++ b/src/prolog/or_stack.rs @@ -0,0 +1,112 @@ +use prolog::ast::*; + +use std::ops::{Index, IndexMut}; +use std::vec::Vec; + +pub struct Frame { + pub global_index: usize, + pub e: usize, + pub cp: CodePtr, + pub b: usize, + pub bp: CodePtr, + pub tr: usize, + pub h: usize, + args: Vec +} + +impl Frame { + fn new(global_index: usize, + e: usize, + cp: CodePtr, + b: usize, + bp: CodePtr, + tr: usize, + h: usize, + n: usize) + -> Self + { + Frame { + global_index: global_index, + e: e, + cp: cp, + b: b, + bp: bp, + tr: tr, + h: h, + args: vec![Addr::HeapCell(0); n] + } + } + + pub fn num_args(&self) -> usize { + self.args.len() + } +} + +pub struct OrStack(Vec); + +impl OrStack { + pub fn new() -> Self { + OrStack(Vec::new()) + } + + pub fn push(&mut self, + global_index: usize, + e: usize, + cp: CodePtr, + b: usize, + bp: CodePtr, + tr: usize, + h: usize, + n: usize) + { + self.0.push(Frame::new(global_index, e, cp, b, bp, tr, h, n)); + } + + pub fn len(&self) -> usize { + self.0.len() + } + + pub fn clear(&mut self) { + self.0.clear() + } + + pub fn top(&self) -> Option<&Frame> { + self.0.last() + } + + pub fn pop(&mut self) { + self.0.pop(); + } + + pub fn is_empty(&self) -> bool { + self.0.is_empty() + } +} + +impl Index for OrStack { + type Output = Frame; + + fn index(&self, index: usize) -> &Self::Output { + self.0.index(index) + } +} + +impl IndexMut for OrStack { + fn index_mut(&mut self, index: usize) -> &mut Self::Output { + self.0.index_mut(index) + } +} + +impl Index for Frame { + type Output = Addr; + + fn index(&self, index: usize) -> &Self::Output { + self.args.index(index - 1) + } +} + +impl IndexMut for Frame { + fn index_mut(&mut self, index: usize) -> &mut Self::Output { + self.args.index_mut(index - 1) + } +} diff --git a/src/prolog/prolog_parser.lalrpop b/src/prolog/prolog_parser.lalrpop new file mode 100644 index 00000000..be557c7d --- /dev/null +++ b/src/prolog/prolog_parser.lalrpop @@ -0,0 +1,77 @@ +use prolog::ast::*; + +use std::cell::Cell; + +grammar; + +pub TopLevel: TopLevel = { + "?-" "." => TopLevel::Query(t), + => TopLevel::Predicate(<>), + "." => TopLevel::Rule(<>), + "." => TopLevel::Fact(<>) +}; + +Atom : Atom = { + r"[a-z][a-z0-9_]*" => <>.trim().to_string(), +}; + +BoxedTerm : Box = { + => Box::new(t) +}; + +Clause : Term = { + "(" ",")*> ")" => { + let mut ts = ts; + ts.push(t); + Term::Clause(Cell::default(), a, ts) + } +}; + +List : Term = { + "[]" => Term::Constant(Cell::default(), Constant::EmptyList), + "[" "]" => <> +}; + +ListInternals : Term = { + => Term::Cons(Cell::default(), + t, + Box::new(Term::Constant(Cell::default(), + Constant::EmptyList))), + "," => Term::Cons(Cell::default(), + t, + Box::new(li)), + "|" => Term::Cons(Cell::default(), t1, t2) +}; + +Predicate : Vec = { + )+> => { + let mut pcs = pcs; + pcs.push(pc); + pcs + } +}; + +PredicateClause : PredicateClause = { + "." => PredicateClause::Rule(<>), + "." => PredicateClause::Fact(<>) +}; + +Rule : Rule = { + ":-" )*> => + Rule { head: (c, h), clauses: cs }, + ":-" )*> => + Rule { head: (Term::Constant(Cell::default(), Constant::Atom(a)), h), + clauses: cs } +}; + +Term : Term = { + => Term::Constant(Cell::default(), Constant::Atom(<>)), + => <>, + => <>, + => Term::Var(Cell::default(), <>), + "_" => Term::AnonVar +}; + +Var : Var = { + r"[A-Z][a-z0-9_]*" => <>.trim().to_string() +}; diff --git a/src/prolog/prolog_parser.rs b/src/prolog/prolog_parser.rs new file mode 100644 index 00000000..9d29dbaa --- /dev/null +++ b/src/prolog/prolog_parser.rs @@ -0,0 +1,2815 @@ +use prolog::ast::*; +use std::cell::Cell; +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 prolog::ast::*; + use std::cell::Cell; + 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_3a_2d_22(&'input str), + Term_22_3f_2d_22(&'input str), + Term_22_5b_22(&'input str), + Term_22_5b_5d_22(&'input str), + Term_22_5d_22(&'input str), + Term_22___22(&'input str), + Term_22_7c_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), + Termerror(__lalrpop_util::ErrorRecovery), + Nt_28_22_2c_22_20_3cTerm_3e_29(Term), + Nt_28_22_2c_22_20_3cTerm_3e_29_2a(::std::vec::Vec), + Nt_28_22_2c_22_20_3cTerm_3e_29_2b(::std::vec::Vec), + 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>), + Nt_28_3cPredicateClause_3e_29(PredicateClause), + Nt_28_3cPredicateClause_3e_29_2b(::std::vec::Vec), + NtAtom(Atom), + NtBoxedTerm(Box), + NtClause(Term), + NtList(Term), + NtListInternals(Term), + NtPredicate(Vec), + NtPredicateClause(PredicateClause), + NtRule(Rule), + NtTerm(Term), + NtTopLevel(TopLevel), + NtVar(Var), + Nt____TopLevel(TopLevel), + } + const __ACTION: &'static [i32] = &[ + // State 0 + 0, 0, 0, 0, 0, 12, 13, 14, 0, 15, 0, 16, 17, 0, + // State 1 + 0, 0, 0, 0, 0, 0, 13, 14, 0, 15, 0, 16, 17, 0, + // State 2 + 21, 0, 0, -30, 22, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 3 + 0, 0, 0, -31, 23, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 4 + 0, 0, 0, -32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 5 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 6 + 0, 0, 0, 0, 0, 0, -12, -12, 0, -12, 0, -12, -12, 0, + // State 7 + 0, 0, 0, 24, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 8 + 0, 0, 0, 25, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 9 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 10 + 0, 0, 0, -33, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 11 + 0, 0, 0, 0, 0, 0, 13, 14, 0, 15, 0, 16, 29, 0, + // State 12 + 0, 0, 0, 0, 0, 0, 37, 38, 0, 39, 0, 40, 41, 0, + // State 13 + 0, 0, 0, -18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 14 + 0, 0, 0, -34, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 15 + 0, 0, 0, -39, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 16 + -14, 0, 0, -14, -14, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 17 + 0, 0, 0, 0, 0, 0, -13, -13, 0, -13, 0, -13, -13, 0, + // State 18 + 0, 0, 0, 42, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 19 + 0, 0, 0, 43, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 20 + 0, 0, 0, 0, 0, 0, 51, 52, 0, 53, 0, 54, 55, 0, + // State 21 + 0, 0, 0, 0, 0, 0, 61, 62, 0, 63, 0, 64, 65, 0, + // State 22 + 0, 0, 0, 0, 0, 0, 61, 62, 0, 63, 0, 64, 65, 0, + // State 23 + 0, 0, 0, 0, 0, 0, -24, -24, 0, -24, 0, -24, -24, 0, + // State 24 + 0, 0, 0, 0, 0, 0, -25, -25, 0, -25, 0, -25, -25, 0, + // State 25 + 67, 0, 0, -30, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 26 + 0, 0, 0, -31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 27 + 0, 0, 0, 68, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 28 + -14, 0, 0, -14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 29 + 69, 0, -30, 0, 0, 0, 0, 0, -30, 0, -30, 0, 0, 0, + // State 30 + 0, 0, 70, 0, 0, 0, 0, 0, -20, 0, 71, 0, 0, 0, + // State 31 + 0, 0, -31, 0, 0, 0, 0, 0, -31, 0, -31, 0, 0, 0, + // State 32 + 0, 0, -32, 0, 0, 0, 0, 0, -32, 0, -32, 0, 0, 0, + // State 33 + 0, 0, 0, 0, 0, 0, 0, 0, 72, 0, 0, 0, 0, 0, + // State 34 + 0, 0, -15, 0, 0, 0, 0, 0, -15, 0, -15, 0, 0, 0, + // State 35 + 0, 0, -33, 0, 0, 0, 0, 0, -33, 0, -33, 0, 0, 0, + // State 36 + 0, 0, 0, 0, 0, 0, 37, 38, 0, 39, 0, 40, 41, 0, + // State 37 + 0, 0, -18, 0, 0, 0, 0, 0, -18, 0, -18, 0, 0, 0, + // State 38 + 0, 0, -34, 0, 0, 0, 0, 0, -34, 0, -34, 0, 0, 0, + // State 39 + 0, 0, -39, 0, 0, 0, 0, 0, -39, 0, -39, 0, 0, 0, + // State 40 + -14, 0, -14, 0, 0, 0, 0, 0, -14, 0, -14, 0, 0, 0, + // State 41 + 0, 0, 0, 0, 0, 0, -24, -24, 0, -24, 0, -24, -24, 0, + // State 42 + 0, 0, 0, 0, 0, 0, -25, -25, 0, -25, 0, -25, -25, 0, + // State 43 + 0, 0, 0, 0, 0, 0, 51, 52, 0, 53, 0, 54, 55, 0, + // State 44 + 75, -30, -30, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 45 + 0, 76, 77, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 46 + 0, -31, -31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 47 + 0, -32, -32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 48 + 0, -15, -15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 49 + 0, -33, -33, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 50 + 0, 0, 0, 0, 0, 0, 37, 38, 0, 39, 0, 40, 41, 0, + // State 51 + 0, -18, -18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 52 + 0, -34, -34, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 53 + 0, -39, -39, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 54 + -14, -14, -14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 55 + 79, 0, -30, -30, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 56 + 0, 0, -31, -31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 57 + 0, 0, -32, -32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 58 + 0, 0, 81, -28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 59 + 0, 0, -33, -33, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 60 + 0, 0, 0, 0, 0, 0, 37, 38, 0, 39, 0, 40, 41, 0, + // State 61 + 0, 0, -18, -18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 62 + 0, 0, -34, -34, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 63 + 0, 0, -39, -39, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 64 + -14, 0, -14, -14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 65 + 0, 0, 81, -26, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 66 + 0, 0, 0, 0, 0, 0, 51, 52, 0, 53, 0, 54, 55, 0, + // State 67 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 68 + 0, 0, 0, 0, 0, 0, 51, 52, 0, 53, 0, 54, 55, 0, + // State 69 + 0, 0, 0, 0, 0, 0, 37, 38, 0, 39, 0, 40, 41, 0, + // State 70 + 0, 0, 0, 0, 0, 0, 95, 96, 0, 97, 0, 98, 99, 0, + // State 71 + 0, 0, 0, -19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 72 + 0, 0, 0, 0, 0, 0, 0, 0, 100, 0, 0, 0, 0, 0, + // State 73 + 0, 101, 102, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 74 + 0, 0, 0, 0, 0, 0, 51, 52, 0, 53, 0, 54, 55, 0, + // State 75 + 0, 0, 0, -16, -16, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 76 + 0, 0, 0, 0, 0, 0, -9, -9, 0, -9, 0, -9, -9, 0, + // State 77 + 0, 0, 0, 0, 0, 0, 0, 0, 105, 0, 0, 0, 0, 0, + // State 78 + 0, 0, 0, 0, 0, 0, 51, 52, 0, 53, 0, 54, 55, 0, + // State 79 + 0, 0, 108, -29, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 80 + 0, 0, 0, 0, 0, 0, 61, 62, 0, 63, 0, 64, 65, 0, + // State 81 + 0, 0, 0, 0, 0, 0, 0, 0, 110, 0, 0, 0, 0, 0, + // State 82 + 0, 0, 108, -27, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 83 + 0, 0, 0, 0, 0, 0, 51, 52, 0, 53, 0, 54, 55, 0, + // State 84 + 0, 112, 77, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 85 + 0, 0, 0, 0, 0, 0, 51, 52, 0, 53, 0, 54, 55, 0, + // State 86 + 0, 114, 77, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 87 + 0, 0, 0, 0, 0, 0, 0, 0, -21, 0, 0, 0, 0, 0, + // State 88 + 115, 0, 0, 0, 0, 0, 0, 0, -30, 0, 0, 0, 0, 0, + // State 89 + 0, 0, 0, 0, 0, 0, 0, 0, -22, 0, 0, 0, 0, 0, + // State 90 + 0, 0, 0, 0, 0, 0, 0, 0, -31, 0, 0, 0, 0, 0, + // State 91 + 0, 0, 0, 0, 0, 0, 0, 0, -32, 0, 0, 0, 0, 0, + // State 92 + 0, 0, 0, 0, 0, 0, 0, 0, -15, 0, 0, 0, 0, 0, + // State 93 + 0, 0, 0, 0, 0, 0, 0, 0, -33, 0, 0, 0, 0, 0, + // State 94 + 0, 0, 0, 0, 0, 0, 37, 38, 0, 39, 0, 40, 41, 0, + // State 95 + 0, 0, 0, 0, 0, 0, 0, 0, -18, 0, 0, 0, 0, 0, + // State 96 + 0, 0, 0, 0, 0, 0, 0, 0, -34, 0, 0, 0, 0, 0, + // State 97 + 0, 0, 0, 0, 0, 0, 0, 0, -39, 0, 0, 0, 0, 0, + // State 98 + -14, 0, 0, 0, 0, 0, 0, 0, -14, 0, 0, 0, 0, 0, + // State 99 + 0, 0, -19, 0, 0, 0, 0, 0, -19, 0, -19, 0, 0, 0, + // State 100 + 0, 0, 0, -17, -17, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 101 + 0, 0, 0, 0, 0, 0, -10, -10, 0, -10, 0, -10, -10, 0, + // State 102 + 0, 0, 0, 0, 0, 0, 51, 52, 0, 53, 0, 54, 55, 0, + // State 103 + 0, 118, 77, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 104 + 0, -19, -19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 105 + 0, 0, 0, 0, 0, 0, 51, 52, 0, 53, 0, 54, 55, 0, + // State 106 + 0, 120, 77, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 107 + 0, 0, 0, 0, 0, 0, 61, 62, 0, 63, 0, 64, 65, 0, + // State 108 + 0, 0, -4, -4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 109 + 0, 0, -19, -19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 110 + 0, 122, 102, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 111 + 0, 0, 0, -16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 112 + 0, 123, 102, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 113 + 0, 0, -16, 0, 0, 0, 0, 0, -16, 0, -16, 0, 0, 0, + // State 114 + 0, 0, 0, 0, 0, 0, 51, 52, 0, 53, 0, 54, 55, 0, + // State 115 + 0, 0, 0, 0, 0, 0, 0, 0, 126, 0, 0, 0, 0, 0, + // State 116 + 0, 127, 102, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 117 + 0, -16, -16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 118 + 0, 128, 102, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 119 + 0, 0, -16, -16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 120 + 0, 0, -5, -5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 121 + 0, 0, 0, -17, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 122 + 0, 0, -17, 0, 0, 0, 0, 0, -17, 0, -17, 0, 0, 0, + // State 123 + 0, 0, 0, 0, 0, 0, 51, 52, 0, 53, 0, 54, 55, 0, + // State 124 + 0, 130, 77, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 125 + 0, 0, 0, 0, 0, 0, 0, 0, -19, 0, 0, 0, 0, 0, + // State 126 + 0, -17, -17, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 127 + 0, 0, -17, -17, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 128 + 0, 131, 102, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 129 + 0, 0, 0, 0, 0, 0, 0, 0, -16, 0, 0, 0, 0, 0, + // State 130 + 0, 0, 0, 0, 0, 0, 0, 0, -17, 0, 0, 0, 0, 0, + ]; + const __EOF_ACTION: &'static [i32] = &[ + 0, + 0, + 0, + 0, + 0, + -36, + 0, + 0, + 0, + -40, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + -23, + 0, + 0, + 0, + 0, + 0, + -37, + -38, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + -24, + -25, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + -35, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + ]; + const __GOTO: &'static [i32] = &[ + // State 0 + 0, 0, 0, 0, 0, 0, 0, 2, 3, 0, 4, 5, 0, 6, 7, 8, 9, 10, 11, 0, + // State 1 + 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 4, 5, 0, 0, 18, 19, 20, 0, 11, 0, + // State 2 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 3 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 4 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 5 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 6 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 7 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 8 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 9 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 10 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 11 + 0, 0, 0, 0, 0, 0, 0, 0, 26, 0, 27, 5, 0, 0, 0, 0, 28, 0, 11, 0, + // State 12 + 0, 0, 0, 0, 0, 0, 0, 0, 30, 31, 32, 33, 34, 0, 0, 0, 35, 0, 36, 0, + // State 13 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 14 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 15 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 16 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 17 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 18 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 19 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 20 + 0, 0, 0, 0, 0, 44, 0, 0, 45, 46, 47, 48, 0, 0, 0, 0, 49, 0, 50, 0, + // State 21 + 0, 0, 0, 0, 0, 0, 0, 0, 56, 0, 57, 58, 0, 0, 0, 0, 59, 0, 60, 0, + // State 22 + 0, 0, 0, 0, 0, 0, 0, 0, 56, 0, 57, 58, 0, 0, 0, 0, 66, 0, 60, 0, + // State 23 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 24 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 25 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 26 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 27 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 28 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 29 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 30 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 31 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 32 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 33 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 34 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 35 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 36 + 0, 0, 0, 0, 0, 0, 0, 0, 30, 31, 32, 33, 73, 0, 0, 0, 35, 0, 36, 0, + // State 37 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 38 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 39 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 40 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 41 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 42 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 43 + 0, 0, 0, 0, 0, 0, 0, 0, 45, 74, 47, 48, 0, 0, 0, 0, 49, 0, 50, 0, + // State 44 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 45 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 46 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 47 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 48 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 49 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 50 + 0, 0, 0, 0, 0, 0, 0, 0, 30, 31, 32, 33, 78, 0, 0, 0, 35, 0, 36, 0, + // State 51 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 52 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 53 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 54 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 55 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 56 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 57 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 58 + 0, 0, 80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 59 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 60 + 0, 0, 0, 0, 0, 0, 0, 0, 30, 31, 32, 33, 82, 0, 0, 0, 35, 0, 36, 0, + // State 61 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 62 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 63 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 64 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 65 + 0, 0, 83, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 66 + 0, 0, 0, 0, 0, 84, 0, 0, 45, 85, 47, 48, 0, 0, 0, 0, 49, 0, 50, 0, + // State 67 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 68 + 0, 0, 0, 0, 0, 86, 0, 0, 45, 87, 47, 48, 0, 0, 0, 0, 49, 0, 50, 0, + // State 69 + 0, 0, 0, 0, 0, 0, 0, 0, 30, 31, 32, 33, 88, 0, 0, 0, 35, 0, 36, 0, + // State 70 + 0, 0, 0, 0, 0, 0, 0, 0, 89, 90, 91, 92, 0, 0, 0, 0, 93, 0, 94, 0, + // State 71 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 72 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 73 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 74 + 0, 0, 0, 0, 0, 103, 0, 0, 45, 104, 47, 48, 0, 0, 0, 0, 49, 0, 50, 0, + // State 75 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 76 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 77 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 78 + 0, 0, 0, 0, 0, 106, 0, 0, 45, 107, 47, 48, 0, 0, 0, 0, 49, 0, 50, 0, + // State 79 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 80 + 0, 0, 0, 0, 0, 0, 0, 0, 56, 0, 57, 58, 0, 0, 0, 0, 109, 0, 60, 0, + // State 81 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 82 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 83 + 0, 0, 0, 0, 0, 0, 0, 0, 45, 111, 47, 48, 0, 0, 0, 0, 49, 0, 50, 0, + // State 84 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 85 + 0, 0, 0, 0, 0, 0, 0, 0, 45, 113, 47, 48, 0, 0, 0, 0, 49, 0, 50, 0, + // State 86 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 87 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 88 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 89 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 90 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 91 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 92 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 93 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 94 + 0, 0, 0, 0, 0, 0, 0, 0, 30, 31, 32, 33, 116, 0, 0, 0, 35, 0, 36, 0, + // State 95 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 96 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 97 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 98 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 99 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 100 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 101 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 102 + 0, 0, 0, 0, 0, 0, 0, 0, 45, 117, 47, 48, 0, 0, 0, 0, 49, 0, 50, 0, + // State 103 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 104 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 105 + 0, 0, 0, 0, 0, 0, 0, 0, 45, 119, 47, 48, 0, 0, 0, 0, 49, 0, 50, 0, + // State 106 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 107 + 0, 0, 0, 0, 0, 0, 0, 0, 56, 0, 57, 58, 0, 0, 0, 0, 121, 0, 60, 0, + // State 108 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 109 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 110 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 111 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 112 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 113 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 114 + 0, 0, 0, 0, 0, 124, 0, 0, 45, 125, 47, 48, 0, 0, 0, 0, 49, 0, 50, 0, + // State 115 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 116 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 117 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 118 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 119 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 120 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 121 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 122 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 123 + 0, 0, 0, 0, 0, 0, 0, 0, 45, 129, 47, 48, 0, 0, 0, 0, 49, 0, 50, 0, + // State 124 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 125 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 126 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 127 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 128 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 129 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 130 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + ]; + fn __expected_tokens(__state: usize) -> Vec<::std::string::String> { + const __TERMINAL: &'static [&'static str] = &[ + r###""(""###, + r###"")""###, + r###"",""###, + r###"".""###, + r###"":-""###, + r###""?-""###, + r###""[""###, + r###""[]""###, + r###""]""###, + r###""_""###, + r###""|""###, + r###"r#"[A-Z][a-z0-9_]*"#"###, + r###"r#"[a-z][a-z0-9_]*"#"###, + ]; + __ACTION[(__state * 14)..].iter().zip(__TERMINAL).filter_map(|(&state, terminal)| { + if state == 0 { + None + } else { + Some(terminal.to_string()) + } + }).collect() + } + 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![]; + let mut __integer; + let mut __lookahead; + let mut __last_location = Default::default(); + '__shift: loop { + __lookahead = match __tokens.next() { + Some(Ok(v)) => v, + None => break '__shift, + Some(Err(e)) => return Err(e), + }; + __last_location = __lookahead.2.clone(); + __integer = match __lookahead.1 { + (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, + (7, _) if true => 7, + (8, _) if true => 8, + (9, _) if true => 9, + (10, _) if true => 10, + (11, _) if true => 11, + (12, _) if true => 12, + _ => { + let __state = *__states.last().unwrap() as usize; + let __error = __lalrpop_util::ParseError::UnrecognizedToken { + token: Some(__lookahead), + expected: __expected_tokens(__state), + }; + return Err(__error); + } + }; + '__inner: loop { + let __state = *__states.last().unwrap() as usize; + let __action = __ACTION[__state * 14 + __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_3a_2d_22(__tok0), + _ => unreachable!(), + }, + 5 => match __lookahead.1 { + (5, __tok0) => __Symbol::Term_22_3f_2d_22(__tok0), + _ => unreachable!(), + }, + 6 => match __lookahead.1 { + (6, __tok0) => __Symbol::Term_22_5b_22(__tok0), + _ => unreachable!(), + }, + 7 => match __lookahead.1 { + (7, __tok0) => __Symbol::Term_22_5b_5d_22(__tok0), + _ => unreachable!(), + }, + 8 => match __lookahead.1 { + (8, __tok0) => __Symbol::Term_22_5d_22(__tok0), + _ => unreachable!(), + }, + 9 => match __lookahead.1 { + (9, __tok0) => __Symbol::Term_22___22(__tok0), + _ => unreachable!(), + }, + 10 => match __lookahead.1 { + (10, __tok0) => __Symbol::Term_22_7c_22(__tok0), + _ => unreachable!(), + }, + 11 => match __lookahead.1 { + (11, __tok0) => __Symbol::Termr_23_22_5bA_2dZ_5d_5ba_2dz0_2d9___5d_2a_22_23(__tok0), + _ => unreachable!(), + }, + 12 => match __lookahead.1 { + (12, __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, ::std::marker::PhantomData::<()>) { + return r; + } + } else { + let __state = *__states.last().unwrap() as usize; + let __error = __lalrpop_util::ParseError::UnrecognizedToken { + token: Some(__lookahead), + expected: __expected_tokens(__state), + }; + return Err(__error) + } + } + } + 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, ::std::marker::PhantomData::<()>) { + return r; + } + } else { + let __state = *__states.last().unwrap() as usize; + let __error = __lalrpop_util::ParseError::UnrecognizedToken { + token: None, + expected: __expected_tokens(__state), + }; + return Err(__error); + } + } + } + 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)>, + _: ::std::marker::PhantomData<()>, + ) -> Option>> + { + let __nonterminal = match -__action { + 1 => { + // ("," ) = ",", Term => ActionFn(26); + let __sym1 = __pop_NtTerm(__symbols); + let __sym0 = __pop_Term_22_2c_22(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym1.2.clone(); + let __nt = super::__action26::<>(input, __sym0, __sym1); + let __states_len = __states.len(); + __states.truncate(__states_len - 2); + __symbols.push((__start, __Symbol::Nt_28_22_2c_22_20_3cTerm_3e_29(__nt), __end)); + 0 + } + 2 => { + // ("," )* = => ActionFn(24); + 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::__action24::<>(input, &__start, &__end); + let __states_len = __states.len(); + __states.truncate(__states_len - 0); + __symbols.push((__start, __Symbol::Nt_28_22_2c_22_20_3cTerm_3e_29_2a(__nt), __end)); + 1 + } + 3 => { + // ("," )* = ("," )+ => ActionFn(25); + let __sym0 = __pop_Nt_28_22_2c_22_20_3cTerm_3e_29_2b(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action25::<>(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::Nt_28_22_2c_22_20_3cTerm_3e_29_2a(__nt), __end)); + 1 + } + 4 => { + // ("," )+ = ",", Term => ActionFn(37); + let __sym1 = __pop_NtTerm(__symbols); + let __sym0 = __pop_Term_22_2c_22(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym1.2.clone(); + let __nt = super::__action37::<>(input, __sym0, __sym1); + let __states_len = __states.len(); + __states.truncate(__states_len - 2); + __symbols.push((__start, __Symbol::Nt_28_22_2c_22_20_3cTerm_3e_29_2b(__nt), __end)); + 2 + } + 5 => { + // ("," )+ = ("," )+, ",", Term => ActionFn(38); + let __sym2 = __pop_NtTerm(__symbols); + let __sym1 = __pop_Term_22_2c_22(__symbols); + let __sym0 = __pop_Nt_28_22_2c_22_20_3cTerm_3e_29_2b(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym2.2.clone(); + let __nt = super::__action38::<>(input, __sym0, __sym1, __sym2); + let __states_len = __states.len(); + __states.truncate(__states_len - 3); + __symbols.push((__start, __Symbol::Nt_28_22_2c_22_20_3cTerm_3e_29_2b(__nt), __end)); + 2 + } + 6 => { + // ( ",") = BoxedTerm, "," => ActionFn(32); + 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::__action32::<>(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)); + 3 + } + 7 => { + // ( ",")* = => ActionFn(30); + 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::__action30::<>(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)); + 4 + } + 8 => { + // ( ",")* = ( ",")+ => ActionFn(31); + 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::__action31::<>(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)); + 4 + } + 9 => { + // ( ",")+ = BoxedTerm, "," => ActionFn(43); + 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::__action43::<>(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)); + 5 + } + 10 => { + // ( ",")+ = ( ",")+, BoxedTerm, "," => ActionFn(44); + 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::__action44::<>(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)); + 5 + } + 11 => { + // () = PredicateClause => ActionFn(29); + let __sym0 = __pop_NtPredicateClause(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action29::<>(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::Nt_28_3cPredicateClause_3e_29(__nt), __end)); + 6 + } + 12 => { + // ()+ = PredicateClause => ActionFn(47); + let __sym0 = __pop_NtPredicateClause(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action47::<>(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::Nt_28_3cPredicateClause_3e_29_2b(__nt), __end)); + 7 + } + 13 => { + // ()+ = ()+, PredicateClause => ActionFn(48); + let __sym1 = __pop_NtPredicateClause(__symbols); + let __sym0 = __pop_Nt_28_3cPredicateClause_3e_29_2b(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym1.2.clone(); + let __nt = super::__action48::<>(input, __sym0, __sym1); + let __states_len = __states.len(); + __states.truncate(__states_len - 2); + __symbols.push((__start, __Symbol::Nt_28_3cPredicateClause_3e_29_2b(__nt), __end)); + 7 + } + 14 => { + // Atom = r#"[a-z][a-z0-9_]*"# => ActionFn(5); + 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::__action5::<>(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtAtom(__nt), __end)); + 8 + } + 15 => { + // BoxedTerm = Term => ActionFn(6); + let __sym0 = __pop_NtTerm(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action6::<>(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtBoxedTerm(__nt), __end)); + 9 + } + 16 => { + // Clause = Atom, "(", BoxedTerm, ")" => ActionFn(45); + 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::__action45::<>(input, __sym0, __sym1, __sym2, __sym3); + let __states_len = __states.len(); + __states.truncate(__states_len - 4); + __symbols.push((__start, __Symbol::NtClause(__nt), __end)); + 10 + } + 17 => { + // Clause = Atom, "(", ( ",")+, BoxedTerm, ")" => ActionFn(46); + 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::__action46::<>(input, __sym0, __sym1, __sym2, __sym3, __sym4); + let __states_len = __states.len(); + __states.truncate(__states_len - 5); + __symbols.push((__start, __Symbol::NtClause(__nt), __end)); + 10 + } + 18 => { + // List = "[]" => ActionFn(8); + let __sym0 = __pop_Term_22_5b_5d_22(__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::NtList(__nt), __end)); + 11 + } + 19 => { + // List = "[", ListInternals, "]" => ActionFn(9); + let __sym2 = __pop_Term_22_5d_22(__symbols); + let __sym1 = __pop_NtListInternals(__symbols); + let __sym0 = __pop_Term_22_5b_22(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym2.2.clone(); + let __nt = super::__action9::<>(input, __sym0, __sym1, __sym2); + let __states_len = __states.len(); + __states.truncate(__states_len - 3); + __symbols.push((__start, __Symbol::NtList(__nt), __end)); + 11 + } + 20 => { + // ListInternals = BoxedTerm => ActionFn(10); + let __sym0 = __pop_NtBoxedTerm(__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::NtListInternals(__nt), __end)); + 12 + } + 21 => { + // ListInternals = BoxedTerm, ",", ListInternals => ActionFn(11); + let __sym2 = __pop_NtListInternals(__symbols); + let __sym1 = __pop_Term_22_2c_22(__symbols); + let __sym0 = __pop_NtBoxedTerm(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym2.2.clone(); + let __nt = super::__action11::<>(input, __sym0, __sym1, __sym2); + let __states_len = __states.len(); + __states.truncate(__states_len - 3); + __symbols.push((__start, __Symbol::NtListInternals(__nt), __end)); + 12 + } + 22 => { + // ListInternals = BoxedTerm, "|", BoxedTerm => ActionFn(12); + let __sym2 = __pop_NtBoxedTerm(__symbols); + let __sym1 = __pop_Term_22_7c_22(__symbols); + let __sym0 = __pop_NtBoxedTerm(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym2.2.clone(); + let __nt = super::__action12::<>(input, __sym0, __sym1, __sym2); + let __states_len = __states.len(); + __states.truncate(__states_len - 3); + __symbols.push((__start, __Symbol::NtListInternals(__nt), __end)); + 12 + } + 23 => { + // Predicate = ()+, PredicateClause => ActionFn(13); + let __sym1 = __pop_NtPredicateClause(__symbols); + let __sym0 = __pop_Nt_28_3cPredicateClause_3e_29_2b(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym1.2.clone(); + let __nt = super::__action13::<>(input, __sym0, __sym1); + let __states_len = __states.len(); + __states.truncate(__states_len - 2); + __symbols.push((__start, __Symbol::NtPredicate(__nt), __end)); + 13 + } + 24 => { + // PredicateClause = Rule, "." => ActionFn(14); + let __sym1 = __pop_Term_22_2e_22(__symbols); + let __sym0 = __pop_NtRule(__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::NtPredicateClause(__nt), __end)); + 14 + } + 25 => { + // PredicateClause = Term, "." => ActionFn(15); + 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::__action15::<>(input, __sym0, __sym1); + let __states_len = __states.len(); + __states.truncate(__states_len - 2); + __symbols.push((__start, __Symbol::NtPredicateClause(__nt), __end)); + 14 + } + 26 => { + // Rule = Clause, ":-", Term => ActionFn(39); + let __sym2 = __pop_NtTerm(__symbols); + let __sym1 = __pop_Term_22_3a_2d_22(__symbols); + let __sym0 = __pop_NtClause(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym2.2.clone(); + let __nt = super::__action39::<>(input, __sym0, __sym1, __sym2); + let __states_len = __states.len(); + __states.truncate(__states_len - 3); + __symbols.push((__start, __Symbol::NtRule(__nt), __end)); + 15 + } + 27 => { + // Rule = Clause, ":-", Term, ("," )+ => ActionFn(40); + let __sym3 = __pop_Nt_28_22_2c_22_20_3cTerm_3e_29_2b(__symbols); + let __sym2 = __pop_NtTerm(__symbols); + let __sym1 = __pop_Term_22_3a_2d_22(__symbols); + let __sym0 = __pop_NtClause(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym3.2.clone(); + let __nt = super::__action40::<>(input, __sym0, __sym1, __sym2, __sym3); + let __states_len = __states.len(); + __states.truncate(__states_len - 4); + __symbols.push((__start, __Symbol::NtRule(__nt), __end)); + 15 + } + 28 => { + // Rule = Atom, ":-", Term => ActionFn(41); + let __sym2 = __pop_NtTerm(__symbols); + let __sym1 = __pop_Term_22_3a_2d_22(__symbols); + let __sym0 = __pop_NtAtom(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym2.2.clone(); + let __nt = super::__action41::<>(input, __sym0, __sym1, __sym2); + let __states_len = __states.len(); + __states.truncate(__states_len - 3); + __symbols.push((__start, __Symbol::NtRule(__nt), __end)); + 15 + } + 29 => { + // Rule = Atom, ":-", Term, ("," )+ => ActionFn(42); + let __sym3 = __pop_Nt_28_22_2c_22_20_3cTerm_3e_29_2b(__symbols); + let __sym2 = __pop_NtTerm(__symbols); + let __sym1 = __pop_Term_22_3a_2d_22(__symbols); + let __sym0 = __pop_NtAtom(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym3.2.clone(); + let __nt = super::__action42::<>(input, __sym0, __sym1, __sym2, __sym3); + let __states_len = __states.len(); + __states.truncate(__states_len - 4); + __symbols.push((__start, __Symbol::NtRule(__nt), __end)); + 15 + } + 30 => { + // Term = Atom => ActionFn(18); + let __sym0 = __pop_NtAtom(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action18::<>(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtTerm(__nt), __end)); + 16 + } + 31 => { + // Term = Clause => ActionFn(19); + let __sym0 = __pop_NtClause(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action19::<>(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtTerm(__nt), __end)); + 16 + } + 32 => { + // Term = List => ActionFn(20); + let __sym0 = __pop_NtList(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action20::<>(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtTerm(__nt), __end)); + 16 + } + 33 => { + // Term = Var => ActionFn(21); + let __sym0 = __pop_NtVar(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action21::<>(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtTerm(__nt), __end)); + 16 + } + 34 => { + // Term = "_" => ActionFn(22); + let __sym0 = __pop_Term_22___22(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action22::<>(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtTerm(__nt), __end)); + 16 + } + 35 => { + // 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)); + 17 + } + 36 => { + // TopLevel = Predicate => ActionFn(2); + let __sym0 = __pop_NtPredicate(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action2::<>(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtTopLevel(__nt), __end)); + 17 + } + 37 => { + // TopLevel = Rule, "." => ActionFn(3); + let __sym1 = __pop_Term_22_2e_22(__symbols); + let __sym0 = __pop_NtRule(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym1.2.clone(); + let __nt = super::__action3::<>(input, __sym0, __sym1); + let __states_len = __states.len(); + __states.truncate(__states_len - 2); + __symbols.push((__start, __Symbol::NtTopLevel(__nt), __end)); + 17 + } + 38 => { + // TopLevel = Term, "." => ActionFn(4); + 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::__action4::<>(input, __sym0, __sym1); + let __states_len = __states.len(); + __states.truncate(__states_len - 2); + __symbols.push((__start, __Symbol::NtTopLevel(__nt), __end)); + 17 + } + 39 => { + // Var = r#"[A-Z][a-z0-9_]*"# => ActionFn(23); + 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::__action23::<>(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtVar(__nt), __end)); + 18 + } + 40 => { + // __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 * 20 + __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_3a_2d_22< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Term_22_3a_2d_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_Term_22_5b_22< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Term_22_5b_22(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Term_22_5b_5d_22< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Term_22_5b_5d_22(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Term_22_5d_22< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Term_22_5d_22(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Term_22___22< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Term_22___22(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Term_22_7c_22< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Term_22_7c_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_Termerror< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, __lalrpop_util::ErrorRecovery, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Termerror(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Nt_28_22_2c_22_20_3cTerm_3e_29< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, Term, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Nt_28_22_2c_22_20_3cTerm_3e_29(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Nt_28_22_2c_22_20_3cTerm_3e_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_22_2c_22_20_3cTerm_3e_29_2a(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Nt_28_22_2c_22_20_3cTerm_3e_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_22_2c_22_20_3cTerm_3e_29_2b(__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_Nt_28_3cPredicateClause_3e_29< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, PredicateClause, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Nt_28_3cPredicateClause_3e_29(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Nt_28_3cPredicateClause_3e_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_3cPredicateClause_3e_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_NtClause< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, Term, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::NtClause(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_NtList< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, Term, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::NtList(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_NtListInternals< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, Term, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::NtListInternals(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_NtPredicate< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, Vec, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::NtPredicate(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_NtPredicateClause< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, PredicateClause, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::NtPredicateClause(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_NtRule< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, Rule, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::NtRule(__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; + } + 58 => /* ':' */ { + __current_state = 5; + continue; + } + 63 => /* '?' */ { + __current_state = 6; + continue; + } + 65 ... 90 => { + __current_match = Some((11, __index + __ch.len_utf8())); + __current_state = 7; + continue; + } + 91 => /* '[' */ { + __current_match = Some((6, __index + 1)); + __current_state = 8; + continue; + } + 93 => /* ']' */ { + __current_match = Some((8, __index + 1)); + __current_state = 9; + continue; + } + 95 => /* '_' */ { + __current_match = Some((9, __index + 1)); + __current_state = 10; + continue; + } + 97 ... 122 => { + __current_match = Some((12, __index + __ch.len_utf8())); + __current_state = 11; + continue; + } + 124 => /* '|' */ { + __current_match = Some((10, __index + 1)); + __current_state = 12; + 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 = 14; + continue; + } + _ => { + return __current_match; + } + } + } + 6 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 45 => /* '-' */ { + __current_match = Some((5, __index + 1)); + __current_state = 15; + 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((11, __index + __ch.len_utf8())); + __current_state = 16; + continue; + } + 95 => /* '_' */ { + __current_match = Some((11, __index + 1)); + __current_state = 16; + continue; + } + 97 ... 122 => { + __current_match = Some((11, __index + __ch.len_utf8())); + __current_state = 16; + continue; + } + _ => { + return __current_match; + } + } + } + 8 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 93 => /* ']' */ { + __current_match = Some((7, __index + 1)); + __current_state = 17; + continue; + } + _ => { + 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 { + _ => { + 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((12, __index + __ch.len_utf8())); + __current_state = 18; + continue; + } + 95 => /* '_' */ { + __current_match = Some((12, __index + 1)); + __current_state = 18; + continue; + } + 97 ... 122 => { + __current_match = Some((12, __index + __ch.len_utf8())); + __current_state = 18; + continue; + } + _ => { + return __current_match; + } + } + } + 12 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + _ => { + return __current_match; + } + } + } + 13 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + _ => { + return __current_match; + } + } + } + 14 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + _ => { + return __current_match; + } + } + } + 15 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + _ => { + return __current_match; + } + } + } + 16 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 48 ... 57 => { + __current_match = Some((11, __index + __ch.len_utf8())); + __current_state = 16; + continue; + } + 95 => /* '_' */ { + __current_match = Some((11, __index + 1)); + __current_state = 16; + continue; + } + 97 ... 122 => { + __current_match = Some((11, __index + __ch.len_utf8())); + __current_state = 16; + continue; + } + _ => { + return __current_match; + } + } + } + 17 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + _ => { + return __current_match; + } + } + } + 18 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 48 ... 57 => { + __current_match = Some((12, __index + __ch.len_utf8())); + __current_state = 18; + continue; + } + 95 => /* '_' */ { + __current_match = Some((12, __index + 1)); + __current_state = 18; + continue; + } + 97 ... 122 => { + __current_match = Some((12, __index + __ch.len_utf8())); + __current_state = 18; + 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, + (_, __0, _): (usize, Vec, usize), +) -> TopLevel +{ + TopLevel::Predicate(__0) +} + +#[allow(unused_variables)] +pub fn __action3< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Rule, usize), + (_, _, _): (usize, &'input str, usize), +) -> TopLevel +{ + TopLevel::Rule(__0) +} + +#[allow(unused_variables)] +pub fn __action4< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Term, usize), + (_, _, _): (usize, &'input str, usize), +) -> TopLevel +{ + TopLevel::Fact(__0) +} + +#[allow(unused_variables)] +pub fn __action5< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, &'input str, usize), +) -> Atom +{ + __0.trim().to_string() +} + +#[allow(unused_variables)] +pub fn __action6< + 'input, +>( + input: &'input str, + (_, t, _): (usize, Term, usize), +) -> Box +{ + Box::new(t) +} + +#[allow(unused_variables)] +pub fn __action7< + '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::default(), a, ts) + } +} + +#[allow(unused_variables)] +pub fn __action8< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, &'input str, usize), +) -> Term +{ + Term::Constant(Cell::default(), Constant::EmptyList) +} + +#[allow(unused_variables)] +pub fn __action9< + 'input, +>( + input: &'input str, + (_, _, _): (usize, &'input str, usize), + (_, __0, _): (usize, Term, usize), + (_, _, _): (usize, &'input str, usize), +) -> Term +{ + __0 +} + +#[allow(unused_variables)] +pub fn __action10< + 'input, +>( + input: &'input str, + (_, t, _): (usize, Box, usize), +) -> Term +{ + Term::Cons(Cell::default(), + t, + Box::new(Term::Constant(Cell::default(), + Constant::EmptyList))) +} + +#[allow(unused_variables)] +pub fn __action11< + 'input, +>( + input: &'input str, + (_, t, _): (usize, Box, usize), + (_, _, _): (usize, &'input str, usize), + (_, li, _): (usize, Term, usize), +) -> Term +{ + Term::Cons(Cell::default(), + t, + Box::new(li)) +} + +#[allow(unused_variables)] +pub fn __action12< + 'input, +>( + input: &'input str, + (_, t1, _): (usize, Box, usize), + (_, _, _): (usize, &'input str, usize), + (_, t2, _): (usize, Box, usize), +) -> Term +{ + Term::Cons(Cell::default(), t1, t2) +} + +#[allow(unused_variables)] +pub fn __action13< + 'input, +>( + input: &'input str, + (_, pcs, _): (usize, ::std::vec::Vec, usize), + (_, pc, _): (usize, PredicateClause, usize), +) -> Vec +{ + { + let mut pcs = pcs; + pcs.push(pc); + pcs + } +} + +#[allow(unused_variables)] +pub fn __action14< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Rule, usize), + (_, _, _): (usize, &'input str, usize), +) -> PredicateClause +{ + PredicateClause::Rule(__0) +} + +#[allow(unused_variables)] +pub fn __action15< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Term, usize), + (_, _, _): (usize, &'input str, usize), +) -> PredicateClause +{ + PredicateClause::Fact(__0) +} + +#[allow(unused_variables)] +pub fn __action16< + 'input, +>( + input: &'input str, + (_, c, _): (usize, Term, usize), + (_, _, _): (usize, &'input str, usize), + (_, h, _): (usize, Term, usize), + (_, cs, _): (usize, ::std::vec::Vec, usize), +) -> Rule +{ + Rule { head: (c, h), clauses: cs } +} + +#[allow(unused_variables)] +pub fn __action17< + 'input, +>( + input: &'input str, + (_, a, _): (usize, Atom, usize), + (_, _, _): (usize, &'input str, usize), + (_, h, _): (usize, Term, usize), + (_, cs, _): (usize, ::std::vec::Vec, usize), +) -> Rule +{ + Rule { head: (Term::Constant(Cell::default(), Constant::Atom(a)), h), + clauses: cs } +} + +#[allow(unused_variables)] +pub fn __action18< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Atom, usize), +) -> Term +{ + Term::Constant(Cell::default(), Constant::Atom(__0)) +} + +#[allow(unused_variables)] +pub fn __action19< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Term, usize), +) -> Term +{ + __0 +} + +#[allow(unused_variables)] +pub fn __action20< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Term, usize), +) -> Term +{ + __0 +} + +#[allow(unused_variables)] +pub fn __action21< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Var, usize), +) -> Term +{ + Term::Var(Cell::default(), __0) +} + +#[allow(unused_variables)] +pub fn __action22< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, &'input str, usize), +) -> Term +{ + Term::AnonVar +} + +#[allow(unused_variables)] +pub fn __action23< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, &'input str, usize), +) -> Var +{ + __0.trim().to_string() +} + +#[allow(unused_variables)] +pub fn __action24< + 'input, +>( + input: &'input str, + __lookbehind: &usize, + __lookahead: &usize, +) -> ::std::vec::Vec +{ + vec![] +} + +#[allow(unused_variables)] +pub fn __action25< + 'input, +>( + input: &'input str, + (_, v, _): (usize, ::std::vec::Vec, usize), +) -> ::std::vec::Vec +{ + v +} + +#[allow(unused_variables)] +pub fn __action26< + 'input, +>( + input: &'input str, + (_, _, _): (usize, &'input str, usize), + (_, __0, _): (usize, Term, usize), +) -> Term +{ + (__0) +} + +#[allow(unused_variables)] +pub fn __action27< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, PredicateClause, usize), +) -> ::std::vec::Vec +{ + vec![__0] +} + +#[allow(unused_variables)] +pub fn __action28< + 'input, +>( + input: &'input str, + (_, v, _): (usize, ::std::vec::Vec, usize), + (_, e, _): (usize, PredicateClause, usize), +) -> ::std::vec::Vec +{ + { let mut v = v; v.push(e); v } +} + +#[allow(unused_variables)] +pub fn __action29< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, PredicateClause, usize), +) -> PredicateClause +{ + (__0) +} + +#[allow(unused_variables)] +pub fn __action30< + 'input, +>( + input: &'input str, + __lookbehind: &usize, + __lookahead: &usize, +) -> ::std::vec::Vec> +{ + vec![] +} + +#[allow(unused_variables)] +pub fn __action31< + 'input, +>( + input: &'input str, + (_, v, _): (usize, ::std::vec::Vec>, usize), +) -> ::std::vec::Vec> +{ + v +} + +#[allow(unused_variables)] +pub fn __action32< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Box, usize), + (_, _, _): (usize, &'input str, usize), +) -> Box +{ + (__0) +} + +#[allow(unused_variables)] +pub fn __action33< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Box, usize), +) -> ::std::vec::Vec> +{ + vec![__0] +} + +#[allow(unused_variables)] +pub fn __action34< + '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 __action35< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Term, usize), +) -> ::std::vec::Vec +{ + vec![__0] +} + +#[allow(unused_variables)] +pub fn __action36< + 'input, +>( + input: &'input str, + (_, v, _): (usize, ::std::vec::Vec, usize), + (_, e, _): (usize, Term, usize), +) -> ::std::vec::Vec +{ + { let mut v = v; v.push(e); v } +} + +#[allow(unused_variables)] +pub fn __action37< + 'input, +>( + input: &'input str, + __0: (usize, &'input str, usize), + __1: (usize, Term, usize), +) -> ::std::vec::Vec +{ + let __start0 = __0.0.clone(); + let __end0 = __1.2.clone(); + let __temp0 = __action26( + input, + __0, + __1, + ); + let __temp0 = (__start0, __temp0, __end0); + __action35( + input, + __temp0, + ) +} + +#[allow(unused_variables)] +pub fn __action38< + 'input, +>( + input: &'input str, + __0: (usize, ::std::vec::Vec, usize), + __1: (usize, &'input str, usize), + __2: (usize, Term, usize), +) -> ::std::vec::Vec +{ + let __start0 = __1.0.clone(); + let __end0 = __2.2.clone(); + let __temp0 = __action26( + input, + __1, + __2, + ); + let __temp0 = (__start0, __temp0, __end0); + __action36( + input, + __0, + __temp0, + ) +} + +#[allow(unused_variables)] +pub fn __action39< + 'input, +>( + input: &'input str, + __0: (usize, Term, usize), + __1: (usize, &'input str, usize), + __2: (usize, Term, usize), +) -> Rule +{ + let __start0 = __2.2.clone(); + let __end0 = __2.2.clone(); + let __temp0 = __action24( + input, + &__start0, + &__end0, + ); + let __temp0 = (__start0, __temp0, __end0); + __action16( + input, + __0, + __1, + __2, + __temp0, + ) +} + +#[allow(unused_variables)] +pub fn __action40< + 'input, +>( + input: &'input str, + __0: (usize, Term, usize), + __1: (usize, &'input str, usize), + __2: (usize, Term, usize), + __3: (usize, ::std::vec::Vec, usize), +) -> Rule +{ + let __start0 = __3.0.clone(); + let __end0 = __3.2.clone(); + let __temp0 = __action25( + input, + __3, + ); + let __temp0 = (__start0, __temp0, __end0); + __action16( + input, + __0, + __1, + __2, + __temp0, + ) +} + +#[allow(unused_variables)] +pub fn __action41< + 'input, +>( + input: &'input str, + __0: (usize, Atom, usize), + __1: (usize, &'input str, usize), + __2: (usize, Term, usize), +) -> Rule +{ + let __start0 = __2.2.clone(); + let __end0 = __2.2.clone(); + let __temp0 = __action24( + input, + &__start0, + &__end0, + ); + let __temp0 = (__start0, __temp0, __end0); + __action17( + input, + __0, + __1, + __2, + __temp0, + ) +} + +#[allow(unused_variables)] +pub fn __action42< + 'input, +>( + input: &'input str, + __0: (usize, Atom, usize), + __1: (usize, &'input str, usize), + __2: (usize, Term, usize), + __3: (usize, ::std::vec::Vec, usize), +) -> Rule +{ + let __start0 = __3.0.clone(); + let __end0 = __3.2.clone(); + let __temp0 = __action25( + input, + __3, + ); + let __temp0 = (__start0, __temp0, __end0); + __action17( + input, + __0, + __1, + __2, + __temp0, + ) +} + +#[allow(unused_variables)] +pub fn __action43< + '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 = __action32( + input, + __0, + __1, + ); + let __temp0 = (__start0, __temp0, __end0); + __action33( + input, + __temp0, + ) +} + +#[allow(unused_variables)] +pub fn __action44< + '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 = __action32( + input, + __1, + __2, + ); + let __temp0 = (__start0, __temp0, __end0); + __action34( + input, + __0, + __temp0, + ) +} + +#[allow(unused_variables)] +pub fn __action45< + '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 = __action30( + input, + &__start0, + &__end0, + ); + let __temp0 = (__start0, __temp0, __end0); + __action7( + input, + __0, + __1, + __temp0, + __2, + __3, + ) +} + +#[allow(unused_variables)] +pub fn __action46< + '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 = __action31( + input, + __2, + ); + let __temp0 = (__start0, __temp0, __end0); + __action7( + input, + __0, + __1, + __temp0, + __3, + __4, + ) +} + +#[allow(unused_variables)] +pub fn __action47< + 'input, +>( + input: &'input str, + __0: (usize, PredicateClause, usize), +) -> ::std::vec::Vec +{ + let __start0 = __0.0.clone(); + let __end0 = __0.2.clone(); + let __temp0 = __action29( + input, + __0, + ); + let __temp0 = (__start0, __temp0, __end0); + __action27( + input, + __temp0, + ) +} + +#[allow(unused_variables)] +pub fn __action48< + 'input, +>( + input: &'input str, + __0: (usize, ::std::vec::Vec, usize), + __1: (usize, PredicateClause, usize), +) -> ::std::vec::Vec +{ + let __start0 = __1.0.clone(); + let __end0 = __1.2.clone(); + let __temp0 = __action29( + input, + __1, + ); + let __temp0 = (__start0, __temp0, __end0); + __action28( + input, + __0, + __temp0, + ) +} + +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 + } +} -- 2.54.0