The code won't be compiled for returning a mutable reference

help
1

Hi, as a newbie, i need help for trying to write a linked list to find some position to be changed.

pub(crate) struct Node<T>(T, Option<Box<Node<T>>>);

pub(crate) struct LinkedList<T>(Option<Box<Node<T>>>);

pub(crate) struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

pub(crate) struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}

It's not compiled for a mutable find() like this:

    pub fn find_mut<'a>(&'a mut self, start: Option<&'a mut Node<T>>, value: &T) -> IterMut<'a, T>
    where
        T: PartialEq,
    {
        let mut head = if let Some(_) = start {
            start
        } else {
            self.0.as_deref_mut()
        };

        loop {
            match head {
                Some(&mut Node(ref v, ref mut next)) => { // 155
                    if v == value {
                        // rr = head;
                        break;
                    } else {
                        head = next.as_deref_mut();
                    }
                }
                None => {
                    // rr = head; // to Tail
                    break;
                }
            }
        }
       
        IterMut { next: head }  // 170 <- error here
    }

it shows the error like these:
cannot move out of head because it is borrowed
move out of head occurs here r...)

linkedlist.rs(155, 39): borrow of head.0.1 occurs here

linkedlist.rs(143, 21): lifetime 'a defined here

linkedlist.rs(170, 9): returning this value requires that head.0.1 is borrowed for 'a

But it would be compiled ok for a non-mutable find():

    pub fn find<'a>(&'a self, start: Option<&'a Node<T>>, value: &T) -> Iter<T>
    where
        T: PartialEq,
    {
        let mut head = if let Some(_) = start {
            start
        } else {
            self.0.as_deref()
        };

        loop {
            match head {
                Some(&Node(ref v, ref next)) => {
                    if v == value {
                        break;
                    } else {
                        head = next.as_deref();
                    }
                }
                None => {
                    break;
                }
            }
        }

        Iter { next: head }
    }
2

due to the rust semantics model (ownership, lifetimes, borrow checker, etc), linked list is not as straight forward as in C/C++.

notably, mutable iterators cannot be safely implemented. for example, the following code would crash if a imaginary iter_mut() could have been implemented:

for node in list.iter_mut() {
    let _ = node.next.take();
}

immutable iterators are ok, the reason being, for a linked list, each node owns it's entire tail, but your iterator must borrow a node, which means the iterator itself and the reference it yielded (i.e. the Iterator::Item associated item) actually share the tail, so it cannot be mutable, otherwise, it violates the mutability and sharability exclusiveness.

3

Linked list are notoriously the worst thing a newbie could implement to learn Rust, but that's still a common starting point for many. You might be interested in the excellent (and fun!) Learn Rust With Entirely Too Many Linked Lists.

4 Likes
4

yes, i just want to learn the concept of borrow, so do some exercise with the rust ownership model. but there seems some gaps prevent to write safe self-structured codes.

5

thanks, I had already learned the article before, and as a reference implementation. and then i tried some different codes to learn rust programming, then have the trouble above.

1 Like
6

in rust type system, the term mutable not only means "mutate", but also conveys the semantic of "exclusiveness", which conflicts in nature with pointer chasing data structures like linked lists, traditional graph-like types, self referential data structures, etc.

it's notoriously newbie unfriendly in this regards.

7

The problem is that you want to do two different and incompatible things with head in only one branch:

  • if v == value you want to break the loop and not consume head (that is, keep it valid in order to return it)
  • if v != value you want to keep looping and consuming head in order to make next have the required lifetime

A possible solution is to use a match guard instead of the if. This moves them to two different branches, solving the problem. Also note that the order of the branches here is important: you need to put the branch that consumes head after the one that doesn't.

2 Likes
8

if you just want to search a given value, it's fairly easy, but I suppose OP want to implement some kind of mutable iterator.

a direct translation from any functional code (e.g. lisp) results the following code (it compiles, but it's nothing to do with self, and the returned type cannot implement Iterator<Item = &mut Node>` anyway, so I assume it's not what OP wanted.):

    pub fn find_mut<'a>(&'a mut self, mut start: Option<&'a mut Node<T>>, value: &T) -> IterMut<'a, T>
    where
        T: PartialEq,
    {
        while let Some(head) = start {
            if head.0.eq(value) {
                return IterMut { next: Some(head) }
            }
            start = head.1.as_deref_mut();
        }
        IterMut { next: None } 
    }
2 Likes
9

So amazing, the modified code seems works. so I learned the reason.

10

nice, this logic is right. my code always return some result.

11

They can be.

7 Likes
12

thanks for the code. what I meant was iterators that yield mutable references to the nodes are not implementable. iterators of references to inner values are fine.

because shared references are Copy, iterator yielding immutable references to list nodes are trivially implementable, new learner (I'm talking about myself) is confused when they find out if they add mut keyword to the reference, the code stops working. it's good lesson to learn about the non-aliasing nature of mut.

3 Likes
13

Yes, that's true, and for the reasons you outlined.

1 Like