0

I am aware what this error means, I just don't have any idea how to solve this puzzle. As a short background - I need a tree structure in my app, I've discovered Rust doesn't play well with circular references, hence I am trying to implement a tree-like data structure myself (but the borrow checker doesn't let me do that either):

playground

struct Node {
    children: Vec<i32>,
}

let mut hm = HashMap::new();

hm.insert(1, Node { children: vec![] });
hm.insert(2, Node { children: vec![1] });

// Let's say I want to remove node 2...
let node = match hm.get(&2) {
    Some(node) => node,
    None => panic!(""),
};

// ...but first I want to remove its children:
for removable in &node.children {
    match hm.get(&removable) {
        Some(_) => hm.remove(&removable), // cannot borrow `hm` as mutable because it is also borrowed as immutable
        None => panic!("Oops, trying to remove data that's not there"),
    };
}

How to solve that?

Nurbol Alpysbayev
  • 19,522
  • 3
  • 54
  • 89
  • There're tons of questions about tree structures in Rust. Did you see them? – Boiethios Nov 21 '19 at 09:19
  • @FrenchBoiethios I googled a bit and I've seen some libraries for making trees. I didn't want to pull a new dependency and thought I'll make a very basic tree. Then I stumbled upon this error. I now have changed my mind and I am going to use a library. However, I am still curious how this basic logic could be handled in Rust. Also, I didn't find a similar-to-mine question. – Nurbol Alpysbayev Nov 21 '19 at 09:21
  • I was talking about SO questions: does this answer your question? [How do I express mutually recursive data structures in safe Rust?](https://stackoverflow.com/questions/36167160/how-do-i-express-mutually-recursive-data-structures-in-safe-rust) especially the Shepmaster's answer. – Boiethios Nov 21 '19 at 09:23
  • how about using `hm.get_mut(&2)`? `node` is an immutable reference, but `.remove()` obviously requires the reference it was invoked on to be mutable. Also, why remove the children explicitly in your example? They'll go out of scope with the removal of node 2 anyways – Sty Nov 21 '19 at 09:26
  • @FrenchBoiethios Thanks so much for useful links! I am going to read them through. – Nurbol Alpysbayev Nov 21 '19 at 09:29
  • @Sty no that doesn't help, unfortunately. Also, `remove()` already has the immutable reference `hm`. `remove` is on `hm`, not on `node`, you are probably confused on that. And... how are children going to go out of scope with the removal of node 2? That even doesn't make sense to me, sorry. – Nurbol Alpysbayev Nov 21 '19 at 09:34
  • @NurbolAlpysbayev oh, indeed I parsed that wrong and did not realise that the the entries in the children structs were supposed to be references to other nodes. Have you ever read about [pointers in Rust](https://doc.rust-lang.org/book/ch15-00-smart-pointers.html), though? Trees should be recursive data structures and certainly don't benefit from this kind of indirection, so I'd recommend using `Rc` or something for an actual tree structure – Sty Nov 21 '19 at 09:47
  • @Sty Thanks for that advice. I believe `Rc` can't be a solution here, because I'd still need to make mutable reference to the main hashmap at the same time with immutable one. I think I'll go with a crate (I thought it would be easier to implement a basic tree myself, but I was wrong). – Nurbol Alpysbayev Nov 21 '19 at 09:52
  • 1
    I notice the problem [goes away if you remove the parent first](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=0745a2982784cfb6a53aa6911e6c2bb9). Failing that, you can still [extract the children vec using `mem::replace`](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=c021e19b111385a099ce6564dada81e1). – trent Nov 21 '19 at 09:52
  • @trentcl Wow! Interesting! Finally someone with the actual solution :D Why on earth I didn't think about that myself (I know why, I have been working for 14 hours already). And that `mem::replace` usage, great! Thank you so much! – Nurbol Alpysbayev Nov 21 '19 at 09:56
  • 1
    Glad to help! Another quick tip: A `match` that panics on `None` can usually be concisely replaced by a call to `.unwrap()` or `.expect("your error message here")`. – trent Nov 21 '19 at 09:59
  • @trentcl Yep, just noticed and admired that :) However, in my actual app I don't panic so I can't use that unfortunately. – Nurbol Alpysbayev Nov 21 '19 at 10:02

0 Answers0