From 064bfa5e0deb003a1ce6277e7fd822475e4eaf7e Mon Sep 17 00:00:00 2001 From: Mark Thom Date: Thu, 7 Apr 2022 20:48:40 -0600 Subject: [PATCH] fix loop in stackful iterator (#1405, #1384) --- src/heap_iter.rs | 31 +++++++++--------- src/heap_print.rs | 83 ++++++++++++++++++++++------------------------- 2 files changed, 55 insertions(+), 59 deletions(-) diff --git a/src/heap_iter.rs b/src/heap_iter.rs index 8c40d56a..b8670de3 100644 --- a/src/heap_iter.rs +++ b/src/heap_iter.rs @@ -103,11 +103,6 @@ impl<'a> StackfulPreOrderHeapIter<'a> { None } - #[inline] - pub fn stack_is_empty(&self) -> bool { - self.stack.is_empty() - } - #[inline] pub fn focus(&self) -> usize { self.h @@ -165,14 +160,10 @@ impl<'a> StackfulPreOrderHeapIter<'a> { } (HeapCellValueTag::Lis, vh) => { self.push_if_unmarked(vh); + self.push_if_unmarked(vh + 1); - self.stack.push(IterStackLoc::iterable_heap_loc(vh + 1)); - - if self.heap[vh + 1].get_mark_bit() { - self.heap[vh + 1].set_forwarding_bit(true); - } else { - forward_if_referent_marked(&mut self.heap, vh + 1); - } + self.stack.push(IterStackLoc::mark_heap_loc(vh + 1)); + forward_if_referent_marked(&mut self.heap, vh + 1); self.stack.push(IterStackLoc::mark_heap_loc(vh)); forward_if_referent_marked(&mut self.heap, vh); @@ -193,19 +184,23 @@ impl<'a> StackfulPreOrderHeapIter<'a> { (HeapCellValueTag::PStr) => { self.push_if_unmarked(h); - forward_if_referent_marked(&mut self.heap, h+1); self.stack.push(IterStackLoc::iterable_heap_loc(h+1)); + forward_if_referent_marked(&mut self.heap, h+1); return Some(self.heap[h]); } (HeapCellValueTag::Atom, (_name, arity)) => { if arity > 0 { self.push_if_unmarked(h); + + for h in h + 1 .. h + arity + 1 { + self.push_if_unmarked(h); + } } for h in (h + 1 .. h + arity + 1).rev() { + self.stack.push(IterStackLoc::mark_heap_loc(h)); forward_if_referent_marked(&mut self.heap, h); - self.stack.push(IterStackLoc::iterable_heap_loc(h)); } return Some(self.heap[h]); @@ -1716,7 +1711,9 @@ mod tests { ); let mut link_back = list_loc_as_cell!(1); + link_back.set_forwarding_bit(true); + link_back.set_mark_bit(true); assert_eq!(iter.next().unwrap(), link_back); @@ -1738,7 +1735,9 @@ mod tests { ); let mut cyclic_link = list_loc_as_cell!(1); + cyclic_link.set_forwarding_bit(true); + cyclic_link.set_mark_bit(true); assert_eq!(iter.next().unwrap(), list_loc_as_cell!(1)); assert_eq!( @@ -1808,7 +1807,7 @@ mod tests { ); assert_eq!( - iter.next().unwrap(), + unmark_cell_bits!(iter.next().unwrap()), atom_as_cell!(atom!("y")) ); @@ -2204,7 +2203,9 @@ mod tests { ); let mut link_back = list_loc_as_cell!(1); + link_back.set_forwarding_bit(true); + link_back.set_mark_bit(true); assert_eq!(iter.next().unwrap(), link_back); diff --git a/src/heap_print.rs b/src/heap_print.rs index 585d8c13..4592e50d 100644 --- a/src/heap_print.rs +++ b/src/heap_print.rs @@ -689,8 +689,7 @@ impl<'a, Outputter: HCValueOutputter> HCPrinter<'a, Outputter> { let op = DirectedOp::Left(name, spec); - self.state_stack - .push(TokenOrRedirect::CompositeRedirect(max_depth, op)); + self.state_stack.push(TokenOrRedirect::CompositeRedirect(max_depth, op)); self.state_stack.push(TokenOrRedirect::Space); self.state_stack.push(TokenOrRedirect::Atom(name)); } @@ -1552,51 +1551,47 @@ impl<'a, Outputter: HCValueOutputter> HCPrinter<'a, Outputter> { } pub fn print(mut self) -> Outputter { - loop { - if let Some(loc_data) = self.state_stack.pop() { - match loc_data { - TokenOrRedirect::Atom(atom) => self.print_atom(atom), - TokenOrRedirect::BarAsOp => append_str!(self, " | "), - TokenOrRedirect::Char(c) => print_char!(self, self.quoted, c), - TokenOrRedirect::Op(atom, _) => self.print_op(atom.as_str()), - TokenOrRedirect::NumberedVar(num_var) => append_str!(self, &num_var), - TokenOrRedirect::CompositeRedirect(max_depth, op) => { - self.handle_heap_term(Some(op), false, max_depth) - } - TokenOrRedirect::FunctorRedirect(max_depth) => { - self.handle_heap_term(None, true, max_depth) - } - TokenOrRedirect::Close => push_char!(self, ')'), - TokenOrRedirect::IpAddr(ip) => self.print_ip_addr(ip), - TokenOrRedirect::RawPtr(ptr) => self.print_raw_ptr(ptr), - TokenOrRedirect::Open => push_char!(self, '('), - TokenOrRedirect::OpenList(delimit) => { - if !self.at_cdr(",") { - push_char!(self, '['); - } else { - let (_, max_depth) = delimit.get(); - delimit.set((false, max_depth)); - } - } - TokenOrRedirect::CloseList(delimit) => { - if delimit.get().0 { - push_char!(self, ']'); - } + let spec = self.toplevel_spec.take(); + self.handle_heap_term(spec, false, self.max_depth); + + while let Some(loc_data) = self.state_stack.pop() { + match loc_data { + TokenOrRedirect::Atom(atom) => self.print_atom(atom), + TokenOrRedirect::BarAsOp => append_str!(self, " | "), + TokenOrRedirect::Char(c) => print_char!(self, self.quoted, c), + TokenOrRedirect::Op(atom, _) => self.print_op(atom.as_str()), + TokenOrRedirect::NumberedVar(num_var) => append_str!(self, &num_var), + TokenOrRedirect::CompositeRedirect(max_depth, op) => { + self.handle_heap_term(Some(op), false, max_depth) + } + TokenOrRedirect::FunctorRedirect(max_depth) => { + self.handle_heap_term(None, true, max_depth) + } + TokenOrRedirect::Close => push_char!(self, ')'), + TokenOrRedirect::IpAddr(ip) => self.print_ip_addr(ip), + TokenOrRedirect::RawPtr(ptr) => self.print_raw_ptr(ptr), + TokenOrRedirect::Open => push_char!(self, '('), + TokenOrRedirect::OpenList(delimit) => { + if !self.at_cdr(",") { + push_char!(self, '['); + } else { + let (_, max_depth) = delimit.get(); + delimit.set((false, max_depth)); } - TokenOrRedirect::HeadTailSeparator => append_str!(self, "|"), - TokenOrRedirect::NumberFocus(max_depth, n, op) => { - self.print_number(max_depth, n, &op); + } + TokenOrRedirect::CloseList(delimit) => { + if delimit.get().0 { + push_char!(self, ']'); } - TokenOrRedirect::Comma => append_str!(self, ","), - TokenOrRedirect::Space => push_char!(self, ' '), - TokenOrRedirect::LeftCurly => push_char!(self, '{'), - TokenOrRedirect::RightCurly => push_char!(self, '}'), } - } else if !self.iter.stack_is_empty() { - let spec = self.toplevel_spec.take(); - self.handle_heap_term(spec, false, self.max_depth); - } else { - break; + TokenOrRedirect::HeadTailSeparator => append_str!(self, "|"), + TokenOrRedirect::NumberFocus(max_depth, n, op) => { + self.print_number(max_depth, n, &op); + } + TokenOrRedirect::Comma => append_str!(self, ","), + TokenOrRedirect::Space => push_char!(self, ' '), + TokenOrRedirect::LeftCurly => push_char!(self, '{'), + TokenOrRedirect::RightCurly => push_char!(self, '}'), } } -- 2.54.0