Rust lifetimes: Separate your immutable parts from your mutable parts using RefCell

I recently ran into a Rust lifetimes issue when working on a toy project of mine. The simplified problem is as such: I have a struct Foo which owns a String and has a counter.

struct Foo {
	owned_string: String,
	prefix_index: usize
}

What I want to do is to implement the Iterator trait for this struct. I want to iterate over all prefixes of this owned string. We might do something like this:

impl Foo {
	// NOTE that lifetimes are not needed here since this has only one parameter
	// Added for clarity
	pub fn next_prefix<'a>(&'a mut self) -> &'a str {
		let res = &self.owned_string[self.prefix_index..];
		self.prefix_index += 1;
		res
	}
}

impl Iterator for Foo {
	type Item = &'a str; // This is not possible, the lifetime 'a is only available inside next
	fn next(&'a mut self) -> Option<Self::Item>{}
}

But before we go into the implementation of the iterator body, we run into a problem: We need a lifetime for Item. We know what we want to do: We want to connect the lifetime of the string to the lifetime of Foo, but there’s no way to do so here, since the lifetime ‘a which we want Item to have is only available inside the next function. This can also be fixed through generic associated traits, where we have Item instead be a generic type constructor that accepts a lifetime - we’re basically deferring the instantiation of Item till we’re in the next function.

Something like:

	impl Iterator for Foo {
		type Item<'a> = &'a str;
		fn next(&'a mut self) -> Option<Self::Item<'a>>{}
	}

NOTE : The above has not been compile-tested, I just added it to illustrate another approach. However, this is not possible without defining a new trait, since we’re changing the signature of the Iterator trait. Is there some way of accomplishing it purely with the Iterator trait?

Here’s an idea: Instead of implementing Iterator for Foo, why not implement it for a reference of Foo? Specifically, a mutable reference, since we want to modify Foo.

	impl<'a> Iterator for &'a mut Foo {
		type Item<'a> = &'a str;
		fn next(&'b mut self) -> Option<Self::Item>{
			self.next_prefix()
		}
	}

Note that self here is of type: &'a mut Foo. So what we actually have is a mutable reference (with lifetime b) to a mutable reference (with lifetime a) of Foo. This almost looks like this should work, what we’re really doing is: &'b mut &'a mut Foo -> &'a str.

However, what happens when we run this? We get the compiler complaining about lifetimes:

function was supposed to return data with lifetime `'a` but it is returning data with lifetime `'b`

Wait what - in next, we’re returning a string from next_prefix. In next_prefix, self is of type: &‘a mut Foo & we’re returning a reference of type &'a str. Why does the compiler think it is &'b str? Here comes the subtlety (at least for me) of mutable references: Since as per Rust, there can only be one active mutable reference, mutable references can only be borrowed, not copied.

This means that the &'a str reference resulting from borrowing &'a mut Foo and &'a mut Foo was obtained by borrowing from &'b mut &'a mut Foo. Thus, the Rust lifetime actually assigns the lifetime 'b to the return value instead of 'a.

So what is the solution? Well, really, we want to borrow from an immutable part of T, so we know that our references would be valid, but Rust doesn’t know that, since the borrow is obtained through a mutable reference to Foo inside next_prefix. So what we want to do is to decouple the mutable parts from the immutable parts - this is precisely the use case for the “interior mutability pattern”.

So, what we can do is to split Foo into Foo and FooMutable, where FooMutable contains and controls all the mutable state and we use RefCell to store an instance of FooMutable inside Foo.

This would be something like:

use std::cell::RefCell;
struct FooMutable {
    prefix_index: usize,
}

impl FooMutable {
    pub fn increment(&mut self) {
        self.prefix_index += 1;
    }
	
	pub fn get_prefix_index(&self) -> usize {
		self.prefix_index
	}
}
struct Foo {
    foo_mutable: RefCell<FooMutable>,
    owned_string: String,
}

impl Foo {
    pub fn next_prefix<'a>(&'a self) -> &'a str {
        let mut foo_mutable = self.foo_mutable.borrow_mut();
        let idx = foo_mutable.get_prefix_index();
		let ret = &self.owned_string[0..idx];
		foo_mutable.increment();
		ret
    }
}

Notice the interior mutability pattern: In next_prefix, we an immutable reference to self. However, we’re able to obtain a mutable reference to foo_mutable through the RefCell (which defers checks of multiple mutable references to runtime). We are not violating any rules around mutability, we’re merely returning a slice of an immutable String (immutable since we don’t have any mut functions with access to it), so it will always be valid. Since we’re borrowing from &'a Foo (an immutable reference), which has the Copy trait implemented, it does not have to borrow from &'b mut &' Foo and can directly copy rhe reference & borrow from it.

Then we can implement Iterator for an immutable reference of Foo instead of a mutable reference for Foo.

impl<'a> Iterator for &'a Foo {
    type Item = &'a str;
    fn next(&mut self) -> Option<Self::Item> {
        return Some(self.next_prefix());
    }
}

    let foo = Foo {
        foo_mutable: RefCell::new(FooMutable {
            prefix_index: 0
        }),
        owned_string: "Hello".to_owned()
    };
    for i in 0..5 {
        println!("{}", (&foo).next().unwrap());
    }
}

Output:

H
He
Hel
Hell

This works as we expect it to.

Side note: Elaboration on why lifetime for “outer” reference is used when you mutably borrow from “inner” reference

TODO

comments powered by Disqus