From 1b5f8a1db21bfe01eec3bc6e55fd2a806d8268b0 Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Tue, 21 Feb 2017 00:31:04 -0700 Subject: [PATCH] transition to l2 --- Cargo.lock | 32 +- Cargo.toml | 6 +- README.md | 73 +- src/l2/ast.rs | 200 +++++ src/l2/codegen.rs | 447 ++++++++++ src/l2/iterators.rs | 175 ++++ src/l2/l2_parser.lalrpop | 42 + src/l2/l2_parser.rs | 1767 ++++++++++++++++++++++++++++++++++++++ src/l2/machine.rs | 400 +++++++++ src/l2/mod.rs | 6 + src/l2/stack.rs | 60 ++ src/main.rs | 54 +- 12 files changed, 3187 insertions(+), 75 deletions(-) create mode 100644 src/l2/ast.rs create mode 100644 src/l2/codegen.rs create mode 100644 src/l2/iterators.rs create mode 100644 src/l2/l2_parser.lalrpop create mode 100644 src/l2/l2_parser.rs create mode 100644 src/l2/machine.rs create mode 100644 src/l2/mod.rs create mode 100644 src/l2/stack.rs diff --git a/Cargo.lock b/Cargo.lock index f1c5f02a..b7dce60d 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -1,9 +1,9 @@ [root] name = "rusty-wam" -version = "0.1.0" +version = "0.3.0" dependencies = [ - "lalrpop 0.12.0 (registry+https://github.com/rust-lang/crates.io-index)", - "lalrpop-util 0.12.0 (registry+https://github.com/rust-lang/crates.io-index)", + "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)", ] [[package]] @@ -79,7 +79,7 @@ dependencies = [ [[package]] name = "lalrpop" -version = "0.12.0" +version = "0.12.5" source = "registry+https://github.com/rust-lang/crates.io-index" dependencies = [ "atty 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)", @@ -88,9 +88,9 @@ dependencies = [ "diff 0.1.9 (registry+https://github.com/rust-lang/crates.io-index)", "docopt 0.6.83 (registry+https://github.com/rust-lang/crates.io-index)", "itertools 0.3.25 (registry+https://github.com/rust-lang/crates.io-index)", - "lalrpop-intern 0.12.0 (registry+https://github.com/rust-lang/crates.io-index)", - "lalrpop-snap 0.12.0 (registry+https://github.com/rust-lang/crates.io-index)", - "lalrpop-util 0.12.0 (registry+https://github.com/rust-lang/crates.io-index)", + "lalrpop-intern 0.12.5 (registry+https://github.com/rust-lang/crates.io-index)", + "lalrpop-snap 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)", "petgraph 0.1.18 (registry+https://github.com/rust-lang/crates.io-index)", "regex 0.1.75 (registry+https://github.com/rust-lang/crates.io-index)", "regex-syntax 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)", @@ -101,12 +101,12 @@ dependencies = [ [[package]] name = "lalrpop-intern" -version = "0.12.0" +version = "0.12.5" source = "registry+https://github.com/rust-lang/crates.io-index" [[package]] name = "lalrpop-snap" -version = "0.12.0" +version = "0.12.5" source = "registry+https://github.com/rust-lang/crates.io-index" dependencies = [ "atty 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)", @@ -115,8 +115,8 @@ dependencies = [ "diff 0.1.9 (registry+https://github.com/rust-lang/crates.io-index)", "docopt 0.6.83 (registry+https://github.com/rust-lang/crates.io-index)", "itertools 0.3.25 (registry+https://github.com/rust-lang/crates.io-index)", - "lalrpop-intern 0.12.0 (registry+https://github.com/rust-lang/crates.io-index)", - "lalrpop-util 0.12.0 (registry+https://github.com/rust-lang/crates.io-index)", + "lalrpop-intern 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)", "petgraph 0.1.18 (registry+https://github.com/rust-lang/crates.io-index)", "regex 0.1.75 (registry+https://github.com/rust-lang/crates.io-index)", "regex-syntax 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)", @@ -127,7 +127,7 @@ dependencies = [ [[package]] name = "lalrpop-util" -version = "0.12.0" +version = "0.12.5" source = "registry+https://github.com/rust-lang/crates.io-index" [[package]] @@ -245,10 +245,10 @@ source = "registry+https://github.com/rust-lang/crates.io-index" "checksum fixedbitset 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "c59882225c22dfcd2db6f0fce45dabe334e64ffa5efacb785b7ffb5af690cc6f" "checksum itertools 0.3.25 (registry+https://github.com/rust-lang/crates.io-index)" = "16b73f1c685cfd8ff8d75698ed87e6188cd09944b30c0863d45c2c3699d1da0c" "checksum kernel32-sys 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "7507624b29483431c0ba2d82aece8ca6cdba9382bff4ddd0f7490560c056098d" -"checksum lalrpop 0.12.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ff7b1575ca8cc268def5a19fd73cea4849a56d2ade819bfe13b8eb78f8a85191" -"checksum lalrpop-intern 0.12.0 (registry+https://github.com/rust-lang/crates.io-index)" = "8acc7d538f0d74e035719d2b46dd34abf919e21f69d9eacd3d33d8bb91b4be91" -"checksum lalrpop-snap 0.12.0 (registry+https://github.com/rust-lang/crates.io-index)" = "40d7ede4572f90583b0bb05af8aec2dad705f865fcecf479b8ebe959b46f8435" -"checksum lalrpop-util 0.12.0 (registry+https://github.com/rust-lang/crates.io-index)" = "b2af45efc901171e23793f5edb55294dfab4fe1dc70d9df9450cb8f233ffea1f" +"checksum lalrpop 0.12.5 (registry+https://github.com/rust-lang/crates.io-index)" = "a50b5cdf6b58f1753c86ebcc4d0852ff30478133fb370a27dbf303cbd5621fdc" +"checksum lalrpop-intern 0.12.5 (registry+https://github.com/rust-lang/crates.io-index)" = "39e21a3b0618b97e727f67d46bf1a21954384f6be6bf72558cc48f149881066e" +"checksum lalrpop-snap 0.12.5 (registry+https://github.com/rust-lang/crates.io-index)" = "e82554f7abfe767e8a22286e7ca6d1ea7d873e91f0259981e15c7c6754d7340d" +"checksum lalrpop-util 0.12.5 (registry+https://github.com/rust-lang/crates.io-index)" = "36497edf44be49f4663ebd9cfb154a81c84491986a62773c62624911efd3d84d" "checksum lazy_static 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "49247ec2a285bb3dcb23cbd9c35193c025e7251bfce77c1d5da97e6362dffe7f" "checksum libc 0.2.16 (registry+https://github.com/rust-lang/crates.io-index)" = "408014cace30ee0f767b1c4517980646a573ec61a57957aeeabcac8ac0a02e8d" "checksum memchr 0.1.11 (registry+https://github.com/rust-lang/crates.io-index)" = "d8b629fb514376c675b98c1421e80b151d3817ac42d7c667717d282761418d20" diff --git a/Cargo.toml b/Cargo.toml index 431d61dd..81db725b 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -1,6 +1,6 @@ [package] name = "rusty-wam" -version = "0.1.0" +version = "0.3.0" authors = ["Mark Thom"] build = "build.rs" @@ -8,7 +8,7 @@ build = "build.rs" [dependencies] [dependencies.lalrpop-util] -version = "0.12.0" +version = "0.12.5" [build-dependencies.lalrpop] -version = "0.12.0" \ No newline at end of file +version = "0.12.5" \ No newline at end of file diff --git a/README.md b/README.md index dd2bd6cb..63397a7c 100644 --- a/README.md +++ b/README.md @@ -8,55 +8,70 @@ pure Prolog. ## Progress -The language L1 is implemented as a simple REPL. It supports -unification on facts and queries without backtracking and rules -without clauses, in the familiar Prolog syntax. No data types apart -from atoms are currently supported. +The language L2 is implemented as a simple REPL. It supports +unification on queries without backtracking, where rules and facts are +limited to a single name/arity pairing, in the familiar Prolog +syntax. No data types apart from atoms are currently supported. An example of the level of interaction currently supported is: ``` -l1> p(Z, Z). -l1> ?- p(Z, Z). +l2> p(Z, Z). +l2> ?- p(Z, Z). yes -l1> ?- p(Z, z). +l2> ?- p(Z, z). yes -l1> ?- p(Z, w). +l2> ?- p(Z, w). yes -l1> clouds(are, nice). -l1> ?- p(z, w). +l2> clouds(are, nice). +l2> ?- p(z, w). no -l1> ?- p(w, w). +l2> ?- p(w, w). yes -l1> ?- clouds(Z, Z). +l2> ?- clouds(Z, Z). no -l1> ?- clouds(Z, W). +l2> ?- clouds(Z, W). yes -l1> ?- clouds(are, W). +l2> ?- clouds(are, W). yes -l1> ?- clouds(W, nice). +l2> ?- clouds(W, nice). yes -l1> ?- clouds(nice, are). +l2> ?- clouds(nice, are). no -l1> ?- p(Z, h(Z, W), f(W)). +l2> ?- p(Z, h(Z, W), f(W)). no -l1> p(Z, h(Z, W), f(W)). -l1> ?- p(z, h(z, z), f(w)). +l2> p(Z, h(Z, W), f(W)). +l2> ?- p(z, h(z, z), f(w)). no -l1> ?- p(z, h(z, w), f(w)). +l2> ?- p(z, h(z, w), f(w)). yes -l1> ?- p(Z, h(z, W), f(w)). +l2> ?- p(Z, h(z, W), f(w)). yes -l1> ?- p(z, h(Z, w), f(w)). +l2> ?- p(z, h(Z, w), f(w)). yes -l1> ?- p(Z, h(Z, w), f(Z)). +l2> ?- p(Z, h(Z, w), f(Z)). yes -l1> ?- p(z, h(Z, w), f(Z)). +l2> ?- p(z, h(Z, w), f(Z)). no -l1> p(f(X), h(Y, f(a)), Y). -l1> ?- p(Z, h(Z, W), f(W)). +l2> p(f(X), h(Y, f(a)), Y). +l2> ?- p(Z, h(Z, W), f(W)). yes -l1> quit +l2> p(X, Y) :- q(X, Z), r(Z, Y). +l2> q(q, s). +l2> r(s, t). +l2> ?- p(X, Y). +yes +l2> ?- p(q, t). +yes +l2> ?- p(t, q). +no +l2> ?- p(q, T). +yes +l2> ?- p(Q, t). +yes +l2> ?- p(t, t). +no +l2> quit ``` ## Occurs check @@ -64,7 +79,7 @@ l1> quit There's no occurs check, so cyclic terms do unify: ``` -l1> p(W, W). -l1> ?- p(f(f(W)), W). +l2> p(W, W). +l2> ?- p(f(f(W)), W). yes ``` \ No newline at end of file diff --git a/src/l2/ast.rs b/src/l2/ast.rs new file mode 100644 index 00000000..bde5b358 --- /dev/null +++ b/src/l2/ast.rs @@ -0,0 +1,200 @@ +use std::cell::Cell; +use std::fmt; +use std::ops::{Add, AddAssign}; +use std::vec::Vec; + +pub type Var = String; + +pub type Atom = String; + +pub enum TopLevel { + Fact(Term), + Rule(Rule), + Query(Term) +} + +#[derive(Clone, Copy)] +pub enum Level { + Shallow, Deep +} + +impl fmt::Display for Level { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match self { + &Level::Shallow => write!(f, "A"), + &Level::Deep => write!(f, "X") + } + } +} + +#[derive(Clone, Copy)] +pub enum RegType { + Perm(usize), + Temp(usize) +} + +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 + } + } +} + +impl From for Addr { + fn from(reg: RegType) -> Addr { + match reg { + RegType::Perm(reg) => Addr::StackCell(reg), + RegType::Temp(reg) => Addr::RegNum(reg) + } + } +} + +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) + } + } +} + +#[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 enum Term { + Atom(Cell, Atom), + Clause(Cell, Atom, Vec>), + Var(Cell, Var) +} + +pub struct Rule { + pub head: (Term, Term), + pub clauses: Vec +} + +pub enum TermRef<'a> { + Atom(Level, &'a Cell, &'a Atom), + Clause(Level, &'a Cell, &'a Atom, &'a Vec>), + Var(Level, &'a Cell, &'a Var) +} + +pub enum FactInstruction { + GetStructure(Level, Atom, usize, RegType), + GetValue(RegType, usize), + GetVariable(RegType, usize), + UnifyVariable(RegType), + UnifyValue(RegType) +} + +pub enum QueryInstruction { + PutStructure(Level, Atom, usize, RegType), + PutValue(RegType, usize), + PutVariable(RegType, usize), + SetVariable(RegType), + SetValue(RegType) +} + +pub enum ControlInstruction { + Allocate(usize), + Call(Atom, usize), + Deallocate, + Proceed +} + +pub type CompiledFact = Vec; + +pub type CompiledQuery = Vec; + +pub enum Line { + Control(ControlInstruction), + Fact(CompiledFact), + Query(CompiledQuery) +} + +pub type Code = Vec; + +#[derive(Clone, Copy, PartialEq)] +pub enum Addr { + HeapCell(usize), + RegNum(usize), + StackCell(usize), +} + +#[derive(Clone)] +pub enum HeapCellValue { + NamedStr(usize, Atom), + Ref(usize), + Str(usize) +} + +#[derive(Clone, Copy)] +pub enum CodePtr { + DirEntry(usize), + 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) -> &Atom { + match self { + &Term::Atom(_, ref atom) + | &Term::Var(_, ref atom) + | &Term::Clause(_, ref atom, _) => atom + } + } + + pub fn arity(&self) -> usize { + match self { + &Term::Atom(_, _) | &Term::Var(_, _) => 0, + &Term::Clause(_, _, ref child_terms) => child_terms.len() + } + } +} diff --git a/src/l2/codegen.rs b/src/l2/codegen.rs new file mode 100644 index 00000000..4754b744 --- /dev/null +++ b/src/l2/codegen.rs @@ -0,0 +1,447 @@ +use l2::ast::*; +use l2::iterators::{FactIterator, QueryIterator}; + +use std::cell::Cell; +use std::collections::HashMap; +use std::fmt; +use std::vec::Vec; + +impl fmt::Display for FactInstruction { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match self { + &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::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::PutStructure(Level::Deep, ref name, ref arity, ref r) => + write!(f, "put_structure {}/{}, A{}", name, arity, r.reg_num()), + &QueryInstruction::PutStructure(Level::Shallow, ref name, ref arity, ref r) => + write!(f, "put_structure {}/{}, {}", name, arity, r), + &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::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") + } + } +} + +trait CompilationTarget<'a> { + type Iterator : Iterator>; + + fn iter(&'a Term) -> Self::Iterator; + + fn to_structure(Level, Atom, usize, RegType) -> 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 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 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 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 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() } + } + + fn to_structure(&mut self, + lvl: Level, + name: &'a Atom, + cell: &'a Cell, + arity: usize) + -> Target + where Target: CompilationTarget<'a> + { + self.marker.mark_non_var(lvl, cell); + Target::to_structure(lvl, name.clone(), arity, cell.get()) + } + + 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::Atom(ref cell, _) | &Term::Clause(ref cell, _, _) => + self.non_var_subterm(cell), + &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(); + + self.marker.advance(term); + + for term in iter { + match term { + TermRef::Atom(lvl, term, atom) => + target.push(self.to_structure(lvl, atom, term, 0)), + TermRef::Clause(lvl, term, atom, terms) => { + target.push(self.to_structure(lvl, atom, term, terms.len())); + + for subterm in terms { + target.push(self.subterm_to_instr(subterm.as_ref())); + } + }, + 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 | TermStatus::Recurrent => + 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 + } + + 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))); + body.push(Line::Fact(self.compile_target(p0))); + + body.append(&mut self.compile_query(p1)); + + let mut 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 { + 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 { + let mut compiled_query = + vec![Line::Query(self.compile_target(term))]; + + if let &Term::Clause(_, ref atom, ref terms) = term { + let call = Line::Control(ControlInstruction::Call(atom.clone(), + terms.len())); + compiled_query.push(call); + } + + compiled_query + } +} diff --git a/src/l2/iterators.rs b/src/l2/iterators.rs new file mode 100644 index 00000000..5c2b713a --- /dev/null +++ b/src/l2/iterators.rs @@ -0,0 +1,175 @@ +use l2::ast::*; + +use std::cell::Cell; +use std::collections::VecDeque; +use std::vec::Vec; + +enum IteratorState<'a> { + Atom(Level, &'a Cell, &'a Atom), + Clause(Level, usize, &'a Cell, &'a Atom, &'a Vec>), + IsolatedAtom(&'a Cell, &'a Atom), + IsolatedVar(&'a Cell, &'a Var), + RootClause(usize, &'a Vec>), + Var(Level, &'a Cell, &'a Var) +} + +impl<'a> IteratorState<'a> { + fn to_state(lvl: Level, term: &'a Term) -> IteratorState<'a> + { + match term { + &Term::Atom(ref cell, ref atom) => + IteratorState::Atom(lvl, cell, atom), + &Term::Clause(ref cell, ref atom, ref child_terms) => + IteratorState::Clause(lvl, 0, cell, atom, child_terms), + &Term::Var(ref cell, ref var) => + IteratorState::Var(lvl, cell, var) + } + } +} + +pub struct QueryIterator<'a> { + state_stack: Vec> +} + +impl<'a> QueryIterator<'a> { + fn push_clause(&mut self, + lvl: Level, + child_num: usize, + cell: &'a Cell, + name: &'a Atom, + child_terms: &'a Vec>) + { + self.state_stack.push(IteratorState::Clause(lvl, + child_num, + cell, + name, + child_terms)); + } + + fn push_root_clause(&mut self, + child_num: usize, + child_terms: &'a Vec>) + { + self.state_stack.push(IteratorState::RootClause(child_num, child_terms)); + } + + fn push_subterm(&mut self, lvl: Level, term: &'a Term) { + self.state_stack.push(IteratorState::to_state(lvl, term)); + } + + fn new(term: &'a Term) -> QueryIterator<'a> { + let state = match term { + &Term::Atom(ref cell, ref atom) => + IteratorState::IsolatedAtom(cell, atom), + &Term::Clause(_, _, ref terms) => + IteratorState::RootClause(0, terms), + &Term::Var(ref cell, ref var) => + IteratorState::IsolatedVar(cell, var) + }; + + QueryIterator { state_stack: vec![state] } + } +} + +impl<'a> Iterator for QueryIterator<'a> { + type Item = TermRef<'a>; + + fn next(&mut self) -> Option { + while let Some(iter_state) = self.state_stack.pop() { + match iter_state { + IteratorState::Atom(lvl, cell, atom) => + return Some(TermRef::Atom(lvl, cell, atom)), + IteratorState::Clause(lvl, child_num, cell, atom, child_terms) => { + if child_num == child_terms.len() { + return Some(TermRef::Clause(lvl, cell, atom, child_terms)); + } else { + self.push_clause(lvl, child_num + 1, cell, atom, child_terms); + self.push_subterm(Level::Deep, child_terms[child_num].as_ref()); + } + }, + IteratorState::IsolatedAtom(cell, atom) => + return Some(TermRef::Atom(Level::Shallow, cell, atom)), + IteratorState::IsolatedVar(cell, var) => + return Some(TermRef::Var(Level::Shallow, cell, var)), + IteratorState::RootClause(child_num, child_terms) => { + if child_num == child_terms.len() { + return None; + } else { + self.push_root_clause(child_num + 1, child_terms); + self.push_subterm(Level::Shallow, child_terms[child_num].as_ref()); + } + }, + IteratorState::Var(lvl, cell, var) => + return Some(TermRef::Var(lvl, cell, var)) + }; + } + + None + } +} + +pub struct FactIterator<'a> { + state_queue: VecDeque>, +} + +impl<'a> FactIterator<'a> { + fn push_subterm(&mut self, lvl: Level, term: &'a Term) { + self.state_queue.push_back(IteratorState::to_state(lvl, term)); + } + + fn new(term: &'a Term) -> FactIterator<'a> { + let states = match term { + &Term::Atom(ref cell, ref atom) => + vec![IteratorState::IsolatedAtom(cell, atom)], + &Term::Clause(_, _, ref terms) => + vec![IteratorState::RootClause(0, terms)], + &Term::Var(ref cell, ref var) => + vec![IteratorState::IsolatedVar(cell, var)] + }; + + FactIterator { state_queue: VecDeque::from(states) } + } +} + +impl<'a> Iterator for FactIterator<'a> { + type Item = TermRef<'a>; + + fn next(&mut self) -> Option { + while let Some(state) = self.state_queue.pop_front() { + match state { + IteratorState::Atom(lvl, cell, atom) => + return Some(TermRef::Atom(lvl, cell, atom)), + IteratorState::Clause(lvl, _, cell, atom, child_terms) => { + for child_term in child_terms { + self.push_subterm(Level::Deep, child_term); + } + + return Some(TermRef::Clause(lvl, cell, atom, child_terms)); + }, + IteratorState::IsolatedAtom(cell, atom) => + return Some(TermRef::Atom(Level::Shallow, cell, atom)), + IteratorState::IsolatedVar(cell, var) => + return Some(TermRef::Var(Level::Shallow, cell, var)), + IteratorState::RootClause(_, child_terms) => { + for child_term in child_terms { + self.push_subterm(Level::Shallow, child_term); + } + }, + IteratorState::Var(lvl, cell, var) => + return Some(TermRef::Var(lvl, cell, var)) + } + } + + None + } +} + +impl Term { + pub fn post_order_iter(&self) -> QueryIterator { + QueryIterator::new(self) + } + + pub fn breadth_first_iter(&self) -> FactIterator { + FactIterator::new(self) + } +} diff --git a/src/l2/l2_parser.lalrpop b/src/l2/l2_parser.lalrpop new file mode 100644 index 00000000..4bb84a7b --- /dev/null +++ b/src/l2/l2_parser.lalrpop @@ -0,0 +1,42 @@ +use l2::ast::*; + +use std::cell::Cell; + +grammar; + +pub TopLevel: TopLevel = { + "?-" "." => TopLevel::Query(t), + "." => TopLevel::Rule(r), + "." => TopLevel::Fact(t), +}; + +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::new(RegType::Temp(0)), a, ts) + }, +}; + +Rule : Rule = { + ":-" )*> => + Rule { head: (c, h), clauses: cs }, +}; + +Term : Term = { + => <>, + => Term::Atom(Cell::new(RegType::Temp(0)), <>), + => Term::Var(Cell::new(VarReg::Norm(RegType::Temp(0))), <>), +}; + +Var : Var = { + r"[A-Z][a-z0-9_]*" => <>.trim().to_string(), +}; \ No newline at end of file diff --git a/src/l2/l2_parser.rs b/src/l2/l2_parser.rs new file mode 100644 index 00000000..6170071b --- /dev/null +++ b/src/l2/l2_parser.rs @@ -0,0 +1,1767 @@ +use l2::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 l2::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), + 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>), + NtAtom(Atom), + NtBoxedTerm(Box), + NtClause(Term), + NtRule(Rule), + NtTerm(Term), + NtTopLevel(TopLevel), + NtVar(Var), + Nt____TopLevel(TopLevel), + } + const __ACTION: &'static [i32] = &[ + // State 0 + 0, 0, 0, 0, 0, 8, 9, 10, 0, + // State 1 + 11, 0, 0, -18, 0, 0, 0, 0, 0, + // State 2 + 0, 0, 0, -17, 12, 0, 0, 0, 0, + // State 3 + 0, 0, 0, 13, 0, 0, 0, 0, 0, + // State 4 + 0, 0, 0, 14, 0, 0, 0, 0, 0, + // State 5 + 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 6 + 0, 0, 0, -19, 0, 0, 0, 0, 0, + // State 7 + 0, 0, 0, 0, 0, 0, 9, 10, 0, + // State 8 + 0, 0, 0, -23, 0, 0, 0, 0, 0, + // State 9 + -11, 0, 0, -11, 0, 0, 0, 0, 0, + // State 10 + 0, 0, 0, 0, 0, 0, 24, 25, 0, + // State 11 + 0, 0, 0, 0, 0, 0, 30, 31, 0, + // State 12 + 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 13 + 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 14 + 32, 0, 0, -18, 0, 0, 0, 0, 0, + // State 15 + 0, 0, 0, -17, 0, 0, 0, 0, 0, + // State 16 + 0, 0, 0, 33, 0, 0, 0, 0, 0, + // State 17 + 0, 0, 0, 0, 0, 0, 24, 25, 0, + // State 18 + 35, -18, -18, 0, 0, 0, 0, 0, 0, + // State 19 + 0, 36, 37, 0, 0, 0, 0, 0, 0, + // State 20 + 0, -17, -17, 0, 0, 0, 0, 0, 0, + // State 21 + 0, -12, -12, 0, 0, 0, 0, 0, 0, + // State 22 + 0, -19, -19, 0, 0, 0, 0, 0, 0, + // State 23 + 0, -23, -23, 0, 0, 0, 0, 0, 0, + // State 24 + -11, -11, -11, 0, 0, 0, 0, 0, 0, + // State 25 + 38, 0, -18, -18, 0, 0, 0, 0, 0, + // State 26 + 0, 0, -17, -17, 0, 0, 0, 0, 0, + // State 27 + 0, 0, 40, -15, 0, 0, 0, 0, 0, + // State 28 + 0, 0, -19, -19, 0, 0, 0, 0, 0, + // State 29 + 0, 0, -23, -23, 0, 0, 0, 0, 0, + // State 30 + -11, 0, -11, -11, 0, 0, 0, 0, 0, + // State 31 + 0, 0, 0, 0, 0, 0, 24, 25, 0, + // State 32 + 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 33 + 0, 43, 44, 0, 0, 0, 0, 0, 0, + // State 34 + 0, 0, 0, 0, 0, 0, 24, 25, 0, + // State 35 + 0, 0, 0, -13, -13, 0, 0, 0, 0, + // State 36 + 0, 0, 0, 0, 0, 0, -9, -9, 0, + // State 37 + 0, 0, 0, 0, 0, 0, 24, 25, 0, + // State 38 + 0, 0, 49, -16, 0, 0, 0, 0, 0, + // State 39 + 0, 0, 0, 0, 0, 0, 30, 31, 0, + // State 40 + 0, 0, 0, 0, 0, 0, 24, 25, 0, + // State 41 + 0, 52, 37, 0, 0, 0, 0, 0, 0, + // State 42 + 0, 0, 0, -14, -14, 0, 0, 0, 0, + // State 43 + 0, 0, 0, 0, 0, 0, -10, -10, 0, + // State 44 + 0, 0, 0, 0, 0, 0, 24, 25, 0, + // State 45 + 0, 54, 37, 0, 0, 0, 0, 0, 0, + // State 46 + 0, 0, 0, 0, 0, 0, 24, 25, 0, + // State 47 + 0, 56, 37, 0, 0, 0, 0, 0, 0, + // State 48 + 0, 0, 0, 0, 0, 0, 30, 31, 0, + // State 49 + 0, 0, -4, -4, 0, 0, 0, 0, 0, + // State 50 + 0, 58, 44, 0, 0, 0, 0, 0, 0, + // State 51 + 0, 0, 0, -13, 0, 0, 0, 0, 0, + // State 52 + 0, 59, 44, 0, 0, 0, 0, 0, 0, + // State 53 + 0, -13, -13, 0, 0, 0, 0, 0, 0, + // State 54 + 0, 60, 44, 0, 0, 0, 0, 0, 0, + // State 55 + 0, 0, -13, -13, 0, 0, 0, 0, 0, + // State 56 + 0, 0, -5, -5, 0, 0, 0, 0, 0, + // State 57 + 0, 0, 0, -14, 0, 0, 0, 0, 0, + // State 58 + 0, -14, -14, 0, 0, 0, 0, 0, 0, + // State 59 + 0, 0, -14, -14, 0, 0, 0, 0, 0, + ]; + const __EOF_ACTION: &'static [i32] = &[ + 0, + 0, + 0, + 0, + 0, + -24, + 0, + 0, + 0, + 0, + 0, + 0, + -21, + -22, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + 0, + -20, + 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, 2, 0, 3, 4, 5, 6, 7, 0, + // State 1 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 2 + 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, + // State 4 + 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, + // State 6 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 7 + 0, 0, 0, 0, 0, 0, 15, 0, 16, 0, 17, 0, 7, 0, + // State 8 + 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, + // State 10 + 0, 0, 0, 0, 0, 18, 19, 20, 21, 0, 22, 0, 23, 0, + // State 11 + 0, 0, 0, 0, 0, 0, 26, 0, 27, 0, 28, 0, 29, 0, + // State 12 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 13 + 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, + // State 15 + 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, + // State 17 + 0, 0, 0, 0, 0, 0, 19, 34, 21, 0, 22, 0, 23, 0, + // State 18 + 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, + // State 20 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 21 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 22 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 23 + 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, + // State 25 + 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, + // State 27 + 0, 0, 39, 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, + // State 29 + 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, + // State 31 + 0, 0, 0, 0, 0, 41, 19, 42, 21, 0, 22, 0, 23, 0, + // State 32 + 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, + // State 34 + 0, 0, 0, 0, 0, 45, 19, 46, 21, 0, 22, 0, 23, 0, + // State 35 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 36 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 37 + 0, 0, 0, 0, 0, 47, 19, 48, 21, 0, 22, 0, 23, 0, + // State 38 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 39 + 0, 0, 0, 0, 0, 0, 26, 0, 27, 0, 50, 0, 29, 0, + // State 40 + 0, 0, 0, 0, 0, 0, 19, 51, 21, 0, 22, 0, 23, 0, + // State 41 + 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, + // State 43 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 44 + 0, 0, 0, 0, 0, 0, 19, 53, 21, 0, 22, 0, 23, 0, + // State 45 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 46 + 0, 0, 0, 0, 0, 0, 19, 55, 21, 0, 22, 0, 23, 0, + // State 47 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 48 + 0, 0, 0, 0, 0, 0, 26, 0, 27, 0, 57, 0, 29, 0, + // State 49 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 50 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 51 + 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, + // State 53 + 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, + // State 55 + 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, + // State 57 + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + // State 58 + 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, + ]; + fn __expected_tokens(__state: usize) -> Vec<::std::string::String> { + const __TERMINAL: &'static [&'static str] = &[ + r###""(""###, + r###"")""###, + r###"",""###, + r###"".""###, + r###"":-""###, + r###""?-""###, + r###"r#"[A-Z][a-z0-9_]*"#"###, + r###"r#"[a-z][a-z0-9_]*"#"###, + ]; + __ACTION[(__state * 9)..].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, + _ => { + 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 * 9 + __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::Termr_23_22_5bA_2dZ_5d_5ba_2dz0_2d9___5d_2a_22_23(__tok0), + _ => unreachable!(), + }, + 7 => match __lookahead.1 { + (7, __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(14); + 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::__action14::<>(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(12); + 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::__action12::<>(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(13); + 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::__action13::<>(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(22); + 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::__action22::<>(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(23); + 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::__action23::<>(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(17); + 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::__action17::<>(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(15); + 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::__action15::<>(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(16); + 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::__action16::<>(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(26); + 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::__action26::<>(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(27); + 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::__action27::<>(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 => { + // Atom = r#"[a-z][a-z0-9_]*"# => ActionFn(4); + let __sym0 = __pop_Termr_23_22_5ba_2dz_5d_5ba_2dz0_2d9___5d_2a_22_23(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action4::<>(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtAtom(__nt), __end)); + 6 + } + 12 => { + // BoxedTerm = Term => ActionFn(5); + let __sym0 = __pop_NtTerm(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action5::<>(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtBoxedTerm(__nt), __end)); + 7 + } + 13 => { + // Clause = Atom, "(", BoxedTerm, ")" => ActionFn(28); + 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::__action28::<>(input, __sym0, __sym1, __sym2, __sym3); + let __states_len = __states.len(); + __states.truncate(__states_len - 4); + __symbols.push((__start, __Symbol::NtClause(__nt), __end)); + 8 + } + 14 => { + // Clause = Atom, "(", ( ",")+, BoxedTerm, ")" => ActionFn(29); + 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::__action29::<>(input, __sym0, __sym1, __sym2, __sym3, __sym4); + let __states_len = __states.len(); + __states.truncate(__states_len - 5); + __symbols.push((__start, __Symbol::NtClause(__nt), __end)); + 8 + } + 15 => { + // Rule = Clause, ":-", Term => ActionFn(24); + 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::__action24::<>(input, __sym0, __sym1, __sym2); + let __states_len = __states.len(); + __states.truncate(__states_len - 3); + __symbols.push((__start, __Symbol::NtRule(__nt), __end)); + 9 + } + 16 => { + // Rule = Clause, ":-", Term, ("," )+ => ActionFn(25); + 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::__action25::<>(input, __sym0, __sym1, __sym2, __sym3); + let __states_len = __states.len(); + __states.truncate(__states_len - 4); + __symbols.push((__start, __Symbol::NtRule(__nt), __end)); + 9 + } + 17 => { + // Term = Clause => ActionFn(8); + let __sym0 = __pop_NtClause(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action8::<>(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtTerm(__nt), __end)); + 10 + } + 18 => { + // Term = Atom => ActionFn(9); + let __sym0 = __pop_NtAtom(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action9::<>(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtTerm(__nt), __end)); + 10 + } + 19 => { + // Term = Var => ActionFn(10); + let __sym0 = __pop_NtVar(__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::NtTerm(__nt), __end)); + 10 + } + 20 => { + // 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)); + 11 + } + 21 => { + // TopLevel = Rule, "." => ActionFn(2); + 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::__action2::<>(input, __sym0, __sym1); + let __states_len = __states.len(); + __states.truncate(__states_len - 2); + __symbols.push((__start, __Symbol::NtTopLevel(__nt), __end)); + 11 + } + 22 => { + // TopLevel = Term, "." => ActionFn(3); + 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::__action3::<>(input, __sym0, __sym1); + let __states_len = __states.len(); + __states.truncate(__states_len - 2); + __symbols.push((__start, __Symbol::NtTopLevel(__nt), __end)); + 11 + } + 23 => { + // Var = r#"[A-Z][a-z0-9_]*"# => ActionFn(11); + 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::__action11::<>(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtVar(__nt), __end)); + 12 + } + 24 => { + // __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 * 14 + __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_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_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_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((6, __index + __ch.len_utf8())); + __current_state = 7; + continue; + } + 97 ... 122 => { + __current_match = Some((7, __index + __ch.len_utf8())); + __current_state = 8; + 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 = 10; + 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 = 11; + continue; + } + _ => { + return __current_match; + } + } + } + 7 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 48 ... 57 => { + __current_match = Some((6, __index + __ch.len_utf8())); + __current_state = 12; + continue; + } + 95 => /* '_' */ { + __current_match = Some((6, __index + 1)); + __current_state = 12; + continue; + } + 97 ... 122 => { + __current_match = Some((6, __index + __ch.len_utf8())); + __current_state = 12; + continue; + } + _ => { + return __current_match; + } + } + } + 8 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 48 ... 57 => { + __current_match = Some((7, __index + __ch.len_utf8())); + __current_state = 13; + continue; + } + 95 => /* '_' */ { + __current_match = Some((7, __index + 1)); + __current_state = 13; + continue; + } + 97 ... 122 => { + __current_match = Some((7, __index + __ch.len_utf8())); + __current_state = 13; + 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 { + _ => { + return __current_match; + } + } + } + 12 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 48 ... 57 => { + __current_match = Some((6, __index + __ch.len_utf8())); + __current_state = 12; + continue; + } + 95 => /* '_' */ { + __current_match = Some((6, __index + 1)); + __current_state = 12; + continue; + } + 97 ... 122 => { + __current_match = Some((6, __index + __ch.len_utf8())); + __current_state = 12; + continue; + } + _ => { + return __current_match; + } + } + } + 13 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 48 ... 57 => { + __current_match = Some((7, __index + __ch.len_utf8())); + __current_state = 13; + continue; + } + 95 => /* '_' */ { + __current_match = Some((7, __index + 1)); + __current_state = 13; + continue; + } + 97 ... 122 => { + __current_match = Some((7, __index + __ch.len_utf8())); + __current_state = 13; + 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, + (_, r, _): (usize, Rule, usize), + (_, _, _): (usize, &'input str, usize), +) -> TopLevel +{ + TopLevel::Rule(r) +} + +#[allow(unused_variables)] +pub fn __action3< + 'input, +>( + input: &'input str, + (_, t, _): (usize, Term, usize), + (_, _, _): (usize, &'input str, usize), +) -> TopLevel +{ + TopLevel::Fact(t) +} + +#[allow(unused_variables)] +pub fn __action4< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, &'input str, usize), +) -> Atom +{ + __0.trim().to_string() +} + +#[allow(unused_variables)] +pub fn __action5< + 'input, +>( + input: &'input str, + (_, t, _): (usize, Term, usize), +) -> Box +{ + Box::new(t) +} + +#[allow(unused_variables)] +pub fn __action6< + 'input, +>( + input: &'input str, + (_, a, _): (usize, Atom, usize), + (_, _, _): (usize, &'input str, usize), + (_, ts, _): (usize, ::std::vec::Vec>, usize), + (_, t, _): (usize, Box, usize), + (_, _, _): (usize, &'input str, usize), +) -> Term +{ + { + let mut ts = ts; + ts.push(t); + Term::Clause(Cell::new(RegType::Temp(0)), a, ts) + } +} + +#[allow(unused_variables)] +pub fn __action7< + '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 __action8< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Term, usize), +) -> Term +{ + __0 +} + +#[allow(unused_variables)] +pub fn __action9< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Atom, usize), +) -> Term +{ + Term::Atom(Cell::new(RegType::Temp(0)), __0) +} + +#[allow(unused_variables)] +pub fn __action10< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Var, usize), +) -> Term +{ + Term::Var(Cell::new(VarReg::Norm(RegType::Temp(0))), __0) +} + +#[allow(unused_variables)] +pub fn __action11< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, &'input str, usize), +) -> Var +{ + __0.trim().to_string() +} + +#[allow(unused_variables)] +pub fn __action12< + 'input, +>( + input: &'input str, + __lookbehind: &usize, + __lookahead: &usize, +) -> ::std::vec::Vec +{ + vec![] +} + +#[allow(unused_variables)] +pub fn __action13< + 'input, +>( + input: &'input str, + (_, v, _): (usize, ::std::vec::Vec, usize), +) -> ::std::vec::Vec +{ + v +} + +#[allow(unused_variables)] +pub fn __action14< + 'input, +>( + input: &'input str, + (_, _, _): (usize, &'input str, usize), + (_, __0, _): (usize, Term, usize), +) -> Term +{ + (__0) +} + +#[allow(unused_variables)] +pub fn __action15< + 'input, +>( + input: &'input str, + __lookbehind: &usize, + __lookahead: &usize, +) -> ::std::vec::Vec> +{ + vec![] +} + +#[allow(unused_variables)] +pub fn __action16< + 'input, +>( + input: &'input str, + (_, v, _): (usize, ::std::vec::Vec>, usize), +) -> ::std::vec::Vec> +{ + v +} + +#[allow(unused_variables)] +pub fn __action17< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Box, usize), + (_, _, _): (usize, &'input str, usize), +) -> Box +{ + (__0) +} + +#[allow(unused_variables)] +pub fn __action18< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Box, usize), +) -> ::std::vec::Vec> +{ + vec![__0] +} + +#[allow(unused_variables)] +pub fn __action19< + '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 __action20< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Term, usize), +) -> ::std::vec::Vec +{ + vec![__0] +} + +#[allow(unused_variables)] +pub fn __action21< + '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 __action22< + '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 = __action14( + input, + __0, + __1, + ); + let __temp0 = (__start0, __temp0, __end0); + __action20( + input, + __temp0, + ) +} + +#[allow(unused_variables)] +pub fn __action23< + '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 = __action14( + input, + __1, + __2, + ); + let __temp0 = (__start0, __temp0, __end0); + __action21( + input, + __0, + __temp0, + ) +} + +#[allow(unused_variables)] +pub fn __action24< + '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 = __action12( + input, + &__start0, + &__end0, + ); + let __temp0 = (__start0, __temp0, __end0); + __action7( + input, + __0, + __1, + __2, + __temp0, + ) +} + +#[allow(unused_variables)] +pub fn __action25< + '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 = __action13( + input, + __3, + ); + let __temp0 = (__start0, __temp0, __end0); + __action7( + input, + __0, + __1, + __2, + __temp0, + ) +} + +#[allow(unused_variables)] +pub fn __action26< + '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 = __action17( + input, + __0, + __1, + ); + let __temp0 = (__start0, __temp0, __end0); + __action18( + input, + __temp0, + ) +} + +#[allow(unused_variables)] +pub fn __action27< + '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 = __action17( + input, + __1, + __2, + ); + let __temp0 = (__start0, __temp0, __end0); + __action19( + input, + __0, + __temp0, + ) +} + +#[allow(unused_variables)] +pub fn __action28< + '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 = __action15( + input, + &__start0, + &__end0, + ); + let __temp0 = (__start0, __temp0, __end0); + __action6( + input, + __0, + __1, + __temp0, + __2, + __3, + ) +} + +#[allow(unused_variables)] +pub fn __action29< + '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 = __action16( + input, + __2, + ); + let __temp0 = (__start0, __temp0, __end0); + __action6( + input, + __0, + __1, + __temp0, + __3, + __4, + ) +} + +pub trait __ToTriple<'input, > { + type Error; + fn to_triple(value: Self) -> Result<(usize,(usize, &'input str),usize),Self::Error>; +} + +impl<'input, > __ToTriple<'input, > for (usize, (usize, &'input str), usize) { + type Error = (); + fn to_triple(value: Self) -> Result<(usize,(usize, &'input str),usize),()> { + Ok(value) + } +} +impl<'input, > __ToTriple<'input, > for Result<(usize, (usize, &'input str), usize),()> { + type Error = (); + fn to_triple(value: Self) -> Result<(usize,(usize, &'input str),usize),()> { + value + } +} diff --git a/src/l2/machine.rs b/src/l2/machine.rs new file mode 100644 index 00000000..c19cb40f --- /dev/null +++ b/src/l2/machine.rs @@ -0,0 +1,400 @@ +use l2::ast::*; +use l2::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, + cp: CodePtr, + fail: bool, + heap: Heap, + mode: MachineMode, + stack: Stack, + registers: Registers +} + +type CodeDir = HashMap<(Atom, usize), usize>; + +pub struct Machine { + ms: MachineState, + code: Code, + code_dir: CodeDir +} + +impl Index for MachineState { + type Output = HeapCellValue; + + fn index(&self, index: Addr) -> &Self::Output { + match index { + Addr::HeapCell(hc) => &self.heap[hc], + Addr::RegNum(reg) => &self.registers[reg], + Addr::StackCell(sc) => &self.stack[sc] + } + } +} + +impl IndexMut for MachineState { + fn index_mut(&mut self, index: Addr) -> &mut Self::Output { + match index { + Addr::HeapCell(hc) => &mut self.heap[hc], + Addr::RegNum(reg) => &mut self.registers[reg], + Addr::StackCell(sc) => &mut self.stack[sc] + } + } +} + +impl Machine { + pub fn new() -> Self { + Machine { + ms: MachineState::new(), + code: Vec::new(), + code_dir: HashMap::new() + } + } + + fn failed(&self) -> bool { + self.ms.fail + } + + pub fn add_fact(&mut self, fact: &Term, mut code: Code) { + let p = self.code.len(); + let name = fact.name().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) { + let p = self.code.len(); + let name = rule.head.0.name().clone(); + let arity = rule.head.1.arity(); + + self.code.append(&mut code); + self.code_dir.insert((name, arity), p); + } + + fn execute_instr(&mut self, instr: &Line) -> bool { + let mut instr = instr; + + loop { + match instr { + &Line::Fact(ref fact) => { + for fact_instr in fact { + self.ms.execute_fact_instr(&fact_instr); + } + self.ms.p += 1; + }, + &Line::Query(ref query) => { + for query_instr in query { + 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() { + return false; + } + + match self.ms.p { + CodePtr::DirEntry(p) if p < self.code.len() => + instr = &self.code[p], + _ => break + } + } + + true + } + + pub fn execute_query(&mut self, query: Code) -> bool { + let mut succeeded = true; + + for instr in query { + succeeded = self.execute_instr(&instr); + if !succeeded { + break; + } + } + + self.ms.reset(); + succeeded + } +} + +impl MachineState { + fn new() -> MachineState { + MachineState { h: 0, + s: 0, + p: CodePtr::TopLevel, + cp: CodePtr::TopLevel, + fail: false, + heap: Vec::with_capacity(256), + mode: MachineMode::Write, + stack: Stack::new(), + registers: vec![HeapCellValue::Ref(0); 32] } + } + + fn lookup(&self, a: Addr) -> &HeapCellValue { + match a { + Addr::HeapCell(hc) => &self.heap[hc], + Addr::RegNum(reg) => &self.registers[reg], + Addr::StackCell(sc) => &self.stack[sc] + } + } + + fn deref(&self, a: Addr) -> Addr { + let mut a = a; + + loop { + if let &HeapCellValue::Ref(value) = self.lookup(a) { + if let Addr::HeapCell(av) = a { + if value != av { + a = Addr::HeapCell(value); + continue; + } + } else { + a = Addr::HeapCell(value); + continue; + } + } + + return a; + }; + } + + fn is_unbound(hc: &HeapCellValue, index: usize) -> bool { + match hc { + &HeapCellValue::Ref(r) => r == index, + _ => false + } + } + + fn bind(&mut self, a: Addr, val: usize) { + let mut a = a; + + loop { + match a { + addr @ Addr::RegNum(_) | addr @ Addr::StackCell(_) => { + if let HeapCellValue::Ref(hc) = self[addr] { + a = Addr::HeapCell(hc); + } else if Self::is_unbound(&self.heap[val], val) { + self.heap[val] = self[addr].clone(); + break; + } else { + self.fail = true; + break; + } + }, + Addr::HeapCell(hc) => { + if Self::is_unbound(&self.heap[hc], hc) { + self.heap[hc] = HeapCellValue::Ref(val); + break; + } else if Self::is_unbound(&self.heap[val], val) { + self.heap[val] = HeapCellValue::Ref(hc); + break; + } else { + self.fail = true; + break; + } + } + }; + } + } + + 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.lookup(d1), self.lookup(d2)) { + (&HeapCellValue::Ref(hc), _) => + self.bind(d2, hc), + (_, &HeapCellValue::Ref(hc)) => + self.bind(d1, hc), + (&HeapCellValue::Str(a1), &HeapCellValue::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 { + pdl.push(Addr::HeapCell(a1 + i)); + pdl.push(Addr::HeapCell(a2 + i)); + } + + continue; + } + } + } + + self.fail = true; + }, + _ => self.fail = true, + }; + } + } + } + + fn execute_query_instr(&mut self, instr: &QueryInstruction) { + match instr { + &QueryInstruction::PutStructure(_, ref name, arity, reg) => { + self.heap.push(HeapCellValue::Str(self.h + 1)); + self.heap.push(HeapCellValue::NamedStr(arity, name.clone())); + + self[Addr::from(reg)] = self.heap[self.h].clone(); + + self.h += 2; + }, + &QueryInstruction::PutValue(norm, arg) => + self.registers[arg] = self[Addr::from(norm)].clone(), + &QueryInstruction::PutVariable(norm, arg) => { + self.heap.push(HeapCellValue::Ref(self.h)); + + self[Addr::from(norm)] = self.heap[self.h].clone(); + self.registers[arg] = self.heap[self.h].clone(); + + self.h += 1; + }, + &QueryInstruction::SetVariable(reg) => { + self.heap.push(HeapCellValue::Ref(self.h)); + self[Addr::from(reg)] = self.heap[self.h].clone(); + + self.h += 1; + }, + &QueryInstruction::SetValue(reg) => { + let heap_val = self[Addr::from(reg)].clone(); + self.heap.push(heap_val); + self.h += 1; + }, + } + } + + fn execute_fact_instr(&mut self, instr: &FactInstruction) { + match instr { + &FactInstruction::GetStructure(_, ref name, arity, reg) => { + let addr = self.deref(Addr::from(reg)); + + match self.lookup(addr) { + &HeapCellValue::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; + } + } + }, + &HeapCellValue::Ref(r) => { + self.heap.push(HeapCellValue::Str(self.h + 1)); + self.heap.push(HeapCellValue::NamedStr(arity, name.clone())); + + let h = self.h; + + self.bind(Addr::HeapCell(r), h); + + self.h += 2; + self.mode = MachineMode::Write; + }, + _ => self.fail = true, + }; + }, + &FactInstruction::GetVariable(norm, arg) => + self[Addr::from(norm)] = self.registers[arg].clone(), + &FactInstruction::GetValue(norm, arg) => + self.unify(Addr::from(norm), Addr::RegNum(arg)), + &FactInstruction::UnifyVariable(reg) => { + match self.mode { + MachineMode::Read => + self[Addr::from(reg)] = self.heap[self.s].clone(), + MachineMode::Write => { + self.heap.push(HeapCellValue::Ref(self.h)); + + self[Addr::from(reg)] = self.heap[self.h].clone(); + self.h += 1; + } + }; + + self.s += 1; + }, + &FactInstruction::UnifyValue(reg) => { + let s = self.s; + + match self.mode { + MachineMode::Read => + self.unify(Addr::from(reg), Addr::HeapCell(s)), + MachineMode::Write => { + let heap_val = self[Addr::from(reg)].clone(); + self.heap.push(heap_val); + self.h += 1; + } + }; + + self.s += 1; + } + } + } + + fn execute_ctrl_instr(&mut self, code_dir: &CodeDir, instr: &ControlInstruction) + { + match instr { + &ControlInstruction::Allocate(num_cells) => { + self.stack.push(self.cp, num_cells); + 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.p = CodePtr::DirEntry(compiled_tl_index); + }, + None => self.fail = true + }; + }, + &ControlInstruction::Deallocate => { + self.p = self.stack.get_cp(); + self.stack.pop(); + }, + &ControlInstruction::Proceed => { + self.p = self.cp; + } + }; + } + + fn reset(&mut self) { + self.h = 0; + self.s = 0; + self.p = CodePtr::TopLevel; + self.cp = CodePtr::TopLevel; + + self.fail = false; + self.heap.clear(); + self.mode = MachineMode::Write; + self.stack = Stack::new(); + self.registers = vec![HeapCellValue::Ref(0); 32]; + } +} diff --git a/src/l2/mod.rs b/src/l2/mod.rs new file mode 100644 index 00000000..503e5366 --- /dev/null +++ b/src/l2/mod.rs @@ -0,0 +1,6 @@ +pub mod ast; +pub mod iterators; +pub mod l2_parser; +pub mod codegen; +pub mod machine; +pub mod stack; diff --git a/src/l2/stack.rs b/src/l2/stack.rs new file mode 100644 index 00000000..35c77770 --- /dev/null +++ b/src/l2/stack.rs @@ -0,0 +1,60 @@ +use l2::ast::*; + +use std::ops::{Index, IndexMut}; +use std::vec::Vec; + +struct Frame { + cp: CodePtr, + perms: Vec +} + +impl Frame { + fn new(cp: CodePtr, n: usize) -> Self { + Frame { + cp: cp, + perms: vec![HeapCellValue::Ref(0); n] + } + } + + fn read_pv(&self, i: usize) -> &HeapCellValue { + self.perms.index(i) + } + + fn read_pv_mut(&mut self, i: usize) -> &mut HeapCellValue { + self.perms.index_mut(i) + } +} + +pub struct Stack(Vec); + +impl Stack { + pub fn new() -> Self { + Stack(Vec::new()) + } + + pub fn push(&mut self, cp: CodePtr, n: usize) { + self.0.push(Frame::new(cp, n)); + } + + pub fn get_cp(&self) -> CodePtr { + self.0.last().unwrap().cp + } + + pub fn pop(&mut self) { + self.0.pop(); + } +} + +impl Index for Stack { + type Output = HeapCellValue; + + fn index(&self, index: usize) -> &Self::Output { + self.0.last().unwrap().read_pv(index - 1) + } +} + +impl IndexMut for Stack { + fn index_mut(&mut self, index: usize) -> &mut Self::Output { + self.0.last_mut().unwrap().read_pv_mut(index - 1) + } +} diff --git a/src/main.rs b/src/main.rs index e3fa6578..f285cbf7 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,56 +1,56 @@ -mod l1; +mod l2; -use l1::ast::TopLevel; -use l1::codegen::{compile_fact, compile_query}; -use l1::machine::Machine; +use l2::ast::*; +use l2::codegen::*; +use l2::machine::*; use std::io::{self, Write}; -fn l1_repl() { - let mut ms = Machine::new(); +fn l2_repl() { + let mut wam = Machine::new(); loop { - print!("l1> "); + print!("l2> "); let _ = io::stdout().flush(); let mut buffer = String::new(); io::stdin().read_line(&mut buffer).unwrap(); - let result = l1::l1_parser::parse_TopLevel(&*buffer); + let result = l2::l2_parser::parse_TopLevel(&*buffer); if &*buffer == "quit\n" { break; } else if &*buffer == "clear\n" { - ms = Machine::new(); + wam = Machine::new(); } - match result { - Ok(TopLevel::Fact(fact)) => { - let name = fact.name().to_owned(); - let arity = fact.arity(); - let fact = compile_fact(&fact); + let mut cg = CodeGenerator::new(); - ms.add_fact(fact, name, arity); + match &result { + &Ok(TopLevel::Fact(ref fact)) => { + let compiled_fact = cg.compile_fact(&fact); + wam.add_fact(fact, compiled_fact); }, - Ok(TopLevel::Query(query)) => { - let compiled_query = compile_query(&query); - - ms.execute_query(&compiled_query); - - if ms.failed() { - println!("no"); - } else { + &Ok(TopLevel::Rule(ref rule)) => { + let compiled_rule = cg.compile_rule(&rule); + wam.add_rule(rule, compiled_rule); + }, + &Ok(TopLevel::Query(ref query)) => { + let compiled_query = cg.compile_query(&query); + let succeeded = wam.execute_query(compiled_query); + + if succeeded { println!("yes"); + } else { + println!("no"); } - - ms.reset_machine_state(); }, - Err(_) => println!("Grammatical error of some kind!"), + &Err(_) => println!("Grammatical error of some kind!"), }; } } fn main() { - l1_repl(); + l2_repl(); } -- 2.54.0