Skip to content

Rust as_ref and as_mut Usage in the Linked List

Recently, I tried to write leetcode by rust. Everything goes well until I started to write code for linked list. The borrow check is quite verbose and I got stuck by the borrow check when handling Option<Box<LinkedNode>> more than the problem itself.

It's sad to find I don't understand the borrow check well, but it's also a good chance to find these missing knowledge for me.

This blog discusses about as_ref, as_mut and take of the Option.

Option and Its Derivatives

The Option<i32> is the most common use case, and you have owned the inner i32 when you are an owner of the outer Option(Some indeed). So you can move the inner value alone or move the whole value.

Here are some derivatives of Option<T>, which contains ref and mut specifiers. Some of them have different owners between inner and outer.

Option<&i32>
Option<mut i32>
Option<&mut i32>
& Option<i32>
&mut Option<i32>
& Option<& i32>
// ...
&mut Option<&mut i32>

These types help you distinguish the inner and outer type.

  • Option<&i32>: you own the Option, so you can turn it to None, this is the ownership to Option means. But the value inside the container isn't yours, you cannot move it, you only hold the reference to it. The &i32 points to its owner, which could be a Option<i32> or a single i32 variable.
  • Option<mut i32>: the outer option is immutable, means that you cannot turn a Some into None. But the inner i32 is owned by you and mutable, so you can change the value to whatever you like.
  • & Option<i32>: the whole Option, both outer and inner are reference, you don't own it at all.
  • &mut Option<i32>: you have a mutable reference of a Option<i32>, so you can change the outer only(turn it to None) because you hold the mutable reference. However, you cannot change the inner i32 because its immutable.
  • & Option<&i32>: both outer and inner are reference, it means that the Option owner doesn't own the inner i32 if any, and now you hold a ref to it. Differ from &Option<i32, the Option owns the inner i32.
  • &mut Option<&mut i32>: inner and outer are mutable, you can change whatever you like.

In short, the Option is a container and it might hold an item. The ownerships of container(Option) and contained value(i32) are separated and depends on the types.

as_ref and as_mut

The signatures are interesting and could explain everything indeed. The 2 functions(as_ref and as_mut) don't require ownership, reference is enough. The returned type is Option, which means it creates a temporary outer Option, instead of reusing the existing one. Hence, the caller of as_ref or as_mut owns the ownership of returned option. Then, the inner value is borrowed from somewhere else.

pub const fn as_mut(&mut self) -> Option<&mut T>
pub const fn as_ref(&self) -> Option<&T>

The as_ref is easy to understand as it borrows the original T and leave it as &T in the new constructed Option. However, the as_mut is a bit confusing because the original &mut self doesn't mark the inner T is mutable.

  • &mut Option<T>.as_mut(): because the whole Option<T> is mutable while the Option owns the T, so it means you can safely borrow the inner T as mutable.
  • &mut Option<&T>.as_mut: this is confusing at the beginning, because the value T never stated it's mutable. It's true, but it doesn't mean the &T cannot be borrowed as mutable. The Option owns the variable of &T(change the ref points to), instead of &T itself. This is why the type of Option<&mut &i32>
    let v = 1;
    let mut of = &mut Some(&v);
    let v: Option<&mut &i32> = of.as_mut();

take

Function take requires a mutable reference for the outer Option because it turns the original Option to None. Then, the take constructs a new outer option and gives caller the ownership. The inner value is taken from the original Option, so it keeps the previous type. If the previous option owns the ownership of inner value, the ownership changes as well.

Remove Duplication from a Linked List

The question is simple. It removes the duplicated nodes from a linked list. It's quite verbose to tackle with the borrow checker.

The keypoint is focus on the reference and the value move. You should always create a reference by calling as_ref or as_mut when you want to change the sentry during looping and move the value only if you want to move it to the final result.

The following code is a correct implementation for leetcode question 83 "Remove Duplicates from Sorted List". It defines the following variables:

  • dummy: the final result, so it a value.
  • prev: the sentry at tail to add new nodes, it should be a reference without ownership.
  • cur: a value with ownership, so it could be moved if it satisfies the limitation.
  • next: a reference because we only want to access its next value instead of moving it.

Besides the reference and value, taking reference also turns the original Option to None. It's a bit subtle and worthy to explain more.

    pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut dummy = Box::new(ListNode::new(0));
        dummy.next = head;
        let mut prev = &mut dummy;
        while let Some(mut cur) = prev.next.take() {
            while let Some(next) = cur.next.as_mut() {
                if cur.val.eq(&next.val) {
                    cur.next = next.next.take();
                } else {
                    break;
                }
            }
            prev.next = Some(cur);
            prev = prev.next.as_mut().unwrap();
        }
        dummy.next
    }

I have draw a diagram for you to see the consequence when moving variables.

rs_lc_move_status.png