From 307cb56ef5fccac7a50c331a09f9a99e5c6eb2d0 Mon Sep 17 00:00:00 2001
From: Mark <markjordanthom@gmail.com>
Date: Sat, 14 Oct 2023 13:00:58 -0600
Subject: [PATCH] fix bugs & incompleteness of cycle-detecting stackless
 iterator (#2111)

---
 src/machine/gc.rs | 20 ++++++++++++++++----
 1 file changed, 16 insertions(+), 4 deletions(-)

diff --git a/src/machine/gc.rs b/src/machine/gc.rs
index 5b1ccca3..a0a802db 100644
--- a/src/machine/gc.rs
+++ b/src/machine/gc.rs
@@ -17,6 +17,7 @@ pub(crate) trait UnmarkPolicy {
     ) -> bool where Self: Sized {
         iter.backward()
     }
+    fn detect_list_tail_cycle(_iter: &mut StacklessPreOrderHeapIter<Self>) where Self: Sized {}
 }
 
 pub(crate) struct IteratorUMP {
@@ -87,12 +88,18 @@ impl UnmarkPolicy for CycleDetectorUMP {
     fn list_head_cycle_detecting_backward(
         iter: &mut StacklessPreOrderHeapIter<Self>,
     ) -> bool {
-        if !iter.iter_state.cycle_detected && iter.iter_state.mark_phase && iter.detect_list_cycle() {
-            iter.iter_state.cycle_detected = true;
+        if !iter.iter_state.cycle_detected && iter.iter_state.mark_phase {
+            iter.iter_state.cycle_detected = iter.detect_list_cycle();
         }
 
         iter.backward()
     }
+
+    fn detect_list_tail_cycle(iter: &mut StacklessPreOrderHeapIter<Self>) {
+        if iter.iter_state.mark_phase && !iter.iter_state.cycle_detected {
+            iter.iter_state.cycle_detected = iter.detect_list_cycle();
+        }
+    }
 }
 
 struct MarkerUMP {}
@@ -273,7 +280,7 @@ impl<'a, UMP: UnmarkPolicy> StacklessPreOrderHeapIter<'a, UMP> {
                         let current = self.current;
 
                         if let Some(cell) = UMP::forward_attr_var(self) {
-                            if current as u64 != next && self.heap[next as usize].is_ref() {
+                            if current as u64 != next && self.heap[next as usize].is_compound(self.heap) {
                                 self.iter_state.cycle_detected();
                             }
 
@@ -292,7 +299,7 @@ impl<'a, UMP: UnmarkPolicy> StacklessPreOrderHeapIter<'a, UMP> {
                         let current = self.current;
 
                         if let Some(cell) = self.forward_var() {
-                            if current as u64 != next && self.heap[next as usize].is_ref() {
+                            if current as u64 != next && self.heap[next as usize].is_compound(self.heap) {
                                 self.iter_state.cycle_detected();
                             }
 
@@ -347,6 +354,11 @@ impl<'a, UMP: UnmarkPolicy> StacklessPreOrderHeapIter<'a, UMP> {
                             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_tail_cycle(self);
+                                }
+
                                 self.backward();
 
                                 if UMP::list_head_cycle_detecting_backward(self) {
-- 
2.54.0