Magic lifetime using Iterator-> next()

[mezeipetister]

Hi Guys,

I have this glory question, could you check if I have any chance to solve it?

I have these structs:

struct Storage<T> {
data: Vec<T>,
path: &'static str,
}

struct StorageIter<'a, T> {
data: &'a mut Vec,
path: &'static str,
}

I would like to implement Iterator for Filter<'a, T>, and in fn next(&mut self) ->Optionself::Item I would like to get a mű table reference to Filter.data vector - which is also a reference.

But i have issues, as in Iter next() function I cannot manage lifetimes, as Iterator trait has fn next(&mut self), and I cannot change it to &'a mut self.

My relevant code is here:

pub struct StorageIter<'a, T> {
    data: &'a mut Vec<T>,
    index: usize,
    path: &'static str,
}

impl<'a, T> Iterator for StorageIter<'a, T> {
    type Item = &'a mut T;
    #[inline]
    fn next(&mut self) -> Option<&'a mut T> {
        if let Some(item) = &self.data.get_mut(self.index) {
            self.index += 1;
            return Some(*item);
        }
        None
    }
}

The error message is:

&mut StorageIter<'a, T>
cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements

note: ...so that reference does not outlive borrowed content
note: ...so that the expression is assignable:
      expected std::option::Option<&'a mut T>
         found std::option::Option<&mut T>

Do you have any advice to solve this?

Thank you in advance,
Best wishes,
Peter Mezei.

[alice]

The problem is that the borrow of data must end inside the next function, as otherwise it would still be borrowed next time you called next, which would prevent you from using it.

You should store a slice in data and use split_first_mut to obtain a reference to the first element that doesn't overlap with the reference stored in StorageIter.

You may need to use mem::replace to take data out of self before splitting it and then putting it back.

Note that alternatively you could just put the Iterator of the vector directly into your struct and call next on that inside your next.

[mezeipetister]

Something better using Slice, but still I have issues get_mut slice item with 'a lifetime.

pub struct StorageIter<'a, T> {
    data: &'a mut [T],
    index: usize,
    path: &'static str,
}

impl<'a, T> Iterator for StorageIter<'a, T> {
    type Item = &'a mut T;
    #[inline]
    fn next(&mut self) -> Option<&'a mut T> {
        if let Some(item) = self.data.get_mut(self.index) {
            self.index += 1;
            return Some(item);
        }
        None
    }
}

cannot infer an appropriate lifetime for autoref due to conflicting requirements

note: ...so that the expression is assignable:
      expected std::option::Option<&'a mut T>
         found std::option::Option<&mut T>rustc(E0495)

[alice]

You have to make the slice shorter, because you are not allowed to have several mutable references that point to the same elements. Note that index is not needed, because after making the slice shorter, the next element is always the first.

[mezeipetister]

Hm. What i haven’t written is I would like to get a mutable reference to an item of Storage data vector and put it inside a new Sturct called Data { } and return it as a result of iter next()

[alice]

Using split_at_mut looks like this:

fn next(&mut self) -> Option<&'a mut T> {
    let slice = mem::replace(&mut self.data, &mut []);
    match slice.split_first_mut() {
        Some((head, tail)) => {
            self.data = tail;
            Some(head)
        },
        None => None,
    }
}

playground

Of course there's nothing stopping you from putting head into some struct:

fn next(&mut self) -> Option<Data<'a, T>> {
    let slice = mem::replace(&mut self.data, &mut []);
    match slice.split_first_mut() {
        Some((head, tail)) => {
            self.data = tail;
            Some(Data {
                field: head,
                path: self.path,
            })
        },
        None => None,
    }
}

playground

[mezeipetister]

OMG it works!

Could you help me to understand what the god hell is happening here? Using slice why the lifetime works? Or in this solution why there is no issue with lifetime? And split_first_mut() removes the first item from slice, but it signatures says it resutrns &mut T and &mut [T]. So why it removes the first item, even its signatures says its just returns a reference?

[alice]

The first thing to understand is that having two mutable references that overlap in any way is never allowed, unless one is a borrow of the other.

If we expand all hidden lifetimes in the signature for next, it says:

impl<'a, T> Iterator for StorageIter<'a, T> {
    fn next<'s>(&'s mut self) -> Option<&'a mut T>;
}

Notice here that the lifetime of the return value is bound to 'a and not to the lifetime of self. This means that the returned reference is not a borrow of anything stored in self (it would have to borrow self to borrow from a field in self). It doesn't borrow from data — instead it borrows from the same thing that data borrows from. Since the returned item is accessible through data in your implementations, we have overlapping mutable references, and one does not borrow from the other. This is not allowed.

In order to avoid this issue and keep this signature, we have to stop data from overlapping with the returned reference. This can be done by creating a shorter slice that doesn't contain the item, which is exactly what split_first_mut does.

@mezeipetister

And split_first_mut() removes the first item from slice, but it signatures says it returns &mut T and &mut [T]. So why it removes the first item, even its signatures says its just returns a reference?

Remember that a slice is just a view into some other container. Of course, given a view, you can create a shorter one. Normally you can do this by typing e.g. &data[1..], which returns a shorter slice that doesn't include the first item. Creating a shorter view doesn't delete the item or anything. It's just a view.

The various split functions on slices allow turning a single mutable reference to a slice into several non-overlapping references. Notice that none of them allow creating overlapping references — that would not be valid.

[mezeipetister]

You made my day!

[mezeipetister]

@alice do you think it is possible to do the same trick with the following updated data struct?

pub struct Storage<T> {
    data: Mutex<Vec<Arc<Mutex<T>>>>,
    lookup_table: Mutex<BTreeMap<String, usize>>,
    path: &'static str,
}

I would like to create a slice from data, and put it into an iterator. My main purpose would be to lock() mutex, quickly create a slice of the contained Arc<Mutex> , put it in an iterator and then close lock(), so the iter process would not affect the lock time of the Storage.data.

I would say, it's possible. What do you think?
Thank you in advance.

[alice]

If the iterator is somehow accessing stuff contained in your value of type T, sure you can do that. If you want to iterate the rows in the vector, you'd have to go through every row you need and clone every arc before you can unlock the mutex. Each arc only gives access to one row.

Of course, you could also lock the mutex in each call to next.