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?
Actually, borrowing any number of siblings simultaneously is be completely fine (if it wasn't, then the values_mut() function could not exist at all). The problem is putting parents and children in the same stack. Putting them in the stack implies they all have the same lifetime — they are all borrowed for the same time — but it’s not possible to &mut, exclusively, borrow any parent and child together, because the existence of an &mut to the parent means that any &mut to any child is no longer exclusive.
No, there are an equal number of mutable borrows involved. But the lack of a shared Vec means they aren't forced to have the same lifetime. Each recursive call to demo_works() works with a lifetime shorter than that of its caller.
More efficient than recursive is a pretty tall order without breaking out unsafe.
If you're willing to move away from the current Value type you have more options:
Depending on your use-case, parsing to a flat Vec of values that link via indices would let you extremely efficiently traverse with only a standard loop, but it's not completely trivial to build and you have to do more work to recover a path to the current value during traversal. This means more work for other operations and bounds checking to access values but due to the compact storage this is normally far more performant than a tree.
A more out there approach is to instead implement Deserialize manually and directly parse from the JSON source into your traversal logic, since you get effectively "object start, property... object end" and the like events that way.
actually, for this algorithm, parents and children are not in the same stack simultaneously, because the parent is popped off the stack before the children are pushed onto it.
given map: &'a mut HashMap<_, Value>, map.values_mut() will yield &'a mut Value, so the lifetime actually checks out. in this case, I'd like to think the signature of HashMap::values_mut() like this: exclusive references are move-only types (forget about reborrow).
in fact, rust has no problem to iteratively traverse a tree structure. my understanding of the problem is that the assignment is inside a nested branch, which messed up the control flow analysis. I feel it a bit like nll case #3, but it turns out not quite, as I tried -Z polonius without success.
for this particular example, if we change the inner match into a match guard using #![feature(if_let_guard)][1], and hoist the inner None clause into a clause on the outer match, we can actually make it compile:
while let Some(node) = stack.pop() {
match node {
Value::Object(map) if map.contains_key("specific-key") => {
if let Some(v) = get_value(map.get("specific_key").unwrap()) {
*node = v;
}
}
Value::Object(map) => {
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,
}
}
it's possible to make it work without if_let_guard, just use contains_key() for the match guard, but a redundent hash lookup and .unwrap() is needed, which I'm not sure would be optimized well. ↩︎
map.values_mut() can't give you &'a mut Value, because the &'a mut HashMap reference to map is non-copyable. It can't exist in more that one place, so it's impossible to give it to the call without removing it from the caller. The reference would have to be irreversibly consumed by the values_mut() call to keep the exact same lifetime.
Instead, calling map.values_mut() automatically reborrows&'a mut HashMap as &'tmp mut HashMap, and therefore you only get &'tmp Value that isn't as long-lived as 'a.
It's annoying because there's not an actual syntax for this, but those are actually different 'a lifetimes to what we normally mean when we talk about the 'a lifetime in an existing reference in, say, a variable.
When it's a shared reference the lifetime parameters in a function or type can be pretty early understood as simply being a narrowed copy of the original made by the function, but that doesn't work for exclusive references. There you have to get that the lifetime parameter is actually already the reborrowed lifetime implicitly made at the call site before it's passed in. That's how the calling function knows there's an existing use if you try to access the parent before the child borrow can be dropped by simply looking at the types involved.
In this example this means you essentially are asking Rust to store a vector of references to the first level, the second level, etc. of reborrows all as the same type, which means the borrow checker can't work. Effectively, it doesn't know how to prove that an individual reborrow is not accessed after it's children are created (to do that is probably dependant typing, where the type of one variable depends on the runtime value of another, which isn't really seen outside of theorem proving languages)