From a6304d3f96a4f051ba3cc30606ec0432ef10361d Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Sat, 29 Apr 2017 16:50:53 -0600 Subject: [PATCH] prep for debray allocation --- Cargo.lock | 2 +- Cargo.toml | 2 +- src/main.rs | 2 +- src/prolog/ast.rs | 39 +- src/prolog/codegen.rs | 814 +++++----------------------------- src/prolog/indexing.rs | 247 +++++++++++ src/prolog/io.rs | 8 +- src/prolog/iterators.rs | 120 ++++- src/prolog/machine.rs | 5 +- src/prolog/mod.rs | 4 + src/prolog/naive_allocator.rs | 163 +++++++ src/prolog/targets.rs | 119 +++++ 12 files changed, 815 insertions(+), 710 deletions(-) create mode 100644 src/prolog/indexing.rs create mode 100644 src/prolog/naive_allocator.rs create mode 100644 src/prolog/targets.rs diff --git a/Cargo.lock b/Cargo.lock index 0a0e3a0b..3d66e845 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -1,6 +1,6 @@ [root] name = "rusty-wam" -version = "0.5.12" +version = "0.5.7" dependencies = [ "lalrpop 0.12.5 (registry+https://github.com/rust-lang/crates.io-index)", "lalrpop-util 0.12.5 (registry+https://github.com/rust-lang/crates.io-index)", diff --git a/Cargo.toml b/Cargo.toml index ad5d42ae..a750dbc3 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -1,6 +1,6 @@ [package] name = "rusty-wam" -version = "0.5.12" +version = "0.5.7" authors = ["Mark Thom"] build = "build.rs" diff --git a/src/main.rs b/src/main.rs index 1be7e779..828fe381 100644 --- a/src/main.rs +++ b/src/main.rs @@ -200,7 +200,7 @@ mod tests { // test shallow cuts. submit(&mut wam, "memberchk(X, [X|_]) :- !. - memberchk(X, [_|Xs]) :- !, memberchk(X, Xs)."); + memberchk(X, [_|Xs]) :- memberchk(X, Xs)."); assert_eq!(submit(&mut wam, "?- memberchk(X, [a,b,c]).").failed_query(), false); assert_eq!(submit(&mut wam, "?- memberchk([X,X], [a,b,c,[d,e],[d,d]]).").failed_query(), false); diff --git a/src/prolog/ast.rs b/src/prolog/ast.rs index c7ec6207..ee81b3f0 100644 --- a/src/prolog/ast.rs +++ b/src/prolog/ast.rs @@ -7,6 +7,11 @@ pub type Var = String; pub type Atom = String; +#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord)] +pub enum GenContext { + Head, Mid(usize), Last(usize) // Mid/Last: chunk_num +} + pub enum PredicateClause { Fact(Term), Rule(Rule) @@ -90,13 +95,6 @@ impl VarReg { pub fn is_temp(self) -> bool { !self.norm().is_perm() } - - pub fn root_register(self) -> usize { - match self { - VarReg::ArgAndNorm(_, root) => root, - VarReg::Norm(root) => root.reg_num() - } - } } impl Default for VarReg { @@ -124,7 +122,7 @@ pub enum TermOrCut { Term(Term) } -impl TermOrCut { +impl TermOrCut { pub fn arity(&self) -> usize { match self { &TermOrCut::Term(ref term) => term.arity(), @@ -147,6 +145,7 @@ impl Rule { } } +#[derive(Clone, Copy)] pub enum TermRef<'a> { AnonVar(Level), Cons(Level, &'a Cell, &'a Term, &'a Term), @@ -155,6 +154,22 @@ pub enum TermRef<'a> { Var(Level, &'a Cell, &'a Var) } +impl<'a> TermRef<'a> { + pub fn level(self) -> Level { + match self { + TermRef::AnonVar(lvl) + | TermRef::Cons(lvl, _, _, _) + | TermRef::Constant(lvl, _, _) + | TermRef::Clause(lvl, _, _, _) + | TermRef::Var(lvl, _, _) => lvl + } + } +} + +pub enum TermOrCutRef<'a> { + Cut, Term(&'a Term) +} + pub enum ChoiceInstruction { RetryMeElse(usize), TrustMe, @@ -410,6 +425,14 @@ impl Term { } } + pub fn is_callable(&self) -> bool { + match self { + &Term::Clause(_, _, _) | &Term::Constant(_, Constant::Atom(_)) => + true, + _ => false + } + } + pub fn subterms(&self) -> usize { match self { &Term::Clause(_, _, ref terms) => terms.len(), diff --git a/src/prolog/codegen.rs b/src/prolog/codegen.rs index b4ded35c..aaf95b71 100644 --- a/src/prolog/codegen.rs +++ b/src/prolog/codegen.rs @@ -1,512 +1,26 @@ use prolog::ast::*; -use prolog::iterators::{FactIterator, QueryIterator}; +use prolog::fixtures::*; +use prolog::indexing::*; +use prolog::iterators::*; +use prolog::naive_allocator::*; +use prolog::targets::*; use std::cell::Cell; -use std::cmp::max; -use std::collections::{HashMap, VecDeque}; -use std::hash::Hash; +use std::collections::HashMap; use std::vec::Vec; -trait CompilationTarget<'a> { - type Iterator : Iterator>; - - fn iter(&'a Term) -> Self::Iterator; - - fn to_constant(Level, Constant, RegType) -> Self; - fn to_list(Level, RegType) -> Self; - fn to_structure(Level, Atom, usize, RegType) -> Self; - fn to_void(usize) -> Self; - - fn constant_subterm(Constant) -> Self; - - fn argument_to_variable(RegType, usize) -> Self; - fn argument_to_value(RegType, usize) -> Self; - - fn subterm_to_variable(RegType) -> Self; - fn subterm_to_value(RegType) -> Self; - - fn clause_arg_to_instr(RegType) -> Self; -} - -impl<'a> CompilationTarget<'a> for FactInstruction { - type Iterator = FactIterator<'a>; - - fn iter(term: &'a Term) -> Self::Iterator { - term.breadth_first_iter() - } - - fn to_constant(lvl: Level, constant: Constant, reg: RegType) -> Self { - FactInstruction::GetConstant(lvl, constant, reg) - } - - fn to_structure(lvl: Level, atom: Atom, arity: usize, reg: RegType) -> Self { - FactInstruction::GetStructure(lvl, atom, arity, reg) - } - - fn to_list(lvl: Level, reg: RegType) -> Self { - FactInstruction::GetList(lvl, reg) - } - - fn to_void(subterms: usize) -> Self { - FactInstruction::UnifyVoid(subterms) - } - - fn constant_subterm(constant: Constant) -> Self { - FactInstruction::UnifyConstant(constant) - } - - fn argument_to_variable(arg: RegType, val: usize) -> Self { - FactInstruction::GetVariable(arg, val) - } - - fn argument_to_value(arg: RegType, val: usize) -> Self { - FactInstruction::GetValue(arg, val) - } - - fn subterm_to_variable(val: RegType) -> Self { - FactInstruction::UnifyVariable(val) - } - - fn subterm_to_value(val: RegType) -> Self { - FactInstruction::UnifyValue(val) - } - - fn clause_arg_to_instr(val: RegType) -> Self { - FactInstruction::UnifyVariable(val) - } -} - -impl<'a> CompilationTarget<'a> for QueryInstruction { - type Iterator = QueryIterator<'a>; - - fn iter(term: &'a Term) -> Self::Iterator { - term.post_order_iter() - } - - fn to_structure(lvl: Level, atom: Atom, arity: usize, reg: RegType) -> Self { - QueryInstruction::PutStructure(lvl, atom, arity, reg) - } - - fn to_constant(lvl: Level, constant: Constant, reg: RegType) -> Self { - QueryInstruction::PutConstant(lvl, constant, reg) - } - - fn to_list(lvl: Level, reg: RegType) -> Self { - QueryInstruction::PutList(lvl, reg) - } - - fn to_void(subterms: usize) -> Self { - QueryInstruction::SetVoid(subterms) - } - - fn constant_subterm(constant: Constant) -> Self { - QueryInstruction::SetConstant(constant) - } - - fn argument_to_variable(arg: RegType, val: usize) -> Self { - QueryInstruction::PutVariable(arg, val) - } - - fn argument_to_value(arg: RegType, val: usize) -> Self { - QueryInstruction::PutValue(arg, val) - } - - fn subterm_to_variable(val: RegType) -> Self { - QueryInstruction::SetVariable(val) - } - - fn subterm_to_value(val: RegType) -> Self { - QueryInstruction::SetValue(val) - } - - fn clause_arg_to_instr(val: RegType) -> Self { - QueryInstruction::SetValue(val) - } -} - -struct TermMarker<'a> { - bindings: HashMap<&'a Var, VarReg>, - arg_c: usize, - temp_c: usize -} - -impl<'a> TermMarker<'a> { - fn new() -> TermMarker<'a> { - TermMarker { bindings: HashMap::new(), - arg_c: 1, - temp_c: 1 } - } - - fn reset(&mut self) { - self.bindings.clear(); - } - - 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 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::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 temp = self.temp_c; - self.temp_c += 1; - RegType::Temp(temp) - } else { - reg - }; - - let reg = match lvl { - Level::Deep => VarReg::Norm(inner_reg), - Level::Shallow => { - let reg = VarReg::ArgAndNorm(inner_reg, self.arg_c); - self.arg_c += 1; - reg - } - }; - - self.insert(var, reg); - reg - } - - fn mark_anon_var(&mut self, lvl: Level) -> VarReg { - let inner_reg = { - let temp = self.temp_c; - self.temp_c += 1; - RegType::Temp(temp) - }; - - match lvl { - Level::Deep => VarReg::Norm(inner_reg), - Level::Shallow => { - let reg = VarReg::ArgAndNorm(inner_reg, self.arg_c); - self.arg_c += 1; - reg - } - } - } - - fn advance_arg(&mut self) { - self.arg_c += 1; - } - - fn advance_at_head(&mut self, term: &'a Term) { - self.arg_c = 1; - self.temp_c = max(term.subterms() + 1, self.temp_c); - } - - fn advance(&mut self, term: &'a Term) { - self.arg_c = 1; - self.temp_c = term.subterms() + 1; - } -} - -#[derive(Clone, Copy)] -enum IntIndex { - External(usize), Fail, Internal(usize) -} - -struct CodeOffsets { - constants: HashMap, - lists: ThirdLevelIndex, - structures: HashMap<(Atom, usize), ThirdLevelIndex> -} - -impl CodeOffsets { - fn new() -> Self { - CodeOffsets { - constants: HashMap::new(), - lists: Vec::new(), - structures: HashMap::new() - } - } - - fn cap_choice_seq_with_trust(prelude: &mut ThirdLevelIndex) { - prelude.last_mut().map(|instr| { - match instr { - &mut IndexedChoiceInstruction::Retry(i) => - *instr = IndexedChoiceInstruction::Trust(i), - _ => {} - }; - }); - } - - fn add_index(is_first_index: bool, index: usize) -> IndexedChoiceInstruction { - if is_first_index { - IndexedChoiceInstruction::Try(index) - } else { - IndexedChoiceInstruction::Retry(index) - } - } - - fn index_term(&mut self, first_arg: &Term, index: usize) { - match first_arg { - &Term::Clause(_, ref name, ref terms) => { - let code = self.structures.entry((name.clone(), terms.len())) - .or_insert(Vec::new()); - - let is_initial_index = code.is_empty(); - code.push(Self::add_index(is_initial_index, index)); - }, - &Term::Cons(_, _, _) => { - let is_initial_index = self.lists.is_empty(); - self.lists.push(Self::add_index(is_initial_index, index)); - }, - &Term::Constant(_, ref constant) => { - let code = self.constants.entry(constant.clone()) - .or_insert(Vec::new()); - - let is_initial_index = code.is_empty(); - code.push(Self::add_index(is_initial_index, index)); - }, - _ => {} - }; - } - - fn second_level_index(indices: HashMap, - prelude: &mut CodeDeque) - -> HashMap - where Index: Eq + Hash - { - let mut index_locs = HashMap::new(); - - for (key, mut code) in indices.into_iter() { - if code.len() > 1 { - index_locs.insert(key, IntIndex::Internal(prelude.len())); - Self::cap_choice_seq_with_trust(&mut code); - prelude.extend(code.into_iter().map(|code| Line::from(code))); - } else { - code.first().map(|i| { - index_locs.insert(key, IntIndex::External(i.offset())); - }); - } - } - - index_locs - } - - fn no_indices(&self) -> bool { - let no_constants = self.constants.is_empty(); - let no_structures = self.structures.is_empty(); - let no_lists = self.lists.is_empty(); - - no_constants && no_structures && no_lists - } - - fn flatten_index(index: HashMap, len: usize) - -> HashMap - where Index: Eq + Hash - { - let mut flattened_index = HashMap::new(); - - for (key, int_index) in index.into_iter() { - match int_index { - IntIndex::External(offset) => { - flattened_index.insert(key, offset + len + 1); - }, - IntIndex::Internal(offset) => { - flattened_index.insert(key, offset + 1); - }, - _ => {} - }; - } - - flattened_index - } - - fn switch_on_constant(con_ind: HashMap, - prelude: &mut CodeDeque) - -> IntIndex - { - let con_ind = Self::second_level_index(con_ind, prelude); - - if con_ind.len() > 1 { - let index = Self::flatten_index(con_ind, prelude.len()); - let instr = IndexingInstruction::SwitchOnConstant(index.len(), index); - - prelude.push_front(Line::from(instr)); - - IntIndex::Internal(1) - } else { - con_ind.values().next() - .map(|i| *i) - .unwrap_or(IntIndex::Fail) - } - } - - fn switch_on_list(mut lists: ThirdLevelIndex, prelude: &mut CodeDeque) -> IntIndex - { - if lists.len() > 1 { - Self::cap_choice_seq_with_trust(&mut lists); - prelude.extend(lists.into_iter().map(|i| Line::from(i))); - IntIndex::Internal(0) - } else { - lists.first() - .map(|i| IntIndex::External(i.offset())) - .unwrap_or(IntIndex::Fail) - } - } - - fn switch_on_structure(str_ind: HashMap<(Atom, usize), ThirdLevelIndex>, - prelude: &mut CodeDeque) - -> IntIndex - { - let str_ind = Self::second_level_index(str_ind, prelude); - - if str_ind.len() > 1 { - let index = Self::flatten_index(str_ind, prelude.len()); - let instr = IndexingInstruction::SwitchOnStructure(index.len(), index); - - prelude.push_front(Line::from(instr)); - - IntIndex::Internal(1) - } else { - str_ind.values().next() - .map(|i| *i) - .unwrap_or(IntIndex::Fail) - } - } - - - fn switch_on_str_offset_from(str_loc: IntIndex, prelude_len: usize, con_loc: IntIndex) - -> usize - { - match str_loc { - IntIndex::External(o) => o + prelude_len + 1, - IntIndex::Fail => 0, - IntIndex::Internal(_) => match con_loc { - IntIndex::Internal(_) => 2, - _ => 1 - } - } - } - - fn switch_on_con_offset_from(con_loc: IntIndex, prelude_len: usize) -> usize - { - match con_loc { - IntIndex::External(offset) => offset + prelude_len + 1, - IntIndex::Fail => 0, - IntIndex::Internal(offset) => offset, - } - } - - fn switch_on_lst_offset_from(lst_loc: IntIndex, prelude_len: usize, lst_offset: usize) - -> usize - { - match lst_loc { - IntIndex::External(o) => o + prelude_len + 1, - IntIndex::Fail => 0, - IntIndex::Internal(_) => prelude_len - lst_offset + 1 - } - } - - fn add_indices(self, code: &mut Code, mut code_body: Code) - { - if self.no_indices() { - *code = code_body; - return; - } - - let mut prelude = VecDeque::new(); - - let lst_loc = Self::switch_on_list(self.lists, &mut prelude); - let lst_offset = prelude.len(); - - let str_loc = Self::switch_on_structure(self.structures, &mut prelude); - let con_loc = Self::switch_on_constant(self.constants, &mut prelude); - - let prelude_length = prelude.len(); - - for (index, line) in prelude.iter_mut().enumerate() { - match line { - &mut Line::IndexedChoice(IndexedChoiceInstruction::Try(ref mut i)) - | &mut Line::IndexedChoice(IndexedChoiceInstruction::Retry(ref mut i)) - | &mut Line::IndexedChoice(IndexedChoiceInstruction::Trust(ref mut i)) => - *i += prelude_length - index, - _ => {} - } - } - - let str_loc = Self::switch_on_str_offset_from(str_loc, prelude.len(), con_loc); - let con_loc = Self::switch_on_con_offset_from(con_loc, prelude.len()); - let lst_loc = Self::switch_on_lst_offset_from(lst_loc, prelude.len(), lst_offset); - - let switch_instr = IndexingInstruction::SwitchOnTerm(prelude.len() + 1, - con_loc, - lst_loc, - str_loc); - - prelude.push_front(Line::from(switch_instr)); - - *code = Vec::from(prelude); - code.append(&mut code_body); - } -} - -#[derive(Copy, Clone)] -enum VarStatus { - New, Old, Permanent(usize) -} - pub struct CodeGenerator<'a> { marker: TermMarker<'a>, var_count: HashMap<&'a Var, usize> } -type VariableFixture<'a> = (VarStatus, Vec<&'a Cell>); -type VariableFixtures<'a> = HashMap<&'a Var, VariableFixture<'a>>; - impl<'a> CodeGenerator<'a> { pub fn new() -> Self { CodeGenerator { marker: TermMarker::new(), var_count: HashMap::new() } } - pub fn vars(&self) -> &HashMap<&Var, VarReg> { + pub fn vars(&self) -> &HashMap<&Var, VarData> { &self.marker.bindings } @@ -588,46 +102,49 @@ impl<'a> CodeGenerator<'a> { Target::constant_subterm(constant.clone()) } - fn anon_var_term(&mut self, lvl: Level) -> Target + fn anon_var_term(&mut self, lvl: Level, target: &mut Vec) where Target: CompilationTarget<'a> { let reg = self.marker.mark_anon_var(lvl); - match reg { + let instr = match reg { VarReg::ArgAndNorm(arg, norm) => Target::argument_to_variable(arg, norm), VarReg::Norm(norm) => Target::subterm_to_variable(norm) - } + }; + + target.push(instr); } fn var_term(&mut self, lvl: Level, cell: &'a Cell, - var: &'a Var) - -> Target + var: &'a Var, + _: GenContext, + target: &mut Vec) where Target: CompilationTarget<'a> { - if !self.marker.contains_var(var) { + if !self.marker.marked_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::ArgAndNorm(arg, norm) => // if arg.reg_num() != norm => + target.push(Target::argument_to_variable(arg, norm)), VarReg::Norm(norm) => - Target::subterm_to_variable(norm) - } + target.push(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::ArgAndNorm(arg, norm) => // if arg.reg_num() != norm => + target.push(Target::argument_to_value(arg, norm)), VarReg::Norm(norm) => - Target::subterm_to_value(norm) - } + target.push(Target::subterm_to_value(norm)), + }; } } @@ -638,27 +155,33 @@ impl<'a> CodeGenerator<'a> { Target::clause_arg_to_instr(cell.get()) } - fn subterm_to_instr(&mut self, subterm: &'a Term) -> Target + fn subterm_to_instr(&mut self, + subterm: &'a Term, + term_loc: GenContext, + target: &mut Vec) where Target: CompilationTarget<'a> { match subterm { &Term::AnonVar => - self.anon_var_term(Level::Deep), + self.anon_var_term(Level::Deep, target), &Term::Cons(ref cell, _, _) | &Term::Clause(ref cell, _, _) => - self.non_var_subterm(cell), + target.push(self.non_var_subterm(cell)), &Term::Constant(_, ref constant) => - self.constant_subterm(constant), + target.push(self.constant_subterm(constant)), &Term::Var(ref cell, ref var) => - self.var_term(Level::Deep, cell, var) - } + self.var_term(Level::Deep, cell, var, term_loc, target) + }; } - fn compile_target(&mut self, term: &'a Term, has_exposed_vars: bool) + fn compile_target(&mut self, + term: &'a Term, + term_loc: GenContext, + has_exposed_vars: bool) -> Vec where Target: CompilationTarget<'a> { let iter = Target::iter(term); - let mut target = Vec::new(); + let mut target = Vec::::new(); for term in iter { match term { @@ -673,26 +196,25 @@ impl<'a> CodeGenerator<'a> { } for subterm in terms { - target.push(self.subterm_to_instr(subterm.as_ref())); + self.subterm_to_instr(subterm.as_ref(), term_loc, &mut target); } }, TermRef::Cons(lvl, cell, head, tail) => { target.push(self.to_list(lvl, cell)); - target.push(self.subterm_to_instr(head)); - target.push(self.subterm_to_instr(tail)); + self.subterm_to_instr(head, term_loc, &mut target); + self.subterm_to_instr(tail, term_loc, &mut target); }, TermRef::Constant(lvl @ Level::Shallow, cell, constant) => target.push(self.to_constant(lvl, cell, constant)), - TermRef::AnonVar(lvl @ Level::Shallow) => { + TermRef::AnonVar(lvl @ Level::Shallow) => if has_exposed_vars { - target.push(self.anon_var_term(lvl)); + self.anon_var_term(lvl, &mut target); } else { self.marker.advance_arg(); - } - }, + }, TermRef::Var(lvl @ Level::Shallow, ref cell, ref var) => - target.push(self.var_term(lvl, cell, var)), + self.var_term(lvl, cell, var, term_loc, &mut target), _ => {} }; } @@ -700,92 +222,34 @@ impl<'a> CodeGenerator<'a> { target } - fn mark_vars_in_term(iter: Iter, vs: &mut VariableFixtures<'a>, i: usize) - where Iter : Iterator> + fn collect_var_data(iter: ChunkedIterator<'a>) -> (VariableFixtures, bool) { - for term in iter { - if let TermRef::Var(_, reg_cell, var) = term { - let mut status = vs.entry(var) - .or_insert((VarStatus::New, Vec::new())); + let mut vs = VariableFixtures::new(); + let has_deep_cut = iter.contains_deep_cut(); + let has_head = iter.at_head(); - status.1.push(reg_cell); + for (chunk_num, (last_term_arity, terms)) in iter.enumerate() { + for (i, term_or_cut_ref) in terms.iter().enumerate() { + let term_loc = if chunk_num == 0 && i == 0 && has_head { + GenContext::Head + } else if i < terms.len() - 1 { + GenContext::Mid(chunk_num) + } else { + GenContext::Last(chunk_num) + }; - match status.0 { - VarStatus::Old => - status.0 = VarStatus::Permanent(i), - VarStatus::Permanent(_) => - status.0 = VarStatus::Permanent(i), + match term_or_cut_ref { + &TermOrCutRef::Term(term) => + vs.mark_vars_in_chunk(term, last_term_arity, chunk_num, term_loc), _ => {} }; } } - for &mut (ref mut term_status, _) in vs.values_mut() { - match *term_status { - VarStatus::New => - *term_status = VarStatus::Old, - _ => {} - } - } - } + vs.populate_restricting_sets(); + vs.set_perm_vals(has_deep_cut); - fn set_perm_vals(vs: &VariableFixtures, offset: usize) { - let mut values_vec : Vec<_> = vs.values() - .map(|ref v| (v.0, &v.1)) - .collect(); - - values_vec.sort_by_key(|ref v| { - match v.0 { - VarStatus::Permanent(i) => i, - _ => usize::min_value() - } - }); - - for (i, v) in values_vec.into_iter().rev().enumerate() { - if let VarStatus::Permanent(_) = v.0 { - for cell in v.1 { - cell.set(VarReg::Norm(RegType::Perm(i + 1 + offset))); - } - } else { - break; - } - } - } - - fn mark_perm_vars(rule: &'a Rule) -> (VariableFixtures, bool) - { - let &Rule { head: (ref p0, ref p1), ref clauses } = rule; - let mut vs = HashMap::new(); - - match p1 { - &TermOrCut::Cut => { - let iter = p0.breadth_first_iter(); - Self::mark_vars_in_term(iter, &mut vs, 0); - }, - &TermOrCut::Term(ref p1) => { - let iter = p0.breadth_first_iter().chain(p1.breadth_first_iter()); - Self::mark_vars_in_term(iter, &mut vs, 0); - } - } - - let mut deep_cuts = false; - - for (i, term) in clauses.iter().enumerate() { - match term { - &TermOrCut::Cut => { - deep_cuts = true; - }, - &TermOrCut::Term(ref term) => { - Self::mark_vars_in_term(term.breadth_first_iter(), - &mut vs, - i + 1); - } - } - } - - Self::set_perm_vals(&vs, deep_cuts as usize); - - (vs, deep_cuts) + (vs, has_deep_cut) } fn add_conditional_call(compiled_query: &mut Code, term: &Term, pvs: usize) @@ -803,21 +267,8 @@ impl<'a> CodeGenerator<'a> { } } - fn vars_above_threshold(vs: &VariableFixtures, index: usize) -> usize { - let mut var_count = 0; - - for &(var_status, _) in vs.values() { - if let VarStatus::Permanent(i) = var_status { - if i > index { - var_count += 1; - } - } - } - - var_count - } - - fn lco(body: &mut Code, rule: &'a Rule) -> usize { + fn lco(body: &mut Code, rule: &'a Rule) -> usize + { let last_arity = rule.last_clause().arity(); let mut dealloc_index = body.len() - 1; @@ -834,58 +285,17 @@ impl<'a> CodeGenerator<'a> { dealloc_index } - fn mark_unsafe_query_vars(head: &Term, vs: &VariableFixtures, query: &mut CompiledQuery) - { - let mut unsafe_vars = HashMap::new(); - - for &(_, ref cb) in vs.values() { - if !cb.is_empty() { - let index = cb.first().unwrap().get().norm(); - unsafe_vars.insert(index, false); - } - } - - for term_ref in head.breadth_first_iter() { - match term_ref { - TermRef::Var(_, cell, _) => { - unsafe_vars.remove(&cell.get().norm()); - }, - _ => {} - }; - } - - for query_instr in query.iter_mut() { - match query_instr { - &mut QueryInstruction::PutValue(RegType::Perm(i), arg) => - if let Some(found) = unsafe_vars.get_mut(&RegType::Perm(i)) { - if !*found { - *found = true; - *query_instr = QueryInstruction::PutUnsafeValue(i, arg); - } - }, - &mut QueryInstruction::SetVariable(reg) - | &mut QueryInstruction::PutVariable(reg, _) => - if let Some(found) = unsafe_vars.get_mut(®) { - *found = true; - }, - &mut QueryInstruction::SetValue(reg) => - if let Some(found) = unsafe_vars.get_mut(®) { - if !*found { - *found = true; - *query_instr = QueryInstruction::SetLocalValue(reg); - } - }, - _ => {} - }; - } - } - pub fn compile_rule(&mut self, rule: &'a Rule) -> Code { - let (vs, deep_cuts) = Self::mark_perm_vars(&rule); + let iter = ChunkedIterator::from_rule(rule); + let (mut vs, deep_cuts) = Self::collect_var_data(iter); + vs = self.marker.drain_var_data(vs); + let &Rule { head: (ref p0, ref p1), ref clauses } = rule; - let perm_vars = Self::vars_above_threshold(&vs, 0) + deep_cuts as usize; + self.marker.advance(p0); + + let perm_vars = vs.vars_above_threshold(0) + deep_cuts as usize; let mut body = Vec::new(); if clauses.len() > 0 { @@ -907,10 +317,8 @@ impl<'a> CodeGenerator<'a> { } }; - self.marker.advance(p0); - if p0.is_clause() { - body.push(Line::Fact(self.compile_target(p0, false))); + body.push(Line::Fact(self.compile_target(p0, GenContext::Head, false))); } match p1 { @@ -927,30 +335,43 @@ impl<'a> CodeGenerator<'a> { self.marker.advance_at_head(p1); if p1.is_clause() { - body.push(Line::Query(self.compile_target(p1, false))); + let term_loc = if p1.is_callable() { + GenContext::Last(0) + } else { + GenContext::Mid(0) + }; + + body.push(Line::Query(self.compile_target(p1, term_loc, false))); } Self::add_conditional_call(&mut body, p1, perm_vars); } }; - body = clauses.iter().enumerate() - .map(|(i, term)| { - match term { - &TermOrCut::Cut if i + 1 < clauses.len() => + let iter = ChunkedIterator::from_term_sequence(clauses); + + for (chunk_num, (_, terms)) in iter.enumerate() { + self.marker.reset_contents(); + + for (i, term) in terms.iter().enumerate() { + let mut body_appendage = match term { + &TermOrCutRef::Cut if i + 1 < terms.len() => vec![Line::Cut(CutInstruction::Cut(Terminal::Non))], - &TermOrCut::Cut => + &TermOrCutRef::Cut => vec![Line::Cut(CutInstruction::Cut(Terminal::Terminal))], - &TermOrCut::Term(ref term) => { - let num_vars = Self::vars_above_threshold(&vs, i + 1); - self.compile_internal_query(term, num_vars) + &TermOrCutRef::Term(term) if i + 1 < terms.len() => { + let num_vars = vs.vars_above_threshold(i + 1); + self.compile_internal_query(term, GenContext::Mid(chunk_num), num_vars) + }, + &TermOrCutRef::Term(term) => { + let num_vars = vs.vars_above_threshold(i + 1); + self.compile_internal_query(term, GenContext::Last(chunk_num), num_vars) } - } - }) - .fold(body, |mut body, ref mut cqs| { - body.append(cqs); - body - }); + }; + + body.append(&mut body_appendage); + } + } if clauses.len() > 0 { let mut index = body.len() - 1; @@ -960,7 +381,7 @@ impl<'a> CodeGenerator<'a> { } if let &mut Line::Query(ref mut query) = &mut body[index] { - Self::mark_unsafe_query_vars(p0, &vs, query); + vs.mark_unsafe_query_vars(p0, query); } } @@ -973,12 +394,12 @@ impl<'a> CodeGenerator<'a> { body } - fn mark_unsafe_fact_vars(fact: &mut CompiledFact, bindings: &HashMap<&Var, VarReg>) + fn mark_unsafe_fact_vars(&self, fact: &mut CompiledFact) { let mut unsafe_vars = HashMap::new(); - for var_reg in bindings.values() { - unsafe_vars.insert(var_reg.norm(), false); + for var_status in self.marker.bindings.values() { + unsafe_vars.insert(var_status.as_reg_type(), false); } for fact_instr in fact.iter_mut() { @@ -1002,14 +423,18 @@ impl<'a> CodeGenerator<'a> { pub fn compile_fact(&mut self, term: &'a Term) -> Code { - self.marker.advance(term); + let iter = ChunkedIterator::from_term(term, true); + let (vs, _) = Self::collect_var_data(iter); + self.marker.drain_var_data(vs); + self.update_var_count(term.breadth_first_iter()); + self.marker.advance(term); let mut code = Vec::new(); if term.is_clause() { - let mut compiled_fact = self.compile_target(term, false); - Self::mark_unsafe_fact_vars(&mut compiled_fact, self.vars()); + let mut compiled_fact = self.compile_target(term, GenContext::Head, false); + self.mark_unsafe_fact_vars(&mut compiled_fact); code.push(Line::Fact(compiled_fact)); } @@ -1019,7 +444,7 @@ impl<'a> CodeGenerator<'a> { code } - fn compile_internal_query(&mut self, term: &'a Term, index: usize) -> Code + fn compile_internal_query(&mut self, term: &'a Term, term_loc: GenContext, index: usize) -> Code { self.marker.advance(term); self.update_var_count(term.breadth_first_iter()); @@ -1027,7 +452,7 @@ impl<'a> CodeGenerator<'a> { let mut code = Vec::new(); if term.is_clause() { - let compiled_query = Line::Query(self.compile_target(term, false)); + let compiled_query = Line::Query(self.compile_target(term, term_loc, false)); code.push(compiled_query); } @@ -1038,14 +463,19 @@ impl<'a> CodeGenerator<'a> { pub fn compile_query(&mut self, term: &'a Term) -> Code { + let iter = ChunkedIterator::from_term(term, true); + let (vs, _) = Self::collect_var_data(iter); + + self.marker.drain_var_data(vs); + self.marker.advance(term); self.update_var_count(term.breadth_first_iter()); let mut code = Vec::new(); if term.is_clause() { - let compiled_query = Line::Query(self.compile_target(term, false)); - code.push(compiled_query); + let compiled_query = self.compile_target(term, GenContext::Last(0), false); + code.push(Line::Query(compiled_query)); } Self::add_conditional_call(&mut code, term, 0); diff --git a/src/prolog/indexing.rs b/src/prolog/indexing.rs new file mode 100644 index 00000000..dc06f47a --- /dev/null +++ b/src/prolog/indexing.rs @@ -0,0 +1,247 @@ +use prolog::ast::*; + +use std::collections::{HashMap, VecDeque}; +use std::hash::Hash; + +#[derive(Clone, Copy)] +enum IntIndex { + External(usize), Fail, Internal(usize) +} + +pub struct CodeOffsets { + pub constants: HashMap, + pub lists: ThirdLevelIndex, + pub structures: HashMap<(Atom, usize), ThirdLevelIndex> +} + +impl CodeOffsets { + pub fn new() -> Self { + CodeOffsets { + constants: HashMap::new(), + lists: Vec::new(), + structures: HashMap::new() + } + } + + fn cap_choice_seq_with_trust(prelude: &mut ThirdLevelIndex) { + prelude.last_mut().map(|instr| { + match instr { + &mut IndexedChoiceInstruction::Retry(i) => + *instr = IndexedChoiceInstruction::Trust(i), + _ => {} + }; + }); + } + + fn add_index(is_first_index: bool, index: usize) -> IndexedChoiceInstruction { + if is_first_index { + IndexedChoiceInstruction::Try(index) + } else { + IndexedChoiceInstruction::Retry(index) + } + } + + pub fn index_term(&mut self, first_arg: &Term, index: usize) + { + match first_arg { + &Term::Clause(_, ref name, ref terms) => { + let code = self.structures.entry((name.clone(), terms.len())) + .or_insert(Vec::new()); + + let is_initial_index = code.is_empty(); + code.push(Self::add_index(is_initial_index, index)); + }, + &Term::Cons(_, _, _) => { + let is_initial_index = self.lists.is_empty(); + self.lists.push(Self::add_index(is_initial_index, index)); + }, + &Term::Constant(_, ref constant) => { + let code = self.constants.entry(constant.clone()) + .or_insert(Vec::new()); + + let is_initial_index = code.is_empty(); + code.push(Self::add_index(is_initial_index, index)); + }, + _ => {} + }; + } + + fn second_level_index(indices: HashMap, + prelude: &mut CodeDeque) + -> HashMap + where Index: Eq + Hash + { + let mut index_locs = HashMap::new(); + + for (key, mut code) in indices.into_iter() { + if code.len() > 1 { + index_locs.insert(key, IntIndex::Internal(prelude.len())); + Self::cap_choice_seq_with_trust(&mut code); + prelude.extend(code.into_iter().map(|code| Line::from(code))); + } else { + code.first().map(|i| { + index_locs.insert(key, IntIndex::External(i.offset())); + }); + } + } + + index_locs + } + + fn no_indices(&self) -> bool { + let no_constants = self.constants.is_empty(); + let no_structures = self.structures.is_empty(); + let no_lists = self.lists.is_empty(); + + no_constants && no_structures && no_lists + } + + fn flatten_index(index: HashMap, len: usize) + -> HashMap + where Index: Eq + Hash + { + let mut flattened_index = HashMap::new(); + + for (key, int_index) in index.into_iter() { + match int_index { + IntIndex::External(offset) => { + flattened_index.insert(key, offset + len + 1); + }, + IntIndex::Internal(offset) => { + flattened_index.insert(key, offset + 1); + }, + _ => {} + }; + } + + flattened_index + } + + fn switch_on_constant(con_ind: HashMap, + prelude: &mut CodeDeque) + -> IntIndex + { + let con_ind = Self::second_level_index(con_ind, prelude); + + if con_ind.len() > 1 { + let index = Self::flatten_index(con_ind, prelude.len()); + let instr = IndexingInstruction::SwitchOnConstant(index.len(), index); + + prelude.push_front(Line::from(instr)); + + IntIndex::Internal(1) + } else { + con_ind.values().next() + .map(|i| *i) + .unwrap_or(IntIndex::Fail) + } + } + + fn switch_on_list(mut lists: ThirdLevelIndex, prelude: &mut CodeDeque) -> IntIndex + { + if lists.len() > 1 { + Self::cap_choice_seq_with_trust(&mut lists); + prelude.extend(lists.into_iter().map(|i| Line::from(i))); + IntIndex::Internal(0) + } else { + lists.first() + .map(|i| IntIndex::External(i.offset())) + .unwrap_or(IntIndex::Fail) + } + } + + fn switch_on_structure(str_ind: HashMap<(Atom, usize), ThirdLevelIndex>, + prelude: &mut CodeDeque) + -> IntIndex + { + let str_ind = Self::second_level_index(str_ind, prelude); + + if str_ind.len() > 1 { + let index = Self::flatten_index(str_ind, prelude.len()); + let instr = IndexingInstruction::SwitchOnStructure(index.len(), index); + + prelude.push_front(Line::from(instr)); + + IntIndex::Internal(1) + } else { + str_ind.values().next() + .map(|i| *i) + .unwrap_or(IntIndex::Fail) + } + } + + + fn switch_on_str_offset_from(str_loc: IntIndex, prelude_len: usize, con_loc: IntIndex) + -> usize + { + match str_loc { + IntIndex::External(o) => o + prelude_len + 1, + IntIndex::Fail => 0, + IntIndex::Internal(_) => match con_loc { + IntIndex::Internal(_) => 2, + _ => 1 + } + } + } + + fn switch_on_con_offset_from(con_loc: IntIndex, prelude_len: usize) -> usize + { + match con_loc { + IntIndex::External(offset) => offset + prelude_len + 1, + IntIndex::Fail => 0, + IntIndex::Internal(offset) => offset, + } + } + + fn switch_on_lst_offset_from(lst_loc: IntIndex, prelude_len: usize, lst_offset: usize) + -> usize + { + match lst_loc { + IntIndex::External(o) => o + prelude_len + 1, + IntIndex::Fail => 0, + IntIndex::Internal(_) => prelude_len - lst_offset + 1 + } + } + + pub fn add_indices(self, code: &mut Code, mut code_body: Code) + { + if self.no_indices() { + *code = code_body; + return; + } + + let mut prelude = VecDeque::new(); + + let lst_loc = Self::switch_on_list(self.lists, &mut prelude); + let lst_offset = prelude.len(); + + let str_loc = Self::switch_on_structure(self.structures, &mut prelude); + let con_loc = Self::switch_on_constant(self.constants, &mut prelude); + + let prelude_length = prelude.len(); + + for (index, line) in prelude.iter_mut().enumerate() { + match line { + &mut Line::IndexedChoice(IndexedChoiceInstruction::Try(ref mut i)) + | &mut Line::IndexedChoice(IndexedChoiceInstruction::Retry(ref mut i)) + | &mut Line::IndexedChoice(IndexedChoiceInstruction::Trust(ref mut i)) => + *i += prelude_length - index, + _ => {} + } + } + + let str_loc = Self::switch_on_str_offset_from(str_loc, prelude.len(), con_loc); + let con_loc = Self::switch_on_con_offset_from(con_loc, prelude.len()); + let lst_loc = Self::switch_on_lst_offset_from(lst_loc, prelude.len(), lst_offset); + + let switch_instr = IndexingInstruction::SwitchOnTerm(prelude.len() + 1, + con_loc, + lst_loc, + str_loc); + + prelude.push_front(Line::from(switch_instr)); + + *code = Vec::from(prelude); + code.append(&mut code_body); + } +} diff --git a/src/prolog/io.rs b/src/prolog/io.rs index 5644e799..5c0727db 100644 --- a/src/prolog/io.rs +++ b/src/prolog/io.rs @@ -121,11 +121,11 @@ impl fmt::Display for IndexedChoiceInstruction { impl fmt::Display for ChoiceInstruction { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - match self { + match self { &ChoiceInstruction::TryMeElse(offset) => write!(f, "try_me_else {}", offset), &ChoiceInstruction::RetryMeElse(offset) => - write!(f, "retry_me_else {}", offset), + write!(f, "retry_me_else {}", offset), &ChoiceInstruction::TrustMe => write!(f, "trust_me") } @@ -277,12 +277,12 @@ Each predicate must have the same name and arity."; }, &Ok(TopLevel::Fact(ref fact)) => { let compiled_fact = cg.compile_fact(&fact); - wam.add_fact(fact, compiled_fact); + wam.add_fact(fact, compiled_fact); EvalResult::EntrySuccess }, &Ok(TopLevel::Rule(ref rule)) => { let compiled_rule = cg.compile_rule(&rule); - wam.add_rule(rule, compiled_rule); + wam.add_rule(rule, compiled_rule); EvalResult::EntrySuccess }, &Ok(TopLevel::Query(ref query)) => { diff --git a/src/prolog/iterators.rs b/src/prolog/iterators.rs index cf71f4f2..b8ca6a3c 100644 --- a/src/prolog/iterators.rs +++ b/src/prolog/iterators.rs @@ -2,6 +2,7 @@ use prolog::ast::*; use std::cell::Cell; use std::collections::VecDeque; +use std::iter::*; use std::vec::Vec; enum IteratorState<'a> { @@ -107,7 +108,7 @@ impl<'a> Iterator for QueryIterator<'a> { IteratorState::InitialCons(lvl, cell, head, tail) => { self.push_final_cons(lvl, cell, head, tail); self.push_subterm(Level::Deep, tail); - self.push_subterm(Level::Deep, head); + self.push_subterm(Level::Deep, head); }, IteratorState::FinalCons(lvl, cell, head, tail) => return Some(TermRef::Cons(lvl, cell, head, tail)), @@ -207,3 +208,120 @@ impl Term { FactIterator::new(self) } } + +pub struct ChunkedIterator<'a> +{ + at_head: bool, + iter: Box> + 'a>, + deep_cut_encountered: bool +} + +impl<'a> ChunkedIterator<'a> +{ + pub fn from_term(term: &'a Term, at_head: bool) -> Self + { + let inner_iter: Box>> = + Box::new(once(TermOrCutRef::Term(term))); + + ChunkedIterator { + at_head: at_head, + iter: inner_iter, + deep_cut_encountered: false + } + } + + pub fn from_term_sequence(terms: &'a Vec) -> Self + { + let iter = terms.iter().map(|c| { + match c { + &TermOrCut::Cut => TermOrCutRef::Cut, + &TermOrCut::Term(ref term) => TermOrCutRef::Term(term) + } + }); + + ChunkedIterator { + at_head: false, + iter: Box::new(iter), + deep_cut_encountered: false + } + } + + pub fn from_rule(rule: &'a Rule) -> Self + { + let &Rule { head: (ref p0, ref p1), ref clauses } = rule; + let iter = once(TermOrCutRef::Term(p0)); + + let inner_iter : Box>> = match p1 { + &TermOrCut::Term(ref p1) => Box::new(once(TermOrCutRef::Term(p1))), + _ => Box::new(empty()) + }; + + let iter = iter.chain(inner_iter.chain(clauses.iter().map(|c| { + match c { + &TermOrCut::Cut => TermOrCutRef::Cut, + &TermOrCut::Term(ref term) => TermOrCutRef::Term(term) + } + }))); + + ChunkedIterator { + at_head: true, + iter: Box::new(iter), + deep_cut_encountered: false + } + } + + pub fn contains_deep_cut(&self) -> bool { + self.deep_cut_encountered + } + + pub fn at_head(&self) -> bool { + self.at_head + } + + fn take_chunk(&mut self, term: TermOrCutRef<'a>) -> (usize, Vec>) + { + let mut result = vec![term]; + let mut arity = 0; + + while let Some(term) = self.iter.next() { + match term { + TermOrCutRef::Term(inner_term) => { + result.push(term); + + if inner_term.is_callable() { + arity = inner_term.arity(); + break; + } + }, + _ => { + result.push(term); + self.deep_cut_encountered = true; + } + }; + } + + (arity, result) + } +} + +impl<'a> Iterator for ChunkedIterator<'a> +{ + // the last term arity, and the reference. + type Item = (usize, Vec>); + + fn next(&mut self) -> Option { + loop { + match self.iter.next() { + None => return None, + Some(TermOrCutRef::Term(term)) if self.at_head => { + self.at_head = false; + return Some(self.take_chunk(TermOrCutRef::Term(term))); + }, + Some(TermOrCutRef::Term(term)) if term.is_callable() => + return Some((term.arity(), vec![TermOrCutRef::Term(term)])), + Some(term_or_cut_ref) => + return Some(self.take_chunk(term_or_cut_ref)) + } + } + } +} diff --git a/src/prolog/machine.rs b/src/prolog/machine.rs index 1bbb2738..8509083b 100644 --- a/src/prolog/machine.rs +++ b/src/prolog/machine.rs @@ -251,8 +251,9 @@ impl Machine { } if succeeded { - for (var, vr) in cg.vars() { - let addr = self.ms.registers[vr.root_register()].clone(); + for (var, var_status) in cg.vars() { + let r = var_status.as_reg_type().reg_num(); + let addr = self.ms.registers[r].clone(); heap_locs.insert((*var).clone(), addr); } diff --git a/src/prolog/mod.rs b/src/prolog/mod.rs index 7eb95ba3..7cfe7cd9 100644 --- a/src/prolog/mod.rs +++ b/src/prolog/mod.rs @@ -1,9 +1,13 @@ pub mod and_stack; pub mod ast; pub mod codegen; +pub mod fixtures; pub mod heapview; +pub mod indexing; pub mod io; pub mod iterators; +pub mod naive_allocator; pub mod prolog_parser; pub mod machine; pub mod or_stack; +pub mod targets; diff --git a/src/prolog/naive_allocator.rs b/src/prolog/naive_allocator.rs new file mode 100644 index 00000000..aefdfd72 --- /dev/null +++ b/src/prolog/naive_allocator.rs @@ -0,0 +1,163 @@ +use prolog::ast::*; +use prolog::fixtures::*; + +use std::cell::Cell; +use std::cmp::max; +use std::collections::{BTreeSet, HashMap}; + +pub struct TermMarker<'a> { + pub bindings: HashMap<&'a Var, VarData>, + arg_c: usize, + temp_c: usize, + contents: HashMap, + in_use: BTreeSet, +} + +impl<'a> TermMarker<'a> { + pub fn new() -> TermMarker<'a> { + TermMarker { + arg_c: 1, + temp_c: 1, + bindings: HashMap::new(), + contents: HashMap::new(), + in_use: BTreeSet::new() + } + } + + pub fn drain_var_data(&mut self, vs: VariableFixtures<'a>) -> VariableFixtures<'a> + { + let mut perm_vs = VariableFixtures::new(); + + for (var, (var_status, cells)) in vs.into_iter() { + match var_status { + VarStatus::Temp(chunk_num, tvd) => { + self.bindings.insert(var, VarData::Temp(chunk_num, 0, tvd)); + }, + VarStatus::Perm(_) => { + self.bindings.insert(var, VarData::Perm(0)); + perm_vs.insert(var, (var_status, cells)); + } + }; + } + + perm_vs + } + + fn get(&self, var: &'a Var) -> RegType { + self.bindings.get(var).unwrap().as_reg_type() + } + + pub fn contains_var(&self, var: &'a Var) -> bool { + self.bindings.contains_key(var) + } + + pub fn marked_var(&self, var: &'a Var) -> bool { + self.get(var).reg_num() != 0 + } + + fn record_register(&mut self, var: &'a Var, r: RegType) { + match self.bindings.get_mut(var).unwrap() { + &mut VarData::Temp(_, ref mut s, _) => *s = r.reg_num(), + &mut VarData::Perm(ref mut s) => *s = r.reg_num() + } + } + + pub 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 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::Temp(arg)); + }, + _ => {} + }; + } + } + + pub fn mark_old_var(&mut self, lvl: Level, var: &'a Var) -> VarReg + { + let inner_reg = self.get(var); + + match lvl { + Level::Deep => VarReg::Norm(inner_reg), + Level::Shallow => { + let reg = VarReg::ArgAndNorm(inner_reg, self.arg_c); + self.arg_c += 1; + reg + } + } + } + + pub fn mark_new_var(&mut self, lvl: Level, var: &'a Var, reg: RegType) -> VarReg + { + let inner_reg = if !reg.is_perm() { + let temp = self.temp_c; + self.temp_c += 1; + RegType::Temp(temp) + } else { + reg + }; + + 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.record_register(var, inner_reg); + reg + } + + pub fn mark_anon_var(&mut self, lvl: Level) -> VarReg { + let inner_reg = { + let temp = self.temp_c; + self.temp_c += 1; + RegType::Temp(temp) + }; + + match lvl { + Level::Deep => VarReg::Norm(inner_reg), + Level::Shallow => { + let reg = VarReg::ArgAndNorm(inner_reg, self.arg_c); + self.arg_c += 1; + reg + } + } + } + + pub fn advance_arg(&mut self) { + self.arg_c += 1; + } + + pub fn advance_at_head(&mut self, term: &'a Term) { + self.arg_c = 1; + self.temp_c = max(term.subterms() + 1, self.temp_c); + } + + pub fn advance(&mut self, term: &'a Term) { + self.arg_c = 1; + self.temp_c = term.subterms() + 1; + } + + pub fn reset(&mut self) { + self.bindings.clear(); + self.contents.clear(); + self.in_use.clear(); + } + + pub fn reset_contents(&mut self) { + self.contents.clear(); + self.in_use.clear(); + } +} diff --git a/src/prolog/targets.rs b/src/prolog/targets.rs new file mode 100644 index 00000000..bef3610d --- /dev/null +++ b/src/prolog/targets.rs @@ -0,0 +1,119 @@ +use prolog::ast::*; +use prolog::iterators::*; + +pub trait CompilationTarget<'a> { + type Iterator : Iterator>; + + fn iter(&'a Term) -> Self::Iterator; + + fn to_constant(Level, Constant, RegType) -> Self; + fn to_list(Level, RegType) -> Self; + fn to_structure(Level, Atom, usize, RegType) -> Self; + fn to_void(usize) -> Self; + + fn constant_subterm(Constant) -> Self; + + fn argument_to_variable(RegType, usize) -> Self; + fn argument_to_value(RegType, usize) -> Self; + + fn subterm_to_variable(RegType) -> Self; + fn subterm_to_value(RegType) -> Self; + + fn clause_arg_to_instr(RegType) -> Self; +} + +impl<'a> CompilationTarget<'a> for FactInstruction { + type Iterator = FactIterator<'a>; + + fn iter(term: &'a Term) -> Self::Iterator { + term.breadth_first_iter() + } + + fn to_constant(lvl: Level, constant: Constant, reg: RegType) -> Self { + FactInstruction::GetConstant(lvl, constant, reg) + } + + fn to_structure(lvl: Level, atom: Atom, arity: usize, reg: RegType) -> Self { + FactInstruction::GetStructure(lvl, atom, arity, reg) + } + + fn to_list(lvl: Level, reg: RegType) -> Self { + FactInstruction::GetList(lvl, reg) + } + + fn to_void(subterms: usize) -> Self { + FactInstruction::UnifyVoid(subterms) + } + + fn constant_subterm(constant: Constant) -> Self { + FactInstruction::UnifyConstant(constant) + } + + fn argument_to_variable(arg: RegType, val: usize) -> Self { + FactInstruction::GetVariable(arg, val) + } + + fn argument_to_value(arg: RegType, val: usize) -> Self { + FactInstruction::GetValue(arg, val) + } + + fn subterm_to_variable(val: RegType) -> Self { + FactInstruction::UnifyVariable(val) + } + + fn subterm_to_value(val: RegType) -> Self { + FactInstruction::UnifyValue(val) + } + + fn clause_arg_to_instr(val: RegType) -> Self { + FactInstruction::UnifyVariable(val) + } +} + +impl<'a> CompilationTarget<'a> for QueryInstruction { + type Iterator = QueryIterator<'a>; + + fn iter(term: &'a Term) -> Self::Iterator { + term.post_order_iter() + } + + fn to_structure(lvl: Level, atom: Atom, arity: usize, reg: RegType) -> Self { + QueryInstruction::PutStructure(lvl, atom, arity, reg) + } + + fn to_constant(lvl: Level, constant: Constant, reg: RegType) -> Self { + QueryInstruction::PutConstant(lvl, constant, reg) + } + + fn to_list(lvl: Level, reg: RegType) -> Self { + QueryInstruction::PutList(lvl, reg) + } + + fn to_void(subterms: usize) -> Self { + QueryInstruction::SetVoid(subterms) + } + + fn constant_subterm(constant: Constant) -> Self { + QueryInstruction::SetConstant(constant) + } + + fn argument_to_variable(arg: RegType, val: usize) -> Self { + QueryInstruction::PutVariable(arg, val) + } + + fn argument_to_value(arg: RegType, val: usize) -> Self { + QueryInstruction::PutValue(arg, val) + } + + fn subterm_to_variable(val: RegType) -> Self { + QueryInstruction::SetVariable(val) + } + + fn subterm_to_value(val: RegType) -> Self { + QueryInstruction::SetValue(val) + } + + fn clause_arg_to_instr(val: RegType) -> Self { + QueryInstruction::SetValue(val) + } +} -- 2.54.0