How to implement an iterator giving struct with lifetimes?

Question

I want to create a mutable iterator that control modifications, for this I create a struct named FitnessIterMut that impl the Iterator trait. The next() method gives a struct that can do things on the container itself when a modification is done. (Is it a good way to do this sort of things ?)

pub struct FitnessModifier<'a, T: 'a> {
    wheel: &'a mut RouletteWheel<T>,
    value: &'a mut (f32, T)
}

impl<'a, T> FitnessModifier<'a, T> {
    pub fn read(&'a self) -> &'a (f32, T) {
        self.value
    }

    pub fn set_fitness(&'a self, new: f32) {
        let &mut (ref mut fitness, _) = self.value;
        self.wheel.proba_sum -= *fitness;
        self.wheel.proba_sum += new;
        *fitness = new;
    }
}

pub struct FitnessIterMut<'a, T: 'a> {
    wheel: &'a mut RouletteWheel<T>,
    iterator: &'a mut IterMut<'a, (f32, T)>
}

impl<'a, T> Iterator for FitnessIterMut<'a, T> {
    type Item = FitnessModifier<'a, T>;

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(value) = self.iterator.next() {
            Some(FitnessModifier { wheel: self.wheel, value: value })
        }
        else {
            None
        }
    }
}

This gives me this error, I think I have to do a 'b lifetime but I'm a little lost.

error: cannot infer an appropriate lifetime for automatic coercion due to conflicting requirements [E0495]
        Some(FitnessModifier { wheel: self.wheel, value: value })
                                      ^~~~~~~~~~
help: consider using an explicit lifetime parameter as shown: fn next(&'a mut self) -> Option<Self::Item>
fn next(&mut self) -> Option<Self::Item> {
    if let Some(value) = self.iterator.next() {
        Some(FitnessModifier { wheel: self.wheel, value: value })
    }
    else {
        None

Francis Gagné · Accepted Answer · 2016-05-21 18:34:32Z

You won't be able to get this to work with simple mutable references, unless you're OK with not implementing the standard Iterator trait. That's because it's not legal in Rust to have more than one usable mutable alias to a particular value at the same time (because it can lead to memory unsafety). Let's see why your code violates this restriction.

First, I can instantiate a FitnessIterMut object. From this object, I can call next to obtain a FitnessModifier. At this point, both the FitnessIterMut and the FitnessModifier contain a mutable reference to a RouletteWheel object, and both the FitnessIterMut and the FitnessModifier are still usable – that's not legal! I could call next again on the FitnessIterMut to obtain another FitnessModifier, and now I'd have 3 mutable aliases to the RouletteWheel.

Your code fails to compile because you assumed that mutable references can be copied, which is not the case. Immutable references (&'a T) implement Copy, but mutable references (&'a mut T) do not, so they cannot be copied.

What could we do to fix this? Rust lets us temporarily make a mutable reference unusable (i.e. you'll get a compiler error if you try to use it) by reborrowing from it. Normally, for types that don't implement Copy, the compiler will move a value instead of copying it, but for mutable references, the compiler will reborrow instead of moving. Reborrowing can be seen as "flattening" or "collapsing" references to references, while keeping the shortest lifetime.

Let's see how this works in practice. Here's a valid implementation of next. Note that this doesn't conform to the contract of the standard Iterator trait, so I made this an inherent method instead.

impl<'a, T> FitnessIterMut<'a, T> {
    fn next<'b>(&'b mut self) -> Option<FitnessModifier<'b, T>> {
        if let Some(value) = self.iterator.next() {
            Some(FitnessModifier { wheel: self.wheel, value: value })
        }
        else {
            None
        }
    }
}

Instead of returning an Option<FitnessModifier<'a, T>>, we now return an Option<FitnessModifier<'b, T>>, where 'b is linked to the lifetime of the self argument. When initializing the wheel field of the result FitnessModifier, the compiler will automatically reborrow from self.wheel (we could make this explicit by writing &mut *self.wheel instead of self.wheel).

Since this expression references a &'a mut RouletteWheel<T>, you thought the type of this expression would also be &'a mut RouletteWheel<T>. However, because this expression borrows from self, which is a &'b mut FitnessIterMut<'a, T>, the type of this expression is actually &'b mut RouletteWheel<T>. In your code, you tried to assign a &'b mut RouletteWheel<T> to a field expecting a &'a mut RouletteWheel<T>, but 'a is longer than 'b, which is why you got a compiler error.

If Rust didn't allow reborrowing, then instead of storing a &'b mut RouletteWheel<T> in FitnessModifier, you'd have to store a &'b &'a mut RouletteWheel<T>, where 'a is the lifetime of the RouletteWheel<T> and 'b is the lifetime of the &'a mut RouletteWheel<T> in the FitnessIterMut<'a, T>. However, Rust lets us "collapse" this reference to a reference and we can just store a &'b mut RouletteWheel<T> instead (the lifetime is 'b, not 'a, because 'b is the shorter lifetime).

The net effect of this change is that, after you call next, you can't use the FitnessIterMut at all until the resulting Option<FitnessModifier<'b, T>> goes out of scope. That's because the FitnessModifier is borrowing from self, and since the method passed self by mutable reference, the compiler assumes that the FitnessModifier keeps a mutable reference to the FitnessIterMut or to one of its fields (which is true here, not is not always true in general). Thus, while there's a FitnessModifier in scope, there's only one usable mutable alias to the RouletteWheel, which is the one in the FitnessModifier object. When the FitnessModifier<'b, T> goes out of scope, the FitnessIterMut object will become usable again.

If you absolutely need to conform to the Iterator trait, then I suggest you replace your mutable references with Rc<RefCell<T>> instead. Rc doesn't implement Copy, but it implements Clone (which only clones the pointer, not the underlying data), so you need to call .clone() explicitly to clone an Rc. RefCell does dynamic borrow checking at runtime, which has a bit of runtime overhead, but gives you more freedom in how you pass mutable objects around.

That's a beautiful explanation you do here, I think I will see another way to do this, the Rc<RefCell<T>> is not appropriate for what I want, I need performances, And I need to use the real Iterator Trait too. Thanks for that, you seem to know many things on Traits and Lifetimes :)

Collectives™ on Stack Overflow

How to implement an iterator giving struct with lifetimes?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related