From bf46c4b5c125bccd89573bad8e9801d5f6af2cb5 Mon Sep 17 00:00:00 2001 From: Mark Date: Wed, 18 Oct 2023 11:58:04 -0600 Subject: [PATCH] use topo_sort to correct acyclic_term (#2124, #2125) --- Cargo.lock | 7 ++ Cargo.toml | 1 + src/heap_iter.rs | 51 +++++---- src/machine/gc.rs | 168 ++++++------------------------ src/machine/machine_state_impl.rs | 47 ++++++++- src/tests/acyclic_term.pl | 54 ++++++---- 6 files changed, 140 insertions(+), 188 deletions(-) diff --git a/Cargo.lock b/Cargo.lock index e054b9db..133b6524 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -2047,6 +2047,7 @@ dependencies = [ "to-syn-value", "to-syn-value_derive", "tokio", + "topo_sort", "walkdir", "warp", "wasm-bindgen", @@ -2576,6 +2577,12 @@ dependencies = [ "tracing", ] +[[package]] +name = "topo_sort" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "156552d3c80df430aaac98c605a4e0eb7da8d06029cce2d40b4a6b095a34b37e" + [[package]] name = "tower-service" version = "0.3.2" diff --git a/Cargo.toml b/Cargo.toml index 5fb0db69..6ed48fc0 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -70,6 +70,7 @@ bytes = "1" dashu = "0.4.0" num-order = { version = "1.2.0" } rand = "0.8.5" +topo_sort = { version = "0.4.0" } [target.'cfg(not(target_arch = "wasm32"))'.dependencies] libffi = { version = "3.2.0", optional = true } diff --git a/src/heap_iter.rs b/src/heap_iter.rs index 9dd30b7e..3c47c934 100644 --- a/src/heap_iter.rs +++ b/src/heap_iter.rs @@ -1,5 +1,3 @@ -#[cfg(test)] -pub(crate) use crate::machine::gc::{IteratorUMP}; pub(crate) use crate::machine::gc::{CycleDetectorUMP, StacklessPreOrderHeapIter}; use crate::atom_table::*; @@ -505,24 +503,14 @@ impl<'a, ElideLists: ListElisionPolicy> Iterator for StackfulPreOrderHeapIter<'a } } -#[cfg(test)] #[inline(always)] -pub(crate) fn stackless_preorder_iter( - heap: &mut Vec, - start: usize, -) -> StacklessPreOrderHeapIter { - StacklessPreOrderHeapIter::::new(heap, start) -} - - pub(crate) fn cycle_detecting_stackless_preorder_iter( - heap: &mut Heap, + heap: &mut Vec, start: usize, ) -> StacklessPreOrderHeapIter { StacklessPreOrderHeapIter::::new(heap, start) } - #[inline(always)] pub(crate) fn stackful_preorder_iter<'a, ElideLists: ListElisionPolicy>( heap: &'a mut Vec, @@ -665,23 +653,30 @@ pub(crate) fn stackful_post_order_iter<'a, ElideLists: ListElisionPolicy>( PostOrderIterator::new(StackfulPreOrderHeapIter::new(heap, stack, cell)) } -#[cfg(test)] -pub(crate) type RightistPostOrderHeapIter<'a> = - PostOrderIterator>; - -#[cfg(test)] -#[inline] -pub(crate) fn stackless_post_order_iter<'a>( - heap: &'a mut Heap, - start: usize, -) -> RightistPostOrderHeapIter<'a> { - PostOrderIterator::new(stackless_preorder_iter(heap, start)) -} - #[cfg(test)] mod tests { use super::*; use crate::machine::mock_wam::*; + use crate::machine::gc::{IteratorUMP}; + + pub(crate) type RightistPostOrderHeapIter<'a> = + PostOrderIterator>; + + #[inline(always)] + pub(crate) fn stackless_preorder_iter( + heap: &mut Vec, + start: usize, + ) -> StacklessPreOrderHeapIter { + StacklessPreOrderHeapIter::::new(heap, start) + } + + #[inline] + pub(crate) fn stackless_post_order_iter<'a>( + heap: &'a mut Heap, + start: usize, + ) -> RightistPostOrderHeapIter<'a> { + PostOrderIterator::new(stackless_preorder_iter(heap, start)) + } #[test] fn heap_stackless_iter_tests() { @@ -1267,6 +1262,10 @@ mod tests { unmark_cell_bits!(iter.next().unwrap()), list_loc_as_cell!(1) ); + assert_eq!( + unmark_cell_bits!(iter.next().unwrap()), + list_loc_as_cell!(1) + ); assert_eq!(iter.next(), None); } diff --git a/src/machine/gc.rs b/src/machine/gc.rs index d7e9a4f1..b7f257a5 100644 --- a/src/machine/gc.rs +++ b/src/machine/gc.rs @@ -10,24 +10,13 @@ pub(crate) trait UnmarkPolicy { where Self: Sized; fn invert_marker(iter: &mut StacklessPreOrderHeapIter) where Self: Sized; - fn cycle_detected(&mut self) where Self: Sized; fn mark_phase(&self) -> bool; - - #[inline(always)] - fn var_rooted_cycle(_iter: &mut StacklessPreOrderHeapIter, _next: usize) - where - Self: Sized {} - - #[inline(always)] - fn var_link_is_cyclic(_iter: &StacklessPreOrderHeapIter) -> bool where Self: Sized { false } - + #[inline] + fn report_var_link(iter: &StacklessPreOrderHeapIter) -> bool where Self: Sized { + iter.heap[iter.next as usize].get_mark_bit() == iter.iter_state.mark_phase() + } #[inline(always)] - fn detect_list_cell_cycle(_iter: &mut StacklessPreOrderHeapIter) where Self: Sized {} - - fn list_head_cycle_detecting_backward( - iter: &mut StacklessPreOrderHeapIter, - ) -> bool where Self: Sized { - iter.backward() + fn record_focus(_iter: &mut StacklessPreOrderHeapIter) where Self: Sized { } } @@ -60,9 +49,6 @@ impl UnmarkPolicy for IteratorUMP { invert_marker(iter); } - #[inline(always)] - fn cycle_detected(&mut self) {} - #[inline] fn mark_phase(&self) -> bool { self.mark_phase @@ -71,7 +57,7 @@ impl UnmarkPolicy for IteratorUMP { pub(crate) struct CycleDetectorUMP { mark_phase: bool, - cycle_detected: bool, + focus: usize, } impl UnmarkPolicy for CycleDetectorUMP { @@ -87,50 +73,18 @@ impl UnmarkPolicy for CycleDetectorUMP { } #[inline] - fn cycle_detected(&mut self) { - self.cycle_detected = true; - } - - #[inline(always)] fn mark_phase(&self) -> bool { self.mark_phase } - #[inline] - fn list_head_cycle_detecting_backward( - iter: &mut StacklessPreOrderHeapIter, - ) -> bool { - Self::detect_list_cell_cycle(iter); - iter.backward() - } - - #[inline] - fn detect_list_cell_cycle(iter: &mut StacklessPreOrderHeapIter) { - if iter.iter_state.mark_phase && !iter.iter_state.cycle_detected { - iter.iter_state.cycle_detected = iter.detect_cycle(iter.current); - } - } - - #[inline] - fn var_rooted_cycle(iter: &mut StacklessPreOrderHeapIter, next: usize) { - if iter.current != next && iter.iter_state.mark_phase && !iter.iter_state.cycle_detected { - iter.iter_state.cycle_detected = iter.detect_cycle(next); - } + #[inline(always)] + fn report_var_link(_iter: &StacklessPreOrderHeapIter) -> bool { + true } - fn var_link_is_cyclic(iter: &StacklessPreOrderHeapIter) -> bool { - if iter.iter_state.cycle_detected || !iter.iter_state.mark_phase { - return false; - } - - let next = iter.next as usize; - - if !iter.heap[next].is_var() && iter.heap[next].is_ref() { - let h = iter.heap[next].get_value() as usize; - iter.heap[h + 1].get_forwarding_bit() - } else { - false - } + #[inline(always)] + fn record_focus(iter: &mut StacklessPreOrderHeapIter) { + iter.iter_state.focus = iter.current; } } @@ -161,9 +115,6 @@ impl UnmarkPolicy for MarkerUMP { fn mark_phase(&self) -> bool { true } - - #[inline(always)] - fn cycle_detected(&mut self) {} } #[derive(Debug)] @@ -210,7 +161,8 @@ impl<'a> StacklessPreOrderHeapIter<'a, MarkerUMP> { } } -impl<'a> StacklessPreOrderHeapIter<'a, CycleDetectorUMP> { +impl<'a> StacklessPreOrderHeapIter<'a, IteratorUMP> { + #[cfg(test)] pub(crate) fn new(heap: &'a mut [HeapCellValue], start: usize) -> Self { heap[start].set_forwarding_bit(true); let next = heap[start].get_value(); @@ -220,41 +172,12 @@ impl<'a> StacklessPreOrderHeapIter<'a, CycleDetectorUMP> { start, current: start, next, - iter_state: CycleDetectorUMP { - mark_phase: true, - cycle_detected: false, - }, - } - } - - #[inline] - pub(crate) fn found_cycle(&self) -> bool { - self.iter_state.cycle_detected - } - - pub(crate) fn detect_cycle(&self, next: usize) -> bool { - use crate::machine::system_calls::BrentAlgState; - - let mut brent_alg_st = BrentAlgState::new(self.current); - - while self.heap[brent_alg_st.hare].get_mark_bit() { - let temp = self.heap[brent_alg_st.hare].get_value() as usize; - - if brent_alg_st.step(temp).is_some() || temp == next { - return true; - } - - if !self.heap[brent_alg_st.hare].is_ref() || temp == self.start { - break; - } + iter_state: IteratorUMP { mark_phase: true,}, } - - false } } -impl<'a> StacklessPreOrderHeapIter<'a, IteratorUMP> { - #[cfg(test)] +impl<'a> StacklessPreOrderHeapIter<'a, CycleDetectorUMP> { pub(crate) fn new(heap: &'a mut [HeapCellValue], start: usize) -> Self { heap[start].set_forwarding_bit(true); let next = heap[start].get_value(); @@ -264,11 +187,19 @@ impl<'a> StacklessPreOrderHeapIter<'a, IteratorUMP> { start, current: start, next, - iter_state: IteratorUMP { - mark_phase: true, - }, + iter_state: CycleDetectorUMP { mark_phase: true, focus: 0 }, } } + + #[inline] + pub(crate) fn focus(&self) -> usize { + self.iter_state.focus + } + + #[inline(always)] + pub(crate) fn current(&self) -> usize { + self.current + } } impl<'a, UMP: UnmarkPolicy> StacklessPreOrderHeapIter<'a, UMP> { @@ -306,24 +237,18 @@ impl<'a, UMP: UnmarkPolicy> StacklessPreOrderHeapIter<'a, UMP> { if self.heap[self.current].get_mark_bit() != self.iter_state.mark_phase() { self.heap[self.current].set_mark_bit(self.iter_state.mark_phase()); + UMP::record_focus(self); + match self.heap[self.current].get_tag() { HeapCellValueTag::AttrVar => { let next = self.next as usize; - if self.heap[next].get_mark_bit() { - UMP::var_rooted_cycle(self, next); - } else if self.heap[next].get_forwarding_bit() { - if UMP::var_link_is_cyclic(self) { - self.iter_state.cycle_detected(); - } - } - if let Some(cell) = UMP::forward_attr_var(self) { return Some(cell); } if self.next < self.heap.len() as u64 { - if self.heap[self.next as usize].get_mark_bit() == self.iter_state.mark_phase() { + if UMP::report_var_link(self) { let tag = HeapCellValueTag::AttrVar; return Some(HeapCellValue::build_with(tag, next as u64)); } @@ -332,20 +257,12 @@ impl<'a, UMP: UnmarkPolicy> StacklessPreOrderHeapIter<'a, UMP> { HeapCellValueTag::Var => { let next = self.next as usize; - if self.heap[next].get_mark_bit() { - UMP::var_rooted_cycle(self, next); - } else if self.heap[next].get_forwarding_bit() { - if UMP::var_link_is_cyclic(self) { - self.iter_state.cycle_detected(); - } - } - if let Some(cell) = self.forward_var() { return Some(cell); } if self.next < self.heap.len() as u64 { - if self.heap[self.next as usize].get_mark_bit() == self.iter_state.mark_phase() { + if UMP::report_var_link(self) { let tag = HeapCellValueTag::Var; return Some(HeapCellValue::build_with(tag, next as u64)); } @@ -353,7 +270,6 @@ impl<'a, UMP: UnmarkPolicy> StacklessPreOrderHeapIter<'a, UMP> { } HeapCellValueTag::Str => { if self.heap[self.next as usize + 1].get_forwarding_bit() { - self.iter_state.cycle_detected(); return Some(self.backward_and_return()); } @@ -378,7 +294,6 @@ impl<'a, UMP: UnmarkPolicy> StacklessPreOrderHeapIter<'a, UMP> { let last_cell_loc = self.next as usize + 1; if self.heap[last_cell_loc].get_forwarding_bit() { - self.iter_state.cycle_detected(); return Some(self.backward_and_return()); } @@ -388,32 +303,12 @@ impl<'a, UMP: UnmarkPolicy> StacklessPreOrderHeapIter<'a, UMP> { self.heap[last_cell_loc].set_forwarding_bit(true); - if self.heap[last_cell_loc].get_mark_bit() == self.iter_state.mark_phase() { - if self.heap[last_cell_loc-1].get_mark_bit() == self.iter_state.mark_phase() { - // the conjunction leading here is a necessary but not sufficient - // condition of the presence of a cycle at the list head. - - if last_cell_loc == self.current { - UMP::detect_list_cell_cycle(self); - } - - self.backward(); - - if UMP::list_head_cycle_detecting_backward(self) { - return None; - } - - continue; - } - } - return Some(list_loc_as_cell!(last_cell_loc - 1)); } HeapCellValueTag::PStrLoc => { let h = self.next as usize; if self.heap[h + 1].get_forwarding_bit() { - self.iter_state.cycle_detected(); return Some(self.backward_and_return()); } @@ -436,7 +331,6 @@ impl<'a, UMP: UnmarkPolicy> StacklessPreOrderHeapIter<'a, UMP> { let last_cell_loc = h + 1; if self.heap[last_cell_loc].get_forwarding_bit() { - self.iter_state.cycle_detected(); return Some(self.backward_and_return()); } diff --git a/src/machine/machine_state_impl.rs b/src/machine/machine_state_impl.rs index eef5f18c..6a7cb95d 100644 --- a/src/machine/machine_state_impl.rs +++ b/src/machine/machine_state_impl.rs @@ -1131,6 +1131,8 @@ impl MachineState { #[inline] pub fn is_cyclic_term(&mut self, value: HeapCellValue) -> bool { + use topo_sort::TopoSort; + let value = self.store(self.deref(value)); if value.is_constant() || value.is_stack_var() { @@ -1140,17 +1142,52 @@ impl MachineState { let h = self.heap.len(); self.heap.push(value); - let found_cycle = { + let found_cycle = (|| { + let mut topo_graph = TopoSort::new(); let mut iter = cycle_detecting_stackless_preorder_iter(&mut self.heap, h); - while let Some(_) = iter.next() { - if iter.found_cycle() { + while let Some(cell) = iter.next() { + let focus = iter.focus(); + + read_heap_cell!(cell, + (HeapCellValueTag::Atom, (_name, arity)) => { + if arity > 0 { + // focus is actually the location of Str(s) here. + let s = iter.current() - arity; + + topo_graph.insert(focus, vec![s]); + topo_graph.insert(s, (s + 1 .. s + arity + 1).collect::>()); + } + } + (HeapCellValueTag::Str, s) => { + topo_graph.insert(focus, vec![s]); + } + (HeapCellValueTag::Lis | HeapCellValueTag::PStrLoc | HeapCellValueTag::PStrOffset, l) => { + if l <= focus && focus < l + 2 { + // TopoSort doesn't consider focus -> + // focus to induce a cycle so in this case + // it must be checked manually. + return true; + } + + topo_graph.insert(focus, (l .. l + 2).collect::>()); + } + (HeapCellValueTag::AttrVar | HeapCellValueTag::Var, h) => { + if focus != h { + topo_graph.insert(focus, vec![h]); + } + } + _ => { + } + ); + + if topo_graph.cycle_detected() { break; } } - iter.found_cycle() - }; + topo_graph.cycle_detected() + })(); self.heap.pop(); found_cycle diff --git a/src/tests/acyclic_term.pl b/src/tests/acyclic_term.pl index 8df3ad11..9c08d9c8 100644 --- a/src/tests/acyclic_term.pl +++ b/src/tests/acyclic_term.pl @@ -81,87 +81,87 @@ test("acyclic_term_13", ( A = [A|2], X = A, T=a(X, A), \+ acyclic_term(T) )). -test("acyclic_term_13", ( +test("acyclic_term_14", ( A = [T|2], X = A, T=a(X, A), \+ acyclic_term(T) )). -test("acyclic_term_14", ( +test("acyclic_term_15", ( T = [_A|T], \+ acyclic_term(T) )). -test("acyclic_term_15", ( +test("acyclic_term_16", ( T = [T|_L], \+ acyclic_term(T) )). -test("acyclic_term_16", ( +test("acyclic_term_17", ( A = [1|A], X = A, T=a(X, A), \+ acyclic_term(T) )). -test("acyclic_term_17", ( +test("acyclic_term_18", ( T = [_A| [[[[L|T]|[]]]]], acyclic_term(L) )). -test("acyclic_term_18", ( +test("acyclic_term_19", ( T = [A| [[[[_L|T]|[]]]]], acyclic_term(A) )). -test("acyclic_term_19", ( +test("acyclic_term_20", ( T = [_A| [[[[_L|T]|[]]]]], \+ acyclic_term(T) )). -test("acyclic_term_20", ( +test("acyclic_term_21", ( A = [_C|_B], X = A, T=a(t(X,A), A), acyclic_term(T) )). -test("acyclic_term_21", ( +test("acyclic_term_22", ( X = [a | Rest], Rest = [_Y | Rest], \+ acyclic_term(X) )). -test("acyclic_term_22", ( +test("acyclic_term_23", ( _X = [a | Rest], Rest = [_Y | Rest], \+ acyclic_term(Rest) )). -test("acyclic_term_23", ( +test("acyclic_term_24", ( T = [[_A, T]], G = [1|T], \+ acyclic_term(G) )). -test("acyclic_term_24", ( +test("acyclic_term_25", ( T = [[_A, T]], \+ acyclic_term(T) )). -test("acyclic_term_25", ( +test("acyclic_term_26", ( T = [[_, _], T], \+ acyclic_term(T) )). -test("acyclic_term_26", ( +test("acyclic_term_27", ( T = [[T, _], 1], \+ acyclic_term(T) )). -test("acyclic_term_27", ( +test("acyclic_term_28", ( T = str(A,A), acyclic_term(T) )). -test("acyclic_term_28", ( +test("acyclic_term_29", ( T = str(A,A,A), acyclic_term(T) )). -test("acyclic_term_29", ( +test("acyclic_term_30", ( A = s(B, d(Y)), Y = B, acyclic_term(A), acyclic_term(B), acyclic_term(Y) )). -test("acyclic_term_30", ( +test("acyclic_term_31", ( A=str(B,B,B), C=str(A,_D,B), acyclic_term(C), acyclic_term(A), acyclic_term(B) )). -test("acyclic_term_31", ( +test("acyclic_term_32", ( A=B*C,A=[]*B*D*B, \+ acyclic_term(A), \+ acyclic_term(B), \+ acyclic_term(C), acyclic_term(D) )). -test("acyclic_term_32", ( +test("acyclic_term_33", ( A=B*C,A=B*[]*B, \+ acyclic_term(A), \+ acyclic_term(B), \+ acyclic_term(C) )). @@ -221,6 +221,20 @@ test("acyclic_term#2123", ( acyclic_term(B), acyclic_term(C) )). +test("acyclic_term#2124", ( + A=B*C,B=[]*C,C=[]*B, \+ acyclic_term(A), + \+ acyclic_term(B), \+ acyclic_term(C) +)). + +test("acyclic_term#2125", ( + A=B*[], + D=B*[], + A=B, + \+ acyclic_term(D), + \+ acyclic_term(A), + \+ acyclic_term(B) +)). + main :- findall(test(Name, Goal), test(Name, Goal), Tests), run_tests(Tests, Failed), -- 2.54.0