4

I am trying to reimplement LinkedList from scratch and I am having some trouble with the IterMut part. I just won't compile and I can't figure out why. The compiler just gives me the message:

src/lib.rs:59:19: 59:27 error: cannot infer an appropriate lifetime for autoref due to conflicting requirements [E0495]
src/lib.rs:59         self.next.as_mut().map(|head| {
                                ^~~~~~~~
src/lib.rs:58:5: 63:6 help: consider using an explicit lifetime parameter as shown: fn next(&'a mut self) -> Option<&'a mut A>
src/lib.rs:58     fn next(&mut self) -> Option<&'a mut A> {
src/lib.rs:59         self.next.as_mut().map(|head| {
src/lib.rs:60             self.next = &mut head.next;
src/lib.rs:61             &mut head.value
src/lib.rs:62         })
src/lib.rs:63     }
error: aborting due to previous error
Could not compile `linked_list`.

To learn more, run the command again with --verbose.

And here is the actual code:

use std::mem;

type Link<T> = Option<Box<Node<T>>>;

pub struct LinkedList<T> {
    head: Link<T>,
    length: usize,
}

struct Node<T> {
    value: T,
    next: Link<T>,
}

pub struct IterMut<'a, T: 'a> {
    next: &'a mut Link<T>,
}

impl<T> Node<T> {
    fn new(value: T) -> Node<T> {
        Node {
            value: value,
            next: None
        }
    }
}

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

    pub fn push_front(&mut self, elem: T) {
        let mut new_head = Box::new(Node::new(elem));
        match self.head {
            None => self.head = Some(new_head),
            Some(ref mut head) => {
                mem::swap(head, &mut new_head);
                head.next = Some(new_head);
            }
        }
        self.length += 1;
    }

    pub fn iter_mut(&mut self) -> IterMut<T> {
        IterMut {
            next: &mut self.head,
        }
    }
}

impl<'a, A> Iterator for IterMut<'a, A> {
    type Item = &'a mut A;

    fn next(&mut self) -> Option<&'a mut A> {
        self.next.as_mut().map(|head| {
            self.next = &mut head.next;
            &mut head.value
        })
    }
}

#[cfg(test)]
mod tests {
    use super::LinkedList;

    #[test]
    fn iter_mut() {
        let mut list = LinkedList::new();
        list.push_front(1);
        list.push_front(2);

        let mut iter = list.iter_mut();
        assert_eq!(iter.next(), Some(&mut 2));
        assert_eq!(iter.next(), Some(&mut 1));
        assert_eq!(iter.next(), None);
    }
}

Edit: Similarly, I implemented Iter which works. I naively assumed, that IterMut would work with just adding mut in the appropriate places. Here is the Iter part:

pub struct Iter<'a, T: 'a> {
    next: &'a Link<T>,
}

impl<T> LinkedList<T> {
    ...

    pub fn iter(&self) -> Iter<T> {
        Iter {
            next: &self.head,
        }
    }

    ...
}

impl<'a, A> Iterator for Iter<'a, A> {
    type Item = &'a A;

    fn next(&mut self) -> Option<&'a A> {
        self.next.as_ref().map(|head| {
            self.next = &head.next;
            &head.value
        })
    }
}

Why does Iter work but IterMut doesn't?

DeBe
  • 491
  • 3
  • 15
  • 1
    Have you seen [*Learning Rust With Entirely Too Many Linked Lists*](http://cglab.ca/~abeinges/blah/too-many-lists/book/)? – Shepmaster Feb 10 '16 at 16:15
  • @Shepmaster I have - unfortunately their implementation of `IterMut` struct slightly differs from mine, and I am wondering how to make it work without changing the struct. – DeBe Feb 10 '16 at 16:17
  • It's not possible without changing the `IterMut` struct. – bluss Feb 10 '16 at 22:40
  • And how would that exactly look like? – DeBe Feb 11 '16 at 06:28
  • In the linked article, the iterators hold references to the nodes, not to the links. This is probably important because it doesn't borrow the predecessor nodes. – Sebastian Redl Feb 11 '16 at 07:49
  • But the compiler does not complain about that, it complains about a lifetime it can't infer. Also: looking at the original implementation of LinkedList, the iterator also holds a reference to the Link. – DeBe Feb 11 '16 at 07:59
  • @SebastianRedl, Stuck with the exact some problem. It would really help if you could elaborate a little more. – Mihir Luthra May 17 '20 at 08:18
  • 2
    Does this answer your question? [\`cannot infer an appropriate lifetime for autoref due to conflicting requirements\` but can't change anything due to trait definition constraints](https://stackoverflow.com/questions/61847200/cannot-infer-an-appropriate-lifetime-for-autoref-due-to-conflicting-requirement) – SCappella May 17 '20 at 09:25
  • 1
    I've proposed [`cannot infer an appropriate lifetime for autoref due to conflicting requirements` but can't change anything due to trait definition constraints](https://stackoverflow.com/questions/61847200/cannot-infer-an-appropriate-lifetime-for-autoref-due-to-conflicting-requirement?noredirect=1#comment109393715_61847200) as a duplicate since it's practically the same question and has a couple good answers now. – SCappella May 17 '20 at 09:26

0 Answers0