Need help with lifetimes in simple piece of code. Beginner

I’m trying to write generic linked list in rust. And I’m stack on IterMut. Someone pls explain to me why there is error in my IterMut. I just copy RefIter which works fine and change all refs to mut refs. Thanks in advance.

This is because &mut T doesn’t mean mutable reference, it means unique reference. Similarly &T means shared reference, not read reference. Finally references are compile time locks, so the compiler must prove these properties at compile time. (The mutability rules are a side effect of safe defaults because shared mutability is a hard problem)

So, the problem is that with Rust must prove that IterMut always yields different unique compile time locks (&mut T), but Rust can’t do that right now because it isn’t true right now. You are trying to create aliasing unique references (they are aliasing for a very short time, but that is enough).
What you can do to fix this is to change your MutIter definition to

struct MutIter<'a, T> {
    next_node: Option<&'a mut Node<T>>,
    length: Index
}

And then use Option::take to temporarily remove the next_node and operate on that.

2 Likes

Be sure to read Learn Rust With Entirely Too Many Linked Lists, it will answer a lot of questions that are likely to arise.

Relevant excerpt (link):

the nature of shared and mutable references means that Iter is “trivial” while IterMut is Legit Wizard Magic.

1 Like

Thank you for explanation. It clear some things for me, particularly this - ’ So, the problem is that with Rust must prove that IterMut always yields different unique compile time locks ( &mut T )’ is what i missed in my understanding. I think i need to do something less complex in rust to wrap my head around ownership, borrowing and etc.

1 Like

Thanks for links, but I already saw that tutorial. The problem is that I did not fully understand what author did and why, so I was trying to implement it myself and figure out everything. But rust turned out to be not that simple for js programmer)

1 Like

Yes, working with lifetimes is challenging, but keep at it and you will get it eventually. To read more about this idea that references are compile time locks and about uniqueness see this blog post


I was on mobile before, so I couldn’t give any code, but here is how you would implement MutIter

playground link

struct MutIter<'a, T> {
    next_node: Option<&'a mut Node<T>>,
    length: usize
}

// IntoIterator allows you to use for loops directly
// like so
// 
// ```rust
// let mut node: Node<_>;
// 
// // init node ...
// 
// for i in &mut node {
//     // .. do stuff ..
// }
// ```
impl<'a, T> IntoIterator for &'a mut Node<T> {
    type Item = &'a mut T;
    type IntoIter = MutIter<'a, T>;
    
    fn into_iter(self) -> Self::IntoIter {
        MutIter {
            length: self.length,
            next_node: Some(self),
        }
    }
}

impl<'a, T> Iterator for MutIter<'a, T> {
    type Item = &'a mut T;
    
    fn next(&mut self) -> Option<Self::Item> {
        self.length = self.length.saturating_sub(1);
        
        let Node { next, data, length: _ } = self.next_node.take()?;
        
        self.next_node = next.as_mut().map(|x| x as &mut Node<T>);
        
        Some(data)
    }
}
1 Like