Stack overflow at runtime when using Rc<RefCell<T>> in cycle detection algorithm

[Ayanekoji]

I tried this code:

use std::{cell::RefCell, rc::Rc};

#[derive(Debug)]
struct CycleNode {
    pos: i32,
    next: Option<Rc<RefCell<CycleNode>>>,
}

impl CycleNode {
    fn new(pos: i32) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(CycleNode { pos, next: None }))
    }
}

pub fn detect_cycle(head: Option<Rc<RefCell<CycleNode>>>) -> Option<Rc<RefCell<CycleNode>>> {
        if head.is_none() {
            return None;
        }

        let mut fast = head.clone();
        let mut slow = head.clone();

        while let (Some(fast_node), Some(slow_node)) = (fast, slow) {
            if fast_node.borrow().next.is_none()
                || fast_node
                    .borrow()
                    .next
                    .as_ref()
                    .unwrap()
                    .borrow()
                    .next
                    .is_none()
            {
                return None;
            }

            fast = fast_node
                .borrow()
                .next
                .as_ref()
                .unwrap()
                .borrow()
                .next
                .clone();
            slow = slow_node.borrow().next.clone();

            if let (Some(f), Some(s)) = (&fast, &slow) {
                if Rc::ptr_eq(f, s) {
                    let mut entry = head.clone();

                    while let (Some(entry_node), Some(fast_node)) = (&entry.clone(), &fast.clone())
                    {
                        if Rc::ptr_eq(entry_node, fast_node) {
                            return entry;
                        }

                        entry = entry_node.borrow().next.clone();
                        fast = fast_node.borrow().next.clone();
                    }
                }
            }
        }

        None
    }
     
fn main() {
   let nodes: Vec<Rc<RefCell<CycleNode>>> = (0..5)
        .map(|pos| CycleNode::new(rand::thread_rng().gen_range(1..10), pos))
        .collect();
    for i in 0..nodes.len() - 1 {
        nodes[i].borrow_mut().next = Some(nodes[i + 1].clone());
    }
    nodes[4].borrow_mut().next = Some(nodes[2].clone());
    let head = Some(nodes[0].clone());
    let result = Solution::detect_cycle(head);
    assert_eq!(result,Some(nodes[2].clone()));
print!("success");
}

I expected to see this happen: success

Instead, this happened:

wind@Unreal:~/Learning_Projects/Rust/leetcode$ cargo build
   Compiling leetcode v0.1.0 (/home/wind/Learning_Projects/Rust/leetcode)
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.59s
wind@Unreal:~/Learning_Projects/Rust/leetcode$ cargo run
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.03s
     Running `/home/wind/Learning_Projects/Rust/target/debug/leetcode`

thread 'main' has overflowed its stack
fatal runtime error: stack overflow

Meta

rustc --version --verbose:

<version> wind@Unreal:~/Learning_Projects/Rust/leetcode$ rustc --version
rustc 1.82.0 (f6e511eec 2024-10-15)

Backtrace

<backtrace>

[ShE3py]

Removing the assert_eq!(result, Some(nodes[2].clone())); solves the stack overflow; I guess the impl PartialEq for CycleNode loops infinitely ?

#93555 0x00005555555607c6 in RefCell<CycleNode>::eq (self=0x5555555f8c70, other=0x5555555f8c70)
// 2nd cycle ↑
#93556 0x000055555555fbaf in Rc<RefCell<CycleNode>>::eq (self=0x5555555f8cd8, other=0x5555555f8cd8)
#93557 0x000055555555fb63 in Rc<RefCell<CycleNode>>::eq (self=0x5555555f8cd8, other=0x5555555f8cd8)
#93558 0x0000555555564573 in Option<Rc<RefCell<CycleNode>>>::eq (self=0x5555555f8cd8, other=0x5555555f8cd8)
#93559 0x000055555555f864 in CycleNode::eq (self=0x5555555f8cd8, other=0x5555555f8cd8)
#93560 0x00005555555607c6 in RefCell<CycleNode>::eq (self=0x5555555f8cd0, other=0x5555555f8cd0)
#93561 0x000055555555fbaf in Rc<RefCell<CycleNode>>::eq (self=0x5555555f8ca8, other=0x5555555f8ca8)
#93562 0x000055555555fb63 in Rc<RefCell<CycleNode>>::eq (self=0x5555555f8ca8, other=0x5555555f8ca8)
#93563 0x0000555555564573 in Option<Rc<RefCell<CycleNode>>>::eq (self=0x5555555f8ca8, other=0x5555555f8ca8)
#93564 0x000055555555f864 in CycleNode::eq (self=0x5555555f8ca8, other=0x5555555f8ca8)
#93565 0x00005555555607c6 in RefCell<CycleNode>::eq (self=0x5555555f8ca0, other=0x5555555f8ca0)
#93566 0x000055555555fbaf in Rc<RefCell<CycleNode>>::eq (self=0x5555555f8c78, other=0x5555555f8c78)
#93567 0x000055555555fb63 in Rc<RefCell<CycleNode>>::eq (self=0x5555555f8c78, other=0x5555555f8c78)
#93568 0x0000555555564573 in Option<Rc<RefCell<CycleNode>>>::eq (self=0x5555555f8c78, other=0x5555555f8c78)
#93569 0x000055555555f864 in CycleNode::eq (self=0x5555555f8c78, other=0x5555555f8c78)
#93570 0x00005555555607c6 in RefCell<CycleNode>::eq (self=0x5555555f8c70, other=0x5555555f8c70)
// 1st cycle ↑
#93571 0x000055555555fbaf in Rc<RefCell<CycleNode>>::eq (self=0x7fffffffe040, other=0x7fffffffe048)
#93572 0x000055555555fb63 in Rc<RefCell<CycleNode>>::eq (self=0x7fffffffe040, other=0x7fffffffe048)
#93573 0x0000555555564573 in Option<Rc<RefCell<CycleNode>>>::eq (self=0x7fffffffe040, other=0x7fffffffe048)
#93574 0x000055555555f4ae in issue_132263::main ()

