From 0c19c5690978b7ddbc180e9886f75ee25a5e1257 Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Sat, 5 Mar 2022 15:27:36 -0700 Subject: [PATCH] mark variables in ArithmeticEvaluator (#690) --- src/allocator.rs | 66 +++++++++++----------- src/arithmetic.rs | 60 +++++++++++++++----- src/codegen.rs | 119 +++++++++++++++++----------------------- src/debray_allocator.rs | 66 +++++++++++----------- src/lib/builtins.pl | 2 +- 5 files changed, 161 insertions(+), 152 deletions(-) diff --git a/src/allocator.rs b/src/allocator.rs index 7a3b43a0..a8fbc693 100644 --- a/src/allocator.rs +++ b/src/allocator.rs @@ -5,48 +5,52 @@ use crate::fixtures::*; use crate::forms::*; use crate::instructions::*; use crate::machine::machine_indices::*; +use crate::targets::*; use std::cell::Cell; use std::rc::Rc; -pub(crate) trait Allocator<'a> { +pub(crate) trait Allocator { fn new() -> Self; - fn mark_anon_var(&mut self, _: Level, _: GenContext, _: &mut Code) - where - Target: crate::targets::CompilationTarget<'a>; - fn mark_non_var( + fn mark_anon_var<'a, Target: CompilationTarget<'a>>( &mut self, - _: Level, - _: GenContext, - _: &'a Cell, - _: &mut Code, - ) where - Target: crate::targets::CompilationTarget<'a>; - fn mark_reserved_var( + lvl: Level, + context: GenContext, + code: &mut Code, + ); + + fn mark_non_var<'a, Target: CompilationTarget<'a>>( + &mut self, + lvl: Level, + context: GenContext, + cell: &'a Cell, + code: &mut Code, + ); + + fn mark_reserved_var<'a, Target: CompilationTarget<'a>>( &mut self, - _: Rc, - _: Level, - _: &'a Cell, - _: GenContext, - _: &mut Code, - _: RegType, - _: bool, - ) where - Target: crate::targets::CompilationTarget<'a>; - fn mark_var( + var_name: Rc, + lvl: Level, + cell: &'a Cell, + term_loc: GenContext, + code: &mut Code, + r: RegType, + is_new_var: bool, + ); + + fn mark_var<'a, Target: CompilationTarget<'a>>( &mut self, - _: Rc, - _: Level, - _: &'a Cell, - _: GenContext, - _: &mut Code, - ) where - Target: crate::targets::CompilationTarget<'a>; + var_name: Rc, + lvl: Level, + cell: &'a Cell, + context: GenContext, + code: &mut Code, + ); fn reset(&mut self); fn reset_contents(&mut self) {} - fn reset_arg(&mut self, _: usize); + fn reset_arg(&mut self, arg_num: usize); fn reset_at_head(&mut self, args: &Vec); fn advance_arg(&mut self); @@ -56,7 +60,7 @@ pub(crate) trait Allocator<'a> { fn take_bindings(self) -> AllocVarDict; - fn drain_var_data( + fn drain_var_data<'a>( &mut self, vs: VariableFixtures<'a>, num_of_chunks: usize, diff --git a/src/arithmetic.rs b/src/arithmetic.rs index 82212522..894e9d1f 100644 --- a/src/arithmetic.rs +++ b/src/arithmetic.rs @@ -1,3 +1,4 @@ +use crate::allocator::*; use crate::arena::*; use crate::atom_table::*; use crate::fixtures::*; @@ -96,7 +97,7 @@ impl<'a> ArithInstructionIterator<'a> { pub(crate) enum ArithTermRef<'a> { Literal(&'a Literal), Op(Atom, usize), // name, arity. - Var(&'a Cell, Rc), + Var(Level, &'a Cell, Rc), } impl<'a> Iterator for ArithInstructionIterator<'a> { @@ -124,8 +125,11 @@ impl<'a> Iterator for ArithInstructionIterator<'a> { } } TermIterState::Literal(_, _, c) => return Some(Ok(ArithTermRef::Literal(c))), - TermIterState::Var(_, cell, var) => { - return Some(Ok(ArithTermRef::Var(cell, var.clone()))); + TermIterState::Var(lvl, cell, var) => { + // the expression is the second argument of an + // is/2 but the iterator can't see that, so the + // level needs to be demoted manually. + return Some(Ok(ArithTermRef::Var(lvl.child_level(), cell, var.clone()))); } _ => { return Some(Err(ArithmeticError::NonEvaluableFunctor( @@ -141,8 +145,8 @@ impl<'a> Iterator for ArithInstructionIterator<'a> { } #[derive(Debug)] -pub(crate) struct ArithmeticEvaluator<'a> { - bindings: &'a AllocVarDict, +pub(crate) struct ArithmeticEvaluator<'a, TermMarker> { + marker: &'a mut TermMarker, interm: Vec, interm_c: usize, } @@ -182,10 +186,10 @@ fn push_literal(interm: &mut Vec, c: &Literal) -> Result<(), Ari Ok(()) } -impl<'a> ArithmeticEvaluator<'a> { - pub(crate) fn new(bindings: &'a AllocVarDict, target_int: usize) -> Self { +impl<'a, TermMarker: Allocator> ArithmeticEvaluator<'a, TermMarker> { + pub(crate) fn new(marker: &'a mut TermMarker, target_int: usize) -> Self { ArithmeticEvaluator { - bindings, + marker, interm: Vec::new(), interm_c: target_int, } @@ -311,20 +315,46 @@ impl<'a> ArithmeticEvaluator<'a> { } } - pub(crate) fn eval(&mut self, src: &'a Term) -> Result { + pub(crate) fn eval( + &mut self, + src: &'a Term, + term_loc: GenContext, + ) -> Result + { let mut code = vec![]; let mut iter = src.iter()?; while let Some(term_ref) = iter.next() { match term_ref? { ArithTermRef::Literal(c) => push_literal(&mut self.interm, c)?, - ArithTermRef::Var(cell, name) => { + ArithTermRef::Var(lvl, cell, name) => { let r = if cell.get().norm().reg_num() == 0 { - match self.bindings.get(&name) { - Some(&VarData::Temp(_, t, _)) if t != 0 => RegType::Temp(t), - Some(&VarData::Perm(p)) if p != 0 => RegType::Perm(p), - _ => return Err(ArithmeticError::UninstantiatedVar), - } + let mut getter = || { + use crate::targets::QueryInstruction; + + loop { + match self.marker.bindings().get(&name) { + Some(&VarData::Temp(_, t, _)) if t != 0 => + return RegType::Temp(t), + Some(&VarData::Perm(p)) if p != 0 => + return RegType::Perm(p), + _ => { + self.marker.mark_var::( + name.clone(), + lvl, + cell, + term_loc, + &mut code, + ); + } + } + } + }; + + getter() + /* + _ => return Err(ArithmeticError::UninstantiatedVar), + */ } else { cell.get().norm() }; diff --git a/src/codegen.rs b/src/codegen.rs index 0b651be9..61390257 100644 --- a/src/codegen.rs +++ b/src/codegen.rs @@ -208,7 +208,7 @@ pub(crate) struct CodeGenerator<'a, TermMarker> { global_jmp_by_locs_offset: usize, } -impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { +impl<'b, TermMarker: Allocator> CodeGenerator<'b, TermMarker> { pub(crate) fn new(atom_tbl: &'b mut AtomTable, settings: CodeGenSettings) -> Self { CodeGenerator { atom_tbl, @@ -221,7 +221,7 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { } } - fn update_var_count>>(&mut self, iter: Iter) { + fn update_var_count<'a, Iter: Iterator>>(&mut self, iter: Iter) { for term in iter { if let TermRef::Var(_, _, var) = term { let entry = self.var_count.entry(var).or_insert(0); @@ -230,7 +230,7 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { } } - fn get_var_count(&self, var: &'a String) -> usize { + fn get_var_count(&self, var: &String) -> usize { *self.var_count.get(var).unwrap() } @@ -238,7 +238,7 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { &mut self, name: Rc, term_loc: GenContext, - vr: &'a Cell, + vr: &Cell, code: &mut Code, ) -> RegType { let mut target = Code::new(); @@ -256,7 +256,7 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { name: Rc, arg: usize, term_loc: GenContext, - vr: &'a Cell, + vr: &Cell, code: &mut Code, ) -> RegType { match self.marker.bindings().get(&name) { @@ -273,7 +273,7 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { } } - fn add_or_increment_void_instr(target: &mut Code) + fn add_or_increment_void_instr<'a, Target>(target: &mut Code) where Target: crate::targets::CompilationTarget<'a>, { @@ -287,10 +287,10 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { target.push(Target::to_void(1)); } - fn deep_var_instr>( + fn deep_var_instr<'a, Target: crate::targets::CompilationTarget<'a>>( &mut self, cell: &'a Cell, - var: &'a Rc, + var: &Rc, term_loc: GenContext, is_exposed: bool, target: &mut Code, @@ -302,7 +302,7 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { } } - fn subterm_to_instr>( + fn subterm_to_instr<'a, Target: crate::targets::CompilationTarget<'a>>( &mut self, subterm: &'a Term, term_loc: GenContext, @@ -331,7 +331,7 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { }; } - fn compile_target( + fn compile_target<'a, Target, Iter>( &mut self, iter: Iter, term_loc: GenContext, @@ -413,7 +413,7 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { target } - fn collect_var_data(&mut self, mut iter: ChunkedIterator<'a>) -> ConjunctInfo<'a> { + fn collect_var_data<'a>(&mut self, mut iter: ChunkedIterator<'a>) -> ConjunctInfo<'a> { let mut vs = VariableFixtures::new(); while let Some((chunk_num, lt_arity, chunked_terms)) = iter.next() { @@ -490,7 +490,7 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { dealloc_index } - fn compile_inlined( + fn compile_inlined<'a>( &mut self, ct: &InlinedClauseType, terms: &'a Vec, @@ -501,8 +501,8 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { &InlinedClauseType::CompareNumber(mut cmp) => { self.marker.reset_arg(2); - let (mut lcode, at_1) = self.call_arith_eval(&terms[0], 1)?; - let (mut rcode, at_2) = self.call_arith_eval(&terms[1], 2)?; + let (mut lcode, at_1) = self.compile_arith_expr(&terms[0], 1, term_loc)?; + let (mut rcode, at_2) = self.compile_arith_expr(&terms[1], 2, term_loc)?; let at_1 = if let &Term::Var(ref vr, ref name) = &terms[0] { ArithmeticTerm::Reg(self.mark_non_callable(name.clone(), 1, term_loc, vr, code)) @@ -655,74 +655,63 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { Ok(()) } - fn call_arith_eval( + fn compile_arith_expr( &mut self, - term: &'a Term, + term: &Term, target_int: usize, + term_loc: GenContext, ) -> Result { - let mut evaluator = ArithmeticEvaluator::new(&self.marker.bindings(), target_int); - evaluator.eval(term) + let mut evaluator = ArithmeticEvaluator::new(&mut self.marker, target_int); + evaluator.eval(term, term_loc) } fn compile_is_call( &mut self, - terms: &'a Vec, + terms: &Vec, code: &mut Code, term_loc: GenContext, use_default_call_policy: bool, ) -> Result<(), CompilationError> { - let (mut acode, at) = self.call_arith_eval(&terms[1], 1)?; - code.append(&mut acode); + macro_rules! compile_expr { + ($self:expr, $terms:expr, $term_loc:expr, $code:expr) => ({ + let (acode, at) = $self.compile_arith_expr(&$terms[1], 1, $term_loc)?; + $code.extend(acode.into_iter()); + at + }); + } self.marker.reset_arg(2); - match &terms[0] { + let at = match &terms[0] { &Term::Var(ref vr, ref name) => { - let mut target = vec![]; - self.marker.mark_var::( name.clone(), Level::Shallow, vr, term_loc, - &mut target, + code, ); - if !target.is_empty() { - code.extend(target.into_iter()); - } - } - &Term::Literal(_, c @ Literal::Integer(_)) - | &Term::Literal(_, c @ Literal::Fixnum(_)) => { - let v = HeapCellValue::from(c); - code.push(instr!("put_constant", Level::Shallow, v, temp_v!(1))); - - self.marker.advance_arg(); - } - &Term::Literal(_, c @ Literal::Float(_)) => { - let v = HeapCellValue::from(c); - code.push(instr!("put_constant", Level::Shallow, v, temp_v!(1))); - - self.marker.advance_arg(); + compile_expr!(self, terms, term_loc, code) } - &Term::Literal(_, c @ Literal::Rational(_)) => { + &Term::Literal(_, c @ Literal::Integer(_) | + c @ Literal::Float(_) | + c @ Literal::Rational(_) | + c @ Literal::Fixnum(_)) => { let v = HeapCellValue::from(c); code.push(instr!("put_constant", Level::Shallow, v, temp_v!(1))); self.marker.advance_arg(); + compile_expr!(self, terms, term_loc, code) } _ => { code.push(instr!("$fail", 0)); return Ok(()); } - } - - let at = if let &Term::Var(ref vr, ref name) = &terms[1] { - ArithmeticTerm::Reg(self.mark_non_callable(name.clone(), 2, term_loc, vr, code)) - } else { - at.unwrap_or(interm!(1)) }; + let at = at.unwrap_or(interm!(1)); + Ok(if use_default_call_policy { code.push(instr!("is", default, temp_v!(1), at, 0)); } else { @@ -731,7 +720,7 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { } #[inline] - fn compile_unblocked_cut(&mut self, code: &mut Code, cell: &'a Cell) { + fn compile_unblocked_cut(&mut self, code: &mut Code, cell: &Cell) { let r = self.marker.get(Rc::new(String::from("!"))); cell.set(VarReg::Norm(r)); code.push(instr!("$set_cp", cell.get().norm(), 0)); @@ -740,7 +729,7 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { fn compile_get_level_and_unify( &mut self, code: &mut Code, - cell: &'a Cell, + cell: &Cell, var: Rc, term_loc: GenContext, ) { @@ -756,7 +745,7 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { code.push(instr!("get_level_and_unify", cell.get().norm())); } - fn compile_seq( + fn compile_seq<'a>( &mut self, iter: ChunkedIterator<'a>, conjunct_info: &ConjunctInfo<'a>, @@ -820,10 +809,10 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { } } - fn compile_cleanup( + fn compile_cleanup<'a>( &mut self, code: &mut Code, - conjunct_info: &ConjunctInfo, + conjunct_info: &ConjunctInfo<'a>, toc: &'a QueryTerm, ) { // add a proceed to bookend any trailing cuts. @@ -850,10 +839,7 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { } } - pub(crate) fn compile_rule<'c: 'a>( - &mut self, - rule: &'c Rule, - ) -> Result { + pub(crate) fn compile_rule(&mut self, rule: &Rule) -> Result { let iter = ChunkedIterator::from_rule(rule); let conjunct_info = self.collect_var_data(iter); @@ -907,7 +893,7 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { UnsafeVarMarker::from_safe_vars(safe_vars) } - pub(crate) fn compile_fact<'c: 'a>(&mut self, term: &'c Term) -> Code { + pub(crate) fn compile_fact(&mut self, term: &Term) -> Code { self.update_var_count(post_order_iter(term)); let mut vs = VariableFixtures::new(); @@ -942,7 +928,7 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { fn compile_query_line( &mut self, - term: &'a QueryTerm, + term: &QueryTerm, term_loc: GenContext, code: &mut Code, num_perm_vars_left: usize, @@ -1029,9 +1015,9 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { subseqs } - fn compile_pred_subseq<'c: 'a, I: Indexer>( + fn compile_pred_subseq( &mut self, - clauses: &'c [PredicateClause], + clauses: &[PredicateClause], optimal_index: usize, ) -> Result { let mut code = VecDeque::new(); @@ -1121,19 +1107,12 @@ impl<'a, 'b: 'a, TermMarker: Allocator<'a>> CodeGenerator<'b, TermMarker> { Ok(Vec::from(code)) } - pub(crate) fn compile_predicate<'c: 'a>( + pub(crate) fn compile_predicate( &mut self, - clauses: &'c Vec, + clauses: &Vec, ) -> Result { let mut code = Code::new(); - /* - let optimal_index = match Self::first_instantiated_index(&clauses) { - Some(index) => index, - None => 0, // Default to first argument indexing. - }; - */ - let split_pred = Self::split_predicate(&clauses); let multi_seq = split_pred.len() > 1; diff --git a/src/debray_allocator.rs b/src/debray_allocator.rs index 9c688858..2161d20e 100644 --- a/src/debray_allocator.rs +++ b/src/debray_allocator.rs @@ -126,10 +126,11 @@ impl DebrayAllocator { } } - fn evacuate_arg<'a, Target>(&mut self, chunk_num: usize, target: &mut Vec) - where - Target: CompilationTarget<'a>, - { + fn evacuate_arg<'a, Target: CompilationTarget<'a>>( + &mut self, + chunk_num: usize, + code: &mut Code, + ) { match self.alloc_in_last_goal_hint(chunk_num) { Some((var, r)) => { let k = self.arg_c; @@ -137,7 +138,7 @@ impl DebrayAllocator { if r != k { let r = RegType::Temp(r); - target.push(Target::move_to_register(r, k)); + code.push(Target::move_to_register(r, k)); self.contents.swap_remove(&k); self.contents.insert(r.reg_num(), var.clone()); @@ -207,7 +208,7 @@ impl DebrayAllocator { } } -impl<'a> Allocator<'a> for DebrayAllocator { +impl Allocator for DebrayAllocator { fn new() -> DebrayAllocator { DebrayAllocator { arity: 0, @@ -219,42 +220,37 @@ impl<'a> Allocator<'a> for DebrayAllocator { } } - fn mark_anon_var( + fn mark_anon_var<'a, Target: CompilationTarget<'a>>( &mut self, lvl: Level, term_loc: GenContext, - target: &mut Vec, - ) - where - Target: CompilationTarget<'a>, - { + code: &mut Code, + ) { let r = RegType::Temp(self.alloc_reg_to_non_var()); match lvl { - Level::Deep => target.push(Target::subterm_to_variable(r)), + Level::Deep => code.push(Target::subterm_to_variable(r)), Level::Root | Level::Shallow => { let k = self.arg_c; if let GenContext::Last(chunk_num) = term_loc { - self.evacuate_arg::(chunk_num, target); + self.evacuate_arg::(chunk_num, code); } self.arg_c += 1; - target.push(Target::argument_to_variable(r, k)); + code.push(Target::argument_to_variable(r, k)); } }; } - fn mark_non_var( + fn mark_non_var<'a, Target: CompilationTarget<'a>>( &mut self, lvl: Level, term_loc: GenContext, - cell: &Cell, - target: &mut Vec, - ) where - Target: CompilationTarget<'a>, - { + cell: &'a Cell, + code: &mut Code, + ) { let r = cell.get(); let r = match lvl { @@ -262,7 +258,7 @@ impl<'a> Allocator<'a> for DebrayAllocator { let k = self.arg_c; if let GenContext::Last(chunk_num) = term_loc { - self.evacuate_arg::(chunk_num, target); + self.evacuate_arg::(chunk_num, code); } self.arg_c += 1; @@ -278,18 +274,18 @@ impl<'a> Allocator<'a> for DebrayAllocator { cell.set(r); } - fn mark_var>( + fn mark_var<'a, Target: CompilationTarget<'a>>( &mut self, var: Rc, lvl: Level, cell: &'a Cell, term_loc: GenContext, - target: &mut Vec, + code: &mut Code, ) { let (r, is_new_var) = match self.get(var.clone()) { RegType::Temp(0) => { // here, r is temporary *and* unassigned. - let o = self.alloc_reg_to_var::(&var, lvl, term_loc, target); + let o = self.alloc_reg_to_var::(&var, lvl, term_loc, code); cell.set(VarReg::Norm(RegType::Temp(o))); (RegType::Temp(o), true) @@ -303,16 +299,16 @@ impl<'a> Allocator<'a> for DebrayAllocator { r => (r, false), }; - self.mark_reserved_var::(var, lvl, cell, term_loc, target, r, is_new_var); + self.mark_reserved_var::(var, lvl, cell, term_loc, code, r, is_new_var); } - fn mark_reserved_var>( + fn mark_reserved_var<'a, Target: CompilationTarget<'a>>( &mut self, var: Rc, lvl: Level, cell: &'a Cell, term_loc: GenContext, - target: &mut Vec, + code: &mut Code, r: RegType, is_new_var: bool, ) { @@ -321,7 +317,7 @@ impl<'a> Allocator<'a> for DebrayAllocator { let k = self.arg_c; if self.is_curr_arg_distinct_from(&var) { - self.evacuate_arg::(term_loc.chunk_num(), target); + self.evacuate_arg::(term_loc.chunk_num(), code); } self.arg_c += 1; @@ -330,24 +326,24 @@ impl<'a> Allocator<'a> for DebrayAllocator { if !self.in_place(&var, term_loc, r, k) { if is_new_var { - target.push(Target::argument_to_variable(r, k)); + code.push(Target::argument_to_variable(r, k)); } else { - target.push(Target::argument_to_value(r, k)); + code.push(Target::argument_to_value(r, k)); } } } Level::Deep if is_new_var => { if let GenContext::Head = term_loc { if self.occurs_shallowly_in_head(&var, r.reg_num()) { - target.push(Target::subterm_to_value(r)); + code.push(Target::subterm_to_value(r)); } else { - target.push(Target::subterm_to_variable(r)); + code.push(Target::subterm_to_variable(r)); } } else { - target.push(Target::subterm_to_variable(r)); + code.push(Target::subterm_to_variable(r)); } } - Level::Deep => target.push(Target::subterm_to_value(r)), + Level::Deep => code.push(Target::subterm_to_value(r)), }; if !r.is_perm() { diff --git a/src/lib/builtins.pl b/src/lib/builtins.pl index c381b313..e21d441e 100644 --- a/src/lib/builtins.pl +++ b/src/lib/builtins.pl @@ -229,7 +229,7 @@ staggered_sc(G, _) :- call('$call'(G)). staggered_sc(_, G) :- call('$call'(G)). -! :- !. +!. :- non_counted_backtracking set_cp/1. -- 2.54.0