Warning

This post was published 32 days ago. The information described in this article may have changed.

Info

This post is auto-generated from RSS feed The Rust Programming Language Forum - Latest topics. Source: Why does this iterative JSON traversal fail borrow check while the recursive version works?

I was trying to traverse and possibly transform a JSON tree (serde_json::Value) without recursion, using an explicit stack. The recursive version works fine, but when I switch to an iterative approach, the borrow checker rejects it with E0506.

I suspect this is due to the lack of regioned borrows in Rust — but I’d like to confirm whether that’s the right way to understand it, and whether there’s a known safe pattern for this kind of traversal.

Minimal reproducer

fn demo_doesnt_work(json: &mut Value) {
    fn get_value(_v: &Value) -> Option<Value> {
        todo!()
    }

    let stack = &mut Vec::<&mut Value>::new();
    stack.push(json);
    while let Some(node) = stack.pop() {
        match node {
            Value::Object(map) => match map.get("specific-key") {
                Some(v) => {
                    if let Some(v) = get_value(v) {
                        *node = v;
                    }
                }
                None => {
                    for val in map.values_mut() {
                        // comment out this to shut up the borrow checker
                        stack.push(val); // this extends the lifetime of `map`
                    }
                }
            },
            _ => continue,
        }
    }
}

fn demo_works(json: &mut Value) {
    fn get_value(_v: &Value) -> Option<Value> {
        todo!()
    }

    match json {
        Value::Object(map) => match map.get("specific-key") {
            Some(v) => {
                if let Some(v) = get_value(v) {
                    *json = v;
                }
            }
            None => {
                for val in map.values_mut() {
                    demo_works(val);
                }
            }
        },
        _ => {}
    }
}

Error message

error[E0506]: cannot assign to `*node` because it is borrowed
  --> src/main.rs:15:25
   |
10 |     while let Some(node) = stack.pop() {
   |                            ----- borrow later used here
11 |         match node {
12 |             Value::Object(map) => match map.get("specific-key") {
   |                           --- `*node` is borrowed here
...
15 |                         *node = v;
   |                         ^^^^^ `*node` is assigned to here but it was already borrowed

My current understanding is that in the iterative version, pushing map.values_mut() into the stack keeps multiple live mutable references to siblings under the same parent Object. So when I later attempt to assign to *node, Rust sees that the parent’s borrow is still active (through other entries in the stack). In contrast, the recursive version only ever holds one mutable borrow at a time, so it passes the borrow checker.

Unsafe attempt

This Passes Miri, but I’m not certain this is fully safe: playground link.

Questions

• Is this indeed the correct way to understand E0506 here?
• Is there a known safe, efficient and natural pattern for iterative tree traversal that avoids recursion?

3 posts - 3 participants

Read full topic

🏷️ Rust_feed