Expected std::iter::Iterator, but std::iter::Iterator found

Question

I am trying to express the following:

Given a matrix and two index increments, return all quadruplets of numbers from the matrix: quadruplets of numbers along the rows, or along the columns, or along some diagonal.

use std::iter::Iterator;
use std::iter::Peekable;
use std::ops::Range;

struct Quads<'a> {
   mx: &'a Vec<Vec<u32>>,
   xs: &'a mut Peekable<Range<i32>>,
   ys: &'a mut Peekable<Range<i32>>,
   dx: i32,
   dy: i32,
}

impl<'a> Quads<'a> {
   fn new(mx: &'a Vec<Vec<u32>>, dx: i32, dy: i32) -> Quads<'a> {
      let ys = (if dy < 0 { -3 * dy } else { 0 })..(mx.len() as i32 - if dy > 0 { 4 * dy } else { 0 });
      let xs = 0..0;

      Quads{
         mx: mx,
         xs: &mut xs.peekable(),
         ys: &mut ys.peekable(),
         dx: dx,
         dy: dy,
      }
   }
}

impl<'a> Iterator for Quads<'a> {
   type Item = &'a mut dyn Iterator<Item = u32>;

   fn next(&mut self) -> Option<Self::Item> {
      while self.xs.peek() == None && self.ys.peek() != None {
         self.xs = &mut ((if self.dx < 0 { -3 * self.dx } else { 0 })..
                         (self.mx[0].len() as i32 - if self.dx > 0 { 4 * self.dx } else { 0 }))
                         .peekable();
         self.ys.next();
      }

      let y = self.ys.peek();
      if y == None {
         return None;
      }

      let y = *y.unwrap();
      let x = self.xs.next().unwrap();

      Some(&mut ((x..).step_by(self.dx as usize)
                      .zip((y..).step_by(self.dy as usize))
                     .take(4)
                     .map(|(x,y)| self.mx[y as usize][x as usize])))
   }
}

This produces confusing error messages:

error[E0495]: cannot infer an appropriate lifetime due to conflicting requirements
  --> src/main.rs:52:27
   |
52 |                      .map(|(x,y)| self.mx[y as usize][x as usize])))
   |                           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 33:4...
  --> src/main.rs:33:4
   |
33 | /    fn next(&mut self) -> Option<Self::Item> {
34 | |       while self.xs.peek() == None && self.ys.peek() != None {
35 | |          self.xs = &mut ((if self.dx < 0 { -3 * self.dx } else { 0 })..
36 | |                          (self.mx[0].len() as i32 - if self.dx > 0 { 4 * self.dx } else { 0 }))
...  |
52 | |                      .map(|(x,y)| self.mx[y as usize][x as usize])))
53 | |    }
   | |____^
   = note: ...so that the types are compatible:
           expected &&mut Quads<'a>
              found &&mut Quads<'a>
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 30:6...
  --> src/main.rs:30:6
   |
30 | impl<'a> Iterator for Quads<'a> {
   |      ^^
   = note: ...so that the types are compatible:
           expected std::iter::Iterator
              found std::iter::Iterator

It seems to indicate that it has found the same things it was looking for. So what's wrong?

---

Intended use

Look at https://projecteuler.net/problem=11

Of course, that problem can be solved in more straightforward ways, but I am learning how to express complex things in Rust. So here I am trying to express a Quad that is an Iterator that can extract quadruples of numbers from that Euler problem, where each quadruple is an Iterator itself.

Everything inside Quad represents the state of the Iterator. xs and ys represent the iterators of the coordinates of "the current cell" from which to start the next quadruple. next then tries to see if reached the end of the row, and advances to the next row by reinitialising xs to a new Iterator. When ys reached beyond the last row, we've extracted all the quadruples.

Then something like this:

for q in Quad::new(mx, 1, 0) {  ... process all quadruples along the rows }
for q in Quad::new(mx, 0, 1) {  ... process all quadruples along the columns }
for q in Quad::new(mx, 1, 1) {  ... process all quadruples along one diagonal }
for q in Quad::new(mx, 1, -1) {  ... process all quadruples along the other diagonal }

I think I've got the idea captured, but I don't know what the compiler does not like about it, and consequently how to move forward.

Answer 1

Another solution would be not to export iterators, but pass an operation to run inside.

Answer 2

Ok, so I figured it out. It is really not helpful that rustc produced such a confusing error message - evidently, it found what it was looking for, but still unsatisfied.

There are several problems with the code as posted. My original assumption has been that by marking a reference as mutable I can tell the compiler that whoever receives the reference is responsible for it henceforth, including memory management. Whereas it may be true in some cases (I am not certain; that's still to figure out), it certainly does not work with struct fields (Quad's xs) and return values. In this case we can get rid of &mut in the declaration of the xs and ys:

struct Quads<'a> {
   mx: &'a Vec<Vec<u32>>,
   xs: Peekable<Range<i32>>,
   ys: Peekable<Range<i32>>,
   dx: i32,
   dy: i32,
}

The other problem has been that if it is not a reference, how do you limit the lifetime of a value. (Eg in this case the Iterator returned by next is valid only for as long as the mx)

The other problem has been the expression problem: how do you make next return an Iterator (I don't want to leak what kind of Iterator) so that the compiler is happy. (Eg just dyn Iterator won't do - "size is not known at compile time"). These two are solved by using Box, which can be annotated with a lifetime, too:

impl<'a> Iterator for Quads<'a> {
   type Item = Box<dyn Iterator<Item = u32> + 'a>;

   fn next(&mut self) -> Option<Self::Item> {
      ...
   }
}

The other problem has been that even though the use of mx is read-only, the closure |(x, y)| self.mx[y][x] captures self, which is a mutable reference. That's the easy one: get a local variable, then move:

  let mx = self.mx;
  Some(Box::new(...
          .map(move |(x, y)| mx[y as usize][x as usize])))

Nearly forgot. And the really strange one, which looked fishy even as I typed it originally: step_by takes usize, which is unsigned, and isn't really constructing a Range that enumerates values by adding a given increment; rather it constructs an Iterator that skips a given number of elements (pretty much). So, a tuple iterator is needed:

struct Tup<T> {
   x: (T, T),
   d: (T, T),
}
...
impl<T: AddAssign + Copy> Iterator for Tup<T> {
   type Item = (T, T);
   fn next(&mut self) -> Option<(T, T)> {
      self.x.0 += self.d.0;
      self.x.1 += self.d.1;
      Some(self.x)
   }
}

So instead of zipping two Iterators with step_by, you get a Tup initialised with known initial values and deltas:

  Some(Box::new(Tup::new((x, y), (self.dx, self.dy))
                     .take(4)
                     .map(move |(x, y)| mx[y as usize][x as usize])))