From 8d1441e20f74b92d63d1a813afc035373ae192cc Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Fri, 28 Oct 2016 19:53:08 -0600 Subject: [PATCH] Initial commit. --- Cargo.lock | 267 +++++++ Cargo.toml | 14 + README.md | 43 +- build.rs | 5 + src/l0/ast.rs | 63 ++ src/l0/codegen.rs | 160 ++++ src/l0/l0_parser.lalrpop | 30 + src/l0/l0_parser.rs | 1593 ++++++++++++++++++++++++++++++++++++++ src/l0/machine.rs | 240 ++++++ src/l0/mod.rs | 4 + src/main.rs | 76 ++ 11 files changed, 2494 insertions(+), 1 deletion(-) create mode 100644 Cargo.lock create mode 100644 Cargo.toml create mode 100644 build.rs create mode 100644 src/l0/ast.rs create mode 100644 src/l0/codegen.rs create mode 100644 src/l0/l0_parser.lalrpop create mode 100644 src/l0/l0_parser.rs create mode 100644 src/l0/machine.rs create mode 100644 src/l0/mod.rs create mode 100644 src/main.rs diff --git a/Cargo.lock b/Cargo.lock new file mode 100644 index 00000000..f1c5f02a --- /dev/null +++ b/Cargo.lock @@ -0,0 +1,267 @@ +[root] +name = "rusty-wam" +version = "0.1.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)", +] + +[[package]] +name = "aho-corasick" +version = "0.5.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "memchr 0.1.11 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "atty" +version = "0.1.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "kernel32-sys 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)", + "libc 0.2.16 (registry+https://github.com/rust-lang/crates.io-index)", + "winapi 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "bit-set" +version = "0.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "bit-vec 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "bit-vec" +version = "0.4.3" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "bitflags" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "diff" +version = "0.1.9" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "docopt" +version = "0.6.83" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "lazy_static 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)", + "regex 0.1.75 (registry+https://github.com/rust-lang/crates.io-index)", + "rustc-serialize 0.3.19 (registry+https://github.com/rust-lang/crates.io-index)", + "strsim 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "fixedbitset" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "itertools" +version = "0.3.25" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "kernel32-sys" +version = "0.2.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "winapi 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)", + "winapi-build 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "lalrpop" +version = "0.12.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "atty 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)", + "bit-set 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)", + "bitflags 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", + "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)", + "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)", + "rustc-serialize 0.3.19 (registry+https://github.com/rust-lang/crates.io-index)", + "term 0.4.4 (registry+https://github.com/rust-lang/crates.io-index)", + "unicode-xid 0.0.2 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "lalrpop-intern" +version = "0.12.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "lalrpop-snap" +version = "0.12.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "atty 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)", + "bit-set 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)", + "bitflags 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", + "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)", + "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)", + "rustc-serialize 0.3.19 (registry+https://github.com/rust-lang/crates.io-index)", + "term 0.4.4 (registry+https://github.com/rust-lang/crates.io-index)", + "unicode-xid 0.0.2 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "lalrpop-util" +version = "0.12.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "lazy_static" +version = "0.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "libc" +version = "0.2.16" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "memchr" +version = "0.1.11" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "libc 0.2.16 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "petgraph" +version = "0.1.18" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "fixedbitset 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "regex" +version = "0.1.75" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "aho-corasick 0.5.2 (registry+https://github.com/rust-lang/crates.io-index)", + "memchr 0.1.11 (registry+https://github.com/rust-lang/crates.io-index)", + "regex-syntax 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)", + "thread_local 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)", + "utf8-ranges 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "regex-syntax" +version = "0.2.6" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "regex-syntax" +version = "0.3.5" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "rustc-serialize" +version = "0.3.19" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "strsim" +version = "0.5.1" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "term" +version = "0.4.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "kernel32-sys 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)", + "winapi 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "thread-id" +version = "2.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "kernel32-sys 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)", + "libc 0.2.16 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "thread_local" +version = "0.2.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "thread-id 2.0.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "unicode-xid" +version = "0.0.2" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "utf8-ranges" +version = "0.1.3" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "winapi" +version = "0.2.8" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "winapi-build" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[metadata] +"checksum aho-corasick 0.5.2 (registry+https://github.com/rust-lang/crates.io-index)" = "2b3fb52b09c1710b961acb35390d514be82e4ac96a9969a8e38565a29b878dc9" +"checksum atty 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "d0fd4c0631f06448cc45a6bbb3b710ebb7ff8ccb96a0800c994afe23a70d5df2" +"checksum bit-set 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "84527c7b0452f22545cc010e72d366a435561d2b28b978035550b3778c4d428d" +"checksum bit-vec 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)" = "5b97c2c8e8bbb4251754f559df8af22fb264853c7d009084a576cdf12565089d" +"checksum bitflags 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "8dead7461c1127cf637931a1e50934eb6eee8bff2f74433ac7909e9afcee04a3" +"checksum diff 0.1.9 (registry+https://github.com/rust-lang/crates.io-index)" = "e48977eec6d3b7707462c2dc2e1363ad91b5dd822cf942537ccdc2085dc87587" +"checksum docopt 0.6.83 (registry+https://github.com/rust-lang/crates.io-index)" = "fc42c6077823a361410c37d47c2535b73a190cbe10838dc4f400fe87c10c8c3b" +"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 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" +"checksum petgraph 0.1.18 (registry+https://github.com/rust-lang/crates.io-index)" = "bfd1de18b0a5f1777162e5b61aaf498032467d5409ab4ca6dbd03049f5708de1" +"checksum regex 0.1.75 (registry+https://github.com/rust-lang/crates.io-index)" = "f62414f9d3b0f53e827ac46d6f8ce2ff6a91afd724225a5986e54e81e170693c" +"checksum regex-syntax 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)" = "a21935ce5a4dfa48e3ded1aefbbe353fb9ab258b0d3fa0bd168bef00797b3dc7" +"checksum regex-syntax 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)" = "279401017ae31cf4e15344aa3f085d0e2e5c1e70067289ef906906fdbe92c8fd" +"checksum rustc-serialize 0.3.19 (registry+https://github.com/rust-lang/crates.io-index)" = "6159e4e6e559c81bd706afe9c8fd68f547d3e851ce12e76b1de7914bab61691b" +"checksum strsim 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)" = "50c069df92e4b01425a8bf3576d5d417943a6a7272fbabaf5bd80b1aaa76442e" +"checksum term 0.4.4 (registry+https://github.com/rust-lang/crates.io-index)" = "3deff8a2b3b6607d6d7cc32ac25c0b33709453ca9cceac006caac51e963cf94a" +"checksum thread-id 2.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "a9539db560102d1cef46b8b78ce737ff0bb64e7e18d35b2a5688f7d097d0ff03" +"checksum thread_local 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)" = "55dd963dbaeadc08aa7266bf7f91c3154a7805e32bb94b820b769d2ef3b4744d" +"checksum unicode-xid 0.0.2 (registry+https://github.com/rust-lang/crates.io-index)" = "f69506a2561962651710609304bbb961fa3da598c812f877975a82e48ee144f9" +"checksum utf8-ranges 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "a1ca13c08c41c9c3e04224ed9ff80461d97e121589ff27c753a16cb10830ae0f" +"checksum winapi 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)" = "167dc9d6949a9b857f3451275e911c3f44255842c1f7a76f33c55103a909087a" +"checksum winapi-build 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "2d315eee3b34aca4797b2da6b13ed88266e6d612562a0c46390af8299fc699bc" diff --git a/Cargo.toml b/Cargo.toml new file mode 100644 index 00000000..431d61dd --- /dev/null +++ b/Cargo.toml @@ -0,0 +1,14 @@ +[package] +name = "rusty-wam" +version = "0.1.0" +authors = ["Mark Thom"] + +build = "build.rs" + +[dependencies] + +[dependencies.lalrpop-util] +version = "0.12.0" + +[build-dependencies.lalrpop] +version = "0.12.0" \ No newline at end of file diff --git a/README.md b/README.md index be2c1a3b..e47e8e40 100644 --- a/README.md +++ b/README.md @@ -1,2 +1,43 @@ # rusty-wam -The Warren Abstract Machine in Rust. + +The beginnings of the Warren Abstract Machine in Rust, according to +the progression of languages in [Warren's Abstract Machine: A Tutorial +Reconstruction](http://wambook.sourceforge.net/wambook.pdf), ending in +pure Prolog. + +## Progress + +The language L0 is implemented as a simple REPL. It supports +unification on facts and queries without backtracking and clauses +without rules, in the familiar Prolog syntax. No data types apart from +atoms are currently supported. + +An example of the level of interaction currently supported is: + +`l0> p(Z, Z). +Program stored. +l0> ?- p(Z, Z). +yes +l0> ?- p(Z, z). +yes +l0> ?- p(Z, w). +yes +l0> ?- p(z, w). +no +l0> ?- p(w, w). +yes +l0> ?- p(Z, w). +yes +l0> ?- p(Z, h(Z, W), f(W)). +no +l0> p(Z, h(Z, W), f(W)). +Program stored. +l0> ?- p(z, h(z, z), f(w)). +no +l0> ?- p(z, h(z, w), f(w)). +yes +l0> ?- p(Z, h(z, W), f(w)). +yes +l0> ?- p(z, h(Z, w), f(w)). +yes +l0> quit` \ No newline at end of file diff --git a/build.rs b/build.rs new file mode 100644 index 00000000..23c7d3f8 --- /dev/null +++ b/build.rs @@ -0,0 +1,5 @@ +extern crate lalrpop; + +fn main() { + lalrpop::process_root().unwrap(); +} diff --git a/src/l0/ast.rs b/src/l0/ast.rs new file mode 100644 index 00000000..fddc3965 --- /dev/null +++ b/src/l0/ast.rs @@ -0,0 +1,63 @@ +use std::vec::{Vec}; + +pub type Var = String; + +pub type Atom = String; + +#[derive(Debug)] +pub enum TopLevel { + Fact(Term), + Query(Term) +} + +#[derive(Debug)] +pub enum Term { + Atom(Atom), + Clause(Atom, Vec>), + Var(Var) +} + +impl Term { + pub fn name(&self) -> &Atom { + match self { + &Term::Atom(ref atom) => atom, + &Term::Var(ref var) => var, + &Term::Clause(ref atom, _) => atom + } + } + + pub fn is_variable(&self) -> bool { + if let &Term::Var(_) = self { + return true; + } + + return false; + } +} + +#[derive(Clone)] +pub enum MachineInstruction { + GetStructure(Atom, usize, usize), + PutStructure(Atom, usize, usize), + SetVariable(usize), + SetValue(usize), + UnifyVariable(usize), + UnifyValue(usize) +} + +pub type Program = Vec; + +#[derive(Clone, Copy, PartialEq)] +pub enum Addr { + HeapCell(usize), + RegNum(usize) +} + +impl Addr { + pub fn heap_offset(&self) -> usize { + match self { + &Addr::HeapCell(hc) => hc, + &Addr::RegNum(reg) => reg + } + } +} diff --git a/src/l0/codegen.rs b/src/l0/codegen.rs new file mode 100644 index 00000000..8b00fa96 --- /dev/null +++ b/src/l0/codegen.rs @@ -0,0 +1,160 @@ +use l0::ast::{Atom, Term, MachineInstruction, Program, TopLevel, Var}; + +use std::collections::{HashMap, VecDeque}; +use std::fmt; +use std::vec::{Vec}; + +impl fmt::Display for MachineInstruction { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match self { + &MachineInstruction::GetStructure(ref a, ref s, ref r) => + write!(f, "get_structure {}/{}, X{}", a, s, r), + &MachineInstruction::PutStructure(ref a, ref s, ref r) => + write!(f, "put_structure {}/{}, X{}", a, s, r), + &MachineInstruction::SetVariable(ref r) => + write!(f, "set_variable X{}", r), + &MachineInstruction::SetValue(ref r) => + write!(f, "set_value X{}", r), + &MachineInstruction::UnifyVariable(ref r) => + write!(f, "unify_variable X{}", r), + &MachineInstruction::UnifyValue(ref r) => + write!(f, "unify_value X{}", r) + } + } +} + +enum IntTerm<'a> { + FinishedClause(usize, &'a Atom, &'a Vec>), + UnfinishedClause(usize, &'a Atom, &'a Vec>), + FinishedAtom(usize, &'a Atom) +} + +pub fn compile_query<'a>(t: &'a Term) -> Program +{ + let mut stack : Vec> = Vec::new(); + let mut variable_allocs : HashMap<&Var, (usize, bool)> = HashMap::new(); + let mut query : Program = Vec::new(); + + match t { + &Term::Clause(ref atom, ref terms) => { + stack.push(IntTerm::UnfinishedClause(1, atom, terms)); + variable_allocs.insert(atom, (1, true)); + }, + &Term::Atom(ref atom) => { + query.push(MachineInstruction::PutStructure(atom.clone(), 0, 1)); + return query; + }, + &Term::Var(_) => { + query.push(MachineInstruction::SetVariable(1)); + return query; + }, + }; + + while let Some(int_term) = stack.pop() { + match int_term { + IntTerm::UnfinishedClause(r, atom, terms) => { + stack.push(IntTerm::FinishedClause(r, atom, terms)); + + let mut counter : usize = r + 1; + + for t in terms { + if t.is_variable() && !variable_allocs.contains_key(t.name()) { + variable_allocs.insert(t.name(), (counter, false)); + } + + counter += 1; + } + + counter = r + terms.len(); + + for t in terms.iter().rev() { + let r = if t.is_variable() { + variable_allocs.get(t.name()).unwrap().0 + } else { + counter + }; + + match t.as_ref() { + &Term::Atom(ref atom) => + stack.push(IntTerm::FinishedAtom(r, atom)), + &Term::Clause(ref atom, ref terms) => + stack.push(IntTerm::UnfinishedClause(r, atom, terms)), + _ => {} + }; + + counter -= 1; + } + }, + IntTerm::FinishedAtom(r, atom) => + query.push(MachineInstruction::PutStructure(atom.clone(), 0, r)), + IntTerm::FinishedClause(r, atom, terms) => { + query.push(MachineInstruction::PutStructure(atom.clone(), terms.len(), r)); + + let mut counter : usize = r + 1; + + for t in terms { + if let &Term::Var(ref var) = t.as_ref() { + let &mut (reg, ref mut seen) = variable_allocs.get_mut(var).unwrap(); + + if !*seen { + query.push(MachineInstruction::SetVariable(reg)); + *seen = true; + } else { + query.push(MachineInstruction::SetValue(reg)); + } + } else { + query.push(MachineInstruction::SetValue(counter)); + } + + counter += 1; + } + } + }; + } + + query +} + +pub fn compile_fact<'a>(t: &'a Term) -> Program { + let mut reg : usize = 2; + let mut queue : VecDeque<(usize, &'a Term)> = VecDeque::new(); + let mut variable_allocs : HashMap<&Var, usize> = HashMap::new(); + let mut fact : Program = Vec::new(); + + queue.push_back((1, t)); + + while let Some(t) = queue.pop_front() { + match t { + (r, &Term::Clause(ref atom, ref terms)) => { + fact.push(MachineInstruction::GetStructure(atom.clone(), terms.len(), r)); + + let mut counter : usize = reg; + + for t in terms { + if t.is_variable() && !variable_allocs.contains_key(t.name()) { + variable_allocs.insert(t.name(), counter); + fact.push(MachineInstruction::UnifyVariable(counter)); + counter += 1; + } else if t.is_variable() { + let r = variable_allocs.get(t.name()).unwrap(); + fact.push(MachineInstruction::UnifyValue(*r)); + } else { + fact.push(MachineInstruction::UnifyVariable(counter)); + queue.push_back((counter, t)); + counter += 1; + } + } + + reg = counter; + }, + (r, &Term::Atom(ref atom)) => + fact.push(MachineInstruction::GetStructure(atom.clone(), 0, r)), + (r, &Term::Var(_)) => { + fact.push(MachineInstruction::UnifyVariable(r)); + return fact; + } + }; + } + + fact +} diff --git a/src/l0/l0_parser.lalrpop b/src/l0/l0_parser.lalrpop new file mode 100644 index 00000000..9743ade7 --- /dev/null +++ b/src/l0/l0_parser.lalrpop @@ -0,0 +1,30 @@ +use l0::ast::{Atom, Term, TopLevel, Var}; + +grammar; + +pub TopLevel: TopLevel = { + "?-" "." => TopLevel::Query(t), + "." => TopLevel::Fact(t), +}; + +Atom : Atom = { + r"[a-z][a-z0-9_]*" => <>.trim().to_string(), +}; + +Var : Var = { + r"[A-Z][a-z0-9_]*" => <>.trim().to_string(), +}; + +BoxedTerm : Box = { + => Box::new(t), +}; + +Term : Term = { + "(" ",")*> ")" => { + let mut ts = ts; + ts.push(t); + Term::Clause(a, ts) + }, + => Term::Atom(<>), + => Term::Var(<>), +}; \ No newline at end of file diff --git a/src/l0/l0_parser.rs b/src/l0/l0_parser.rs new file mode 100644 index 00000000..cd9c7803 --- /dev/null +++ b/src/l0/l0_parser.rs @@ -0,0 +1,1593 @@ +use l0::ast::{Atom, Term, TopLevel, Var}; +extern crate lalrpop_util as __lalrpop_util; + +mod __parse__TopLevel { + #![allow(non_snake_case, non_camel_case_types, unused_mut, unused_variables, unused_imports)] + + use l0::ast::{Atom, Term, TopLevel, Var}; + extern crate lalrpop_util as __lalrpop_util; + #[allow(dead_code)] + pub enum __Symbol<'input> { + Term_22_28_22(&'input str), + Term_22_29_22(&'input str), + Term_22_2c_22(&'input str), + Term_22_2e_22(&'input str), + Term_22_3f_2d_22(&'input str), + Termr_23_22_5bA_2dZ_5d_5ba_2dz0_2d9___5d_2a_22_23(&'input str), + Termr_23_22_5ba_2dz_5d_5ba_2dz0_2d9___5d_2a_22_23(&'input str), + Nt_28_3cBoxedTerm_3e_20_22_2c_22_29(Box), + Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2a(::std::vec::Vec>), + Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2b(::std::vec::Vec>), + NtAtom(Atom), + NtBoxedTerm(Box), + NtTerm(Term), + NtTopLevel(TopLevel), + NtVar(Var), + Nt____TopLevel(TopLevel), + } + const __ACTION: &'static [i32] = &[ + // State 0 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 6, // on "?-", goto 5 + 7, // on r#"[A-Z][a-z0-9_]*"#, goto 6 + 8, // on r#"[a-z][a-z0-9_]*"#, goto 7 + // State 1 + 9, // on "(", goto 8 + 0, // on ")", error + 0, // on ",", error + -10, // on ".", reduce `Term = Atom => ActionFn(7);` + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 2 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 10, // on ".", goto 9 + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 3 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 4 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + -11, // on ".", reduce `Term = Var => ActionFn(8);` + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 5 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + 7, // on r#"[A-Z][a-z0-9_]*"#, goto 6 + 8, // on r#"[a-z][a-z0-9_]*"#, goto 7 + // State 6 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + -14, // on ".", reduce `Var = r#"[A-Z][a-z0-9_]*"# => ActionFn(4);` + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 7 + -6, // on "(", reduce `Atom = r#"[a-z][a-z0-9_]*"# => ActionFn(3);` + 0, // on ")", error + 0, // on ",", error + -6, // on ".", reduce `Atom = r#"[a-z][a-z0-9_]*"# => ActionFn(3);` + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 8 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + 17, // on r#"[A-Z][a-z0-9_]*"#, goto 16 + 18, // on r#"[a-z][a-z0-9_]*"#, goto 17 + // State 9 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 10 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 19, // on ".", goto 18 + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 11 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + 17, // on r#"[A-Z][a-z0-9_]*"#, goto 16 + 18, // on r#"[a-z][a-z0-9_]*"#, goto 17 + // State 12 + 21, // on "(", goto 20 + -10, // on ")", reduce `Term = Atom => ActionFn(7);` + -10, // on ",", reduce `Term = Atom => ActionFn(7);` + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 13 + 0, // on "(", error + 22, // on ")", goto 21 + 23, // on ",", goto 22 + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 14 + 0, // on "(", error + -7, // on ")", reduce `BoxedTerm = Term => ActionFn(5);` + -7, // on ",", reduce `BoxedTerm = Term => ActionFn(5);` + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 15 + 0, // on "(", error + -11, // on ")", reduce `Term = Var => ActionFn(8);` + -11, // on ",", reduce `Term = Var => ActionFn(8);` + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 16 + 0, // on "(", error + -14, // on ")", reduce `Var = r#"[A-Z][a-z0-9_]*"# => ActionFn(4);` + -14, // on ",", reduce `Var = r#"[A-Z][a-z0-9_]*"# => ActionFn(4);` + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 17 + -6, // on "(", reduce `Atom = r#"[a-z][a-z0-9_]*"# => ActionFn(3);` + -6, // on ")", reduce `Atom = r#"[a-z][a-z0-9_]*"# => ActionFn(3);` + -6, // on ",", reduce `Atom = r#"[a-z][a-z0-9_]*"# => ActionFn(3);` + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 18 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 19 + 0, // on "(", error + 24, // on ")", goto 23 + 25, // on ",", goto 24 + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 20 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + 17, // on r#"[A-Z][a-z0-9_]*"#, goto 16 + 18, // on r#"[a-z][a-z0-9_]*"#, goto 17 + // State 21 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + -8, // on ".", reduce `Term = Atom, "(", BoxedTerm, ")" => ActionFn(16);` + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 22 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + -4, // on r#"[A-Z][a-z0-9_]*"#, reduce `( ",")+ = BoxedTerm, "," => ActionFn(14);` + -4, // on r#"[a-z][a-z0-9_]*"#, reduce `( ",")+ = BoxedTerm, "," => ActionFn(14);` + // State 23 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + -9, // on ".", reduce `Term = Atom, "(", ( ",")+, BoxedTerm, ")" => ActionFn(17);` + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 24 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + -5, // on r#"[A-Z][a-z0-9_]*"#, reduce `( ",")+ = ( ",")+, BoxedTerm, "," => ActionFn(15);` + -5, // on r#"[a-z][a-z0-9_]*"#, reduce `( ",")+ = ( ",")+, BoxedTerm, "," => ActionFn(15);` + // State 25 + 0, // on "(", error + 0, // on ")", error + 0, // on ",", error + 0, // on ".", error + 0, // on "?-", error + 17, // on r#"[A-Z][a-z0-9_]*"#, goto 16 + 18, // on r#"[a-z][a-z0-9_]*"#, goto 17 + // State 26 + 0, // on "(", error + 29, // on ")", goto 28 + 23, // on ",", goto 22 + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 27 + 0, // on "(", error + 30, // on ")", goto 29 + 25, // on ",", goto 24 + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 28 + 0, // on "(", error + -8, // on ")", reduce `Term = Atom, "(", BoxedTerm, ")" => ActionFn(16);` + -8, // on ",", reduce `Term = Atom, "(", BoxedTerm, ")" => ActionFn(16);` + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + // State 29 + 0, // on "(", error + -9, // on ")", reduce `Term = Atom, "(", ( ",")+, BoxedTerm, ")" => ActionFn(17);` + -9, // on ",", reduce `Term = Atom, "(", ( ",")+, BoxedTerm, ")" => ActionFn(17);` + 0, // on ".", error + 0, // on "?-", error + 0, // on r#"[A-Z][a-z0-9_]*"#, error + 0, // on r#"[a-z][a-z0-9_]*"#, error + ]; + const __EOF_ACTION: &'static [i32] = &[ + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + -15, // on EOF, reduce `__TopLevel = TopLevel => ActionFn(0);` + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + -13, // on EOF, reduce `TopLevel = Term, "." => ActionFn(2);` + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + -12, // on EOF, reduce `TopLevel = "?-", Term, "." => ActionFn(1);` + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + 0, // on EOF, error + ]; + const __GOTO: &'static [i32] = &[ + // State 0 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 2, // on Atom, goto 1 + 0, // on BoxedTerm, error + 3, // on Term, goto 2 + 4, // on TopLevel, goto 3 + 5, // on Var, goto 4 + 0, // on __TopLevel, error + // State 1 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 2 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 3 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 4 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 5 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 2, // on Atom, goto 1 + 0, // on BoxedTerm, error + 11, // on Term, goto 10 + 0, // on TopLevel, error + 5, // on Var, goto 4 + 0, // on __TopLevel, error + // State 6 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 7 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 8 + 0, // on ( ","), error + 0, // on ( ",")*, error + 12, // on ( ",")+, goto 11 + 13, // on Atom, goto 12 + 14, // on BoxedTerm, goto 13 + 15, // on Term, goto 14 + 0, // on TopLevel, error + 16, // on Var, goto 15 + 0, // on __TopLevel, error + // State 9 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 10 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 11 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 13, // on Atom, goto 12 + 20, // on BoxedTerm, goto 19 + 15, // on Term, goto 14 + 0, // on TopLevel, error + 16, // on Var, goto 15 + 0, // on __TopLevel, error + // State 12 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 13 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 14 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 15 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 16 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 17 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 18 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 19 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 20 + 0, // on ( ","), error + 0, // on ( ",")*, error + 26, // on ( ",")+, goto 25 + 13, // on Atom, goto 12 + 27, // on BoxedTerm, goto 26 + 15, // on Term, goto 14 + 0, // on TopLevel, error + 16, // on Var, goto 15 + 0, // on __TopLevel, error + // State 21 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 22 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 23 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 24 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 25 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 13, // on Atom, goto 12 + 28, // on BoxedTerm, goto 27 + 15, // on Term, goto 14 + 0, // on TopLevel, error + 16, // on Var, goto 15 + 0, // on __TopLevel, error + // State 26 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 27 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 28 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + // State 29 + 0, // on ( ","), error + 0, // on ( ",")*, error + 0, // on ( ",")+, error + 0, // on Atom, error + 0, // on BoxedTerm, error + 0, // on Term, error + 0, // on TopLevel, error + 0, // on Var, error + 0, // on __TopLevel, error + ]; + pub fn parse_TopLevel< + 'input, + >( + input: &'input str, + ) -> Result> + { + let mut __tokens = super::__intern_token::__Matcher::new(input); + let mut __states = vec![0_i32]; + let mut __symbols = vec![]; + '__shift: loop { + let __lookahead = match __tokens.next() { + Some(Ok(v)) => v, + None => break '__shift, + Some(Err(e)) => return Err(e), + }; + let __integer = match __lookahead { + (_, (0, _), _) if true => 0, + (_, (1, _), _) if true => 1, + (_, (2, _), _) if true => 2, + (_, (3, _), _) if true => 3, + (_, (4, _), _) if true => 4, + (_, (5, _), _) if true => 5, + (_, (6, _), _) if true => 6, + _ => { + return Err(__lalrpop_util::ParseError::UnrecognizedToken { + token: Some(__lookahead), + expected: vec![], + }); + } + }; + loop { + let __state = *__states.last().unwrap() as usize; + let __action = __ACTION[__state * 7 + __integer]; + if __action > 0 { + let __symbol = match __integer { + 0 => match __lookahead.1 { + (0, __tok0) => __Symbol::Term_22_28_22(__tok0), + _ => unreachable!(), + }, + 1 => match __lookahead.1 { + (1, __tok0) => __Symbol::Term_22_29_22(__tok0), + _ => unreachable!(), + }, + 2 => match __lookahead.1 { + (2, __tok0) => __Symbol::Term_22_2c_22(__tok0), + _ => unreachable!(), + }, + 3 => match __lookahead.1 { + (3, __tok0) => __Symbol::Term_22_2e_22(__tok0), + _ => unreachable!(), + }, + 4 => match __lookahead.1 { + (4, __tok0) => __Symbol::Term_22_3f_2d_22(__tok0), + _ => unreachable!(), + }, + 5 => match __lookahead.1 { + (5, __tok0) => __Symbol::Termr_23_22_5bA_2dZ_5d_5ba_2dz0_2d9___5d_2a_22_23(__tok0), + _ => unreachable!(), + }, + 6 => match __lookahead.1 { + (6, __tok0) => __Symbol::Termr_23_22_5ba_2dz_5d_5ba_2dz0_2d9___5d_2a_22_23(__tok0), + _ => unreachable!(), + }, + _ => unreachable!(), + }; + __states.push(__action - 1); + __symbols.push((__lookahead.0, __symbol, __lookahead.2)); + continue '__shift; + } else if __action < 0 { + if let Some(r) = __reduce(input, __action, Some(&__lookahead.0), &mut __states, &mut __symbols) { + return r; + } + } else { + return Err(__lalrpop_util::ParseError::UnrecognizedToken { + token: Some(__lookahead), + expected: vec![], + }); + } + } + } + loop { + let __state = *__states.last().unwrap() as usize; + let __action = __EOF_ACTION[__state]; + if __action < 0 { + if let Some(r) = __reduce(input, __action, None, &mut __states, &mut __symbols) { + return r; + } + } else { + return Err(__lalrpop_util::ParseError::UnrecognizedToken { + token: None, + expected: vec![], + }); + } + } + } + pub fn __reduce< + 'input, + >( + input: &'input str, + __action: i32, + __lookahead_start: Option<&usize>, + __states: &mut ::std::vec::Vec, + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)>, + ) -> Option>> + { + let __nonterminal = match -__action { + 1 => { + // ( ",") = BoxedTerm, "," => ActionFn(11); + let __sym1 = __pop_Term_22_2c_22(__symbols); + let __sym0 = __pop_NtBoxedTerm(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym1.2.clone(); + let __nt = super::__action11(input, __sym0, __sym1); + let __states_len = __states.len(); + __states.truncate(__states_len - 2); + __symbols.push((__start, __Symbol::Nt_28_3cBoxedTerm_3e_20_22_2c_22_29(__nt), __end)); + 0 + } + 2 => { + // ( ",")* = => ActionFn(9); + let __start = __symbols.last().map(|s| s.2.clone()).unwrap_or_default(); + let __end = __lookahead_start.cloned().unwrap_or_else(|| __start.clone()); + let __nt = super::__action9(input, &__start, &__end); + let __states_len = __states.len(); + __states.truncate(__states_len - 0); + __symbols.push((__start, __Symbol::Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2a(__nt), __end)); + 1 + } + 3 => { + // ( ",")* = ( ",")+ => ActionFn(10); + let __sym0 = __pop_Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2b(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action10(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2a(__nt), __end)); + 1 + } + 4 => { + // ( ",")+ = BoxedTerm, "," => ActionFn(14); + let __sym1 = __pop_Term_22_2c_22(__symbols); + let __sym0 = __pop_NtBoxedTerm(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym1.2.clone(); + let __nt = super::__action14(input, __sym0, __sym1); + let __states_len = __states.len(); + __states.truncate(__states_len - 2); + __symbols.push((__start, __Symbol::Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2b(__nt), __end)); + 2 + } + 5 => { + // ( ",")+ = ( ",")+, BoxedTerm, "," => ActionFn(15); + let __sym2 = __pop_Term_22_2c_22(__symbols); + let __sym1 = __pop_NtBoxedTerm(__symbols); + let __sym0 = __pop_Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2b(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym2.2.clone(); + let __nt = super::__action15(input, __sym0, __sym1, __sym2); + let __states_len = __states.len(); + __states.truncate(__states_len - 3); + __symbols.push((__start, __Symbol::Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2b(__nt), __end)); + 2 + } + 6 => { + // Atom = r#"[a-z][a-z0-9_]*"# => ActionFn(3); + let __sym0 = __pop_Termr_23_22_5ba_2dz_5d_5ba_2dz0_2d9___5d_2a_22_23(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action3(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtAtom(__nt), __end)); + 3 + } + 7 => { + // BoxedTerm = Term => ActionFn(5); + let __sym0 = __pop_NtTerm(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action5(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtBoxedTerm(__nt), __end)); + 4 + } + 8 => { + // Term = Atom, "(", BoxedTerm, ")" => ActionFn(16); + let __sym3 = __pop_Term_22_29_22(__symbols); + let __sym2 = __pop_NtBoxedTerm(__symbols); + let __sym1 = __pop_Term_22_28_22(__symbols); + let __sym0 = __pop_NtAtom(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym3.2.clone(); + let __nt = super::__action16(input, __sym0, __sym1, __sym2, __sym3); + let __states_len = __states.len(); + __states.truncate(__states_len - 4); + __symbols.push((__start, __Symbol::NtTerm(__nt), __end)); + 5 + } + 9 => { + // Term = Atom, "(", ( ",")+, BoxedTerm, ")" => ActionFn(17); + let __sym4 = __pop_Term_22_29_22(__symbols); + let __sym3 = __pop_NtBoxedTerm(__symbols); + let __sym2 = __pop_Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2b(__symbols); + let __sym1 = __pop_Term_22_28_22(__symbols); + let __sym0 = __pop_NtAtom(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym4.2.clone(); + let __nt = super::__action17(input, __sym0, __sym1, __sym2, __sym3, __sym4); + let __states_len = __states.len(); + __states.truncate(__states_len - 5); + __symbols.push((__start, __Symbol::NtTerm(__nt), __end)); + 5 + } + 10 => { + // Term = Atom => ActionFn(7); + let __sym0 = __pop_NtAtom(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action7(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtTerm(__nt), __end)); + 5 + } + 11 => { + // Term = Var => ActionFn(8); + let __sym0 = __pop_NtVar(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action8(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtTerm(__nt), __end)); + 5 + } + 12 => { + // TopLevel = "?-", Term, "." => ActionFn(1); + let __sym2 = __pop_Term_22_2e_22(__symbols); + let __sym1 = __pop_NtTerm(__symbols); + let __sym0 = __pop_Term_22_3f_2d_22(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym2.2.clone(); + let __nt = super::__action1(input, __sym0, __sym1, __sym2); + let __states_len = __states.len(); + __states.truncate(__states_len - 3); + __symbols.push((__start, __Symbol::NtTopLevel(__nt), __end)); + 6 + } + 13 => { + // TopLevel = Term, "." => ActionFn(2); + let __sym1 = __pop_Term_22_2e_22(__symbols); + let __sym0 = __pop_NtTerm(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym1.2.clone(); + let __nt = super::__action2(input, __sym0, __sym1); + let __states_len = __states.len(); + __states.truncate(__states_len - 2); + __symbols.push((__start, __Symbol::NtTopLevel(__nt), __end)); + 6 + } + 14 => { + // Var = r#"[A-Z][a-z0-9_]*"# => ActionFn(4); + let __sym0 = __pop_Termr_23_22_5bA_2dZ_5d_5ba_2dz0_2d9___5d_2a_22_23(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action4(input, __sym0); + let __states_len = __states.len(); + __states.truncate(__states_len - 1); + __symbols.push((__start, __Symbol::NtVar(__nt), __end)); + 7 + } + 15 => { + // __TopLevel = TopLevel => ActionFn(0); + let __sym0 = __pop_NtTopLevel(__symbols); + let __start = __sym0.0.clone(); + let __end = __sym0.2.clone(); + let __nt = super::__action0(input, __sym0); + return Some(Ok(__nt)); + } + _ => panic!("invalid action code {}", __action) + }; + let __state = *__states.last().unwrap() as usize; + let __next_state = __GOTO[__state * 9 + __nonterminal] - 1; + __states.push(__next_state); + None + } + fn __pop_Term_22_28_22< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Term_22_28_22(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Term_22_29_22< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Term_22_29_22(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Term_22_2c_22< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Term_22_2c_22(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Term_22_2e_22< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Term_22_2e_22(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Term_22_3f_2d_22< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Term_22_3f_2d_22(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Termr_23_22_5bA_2dZ_5d_5ba_2dz0_2d9___5d_2a_22_23< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Termr_23_22_5bA_2dZ_5d_5ba_2dz0_2d9___5d_2a_22_23(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Termr_23_22_5ba_2dz_5d_5ba_2dz0_2d9___5d_2a_22_23< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, &'input str, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Termr_23_22_5ba_2dz_5d_5ba_2dz0_2d9___5d_2a_22_23(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Nt_28_3cBoxedTerm_3e_20_22_2c_22_29< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, Box, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Nt_28_3cBoxedTerm_3e_20_22_2c_22_29(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2a< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, ::std::vec::Vec>, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2a(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2b< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, ::std::vec::Vec>, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Nt_28_3cBoxedTerm_3e_20_22_2c_22_29_2b(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_NtAtom< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, Atom, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::NtAtom(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_NtBoxedTerm< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, Box, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::NtBoxedTerm(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_NtTerm< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, Term, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::NtTerm(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_NtTopLevel< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, TopLevel, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::NtTopLevel(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_NtVar< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, Var, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::NtVar(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } + fn __pop_Nt____TopLevel< + 'input, + >( + __symbols: &mut ::std::vec::Vec<(usize,__Symbol<'input>,usize)> + ) -> (usize, TopLevel, usize) { + match __symbols.pop().unwrap() { + (__l, __Symbol::Nt____TopLevel(__v), __r) => (__l, __v, __r), + _ => panic!("symbol type mismatch") + } + } +} +pub use self::__parse__TopLevel::parse_TopLevel; +mod __intern_token { + extern crate lalrpop_util as __lalrpop_util; + pub struct __Matcher<'input> { + text: &'input str, + consumed: usize, + } + + fn __tokenize(text: &str) -> Option<(usize, usize)> { + let mut __chars = text.char_indices(); + let mut __current_match: Option<(usize, usize)> = None; + let mut __current_state: usize = 0; + loop { + match __current_state { + 0 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 40 => /* '(' */ { + __current_match = Some((0, __index + 1)); + __current_state = 1; + continue; + } + 41 => /* ')' */ { + __current_match = Some((1, __index + 1)); + __current_state = 2; + continue; + } + 44 => /* ',' */ { + __current_match = Some((2, __index + 1)); + __current_state = 3; + continue; + } + 46 => /* '.' */ { + __current_match = Some((3, __index + 1)); + __current_state = 4; + continue; + } + 63 => /* '?' */ { + __current_state = 5; + continue; + } + 65 ... 90 => { + __current_match = Some((5, __index + __ch.len_utf8())); + __current_state = 6; + continue; + } + 97 ... 122 => { + __current_match = Some((6, __index + __ch.len_utf8())); + __current_state = 7; + continue; + } + _ => { + return __current_match; + } + } + } + 1 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + _ => { + return __current_match; + } + } + } + 2 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + _ => { + return __current_match; + } + } + } + 3 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + _ => { + return __current_match; + } + } + } + 4 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + _ => { + return __current_match; + } + } + } + 5 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 45 => /* '-' */ { + __current_match = Some((4, __index + 1)); + __current_state = 9; + continue; + } + _ => { + return __current_match; + } + } + } + 6 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 48 ... 57 => { + __current_match = Some((5, __index + __ch.len_utf8())); + __current_state = 10; + continue; + } + 95 => /* '_' */ { + __current_match = Some((5, __index + 1)); + __current_state = 10; + continue; + } + 97 ... 122 => { + __current_match = Some((5, __index + __ch.len_utf8())); + __current_state = 10; + continue; + } + _ => { + return __current_match; + } + } + } + 7 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 48 ... 57 => { + __current_match = Some((6, __index + __ch.len_utf8())); + __current_state = 11; + continue; + } + 95 => /* '_' */ { + __current_match = Some((6, __index + 1)); + __current_state = 11; + continue; + } + 97 ... 122 => { + __current_match = Some((6, __index + __ch.len_utf8())); + __current_state = 11; + continue; + } + _ => { + return __current_match; + } + } + } + 8 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + _ => { + return __current_match; + } + } + } + 9 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + _ => { + return __current_match; + } + } + } + 10 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 48 ... 57 => { + __current_match = Some((5, __index + __ch.len_utf8())); + __current_state = 10; + continue; + } + 95 => /* '_' */ { + __current_match = Some((5, __index + 1)); + __current_state = 10; + continue; + } + 97 ... 122 => { + __current_match = Some((5, __index + __ch.len_utf8())); + __current_state = 10; + continue; + } + _ => { + return __current_match; + } + } + } + 11 => { + let (__index, __ch) = match __chars.next() { Some(p) => p, None => return __current_match }; + match __ch as u32 { + 48 ... 57 => { + __current_match = Some((6, __index + __ch.len_utf8())); + __current_state = 11; + continue; + } + 95 => /* '_' */ { + __current_match = Some((6, __index + 1)); + __current_state = 11; + continue; + } + 97 ... 122 => { + __current_match = Some((6, __index + __ch.len_utf8())); + __current_state = 11; + continue; + } + _ => { + return __current_match; + } + } + } + _ => { panic!("invalid state {}", __current_state); } + } + } + } + + impl<'input> __Matcher<'input> { + pub fn new(s: &'input str) -> __Matcher<'input> { + __Matcher { text: s, consumed: 0 } + } + } + + impl<'input> Iterator for __Matcher<'input> { + type Item = Result<(usize, (usize, &'input str), usize), __lalrpop_util::ParseError>; + + fn next(&mut self) -> Option { + let __text = self.text.trim_left(); + let __whitespace = self.text.len() - __text.len(); + let __start_offset = self.consumed + __whitespace; + if __text.is_empty() { + self.text = __text; + self.consumed = __start_offset; + None + } else { + match __tokenize(__text) { + Some((__index, __length)) => { + let __result = &__text[..__length]; + let __remaining = &__text[__length..]; + let __end_offset = __start_offset + __length; + self.text = __remaining; + self.consumed = __end_offset; + Some(Ok((__start_offset, (__index, __result), __end_offset))) + } + None => { + Some(Err(__lalrpop_util::ParseError::InvalidToken { location: __start_offset })) + } + } + } + } + } +} + +#[allow(unused_variables)] +pub fn __action0< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, TopLevel, usize), +) -> TopLevel +{ + (__0) +} + +#[allow(unused_variables)] +pub fn __action1< + 'input, +>( + input: &'input str, + (_, _, _): (usize, &'input str, usize), + (_, t, _): (usize, Term, usize), + (_, _, _): (usize, &'input str, usize), +) -> TopLevel +{ + TopLevel::Query(t) +} + +#[allow(unused_variables)] +pub fn __action2< + 'input, +>( + input: &'input str, + (_, t, _): (usize, Term, usize), + (_, _, _): (usize, &'input str, usize), +) -> TopLevel +{ + TopLevel::Fact(t) +} + +#[allow(unused_variables)] +pub fn __action3< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, &'input str, usize), +) -> Atom +{ + __0.trim().to_string() +} + +#[allow(unused_variables)] +pub fn __action4< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, &'input str, usize), +) -> Var +{ + __0.trim().to_string() +} + +#[allow(unused_variables)] +pub fn __action5< + 'input, +>( + input: &'input str, + (_, t, _): (usize, Term, usize), +) -> Box +{ + Box::new(t) +} + +#[allow(unused_variables)] +pub fn __action6< + 'input, +>( + input: &'input str, + (_, a, _): (usize, Atom, usize), + (_, _, _): (usize, &'input str, usize), + (_, ts, _): (usize, ::std::vec::Vec>, usize), + (_, t, _): (usize, Box, usize), + (_, _, _): (usize, &'input str, usize), +) -> Term +{ + { + let mut ts = ts; + ts.push(t); + Term::Clause(a, ts) + } +} + +#[allow(unused_variables)] +pub fn __action7< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Atom, usize), +) -> Term +{ + Term::Atom(__0) +} + +#[allow(unused_variables)] +pub fn __action8< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Var, usize), +) -> Term +{ + Term::Var(__0) +} + +#[allow(unused_variables)] +pub fn __action9< + 'input, +>( + input: &'input str, + __lookbehind: &usize, + __lookahead: &usize, +) -> ::std::vec::Vec> +{ + vec![] +} + +#[allow(unused_variables)] +pub fn __action10< + 'input, +>( + input: &'input str, + (_, v, _): (usize, ::std::vec::Vec>, usize), +) -> ::std::vec::Vec> +{ + v +} + +#[allow(unused_variables)] +pub fn __action11< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Box, usize), + (_, _, _): (usize, &'input str, usize), +) -> Box +{ + (__0) +} + +#[allow(unused_variables)] +pub fn __action12< + 'input, +>( + input: &'input str, + (_, __0, _): (usize, Box, usize), +) -> ::std::vec::Vec> +{ + vec![__0] +} + +#[allow(unused_variables)] +pub fn __action13< + 'input, +>( + input: &'input str, + (_, v, _): (usize, ::std::vec::Vec>, usize), + (_, e, _): (usize, Box, usize), +) -> ::std::vec::Vec> +{ + { let mut v = v; v.push(e); v } +} + +#[allow(unused_variables)] +pub fn __action14< + 'input, +>( + input: &'input str, + __0: (usize, Box, usize), + __1: (usize, &'input str, usize), +) -> ::std::vec::Vec> +{ + let __start0 = __0.0.clone(); + let __end0 = __1.2.clone(); + let __temp0 = __action11( + input, + __0, + __1, + ); + let __temp0 = (__start0, __temp0, __end0); + __action12( + input, + __temp0, + ) +} + +#[allow(unused_variables)] +pub fn __action15< + 'input, +>( + input: &'input str, + __0: (usize, ::std::vec::Vec>, usize), + __1: (usize, Box, usize), + __2: (usize, &'input str, usize), +) -> ::std::vec::Vec> +{ + let __start0 = __1.0.clone(); + let __end0 = __2.2.clone(); + let __temp0 = __action11( + input, + __1, + __2, + ); + let __temp0 = (__start0, __temp0, __end0); + __action13( + input, + __0, + __temp0, + ) +} + +#[allow(unused_variables)] +pub fn __action16< + 'input, +>( + input: &'input str, + __0: (usize, Atom, usize), + __1: (usize, &'input str, usize), + __2: (usize, Box, usize), + __3: (usize, &'input str, usize), +) -> Term +{ + let __start0 = __1.2.clone(); + let __end0 = __2.0.clone(); + let __temp0 = __action9( + input, + &__start0, + &__end0, + ); + let __temp0 = (__start0, __temp0, __end0); + __action6( + input, + __0, + __1, + __temp0, + __2, + __3, + ) +} + +#[allow(unused_variables)] +pub fn __action17< + 'input, +>( + input: &'input str, + __0: (usize, Atom, usize), + __1: (usize, &'input str, usize), + __2: (usize, ::std::vec::Vec>, usize), + __3: (usize, Box, usize), + __4: (usize, &'input str, usize), +) -> Term +{ + let __start0 = __2.0.clone(); + let __end0 = __2.2.clone(); + let __temp0 = __action10( + input, + __2, + ); + let __temp0 = (__start0, __temp0, __end0); + __action6( + input, + __0, + __1, + __temp0, + __3, + __4, + ) +} + +pub trait __ToTriple<'input, > { + type Error; + fn to_triple(value: Self) -> Result<(usize,(usize, &'input str),usize),Self::Error>; +} + +impl<'input, > __ToTriple<'input, > for (usize, (usize, &'input str), usize) { + type Error = (); + fn to_triple(value: Self) -> Result<(usize,(usize, &'input str),usize),()> { + Ok(value) + } +} +impl<'input, > __ToTriple<'input, > for Result<(usize, (usize, &'input str), usize),()> { + type Error = (); + fn to_triple(value: Self) -> Result<(usize,(usize, &'input str),usize),()> { + value + } +} diff --git a/src/l0/machine.rs b/src/l0/machine.rs new file mode 100644 index 00000000..8018a6b0 --- /dev/null +++ b/src/l0/machine.rs @@ -0,0 +1,240 @@ +use l0::ast::{Addr, Atom, MachineInstruction, Program, Term, TopLevel, Var}; + +use std::fmt; +use std::vec::{Vec}; + +#[derive(Clone)] +enum HeapCell { + NamedStr(usize, Atom), + Ref(usize), // these offsets are always in reference to cells on the Heap! + Str(usize), +} + +#[derive(Clone, Copy)] +enum MachineMode { + Read, + Write +} + +type Heap = Vec; + +type Registers = Vec; + +pub struct MachineState { + h : usize, + s : usize, + pub fail : bool, + heap : Heap, + mode : MachineMode, + pub program : Option, + registers : Registers +} + +impl MachineState { + pub fn new() -> MachineState { + MachineState { h : 0, + s : 0, + fail : false, + heap : Vec::with_capacity(256), + mode : MachineMode::Write, + program : None, + registers : vec![HeapCell::Ref(0); 33] } + } + + fn lookup(&self, a: Addr) -> &HeapCell { + match a { + Addr::HeapCell(hc) => &self.heap[hc], + Addr::RegNum(reg) => &self.registers[reg] + } + } + + fn deref(&self, a: Addr) -> Addr { + let mut a = a; + + loop { + if let &HeapCell::Ref(value) = self.lookup(a) { + if value != a.heap_offset() { + a = Addr::HeapCell(value); + continue; + } else { + return a; + } + } + + return a; + }; + } + + fn bind(&mut self, a: Addr, val: Addr) { + match a { + Addr::RegNum(reg) => self.registers[reg] = HeapCell::Ref(val.heap_offset()), + Addr::HeapCell(hc) => self.heap[hc] = HeapCell::Ref(val.heap_offset()), + }; + } + + fn unify(&mut self, a1: Addr, a2: Addr) { + let mut pdl : Vec = vec![a1, a2]; + + self.fail = false; + + while !(pdl.is_empty() || self.fail) { + let d1 = self.deref(pdl.pop().unwrap()); + let d2 = self.deref(pdl.pop().unwrap()); + + if d1 != d2 { + match (self.lookup(d1), self.lookup(d2)) { + (&HeapCell::Ref(_), _) | (_, &HeapCell::Ref(_)) => + self.bind(d1, d2), + (&HeapCell::Str(a1), &HeapCell::Str(a2)) => { + let r1 = &self.heap[a1]; + let r2 = &self.heap[a2]; + + if let &HeapCell::NamedStr(n1, ref f1) = r1 { + if let &HeapCell::NamedStr(n2, ref f2) = r2 { + if n1 == n2 && *f1 == *f2 { + for i in 1 .. n1 { + pdl.push(Addr::HeapCell(a1 + i)); + pdl.push(Addr::HeapCell(a2 + i)); + } + + continue; + } + } + } + + self.fail = true; + }, + _ => self.fail = true, + }; + } + } + } + + pub fn execute(&mut self, instr: MachineInstruction) { + match instr { + MachineInstruction::GetStructure(name, arity, reg) => { + let addr = self.deref(Addr::RegNum(reg)); + + match self.lookup(addr) { + &HeapCell::Str(a) => { + let result = &self.heap[a]; + + if let &HeapCell::NamedStr(named_arity, ref named_str) = result { + if arity == named_arity && name == *named_str { + self.s = a + 1; + self.mode = MachineMode::Read; + } else { + self.fail = true; + } + } + }, + &HeapCell::Ref(reg) => { + self.heap.push(HeapCell::Str(self.h + 1)); + self.heap.push(HeapCell::NamedStr(arity, name)); + + let h = self.h; + + self.bind(Addr::RegNum(reg), Addr::HeapCell(h)); + + self.h += 2; + self.mode = MachineMode::Write; + }, + _ => { + self.fail = true; + } + }; + }, + MachineInstruction::PutStructure(name, arity, reg) => { + self.heap.push(HeapCell::Str(self.h + 1)); + self.heap.push(HeapCell::NamedStr(arity, name)); + + self.registers[reg] = self.heap[self.h].clone(); + + self.h += 2; + }, + MachineInstruction::SetVariable(reg) => { + self.heap.push(HeapCell::Ref(self.h)); + self.registers[reg] = self.heap[self.h].clone(); + + self.h += 1; + }, + MachineInstruction::SetValue(reg) => { + self.heap.push(self.registers[reg].clone()); + self.h += 1; + }, + MachineInstruction::UnifyVariable(reg) => { + if self.s < self.h { + match self.mode { + MachineMode::Read => self.registers[reg] = self.heap[self.s].clone(), + MachineMode::Write => { + self.heap.push(HeapCell::Ref(self.h)); + self.registers[reg] = self.heap[self.h].clone(); + self.h += 1; + } + }; + + self.s += 1; + } else { + self.fail = true; + } + }, + MachineInstruction::UnifyValue(reg) => { + if self.s < self.h { + let s = self.s; + + match self.mode { + MachineMode::Read => self.unify(Addr::RegNum(reg), Addr::HeapCell(s)), + MachineMode::Write => { + self.heap.push(self.registers[reg].clone()); + self.h += 1; + } + }; + + self.s += 1; + } else { + self.fail = true; + } + } + } + } + + pub fn reset_heap(&mut self) { + let program = self.program.take(); + + *self = MachineState::new(); + self.program = program; + } + + pub fn dump_registers_and_heap(&self) { + let mut c = 0; + + let printer = |contents, c| { + match contents { + &HeapCell::NamedStr(ref arity, ref atom) => { + println!("{} = NAME({}, {})", c, arity, atom); + }, + &HeapCell::Ref(hc) => { + println!("{} = REF({})", c, hc); + }, + &HeapCell::Str(hc) => { + println!("{} = STR({})", c, hc); + } + }; + }; + + for contents in &self.registers { + print!("X"); + printer(contents, c); + c += 1; + } + + println!(""); + + c = 0; + + for contents in &self.heap { + printer(contents, c); + c += 1; + } + } +} diff --git a/src/l0/mod.rs b/src/l0/mod.rs new file mode 100644 index 00000000..933bebe5 --- /dev/null +++ b/src/l0/mod.rs @@ -0,0 +1,4 @@ +pub mod ast; +pub mod l0_parser; +pub mod codegen; +pub mod machine; diff --git a/src/main.rs b/src/main.rs new file mode 100644 index 00000000..6282a8e0 --- /dev/null +++ b/src/main.rs @@ -0,0 +1,76 @@ +mod l0; + +use l0::ast::{Atom, Program, Term, TopLevel, Var}; +use l0::codegen::{compile_fact, compile_query}; +use l0::machine::{MachineState}; + +use std::io::{self, Write}; + +fn print_instructions(program : Program) { + for instruction in program { + println!("{:}", instruction); + } +} + +fn l0_repl<'a>() { + let mut ms = MachineState::new(); + + loop { + print!("l0> "); + io::stdout().flush(); + + let mut buffer = String::new(); + io::stdin().read_line(&mut buffer).unwrap(); + + let result = l0::l0_parser::parse_TopLevel(&*buffer); + + if &*buffer == "quit\n" { + break; + } else if &*buffer == "clear\n" { + ms = MachineState::new(); + } + + match result { + Ok(TopLevel::Fact(fact)) => { + let program = compile_fact(&fact); + + ms = MachineState::new(); + ms.program = Some(program); + + println!("Program stored."); + }, + Ok(TopLevel::Query(query)) => { + if let Some(program) = ms.program.clone().take() { + let query = compile_query(&query); + + for instruction in query { + ms.execute(instruction); + } + + for instruction in program { + ms.execute(instruction); + + if ms.fail { + break; + } + } + + if ms.fail { + println!("no"); + } else { + println!("yes"); + } + + ms.reset_heap(); + } else { + println!("No program to speak of."); + } + }, + Err(_) => println!("Grammatical error of some kind!"), + }; + } +} + +fn main() { + l0_repl(); +} -- 2.54.0