what's the best way to 'borrow' a struct deeply moved into other objects?

Question

I am working on a way to programmatically new struct in memory and append it to the linked list.

The way I am doing is to new a struct, new a box pointing to it and wrap it by Option. Then I need to move the tail pointer down to the newly created one.

I want to previous node owns the next node. So the tail pointer has to 'borrow' the node.

#[derive(Debug)]
struct S {
    next: Option<Box<S>>,
}

#[cfg(test)]
mod test {
    use crate::tmp::S;
    use std::borrow::Borrow;

    #[test]
    fn test_tmp() {
        let mut s1 = S { next: None };
        let mut tail = &s1;
        // potentially within a loop as a linked list has multiple nodes
        {
            let mut s2 = S { next: None };
            s1.next = Some(Box::new(s2));
//            tail = &s2;
            tail = s1.next.as_ref().unwrap();
        }
        println!("s1: {:?}", &s1);
        println!("tail: {:?}", &tail);
    }
}

The line commented out does not work as the owner has been moved to s1, I am fine with it.

tail = &s2

It's just so ugly but the next line works. Assuming if I have a struct that deeply wrapped and I want to borrow it. Does that mean I have to unwrap it deeply again?

tail = s1.next.as_ref().unwrap();

There must be some way to do it better. Any hints?

Since you are working with references that needs to be counted in such case, it is better to use Rc. Because of you want to mutate the data from the references you have, it is better to wrap it with Mutex. Playground — Akiner Alkan
I am very new to rust. Haven't tried Rc yet. but I will. Thanks! — Fangzhou Xu

SOFe SOFe · Accepted Answer · 2019-08-16T07:14:43

Yes, this is the only way to do it, but it is not bad at all.

When you push a value into a linked list, you already moved the value's effective ownership (I said effective, because a Box only effectively owns the underlying value, but does not directly own it in terms of Safe Rust) to the last node. But how did you do it? To move A into B, you also have to own &mut B. And you only want to get a &A (or a &mut A). Why don't you get that from &mut B, since you already borrowed it anyway?

I don't understand what you really mean by "deeply wrapped". But assume we have a head: S and a tail: &mut S, where the tail borrows the last node of the linked list led by head. Now, to get an updated reference of tail after moving new_tail into tail, you simply change tail to tail.next (plus the Option and Box unwrapping code, but those don't affect ownership).

Have a look at this new playground code: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=1103d2f039c24ed6ea78408d613a4261

You should insert your data with tail: &mut S rather than from head. This is the whole point of the linked list. So to answer your question, yes, you have to borrow the moved node from its precedent node, but you already borrowed precedent node anyway, so it is nothing ugly.

Actually, I cheated there. I secretly swapped the last two println! lines. If you swap them back, you would realize that &s1 cannot be used before the last use of tail, because tail mutably (hence exclusively) borrows something inside s1.

error[E0502]: cannot borrow `s1` as immutable because it is also borrowed as mutable

So how to fix this? You can't do this directly, because you might end up with poisoned data if the thread panics while working with some mutable data. This question also discusses why mutable references cannot be reused.

You might want to use a Cell to hold data that you want to make internally mutable with just an immutable borrow. But this would be tricky. Or if you want to go multi-threaded, you might try Mutex.

But all this complexity aside, if you want real, intuitive, fast, low-level Rust, you have to work with Unsafe Rust.

what's the best way to 'borrow' a struct deeply moved into other objects?

1 Answers