How to prevent stack overflow when dropping deep structures?

help
1

Hi,

I'm porting tests of custom JSON parser from another language to Rust. The original library contains test with 10 million nested JSON arrays. I can parse it in Rust easily. But unfortunately the problem happens when it goes out of scope and it should be dropped. Instead of dropping, my program runs out of stack space.

I also tried using serde_json representation and it's the same:

fn main() {
    let mut json = serde_json::Value::Bool(true);
    for i in 0..10_000_000 {
        json = serde_json::Value::Array(vec![json]);
    }
    println!("Created");
    drop(json);
    println!("Destroyed");  // This line isn't reached.
}

Is there some solution to it without increasing a stack space? Thanks

2

You can write your own helper function that drops using the heap as temporary storage. Something like this

pub fn drop_with_heap(mut value: Value) {
    let mut vecs = vec![];
    let mut maps = vec![];
    'main: loop {
        match value {
            Value::Object(map) => maps.push(map.into_values()),
            Value::Array(vec) => vecs.push(vec),
            _ = (),
        }
        while let Some(map) = maps.pop() {
            if let Some(val) = map.next() {
                value = val;
                maps.push(map);
                continue 'main
            }
        }
        while let Some(v) = vecs.pop() {
            if let Some(val) = v.pop() {
                value = val;
                vecs.push(v);
                continue 'main
            }
        }
        break
    }
}

Edit: Added missing push

3

that can be simplified, how about:

fn custom_stack(value: Value) {
    let mut stack = vec![value];
    
    while let Some(value) = stack.pop() {
        match value {
            Value::Array(values) => stack.extend(values),
            Value::Object(maps) => stack.extend(maps.into_iter().map(|(_, value)| value)),
            _ => {}
        }
    }
}
4

I'd also recommend a wrapper struct for automatically calling the custom drop code: Rust Playground

5

I tried to reduce the heap usage. For my solution the heap usage is limited by the depth. For yours the object/array size is relevant.

6

I tried to find a counter example where your code stack overflows, with a Array of Arrays where the second Array is large it should be dropped and cause a stack overflow, instead it caused a sigkill (or maybe it's also a stack overflow being reported in a weird way): Rust Playground

i tried to rewrite your solution with less-mind-bending control flow and that worked as expected: Rust Playground

fn custom_stack(value: Value) {
    let mut arrays = Vec::new();
    let mut maps = Vec::new();
    
    match value {
        Value::Array(array) => arrays.push(array),
        Value::Object(map) => maps.push(map),
        _ => {}
    }
    
    while !arrays.is_empty() || !maps.is_empty() {
        for value in arrays.pop()
            .into_iter()
            .flatten()
            .chain(maps.pop()
                .into_iter()
                .flatten()
                .map(|(_, val)| val)
            )
        {
            match value {
                Value::Array(array) => arrays.push(array),
                Value::Object(map) => maps.push(map),
                _ => {}
            }
        }
    }
}
7

For my solution the heap usage is limited by the depth

your solution, if it didn't sigkill in more complex cases, would avoid 1 layer of needlessly moving val's, if i give it a array of size 1M (with no depth) it will spend some time dropping all those elements, size is still relevent.

8

Yes, turn on the parsing features that limit recursion depth during parsing and stop having json that looks like this.

There's a reason the JsonReaderOptions.MaxDepth Property (System.Text.Json) | Microsoft Learn defaults to 64, for example. Nobody needs 10-million depth json.

9

I wonder how the specific value 64 was arrived at. It's both too small to be related to any particular resource limitation, and not quite big enough that it would be completely crazy to hit in real data (eg a JSON serialization of an expression AST could hit that for realistic code)

I'd expect something closer to 1000, for comparison.

10

Nobody needs 10-million depth json.

Honestly there's probably some company with absolutely insane "enterprise" software that actually serializes and deserializes 10 million levels of nested json.

11

If you try to serialize coding trees(like an AST), this is quite realistic, especially if you're thinking about something like dumping a big functional IR.

12

I wonder if rust types can reach 10 million levels of nesting before the compiler explodes.

13

This made me remember this topic : Virtual machine in Rust type system

14

My bet is that it's a pretty arbitrary choice, probably chosen for what's common in web request scenarios -- where even 64 is pretty high -- and with, in a way, being a bit too low being better because it's more likely that you'll hit it and find out that you need to raise it (versus being too high and never finding out that you need to lower it).

If it was a hard limit then I agree it needs to be the "10x anything that might be reasonable", but it's a configurable limit.

15

someone also made chess in the type system: GitHub - Dragon-Hatcher/type-system-chess: Chess implemented entirely in the Rust and TS type systems. · GitHub

16

Yeah, makes sense - the main risk is you not hitting it but your users doing so. Perhaps, in that sense, it's too high!