From e0f49e8f43e30c20fe3c646a44f32407e097d1d0 Mon Sep 17 00:00:00 2001 From: Mark Date: Fri, 26 May 2023 15:19:07 -0600 Subject: [PATCH] optionally read from machine stack in stackful pre-order iterator (#1812) --- Cargo.lock | 6 + src/heap_iter.rs | 425 +++++++++++++++++++++++++---------- src/heap_print.rs | 93 ++++---- src/machine/loader.rs | 2 +- src/machine/machine_state.rs | 1 + src/machine/mock_wam.rs | 1 + 6 files changed, 374 insertions(+), 154 deletions(-) diff --git a/Cargo.lock b/Cargo.lock index 76c1c10c..364b4891 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -524,6 +524,12 @@ version = "0.1.1" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "00b0228411908ca8685dba7fc2cdd70ec9990a6e753e89b6ac91a84c40fbaf4b" +[[package]] +name = "funty" +version = "2.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e6d5a32815ae3f33302d95fdcb2ce17862f8c65363dcfd29360480ba1001fc9c" + [[package]] name = "futf" version = "0.1.5" diff --git a/src/heap_iter.rs b/src/heap_iter.rs index d7f1f2e4..96aef41d 100644 --- a/src/heap_iter.rs +++ b/src/heap_iter.rs @@ -1,8 +1,9 @@ #[cfg(test)] pub(crate) use crate::machine::gc::{IteratorUMP, StacklessPreOrderHeapIter}; -use crate::machine::heap::*; use crate::atom_table::*; +use crate::machine::heap::*; +use crate::machine::stack::*; use crate::types::*; use modular_bitfield::prelude::*; @@ -18,28 +19,45 @@ enum IterStackLocTag { PendingMark, } +#[derive(BitfieldSpecifier, Clone, Copy, Debug, PartialEq, Eq)] +#[bits = 1] +pub enum HeapOrStackTag { + Heap, + Stack, +} + #[bitfield] #[repr(u64)] #[derive(Clone, Copy, Debug)] pub struct IterStackLoc { - value: B62, + pub value: B61, tag: IterStackLocTag, + heap_or_stack: HeapOrStackTag, } impl IterStackLoc { #[inline] - pub fn iterable_heap_loc(h: usize) -> Self { - IterStackLoc::new().with_tag(IterStackLocTag::Iterable).with_value(h as u64) + pub fn iterable_loc(h: usize, heap_or_stack: HeapOrStackTag) -> Self { + IterStackLoc::new() + .with_tag(IterStackLocTag::Iterable) + .with_heap_or_stack(heap_or_stack) + .with_value(h as u64) } #[inline] - pub fn mark_heap_loc(h: usize) -> Self { - IterStackLoc::new().with_tag(IterStackLocTag::Marked).with_value(h as u64) + fn mark_loc(h: usize, heap_or_stack: HeapOrStackTag) -> Self { + IterStackLoc::new() + .with_tag(IterStackLocTag::Marked) + .with_heap_or_stack(heap_or_stack) + .with_value(h as u64) } #[inline] - pub fn pending_mark_heap_loc(h: usize) -> Self { - IterStackLoc::new().with_tag(IterStackLocTag::PendingMark).with_value(h as u64) + fn pending_mark_loc(h: usize, heap_or_stack: HeapOrStackTag) -> Self { + IterStackLoc::new() + .with_tag(IterStackLocTag::PendingMark) + .with_heap_or_stack(heap_or_stack) + .with_value(h as u64) } #[inline] @@ -51,38 +69,35 @@ impl IterStackLoc { pub fn is_pending_mark(self) -> bool { self.tag() == IterStackLocTag::PendingMark } -} -#[inline] -fn forward_if_referent_marked(heap: &mut [HeapCellValue], h: usize) { - read_heap_cell!(heap[h], - (HeapCellValueTag::Str - | HeapCellValueTag::Lis - | HeapCellValueTag::AttrVar - | HeapCellValueTag::Var - | HeapCellValueTag::PStrLoc, vh) => { - if heap[vh].get_mark_bit() { - heap[h].set_forwarding_bit(true); + #[inline] + pub fn as_ref(self) -> Ref { + match self.heap_or_stack() { + HeapOrStackTag::Heap => { + Ref::heap_cell(self.value() as usize) + } + HeapOrStackTag::Stack => { + Ref::stack_cell(self.value() as usize) } } - _ => {} - ) + } } #[derive(Debug)] pub struct StackfulPreOrderHeapIter<'a> { pub heap: &'a mut Vec, + pub machine_stack: &'a mut Stack, stack: Vec, - h: usize, + h: IterStackLoc, } impl<'a> Drop for StackfulPreOrderHeapIter<'a> { fn drop(&mut self) { while let Some(h) = self.stack.pop() { - let h = h.value() as usize; + let cell = self.read_cell_mut(h); - self.heap[h].set_forwarding_bit(false); - self.heap[h].set_mark_bit(false); + cell.set_forwarding_bit(false); + cell.set_mark_bit(false); } self.heap.pop(); @@ -90,48 +105,93 @@ impl<'a> Drop for StackfulPreOrderHeapIter<'a> { } pub trait FocusedHeapIter: Iterator { - fn focus(&self) -> usize; + fn focus(&self) -> IterStackLoc; } impl<'a> FocusedHeapIter for StackfulPreOrderHeapIter<'a> { #[inline] - fn focus(&self) -> usize { + fn focus(&self) -> IterStackLoc { self.h } } impl<'a> StackfulPreOrderHeapIter<'a> { #[inline] - fn new(heap: &'a mut Vec, cell: HeapCellValue) -> Self { - let h = heap.len(); + fn new(heap: &'a mut Vec, stack: &'a mut Stack, cell: HeapCellValue) -> Self { + let h = IterStackLoc::iterable_loc(heap.len(), HeapOrStackTag::Heap); heap.push(cell); Self { heap, h, - stack: vec![IterStackLoc::iterable_heap_loc(h)], + machine_stack: stack, + stack: vec![h], + } + } + + #[inline] + fn forward_if_referent_marked(&mut self, loc: IterStackLoc) { + read_heap_cell!(self.read_cell(loc), + (HeapCellValueTag::Str | + HeapCellValueTag::Lis | + HeapCellValueTag::AttrVar | + HeapCellValueTag::Var | + HeapCellValueTag::PStrLoc, vh) => { + if self.heap[vh].get_mark_bit() { + self.read_cell_mut(loc).set_forwarding_bit(true); + } + } + (HeapCellValueTag::StackVar, vs) => { + if self.machine_stack[vs].get_mark_bit() { + self.read_cell_mut(loc).set_forwarding_bit(true); + } + } + _ => {} + ); + } + + #[inline] + pub fn push_stack(&mut self, h: IterStackLoc) { + self.stack.push(h); + } + + #[inline] + pub fn read_cell_mut(&mut self, loc: IterStackLoc) -> &mut HeapCellValue { + match loc.heap_or_stack() { + HeapOrStackTag::Heap => { + &mut self.heap[loc.value() as usize] + } + HeapOrStackTag::Stack => { + &mut self.machine_stack[loc.value() as usize] + } } } #[inline] - pub fn push_stack(&mut self, h: usize) { - self.stack.push(IterStackLoc::iterable_heap_loc(h)); + pub fn read_cell(&self, loc: IterStackLoc) -> HeapCellValue { + match loc.heap_or_stack() { + HeapOrStackTag::Heap => { + self.heap[loc.value() as usize] + } + HeapOrStackTag::Stack => { + self.machine_stack[loc.value() as usize] + } + } } #[inline] - pub fn stack_last(&self) -> Option { + pub fn stack_last(&self) -> Option { for h in self.stack.iter().rev() { let is_readable_marked = h.is_marked(); - let h = h.value() as usize; - let cell = self.heap[h]; + let cell = self.read_cell(*h); if cell.get_forwarding_bit() { - return Some(h); + return Some(*h); } else if cell.get_mark_bit() && !is_readable_marked { continue; } - return Some(h); + return Some(*h); } None @@ -141,10 +201,9 @@ impl<'a> StackfulPreOrderHeapIter<'a> { pub fn pop_stack(&mut self) -> Option { while let Some(h) = self.stack.pop() { let is_readable_marked = h.is_marked(); - let h = h.value() as usize; - self.h = h; - let cell = &mut self.heap[h]; + self.h = h; + let cell = self.read_cell_mut(h); if cell.get_forwarding_bit() { cell.set_forwarding_bit(false); @@ -159,30 +218,29 @@ impl<'a> StackfulPreOrderHeapIter<'a> { None } - fn push_if_unmarked(&mut self, h: usize) { - if !self.heap[h].get_mark_bit() { - self.heap[h].set_mark_bit(true); - self.stack.push(IterStackLoc::iterable_heap_loc(h)); + fn push_if_unmarked(&mut self, loc: IterStackLoc) { + let cell = self.read_cell_mut(loc); + + if !cell.get_mark_bit() { + cell.set_mark_bit(true); + self.stack.push(IterStackLoc::iterable_loc(loc.value() as usize, loc.heap_or_stack())); } } fn follow(&mut self) -> Option { while let Some(h) = self.stack.pop() { if h.is_pending_mark() { - let h = h.value() as usize; - self.push_if_unmarked(h); - self.stack.push(IterStackLoc::mark_heap_loc(h)); + self.stack.push(IterStackLoc::mark_loc(h.value() as usize, h.heap_or_stack())); - forward_if_referent_marked(&mut self.heap, h); + self.forward_if_referent_marked(h); continue; } - let is_readable_marked = h.is_marked(); - let h = h.value() as usize; - self.h = h; - let cell = &mut self.heap[h]; + + let is_readable_marked = h.is_marked(); + let cell = self.read_cell_mut(h); if cell.get_forwarding_bit() { let copy = *cell; @@ -195,50 +253,68 @@ impl<'a> StackfulPreOrderHeapIter<'a> { read_heap_cell!(*cell, (HeapCellValueTag::Str | HeapCellValueTag::PStrLoc, vh) => { - self.push_if_unmarked(vh); - self.stack.push(IterStackLoc::mark_heap_loc(vh)); + let loc = IterStackLoc::iterable_loc(vh, HeapOrStackTag::Heap); + + self.push_if_unmarked(loc); + self.stack.push(IterStackLoc::mark_loc(vh, HeapOrStackTag::Heap)); } (HeapCellValueTag::Lis, vh) => { - self.push_if_unmarked(vh); + let loc = IterStackLoc::iterable_loc(vh, HeapOrStackTag::Heap); + + self.push_if_unmarked(loc); - self.stack.push(IterStackLoc::pending_mark_heap_loc(vh + 1)); - self.stack.push(IterStackLoc::mark_heap_loc(vh)); + self.stack.push(IterStackLoc::pending_mark_loc(vh + 1, HeapOrStackTag::Heap)); + self.stack.push(IterStackLoc::mark_loc(vh, HeapOrStackTag::Heap)); - forward_if_referent_marked(&mut self.heap, vh); + self.forward_if_referent_marked(loc); - return Some(self.heap[h]); + return Some(self.read_cell(h)); } (HeapCellValueTag::AttrVar | HeapCellValueTag::Var, vh) => { - self.push_if_unmarked(vh); - self.stack.push(IterStackLoc::mark_heap_loc(vh)); - forward_if_referent_marked(&mut self.heap, vh); + let loc = IterStackLoc::iterable_loc(vh, HeapOrStackTag::Heap); + + self.push_if_unmarked(loc); + self.stack.push(IterStackLoc::mark_loc(vh, HeapOrStackTag::Heap)); + self.forward_if_referent_marked(loc); + } + (HeapCellValueTag::StackVar, vs) => { + let loc = IterStackLoc::iterable_loc(vs, HeapOrStackTag::Stack); + + self.push_if_unmarked(loc); + self.stack.push(IterStackLoc::mark_loc(vs, HeapOrStackTag::Stack)); + self.forward_if_referent_marked(loc); } (HeapCellValueTag::PStrOffset, offset) => { - self.push_if_unmarked(offset); - self.stack.push(IterStackLoc::iterable_heap_loc(h+1)); + self.push_if_unmarked(IterStackLoc::iterable_loc(offset, HeapOrStackTag::Heap)); + self.stack.push(IterStackLoc::iterable_loc((h.value()+1) as usize, HeapOrStackTag::Heap)); - return Some(self.heap[h]); + return Some(self.read_cell(h)); } (HeapCellValueTag::PStr) => { - self.push_if_unmarked(h); + let tail_loc = IterStackLoc::iterable_loc((h.value()+1) as usize, HeapOrStackTag::Heap); - self.stack.push(IterStackLoc::iterable_heap_loc(h+1)); - forward_if_referent_marked(&mut self.heap, h+1); + self.push_if_unmarked(IterStackLoc::iterable_loc(h.value() as usize, HeapOrStackTag::Heap)); + self.stack.push(tail_loc); + self.forward_if_referent_marked(tail_loc); - return Some(self.heap[h]); + return Some(self.read_cell(h)); } (HeapCellValueTag::Atom, (_name, arity)) => { - for h in (h + 2 .. h + arity + 1).rev() { - self.stack.push(IterStackLoc::pending_mark_heap_loc(h)); + let l = h.value() as usize; + + for l in (l + 2 .. l + arity + 1).rev() { + self.stack.push(IterStackLoc::pending_mark_loc(l, HeapOrStackTag::Heap)); } if arity > 0 { - self.push_if_unmarked(h+1); - self.stack.push(IterStackLoc::mark_heap_loc(h+1)); - forward_if_referent_marked(&mut self.heap, h+1); + let first_arg_loc = IterStackLoc::iterable_loc(l+1, HeapOrStackTag::Heap); + + self.push_if_unmarked(first_arg_loc); + self.stack.push(IterStackLoc::mark_loc(l+1, HeapOrStackTag::Heap)); + self.forward_if_referent_marked(first_arg_loc); } - return Some(self.heap[h]); + return Some(self.read_cell(h)); } _ => { return Some(*cell); @@ -269,19 +345,20 @@ pub(crate) fn stackless_preorder_iter( } #[inline(always)] -pub(crate) fn stackful_preorder_iter( - heap: &mut Vec, +pub(crate) fn stackful_preorder_iter<'a>( + heap: &'a mut Vec, + stack: &'a mut Stack, cell: HeapCellValue, -) -> StackfulPreOrderHeapIter { - StackfulPreOrderHeapIter::new(heap, cell) +) -> StackfulPreOrderHeapIter<'a> { + StackfulPreOrderHeapIter::new(heap, stack, cell) } #[derive(Debug)] pub(crate) struct PostOrderIterator { - focus: usize, + focus: IterStackLoc, base_iter: Iter, base_iter_valid: bool, - parent_stack: Vec<(usize, HeapCellValue, usize)>, // number of children, parent node, focus. + parent_stack: Vec<(usize, HeapCellValue, IterStackLoc)>, // number of children, parent node, focus. } impl Deref for PostOrderIterator { @@ -295,7 +372,7 @@ impl Deref for PostOrderIterator { impl PostOrderIterator { pub(crate) fn new(base_iter: Iter) -> Self { PostOrderIterator { - focus: 0, + focus: IterStackLoc::iterable_loc(0, HeapOrStackTag::Heap), base_iter, base_iter_valid: true, parent_stack: vec![], @@ -352,7 +429,7 @@ impl Iterator for PostOrderIterator { impl FocusedHeapIter for PostOrderIterator { #[inline(always)] - fn focus(&self) -> usize { + fn focus(&self) -> IterStackLoc { self.focus } } @@ -368,7 +445,8 @@ impl PostOrderIterator { if let Some((_child_count, item, focus)) = self.parent_stack.last() { read_heap_cell!(item, (HeapCellValueTag::Atom, (_name, arity)) => { - return focus + arity >= idx_loc && *focus < idx_loc; + let focus = focus.value() as usize; + return focus + arity >= idx_loc && focus < idx_loc; } _ => {} ); @@ -401,9 +479,10 @@ impl<'a> LeftistPostOrderHeapIter<'a> { #[inline] pub(crate) fn stackful_post_order_iter<'a>( heap: &'a mut Heap, + stack: &'a mut Stack, cell: HeapCellValue, ) -> LeftistPostOrderHeapIter<'a> { - PostOrderIterator::new(StackfulPreOrderHeapIter::new(heap, cell)) + PostOrderIterator::new(StackfulPreOrderHeapIter::new(heap, stack, cell)) } #[cfg(test)] @@ -424,6 +503,7 @@ mod tests { use super::*; use crate::machine::mock_wam::*; + #[test] fn heap_stackless_iter_tests() { let mut wam = MockWAM::new(); @@ -1381,7 +1461,11 @@ mod tests { .extend(functor!(f_atom, [atom(a_atom), atom(b_atom)])); { - let mut iter = StackfulPreOrderHeapIter::new(&mut wam.machine_st.heap, str_loc_as_cell!(0)); + let mut iter = StackfulPreOrderHeapIter::new( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + str_loc_as_cell!(0), + ); assert_eq!( unmark_cell_bits!(iter.next().unwrap()), @@ -1412,7 +1496,11 @@ mod tests { )); for _ in 0..20 { - let mut iter = StackfulPreOrderHeapIter::new(&mut wam.machine_st.heap, str_loc_as_cell!(0)); + let mut iter = StackfulPreOrderHeapIter::new( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + str_loc_as_cell!(0), + ); assert_eq!( unmark_cell_bits!(iter.next().unwrap()), @@ -1440,7 +1528,12 @@ mod tests { { wam.machine_st.heap.push(heap_loc_as_cell!(0)); - let mut iter = StackfulPreOrderHeapIter::new(&mut wam.machine_st.heap, heap_loc_as_cell!(0)); + let mut iter = StackfulPreOrderHeapIter::new( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + heap_loc_as_cell!(0), + ); + let mut var = heap_loc_as_cell!(0); // self-referencing variables are copied with their forwarding @@ -1462,7 +1555,11 @@ mod tests { wam.machine_st.heap.push(heap_loc_as_cell!(1)); wam.machine_st.heap.push(heap_loc_as_cell!(0)); - let mut iter = StackfulPreOrderHeapIter::new(&mut wam.machine_st.heap, heap_loc_as_cell!(0)); + let mut iter = StackfulPreOrderHeapIter::new( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + heap_loc_as_cell!(0), + ); assert_eq!( unmark_cell_bits!(iter.next().unwrap()), @@ -1482,7 +1579,11 @@ mod tests { wam.machine_st.heap.push(empty_list_as_cell!()); { - let mut iter = StackfulPreOrderHeapIter::new(&mut wam.machine_st.heap, heap_loc_as_cell!(0)); + let mut iter = StackfulPreOrderHeapIter::new( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + heap_loc_as_cell!(0), + ); assert_eq!( unmark_cell_bits!(iter.next().unwrap()), @@ -1514,7 +1615,11 @@ mod tests { wam.machine_st.heap.push(heap_loc_as_cell!(0)); { - let mut iter = StackfulPreOrderHeapIter::new(&mut wam.machine_st.heap, heap_loc_as_cell!(0)); + let mut iter = StackfulPreOrderHeapIter::new( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + heap_loc_as_cell!(0), + ); // the cycle will be iterated twice before being detected. assert_eq!( @@ -1542,7 +1647,11 @@ mod tests { } { - let mut iter = StackfulPreOrderHeapIter::new(&mut wam.machine_st.heap, heap_loc_as_cell!(0)); + let mut iter = StackfulPreOrderHeapIter::new( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + heap_loc_as_cell!(0), + ); // cut the iteration short to check that all cells are // unmarked and unforwarded by the Drop instance of @@ -1576,7 +1685,11 @@ mod tests { let pstr_cell = wam.machine_st.heap[pstr_var_cell.get_value() as usize]; { - let mut iter = StackfulPreOrderHeapIter::new(&mut wam.machine_st.heap, heap_loc_as_cell!(0)); + let mut iter = StackfulPreOrderHeapIter::new( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + heap_loc_as_cell!(0), + ); assert_eq!(unmark_cell_bits!(iter.next().unwrap()), pstr_cell); assert_eq!( @@ -1596,7 +1709,11 @@ mod tests { let pstr_second_cell = wam.machine_st.heap[pstr_second_var_cell.get_value() as usize]; { - let mut iter = stackful_preorder_iter(&mut wam.machine_st.heap, heap_loc_as_cell!(0)); + let mut iter = stackful_preorder_iter( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + heap_loc_as_cell!(0), + ); assert_eq!(unmark_cell_bits!(iter.next().unwrap()), pstr_cell); assert_eq!(unmark_cell_bits!(iter.next().unwrap()), pstr_second_cell); @@ -1615,7 +1732,12 @@ mod tests { wam.machine_st.heap.push(fixnum_as_cell!(Fixnum::build_with(0i64))); { - let mut iter = stackful_preorder_iter(&mut wam.machine_st.heap, pstr_loc_as_cell!(0)); + let mut iter = stackful_preorder_iter( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + pstr_loc_as_cell!(0), + ); + let pstr_offset_cell = pstr_offset_as_cell!(0); // pstr_offset_cell.set_forwarding_bit(true); @@ -1640,7 +1762,12 @@ mod tests { wam.machine_st.heap.push(fixnum_as_cell!(Fixnum::build_with(1i64))); { - let mut iter = stackful_preorder_iter(&mut wam.machine_st.heap, pstr_loc_as_cell!(0)); + let mut iter = stackful_preorder_iter( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + pstr_loc_as_cell!(0), + ); + let pstr_offset_cell = pstr_offset_as_cell!(0); // pstr_offset_cell.set_forwarding_bit(true); @@ -1653,7 +1780,7 @@ mod tests { let h = iter.focus(); - assert_eq!(h, 5); + assert_eq!(h.value(), 5); assert_eq!(unmark_cell_bits!(iter.heap[4]), pstr_offset_as_cell!(0)); assert_eq!(unmark_cell_bits!(iter.heap[5]), fixnum_as_cell!(Fixnum::build_with(1i64))); @@ -1673,7 +1800,11 @@ mod tests { wam.machine_st.heap.extend(functor); { - let mut iter = StackfulPreOrderHeapIter::new(&mut wam.machine_st.heap, heap_loc_as_cell!(0)); + let mut iter = StackfulPreOrderHeapIter::new( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + heap_loc_as_cell!(0), + ); assert_eq!( unmark_cell_bits!(iter.next().unwrap()), @@ -1732,7 +1863,11 @@ mod tests { wam.machine_st.heap[4] = list_loc_as_cell!(1); { - let mut iter = stackful_preorder_iter(&mut wam.machine_st.heap, heap_loc_as_cell!(0)); + let mut iter = stackful_preorder_iter( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + heap_loc_as_cell!(0), + ); assert_eq!( unmark_cell_bits!(iter.next().unwrap()), @@ -1799,6 +1934,7 @@ mod tests { { let mut iter = StackfulPreOrderHeapIter::new( &mut wam.machine_st.heap, + &mut wam.machine_st.stack, heap_loc_as_cell!(0), ); @@ -1830,6 +1966,7 @@ mod tests { { let mut iter = stackful_preorder_iter( &mut wam.machine_st.heap, + &mut wam.machine_st.stack, heap_loc_as_cell!(0), ); @@ -1864,6 +2001,7 @@ mod tests { { let mut iter = stackful_preorder_iter( &mut wam.machine_st.heap, + &mut wam.machine_st.stack, heap_loc_as_cell!(0), ); @@ -1898,7 +2036,11 @@ mod tests { .extend(functor!(f_atom, [atom(a_atom), atom(b_atom)])); { - let mut iter = stackful_post_order_iter(&mut wam.machine_st.heap, str_loc_as_cell!(0)); + let mut iter = stackful_post_order_iter( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + str_loc_as_cell!(0), + ); assert_eq!( unmark_cell_bits!(iter.next().unwrap()), @@ -1929,7 +2071,11 @@ mod tests { )); for _ in 0..20 { // 0000 { - let mut iter = stackful_post_order_iter(&mut wam.machine_st.heap, str_loc_as_cell!(0)); + let mut iter = stackful_post_order_iter( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + str_loc_as_cell!(0), + ); assert_eq!( unmark_cell_bits!(iter.next().unwrap()), @@ -1959,7 +2105,12 @@ mod tests { { wam.machine_st.heap.push(heap_loc_as_cell!(0)); - let mut iter = stackful_post_order_iter(&mut wam.machine_st.heap, heap_loc_as_cell!(0)); + let mut iter = stackful_post_order_iter( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + heap_loc_as_cell!(0), + ); + let mut var = heap_loc_as_cell!(0); // self-referencing variables are copied with their forwarding @@ -1981,7 +2132,11 @@ mod tests { wam.machine_st.heap.push(heap_loc_as_cell!(1)); wam.machine_st.heap.push(heap_loc_as_cell!(0)); - let mut iter = stackful_post_order_iter(&mut wam.machine_st.heap, heap_loc_as_cell!(0)); + let mut iter = stackful_post_order_iter( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + heap_loc_as_cell!(0), + ); assert_eq!( unmark_cell_bits!(iter.next().unwrap()), @@ -2001,7 +2156,11 @@ mod tests { wam.machine_st.heap.push(empty_list_as_cell!()); { - let mut iter = stackful_post_order_iter(&mut wam.machine_st.heap, heap_loc_as_cell!(0)); + let mut iter = stackful_post_order_iter( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + heap_loc_as_cell!(0), + ); assert_eq!( unmark_cell_bits!(iter.next().unwrap()), @@ -2033,7 +2192,11 @@ mod tests { wam.machine_st.heap.push(heap_loc_as_cell!(0)); { - let mut iter = stackful_post_order_iter(&mut wam.machine_st.heap, heap_loc_as_cell!(0)); + let mut iter = stackful_post_order_iter( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + heap_loc_as_cell!(0), + ); // the cycle will be iterated twice before being detected. assert_eq!( @@ -2063,6 +2226,7 @@ mod tests { { let mut iter = stackful_post_order_iter( &mut wam.machine_st.heap, + &mut wam.machine_st.stack, heap_loc_as_cell!(0), ); @@ -2098,7 +2262,11 @@ mod tests { let pstr_cell = wam.machine_st.heap[pstr_var_cell.get_value() as usize]; { - let mut iter = stackful_post_order_iter(&mut wam.machine_st.heap, pstr_loc_as_cell!(0)); + let mut iter = stackful_post_order_iter( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + pstr_loc_as_cell!(0), + ); assert_eq!( unmark_cell_bits!(iter.next().unwrap()), @@ -2117,7 +2285,11 @@ mod tests { let pstr_second_cell = wam.machine_st.heap[pstr_second_var_cell.get_value() as usize]; { - let mut iter = stackful_post_order_iter(&mut wam.machine_st.heap, pstr_loc_as_cell!(0)); + let mut iter = stackful_post_order_iter( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + pstr_loc_as_cell!(0), + ); assert_eq!( unmark_cell_bits!(iter.next().unwrap()), @@ -2136,7 +2308,11 @@ mod tests { wam.machine_st.heap.push(fixnum_as_cell!(Fixnum::build_with(0i64))); { - let mut iter = stackful_post_order_iter(&mut wam.machine_st.heap, pstr_loc_as_cell!(0)); + let mut iter = stackful_post_order_iter( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + pstr_loc_as_cell!(0), + ); assert_eq!(iter.next().unwrap(), fixnum_as_cell!(Fixnum::build_with(0i64))); assert_eq!(unmark_cell_bits!(iter.next().unwrap()), pstr_offset_as_cell!(0)); @@ -2151,7 +2327,11 @@ mod tests { wam.machine_st.heap.push(fixnum_as_cell!(Fixnum::build_with(1i64))); { - let mut iter = stackful_post_order_iter(&mut wam.machine_st.heap, pstr_loc_as_cell!(0)); + let mut iter = stackful_post_order_iter( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + pstr_loc_as_cell!(0), + ); assert_eq!(iter.next().unwrap(), fixnum_as_cell!(Fixnum::build_with(1i64))); assert_eq!(unmark_cell_bits!(iter.next().unwrap()), pstr_offset_as_cell!(0)); @@ -2175,7 +2355,11 @@ mod tests { wam.machine_st.heap.extend(functor); { - let mut iter = stackful_post_order_iter(&mut wam.machine_st.heap, heap_loc_as_cell!(0)); + let mut iter = stackful_post_order_iter( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + heap_loc_as_cell!(0), + ); assert_eq!( unmark_cell_bits!(iter.next().unwrap()), @@ -2235,7 +2419,11 @@ mod tests { wam.machine_st.heap[4] = list_loc_as_cell!(1); { - let mut iter = stackful_post_order_iter(&mut wam.machine_st.heap, heap_loc_as_cell!(0)); + let mut iter = stackful_post_order_iter( + &mut wam.machine_st.heap, + &mut wam.machine_st.stack, + heap_loc_as_cell!(0), + ); assert_eq!( unmark_cell_bits!(iter.next().unwrap()), @@ -2342,7 +2530,10 @@ mod tests { )); for _ in 0..20 { - let mut iter = stackless_post_order_iter(&mut wam.machine_st.heap, str_loc_as_cell!(0)); + let mut iter = stackless_post_order_iter( + &mut wam.machine_st.heap, + str_loc_as_cell!(0), + ); assert_eq!(unmark_cell_bits!(iter.next().unwrap()), str_loc_as_cell!(0)); @@ -2372,7 +2563,10 @@ mod tests { { wam.machine_st.heap.push(heap_loc_as_cell!(0)); - let mut iter = stackless_post_order_iter(&mut wam.machine_st.heap, heap_loc_as_cell!(0)); + let mut iter = stackless_post_order_iter( + &mut wam.machine_st.heap, + heap_loc_as_cell!(0), + ); assert_eq!( unmark_cell_bits!(iter.next().unwrap()), @@ -2388,7 +2582,10 @@ mod tests { wam.machine_st.heap.push(heap_loc_as_cell!(1)); wam.machine_st.heap.push(heap_loc_as_cell!(0)); - let mut iter = stackless_post_order_iter(&mut wam.machine_st.heap, heap_loc_as_cell!(0)); + let mut iter = stackless_post_order_iter( + &mut wam.machine_st.heap, + heap_loc_as_cell!(0), + ); assert_eq!( unmark_cell_bits!(iter.next().unwrap()), diff --git a/src/heap_print.rs b/src/heap_print.rs index dfb2efde..26f3f5d2 100644 --- a/src/heap_print.rs +++ b/src/heap_print.rs @@ -14,6 +14,7 @@ use crate::machine::heap::*; use crate::machine::machine_indices::*; use crate::machine::machine_state::pstr_loc_and_offset; use crate::machine::partial_string::*; +use crate::machine::stack::*; use crate::machine::streams::*; use crate::types::*; @@ -474,6 +475,7 @@ pub struct HCPrinter<'a, Outputter> { outputter: Outputter, iter: StackfulPreOrderHeapIter<'a>, atom_tbl: &'a mut AtomTable, + stack: &'a Stack, op_dir: &'a OpDir, state_stack: Vec, toplevel_spec: Option, @@ -539,6 +541,7 @@ impl<'a, Outputter: HCValueOutputter> HCPrinter<'a, Outputter> { pub fn new( heap: &'a mut Heap, atom_tbl: &'a mut AtomTable, + stack: &'a Stack, op_dir: &'a OpDir, output: Outputter, cell: HeapCellValue, @@ -547,6 +550,7 @@ impl<'a, Outputter: HCValueOutputter> HCPrinter<'a, Outputter> { outputter: output, iter: stackful_preorder_iter(heap, cell), atom_tbl, + stack, op_dir, state_stack: vec![], toplevel_spec: None, @@ -1443,12 +1447,7 @@ impl<'a, Outputter: HCValueOutputter> HCPrinter<'a, Outputter> { ) { let negated_operand = negated_op_needs_bracketing(&self.iter, self.op_dir, &op); - let addr = match self.check_for_seen() { - Some(addr) => addr, - None => return, - }; - - let print_atom = |printer: &mut Self, name: Atom, arity: usize| { + let print_struct = |printer: &mut Self, name: Atom, arity: usize| { if name == atom!("[]") && arity == 0 { if !printer.at_cdr("") { append_str!(printer, "[]"); @@ -1496,29 +1495,33 @@ impl<'a, Outputter: HCValueOutputter> HCPrinter<'a, Outputter> { } }; + let addr = match self.check_for_seen() { + Some(addr) => addr, + None => return, + }; + read_heap_cell!(addr, (HeapCellValueTag::Atom, (name, arity)) => { - print_atom(self, name, arity); + print_struct(self, name, arity); } (HeapCellValueTag::Char, c) => { let name = self.atom_tbl.build_with(&String::from(c)); - print_atom(self, name, 0); - // print_char!(self, self.quoted, c); + print_struct(self, name, 0); } (HeapCellValueTag::Str, s) => { let (name, arity) = cell_as_atom_cell!(self.iter.heap[s]) .get_name_and_arity(); if let Some(spec) = fetch_op_spec(name, arity, self.op_dir) { - self.handle_op_as_struct( - name, - arity, - &op, - is_functor_redirect, - spec, - negated_operand, - max_depth, - ); + self.handle_op_as_struct( + name, + arity, + &op, + is_functor_redirect, + spec, + negated_operand, + max_depth, + ); } else { push_space_if_amb!(self, name.as_str(), { self.format_clause(max_depth, arity, name, None); @@ -1553,27 +1556,27 @@ impl<'a, Outputter: HCValueOutputter> HCPrinter<'a, Outputter> { } (HeapCellValueTag::Cons, c) => { match_untyped_arena_ptr!(c, - (ArenaHeaderTag::Integer, n) => { - self.print_number(max_depth, NumberFocus::Unfocused(Number::Integer(n)), &op); - } - (ArenaHeaderTag::Rational, r) => { - self.print_number(max_depth, NumberFocus::Unfocused(Number::Rational(r)), &op); - } - (ArenaHeaderTag::Stream, stream) => { - self.print_stream(stream, max_depth); - } - (ArenaHeaderTag::OssifiedOpDir, _op_dir) => { - self.print_impromptu_atom(atom!("$ossified_op_dir")); - } - (ArenaHeaderTag::Dropped, _value) => { - self.print_impromptu_atom(atom!("$dropped_value")); - } - (ArenaHeaderTag::IndexPtr, index_ptr) => { - self.print_index_ptr(*index_ptr, max_depth); - } - _ => { - } - ); + (ArenaHeaderTag::Integer, n) => { + self.print_number(max_depth, NumberFocus::Unfocused(Number::Integer(n)), &op); + } + (ArenaHeaderTag::Rational, r) => { + self.print_number(max_depth, NumberFocus::Unfocused(Number::Rational(r)), &op); + } + (ArenaHeaderTag::Stream, stream) => { + self.print_stream(stream, max_depth); + } + (ArenaHeaderTag::OssifiedOpDir, _op_dir) => { + self.print_impromptu_atom(atom!("$ossified_op_dir")); + } + (ArenaHeaderTag::Dropped, _value) => { + self.print_impromptu_atom(atom!("$dropped_value")); + } + (ArenaHeaderTag::IndexPtr, index_ptr) => { + self.print_index_ptr(*index_ptr, max_depth); + } + _ => { + } + ); } _ => { unreachable!() @@ -1596,6 +1599,8 @@ impl<'a, Outputter: HCValueOutputter> HCPrinter<'a, Outputter> { pub fn print(mut self) -> Outputter { let spec = self.toplevel_spec.take(); + + self.iter.iterate_over_machine_stack(self.stack); self.handle_heap_term(spec, false, self.max_depth); while let Some(loc_data) = self.state_stack.pop() { @@ -1667,6 +1672,7 @@ mod tests { let printer = HCPrinter::new( &mut wam.machine_st.heap, &mut wam.machine_st.atom_tbl, + &wam.machine_st.stack, &wam.op_dir, PrinterOutputter::new(), heap_loc_as_cell!(0) @@ -1695,6 +1701,7 @@ mod tests { let printer = HCPrinter::new( &mut wam.machine_st.heap, &mut wam.machine_st.atom_tbl, + &wam.machine_st.stack, &wam.op_dir, PrinterOutputter::new(), heap_loc_as_cell!(0) @@ -1718,6 +1725,7 @@ mod tests { let printer = HCPrinter::new( &mut wam.machine_st.heap, &mut wam.machine_st.atom_tbl, + &wam.machine_st.stack, &wam.op_dir, PrinterOutputter::new(), heap_loc_as_cell!(0) @@ -1730,6 +1738,7 @@ mod tests { let mut printer = HCPrinter::new( &mut wam.machine_st.heap, &mut wam.machine_st.atom_tbl, + &wam.machine_st.stack, &wam.op_dir, PrinterOutputter::new(), heap_loc_as_cell!(0) @@ -1760,6 +1769,7 @@ mod tests { let printer = HCPrinter::new( &mut wam.machine_st.heap, &mut wam.machine_st.atom_tbl, + &wam.machine_st.stack, &wam.op_dir, PrinterOutputter::new(), heap_loc_as_cell!(0), @@ -1778,6 +1788,7 @@ mod tests { let printer = HCPrinter::new( &mut wam.machine_st.heap, &mut wam.machine_st.atom_tbl, + &wam.machine_st.stack, &wam.op_dir, PrinterOutputter::new(), heap_loc_as_cell!(0), @@ -1794,6 +1805,7 @@ mod tests { let mut printer = HCPrinter::new( &mut wam.machine_st.heap, &mut wam.machine_st.atom_tbl, + &wam.machine_st.stack, &wam.op_dir, PrinterOutputter::new(), heap_loc_as_cell!(0) @@ -1823,6 +1835,7 @@ mod tests { let mut printer = HCPrinter::new( &mut wam.machine_st.heap, &mut wam.machine_st.atom_tbl, + &wam.machine_st.stack, &wam.op_dir, PrinterOutputter::new(), heap_loc_as_cell!(0) @@ -1845,6 +1858,7 @@ mod tests { let printer = HCPrinter::new( &mut wam.machine_st.heap, &mut wam.machine_st.atom_tbl, + &wam.machine_st.stack, &wam.op_dir, PrinterOutputter::new(), pstr_loc_as_cell!(0) @@ -1872,6 +1886,7 @@ mod tests { let printer = HCPrinter::new( &mut wam.machine_st.heap, &mut wam.machine_st.atom_tbl, + &wam.machine_st.stack, &wam.op_dir, PrinterOutputter::new(), heap_loc_as_cell!(0), diff --git a/src/machine/loader.rs b/src/machine/loader.rs index 51815c7e..6c98024c 100644 --- a/src/machine/loader.rs +++ b/src/machine/loader.rs @@ -1404,7 +1404,7 @@ impl MachineState { let term_addr = self[r]; let mut term_stack = vec![]; - let mut iter = stackful_post_order_iter(&mut self.heap, term_addr); + let mut iter = stackful_post_order_iter(&mut self.heap, &mut self.stack, term_addr); while let Some(addr) = iter.next() { let addr = unmark_cell_bits!(addr); diff --git a/src/machine/machine_state.rs b/src/machine/machine_state.rs index 7d0f6c77..0203f62f 100644 --- a/src/machine/machine_state.rs +++ b/src/machine/machine_state.rs @@ -765,6 +765,7 @@ impl MachineState { let mut printer = HCPrinter::new( &mut self.heap, &mut self.atom_tbl, + &mut self.stack, op_dir, PrinterOutputter::new(), term_to_be_printed, diff --git a/src/machine/mock_wam.rs b/src/machine/mock_wam.rs index 2ddde129..f71f32e3 100644 --- a/src/machine/mock_wam.rs +++ b/src/machine/mock_wam.rs @@ -62,6 +62,7 @@ impl MockWAM { let mut printer = HCPrinter::new( &mut self.machine_st.heap, &mut self.machine_st.atom_tbl, + &mut self.machine_st.stack, &self.op_dir, PrinterOutputter::new(), heap_loc_as_cell!(term_write_result.heap_loc), -- 2.54.0