From e41d1b319bb9d55f3b0a8467fc112406cba9854b Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Mon, 17 Oct 2022 22:56:08 -0600 Subject: [PATCH] adapt code generation --- src/allocator.rs | 3 + src/fixtures.rs | 2 +- src/forms.rs | 23 +- src/lib.rs | 1 - src/machine/disjuncts.rs | 640 ++++++++++++++++++++++++++++++++++++ src/machine/load_state.rs | 2 +- src/machine/mod.rs | 1 + src/machine/preprocessor.rs | 451 ++----------------------- 8 files changed, 698 insertions(+), 425 deletions(-) create mode 100644 src/machine/disjuncts.rs diff --git a/src/allocator.rs b/src/allocator.rs index 76bdfb53..bc0d2f44 100644 --- a/src/allocator.rs +++ b/src/allocator.rs @@ -60,6 +60,9 @@ pub(crate) trait Allocator { fn take_bindings(self) -> AllocVarDict; fn max_reg_allocated(&self) -> usize; + // TODO: wha.. why?? grrr. it drains the VarStatus data from vs (which it owns!) + // into self.bindings and perm_vs after all is computed (i.e. vs.populate_restricting_sets() + // and vs.set_perm_vals(has_deep_cut) have both been called). fn drain_var_data<'a>( &mut self, vs: VariableFixtures<'a>, diff --git a/src/fixtures.rs b/src/fixtures.rs index 1433b092..67740989 100644 --- a/src/fixtures.rs +++ b/src/fixtures.rs @@ -84,7 +84,7 @@ type VariableFixture<'a> = (VarStatus, Vec<&'a Cell>); #[derive(Debug)] pub(crate) struct VariableFixtures<'a> { perm_vars: IndexMap>, - last_chunk_temp_vars: IndexSet, + last_chunk_temp_vars: IndexSet, // TODO: has no use at all! } impl<'a> VariableFixtures<'a> { diff --git a/src/forms.rs b/src/forms.rs index 9db69581..d571e2d9 100644 --- a/src/forms.rs +++ b/src/forms.rs @@ -1,6 +1,7 @@ use crate::arena::*; use crate::atom_table::*; use crate::instructions::*; +use crate::machine::disjuncts::VarRecord; use crate::machine::heap::*; use crate::machine::loader::PredicateQueue; use crate::machine::machine_errors::*; @@ -34,7 +35,7 @@ pub type JumpStub = Vec; #[derive(Debug, Clone)] pub enum TopLevel { - Fact(Term), // Term, line_num, col_num + Fact(Fact), // Term, line_num, col_num Predicate(Predicate), Query(Vec), Rule(Rule), // Rule, line_num, col_num @@ -82,10 +83,11 @@ pub enum CallPolicy { pub enum QueryTerm { // register, clause type, subterms, clause call policy. Clause(Cell, ClauseType, Vec, CallPolicy), - BlockedCut, // a cut which is 'blocked by letters', like the P term in P -> Q. - UnblockedCut(Cell), + Cut, + Not(Vec), + IfThen(Vec, Vec), + Branch(Vec>), GetLevelAndUnify(Cell, Var), - Jump(JumpStub), // SOON: Branch(Vec), } impl QueryTerm { @@ -99,17 +101,24 @@ impl QueryTerm { pub(crate) fn arity(&self) -> usize { match self { &QueryTerm::Clause(_, _, ref subterms, ..) => subterms.len(), - &QueryTerm::BlockedCut | &QueryTerm::UnblockedCut(..) => 0, - &QueryTerm::Jump(ref vars) => vars.len(), - &QueryTerm::GetLevelAndUnify(..) => 1, + &QueryTerm::Cut | &QueryTerm::Branch(_) => 0, + &QueryTerm::IfThen(..) => 2, + &QueryTerm::Not(_) | &QueryTerm::GetLevelAndUnify(..) => 1, } } } +#[derive(Debug, Clone)] +pub struct Fact { + pub(crate) head: Term, + pub(crate) var_records: Vec, +} + #[derive(Debug, Clone)] pub struct Rule { pub(crate) head: (Atom, Vec, QueryTerm), pub(crate) clauses: Vec, + pub(crate) var_records: Vec, } #[derive(Clone, Debug, Hash)] diff --git a/src/lib.rs b/src/lib.rs index b117ab16..45dc2385 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -27,7 +27,6 @@ pub mod instructions { include!(concat!(env!("OUT_DIR"), "/instructions.rs")); } mod iterators; -mod disjuncts; pub mod machine; mod raw_block; pub mod read; diff --git a/src/machine/disjuncts.rs b/src/machine/disjuncts.rs new file mode 100644 index 00000000..a97f08c5 --- /dev/null +++ b/src/machine/disjuncts.rs @@ -0,0 +1,640 @@ + +/* +================================================================================ + +This is a disjunction compilation experiment attempting to adapt the +paper "Compiling Large Disjunctions" to Scryer Prolog. + +================================================================================ + */ + +use crate::atom_table::*; +use crate::forms::*; +use crate::instructions::*; +use crate::iterators::*; +use crate::machine::loader::*; +use crate::machine::machine_errors::CompilationError; +use crate::machine::preprocessor::*; +use crate::parser::ast::*; +use crate::parser::rug::Rational; + +use indexmap::{IndexMap, IndexSet}; + +use std::cell::Cell; +use std::cmp::Ordering; +use std::hash::{Hash, Hasher}; +use std::ops::{Deref, DerefMut}; + +#[derive(Debug, Clone)] +struct BranchNumber { + branch_num: Rational, + delta: Rational, +} + +impl Default for BranchNumber { + fn default() -> Self { + Self { + branch_num: Rational::from(1 << 10), + delta: Rational::from(1), + } + } +} + +impl PartialEq for BranchNumber { + #[inline] + fn eq(&self, rhs: &BranchNumber) -> bool { + self.branch_num == rhs.branch_num + } +} + +impl Eq for BranchNumber {} + +impl Hash for BranchNumber { + #[inline(always)] + fn hash(&self, hasher: &mut H) { + self.branch_num.hash(hasher) + } +} + +impl PartialOrd for BranchNumber { + #[inline] + fn partial_cmp(&self, rhs: &BranchNumber) -> Option { + self.branch_num.partial_cmp(&rhs.branch_num) + } +} + +impl BranchNumber { + fn split(&self) -> BranchNumber { + BranchNumber { + branch_num: self.branch_num.clone() + &self.delta / Rational::from(2), + delta: &self.delta / Rational::from(4), + } + } + + fn incr_by_delta(&self) -> BranchNumber { + BranchNumber { + branch_num: self.branch_num.clone() + &self.delta, + delta: self.delta.clone(), + } + } + + fn halve_delta(&self) -> BranchNumber { + BranchNumber { + branch_num: self.branch_num.clone(), + delta : &self.delta / Rational::from(2), + } + } +} + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub struct ChunkInfo { + chunk_num: usize, + vars: Vec, // pointer to incidence +} + +impl ChunkInfo { + fn new(chunk_num: usize) -> Self { + ChunkInfo { chunk_num, vars: vec![] } + } +} + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub struct BranchInfo { + branch_num: BranchNumber, + chunks: Vec, +} + +impl BranchInfo { + fn new(branch_num: BranchNumber) -> Self { + Self { branch_num, chunks: vec![] } + } +} + +type BranchMapInt = IndexMap>; + +#[derive(Debug, Clone)] +pub struct BranchMap(BranchMapInt); + +impl Deref for BranchMap { + type Target = BranchMapInt; + + #[inline(always)] + fn deref(&self) -> &BranchMapInt { + &self.0 + } +} + +impl DerefMut for BranchMap { + #[inline(always)] + fn deref_mut(&mut self) -> &mut BranchMapInt { + &mut self.0 + } +} + +type RootSet = IndexSet; + +enum TraversalState { + BuildDisjunct(usize), // construct a QueryTerm::Branch with number of disjuncts. + BuildIf(usize, Term), // build the P term of P -> Q + BuildThen(usize, Vec), // build the Q term of P -> Q + BuildNot(usize), // build the P term of \+ P + ResetCallPolicy(CallPolicy), + Term(Term), + AddBranchNum(BranchNumber), // set current_branch_number, add it to the root set + RemoveBranchNum, // remove latest branch number from the root set + RepBranchNum(BranchNumber), // replace current_branch_number and the latest in the root set + IncrChunkNum, // increment self.current_chunk_number +} + +impl Term { + #[inline] + fn is_var(&self) -> bool { + if let Term::Var(..) = self { + true + } else { + false + } + } + + #[inline] + fn is_compound(&self) -> bool { + match self { + Term::Clause(..) | Term::Cons(..) => true, + _ => false, + } + } +} + +pub struct VariableClassifier { + call_policy: CallPolicy, + current_branch_num: BranchNumber, + current_chunk_num: usize, + branch_map: BranchMap, + root_set: RootSet, +} + +#[derive(Debug)] +pub enum VarClassification { + Void, + Temp, + Perm, +} + +pub struct VarRecord { + pub classification: VarClassification, + pub chunk_occurrences: Vec, + pub num_occurrences: usize, +} + +pub type ClassifyFactResult = (Term, Vec); +pub type ClassifyRuleResult = (Term, Vec, Vec); + +fn merge_branch_seq>(branches: Iter) -> BranchInfo { + let mut branch_info = BranchInfo::new(BranchNumber::default()); + + for mut branch in branches { + branch_info.branch_num = branch.branch_num; + + if let Some(last_chunk) = branch_info.chunks.last_mut() { + if let Some(first_moved_chunk) = branch.chunks.first_mut() { + if last_chunk.chunk_num == first_moved_chunk.chunk_num { + last_chunk.vars.extend(first_moved_chunk.vars.drain(..)); + branch_info.chunks.extend(branch.chunks.drain(1 ..)); + + continue; + } + } + } + + branch_info.chunks.extend(branch.chunks.drain(..)); + } + + branch_info.branch_num.delta *= 2; + branch_info.branch_num.branch_num -= &branch_info.branch_num.delta; + + branch_info +} + +impl VariableClassifier { + pub fn new(call_policy: CallPolicy) -> Self { + Self { + call_policy, + current_branch_num: BranchNumber::default(), + current_chunk_num: 0, + branch_map: BranchMap(BranchMapInt::new()), + root_set: RootSet::new(), + } + } + + pub fn classify_fact(mut self, term: Term) -> Result { + self.classify_head_variables(&term)?; + Ok((term, self.branch_map.separate_and_classify_variables())) + } + + pub fn classify_rule<'a, LS: LoadState<'a>>( + mut self, + loader: &mut Loader<'a, LS>, + head: Term, + body: Term, + ) -> Result { + self.classify_head_variables(&head)?; + let query_terms = self.classify_body_variables(loader, body)?; + + Ok((head, query_terms, self.branch_map.separate_and_classify_variables())) + } + + /* + pub fn to_branch_map(mut self, term: Term) -> Result { + self.root_set.insert(BranchNumber::default()); + + let (head_term, query_terms) = match term { + Term::Clause(_, atom!(":-"), terms) if terms.len() == 2 => { + let head_term = terms[0]; + + self.classify_head_variables(&head_term)?; + (head_term, self.classify_body_variables(terms[1])?) + } + _ => { + self.classify_head_variables(&term)?; + (term, vec![]) + } + }; + + self.merge_branches(); + Ok((head_term, query_terms, self.branch_map)) + } + */ + + fn merge_branches(&mut self) { + for branches in self.branch_map.values_mut() { + let mut old_branches = std::mem::replace(branches, vec![]); + + while let Some(last_branch_num) = old_branches.last().map(|bi| &bi.branch_num) { + let mut old_branches_len = old_branches.len(); + + for (rev_idx, bi) in old_branches.iter().rev().enumerate() { + if &bi.branch_num > last_branch_num { + old_branches_len = old_branches.len() - rev_idx; + } + } + + let iter = old_branches.drain(old_branches_len - 1 ..); + branches.push(merge_branch_seq(iter)); + } + + branches.reverse(); + } + } + + fn probe_body_term(&mut self, term: &Term) { + // true to iterate the root, which may be a variable! + for term_ref in breadth_first_iter(term, true) { + if let TermRef::Var(_, _, var_name) = term_ref { + self.probe_body_var(Var::from(var_name)); + } + } + } + + fn probe_body_var(&mut self, var_name: Var) { + let branch_info_v = self.branch_map.entry(var_name) + .or_insert_with(|| vec![]); + + let needs_new_branch = if let Some(last_bi) = branch_info_v.last() { + !self.root_set.contains(&last_bi.branch_num) + } else { + true + }; + + if needs_new_branch { + branch_info_v.push(BranchInfo::new(self.current_branch_num.clone())); + } + + let branch_info = branch_info_v.last_mut().unwrap(); + + let needs_new_chunk = if let Some(last_ci) = branch_info.chunks.last() { + last_ci.chunk_num != self.current_chunk_num + } else { + true + }; + + if needs_new_chunk { + branch_info.chunks.push(ChunkInfo::new(self.current_chunk_num)); + } + + let chunk_info = branch_info.chunks.last_mut().unwrap(); + chunk_info.vars.push(VarPtr::from(&var_name)); + } + + fn classify_head_variables(&mut self, term: &Term) -> Result<(), CompilationError> { + match term { + Term::Clause(..) | Term::Literal(_, Literal::Atom(_)) => { + } + _ => return Err(CompilationError::InvalidRuleHead), + } + + // false argument to breadth_first_iter because the root is not iterable. + for term_ref in breadth_first_iter(term, false) { + if let TermRef::Var(_, _, var_name) = term_ref { + // the body of the if let here is an inlined + // "probe_head_var". note the difference between it + // and "probe_body_var". + let branch_info_v = self.branch_map.entry(Var::from(var_name)) + .or_insert_with(|| vec![]); + + let needs_new_branch = branch_info_v.is_empty(); + + if needs_new_branch { + branch_info_v.push(BranchInfo::new(self.current_branch_num.clone())); + } + + let branch_info = branch_info_v.last_mut().unwrap(); + let needs_new_chunk = branch_info.chunks.is_empty(); + + if needs_new_chunk { + branch_info.chunks.push(ChunkInfo::new(self.current_chunk_num)); + } + + let chunk_info = branch_info.chunks.last_mut().unwrap(); + chunk_info.vars.push(VarPtr::from(&var_name)); + } + } + + Ok(()) + } + + fn classify_body_variables<'a, LS: LoadState<'a>>( + &mut self, + loader: &mut Loader<'a, LS>, + term: Term, + ) -> Result, CompilationError> { + let mut state_stack = vec![TraversalState::Term(term)]; + let mut build_stack = vec![]; + + while let Some(traversal_st) = state_stack.pop() { + match traversal_st { + TraversalState::AddBranchNum(branch_num) => { + self.root_set.insert(branch_num.clone()); + self.current_branch_num = branch_num; + } + TraversalState::RemoveBranchNum => { + self.root_set.pop(); + } + TraversalState::RepBranchNum(branch_num) => { + self.root_set.pop(); + self.root_set.insert(branch_num.clone()); + self.current_branch_num = branch_num; + } + TraversalState::IncrChunkNum => { + self.current_chunk_num += 1; + } + TraversalState::BuildDisjunct(preceding_len) => { + let iter = build_stack.drain(preceding_len ..); + + if let QueryTerm::Branch(ref mut disjuncts) = &mut build_stack[preceding_len] { + disjuncts.push(iter.collect()); + } + } + TraversalState::BuildIf(preceding_len, then_term) => { + let iter = build_stack.drain(preceding_len ..); + let build_stack_len = build_stack.len(); + + state_stack.push(TraversalState::BuildThen(build_stack_len, iter.collect())); + } + TraversalState::BuildThen(preceding_len, if_terms) => { + let iter = build_stack.drain(preceding_len ..); + build_stack.push(QueryTerm::IfThen(if_terms, iter.collect())); + } + TraversalState::BuildNot(preceding_len) => { + let iter = build_stack.drain(preceding_len ..); + build_stack.push(QueryTerm::Not(iter.collect())); + } + TraversalState::ResetCallPolicy(call_policy) => { + self.call_policy = call_policy; + } + TraversalState::Term(term) => { + match term { + Term::Clause(_, atom!(","), terms) if terms.len() == 2 => { + state_stack.extend( + unfold_by_str(terms[1], atom!(",")) + .into_iter() + .rev() + .map(TraversalState::Term), + ); + + state_stack.push(TraversalState::Term(terms[0])); + } + Term::Clause(_, atom!(";"), terms) if terms.len() == 2 => { + let first_branch_num = self.current_branch_num.split(); + let branches: Vec<_> = std::iter::once(terms[0]) + .chain(unfold_by_str(terms[1], atom!(";")).into_iter()) + .collect(); + + let mut branch_numbers = vec![first_branch_num]; + + for idx in 1 .. branches.len() { + let succ_branch_number = branch_numbers[idx - 1].incr_by_delta(); + + branch_numbers.push(if idx + 1 < branches.len() { + succ_branch_number.split() + } else { + succ_branch_number + }); + } + + let build_stack_len = build_stack.len(); + + build_stack.push(QueryTerm::Branch(vec![])); + state_stack.push(TraversalState::BuildDisjunct(build_stack_len)); + + state_stack.push(TraversalState::RepBranchNum( + self.current_branch_num.halve_delta(), + )); + + let iter = branches.into_iter().zip(branch_numbers.into_iter()); + + for (term, branch_num) in iter.rev() { + state_stack.push(TraversalState::BuildDisjunct(build_stack_len)); + + state_stack.push(TraversalState::RemoveBranchNum); + state_stack.push(TraversalState::Term(term)); + state_stack.push(TraversalState::AddBranchNum(branch_num)); + } + } + Term::Clause(_, atom!("->"), mut terms) if terms.len() == 2 => { + let then_term = terms.pop().unwrap(); + let if_term = terms.pop().unwrap(); + let build_stack_len = build_stack.len(); + + state_stack.push(TraversalState::BuildIf(build_stack_len, then_term)); + state_stack.push(TraversalState::Term(if_term)); + } + Term::Clause(_, atom!("\\+"), terms) if terms.len() == 1 => { + let build_stack_len = build_stack.len(); + + state_stack.push(TraversalState::BuildNot(build_stack_len)); + state_stack.push(TraversalState::Term(terms[0])); + } + Term::Clause(_, atom!("$get_level"), terms) if terms.len() == 1 => { + state_stack.push(TraversalState::IncrChunkNum); + + if let Term::Var(_, ref var) = &terms[0] { + build_stack.push(QueryTerm::GetLevelAndUnify(Cell::default(), var.clone())); + } else { + return Err(CompilationError::InadmissibleQueryTerm); + } + } + Term::Clause(_, atom!(":"), mut terms) if terms.len() == 2 => { + let predicate_name = terms.pop().unwrap(); + let module_name = terms.pop().unwrap(); + + match (module_name, predicate_name) { + ( + Term::Literal(_, Literal::Atom(module_name)), + Term::Literal(_, Literal::Atom(predicate_name)), + ) => { + if !ClauseType::is_inbuilt(name, 0) { + state_stack.push(TraversalState::IncrChunkNum); + } + + build_stack.push( + qualified_clause_to_query_term( + loader, + module_name, + predicate_name, + vec![], + self.call_policy, + ), + ); + } + ( + Term::Literal(_, Literal::Atom(module_name)), + Term::Clause(_, name, terms), + ) => { + if !ClauseType::is_inbuilt(name, terms.len()) { + state_stack.push(TraversalState::IncrChunkNum); + } + + build_stack.push( + qualified_clause_to_query_term( + loader, + module_name, + name, + terms, + self.call_policy, + ), + ); + } + (module_name, predicate_name) => { + state_stack.push(TraversalState::IncrChunkNum); + + terms.push(module_name); + terms.push(predicate_name); + + build_stack.push( + clause_to_query_term( + loader, + atom!("call"), + vec![Term::Clause(Cell::default(), atom!(":"), terms)], + self.call_policy, + ), + ); + } + } + } + Term::Clause(cell, atom!("$call_with_inference_counting"), terms) if terms.len() == 2 => { + state_stack.push(TraversalState::ResetCallPolicy(self.call_policy)); + state_stack.push(TraversalState::Term(terms[0])); + + self.call_policy = CallPolicy::Counted; + } + Term::Clause(cell, name, terms) => { + if !ClauseType::is_inbuilt(name, terms.len()) { + state_stack.push(TraversalState::IncrChunkNum); + } + + for term in terms.iter() { + self.probe_body_term(term); + } + + build_stack.push( + clause_to_query_term( + loader, + name, + terms, + self.call_policy, + ), + ); + } + Term::Literal(_, Literal::Atom(atom!("!"))) | + Term::Literal(_, Literal::Char('!')) => { + build_stack.push(QueryTerm::Cut); + } + Term::Literal(cell, Literal::Atom(name)) => { + if !ClauseType::is_inbuilt(name, 0) { + state_stack.push(TraversalState::IncrChunkNum); + } + + build_stack.push( + clause_to_query_term( + loader, + name, + vec![], + self.call_policy, + ), + ); + } + _ => { + return Err(CompilationError::InadmissibleQueryTerm); + } + } + } + } + } + + Ok(build_stack) + } +} + +impl BranchMap { + pub fn separate_and_classify_variables(&mut self) -> Vec { + let mut var_num = 0usize; + let mut records = vec![]; + + for branches in self.values_mut() { + for branch in branches.iter_mut() { + let mut num_occurrences = 0; + let mut chunk_occurrences = vec![]; + + for chunk in branch.chunks.iter_mut() { + num_occurrences += chunk.vars.len(); + + for var in chunk.vars.iter_mut() { + var.set(Var::Generated(var_num)); + } + + chunk_occurrences.push(chunk.chunk_num); + } + + let classification = if branch.chunks.len() > 1 { + VarClassification::Perm + } else { + branch.chunks + .first() + .map(|chunk| if chunk.vars.len() > 1 { + VarClassification::Temp + } else { + VarClassification::Void + }) + .unwrap_or(VarClassification::Void) + }; + + records.push(VarRecord { classification, chunk_occurrences, num_occurrences }); + var_num += 1; + } + } + + debug_assert_eq!(records.len(), var_num); + + records + } +} diff --git a/src/machine/load_state.rs b/src/machine/load_state.rs index 802d51eb..3d0a638a 100644 --- a/src/machine/load_state.rs +++ b/src/machine/load_state.rs @@ -441,7 +441,7 @@ impl<'a, LS: LoadState<'a>> Loader<'a, LS> { term: Term, preprocessor: &mut Preprocessor, ) -> Result { - let tl = preprocessor.try_term_to_tl(self, term, CutContext::BlocksCuts)?; + let tl = preprocessor.try_term_to_tl(self, term)?; Ok(match tl { TopLevel::Fact(fact) => PredicateClause::Fact(fact), diff --git a/src/machine/mod.rs b/src/machine/mod.rs index 5193eb66..dab4c54c 100644 --- a/src/machine/mod.rs +++ b/src/machine/mod.rs @@ -16,6 +16,7 @@ pub mod machine_state; pub mod machine_state_impl; pub mod mock_wam; pub mod partial_string; +pub mod disjuncts; pub mod preprocessor; pub mod stack; pub mod streams; diff --git a/src/machine/preprocessor.rs b/src/machine/preprocessor.rs index d2c33b06..0564af8c 100644 --- a/src/machine/preprocessor.rs +++ b/src/machine/preprocessor.rs @@ -2,7 +2,7 @@ use crate::atom_table::*; use crate::codegen::CodeGenSettings; use crate::forms::*; use crate::instructions::*; -use crate::iterators::*; +use crate::machine::disjuncts::*; use crate::machine::loader::*; use crate::machine::machine_errors::*; use crate::parser::ast::*; @@ -13,21 +13,6 @@ use std::cell::Cell; use std::collections::VecDeque; use std::convert::TryFrom; -/* - * The preprocessor fabricates if-then-else ( .. -> ... ; ...) - * clauses into nameless standalone predicates, which it queues for - * later preprocessing and compilation. Fabricated predicates inherit - * explicit "cut variables" from the handwritten predicate - * surrounding their source if-then-else. They must be specially - * handled. - */ - -#[derive(Clone, Copy, Debug)] -pub(crate) enum CutContext { - BlocksCuts, - HasCutVariable, -} - pub(crate) fn fold_by_str(terms: I, mut term: Term, sym: Atom) -> Term where I: DoubleEndedIterator, @@ -131,6 +116,13 @@ fn setup_module_export( }) } +pub(crate) fn build_rule_body(vars: &[Term], body_term: Term) -> Term { + let head_term = Term::Clause(Cell::default(), atom!(""), vars.iter().cloned().collect()); + let rule = vec![head_term, body_term]; + + Term::Clause(Cell::default(), atom!(":-"), rule) +} + pub(super) fn setup_module_export_list( mut export_list: Term, atom_tbl: &mut AtomTable, @@ -324,110 +316,6 @@ fn setup_meta_predicate<'a, LS: LoadState<'a>>( } } -fn merge_clauses(tls: &mut VecDeque) -> Result { - let mut clauses = vec![]; - - while let Some(tl) = tls.pop_front() { - match tl { - TopLevel::Query(_) if clauses.is_empty() && tls.is_empty() => { - return Ok(tl); - } - TopLevel::Query(_) => { - return Err(CompilationError::InconsistentEntry); - } - TopLevel::Fact(fact) => { - let clause = PredicateClause::Fact(fact); - clauses.push(clause); - } - TopLevel::Rule(rule) => { - let clause = PredicateClause::Rule(rule); - clauses.push(clause); - } - TopLevel::Predicate(predicate) => clauses.extend(predicate.into_iter()), - } - } - - if clauses.is_empty() { - Err(CompilationError::InconsistentEntry) - } else { - Ok(TopLevel::Predicate(clauses)) - } -} - -fn mark_cut_variables_as(terms: &mut Vec, name: Atom) { - for term in terms.iter_mut() { - match term { - &mut Term::Literal(_, Literal::Atom(ref mut var)) if *var == atom!("!") => { - *var = name; - } - _ => {} - } - } -} - -fn mark_cut_variable(term: &mut Term) -> bool { - let cut_var_found = match term { - &mut Term::Literal(_, Literal::Atom(ref var)) if *var == atom!("!") => true, - _ => false, - }; - - if cut_var_found { - *term = Term::Var(Cell::default(), Var::from("!")); - true - } else { - false - } -} - -fn mark_cut_variables(terms: &mut Vec) -> bool { - let mut found_cut_var = false; - - for item in terms.iter_mut() { - found_cut_var = mark_cut_variable(item) || found_cut_var; - } - - found_cut_var -} - -// terms is a list of goals composing one clause in a (;) functor. it -// checks that the first (and only) of these clauses is a ->. if so, -// it expands its terms using a blocked_!. -fn check_for_internal_if_then(terms: &mut Vec) { - if terms.len() != 1 { - return; - } - - if let Some(Term::Clause(_, name, ref subterms)) = terms.last() { - if *name != atom!("->") || source_arity(subterms) != 2 { - return; - } - } else { - return; - } - - if let Some(Term::Clause(_, _, mut subterms)) = terms.pop() { - let mut conq_terms = VecDeque::from(unfold_by_str(subterms.pop().unwrap(), atom!(","))); - let mut pre_cut_terms = VecDeque::from(unfold_by_str(subterms.pop().unwrap(), atom!(","))); - - conq_terms.push_front(Term::Literal( - Cell::default(), - Literal::Atom(atom!("blocked_!")), - )); - - while let Some(term) = pre_cut_terms.pop_back() { - conq_terms.push_front(term); - } - - let tail_term = conq_terms.pop_back().unwrap(); - - terms.push(fold_by_str( - conq_terms.into_iter(), - tail_term, - atom!(","), - )); - } -} - pub(super) fn setup_declaration<'a, LS: LoadState<'a>>( loader: &mut Loader<'a, LS>, mut terms: Vec, @@ -569,7 +457,7 @@ fn build_meta_predicate_clause<'a, LS: LoadState<'a>>( } #[inline] -fn clause_to_query_term<'a, LS: LoadState<'a>>( +pub(super) fn clause_to_query_term<'a, LS: LoadState<'a>>( loader: &mut Loader<'a, LS>, name: Atom, mut terms: Vec, @@ -608,7 +496,7 @@ fn clause_to_query_term<'a, LS: LoadState<'a>>( } #[inline] -fn qualified_clause_to_query_term<'a, LS: LoadState<'a>>( +pub(super) fn qualified_clause_to_query_term<'a, LS: LoadState<'a>>( loader: &mut Loader<'a, LS>, module_name: Atom, name: Atom, @@ -646,308 +534,65 @@ fn qualified_clause_to_query_term<'a, LS: LoadState<'a>>( QueryTerm::Clause(Cell::default(), ct, terms, call_policy) } -fn compute_head(term: &Term) -> Vec { - let mut vars = IndexSet::new(); - - for term in post_order_iter(term) { - if let TermRef::Var(_, _, v) = term { - vars.insert(v.clone()); - } - } - - vars.insert(Var::from("!")); - vars.into_iter() - .map(|v| Term::Var(Cell::default(), v)) - .collect() -} - -pub(crate) fn build_rule_body(vars: &[Term], body_term: Term) -> Term { - let head_term = Term::Clause(Cell::default(), atom!(""), vars.iter().cloned().collect()); - let rule = vec![head_term, body_term]; - - Term::Clause(Cell::default(), atom!(":-"), rule) -} - -// the terms form the body of the rule. We create a head, by -// gathering variables from the body of terms and recording them -// in the head clause. -fn build_rule(body_term: Term) -> (JumpStub, VecDeque) { - // collect the vars of body_term into a head, return the num_vars - // (the arity) as well. - let vars = compute_head(&body_term); - let rule = build_rule_body(&vars, body_term); - - (vars, VecDeque::from(vec![rule])) -} - -fn build_disjunct(body_term: Term) -> (JumpStub, VecDeque) { - let vars = compute_head(&body_term); - let results = unfold_by_str(body_term, atom!(";")) - .into_iter() - .map(|term| { - let mut subterms = unfold_by_str(term, atom!(",")); - mark_cut_variables(&mut subterms); - - check_for_internal_if_then(&mut subterms); - - let term = subterms.pop().unwrap(); - let clause = fold_by_str(subterms.into_iter(), term, atom!(",")); - - build_rule_body(&vars, clause) - }) - .collect(); - - (vars, results) -} - -fn build_if_then(prec: Term, conq: Term) -> (JumpStub, VecDeque) { - let mut prec_seq = unfold_by_str(prec, atom!(",")); - let comma_sym = atom!(","); - let cut_sym = Literal::Atom(atom!("!")); - - prec_seq.push(Term::Literal(Cell::default(), cut_sym)); - - mark_cut_variables_as(&mut prec_seq, atom!("blocked_!")); - - let mut conq_seq = unfold_by_str(conq, atom!(",")); - - mark_cut_variables(&mut conq_seq); - prec_seq.extend(conq_seq.into_iter()); - - let back_term = prec_seq.pop().unwrap(); - let front_term = prec_seq.pop().unwrap(); - - let body_term = Term::Clause( - Cell::default(), - comma_sym, - vec![front_term, back_term], - ); - - build_rule(fold_by_str(prec_seq.into_iter(), body_term, comma_sym)) -} - #[derive(Debug)] pub(crate) struct Preprocessor { - queue: VecDeque>, settings: CodeGenSettings, } impl Preprocessor { pub(super) fn new(settings: CodeGenSettings) -> Self { Preprocessor { - queue: VecDeque::new(), settings, } } - fn setup_fact(&mut self, term: Term) -> Result { + fn setup_fact(&mut self, term: Term) -> Result { match term { - Term::Clause(..) | Term::Literal(_, Literal::Atom(..)) => Ok(term), - _ => Err(CompilationError::InadmissibleFact), - } - } - - fn to_query_term<'a, LS: LoadState<'a>>( - &mut self, - loader: &mut Loader<'a, LS>, - term: Term, - ) -> Result { - match term { - Term::Literal(_, Literal::Atom(name)) => { - if name == atom!("!") || name == atom!("blocked_!") { - Ok(QueryTerm::BlockedCut) - } else { - Ok(clause_to_query_term( - loader, - name, - vec![], - self.settings.default_call_policy(), - )) - } - } - Term::Literal(_, Literal::Char('!')) => Ok(QueryTerm::BlockedCut), - Term::Var(_, ref v) if v.as_str() == Some("!") => { - Ok(QueryTerm::UnblockedCut(Cell::default())) - } - Term::Clause(r, name, mut terms) => match (name, source_arity(&terms)) { - (atom!(";"), 2) => { - let term = Term::Clause(r, name, terms); - - let (stub, clauses) = build_disjunct(term); - self.queue.push_back(clauses); - - Ok(QueryTerm::Jump(stub)) - } - (atom!("->"), 2) => { - let conq = terms.pop().unwrap(); - let prec = terms.pop().unwrap(); + Term::Clause(..) | Term::Literal(_, Literal::Atom(..)) => { + let mut classifier = VariableClassifier::new( + self.settings.default_call_policy(), + ); - let (stub, clauses) = build_if_then(prec, conq); - self.queue.push_back(clauses); + let (head, var_records) = classifier.classify_fact(term)?; - Ok(QueryTerm::Jump(stub)) - } - (atom!("\\+"), 1) => { - terms.push(Term::Literal( - Cell::default(), - Literal::Atom(atom!("$fail")), - )); - - let conq = Term::Literal(Cell::default(), Literal::Atom(atom!("true"))); - - let prec = Term::Clause(Cell::default(), atom!("->"), terms); - let terms = vec![prec, conq]; - - let term = Term::Clause(Cell::default(), atom!(";"), terms); - let (stub, clauses) = build_disjunct(term); - - debug_assert!(clauses.len() > 0); - self.queue.push_back(clauses); - - Ok(QueryTerm::Jump(stub)) - } - (atom!("$get_level"), 1) => { - if let Term::Var(_, ref var) = &terms[0] { - Ok(QueryTerm::GetLevelAndUnify(Cell::default(), var.clone())) - } else { - Err(CompilationError::InadmissibleQueryTerm) - } - } - (atom!(":"), 2) => { - let predicate_name = terms.pop().unwrap(); - let module_name = terms.pop().unwrap(); - - match (module_name, predicate_name) { - ( - Term::Literal(_, Literal::Atom(module_name)), - Term::Literal(_, Literal::Atom(predicate_name)), - ) => Ok(qualified_clause_to_query_term( - loader, - module_name, - predicate_name, - vec![], - self.settings.default_call_policy(), - )), - ( - Term::Literal(_, Literal::Atom(module_name)), - Term::Clause(_, name, terms), - ) => Ok(qualified_clause_to_query_term( - loader, - module_name, - name, - terms, - self.settings.default_call_policy() - )), - (module_name, predicate_name) => { - terms.push(module_name); - terms.push(predicate_name); - - Ok(clause_to_query_term( - loader, - atom!("call"), - vec![Term::Clause(r, name, terms)], - self.settings.default_call_policy(), - )) - } - } - } - _ => Ok(clause_to_query_term(loader, name, terms, - self.settings.default_call_policy())), - }, - Term::Var(..) => Ok(QueryTerm::Clause( - Cell::default(), - ClauseType::CallN(1), - vec![term], - self.settings.default_call_policy(), - )), - _ => Err(CompilationError::InadmissibleQueryTerm), - } - } - - fn pre_query_term<'a, LS: LoadState<'a>>( - &mut self, - loader: &mut Loader<'a, LS>, - term: Term, - ) -> Result { - match term { - Term::Clause(r, name, mut subterms) => { - if subterms.len() == 1 && name == atom!("$call_with_inference_counting") { - self.to_query_term(loader, subterms.pop().unwrap()) - .map(|mut query_term| { - query_term.set_call_policy(CallPolicy::Counted); - query_term - }) - } else { - let clause = Term::Clause(r, name, subterms); - self.to_query_term(loader, clause) - } - } - _ => self.to_query_term(loader, term), - } - } - - fn setup_query<'a, LS: LoadState<'a>>( - &mut self, - loader: &mut Loader<'a, LS>, - terms: Vec, - cut_context: CutContext, - ) -> Result, CompilationError> { - let mut query_terms = vec![]; - let mut work_queue = VecDeque::from(terms); - - while let Some(term) = work_queue.pop_front() { - let mut term = term; - - if let Term::Clause(cell, name, terms) = term { - if name == atom!(",") && source_arity(&terms) == 2 { - let term = Term::Clause(cell, name, terms); - let mut subterms = unfold_by_str(term, atom!(",")); - - while let Some(subterm) = subterms.pop() { - work_queue.push_front(subterm); - } - - continue; - } else { - term = Term::Clause(cell, name, terms); - } - } - - if let CutContext::HasCutVariable = cut_context { - mark_cut_variable(&mut term); + Ok(Fact { head, var_records }) } - - query_terms.push(self.pre_query_term(loader, term)?); + _ => Err(CompilationError::InadmissibleFact), } - - Ok(query_terms) } fn setup_rule<'a, LS: LoadState<'a>>( &mut self, loader: &mut Loader<'a, LS>, - mut terms: Vec, - cut_context: CutContext, + head: Term, + body: Term, ) -> Result { - let post_head_terms: Vec<_> = terms.drain(1..).collect(); - let mut query_terms = self.setup_query(loader, post_head_terms, cut_context)?; + let mut classifier = VariableClassifier::new( + self.settings.default_call_policy(), + ); + + let (head, mut query_terms, var_records) = + classifier.classify_rule(loader, head, body)?; let clauses = query_terms.drain(1..).collect(); let qt = query_terms.pop().unwrap(); - match terms.pop().unwrap() { + match head { Term::Clause(_, name, terms) => Ok(Rule { head: (name, terms, qt), clauses, + var_records, }), Term::Literal(_, Literal::Atom(name)) => Ok(Rule { head: (name, vec![], qt), clauses, + var_records, }), _ => Err(CompilationError::InvalidRuleHead), } } + /* fn try_term_to_query<'a, LS: LoadState<'a>>( &mut self, loader: &mut Loader<'a, LS>, @@ -960,23 +605,19 @@ impl Preprocessor { cut_context, )?)) } + */ pub(super) fn try_term_to_tl<'a, LS: LoadState<'a>>( &mut self, loader: &mut Loader<'a, LS>, term: Term, - cut_context: CutContext, ) -> Result { match term { Term::Clause(r, name, terms) => { - if name == atom!("?-") { - self.try_term_to_query(loader, terms, cut_context) - } else if name == atom!(":-") && terms.len() == 2 { - Ok(TopLevel::Rule(self.setup_rule( - loader, - terms, - cut_context, - )?)) + let is_rule = name == atom!(":-") && terms.len() == 2; + + if is_rule { + Ok(TopLevel::Rule(self.setup_rule(loader, terms[0], terms[1])?)) } else { let term = Term::Clause(r, name, terms); Ok(TopLevel::Fact(self.setup_fact(term)?)) @@ -990,33 +631,13 @@ impl Preprocessor { &mut self, loader: &mut Loader<'a, LS>, terms: I, - cut_context: CutContext, ) -> Result, CompilationError> { let mut results = VecDeque::new(); for term in terms.into_iter() { - results.push_back(self.try_term_to_tl(loader, term, cut_context)?); + results.push_back(self.try_term_to_tl(loader, term)?); } Ok(results) } - - pub(super) fn parse_queue<'a, LS: LoadState<'a>>( - &mut self, - loader: &mut Loader<'a, LS>, - ) -> Result, CompilationError> { - let mut queue = VecDeque::new(); - - while let Some(terms) = self.queue.pop_front() { - let clauses = merge_clauses(&mut self.try_terms_to_tls( - loader, - terms, - CutContext::HasCutVariable, - )?)?; - - queue.push_back(clauses); - } - - Ok(queue) - } } -- 2.54.0