I'm using a custom tree structure using vectors to store data and indices for the edges instead of pointers. Making an iterator with immutable references was fine, but I had to work around lifetime and multiple borrow compiler errors with the mutable version.
I would like to know if the work-around I chose is sound and idiomatic (as much as it can be for a work-around), and if there isn't a side-effect I overlooked.
I've put a simplified version here, with only one edge to the next item: playground. Please bear in mind that the actual tree structure has multiple edges and other features, so the idea isn't to refactor the code shown here to use slice iterators, for example.
The naive, first attempt looked like this:
// The list structure:
pub struct RevList<T> {
data: Vec<T>, // items
next: Vec<Option<usize>>, // next[i] is the index of data[i]'s next item
head: Option<usize> // index of first item in the list
}
// The mutable iterator:
pub struct RLIterMut<'a, T> {
next: Option<usize>,
list: &'a mut RevList<T>
}
impl<'a, T> Iterator for RLIterMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
if let Some(index) = self.next {
self.next = self.list.next[index];
Some(&mut self.list.data[index]) // <=== ERROR
} else {
None
}
}
}
which generates error: lifetime may not live long enough since the lifetime of &mut self doesn't equal the expected &'a mut T of the return type. There is also the hidden problem that the compiler can't tell if one or several &mut references to the same items are returned (this error can be seen by using a custom iterator trait to work around the 'a lifetime issue).
For the safety: in my code, both here and in the real project, I'm sure that each item reference is returned only once by the iterator. I can also tell the lifetime of self.list.data is the same as self because I don't drop anything.
Here are the two alternatives I have, to replace the faulty line shown above:
let value: &mut T = &mut self.list.data[index];
// 2 alternatives:
let ptr: &mut T = unsafe {
std::mem::transmute::<&mut T, &'a mut T>(value)
};
let ptr: &mut T = unsafe {
&mut *(value as *mut T)
};
Some(ptr)
The transmute seems the better choice to me since it allows to explicit the lifetime conversion.
It would also be possible to store raw pointers in the iterator, but the idea is the same as the reference cast alternative above: making the lifetime disappear with raw pointers in unsafe code.
Which is better? Is there another, better way to deal with this?
Thanks. 
