From f41b5f465e6c383321aeb144c7f6b2e1a74cf5af Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Fri, 22 Feb 2019 00:56:04 -0700 Subject: [PATCH] add findall/3 --- src/prolog/copier.rs | 4 +- src/prolog/heap.rs | 71 ++++++++++++++++++ src/prolog/instructions.rs | 91 ++++++----------------- src/prolog/lib/builtins.pl | 23 +++++- src/prolog/machine/machine_state.rs | 53 +++++++------ src/prolog/machine/machine_state_impl.rs | 15 ++-- src/prolog/machine/mod.rs | 2 +- src/prolog/machine/system_calls.rs | 95 ++++++++++++++++++++++-- src/prolog/mod.rs | 1 + src/tests.rs | 14 ++++ 10 files changed, 255 insertions(+), 114 deletions(-) create mode 100644 src/prolog/heap.rs diff --git a/src/prolog/copier.rs b/src/prolog/copier.rs index 13c912aa..96e4ce5e 100644 --- a/src/prolog/copier.rs +++ b/src/prolog/copier.rs @@ -7,7 +7,6 @@ type Trail = Vec<(Ref, HeapCellValue)>; pub(crate) trait CopierTarget: IndexMut { - fn source(&self) -> usize; fn threshold(&self) -> usize; fn push(&mut self, HeapCellValue); fn store(&self, Addr) -> Addr; @@ -33,7 +32,7 @@ impl CopyTermState { fn new(target: T) -> Self { CopyTermState { trail: vec![], - scan: target.source(), + scan: 0, old_h: target.threshold(), target } @@ -168,6 +167,7 @@ impl CopyTermState { } fn copy_term_impl(&mut self, addr: Addr) { + self.scan = self.target.threshold(); self.target.push(HeapCellValue::Addr(addr)); while self.scan < self.target.threshold() { diff --git a/src/prolog/heap.rs b/src/prolog/heap.rs new file mode 100644 index 00000000..d929e86a --- /dev/null +++ b/src/prolog/heap.rs @@ -0,0 +1,71 @@ +use prolog_parser::ast::*; + +use prolog::instructions::*; + +use std::ops::{Index, IndexMut}; + +pub struct Heap { + heap: Vec, + pub h: usize, +} + +impl Heap { + pub fn with_capacity(cap: usize) -> Self { + Heap { heap: Vec::with_capacity(cap), + h: 0 } + } + + pub fn push(&mut self, val: HeapCellValue) { + self.heap.push(val); + self.h += 1; + } + + pub fn truncate(&mut self, h: usize) { + self.h = h; + self.heap.truncate(h); + } + + pub fn len(&self) -> usize { + self.heap.len() + } + + pub fn append(&mut self, vals: Vec) { + let n = vals.len(); + + self.heap.extend(vals.into_iter()); + self.h += n; + } + + pub fn clear(&mut self) { + self.heap.clear(); + self.h = 0; + } + + pub fn to_list>(&mut self, values: Iter) -> usize { + let head_addr = self.h; + + for value in values { + let h = self.h; + + self.push(HeapCellValue::Addr(Addr::Lis(h+1))); + self.push(HeapCellValue::Addr(value)); + } + + self.push(HeapCellValue::Addr(Addr::Con(Constant::EmptyList))); + head_addr + } +} + +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] + } +} diff --git a/src/prolog/instructions.rs b/src/prolog/instructions.rs index 43462e87..875921bc 100644 --- a/src/prolog/instructions.rs +++ b/src/prolog/instructions.rs @@ -4,7 +4,7 @@ use prolog_parser::tabled_rc::*; use std::cell::{Cell, RefCell}; use std::collections::{BTreeSet, HashMap, VecDeque}; use std::cmp::Ordering; -use std::ops::{Add, AddAssign, Index, IndexMut, Sub}; +use std::ops::{Add, AddAssign, Sub, SubAssign}; use std::rc::Rc; #[derive(Clone, PartialEq)] @@ -238,6 +238,7 @@ pub struct Module { #[derive(Copy, Clone, PartialEq)] pub enum SystemClauseType { CheckCutPoint, + CopyToLiftedHeap, DeleteAttribute, DeleteHeadAttribute, DynamicModuleResolution, @@ -245,13 +246,16 @@ pub enum SystemClauseType { EnqueueAttributedVar, ExpandGoal, ExpandTerm, + TruncateIfNoLiftedHeapGrowth, GetAttributedVariableList, GetAttrVarQueueDelimiter, - GetAttrVarQueueBeyond, + GetAttrVarQueueBeyond, GetBValue, + GetLiftedHeapFromOffset, GetSCCCleaner, InstallSCCCleaner, InstallInferenceCounter, + LiftedHeapLength, ModuleOf, RedoAttrVarBindings, RemoveCallPolicyCheck, @@ -282,8 +286,9 @@ pub enum SystemClauseType { impl SystemClauseType { pub fn name(&self) -> ClauseName { - match self { + match self { &SystemClauseType::CheckCutPoint => clause_name!("$check_cp"), + &SystemClauseType::CopyToLiftedHeap => clause_name!("$copy_to_lh"), &SystemClauseType::DeleteAttribute => clause_name!("$del_attr_non_head"), &SystemClauseType::DeleteHeadAttribute => clause_name!("$del_attr_head"), &SystemClauseType::DynamicModuleResolution => clause_name!("$module_call"), @@ -291,14 +296,17 @@ impl SystemClauseType { &SystemClauseType::EnqueueAttributedVar => clause_name!("$enqueue_attr_var"), &SystemClauseType::ExpandTerm => clause_name!("$expand_term"), &SystemClauseType::ExpandGoal => clause_name!("$expand_goal"), + &SystemClauseType::TruncateIfNoLiftedHeapGrowth => clause_name!("$truncate_if_no_lh_growth"), &SystemClauseType::GetAttributedVariableList => clause_name!("$get_attr_list"), &SystemClauseType::GetAttrVarQueueDelimiter => clause_name!("$get_attr_var_queue_delim"), &SystemClauseType::GetAttrVarQueueBeyond => clause_name!("$get_attr_var_queue_beyond"), + &SystemClauseType::GetLiftedHeapFromOffset => clause_name!("$get_lh_from_offset"), &SystemClauseType::GetBValue => clause_name!("$get_b_value"), &SystemClauseType::GetDoubleQuotes => clause_name!("$get_double_quotes"), &SystemClauseType::GetSCCCleaner => clause_name!("$get_scc_cleaner"), &SystemClauseType::InstallSCCCleaner => clause_name!("$install_scc_cleaner"), &SystemClauseType::InstallInferenceCounter => clause_name!("$install_inference_counter"), + &SystemClauseType::LiftedHeapLength => clause_name!("$lh_length"), &SystemClauseType::ModuleOf => clause_name!("$module_of"), &SystemClauseType::RedoAttrVarBindings => clause_name!("$redo_attr_var_bindings"), &SystemClauseType::RemoveCallPolicyCheck => clause_name!("$remove_call_policy_check"), @@ -328,8 +336,9 @@ impl SystemClauseType { } pub fn from(name: &str, arity: usize) -> Option { - match (name, arity) { + match (name, arity) { ("$check_cp", 1) => Some(SystemClauseType::CheckCutPoint), + ("$copy_to_lh", 2) => Some(SystemClauseType::CopyToLiftedHeap), ("$del_attr_non_head", 1) => Some(SystemClauseType::DeleteAttribute), ("$del_attr_head", 1) => Some(SystemClauseType::DeleteHeadAttribute), ("$module_call", 2) => Some(SystemClauseType::DynamicModuleResolution), @@ -337,12 +346,15 @@ impl SystemClauseType { ("$enqueue_attr_var", 1) => Some(SystemClauseType::EnqueueAttributedVar), ("$expand_term", 2) => Some(SystemClauseType::ExpandTerm), ("$expand_goal", 2) => Some(SystemClauseType::ExpandGoal), + ("$truncate_if_no_lh_growth", 1) => Some(SystemClauseType::TruncateIfNoLiftedHeapGrowth), ("$get_attr_list", 2) => Some(SystemClauseType::GetAttributedVariableList), ("$get_b_value", 1) => Some(SystemClauseType::GetBValue), + ("$get_lh_from_offset", 2) => Some(SystemClauseType::GetLiftedHeapFromOffset), ("$get_double_quotes", 1) => Some(SystemClauseType::GetDoubleQuotes), ("$get_scc_cleaner", 1) => Some(SystemClauseType::GetSCCCleaner), ("$install_scc_cleaner", 2) => Some(SystemClauseType::InstallSCCCleaner), ("$install_inference_counter", 3) => Some(SystemClauseType::InstallInferenceCounter), + ("$lh_length", 1) => Some(SystemClauseType::LiftedHeapLength), ("$module_of", 2) => Some(SystemClauseType::ModuleOf), ("$redo_attr_var_bindings", 0) => Some(SystemClauseType::RedoAttrVarBindings), ("$remove_call_policy_check", 1) => Some(SystemClauseType::RemoveCallPolicyCheck), @@ -834,6 +846,12 @@ impl Sub for Addr { } } +impl SubAssign for Addr { + fn sub_assign(&mut self, rhs: usize) { + *self = self.clone() - rhs; + } +} + impl From for Addr { fn from(r: Ref) -> Self { match r { @@ -1067,71 +1085,6 @@ impl AddAssign for CodePtr { } } -pub struct Heap { - heap: Vec, - pub h: usize -} - -impl Heap { - pub fn with_capacity(cap: usize) -> Self { - Heap { heap: Vec::with_capacity(cap), h: 0 } - } - - pub fn push(&mut self, val: HeapCellValue) { - self.heap.push(val); - self.h += 1; - } - - pub fn truncate(&mut self, h: usize) { - self.h = h; - self.heap.truncate(h); - } - - pub fn len(&self) -> usize { - self.heap.len() - } - - pub fn append(&mut self, vals: Vec) { - let n = vals.len(); - - self.heap.extend(vals.into_iter()); - self.h += n; - } - - pub fn clear(&mut self) { - self.heap.clear(); - self.h = 0; - } - - pub fn to_list>(&mut self, values: Iter) -> usize { - let head_addr = self.h; - - for value in values { - let h = self.h; - - self.push(HeapCellValue::Addr(Addr::Lis(h+1))); - self.push(HeapCellValue::Addr(value)); - } - - self.push(HeapCellValue::Addr(Addr::Con(Constant::EmptyList))); - head_addr - } -} - -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; pub enum TermIterState<'a> { diff --git a/src/prolog/lib/builtins.pl b/src/prolog/lib/builtins.pl index 02721d6e..7fae977f 100644 --- a/src/prolog/lib/builtins.pl +++ b/src/prolog/lib/builtins.pl @@ -7,9 +7,9 @@ (=..)/2, (==)/2, (\==)/2, (@=<)/2, (@>=)/2, (@<)/2, (@>)/2, (=@=)/2, (\=@=)/2, (:)/2, call_with_inference_limit/3, catch/3, current_prolog_flag/2, expand_goal/2, expand_term/2, - set_prolog_flag/2, setup_call_cleanup/3, term_variables/2, - throw/1, true/0, false/0, write/1, write_canonical/1, - writeq/1, write_term/2]). + findall/3, set_prolog_flag/2, setup_call_cleanup/3, + term_variables/2, throw/1, true/0, false/0, write/1, + write_canonical/1, writeq/1, write_term/2]). /* this is an implementation specific declarative operator used to implement call_with_inference_limit/3 and setup_call_cleanup/3. switches to the default trust_me and retry_me_else. Indexing choice @@ -351,3 +351,20 @@ handle_ball(C, C, R) :- !, '$erase_ball', call(R). handle_ball(_, _, _) :- '$unwind_stack'. throw(Ball) :- '$set_ball'(Ball), '$unwind_stack'. + +:- non_counted_backtracking '$iterate_find_all'/4. +'$iterate_find_all'(Template, Goal, _, LhOffset) :- + call(Goal), + '$copy_to_lh'(LhOffset, Template), + '$fail'. +'$iterate_find_all'(_, _, Solutions, LhOffset) :- + '$truncate_if_no_lh_growth'(LhOffset), + '$get_lh_from_offset'(LhOffset, Solutions). + +findall(Template, Goal, Solutions) :- + '$skip_max_list'(_, -1, Solutions, R), + ( nonvar(R), R \== [], throw(error(type_error(list, Solutions), findall/3)) + ; true + ), + '$lh_length'(LhLength), + '$call_with_default_policy'('$iterate_find_all'(Template, Goal, Solutions, LhLength)). diff --git a/src/prolog/machine/machine_state.rs b/src/prolog/machine/machine_state.rs index 5e580bcd..8cc4b62e 100644 --- a/src/prolog/machine/machine_state.rs +++ b/src/prolog/machine/machine_state.rs @@ -4,6 +4,7 @@ use prolog_parser::string_list::*; use prolog::instructions::*; use prolog::and_stack::*; use prolog::copier::*; +use prolog::heap::*; use prolog::machine::{AttrVarInitializer, IndexStore}; use prolog::machine::machine_errors::*; use prolog::num::{BigInt, BigUint, Zero, One}; @@ -59,10 +60,6 @@ impl<'a> IndexMut for CopyTerm<'a> { // the ordinary, heap term copier, used by duplicate_term. impl<'a> CopierTarget for CopyTerm<'a> { - fn source(&self) -> usize { - self.state.heap.h - } - fn threshold(&self) -> usize { self.state.heap.h } @@ -85,14 +82,17 @@ impl<'a> CopierTarget for CopyTerm<'a> { } pub(super) struct CopyBallTerm<'a> { - state: &'a mut MachineState, - heap_boundary: usize + and_stack: &'a mut AndStack, + heap: &'a mut Heap, + heap_boundary: usize, + stub: &'a mut MachineStub, } impl<'a> CopyBallTerm<'a> { - pub(super) fn new(state: &'a mut MachineState) -> Self { - let hb = state.heap.len(); - CopyBallTerm { state, heap_boundary: hb } + pub(super) fn new(and_stack: &'a mut AndStack, heap: &'a mut Heap, stub: &'a mut MachineStub) -> Self + { + let hb = heap.len(); + CopyBallTerm { and_stack, heap, heap_boundary: hb, stub } } } @@ -101,10 +101,10 @@ impl<'a> Index for CopyBallTerm<'a> { fn index(&self, index: usize) -> &Self::Output { if index < self.heap_boundary { - &self.state.heap[index] + &self.heap[index] } else { let index = index - self.heap_boundary; - &self.state.ball.stub[index] + &self.stub[index] } } } @@ -112,38 +112,34 @@ impl<'a> Index for CopyBallTerm<'a> { impl<'a> IndexMut for CopyBallTerm<'a> { fn index_mut(&mut self, index: usize) -> &mut Self::Output { if index < self.heap_boundary { - &mut self.state.heap[index] + &mut self.heap[index] } else { let index = index - self.heap_boundary; - &mut self.state.ball.stub[index] + &mut self.stub[index] } } } // the ordinary, heap term copier, used by duplicate_term. impl<'a> CopierTarget for CopyBallTerm<'a> { - fn source(&self) -> usize { - self.heap_boundary - } - fn threshold(&self) -> usize { - self.heap_boundary + self.state.ball.stub.len() + self.heap_boundary + self.stub.len() } - fn push(&mut self, hcv: HeapCellValue) { - self.state.ball.stub.push(hcv); + fn push(&mut self, value: HeapCellValue) { + self.stub.push(value); } fn store(&self, addr: Addr) -> Addr { match addr { - Addr::HeapCell(hc) if hc < self.heap_boundary => - self.state.heap[hc].as_addr(hc), - Addr::HeapCell(hc) => { - let index = hc - self.heap_boundary; - self.state.ball.stub[index].as_addr(hc) + Addr::HeapCell(h) | Addr::AttrVar(h) if h < self.heap_boundary => + self.heap[h].as_addr(h), + Addr::HeapCell(h) | Addr::AttrVar(h) => { + let index = h - self.heap_boundary; + self.stub[index].as_addr(h) }, Addr::StackCell(fr, sc) => - self.state.and_stack[fr][sc].clone(), + self.and_stack[fr][sc].clone(), addr => addr } } @@ -162,7 +158,7 @@ impl<'a> CopierTarget for CopyBallTerm<'a> { } fn stack(&mut self) -> &mut AndStack { - &mut self.state.and_stack + self.and_stack } } @@ -220,6 +216,7 @@ pub struct MachineState { pub(super) hb: usize, pub(super) block: usize, // an offset into the OR stack. pub(super) ball: Ball, + pub(super) lifted_heap: Vec, pub(super) interms: Vec, // intermediate numbers. pub(super) last_call: bool, pub(crate) flags: MachineFlags @@ -626,7 +623,7 @@ pub(crate) trait CallPolicy: Any { } }, &BuiltInClauseType::CopyTerm => { - machine_st.duplicate_term(); + machine_st.copy_term(); return_from_clause!(machine_st.last_call, machine_st) }, &BuiltInClauseType::Eq => { diff --git a/src/prolog/machine/machine_state_impl.rs b/src/prolog/machine/machine_state_impl.rs index c990b7ac..a579f35b 100644 --- a/src/prolog/machine/machine_state_impl.rs +++ b/src/prolog/machine/machine_state_impl.rs @@ -4,6 +4,7 @@ use prolog_parser::string_list::StringList; use prolog::instructions::*; use prolog::and_stack::*; use prolog::copier::*; +use prolog::heap::*; use prolog::heap_iter::*; use prolog::heap_print::*; use prolog::machine::{AttrVarInitializer, IndexStore}; @@ -42,7 +43,7 @@ impl MachineState { cp: LocalCodePtr::default(), attr_var_init: AttrVarInitializer::new(0, 0), fail: false, - heap: Heap::with_capacity(256), + heap: Heap::with_capacity(1024), mode: MachineMode::Write, and_stack: AndStack::new(), or_stack: OrStack::new(), @@ -54,6 +55,7 @@ impl MachineState { hb: 0, block: 0, ball: Ball::new(), + lifted_heap: Vec::with_capacity(1024), interms: vec![Number::default(); 256], last_call: false, flags: MachineFlags::default() @@ -1348,7 +1350,7 @@ impl MachineState { pub(super) fn set_ball(&mut self) { let addr = self[temp_v!(1)].clone(); self.ball.boundary = self.heap.h; - copy_term(CopyBallTerm::new(self), addr); + copy_term(CopyBallTerm::new(&mut self.and_stack, &mut self.heap, &mut self.ball.stub), addr); } pub(super) fn setup_call_n(&mut self, arity: usize) -> Option @@ -1416,10 +1418,12 @@ impl MachineState { } } - pub(super) fn copy_and_align_ball_to_heap(&mut self) -> usize { + pub(super) fn copy_and_align_ball_to_heap(&mut self, from: usize) -> usize { let diff = self.heap_ball_boundary_diff(); - for heap_value in self.ball.stub.iter().cloned() { + for index in from .. self.ball.stub.len() { + let heap_value = self.ball.stub[index].clone(); + self.heap.push(match heap_value { HeapCellValue::Addr(addr) => HeapCellValue::Addr(addr - diff), _ => heap_value @@ -2021,7 +2025,7 @@ impl MachineState { } } - pub(super) fn duplicate_term(&mut self) { + pub(super) fn copy_term(&mut self) { let old_h = self.heap.h; let a1 = self[temp_v!(1)].clone(); @@ -2380,5 +2384,6 @@ impl MachineState { self.block = 0; self.ball.reset(); + self.lifted_heap.clear(); } } diff --git a/src/prolog/machine/mod.rs b/src/prolog/machine/mod.rs index 89feda2f..762ce15e 100644 --- a/src/prolog/machine/mod.rs +++ b/src/prolog/machine/mod.rs @@ -446,7 +446,7 @@ impl Machine { { if self.machine_st.ball.stub.len() > 0 { let h = self.machine_st.heap.h; - self.machine_st.copy_and_align_ball_to_heap(); + self.machine_st.copy_and_align_ball_to_heap(0); let error_str = self.machine_st.print_exception(Addr::HeapCell(h), &heap_locs, diff --git a/src/prolog/machine/system_calls.rs b/src/prolog/machine/system_calls.rs index 7e688e2b..ed0208e3 100644 --- a/src/prolog/machine/system_calls.rs +++ b/src/prolog/machine/system_calls.rs @@ -1,5 +1,6 @@ use prolog_parser::ast::*; +use prolog::copier::*; use prolog::heap_iter::*; use prolog::heap_print::*; use prolog::instructions::*; @@ -190,13 +191,34 @@ impl MachineState { } } - pub(super) fn system_call(&mut self, ct: &SystemClauseType, + fn copy_findall_solution(&mut self, lh_offset: usize, copy_target: Addr) -> usize + { + let threshold = self.lifted_heap.len() - lh_offset; + let mut copy_ball_term = CopyBallTerm::new(&mut self.and_stack, &mut self.heap, + &mut self.lifted_heap); + + copy_ball_term.push(HeapCellValue::Addr(Addr::Lis(threshold + 1))); + copy_ball_term.push(HeapCellValue::Addr(Addr::HeapCell(threshold + 3))); + copy_ball_term.push(HeapCellValue::Addr(Addr::HeapCell(threshold + 2))); + + copy_term(copy_ball_term, copy_target); + threshold + lh_offset + 2 + } + + pub(super) fn system_call(&mut self, + ct: &SystemClauseType, indices: &IndexStore, call_policy: &mut Box, cut_policy: &mut Box) -> CallResult { match ct { + &SystemClauseType::LiftedHeapLength => { + let a1 = self[temp_v!(1)].clone(); + let lh_len = Addr::Con(Constant::Usize(self.lifted_heap.len())); + + self.unify(a1, lh_len); + }, &SystemClauseType::CheckCutPoint => { let addr = self.store(self.deref(self[temp_v!(1)].clone())); @@ -205,6 +227,27 @@ impl MachineState { _ => self.fail = true }; }, + &SystemClauseType::CopyToLiftedHeap => + // now, stagger everything down by the length of the heap + lh offset. + match self.store(self.deref(self[temp_v!(1)].clone())) { + Addr::Con(Constant::Usize(lh_offset)) => { + let copy_target = self[temp_v!(2)].clone(); + + let old_threshold = self.copy_findall_solution(lh_offset, copy_target); + let new_threshold = self.lifted_heap.len() - lh_offset; + + self.lifted_heap[old_threshold] = HeapCellValue::Addr(Addr::HeapCell(new_threshold)); + + for index in old_threshold + 1 .. self.lifted_heap.len() { + match &mut self.lifted_heap[index] { + &mut HeapCellValue::Addr(ref mut addr) => + *addr -= self.heap.len() + lh_offset, + _ => {} + } + } + }, + _ => self.fail = true + }, &SystemClauseType::DeleteAttribute => { let ls0 = self.store(self.deref(self[temp_v!(1)].clone())); @@ -282,6 +325,18 @@ impl MachineState { self.p = CodePtr::Local(LocalCodePtr::UserTermExpansion(0)); return Ok(()); }, + &SystemClauseType::TruncateIfNoLiftedHeapGrowth => + match self.store(self.deref(self[temp_v!(1)].clone())) { + Addr::Con(Constant::Usize(lh_offset)) => { + if lh_offset >= self.lifted_heap.len() { + self.lifted_heap.truncate(lh_offset); + } else { + self.lifted_heap.push(HeapCellValue::Addr(Addr::Con(Constant::EmptyList))); + } + }, + _ => + self.fail = true + }, &SystemClauseType::GetAttributedVariableList => { let attr_var = self.store(self.deref(self[temp_v!(1)].clone())); let mut attr_var_list = match attr_var { @@ -317,15 +372,43 @@ impl MachineState { match self.store(self.deref(addr)) { Addr::Con(Constant::Usize(b)) => { let iter = self.gather_attr_vars_created_since(b); - - let var_list_addr = Addr::HeapCell(self.heap.to_list(iter)); + + let var_list_addr = Addr::HeapCell(self.heap.to_list(iter)); let list_addr = self[temp_v!(2)].clone(); - - self.unify(var_list_addr, list_addr); + + self.unify(var_list_addr, list_addr); }, _ => self.fail = true } }, + &SystemClauseType::GetLiftedHeapFromOffset => { + let lh_offset = self[temp_v!(1)].clone(); + + match self.store(self.deref(lh_offset)) { + Addr::Con(Constant::Usize(lh_offset)) => + if lh_offset >= self.lifted_heap.len() { + let solutions = self[temp_v!(2)].clone(); + self.unify(solutions, Addr::Con(Constant::EmptyList)); + } else { + let h = self.heap.h; + + for index in lh_offset .. self.lifted_heap.len() { + match self.lifted_heap[index].clone() { + HeapCellValue::Addr(addr) => + self.heap.push(HeapCellValue::Addr(addr + h)), + value => + self.heap.push(value) + } + } + + self.lifted_heap.truncate(lh_offset); + + let solutions = self[temp_v!(2)].clone(); + self.unify(Addr::HeapCell(h), solutions); + }, + _ => self.fail = true + } + }, &SystemClauseType::GetDoubleQuotes => { let a1 = self[temp_v!(1)].clone(); @@ -574,7 +657,7 @@ impl MachineState { let h = self.heap.h; if self.ball.stub.len() > 0 { - self.copy_and_align_ball_to_heap(); + self.copy_and_align_ball_to_heap(0); } else { self.fail = true; return Ok(()); diff --git a/src/prolog/mod.rs b/src/prolog/mod.rs index a546e118..31ed6bcf 100644 --- a/src/prolog/mod.rs +++ b/src/prolog/mod.rs @@ -3,6 +3,7 @@ extern crate ordered_float; extern crate prolog_parser; #[macro_use] pub mod instructions; +pub mod heap; mod and_stack; #[macro_use] mod macros; #[macro_use] mod allocator; diff --git a/src/tests.rs b/src/tests.rs index 2887677b..b0669b90 100644 --- a/src/tests.rs +++ b/src/tests.rs @@ -1711,6 +1711,20 @@ fn test_queries_on_builtins() [["X = f(((a,b),c))"]]); assert_prolog_success!(&mut wam, "?- X = f(((a,b),(c, d))).", [["X = f(((a,b),c,d))"]]); + + assert_prolog_success!(&mut wam, "?- findall(X, (X = 1 ; X = 2), S).", + [["S = [1, 2]", "X = _0"]]); + assert_prolog_success!(&mut wam, "?- findall(X+Y, (X = 1), S).", + [["S = [1+_18]", "X = _1", "Y = _2"]]); + assert_prolog_success!(&mut wam, "?- findall(X, false, S).", + [["S = []", "X = _0"]]); + assert_prolog_success!(&mut wam, "?- findall(X, (X = 1 ; X = 1), S).", + [["S = [1, 1]", "X = _0"]]); + assert_prolog_failure!(&mut wam, "?- findall(X, (X = 2 ; X = 1), [1, 2])."); + assert_prolog_success!(&mut wam, "?- findall(X, (X = 1 ; X = 2), [X, Y]).", + [["X = 1", "Y = 2"]]); + assert_prolog_success!(&mut wam, "?- catch(findall(X, 4, S), error(type_error(callable, 4), _), true).", + [["S = _3", "X = _1"]]); } #[test] -- 2.54.0