From c9a34bde3f51f8d77917d984335e67e1ef2b4d21 Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Sat, 2 Apr 2022 17:30:04 -0600 Subject: [PATCH] removal of old stackless iterator, implementation of new more faithful one --- src/heap_iter.rs | 51 ++++++- src/machine/arithmetic_ops.rs | 4 +- src/machine/gc.rs | 248 ++++++++++++++++++++++++++++++++-- src/machine/system_calls.rs | 2 +- 4 files changed, 285 insertions(+), 20 deletions(-) diff --git a/src/heap_iter.rs b/src/heap_iter.rs index c88ad721..f1e9ca66 100644 --- a/src/heap_iter.rs +++ b/src/heap_iter.rs @@ -1,4 +1,4 @@ -pub(crate) use crate::machine::gc::{IteratorUMP, StacklessPreOrderHeapIter}; +// pub(crate) use crate::machine::gc::{IteratorUMP, StacklessPreOrderHeapIter}; use crate::machine::heap::*; use crate::atom_table::*; @@ -223,6 +223,7 @@ impl<'a> Iterator for StackfulPreOrderHeapIter<'a> { } } +/* #[inline(always)] pub(crate) fn stackless_preorder_iter( heap: &mut Vec, @@ -230,6 +231,7 @@ pub(crate) fn stackless_preorder_iter( ) -> StacklessPreOrderHeapIter { StacklessPreOrderHeapIter::new(heap, cell) } +*/ #[inline(always)] pub(crate) fn stackful_preorder_iter( @@ -335,9 +337,10 @@ pub(crate) fn stackful_post_order_iter<'a>( PostOrderIterator::new(StackfulPreOrderHeapIter::new(heap, cell)) } -pub(crate) type RightistPostOrderHeapIter<'a> = - PostOrderIterator>; +// pub(crate) type RightistPostOrderHeapIter<'a> = +// PostOrderIterator>; +/* #[inline] pub(crate) fn stackless_post_order_iter<'a>( heap: &'a mut Heap, @@ -345,12 +348,14 @@ pub(crate) fn stackless_post_order_iter<'a>( ) -> RightistPostOrderHeapIter<'a> { PostOrderIterator::new(stackless_preorder_iter(heap, cell)) } +*/ #[cfg(test)] mod tests { use super::*; use crate::machine::mock_wam::*; + /* #[test] fn heap_stackless_iter_tests() { let mut wam = MockWAM::new(); @@ -1257,8 +1262,44 @@ mod tests { assert_eq!(wam.machine_st.heap[0], atom_as_cell!(atom!("f"), 2)); assert_eq!(wam.machine_st.heap[1], heap_loc_as_cell!(1)); assert_eq!(wam.machine_st.heap[2], heap_loc_as_cell!(1)); - } + wam.machine_st.heap.clear(); + + // representation of one of the heap terms as in issue #1384. +/* + wam.machine_st.heap.push(list_loc_as_cell!(7)); + wam.machine_st.heap.push(heap_loc_as_cell!(0)); + wam.machine_st.heap.push(list_loc_as_cell!(3)); + wam.machine_st.heap.push(list_loc_as_cell!(5)); + wam.machine_st.heap.push(empty_list_as_cell!()); + wam.machine_st.heap.push(heap_loc_as_cell!(2)); + wam.machine_st.heap.push(heap_loc_as_cell!(2)); + wam.machine_st.heap.push(empty_list_as_cell!()); + wam.machine_st.heap.push(heap_loc_as_cell!(3)); + + { + let mut iter = stackless_preorder_iter( + &mut wam.machine_st.heap, + heap_loc_as_cell!(0), + ); + + while let Some(_) = iter.next() { + print_heap_terms(iter.heap.iter(), 0); + println!(""); + } + + /* + assert_eq!( + unmark_cell_bits!(iter.next().unwrap()), + atom_as_cell!(atom!("f"), 2) + ); + + assert!(iter.next().is_none()); + */ + } +*/ + } +*/ #[test] fn heap_stackful_iter_tests() { let mut wam = MockWAM::new(); @@ -2178,6 +2219,7 @@ mod tests { wam.machine_st.heap.clear(); } +/* #[test] fn heap_stackless_post_order_iter() { let mut wam = MockWAM::new(); @@ -2590,4 +2632,5 @@ mod tests { all_cells_unmarked(&wam.machine_st.heap); } +*/ } diff --git a/src/machine/arithmetic_ops.rs b/src/machine/arithmetic_ops.rs index b4378afd..6de4d340 100644 --- a/src/machine/arithmetic_ops.rs +++ b/src/machine/arithmetic_ops.rs @@ -1098,7 +1098,7 @@ impl MachineState { pub(crate) fn arith_eval_by_metacall(&mut self, value: HeapCellValue) -> Result { let stub_gen = || functor_stub(atom!("is"), 2); - let mut iter = stackless_post_order_iter(&mut self.heap, value); + let mut iter = stackful_post_order_iter(&mut self.heap, value); // was stackless! while let Some(value) = iter.next() { if value.is_forwarded() { @@ -1125,8 +1125,8 @@ impl MachineState { read_heap_cell!(value, (HeapCellValueTag::Atom, (name, arity)) => { if arity == 2 { - let a1 = self.interms.pop().unwrap(); let a2 = self.interms.pop().unwrap(); + let a1 = self.interms.pop().unwrap(); match name { atom!("+") => self.interms.push(drop_iter_on_err!( diff --git a/src/machine/gc.rs b/src/machine/gc.rs index e9e82b25..8e93cecc 100644 --- a/src/machine/gc.rs +++ b/src/machine/gc.rs @@ -7,7 +7,7 @@ use core::marker::PhantomData; pub(crate) trait UnmarkPolicy { fn unmark(heap: &mut [HeapCellValue], current: usize); fn mark(heap: &mut [HeapCellValue], current: usize); - fn forward_attr_var(iter: &mut StacklessPreOrderHeapIter) -> Option + fn forward_attr_var(iter: &mut StacklessPreOrderHeapIter) -> bool where Self: Sized; } @@ -24,7 +24,7 @@ impl UnmarkPolicy for IteratorUMP { fn mark(_heap: &mut [HeapCellValue], _current: usize) {} #[inline(always)] - fn forward_attr_var(iter: &mut StacklessPreOrderHeapIter) -> Option { + fn forward_attr_var(iter: &mut StacklessPreOrderHeapIter) -> bool { iter.forward_var() } } @@ -41,8 +41,8 @@ impl UnmarkPolicy for MarkerUMP { } #[inline(always)] - fn forward_attr_var(iter: &mut StacklessPreOrderHeapIter) -> Option { - if iter.heap[iter.current + 1].get_mark_bit() { + fn forward_attr_var(iter: &mut StacklessPreOrderHeapIter) -> bool { + if iter.heap[iter.current + 1].get_forwarding_bit() == Some(true) { return iter.forward_var(); } @@ -52,11 +52,11 @@ impl UnmarkPolicy for MarkerUMP { iter.current += 1; iter.next = iter.heap[iter.current].get_value(); - iter.heap[iter.current].set_value(temp); - iter.heap[iter.current].set_mark_bit(true); - None + iter.heap[iter.current].set_forwarding_bit(true); // forward the attr vars list. + + false } } @@ -86,12 +86,12 @@ impl<'a, UMP: UnmarkPolicy> Drop for StacklessPreOrderHeapIter<'a, UMP> { impl<'a, UMP: UnmarkPolicy> StacklessPreOrderHeapIter<'a, UMP> { pub(crate) fn new(heap: &'a mut Vec, cell: HeapCellValue) -> Self { let orig_heap_len = heap.len(); - let start = orig_heap_len + 1; + let start = orig_heap_len; // + 1; heap.push(cell); - heap.push(heap_loc_as_cell!(orig_heap_len)); + // heap.push(heap_loc_as_cell!(orig_heap_len)); - heap[start].set_mark_bit(true); + heap[start].set_forwarding_bit(true); let next = heap[start].get_value(); Self { @@ -104,6 +104,181 @@ impl<'a, UMP: UnmarkPolicy> StacklessPreOrderHeapIter<'a, UMP> { } } + // NEW implementation! + fn forward_var(&mut self) -> bool { + if self.heap[self.next].get_forwarding_bit() == Some(true) { + return self.backward(); + } + + let temp = self.heap[self.next].get_value(); + + self.heap[self.next].set_value(self.current); + self.current = self.next; + self.next = temp; + + false + } + + fn forward(&mut self) { + loop { + if !self.heap[self.current].get_mark_bit() { + self.heap[self.current].set_mark_bit(true); + + match self.heap[self.current].get_tag() { + HeapCellValueTag::AttrVar => { + if UMP::forward_attr_var(self) { return; } + } + HeapCellValueTag::Var => { + if self.forward_var() { return; } + } + HeapCellValueTag::Str => { + if self.heap[self.next + 1].get_forwarding_bit() == Some(true) { + if self.backward() { + return; + } else { + continue; + } + } + + let h = self.next; + let arity = cell_as_atom_cell!(self.heap[h]).get_arity(); + + for cell in &mut self.heap[h + 1 .. h + arity + 1] { + cell.set_forwarding_bit(true); + } + + let mut last_cell_loc = h + arity; + + self.next = self.heap[last_cell_loc].get_value(); + self.heap[last_cell_loc].set_value(self.current); + self.current = last_cell_loc; + } + HeapCellValueTag::Lis => { + let mut last_cell_loc = self.next + 1; + + if self.heap[last_cell_loc].get_forwarding_bit() == Some(true) { + if self.backward() { + return; + } else { + continue; + } + } + + self.heap[last_cell_loc].set_forwarding_bit(true); + + self.next = self.heap[last_cell_loc].get_value(); + self.heap[last_cell_loc].set_value(self.current); + self.current = last_cell_loc; + } + HeapCellValueTag::PStrLoc => { + let h = self.next; + let cell = self.heap[h]; + + if self.heap[h+1].get_forwarding_bit() == Some(true) { + if self.backward() { + return; + } else { + continue; + } + } + + if self.heap[h].get_tag() == HeapCellValueTag::PStr { + let mut last_cell_loc = h+1; + self.heap[last_cell_loc].set_forwarding_bit(true); + + self.next = self.heap[last_cell_loc].get_value(); + self.heap[last_cell_loc].set_value(self.current); + self.current = last_cell_loc; + } else { + debug_assert!(self.heap[h].get_tag() == HeapCellValueTag::PStrOffset); + + self.next = self.heap[h].get_value(); + self.heap[h].set_value(self.current); + self.current = h; + } + } + HeapCellValueTag::PStrOffset => { + let h = self.next; + + // mark the Fixnum offset. + UMP::mark(self.heap, self.current+1); + + if self.heap[h].get_tag() == HeapCellValueTag::PStr { + let mut last_cell_loc = h+1; + + if self.heap[last_cell_loc].get_forwarding_bit() == Some(true) { + if self.backward() { + return; + } else { + continue; + } + } + + self.heap[last_cell_loc].set_forwarding_bit(true); + + self.next = self.heap[last_cell_loc].get_value(); + self.heap[last_cell_loc].set_value(self.current); + self.current = last_cell_loc; + } else { + debug_assert!(self.heap[h].get_tag() == HeapCellValueTag::CStr); + + self.next = self.heap[h].get_value(); + self.heap[h].set_value(self.current); + self.current = h; + } + } + HeapCellValueTag::StackVar => { + /* + let cell = self.heap[self.current]; + self.heap[self.current].set_forwarding_bit(true); + return Some(cell); + */ + } + _ => { + if self.backward() { + return; + } + } + } + } else { + if self.backward() { + return; + } + } + } + } + + fn backward(&mut self) -> bool { + while !self.heap[self.current].get_forwarding_bit().unwrap_or(false) { + let temp = self.heap[self.current].get_value(); + + // UMP::mark(self.heap, self.current); + + self.heap[self.current].set_value(self.next); + self.next = self.current; + self.current = temp; + } + + self.heap[self.current].set_forwarding_bit(false); + + // UMP::unmark(self.heap, self.current); + + if self.current == self.start { + return true; + } + + self.current -= 1; + + let temp = self.heap[self.current+1].get_value(); + + self.heap[self.current+1].set_value(self.next); + self.next = self.heap[self.current].get_value(); + self.heap[self.current].set_value(temp); + + false + } + + /* fn backward_and_return(&mut self) -> Option { let current = self.current; @@ -336,8 +511,10 @@ impl<'a, UMP: UnmarkPolicy> StacklessPreOrderHeapIter<'a, UMP> { false } + */ } +/* impl<'a, UMP: UnmarkPolicy> Iterator for StacklessPreOrderHeapIter<'a, UMP> { type Item = HeapCellValue; @@ -346,10 +523,26 @@ impl<'a, UMP: UnmarkPolicy> Iterator for StacklessPreOrderHeapIter<'a, UMP> { self.forward() } } +*/ pub fn mark_cells(heap: &mut Heap, cell: HeapCellValue) { let mut iter = StacklessPreOrderHeapIter::::new(heap, cell); - while let Some(_) = iter.forward() {} + + let print_ptrs = |iter: &StacklessPreOrderHeapIter::| { + println!("self.current = {}, self.next = {}\n", iter.current, iter.next); + }; + + iter.forward(); + + print_heap_terms(iter.heap.iter(), 0); + print_ptrs(&iter); + + /* + while let Some(_) = iter.forward() { + print_heap_terms(iter.heap.iter(), 0); + print_ptrs(&iter); + } + */ } #[cfg(test)] @@ -941,7 +1134,6 @@ mod tests { wam.machine_st.heap.push(list_loc_as_cell!(9)); wam.machine_st.heap.push(heap_loc_as_cell!(9)); wam.machine_st.heap.push(empty_list_as_cell!()); - wam.machine_st.heap.push(attr_var_as_cell!(11)); // linked from 7. wam.machine_st.heap.push(heap_loc_as_cell!(12)); @@ -1118,7 +1310,7 @@ mod tests { wam.machine_st.heap.clear(); - // representation of the heap terms as in issue #1384. + // representation of one of the heap terms as in issue #1384. wam.machine_st.heap.push(list_loc_as_cell!(1)); wam.machine_st.heap.push(empty_list_as_cell!()); @@ -1139,5 +1331,35 @@ mod tests { assert_eq!(unmark_cell_bits!(wam.machine_st.heap[4]), heap_loc_as_cell!(0)); assert_eq!(unmark_cell_bits!(wam.machine_st.heap[5]), empty_list_as_cell!()); assert_eq!(unmark_cell_bits!(wam.machine_st.heap[6]), heap_loc_as_cell!(2)); + + wam.machine_st.heap.clear(); + + // representation of one of the heap terms as in issue #1384. + + println!("DELINEATE"); + + wam.machine_st.heap.push(list_loc_as_cell!(7)); + wam.machine_st.heap.push(heap_loc_as_cell!(0)); + wam.machine_st.heap.push(list_loc_as_cell!(3)); // A = [B|[]]. + wam.machine_st.heap.push(list_loc_as_cell!(5)); // B = [A|A]. + wam.machine_st.heap.push(empty_list_as_cell!()); + wam.machine_st.heap.push(heap_loc_as_cell!(2)); + wam.machine_st.heap.push(heap_loc_as_cell!(2)); + wam.machine_st.heap.push(empty_list_as_cell!()); // C = [[]|B]. + wam.machine_st.heap.push(heap_loc_as_cell!(3)); + + mark_cells(&mut wam.machine_st.heap, heap_loc_as_cell!(0)); + + all_cells_marked_and_unforwarded(&wam.machine_st.heap); + + assert_eq!(unmark_cell_bits!(wam.machine_st.heap[0]), list_loc_as_cell!(7)); + assert_eq!(unmark_cell_bits!(wam.machine_st.heap[1]), heap_loc_as_cell!(0)); + assert_eq!(unmark_cell_bits!(wam.machine_st.heap[2]), list_loc_as_cell!(3)); + assert_eq!(unmark_cell_bits!(wam.machine_st.heap[3]), list_loc_as_cell!(5)); + assert_eq!(unmark_cell_bits!(wam.machine_st.heap[4]), empty_list_as_cell!()); + assert_eq!(unmark_cell_bits!(wam.machine_st.heap[5]), heap_loc_as_cell!(2)); + assert_eq!(unmark_cell_bits!(wam.machine_st.heap[6]), heap_loc_as_cell!(2)); + assert_eq!(unmark_cell_bits!(wam.machine_st.heap[7]), empty_list_as_cell!()); + assert_eq!(unmark_cell_bits!(wam.machine_st.heap[8]), heap_loc_as_cell!(3)); } } diff --git a/src/machine/system_calls.rs b/src/machine/system_calls.rs index aa70337e..c8b999f9 100644 --- a/src/machine/system_calls.rs +++ b/src/machine/system_calls.rs @@ -4906,7 +4906,7 @@ impl Machine { { let orig_heap_len = self.machine_st.heap.len(); - let mut iter = stackless_preorder_iter(&mut self.machine_st.heap, stored_v); + let mut iter = stackful_preorder_iter(&mut self.machine_st.heap, stored_v); while let Some(addr) = iter.next() { let addr = unmark_cell_bits!(addr); -- 2.54.0