0

I have a struct (Lines) containing a vec of Coordinates. I'm trying to implement a non-consuming mutable iterator over non-overlapping sub-slices into this vector as &mut [Coordinate]. Each sub-slice would represent 1 line stored in Lines. -edit: Additionally the lists of indices may be reordered without the vertices being moved. As such the lines in vertices cannot be assumed to be in the same order as the indices.

The implementation works for the immutable iterator (same implementation as below, but without muts)

https://play.rust-lang.org/?version=stable&mode=debug&edition=2015&gist=dc03530c82e8113ea532e5345dda4142

use std::ops::{Index, IndexMut};

#[derive(Debug)]
pub struct Coordinate {
    x: u32,
    y: u32,
}

/// SOA containing multiple line geometries
/// All coordinates of all the lines are stored contiguously in vertices
/// start_indices & end_indices both contain 1 entry for every geometry
#[derive(Debug)]
struct Lines {
    vertices: Vec<Coordinate>, 
    start_indices: Vec<usize>,
    end_indices: Vec<usize>,
}
impl Lines {
    pub fn len(&self) -> usize {
        self.start_indices.len()
    }
    fn iter_mut(&mut self) -> LinesIterMut {
        LinesIterMut {
            lines: self,
            next_index: 0,
        }
    }
}

impl Index<usize> for Lines {
    type Output = [Coordinate];

    fn index(&self, index: usize) -> &Self::Output {
        &self.vertices[self.start_indices[index]..self.end_indices[index]]
    }
}
impl IndexMut<usize> for Lines {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        &mut self.vertices[self.start_indices[index]..self.end_indices[index]]
    }
}

pub struct LinesIterMut<'a> {
    lines: &'a mut Lines,
    next_index: usize,
}
impl<'a> Iterator for LinesIterMut<'a> {
    type Item = &'a mut [Coordinate];

    fn next(&mut self) -> Option<Self::Item> {
        if self.next_index < self.lines.len() {
            let current_index = self.next_index;
            self.next_index += 1;
            Some(&mut self.lines[current_index])
        } else {
            None
        }
    }
}

fn main() {
    let mut my_lines = Lines {
        vertices: vec![
            Coordinate {
                x: 1,
                y: 2,
            },
            Coordinate {
                x: 4,
                y: 5,
            },
        ],
        start_indices: vec![0],
        end_indices: vec![2],
    };

    for line in my_lines.iter_mut() {
        line[0].y = 33;
        println!("=> {:?}", line);
    }
}

I get the following lifetime error:

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
  --> src/main.rs:54:23
   |
54 |             Some(&mut self.lines[current_index])
   |                       ^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 50:5...
  --> src/main.rs:50:5
   |
50 |     fn next(&mut self) -> Option<Self::Item> {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:54:23
   |
54 |             Some(&mut self.lines[current_index])
   |                       ^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 47:6...
  --> src/main.rs:47:6
   |
47 | impl<'a> Iterator for LinesIterMut<'a> {
   |      ^^
note: ...so that the types are compatible
  --> src/main.rs:50:46
   |
50 |       fn next(&mut self) -> Option<Self::Item> {
   |  ______________________________________________^
51 | |         if self.next_index < self.lines.len() {
52 | |             let current_index = self.next_index;
53 | |             self.next_index += 1;
...  |
57 | |         }
58 | |     }
   | |_____^
   = note: expected `Iterator`
              found `Iterator`

How do I tell the compiler that the lifetime of the reference is related to Lines?

-edit: Using the link provided by @kmdreko : https://stackoverflow.com/a/60072822/13138916 I wrote this. It works, but is this safe? How can I tell?

pub struct LinesIterMut<'a> {
    lines: &'a mut Lines,
    next_index: usize,
}
impl<'a> Iterator for LinesIterMut<'a> {
    type Item = &'a mut [Coordinate];

    fn next(&mut self) -> Option<Self::Item> {
        if self.next_index < self.lines.len() {
            let current_index = self.next_index;
            self.next_index += 1;
            Some(unsafe { std::mem::transmute(&mut self.lines[current_index]) }) // <<--- Only changed this line
        } else {
            None
        }
    }
}
  • 2
    Does this answer your question? [How can I create my own data structure with an iterator that returns mutable references?](https://stackoverflow.com/questions/25730586/how-can-i-create-my-own-data-structure-with-an-iterator-that-returns-mutable-ref) or this? [How to implement Iterator yielding mutable references](https://stackoverflow.com/questions/60072498/how-to-implement-iterator-yielding-mutable-references) – kmdreko Feb 09 '21 at 05:46
  • Note that your `Lines` struct is not an SOA. An SOA would be: `struct Lines { xs: Vec, ys: Vec, /*...*/ }`. – Jmb Feb 09 '21 at 07:43
  • Hmm hard to say. If I understand it correctly then the first URL says: "Use an old library, or write custom iterator type, or use unsafe", but does not really specify how. The second URL provides some unsafe implementations for a slightly different problem. But it is hard for me to say whether or not this has UB, especially after I adapt it to my problem. (It doesn't use the PhantomData as suggested it should be the 1st URL for example) So they are useful links, but do no solve my problem directly. I have to look into it more. – Sjors Donkers Feb 09 '21 at 07:44
  • @Jmb Yes, I am aware :) It is part of a bigger thing – Sjors Donkers Feb 09 '21 at 07:45
  • @kmdreko I added an implementation that works. If we assume for a moment that Lines is always constructed properly. Is `Some(unsafe { std::mem::transmute(&mut self.lines[current_index]) })` a safe solution? – Sjors Donkers Feb 09 '21 at 08:06
  • 1
    The first link basically says "you cannot create an iterator over mutable references without unsafe because the compiler is unable to enforce that all results are exclusive". If you can uphold that guarantee, then you can use `std::mem::transmute` to force the lifetimes to match. I can't say for certain since your code looks incomplete; its lacking formal creation and modification methods. If these methods are implemented without this guarantee in mind, the iterator implementation would be unsound. – kmdreko Feb 09 '21 at 08:13
  • OK, thanks! I will be able to guarantee that no data is referenced twice with the missing code. So I'll stick with this solution and add a bunch of tests. – Sjors Donkers Feb 09 '21 at 08:22
  • You can [use `split_at_mut` to implement mutable iterators that are based on slices](/q/62361624/3650362), although it can be a bit awkward. [Here's a non-`unsafe` version of `LinesIterMut`](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=06f72b796a35982e176eba3464d5120a) based on my understanding of what you're doing. – trent Feb 09 '21 at 17:11
  • @trentcl Thanks for the sample code! I'll adopt some of the ideas into my code. However, one previously unmentioned requirement is that the indices can be reordered without reordering the lines in vertices. That means we cannot assume the lines are next to each other in memory, they maybe in a random order `let (head, tail) = vertices.split_at_mut(len);` `self.vertices = &mut tail[next_start..];` would not work for me as the next line is not always the new head. I've added now added the requirement to the question. – Sjors Donkers Feb 10 '21 at 01:05

0 Answers0