2

I've searched about this question before, like this and this, but following the solution of the first link and try to apply them to my code, rustc seems misunderstand what I'm trying to do.

I wanted to create a linked list and assign some reference to the middle of the nodes and print their values. First I made them mutable in order to create the list from head ref to tail ref, then I wanted to convert them to be immutable, from tail ref to head ref, which wouldn't violate ownership rules. In the end, I wanted to access some immutable references(midway points) to get their values.

My code: (playground)

struct Node<T> {
    val: T,
    next: Option<Box<Node<T>>>,
}
impl<T> Node<T> {
    fn new(val: T) -> Option<Box<Node<T>>> {
        Some(Box::new(Node { val, next: None }))
    }
}
fn main() {
    let head = &mut Node::new(0);
    let a = &mut head.as_mut().unwrap().next;
    *a = Node::new(10);
    let b = &mut a.as_mut().unwrap().next;
    *b = Node::new(20);
    let c = &mut b.as_mut().unwrap().next;
    *c = Node::new(30);
    let tail = &mut c.as_mut().unwrap().next;
    *tail = Node::new(40);
    // Trying to make these mutable reference immutable.
    let tail = &*tail;
    // reference 'c' is converted to immutable,
    // so nothing borrows 'b' as mutable anymore
    let c = &*c;
    // Reports error anyway.
    // error[E0502]: cannot borrow `*b` as immutable
    // because it is also borrowed as mutable
    //  16 |     let c = &mut b.as_mut().unwrap().next;
    //     |                  ---------- mutable borrow occurs here
    // Didn't I just convert c to immutable?
    let b = &*b;
    let a = &*a;
    let head = &*head;
    println!(
        "a is {}, b is {}, c is {}",
        a.as_ref().unwrap().val,
        b.as_ref().unwrap().val,
        c.as_ref().unwrap().val
    );
}

Things had gone wrong here, rustc still reports that I try to borrow them as immutable because they are borrowed by ref that is mutable. But I already converted the ref to immutable before. Why?

Could there be any solution to make my program run as expected?

tadman
  • 208,517
  • 23
  • 234
  • 262
ArchBug
  • 45
  • 5
  • 3
    A playground link is good but not enough; the question must be self-contained. – Chayim Friedman Jun 26 '23 at 16:43
  • I think you're trying to force a pointer-style approach onto Rust here, which it doesn't really like or make easy. Why can't you have an `append()` method that adds on a `Box>`? – tadman Jun 26 '23 at 16:45
  • 2
    A reborrow that ends the original lifetime of the `&mut` and starts a new with `&` would allow for undefined behavior. See [this](https://github.com/pretzelhammer/rust-blog/blob/master/posts/common-rust-lifetime-misconceptions.md#9-downgrading-mut-refs-to-shared-refs-is-safe) – PatientPenguin Jun 26 '23 at 17:02

2 Answers2

5

You cannot.

You can convert a mutable reference to immutable one, as the linked questions show, but the object will still be borrowed mutably.

This is necessary for APIs like Cell::from_mut() to be sound: they convert a mutable reference to immutable, and rely on the object to continue be mutably borrowed.

If you want, you can re-follow the next pointers immutably:

let head = &*head;
let a = &head.as_ref().unwrap().next;
let b = &a.as_ref().unwrap().next;
let c = &b.as_ref().unwrap().next;

Playground.

But really, this whole linked-list-style-programming doesn't really fit into Rust.

Chayim Friedman
  • 47,971
  • 5
  • 48
  • 77
3

The problem is that a node owns its successors, so

  • c owns tail
  • b owns c and tail
  • a owns b, c and tail
  • head recursively owns the entire linked list.

This means that you can't keep a reference to head while mutating nodes it points to.

It doesn't matter if head is mutable or not; Rust's borrowing rules require that when you have a mutable reference to something, there can't be any other reference to the same data, mutable or not. A mutable reference is guaranteed to be exclusive.

You can fix your code by not keeping the references around:

let head = ...;
let a = &mut head.as_mut().unwrap().next;
drop(head);

The drop(head) isn't actually needed thanks to non-lexical lifetimes. A reference is implicitly invalidated when used for the last time.

So this code works:

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

impl<T> Node<T> {
    fn new(val: T) -> Option<Box<Node<T>>> {
        Some(Box::new(Node { val, next: None }))
    }
}

fn main() {
    let head = &mut Node::new(0);

    let a = &mut head.as_mut().unwrap().next;
    *a = Node::new(10);

    let b = &mut a.as_mut().unwrap().next;
    *b = Node::new(20);

    let c = &mut b.as_mut().unwrap().next;
    *c = Node::new(30);

    let tail = &mut c.as_mut().unwrap().next;
    *tail = Node::new(40);

    println!("head is {head:?}");
}

Note that you aren't able to access a, b and c at the end. However, you can still print them by accessing head.

You can also add a custom Debug implementation to get prettier output:

use std::fmt;

impl<T: fmt::Debug> fmt::Debug for Node<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut node = Some(self);
        write!(f, "[")?;
        while let Some(next_node) = node {
            write!(f, "{:?}, ", next_node.val)?;
            node = next_node.next.as_deref();
        }
        write!(f, "]")
    }
}

Then the output looks like this:

head is Some([0, 10, 20, 30, 40, ])

Note that there is an easier way to construct a linked list by creating the nodes in reverse order:

struct Node<T> {
    val: T,
    next: Option<Box<Node<T>>>,
}

impl<T> Node<T> {
    fn tail(val: T) -> Self {
        Node { val, next: None }
    }

    fn add(self, val: T) -> Self {
        Node { val, next: Some(Box::new(self)) }
    }
}

let head = Node::tail(40)
    .add(30)
    .add(20)
    .add(10)
    .add(0);
println!("head is {head:?}");
// output:
// head is [0, 10, 20, 30, 40, ]

Full code in playground

Aloso
  • 5,123
  • 4
  • 24
  • 41