Borrow check error with a boxed iterator (Error E0495)

Hello there!

I'm trying to write a function that takes any iterator and checks for duplicates (the iterators iterate through rows, columns and boxes of a sudoku board). However, I've run into a lifetime error.

Here it is a "minimal" reproduction of the buggy code:

#[derive(Copy, Clone)]
pub struct BoardNum(u8);

impl BoardNum {
    pub fn new (value : u8) -> BoardNum {
        BoardNum(value)
    }

    pub fn value(&self) -> u8 {
        self.0
    } 
}

#[derive(Copy, Clone)]
pub struct Board {
    values : [Option<BoardNum>; 81],
}

impl Board {
    pub fn new() -> Board {
        Board{values : [None; 81]}
    }

    pub fn get(&self, row : usize, column : usize) -> &Option<BoardNum> {
        &self.values[row * 9 + column]
    }

    pub fn row(&self, row : usize) -> Row {
        Row::new(row, &self)
    }

    fn is_valid(&self) -> bool {
        for i in 0..9 {
            if no_duplicate(Box::new(self.row(i))) { //TODO
                    return false;
               } 
        }

        true
    }
}

fn no_duplicate(iter : Box<dyn Iterator<Item = &Option<BoardNum>>>) -> bool {
    let mut value_set = [false; 9];

    for value in iter {
        if let Some(board_num) = value {
            let index = (board_num.value() - 1) as usize;

            if value_set[index] {
                return false; // We have a duplicate!
            } else {
                value_set[index] = true;
            }
        }
    }

    true
}

pub struct Row<'a> {
    row : usize,
    current_column : usize,
    board : &'a Board,
}

impl<'a> Row<'a> {
    pub fn new(row: usize, board: &'a Board) -> Self {
        Self { row, current_column : 0, board }
    }
}

impl<'a> Iterator for Row<'a> {
    type Item = &'a Option<BoardNum>;
    fn next(&mut self) -> Option<Self::Item> {
        if self.current_column != 9 {
            let res = Some(self.board.get(self.row, self.current_column));
            self.current_column += 1;
            res
        } else {
            None
        }
    }
}

And here it is the error that cargo check gives:

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/lib.rs:35:43
   |
35 |             if no_duplicate(Box::new(self.row(i))) { //TODO
   |                                           ^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 33:5...
  --> src/lib.rs:33:5
   |
33 | /     fn is_valid(&self) -> bool {
34 | |         for i in 0..9 {
35 | |             if no_duplicate(Box::new(self.row(i))) { //TODO
36 | |                     return false;
...  |
40 | |         true
41 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/lib.rs:35:38
   |
35 |             if no_duplicate(Box::new(self.row(i))) { //TODO
   |                                      ^^^^
   = note: but, the lifetime must be valid for the static lifetime...
note: ...so that the expression is assignable
  --> src/lib.rs:35:29
   |
35 |             if no_duplicate(Box::new(self.row(i))) { //TODO
   |                             ^^^^^^^^^^^^^^^^^^^^^
   = note: expected `std::boxed::Box<(dyn std::iter::Iterator<Item = &std::option::Option<BoardNum>> + 'static)>`
              found `std::boxed::Box<dyn std::iter::Iterator<Item = &std::option::Option<BoardNum>>>`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0495`.
error: could not compile `sudoku`.

To learn more, run the command again with --verbose.

I have a couple of questions:

  1. Can this be done with a template instead of Box<dyn>?
  2. There is a mention of a static lifetime, which is most likely the problem here. Where does this requirement comes from?
  3. How can I fix the code? :slight_smile:

Thank you for your time!

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=9891e4c926aadc7eea301d4f5b0a9963

Rule of thumb: whenever you have dyn Trait or impl Trait you want to add a + '_ next to it.

By default trait objects introduce an implicit 'static requirement. This means that in practice only owned types that implement the trait will be usable. You flip the inference by using either an unnamed or a named lifetime.

2 Likes

Leaving the answers to my questions here:

  1. This can be (and probably should) done with templates. I'll leave here the function signature I came up with:
fn no_duplicate<'a, T : Iterator<Item = &'a Option<BoardNum>>>(iter : T) -> bool {}
  1. Regarding the static lifetime, see @ekuber's answer (thanks!)

  2. The code can be fixed by adding an unnamed lifetime:

fn no_duplicate(iter : Box<dyn Iterator<Item = &Option<BoardNum>> + '_>) -> bool {}
1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.