In attempting to do a leetcode problem I tried a less optimal but interesting approach where I made the infected node the root of the tree and just checked the height. It failed with runtime error. I downloaded the test case from leetcode and it is a 1.1mb input. Running locally I was able to find out that I found out I was getting fatal runtime error: stack overflow. After converting my code to be iterative instead of recursive I was still getting a stack overflow. Turns out it was at the end of the function when drop was automatically called. Once I leaked the memory it would run but took over 240 seconds. I tried not cloning the large arrays of parent vecs but used a linked list and unsurprisingly that is also a problem. Still working on it as I haven’t quite figured out how to solve that problem. Doesn’t appear to be able to be solved using forget or more likely I need to track down where the drop is happening.

In the process of all that I produced a MRE that works as a test.

#[test]
fn drop_stack_overflow() {
    struct Node {
        next: Option<Box<Node>>,
    }
    let mut linked_list: Option<Box<Node>> = None;
    for _ in 0..21_767 {
        let node = Node { next: linked_list };
        linked_list = Some(Box::new(node));
    }
    dbg!(linked_list.as_ref().unwrap().next.is_some());
    // std::mem::forget(linked_list);
}

Reducing to 21_766 or uncommenting the last line cause it not to crash anymore on my machine. I tried similar code as a binary and realized I was getting non deterministic behaviour. With the number of iterations set to 87_252 I was getting about 20% failure rate. Meaning it would usually crash 2 out of 10 runs. The non-determinism is likely due to one of two things

1. What is mentioned in the post and the OS is changing the “allowed” size.
2. Or in preparing to test that idea discovered in the docs for Function std::mem::size_of

   In general, the size of a type is not stable across compilations, but specific types such as primitives are.

Based on testing on main it is the first option as each run appears to have a slight different amount of stack available. Tested using stacker::remaining_stack().

I further found that running the tests in release mode cargo test -r -- --nocapture drop_stack_overflow increase the number before crashing to 65_320 on my machine. On rust playground it seems to be at 21_768. The machine specific size is likely explained by what is in the post.

Function stacker::remaining_stack

Queries the amount of remaining stack as interpreted by this library.

Function stacker::maybe_grow

Grows the call stack if necessary. This function is intended to be called at manually instrumented points in a program where recursion is known to happen quite a bit. This function will check to see if we’re within red_zone bytes of the end of the stack, and if so it will allocate a new stack of at least stack_size bytes. The closure f is guaranteed to run on a stack with at least red_zone bytes, and it will be run on the current stack if there’s space available.