Multiple mutable references

Here's the full code for reference (I use this as a module in another file):

use std::ops::{Index, IndexMut};

pub struct LinkedList<T> {
    head: Option<Node<T>>,
    len: usize
}

impl<T> LinkedList<T> {
    pub fn new() -> Self {
        Self {
            head: None,
            len: 0
        }
    }

    pub fn push(&mut self, val: T) {
        if let Some(mut current) = self.head.as_mut() {
            while current.has_next() {
                current = current.next_mut().unwrap();
            }

            current.set_next(Node::new(val));
        } else {
            self.head = Some(Node::new(val));
        }

        self.len += 1;
    }
    
    pub fn len(&self) -> usize {
        self.len
    }
}

impl<T> Index<usize> for LinkedList<T> {
    type Output = T;

    fn index(&self, idx: usize) -> &Self::Output {
        if idx >= self.len() {
            panic!("index out of bounds: the len is {} but the index is {}", self.len, idx);
        }

        let mut current = self.head.as_ref().unwrap();

        for _ in 0..idx {
            if let Some(next) = current.next() {
                current = next;
            } else {
                return current.val_ref();
            }
        }

        current.val_ref()
    }
}

impl<T> IndexMut<usize> for LinkedList<T> {
    fn index_mut(&mut self, idx: usize) -> &mut Self::Output {
        if idx >= self.len() {
            panic!("index out of bounds: the len is {} but the index is {}", self.len, idx);
        }

        let mut current = self.head.as_mut().unwrap();

        for _ in 0..idx {
            if let Some(next) = current.next_mut() {
                current = next;
            } else {
//======================================================================================================
                return current.val_mut(); // here
//======================================================================================================
            }
        }

        current.val_mut()
    }
}

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

struct Node<T> {
    raw: Box<RawNode<T>>
}

impl<T> Node<T> {
    fn new(val: T) -> Self {
        Self {
            raw: Box::new(RawNode {
                val: val,
                next: None
            })
        }
    }

    fn val_ref(&self) -> &T {
        &self.raw.val
    }

    fn val_mut(&mut self) -> &mut T {
        &mut self.raw.val
    }

    fn has_next(&self) -> bool {
        self.raw.next.is_some()
    }

    fn next(&self) -> Option<&Node<T>> {
        self.raw.next.as_ref()
    }

    fn next_mut(&mut self) -> Option<&mut Node<T>> {
        self.raw.next.as_mut()
    }

    fn set_next(&mut self, next: Node<T>) {
        self.raw.next = Some(next);
    }
}

I get a: cannot borrow `*current` as mutable more than once at a time.
I understand that you can't have multiple mutable references to anything at a time but I don't know why it happens with my code.

if let Some(next) = current.next_mut() { // 1st borrow?
    current = next;
} else { // 1st borrow lifetime ends?
    return current.val_mut(); // 2nd borrow?
} // 2nd borrow lifetime ends?

I also found out that the following code works (what I did in LinkedList::<T>::push):

if current.has_next() {
    current = current.next_mut().unwrap(); // 1st borrow?
} else {
    return current.val_mut(); // 2nd borrow?
}

I'm not sure if the main cause is the if let or something completely different. I'd like to understand why the first case doesn't work and if there are more possible solutions. Thanks.

Maybe this could be helpful https://rust-unofficial.github.io/too-many-lists/

@Luro02 thanks! I'll check that out to learn how people usually implement linked lists, but I would also like to understand why my code does not work.

Basically the issue is that the value current is eventually used to return a value with a lifetime long enough to outlast the function call. This means that when you call current.next_mut(), this borrows current for that long, meaning current is now borrowed for the entire duration of the function call. Since the later current.val_mut() happens inside the function call, the previous borrow has not yet ended.

2 Likes

@alice I think I get what you mean, but I'm still having a hard time understanding the difference between the 2 snippets. Why isn't current.next_mut().unwrap() borrowing for the entire duration of the call? Is there a difference between unwrapping and destructuring enums?

The difference is the order in which things happens: The unwrap doesn't happen when the val_mut call happens. I believe you may be interested in this similar thread.

2 Likes

@alice Thanks for explaining! That thread was also really helpful! From what I understand, *current is borrowed unconditionally in the first snippet on the if let line, I didn't think that was the case because next was out of scope in the else block, but it looks like I was mistaken.
The difference is more obvious here:

let next = current.next_mut();
if next.is_some() {
    current = next.unwrap();
} else {
    return current.val_mut();
}

Please correct me if I'm wrong in my understanding.