Make a mutable reference [solved]

help
1

Hello!

I'm trying Rust. I implement doubly-linked list in order to get some practical skills. So... I have a structure represents a doubly-linked list, it's ok. There are also Item structure and Iter structure. Let's take a look at the code.

type OptItem<T> = Option<Box<Item<T>>>;

#[derive(Debug)]
struct Item<T> {
    value: T,
    prev: *mut Item<T>,
    next: OptItem<T>,
}

pub struct Iter<'a, C: 'a> {
    link: Option<&'a mut Item<C>>,
}

So I've got an issue with moving an iterator. Let's take a look at the code.

impl<'a, C: 'a> Iter<'a, C> {
    pub fn next(&mut self) {
        self.link = match self.link {
            Some(Item{ value: _, prev: _, next: Some(next_item) }) => Some(&mut **next_item),
            _ => None,
        };
}

The error I get looks so

error[E0495]: cannot infer an appropriate lifetime for pattern due to conflicting requirements
  --> src/list/mod.rs:60:54
   |
60 |             Some(Item{ value: _, prev: _, next: Some(next_item) }) => Some(&mut **next_item),
   |                                                      ^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 58:5...
  --> src/list/mod.rs:58:5
   |
58 | /     pub fn next(&mut self) {
59 | |         self.link = match self.link {
60 | |             Some(Item{ value: _, prev: _, next: Some(next_item) }) => Some(&mut **next_item),
61 | |             _ => None,
62 | |         };
63 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/list/mod.rs:60:54
   |
60 |             Some(Item{ value: _, prev: _, next: Some(next_item) }) => Some(&mut **next_item),
   |                                                      ^^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 57:1...
  --> src/list/mod.rs:57:1
   |
57 | impl<'a, C: 'a> Iter<'a, C> {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: ...so that the expression is assignable:
           expected std::option::Option<&'a mut list::Item<C>>
              found std::option::Option<&mut list::Item<C>>

As far as I get the Borrow Checker doesn't know that the available by field next will live long enough supposing that link field can be changed. Am I right? Please help me to get what the Borrow Checker means.

2

This book covers everything you would want to know about doubly linked lists in Rust, if you haven't already seen it: Learning Rust With Entirely Too Many Linked Lists

4 Likes
3

BTW, doubly-linked list is the worst structure to learn Rust, because it's one of the few structures that don't fit Rust's borrowing model. So you're not learning safe idiomatic Rust, but learning how to work around it and use it like C (that's still useful, but not as the first thing you learn).

Try exercism.io. It has similarly small tasks, but they can be done in safe idiomatic Rust.

3 Likes
4

All of links are really interesting for me. Thank you very much! But my question is why can't I assign a mutable reference I got from a structure field to the field inside match block? I see what compiler tell me about anonymous lifetime of the reference but the reference is owned by value that is referenced by the field of the Iter structure. Binary question. Is it possible to "explain" that to compiler or I should just admit that?

5

This compiles:

pub struct Iter<'a, C: 'a> {
    link: Option<&'a Item<C>>,
}

impl<'a, C: 'a> Iter<'a, C> {
    pub fn next(&mut self) {
        self.link = Some(self.link.as_ref().unwrap().next.as_ref().unwrap());
    }
}

but this doesn't:

#![feature(nll)]
type OptItem<T> = Option<Box<Item<T>>>;

#[derive(Debug)]
struct Item<T> {
    value: T,
    prev: *mut Item<T>,
    next: OptItem<T>,
}

pub struct Iter<'a, C: 'a> {
    link: Option<&'a mut Item<C>>,
}

impl<'a, C: 'a> Iter<'a, C> {
    pub fn next(&mut self) {
        self.link = Some(self.link.as_mut().unwrap().next.as_mut().unwrap());
        
    }
}

so it's probably one of these cases where immutable reference works due to variance (the compiler is flexible and can narrow lifetimes to match requirements), but the compiler is super strict about mutable lifetimes and wants them all identical (invariant). Shorter mutable lifetimes are handled differently as "reborrows", which don't work in all cases.

I'd file it under "borrow checker doesn't understand that such code is safe, because of edge cases lurking behind mutable borrows", but @vitalyd understands more of this trickyness than I do.

1 Like
6

Yeah, mutability throws a big 'ol wrench into the mix :slight_smile:. Your 2nd example can be made to work with:

impl<'a, C: 'a> Iter<'a, C> {
    pub fn next(&mut self) {
        self.link = Some(self.link.take().unwrap().next.as_mut().unwrap());
    }
}

The issue is that next() only borrows self mutably for some (elided) lifetime, which is shorter than 'a. But the link field wants a &'a mut based reference (borrow). So the compiler complains that it cannot satisfy that &'a mut lifetimed borrow when it only has a shorter (elided) mutable borrow on self. Mutable references place us back into the world of move-only constructs (modulo reborrows in some contexts, as you mentioned) - we need to ensure that the mutable reference is only in one place if we want to "transfer" it around, even if "around" is within the Iter struct (more on that below). Immutable references are Copy types, and yeah, they're easier to use because variance makes things simpler.

So, we take() the &'a mut borrow out of link, which disassociates the &mut self lifetime with the field's lifetime, and then put back another &'a mut borrow by "following" the &'a mut borrow we had over that value to its next value.

2 Likes
7

I thought so and I tried something like that

impl<'a, C: 'a> Iter<'a, C> {
    pub fn next(&mut self) {
        let link = replace(&mut self.link, None);
        self.link = match link {
            Some(Item{ value: _, prev: _, next: Some(next_item) }) => Some(&mut **next_item),
            _ => None,
        };
    }
}

But it hasn't worked before. Damn magic. Thanks for all. Solved!

1 Like