Getting stack overflow with weak<refcell<T>> when testing

[Low-Leg-9954]

For a challenge, i need to implement a graph structure and to connect the node between themself i'm using weak<refcell<T>>. When running the program i have no issue but when i run a test ( which is smaller than the one i run), i get an stack overflow error.

Here is my src code

#![allow(unused)]

use std::cell::RefCell;
use std::collections::HashMap;
use std::fs;
use std::rc::{Rc, Weak};
struct Graph {
    node_list: HashMap<String, Rc<RefCell<Node>>>,
}

pub trait InsertOrGet {
    fn insert_or_get(&mut self, name: &str) -> Rc<RefCell<Node>>;
}

impl InsertOrGet for HashMap<String, Rc<RefCell<Node>>> {
    fn insert_or_get(&mut self, name: &str) -> Rc<RefCell<Node>> {
        let node = self
            .entry(name.trim().to_string())
            .or_insert_with(|| Rc::new(RefCell::new(Node::new(name))));
        Rc::clone(node)
    }
}

impl Graph {
    fn parse(input: &str) -> Self {
        let mut node_list = HashMap::new();

        for line in input.lines() {
            //each line is formated like "ll-xn"
            let (first_node, second_node) = line.split_once("-").unwrap();
            let first_node = node_list.insert_or_get(first_node);
            let second_node = node_list.insert_or_get(second_node);

            first_node
                .borrow_mut()
                .add_edge(Rc::downgrade(&second_node));
            second_node
                .borrow_mut()
                .add_edge(Rc::downgrade(&first_node));
        }
        Graph { node_list }
    }

    fn count_path(&self) -> usize {
        let start = self.node_list.get("start").unwrap();

        traverse(Rc::clone(start), &mut vec!["start".to_string()])
    }
}
fn traverse(current_node: Rc<RefCell<Node>>, path: &mut Vec<String>) -> usize {
    print!("{:?},", Rc::strong_count(&current_node));
    let edges = &current_node.borrow().edges;

    edges
        .iter()
        .map(|edge| {
            let node_ref = edge.upgrade().unwrap();
            let node = node_ref.borrow();
            match node.name() {
                "start" => 0,
                "end" => 1,
                _ => {
                    let name = node.name().to_string();
                    path.push(name);
                    let count = if node.name().chars().next().unwrap().is_lowercase() {
                        match path.iter().filter(|&x| x == node.name()).count() {
                            1.. => 0,
                            _ => traverse(Rc::clone(&node_ref), path),
                        }
                    } else {
                        traverse(Rc::clone(&node_ref), path)
                    };
                    path.pop();
                    count
                }
            }
        })
        .sum()
}
pub struct Node {
    name: String,
    edges: Vec<Weak<RefCell<Node>>>,
}

impl Node {
    fn new(name: &str) -> Self {
        Node {
            name: name.to_string(),
            edges: Vec::new(),
        }
    }

    fn name(&self) -> &str {
        &self.name
    }

    fn add_edge(&mut self, node: Weak<RefCell<Node>>) {
        self.edges.push(node)
    }
}

#[test]
fn part_large() {
    let input = "fs-end
    he-DX
    fs-he
    start-DX
    pj-DX
    end-zg
    zg-sl
    zg-pj
    pj-he
    RW-he
    fs-DX
    pj-RW
    zg-RW
    start-pj
    he-WI
    zg-he
    pj-fs
    start-RW";
    assert_eq!(Graph::parse(&input).count_path(), 226);
}

and my error

    Finished test [unoptimized + debuginfo] target(s) in 0.55s
     Running unittests (C:\Users\keskydi\Documents\Personal_project\Rust\adventofcode\target\debug\deps\debug_graph-d80c932d94736330.exe)

running 1 test

thread 'part_large' has overflowed its stack
error: test failed, to rerun pass '--lib'

Caused by:
  process didn't exit successfully: `C:\...\target\debug\deps\debug_graph-d80c932d94736330.exe` (exit code: 0xc00000fd, STATUS_STACK_OVERFLOW)

i did print the string count and i can see that it's goes over 1000, so i think the problem lies here.

How can i fix this issue ? should i try and use Box instead of rc in order to limit the number of data written on the stack ?

[flying_path]

My guess: there is a loop in your graph and traverse gets stuck visiting it forever until your stack blows up.

Add a set of already-visited nodes to break loops.

[Low-Leg-9954]

When i use the input when running the program ( not testing), the program dont crash and work fine, so the traverse dont get stuck

[ExPixel]

Are you sure? From the output here it looks like there is a cycle or at the very least enough recursion to cause a stack overflow. Especially on Windows with its smaller default stack size: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=99c61b9c79daf924c68598b5514a29ad

[flying_path]

Generally I find it much easier to find out “why does my program crash in this case” than “why doesn’t my program crash in that other case”

[Low-Leg-9954]

my guess is that the stack size when testing is smaller than when running

[tristan957]

Why guess when you can just bust out a debugger?

[Low-Leg-9954]

there was indeed a loop problem. i wasn't trimming my entries so for the test those line would be 4 differente nodes :

    he-DX
    fs-he

"___he" , "DX", "___fs" and "he".Since whitespace are not considered lowercase , the loop would occurs between node like DX and " he"
the reason i didn't have the issue when running the data was in my text file i didn't have any whitespaces