I'm trying to implement the logic to take json like below as input
[{"key": "a", "children": [{"key": "a1", "children": [{"key": "a11", "children": []}]}]}, {"key": "b", "children": [{"key": "b1", "children": [{"key": "b11", "children": []}]}]}]
and the expected output is
{"a": {"a1": {"a11": ""}}, "b": {"b1": {"b11": ""}}}
my main function is listed as below
use serde_json::{json, Value};
use std::{collections::VecDeque};
fn convert_tree(lst: &Vec<serde_json::Value>) -> serde_json::Value {
let mut tree = serde_json::Map::new();
let mut queue = VecDeque::new();
queue.push_back((lst, &mut tree));
while let Some((entries, branch)) = queue.pop_front() {
for entry in entries {
let key = entry["key"].as_str().unwrap();
let children = entry["children"].as_array();
if let Some(children) = children {
let child_branch = serde_json::Map::new();
branch.insert(key.to_owned(), serde_json::Value::Object(child_branch));
let mut branch_ref = branch.get_mut(key).unwrap().as_object_mut().unwrap();
queue.push_back((children, &mut branch_ref));
} else {
branch.insert(key.to_owned(), serde_json::Value::String("".to_owned()));
}
}
}
serde_json::Value::Object(tree)
}
#[test]
fn test_convert_tree(){
let a_str = r#"[{"key": "a", "children": [{"key": "a1", "children": [{"key": "a11", "children": []}]}]}, {"key": "b", "children": [{"key": "b1", "children": [{"key": "b11", "children": []}]}]}]"#;
let v: Vec<serde_json::Value>= serde_json::from_str(a_str).unwrap();
println!("{:#?}", v);
let zed = convert_tree(&v);
}
cargo test --package flashlight --example test_serde_json2 -- test_convert_tree --exact --nocapture runs into error
error[E0499]: cannot borrow `*branch` as mutable more than once at a time
--> examples/test_serde_json2.rs:68:17
|
68 | branch.insert(key.to_owned(), serde_json::Value::Object(child_branch));
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ second mutable borrow occurs here
69 | let mut branch_ref = branch.get_mut(key).unwrap().as_object_mut().unwrap();
| ------------------- first mutable borrow occurs here
70 | queue.push_back((children, &mut branch_ref));
| -------------------------------------------- first borrow later used here
error[E0499]: cannot borrow `*branch` as mutable more than once at a time
--> examples/test_serde_json2.rs:69:38
|
62 | while let Some((entries, branch)) = queue.pop_front() {
| ----------------- first borrow used here, in later iteration of loop
...
69 | let mut branch_ref = branch.get_mut(key).unwrap().as_object_mut().unwrap();
| ^^^^^^^^^^^^^^^^^^^ `*branch` was mutably borrowed here in the previous iteration of the loop
error[E0597]: `branch_ref` does not live long enough
--> examples/test_serde_json2.rs:70:44
|
62 | while let Some((entries, branch)) = queue.pop_front() {
| ----------------- borrow later used here
...
70 | queue.push_back((children, &mut branch_ref));
| ^^^^^^^^^^^^^^^ borrowed value does not live long enough
71 | } else {
| - `branch_ref` dropped here while still borrowed
error[E0499]: cannot borrow `*branch` as mutable more than once at a time
--> examples/test_serde_json2.rs:72:17
|
62 | while let Some((entries, branch)) = queue.pop_front() {
| ----------------- first borrow later used here
...
69 | let mut branch_ref = branch.get_mut(key).unwrap().as_object_mut().unwrap();
| ------------------- first mutable borrow occurs here
...
72 | branch.insert(key.to_owned(), serde_json::Value::String("".to_owned()));
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ second mutable borrow occurs here
Some errors have detailed explanations: E0499, E0597.
For more information about an error, try `rustc --explain E0499`.
warning: `flashlight` (example "test_serde_json2" test) generated 1 warning
error: could not compile `flashlight` due to 4 previous errors; 1 warning emitted
The reason I use branch as mutable more than once at a time is because I have to fetch a mutable reference to what I just inserted in the Map, if I can do these two step once, then the problem would be gone.
I think my problem would be solved if serde_json::Map has a method similar to try_insert in std::collections::HashMap.
Even I make to combine the previously mentioned two steps together,
I just reaslize actually I was mutably borrowing branch in every iteration, does that also count as "more than once at a time"?
fn insert_and_get<'a>(map: &'a mut Map<String, Value>, key: String, value: Value) -> &'a mut Value {
map.entry(key).or_insert(value)
}
fn convert_tree(lst: &Vec<serde_json::Value>) -> serde_json::Value {
let mut tree = serde_json::Map::new();
let mut queue = VecDeque::new();
queue.push_back((lst, &mut tree));
while let Some((entries, branch)) = queue.pop_front() {
for entry in entries {
let key = entry["key"].as_str().unwrap();
let children = entry["children"].as_array();
if let Some(children) = children {
let child_branch = json!({});
let zed = insert_and_get(branch, key.to_owned(), child_branch).as_object_mut().unwrap();
queue.push_back((children, zed));
} else {
branch.insert(key.to_owned(), serde_json::Value::String("".to_owned()));
}
}
}
serde_json::Value::Object(tree)
}
Here is an iterative solution.
use serde_json::{Map, Value};
pub fn convert_tree(list: &[Value]) -> Option<Value> {
// Contains a tuple of:
// - the parent list as an iterator
// - the parent map
// - the key that the current map/iterator belongs to in the parent map
let mut stack: Vec<(std::slice::Iter<Value>, Map<String, Value>, String)> = vec![];
// Iterator of all the items that go into the current map
let mut current_iter = list.iter();
// Map containing all the items that we have consumed from the iterator
let mut current_map = Map::new();
// Loop until the stack is empty.
//
// Normally I'd do `while let Some(item) = stack.pop()`, but since we start with an item
// in-progress (known to be an array), the pop isn't the first thing in the loop, so `while`
// can't be used.
let final_map = loop {
// There are more items in the current iterator, so we must descend into the tree.
if let Some(next) = current_iter.next() {
// Validation
let obj = next.as_object()?;
let key = obj.get("key")?.as_str()?;
let children = obj.get("children")?.as_array()?;
// Push the current state onto the stack
stack.push((current_iter, current_map, key.to_owned()));
// Descend the tree
current_iter = children.iter();
current_map = Map::new();
// There are no more items in the current iterator, so we must insert this result to the
// current map.
} else if let Some((parent_iter, mut parent_map, key)) = stack.pop() {
// Insert the current map the parent map
if current_map.is_empty() {
// Transform any `{}` values into `""`
parent_map.insert(key, Value::String("".to_owned()));
} else {
// Maps with contents are inserted unchanged
parent_map.insert(key, Value::Object(current_map));
}
// Ascend the tree
current_iter = parent_iter;
current_map = parent_map;
// There are no more parents, so this is the fully-formed answer
} else {
break current_map;
}
};
Some(Value::Object(final_map))
}
I've changed &Vec<Value> to &[Value] for reasons explained here. I've also made the return Option<Value> as minimal error handling.
I've tried to make this as refactorable as possible in three areas. First, the validation.
// Validation
let obj = next.as_object()?;
let key = obj.get("key")?.as_str()?;
let children = obj.get("children")?.as_array()?;
This would not be needed if you make the function accept a stronger type. For example, you could use this:
#[derive(Deserialize)]
pub struct KeyAndChildren {
key: String,
children: Vec<KeyAndChildren>,
}
pub fn convert_tree(list: &[KeyAndChildren]) -> Value { ... }
With this, validation is moved to the caller, and your function no longer needs an error path.
Second, the special case for the empty string.
if current_map.is_empty() {
// Transform any `{}` values into `""`
parent_map.insert(key, Value::String("".to_owned()));
} else {
// Maps with contents are inserted unchanged
parent_map.insert(key, Value::Object(current_map));
}
If you can accept {} instead of "" for empty maps, this conditional is unnecessary and the second branch can always be used instead.
Third, whether to consume the list or not. If you don't need the list after calling convert_tree, you can avoid all the string allocations by consuming the list.
pub fn convert_tree(list: &[Value]) -> Option<Value>
pub fn convert_tree(list: Vec<Value>) -> Option<Value>
Inside the function, you will use into_iter instead of iter and match the Value variants to obtain their owned contents.
// Validation
let Value::Object(mut obj) = next else {
return None;
};
let Value::String(key) = obj.get_mut("key")?.take() else {
return None;
};
let Value::Array(children) = obj.get_mut("children")?.take() else {
return None;
};
Using owned values also allows you to do validation incrementally with a struct. Here I'm using Vec<Value> instead of Vec<KeyAndChildren> from above since I need to use children to create an iterator over Value.
#[derive(serde::Deserialize)]
struct KeyAndChildren {
key: String,
children: Vec<Value>,
}
let KeyAndChildren { key, children } = serde_json::from_value(next).ok()?;