Why is a reference considered borrowed?


#1

Why does the following code fail to compile?

struct Foo;

fn main() {
    let mut a = Foo;
    let mut b = Foo;
    let mut x = &mut a;
    let y = &*x;
    x = &mut b;
}

Error:

test18.rs:8:5: 8:15 error: cannot assign to `x` because it is borrowed [E0506]
test18.rs:8     x = &mut b;
                ^~~~~~~~~~
test18.rs:7:14: 7:16 note: borrow of `x` occurs here
test18.rs:7     let y = &*x;
                         ^~

I am puzzled at the error message regarding let y = &*x because y is borrowing *x but not x, so why cannot I change the binding of x in x = &mut b ?


#2

*x is Deref which borrows x.
It would need to be copied or cloned to no longer borrow.

To avoid the error shadow x.

let mut x = &mut b;

The compiler can not infer the intention is y should take over borrow reference to a directly. Decision may be at runtime.

let mut x = if rand()<0.5 {&mut a} else {&mut b};

#3

y = &*x is called a “reborrow” and is explained in more detail in the Rustonomicon. A mutable reference is treated as borrowed while any reborrow is live.

There is probably some way that Rust’s borrow checking could be relaxed to make your code compile, but it might make the implementation more complicated because it would still need to ensure that the next reference assigned to x doesn’t alias any values that are now reachable from y.


#4

Thanks for the explanation. I asked this question because it prevented me from writing a function that inserts into a binary search tree without using recursion. I ended up using transmute as in the code below. Is it possible to achieve this goal without any unsafe code?

use std::mem;
type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    key: T,
    left: Link<T>,
    right: Link<T>,
}

impl<T> Node<T> {
    fn new(key: T) -> Link<T> {
        Some(Box::new(Node{ key: key, left: None, right: None }))
    }
}

pub struct Tree<T> {
    root: Link<T>,
}

impl<T: Ord> Tree<T> {
    pub fn new() -> Self {
        Tree { root: None }
    }

    #[allow(mutable_transmutes)]
    pub fn insert(&mut self, key: T) -> bool {
        let mut link = &self.root;
        while let Some(ref node) = *link {
            if key == node.key {
                return false;
            } else if key < node.key {
                link = &node.left;
            } else {
                link = &node.right;
            }
        }
        let r: &mut Link<T>;
        unsafe {
            // change from & to &mut
            r = mem::transmute(link);
        }
        mem::replace(r, Node::new(key));
        true
    }
}

#5
    pub fn insert(&mut self, key: T) -> bool {
        fn move_reference<T>(t: T) -> T { t }
        let mut link = &mut self.root;
        loop {
            match move_reference(link) {
                &mut Some(ref mut node) =>  {
                    if key == node.key {
                        return false;
                    } else if key < node.key {
                        link = &mut node.left;
                    } else {
                        link = &mut node.right;
                    }
                }
                none_link => {
                    link = none_link;
                    break;
                }
            }
        }
        mem::replace(link, Node::new(key));
        true
    }

There’s a couple little tricks here, but essentially the key is to make sure to avoid reborrowing the pointer.


#6

You should never do this. Rust considers &-references to be deeply immutable (assuming there are no cells in the type). If your code works, this may be just luck that compiler isn’t smart enough yet to use that knowlege.

If you want to do it with unsafe, it’s better to use raw pointers:

let mut link: *mut _ = &mut self.root;
// (_ means "I'm too lazy to type Link<T>")

But of course, it’s better to use no-unsafe solution if possible.