From 516b67460d6f076a78886e93658dc138bb584f54 Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Sun, 29 Apr 2018 21:53:20 -0600 Subject: [PATCH] add '', type checking for incomplete lists in sort, keysort (re: #17) --- src/prolog/ast.rs | 13 ++- src/prolog/machine/machine_state.rs | 6 + src/prolog/machine/machine_state_impl.rs | 133 +++++++++++++++++++++-- src/prolog/machine/mod.rs | 8 +- src/tests.rs | 52 +++++++++ 5 files changed, 196 insertions(+), 16 deletions(-) diff --git a/src/prolog/ast.rs b/src/prolog/ast.rs index 5c585650..b1208c0a 100644 --- a/src/prolog/ast.rs +++ b/src/prolog/ast.rs @@ -808,7 +808,7 @@ impl ClauseType { &ClauseType::Op(ref name, ..) => name.clone(), &ClauseType::Named(ref name, ..) => name.clone(), &ClauseType::SetupCallCleanup => clause_name!("setup_call_cleanup"), - &ClauseType::SkipMaxList => clause_name!("'$skip_max_list'"), + &ClauseType::SkipMaxList => clause_name!("$skip_max_list"), &ClauseType::Sort => clause_name!("sort"), &ClauseType::Throw => clause_name!("throw") } @@ -838,7 +838,7 @@ impl ClauseType { ("keysort", 2) => ClauseType::KeySort, ("\\==", 2) => ClauseType::NotEq, ("setup_call_cleanup", 3) => ClauseType::SetupCallCleanup, - ("'$skip_max_list'", 4) => ClauseType::SkipMaxList, + ("$skip_max_list", 4) => ClauseType::SkipMaxList, ("sort", 2) => ClauseType::Sort, ("throw", 1) => ClauseType::Throw, _ => if let Some(fixity) = fixity { @@ -1360,6 +1360,13 @@ impl Addr { _ => true } } + + pub fn is_empty_list(&self) -> bool { + match self { + &Addr::Con(Constant::EmptyList) => true, + _ => false + } + } } impl From for Addr { @@ -1405,7 +1412,7 @@ pub struct ModuleCodeIndex(pub IndexPtr, pub ClauseName); impl From for CodeIndex { fn from(value: ModuleCodeIndex) -> Self { - CodeIndex(Rc::new(RefCell::new((value.0, value.1.clone())))) + CodeIndex(Rc::new(RefCell::new((value.0, value.1)))) } } diff --git a/src/prolog/machine/machine_state.rs b/src/prolog/machine/machine_state.rs index 6c6b6d00..e5749ef5 100644 --- a/src/prolog/machine/machine_state.rs +++ b/src/prolog/machine/machine_state.rs @@ -554,6 +554,12 @@ pub(crate) trait CallPolicy: Any { }, &ClauseType::Inlined(ref inlined) => { machine_st.execute_inlined(inlined, &vec![temp_v!(1), temp_v!(2)]); + Ok(()) + }, + &ClauseType::SkipMaxList => { + machine_st.skip_max_list(); + machine_st.p += 1; + Ok(()) } } diff --git a/src/prolog/machine/machine_state_impl.rs b/src/prolog/machine/machine_state_impl.rs index 6d1b33f0..71397049 100644 --- a/src/prolog/machine/machine_state_impl.rs +++ b/src/prolog/machine/machine_state_impl.rs @@ -4,7 +4,7 @@ use prolog::copier::*; use prolog::heap_iter::*; use prolog::heap_print::*; use prolog::machine::machine_state::*; -use prolog::num::{Integer, ToPrimitive, Zero}; +use prolog::num::{Integer, Signed, ToPrimitive, Zero}; use prolog::num::bigint::{BigInt, BigUint}; use prolog::num::rational::Ratio; use prolog::or_stack::*; @@ -26,6 +26,14 @@ macro_rules! try_or_fail { }} } +// used by '$skip_max_list'. +enum CycleSearchResult { + EmptyList, + NotList, + PartialOrProperList(usize, usize), // returns the list length (up to max), and an offset into the heap. + UntouchedList(usize) // return the offset of an uniterated Addr::Lis(offset). +} + impl MachineState { pub(super) fn new(atom_tbl: TabledData) -> MachineState { MachineState { @@ -915,8 +923,8 @@ impl MachineState { } } } - - self.fail = true; + + self.fail = true; } pub(super) fn goto_throw(&mut self) { @@ -928,9 +936,9 @@ impl MachineState { fn unwind_stack(&mut self) { self.b = self.block; self.or_stack.truncate(self.b); - + self.fail = true; - } + } fn throw_exception(&mut self, hcv: Vec) { let h = self.heap.h; @@ -1014,17 +1022,17 @@ impl MachineState { pub(super) fn is_cyclic_term(&self, addr: Addr) -> bool { let mut seen = HashSet::new(); let mut fail = false; - + let mut iter = self.pre_order_iter(addr); loop { if let Some(addr) = iter.stack().last() { - if !seen.contains(addr) { + if !seen.contains(addr) { seen.insert(addr.clone()); } else { fail = true; break; - } + } } if iter.next().is_none() { @@ -1034,7 +1042,7 @@ impl MachineState { fail } - + fn try_get_arg(&mut self) -> Result<(), Vec> { let a1 = self.store(self.deref(self[temp_v!(1)].clone())); @@ -1666,6 +1674,13 @@ impl MachineState { { let a1 = self.store(self.deref(self[r].clone())); + // detect cycles. + match self.detect_cycles(usize::max_value(), a1.clone()) { + CycleSearchResult::PartialOrProperList(_, h) + if self.store(self.deref(self.heap[h].as_addr(h))).is_empty_list() => {}, + _ => return Err(functor!("type_error", 2, [heap_atom!("list"), HeapCellValue::Addr(a1)])) + }; + match a1.clone() { Addr::Lis(mut l) => { let mut result = Vec::new(); @@ -1709,6 +1724,106 @@ impl MachineState { } } + fn detect_cycles(&self, max_steps: usize, addr: Addr) -> CycleSearchResult + { + let addr = self.store(self.deref(addr)); + + let mut hare = match addr { + Addr::Lis(offset) if max_steps > 0 => offset + 1, + Addr::Lis(offset) => return CycleSearchResult::UntouchedList(offset), + Addr::Con(Constant::EmptyList) => return CycleSearchResult::EmptyList, + _ => return CycleSearchResult::NotList + }; + + // use Brent's algorithm to detect cycles. + let mut tortoise = hare; + let mut power = 2; + let mut steps = 1; + + loop { + if steps == max_steps { + return CycleSearchResult::PartialOrProperList(steps, hare); + } + + match self.heap[hare].clone() { + HeapCellValue::Addr(Addr::Lis(l)) => { + hare = l + 1; + steps += 1; + + if tortoise == hare { + return CycleSearchResult::NotList; + } else if steps == power { + tortoise = hare; + power <<= 1; + } + }, + HeapCellValue::Addr(Addr::Con(Constant::EmptyList)) => + return CycleSearchResult::PartialOrProperList(steps, hare), + HeapCellValue::Addr(Addr::HeapCell(hc)) if hc == hare => + return CycleSearchResult::PartialOrProperList(steps, hare), + HeapCellValue::Addr(ref sc @ Addr::StackCell(..)) + if *sc == self.store(self.deref(sc.clone())) => + return CycleSearchResult::PartialOrProperList(steps, hare), + _ => return CycleSearchResult::NotList + } + } + } + + fn finalize_skip_max_list(&mut self, n: usize, addr: Addr) { + let target_n = self[temp_v!(1)].clone(); + self.unify(Addr::Con(integer!(n)), target_n); + + if !self.fail { + let xs = self[temp_v!(4)].clone(); + self.unify(addr, xs); + } + } + +/* + '$skip_max_list'(N, Max, Xs0, Xs): + valid modes: Max is always +Max (a non-negative integer), Xs, Xs0 and N are all ?_. + + Modes | Conditions for success + ====================================================================================== + ?N, -Xs0 : N = 0, Xs = Xs0. + ?N, +Xs0 : Xs0 is a proper or partial list, Xs0 = [X1, X2, ..., XN | Xs], N = Max, + if |Xs0| >= Max, or, Xs = [] and N = |Xs0|. +*/ + pub(super) fn skip_max_list(&mut self) { + let max = self.store(self.deref(self[temp_v!(2)].clone())); + + match max { + Addr::Con(Constant::Number(Number::Integer(ref max))) + if !max.is_negative() => { + let n = self.store(self.deref(self[temp_v!(1)].clone())); + + match n { + Addr::Con(Constant::Number(Number::Integer(ref n))) if n.is_zero() => { + let xs0 = self[temp_v!(3)].clone(); + let xs = self[temp_v!(4)].clone(); + + self.unify(xs0, xs); + }, + _ => { + let max = max.to_usize().unwrap_or(usize::max_value()); + + match self.detect_cycles(max, self[temp_v!(3)].clone()) { + CycleSearchResult::UntouchedList(l) => + self.finalize_skip_max_list(0, Addr::Lis(l)), + CycleSearchResult::EmptyList => + self.finalize_skip_max_list(0, Addr::Con(Constant::EmptyList)), + CycleSearchResult::PartialOrProperList(n, hc) => + self.finalize_skip_max_list(n, Addr::HeapCell(hc)), + CycleSearchResult::NotList => + self.fail = true + } + } + } + }, + _ => self.fail = true + }; + } + pub(super) fn duplicate_term(&mut self) { let old_h = self.heap.h; diff --git a/src/prolog/machine/mod.rs b/src/prolog/machine/mod.rs index f9c1a621..eeb9532d 100644 --- a/src/prolog/machine/mod.rs +++ b/src/prolog/machine/mod.rs @@ -15,9 +15,9 @@ use std::mem::swap; use std::ops::Index; use std::rc::Rc; -struct MachineCodeIndex<'a> { - code_dir: &'a mut CodeDir, - op_dir: &'a mut OpDir, +pub(super) struct MachineCodeIndex<'a> { + pub(super) code_dir: &'a mut CodeDir, + pub(super) op_dir: &'a mut OpDir, } pub struct Machine { @@ -148,7 +148,7 @@ impl Machine { let mut indices = MachineCodeIndex { code_dir: &mut self.code_dir, op_dir: &mut self.op_dir }; - indices.use_qualified_module(module, exports) + indices.use_qualified_module(module, &exports) }, None => EvalSession::from(EvalError::ModuleNotFound) } diff --git a/src/tests.rs b/src/tests.rs index a0fabccc..b970af2a 100644 --- a/src/tests.rs +++ b/src/tests.rs @@ -1593,3 +1593,55 @@ fn test_queries_on_call_with_inference_limit() [["R = inference_limit_exceeded", "X = _1"]]); } + +#[test] +fn test_queries_on_skip_max_list() { + let mut wam = Machine::new(); + + // test on proper and empty lists. + assert_prolog_success!(&mut wam, "?- '$skip_max_list'(N, 5, [], Xs).", + [["Xs = []", "N = 0"]]); + assert_prolog_success!(&mut wam, "?- '$skip_max_list'(N, 5, [a,b,c], Xs).", + [["Xs = []", "N = 3"]]); + assert_prolog_success!(&mut wam, "?- '$skip_max_list'(N, 2, [a,b,c], Xs).", + [["Xs = [c]", "N = 2"]]); + assert_prolog_success!(&mut wam, "?- '$skip_max_list'(N, 3, [a,b,c], Xs).", + [["Xs = []", "N = 3"]]); + + assert_prolog_success!(&mut wam, "?- '$skip_max_list'(N, 0, [], Xs).", + [["Xs = []", "N = 0"]]); + assert_prolog_success!(&mut wam, "?- '$skip_max_list'(N, 0, [a,b,c], Xs).", + [["Xs = [a, b, c]", "N = 0"]]); + assert_prolog_success!(&mut wam, "?- '$skip_max_list'(N, 0, [a,b,c], Xs).", + [["Xs = [a, b, c]", "N = 0"]]); + assert_prolog_success!(&mut wam, "?- '$skip_max_list'(N, 0, [a,b,c], Xs).", + [["Xs = [a, b, c]", "N = 0"]]); + + assert_prolog_failure!(&mut wam, "?- '$skip_max_list'(4, 0, [], Xs)."); + assert_prolog_failure!(&mut wam, "?- '$skip_max_list'(3, 0, [a,b,c], Xs)."); + assert_prolog_failure!(&mut wam, "?- '$skip_max_list'(2, 0, [a,b,c], Xs)."); + assert_prolog_failure!(&mut wam, "?- '$skip_max_list'(1, 0, [a,b,c], Xs)."); + + assert_prolog_success!(&mut wam, "?- '$skip_max_list'(0, 5, [], Xs).", + [["Xs = []"]]); + assert_prolog_success!(&mut wam, "?- '$skip_max_list'(3, 5, [a,b,c], Xs).", + [["Xs = []"]]); + assert_prolog_success!(&mut wam, "?- '$skip_max_list'(2, 2, [a,b,c], Xs).", + [["Xs = [c]"]]); + assert_prolog_success!(&mut wam, "?- '$skip_max_list'(3, 3, [a,b,c], Xs).", + [["Xs = []"]]); + + // tests on partial lists. + assert_prolog_success!(&mut wam, "?- '$skip_max_list'(3, 4, [a,b,c|X], Xs0).", + [["X = _1", "Xs0 = _1"]]); + assert_prolog_success!(&mut wam, "?- '$skip_max_list'(3, 3, [a,b,c|X], Xs0).", + [["X = _1", "Xs0 = _1"]]); + assert_prolog_failure!(&mut wam, "?- '$skip_max_list'(3, 2, [a,b,c|X], Xs0)."); + assert_prolog_failure!(&mut wam, "?- '$skip_max_list'(3, 1, [a,b,c|X], Xs0)."); + assert_prolog_failure!(&mut wam, "?- '$skip_max_list'(3, 0, [a,b,c|X], Xs0)."); + + // tests on cyclic lists. + assert_prolog_failure!(&mut wam, "?- Xs = [a,b|Xs], '$skip_max_list'(3, 5, X, Xs0)."); + assert_prolog_failure!(&mut wam, "?- X = [a,b|Y], Y = [c,d|X], '$skip_max_list'(4, 5, X, Xs0)."); + assert_prolog_failure!(&mut wam, "?- X = [a,b|Y], Y = [c,d|X], '$skip_max_list'(4, 3, X, Xs0)."); +} -- 2.54.0