From cee2d5a9c498ba8cf741d175e7bf4c329193f9c9 Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Fri, 8 Dec 2017 21:38:18 -0700 Subject: [PATCH] don't truly truncate the heap. --- src/prolog/ast.rs | 62 +++++++++++++++++++- src/prolog/codegen.rs | 28 ++++----- src/prolog/indexing.rs | 10 ++-- src/prolog/io.rs | 4 ++ src/prolog/machine.rs | 128 +++++++++++++++-------------------------- 5 files changed, 129 insertions(+), 103 deletions(-) diff --git a/src/prolog/ast.rs b/src/prolog/ast.rs index 77d5ca02..cc0dd21f 100644 --- a/src/prolog/ast.rs +++ b/src/prolog/ast.rs @@ -10,7 +10,7 @@ use std::collections::{HashMap, VecDeque}; use std::fmt; use std::io::Error as IOError; use std::num::{ParseFloatError}; -use std::ops::{Add, AddAssign, Div, Sub, Mul, Neg}; +use std::ops::{Add, AddAssign, Div, Index, IndexMut, Sub, Mul, Neg}; use std::str::Utf8Error; use std::vec::Vec; @@ -957,7 +957,65 @@ impl AddAssign for CodePtr { } } -pub type Heap = Vec; +pub struct Heap { + heap: Vec, + pub h: usize +} + +impl Heap { + pub fn new() -> Self { + Heap { heap: vec![], h : 0 } + } + + pub fn with_capacity(cap: usize) -> Self { + Heap { heap: vec![HeapCellValue::Str(0); cap], h: 0 } + } + + pub fn push(&mut self, val: HeapCellValue) { + let h = self.h; + + if h < self.heap.len() { + self.heap[h] = val; + } else { + self.heap.push(val); + } + + self.h += 1; + } + + pub fn truncate(&mut self, h: usize) { + self.h = h; + } + + pub fn len(&self) -> usize { + self.heap.len() + } + + pub fn append(&mut self, vals: Vec) { + for val in vals.into_iter() { + self.push(val); + } + } + + pub fn clear(&mut self) { + self.heap.clear(); + self.h = 0; + } +} + +impl Index for Heap { + type Output = HeapCellValue; + + fn index(&self, index: usize) -> &Self::Output { + &self.heap[index] + } +} + +impl IndexMut for Heap { + fn index_mut(&mut self, index: usize) -> &mut Self::Output { + &mut self.heap[index] + } +} pub type Registers = Vec; diff --git a/src/prolog/codegen.rs b/src/prolog/codegen.rs index 2dac5839..c13ccea1 100644 --- a/src/prolog/codegen.rs +++ b/src/prolog/codegen.rs @@ -95,7 +95,7 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> let mut target = Vec::new(); self.marker.reset_arg(arity); - self.marker.mark_var(name, Level::Shallow, vr, term_loc, &mut target); + self.marker.mark_var(name, Level::Shallow, vr, term_loc, &mut target); code.push(Line::Query(target)); vr.get().norm() } @@ -233,15 +233,15 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> fn add_conditional_call_inlined(_: &InlinedQueryTerm, code: &mut Code) { code.push(proceed!()); - + /* match term { &InlinedQueryTerm::IsAtomic(_) | &InlinedQueryTerm::IsVar(_) => - code.push(proceed!()) + code.push(proceed!()) }; */ } - + fn add_conditional_call(code: &mut Code, qt: &QueryTerm, pvs: usize) { match qt { @@ -274,7 +274,7 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> if let Some(&mut Line::Control(ref mut ctrl)) = code.last_mut() { let mut instr = ControlInstruction::Proceed; swap(ctrl, &mut instr); - + match instr { ControlInstruction::Call(name, arity, _) => *ctrl = ControlInstruction::Execute(name, arity), @@ -293,7 +293,7 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> dealloc_index } - + fn compile_inlined(&mut self, term: &'a InlinedQueryTerm, term_loc: GenContext, code: &mut Code) -> Result<(), ParserError> { @@ -304,10 +304,10 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> code.append(&mut lcode); code.append(&mut rcode); - + code.push(compare_number_instr!(cmp, at_1.unwrap_or(interm!(1)), - at_2.unwrap_or(interm!(2)))); + at_2.unwrap_or(interm!(2)))); }, &InlinedQueryTerm::IsAtomic(ref inner_term) => match inner_term[0].as_ref() { @@ -321,7 +321,7 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> let r = self.mark_non_callable(name, 1, term_loc, vr, code); code.push(is_atomic!(r)); } - }, + }, &InlinedQueryTerm::IsVar(ref inner_term) => match inner_term[0].as_ref() { &Term::Constant(_, _) | &Term::Clause(_, _, _) | &Term::Cons(_, _, _) => { @@ -339,13 +339,13 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> Ok(()) } - + fn call_arith_eval(&self, term: &'a Term, target_int: usize) -> Result { let mut evaluator = ArithmeticEvaluator::new(self.marker.bindings(), target_int); evaluator.eval(term) } - + fn compile_seq(&mut self, iter: ChunkedIterator<'a>, conjunct_info: &ConjunctInfo<'a>, @@ -377,7 +377,7 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> }); }, &QueryTerm::Inlined(ref term) => - self.compile_inlined(term, term_loc, code)?, + self.compile_inlined(term, term_loc, code)?, &QueryTerm::Is(ref terms) => { let (mut acode, at) = try!(self.call_arith_eval(terms[1].as_ref(), 1)); code.append(&mut acode); @@ -409,7 +409,7 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> code.push(fail!()); } } - }, + }, _ if chunk_num == 0 => { self.marker.reset_arg(term.arity()); @@ -429,7 +429,7 @@ impl<'a, TermMarker: Allocator<'a>> CodeGenerator<'a, TermMarker> Ok(()) } - + fn compile_seq_prelude(&mut self, conjunct_info: &ConjunctInfo, body: &mut Code) { if conjunct_info.allocates() { diff --git a/src/prolog/indexing.rs b/src/prolog/indexing.rs index dc06f47a..f087c831 100644 --- a/src/prolog/indexing.rs +++ b/src/prolog/indexing.rs @@ -66,8 +66,7 @@ impl CodeOffsets { }; } - fn second_level_index(indices: HashMap, - prelude: &mut CodeDeque) + fn second_level_index(indices: HashMap, prelude: &mut CodeDeque) -> HashMap where Index: Eq + Hash { @@ -117,8 +116,7 @@ impl CodeOffsets { flattened_index } - fn switch_on_constant(con_ind: HashMap, - prelude: &mut CodeDeque) + fn switch_on_constant(con_ind: HashMap, prelude: &mut CodeDeque) -> IntIndex { let con_ind = Self::second_level_index(con_ind, prelude); @@ -150,8 +148,7 @@ impl CodeOffsets { } } - fn switch_on_structure(str_ind: HashMap<(Atom, usize), ThirdLevelIndex>, - prelude: &mut CodeDeque) + fn switch_on_structure(str_ind: HashMap<(Atom, usize), ThirdLevelIndex>, prelude: &mut CodeDeque) -> IntIndex { let str_ind = Self::second_level_index(str_ind, prelude); @@ -203,6 +200,7 @@ impl CodeOffsets { } } + pub fn add_indices(self, code: &mut Code, mut code_body: Code) { if self.no_indices() { diff --git a/src/prolog/io.rs b/src/prolog/io.rs index 298ecb35..c3043fb6 100644 --- a/src/prolog/io.rs +++ b/src/prolog/io.rs @@ -368,12 +368,14 @@ pub fn eval<'a, 'b: 'a>(wam: &'a mut Machine, tl: &'b TopLevel) -> EvalSession<' Err(e) => return EvalSession::ParserError(e) }; + print_code(&compiled_pred); wam.add_predicate(clauses, compiled_pred) }, &TopLevel::Fact(ref fact) => { let mut cg = CodeGenerator::::new(); let compiled_fact = cg.compile_fact(fact); + print_code(&compiled_fact); wam.add_fact(fact, compiled_fact) }, &TopLevel::Rule(ref rule) => { @@ -384,6 +386,7 @@ pub fn eval<'a, 'b: 'a>(wam: &'a mut Machine, tl: &'b TopLevel) -> EvalSession<' Err(e) => return EvalSession::ParserError(e) }; + print_code(&compiled_rule); wam.add_rule(rule, compiled_rule) }, &TopLevel::Query(ref query) => { @@ -394,6 +397,7 @@ pub fn eval<'a, 'b: 'a>(wam: &'a mut Machine, tl: &'b TopLevel) -> EvalSession<' Err(e) => return EvalSession::ParserError(e) }; + print_code(&compiled_query); wam.submit_query(compiled_query, cg.take_vars()) } } diff --git a/src/prolog/machine.rs b/src/prolog/machine.rs index 73d5eb8f..aea29904 100644 --- a/src/prolog/machine.rs +++ b/src/prolog/machine.rs @@ -22,7 +22,6 @@ enum MachineMode { } struct MachineState { - h: usize, s: usize, p: CodePtr, b: usize, @@ -40,7 +39,7 @@ struct MachineState { tr: usize, hb: usize, block: usize, // an offset into the OR stack. - ball: (usize, Heap), // heap boundary, and a term copy + ball: (usize, Vec), // heap boundary, and a term copy interms: Vec // intermediate numbers. } @@ -71,16 +70,16 @@ impl<'a> IndexMut for DuplicateTerm<'a> { // the ordinary, heap term copier, used by duplicate_term. impl<'a> CopierTarget for DuplicateTerm<'a> { fn source(&self) -> usize { - self.state.h + self.state.heap.h } fn threshold(&self) -> usize { - self.state.h + self.state.heap.h } fn push(&mut self, hcv: HeapCellValue) { self.state.heap.push(hcv); - self.state.h += 1; + self.state.heap.h += 1; } fn store(&self, a: Addr) -> Addr { @@ -444,7 +443,7 @@ impl Machine { fn fail<'a>(&mut self) -> EvalSession<'a> { if self.ms.ball.1.len() > 0 { - let h = self.ms.h; + let h = self.ms.heap.h; self.ms.copy_and_align_ball_to_heap(); EvalSession::QueryFailureWithException(self.print_term(&Addr::HeapCell(h))) @@ -620,8 +619,7 @@ macro_rules! try_or_fail { impl MachineState { fn new() -> MachineState { - MachineState { h: 0, - s: 0, + MachineState { s: 0, p: CodePtr::default(), b: 0, b0: 0, @@ -629,7 +627,7 @@ impl MachineState { num_of_args: 0, cp: CodePtr::default(), fail: false, - heap: Vec::with_capacity(256), + heap: Heap::with_capacity(256), mode: MachineMode::Write, and_stack: AndStack::new(), or_stack: OrStack::new(), @@ -646,7 +644,7 @@ impl MachineState { fn num_frames(&self) -> usize { self.and_stack.len() + self.or_stack.len() } - + fn store(&self, a: Addr) -> Addr { match a { Addr::HeapCell(r) => self.heap[r].as_addr(r), @@ -1155,21 +1153,19 @@ impl MachineState { match self.store(addr.clone()) { Addr::HeapCell(hc) => { - let h = self.h; + let h = self.heap.h; self.heap.push(HeapCellValue::Lis(h+1)); self.bind(Ref::HeapCell(hc), Addr::HeapCell(h)); - self.h += 1; self.mode = MachineMode::Write; }, Addr::StackCell(fr, sc) => { - let h = self.h; + let h = self.heap.h; self.heap.push(HeapCellValue::Lis(h+1)); self.bind(Ref::StackCell(fr, sc), Addr::HeapCell(h)); - self.h += 1; self.mode = MachineMode::Write; }, Addr::Lis(a) => { @@ -1196,14 +1192,13 @@ impl MachineState { } }, Addr::HeapCell(_) | Addr::StackCell(_, _) => { - self.heap.push(HeapCellValue::Str(self.h + 1)); + let h = self.heap.h; + + self.heap.push(HeapCellValue::Str(h + 1)); self.heap.push(HeapCellValue::NamedStr(arity, name.clone())); - let h = self.h; - self.bind(addr.as_ref().unwrap(), Addr::HeapCell(h)); - self.h += 2; self.mode = MachineMode::Write; }, _ => self.fail = true @@ -1225,7 +1220,6 @@ impl MachineState { }, MachineMode::Write => { self.heap.push(HeapCellValue::Con(c.clone())); - self.h += 1; } }; @@ -1236,11 +1230,10 @@ impl MachineState { MachineMode::Read => self[reg] = self.heap[self.s].as_addr(self.s), MachineMode::Write => { - let h = self.h; + let h = self.heap.h; self.heap.push(HeapCellValue::Ref(Ref::HeapCell(h))); - self[reg] = Addr::HeapCell(self.h); - self.h += 1; + self[reg] = Addr::HeapCell(h); } }; @@ -1256,14 +1249,13 @@ impl MachineState { }, MachineMode::Write => { let addr = self.deref(self[reg].clone()); - let h = self.h; + let h = self.heap.h; if let Addr::HeapCell(hc) = addr { if hc < h { let val = self.heap[hc].clone(); + self.heap.push(val); - - self.h += 1; self.s += 1; return; @@ -1272,8 +1264,6 @@ impl MachineState { self.heap.push(HeapCellValue::Ref(Ref::HeapCell(h))); self.bind(Ref::HeapCell(h), addr); - - self.h += 1; } }; @@ -1290,7 +1280,6 @@ impl MachineState { MachineMode::Write => { let heap_val = self.store(self[reg].clone()); self.heap.push(HeapCellValue::from(heap_val)); - self.h += 1; } }; @@ -1301,13 +1290,11 @@ impl MachineState { MachineMode::Read => self.s += n, MachineMode::Write => { - let h = self.h; + let h = self.heap.h; for i in h .. h + n { self.heap.push(HeapCellValue::Ref(Ref::HeapCell(i))); } - - self.h += n; } }; } @@ -1384,11 +1371,12 @@ impl MachineState { &QueryInstruction::PutConstant(_, ref constant, reg) => self[reg] = Addr::Con(constant.clone()), &QueryInstruction::PutList(_, reg) => - self[reg] = Addr::Lis(self.h), + self[reg] = Addr::Lis(self.heap.h), &QueryInstruction::PutStructure(_, ref name, arity, reg) => { + let h = self.heap.h; + self.heap.push(HeapCellValue::NamedStr(arity, name.clone())); - self[reg] = Addr::Str(self.h); - self.h += 1; + self[reg] = Addr::Str(h); }, &QueryInstruction::PutUnsafeValue(n, arg) => { let e = self.e; @@ -1397,13 +1385,12 @@ impl MachineState { if addr.is_protected(e) { self.registers[arg] = self.store(addr); } else { - let h = self.h; + let h = self.heap.h; self.heap.push(HeapCellValue::Ref(Ref::HeapCell(h))); self.bind(Ref::HeapCell(h), addr); self.registers[arg] = self.heap[h].as_addr(h); - self.h += 1; } }, &QueryInstruction::PutValue(norm, arg) => @@ -1417,58 +1404,46 @@ impl MachineState { self.registers[arg] = self[norm].clone(); }, RegType::Temp(_) => { - let h = self.h; + let h = self.heap.h; self.heap.push(HeapCellValue::Ref(Ref::HeapCell(h))); self[norm] = Addr::HeapCell(h); self.registers[arg] = Addr::HeapCell(h); - - self.h += 1; } }; }, &QueryInstruction::SetConstant(ref constant) => { self.heap.push(HeapCellValue::Con(constant.clone())); - self.h += 1; }, &QueryInstruction::SetLocalValue(reg) => { let addr = self.deref(self[reg].clone()); - let h = self.h; + let h = self.heap.h; if let Addr::HeapCell(hc) = addr { if hc < h { self.heap.push(HeapCellValue::from(addr)); - self.h += 1; return; } } self.heap.push(HeapCellValue::Ref(Ref::HeapCell(h))); self.bind(Ref::HeapCell(h), addr); - - self.h += 1; }, &QueryInstruction::SetVariable(reg) => { - let h = self.h; + let h = self.heap.h; self.heap.push(HeapCellValue::Ref(Ref::HeapCell(h))); self[reg] = Addr::HeapCell(h); - - self.h += 1; }, &QueryInstruction::SetValue(reg) => { let heap_val = self[reg].clone(); self.heap.push(HeapCellValue::from(heap_val)); - - self.h += 1; }, &QueryInstruction::SetVoid(n) => { - let h = self.h; + let h = self.heap.h; for i in h .. h + n { self.heap.push(HeapCellValue::Ref(Ref::HeapCell(i))); } - - self.h += n; } } } @@ -1528,13 +1503,12 @@ impl MachineState { self.p = CodePtr::DirEntry(59); } - fn throw_exception(&mut self, mut hcv: Vec) { - let h = self.h; + fn throw_exception(&mut self, hcv: Vec) { + let h = self.heap.h; self.registers[1] = Addr::HeapCell(h); - self.h += hcv.len(); - - self.heap.append(&mut hcv); + + self.heap.append(hcv); self.goto_throw(); } @@ -1586,8 +1560,8 @@ impl MachineState { } fn copy_and_align_ball_to_heap(&mut self) { - let diff = self.ball.0 - self.h; - + let diff = self.ball.0 - self.heap.h; + for heap_value in self.ball.1.iter().cloned() { self.heap.push(match heap_value { HeapCellValue::Con(c) => HeapCellValue::Con(c), @@ -1598,8 +1572,6 @@ impl MachineState { _ => heap_value }); } - - self.h += self.ball.1.len(); } fn execute_built_in_instr(&mut self, code_dir: &CodeDir, instr: &BuiltInInstruction) @@ -1622,7 +1594,7 @@ impl MachineState { self.p += 1; }, &BuiltInInstruction::DuplicateTerm => { - let old_h = self.h; + let old_h = self.heap.h; let a1 = self[temp_v!(1)].clone(); let a2 = self[temp_v!(2)].clone(); @@ -1652,7 +1624,7 @@ impl MachineState { }, &BuiltInInstruction::GetBall => { let addr = self.store(self.deref(self[temp_v!(1)].clone())); - let h = self.h; + let h = self.heap.h; if self.ball.1.len() > 0 { self.copy_and_align_ball_to_heap(); @@ -1673,7 +1645,7 @@ impl MachineState { }, &BuiltInInstruction::SetBall => { let addr = self[temp_v!(1)].clone(); - self.ball.0 = self.h; + self.ball.0 = self.heap.h; { let mut duplicator = DuplicateBallTerm::new(self); @@ -1865,7 +1837,7 @@ impl MachineState { self.b, self.p + 1, self.tr, - self.h, + self.heap.h, self.b0, self.num_of_args); @@ -1876,7 +1848,7 @@ impl MachineState { self.or_stack[b][i] = self.registers[i].clone(); } - self.hb = self.h; + self.hb = self.heap.h; self.p += l; }, &IndexedChoiceInstruction::Retry(l) => { @@ -1901,8 +1873,7 @@ impl MachineState { self.trail.truncate(self.tr); self.heap.truncate(self.or_stack[b].h); - self.h = self.or_stack[b].h; - self.hb = self.h; + self.hb = self.heap.h; self.p += l; }, @@ -1925,14 +1896,12 @@ impl MachineState { self.tr = self.or_stack[b].tr; self.trail.truncate(self.tr); - self.h = self.or_stack[b].h; - self.heap.truncate(self.h); - + self.heap.truncate(self.or_stack[b].h); self.b = self.or_stack[b].b; self.or_stack.pop(); - self.hb = self.h; + self.hb = self.heap.h; self.p += l; }, }; @@ -1951,7 +1920,7 @@ impl MachineState { self.b, self.p + offset, self.tr, - self.h, + self.heap.h, self.b0, self.num_of_args); @@ -1962,7 +1931,7 @@ impl MachineState { self.or_stack[b][i] = self.registers[i].clone(); } - self.hb = self.h; + self.hb = self.heap.h; self.p += 1; }, &ChoiceInstruction::RetryMeElse(offset) => { @@ -1987,8 +1956,7 @@ impl MachineState { self.trail.truncate(self.tr); self.heap.truncate(self.or_stack[b].h); - self.h = self.or_stack[b].h; - self.hb = self.h; + self.hb = self.heap.h; self.p += 1; }, @@ -2011,14 +1979,13 @@ impl MachineState { self.tr = self.or_stack[b].tr; self.trail.truncate(self.tr); - self.h = self.or_stack[b].h; - self.heap.truncate(self.h); + self.heap.truncate(self.or_stack[b].h); self.b = self.or_stack[b].b; self.or_stack.pop(); - self.hb = self.h; + self.hb = self.heap.h; self.p += 1; } } @@ -2045,7 +2012,7 @@ impl MachineState { &CutInstruction::GetLevel => { let b0 = self.b0; let e = self.e; - + self.and_stack[e].b0 = b0; self.p += 1; }, @@ -2068,7 +2035,6 @@ impl MachineState { } fn reset(&mut self) { - self.h = 0; self.hb = 0; self.e = 0; self.b = 0; -- 2.54.0