As self == other, you may want to do something like this:

impl PartialEq for CycleNode {
    fn eq(&self, other: &CycleNode) -> bool {
        (match (&self.next, &other.next) {
            (Some(x), Some(y)) => Rc::ptr_eq(x, y),
            (None, None) => true,
            _ => false,
        }) && self.pos == other.pos
    }
}

@rustbot label -C-bug -needs-triage

[Ayanekoji]

Removing the assert_eq!(result, Some(nodes[2].clone())); solves the stack overflow; I guess the impl PartialEq for CycleNode loops infinitely ?

#93555 0x00005555555607c6 in RefCell::eq (self=0x5555555f8c70, other=0x5555555f8c70)
// 2nd cycle ↑
#93556 0x000055555555fbaf in Rc<RefCell>::eq (self=0x5555555f8cd8, other=0x5555555f8cd8)
#93557 0x000055555555fb63 in Rc<RefCell>::eq (self=0x5555555f8cd8, other=0x5555555f8cd8)
#93558 0x0000555555564573 in Option<Rc<RefCell>>::eq (self=0x5555555f8cd8, other=0x5555555f8cd8)
#93559 0x000055555555f864 in CycleNode::eq (self=0x5555555f8cd8, other=0x5555555f8cd8)
#93560 0x00005555555607c6 in RefCell::eq (self=0x5555555f8cd0, other=0x5555555f8cd0)
#93561 0x000055555555fbaf in Rc<RefCell>::eq (self=0x5555555f8ca8, other=0x5555555f8ca8)
#93562 0x000055555555fb63 in Rc<RefCell>::eq (self=0x5555555f8ca8, other=0x5555555f8ca8)
#93563 0x0000555555564573 in Option<Rc<RefCell>>::eq (self=0x5555555f8ca8, other=0x5555555f8ca8)
#93564 0x000055555555f864 in CycleNode::eq (self=0x5555555f8ca8, other=0x5555555f8ca8)
#93565 0x00005555555607c6 in RefCell::eq (self=0x5555555f8ca0, other=0x5555555f8ca0)
#93566 0x000055555555fbaf in Rc<RefCell>::eq (self=0x5555555f8c78, other=0x5555555f8c78)
#93567 0x000055555555fb63 in Rc<RefCell>::eq (self=0x5555555f8c78, other=0x5555555f8c78)
#93568 0x0000555555564573 in Option<Rc<RefCell>>::eq (self=0x5555555f8c78, other=0x5555555f8c78)
#93569 0x000055555555f864 in CycleNode::eq (self=0x5555555f8c78, other=0x5555555f8c78)
#93570 0x00005555555607c6 in RefCell::eq (self=0x5555555f8c70, other=0x5555555f8c70)
// 1st cycle ↑
#93571 0x000055555555fbaf in Rc<RefCell>::eq (self=0x7fffffffe040, other=0x7fffffffe048)
#93572 0x000055555555fb63 in Rc<RefCell>::eq (self=0x7fffffffe040, other=0x7fffffffe048)
#93573 0x0000555555564573 in Option<Rc<RefCell>>::eq (self=0x7fffffffe040, other=0x7fffffffe048)
#93574 0x000055555555f4ae in issue_132263::main ()
As self == other, you may want to do something like this:

impl PartialEq for CycleNode {
fn eq(&self, other: &CycleNode) -> bool {
(match (&self.next, &other.next) {
(Some(x), Some(y)) => Rc::ptr_eq(x, y),
(None, None) => true,
_ => false,
}) && self.pos == other.pos
}
}
@rustbot label -C-bug -needs-triage

that's very helpful and impressive, thanks!!!

[saethlin]

I don't see any indication of a double free, or any other kind of bug in Rust or rustc here so I'm going to close this.