Fix borrowing references in Node structure

UPD: fixed typos
I read books about rust, lifetimes, borrowing rules etc. And everything looked like an innovation in the world of programming. But then I started writing my own application and now the borrowing rules are stopping me.
Here is the MRE:

fn main() {
    // We take ownership of a database object
    // We need `mut` to change some values in the tree sometimes, like `name` or smth.
    let mut root = get_root();
    // Set this value that points to the current Tree Node
    let mut cursor = &mut root;

    // Go deeper into the tree and update the cursor value
    go(&mut cursor, 0);
    // Method on the immutable reference to show the conflict
    cursor.printy();
}

#[derive(Debug)]
// The node that owns their own sons
struct Node {
    name: String,
    list: Vec<Node>,
}

impl Node {
    // The random method that uses an immutable ref
    fn printy(&self) {
        println!("{:?}", self);
    }
}

// Take the mut reference to the mut reference to the Node
// Change outer ref to another mut Node
fn go<'a>(cursor: &'a mut &'a mut Node, number: usize) {
    *cursor = &mut cursor.list[number];
}

// Generate Mock-Node
fn get_root() -> Node {
    Node {
        name: format!("Name 1"),
        list: vec![
            Node {
                name: format!("Name 2"),
                list: vec![],
            },
            Node {
                name: format!("Name 3"),
                list: vec![],
            },
        ],
    }
}

What do I want to implement? I take ownership of root Node structure from the file (db). Then I create cursor var which helps me to move along Node structure and don't mess up root var in case I need to move to the root again. So as I understood right, cursor needs to be the type of &mut Node and when we pass it to the function which moves down in a tree, we need type &mut &mut Node to change reference to another part of tree (*cursor = &mut anotherPartOfTree). In my head everything should works fine, but I think I overthink it a little.
If you need additional comments on the code, let me know.

Forgot to say exactly what the problem is:

error[E0502]: cannot borrow `*cursor` as immutable because it is also borrowed as mutable
  --> src/main.rs:10:5
   |
8  |     go(&mut cursor, 0);
   |        ----------- mutable borrow occurs here
9  |     // Method on the immutable reference to show the conflict
10 |     cursor.printy();
   |     ^^^^^^^^^^^^^^^
   |     |
   |     immutable borrow occurs here
   |     mutable borrow later used here

I think I understand what the compiler says here but how to solve it? Is it possible?

&'a mut T<'a> is a well-recognized anti-pattern. (Here T = &'a mut Node.) It essentially makes the value borrowed for the entirety of its lifetime, making it basically useless.

So if the same lifetime doesn't work, would a longer or shorter lifetime in the inner borrow work? You can check, but the answer is no, neither works. Consequently, you can't write such a go() function as-is.

I tried to imitate the pattern using shared references and interior mutability, but ran in to the same kind of errors, which suggests to me that this would lead to aliased mutability, i.e. it's unsound. It is exceedingly rare to use this kind of "cursor" pattern in Rust; maybe you could use an explicit path represented by a vector of indices into each node instead.

1 Like

maybe you could use an explicit path represented by a vector of indices into each node instead.

I don't quite understand this sentence, what is "explicit path" and "vector of indices". Сan you explain it a little bit, please?

You get to a node by starting at the root, and choosing the i1-th child, then chosing its i2-th child, etc. Thus, a path from the root to a child can be represented as an ordered list of child indices. Example.

Oof, that's an ugly case.

The problem here is that &mut loans are treated by the compiler as uniquely owned non-copyable objects (almost like a String). When you call a &mut self method (including indexing list), it implicitly performs a reborrow, which creates a new loan (another &mut Node instance which isn't your old &mut Node instance).

But once you put explicit lifetimes on this, like &'a mut &'a mut Node or &'a mut &'b mut Node where 'a: 'b, this tells the compiler that borrowing &mut cursor is same or longer than borrowing &mut root, so the cursor stays borrowed "forever".

edit: bad idea removed

A different solution could be:

cursor = go(cursor, 0);

fn go(cursor: &mut Node, number: usize) -> &mut Node {
    &mut cursor.list[number]
}

Then the reborrowing happens inside go, and you don't deal with nested lifetimes.

This seems like a non-solution to me, which if I’m not mistaken in this assessment would also imply that it would be a bad suggestion to have the compiler suggest this. As far as I understand, the intention here is that after the go(&mut cursor, 0); call, the cursor variable ought to have been updated via the *cursor = … assignment inside go (where cursor is the function argument; same name, different thing). By passing a borrow of a re-borrow, the original cursor is never modified.

The correct signature for go that we would actually want for this is

fn go<'a>(cursor: &mut &'a mut Node, number: usize)

but that seems to be hard to implement correctly.

Oh, right. I forgot that it needs to update, not just compile :slight_smile:

Would fudging this with unsafe actually be unsafe?

fn go(cursor: &mut &mut Node, number: usize) {
    *cursor = unsafe { std::mem::transmute::<&mut Node, &mut Node>(&mut cursor.list[number]) };
}

I mean it is possible, using some trickery

fn go<'a>(cursor: &mut &'a mut Node, number: usize) {
    let _ = &cursor.list[number]; // panic if out-of-bounds, to avoid an abort below
    replace_with::replace_with_or_abort(cursor, |cursor| &mut cursor.list[number]);
}

Rust Explorer

Edit: Right… having the 'a lifetime still named is redundant now, and &mut &mut Node – like @kornel did above –is nicer to read. Im not going to edit all my usages of this signature now, but note that they’re the same.

2 Likes

I do believe that a sufficiently advanced / improved borrow checker might/could/should actually eventually allow the original code with the “corrected” signature.

Wow, it looks like magic. I quickly checked whether this crate was suitable for my real project and not only for MRE. At first glance, it looks like it's working, maybe later there will be cornerstones. Thank you all. Looks like I shouldn't have skipped software design classes :slight_smile:

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.