How to overcome the borrow checking here?

I'm trying to implement a balanced push in binary tree as below

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

type Link<T> = Option<Box<Node<T>>>;

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

impl<T> Node<T> {
	pub fn new(elem: T) -> Self {
		Self {
			elem, left: Default::default(), right: Default::default()
		}
	}

	fn balanced_push(&mut self, n: usize) -> (&mut Link<T>, usize) {
		if let Some(left_node) = self.left.as_mut() {
			if let Some(right_node) = self.right.as_mut() {
				let (lo, l) = left_node.balanced_push(n + 1);
				let (ro, r) = right_node.balanced_push(n + 1);
				if l <= r { (lo, l) } else { (ro, r) }
			} else {
				(&mut self.right, n)
			}
		} else {
			(&mut self.left, n)
		}
	}
}

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

	pub fn push(&mut self, elem: T) {
		if let Some(node) = self.root.as_mut() {
			let (link, _) = node.balanced_push(0);
			*link = Some(Box::new(Node::new(elem)));
		} else {
			self.root = Some(Box::new(Node::new(elem)));
		}
	}
}

I've a problem with the method balanced_push. There are two mutable borrows occurring and compiler is complaining about it. How to solve this problem and compile it?. Can anyone help help me me please :pray:? This is only function I'm having the double mut problem

I think you've run into a known limitation of the borrow checker. In the future this will be fixed by a new version of borrowck called Polonius, but for now I think you can work around it with is_some:

fn balanced_push(&mut self, n: usize) -> (&mut Link<T>, usize) {
	if self.left.is_some() {
		if self.right.is_some() {
			let (lo, l) = self.left.as_mut().unwrap().balanced_push(n + 1);
			let (ro, r) = self.right.as_mut().unwrap().balanced_push(n + 1);
			if l <= r { (lo, l) } else { (ro, r) }
		} else {
			(&mut self.right, n)
		}
	} else {
		(&mut self.left, n)
	}
}
2 Likes

Thanks for the help. I hope this limitation will be fixed ASAP

In this case, you can actually mostly keep the original version if you do a destructuring borrow at the top of the function.

 fn balanced_push(&mut self, n: usize) -> (&mut Link<T>, usize) {
        let Self { left, right, .. } = self;
        if let Some(left_node) = left {
            if let Some(right_node) = right {
                let (lo, l) = left_node.balanced_push(n + 1);
                let (ro, r) = right_node.balanced_push(n + 1);
                if l <= r { (lo, l) } else { (ro, r) }
            } else {
                (right, n)
            }
        } else {
            (left, n)
        }
    }
2 Likes

Another possible solution is using ref mut instead of as_mut().

fn balanced_push(&mut self, n: usize) -> (&mut Link<T>, usize) {
	if let Some(ref mut left_node) = self.left {
		if let Some(ref mut right_node) = self.right {
			let (lo, l) = left_node.balanced_push(n + 1);
			let (ro, r) = right_node.balanced_push(n + 1);
			if l <= r { (lo, l) } else { (ro, r) }
		} else {
			(&mut self.right, n)
		}
	} else {
		(&mut self.left, n)
	}
}
4 Likes

Thanks for the answers :smiley:. But, you broke my understanding of the rust.
Doesn't it move the value when you do like this.

or like this:

Both answers successfully compiles but, if do like this:

fn swap<T>( ref mut a: T,  ref mut b: T) {
    std::mem::swap(a, b);
}

fn main() {
    let a = String::from("asdas");
    let b = String::from("fasld");
    swap(a, b);
    println!("{} {}", a, b);
}

this gives me error that the value has moved like this:

error[E0382]: borrow of moved value: `a`
 --> src\main.rs:9:23
  |
6 |     let a = String::from("asdas");
  |         - move occurs because `a` has type `String`, which does not implement the `Copy` trait
7 |     let b = String::from("fasld");
8 |     swap(a, b);
  |          - value moved here
9 |     println!("{} {}", a, b);
  |                       ^ value borrowed here after move

I don't seem to understand when does the compiler does a move or a borrow

If you put ref or mut on an argument, that doesn't change anything wrt. whether it moves or borrows it. In function signatures, that is solely determined by the type, which is to the right of the colon. If the type is T, it moves it.

1 Like

You can read some information about the ref pattern in the book and in the docs.

The basic idea is that using ref in a pattern allows you to specify that the matched thing must borrow and not move. This is exactly what is happening in the code written by @jan17.

On the other hand, the solution by @drewkett works because of the match ergonomics. Let me show you what I mean:

Here self is of type &Self (note the &), which means that the pattern cannot take ownership of Self. Without match ergonomics we should have written the following:

let &Self { ref left, ref right, ..} = self;

which is obviously more explicit, but extremely verbose. Thanks to this feature we can let the compiler deduce the only thing that is possible (borrow left and right). If you don't know about this feature, it is obviously misleading, but after some time you will appreciate not having to be explicit about ref.

@alice was faster :grin:

1 Like

I think it is usually best to avoid any use of ref unless you run into one of the edge-cases where it only compiles if you use it. Besides those few edge cases, it is never necessary.

Thanks for the answers :smile:. But, I think I need more practice to get the intuition about this pattern matching. It seems very magical to me.

Generally the rule of pattern matching when borrowing is involved is that if you match on a reference to a struct, then it works like normal except that all the struct's fields turn into references to fields.

The above rule applies as long as you are not using ref anywhere in your pattern.

2 Likes