Implementing iterator-like trait for borrowed collection with named lifetime

[simpson.eric]

I tried to cut out a bunch of code to provide a minimal (non)-working example below.

The basic background is:

• I have a borrowed slice that I'm treating as a circular buffer view
• I'm attempting to implement nom's InputIter trait for this struct, but cannot figure out the correct way to specify lifetimes.

impl<'a> RingReader<'a> {

    /// Returns the number of elements currently in the ring.
    pub fn len(&self) -> usize {
        if self.wr < self.rd {
            self.wr + self.buffer.len() - self.rd
        } else {
            self.wr - self.rd
        }
    }

    pub fn get(&self, index: usize) -> u8 {
        let pos = (self.rd + index) % (self.buffer.len());
        self.buffer[pos]
    }

    pub fn iter(&self) -> RingIter {
        RingIter {
            rb: self,
            cur: 0,
            end: self.len(),
        }
    }
}
/// Used as reader view into a circular buffer
pub struct RingReader<'a> {
    buffer: &'a [u8],
    pub rd: usize,
    pub wr: usize,
}

pub struct RingIter<'a> {
    rb: &'a RingReader<'a>,
    cur: usize,
    end: usize,
}

impl Iterator for RingIter<'_> {
    type Item = u8;

    fn next(&mut self) -> Option<Self::Item> {
        if self.cur == self.end {
            None
        } else {
            let v = self.rb.get(self.cur);
            self.cur += 1;
            Some(v)
        }
    }
}

/// XXX this is actually from the `nom::InputIter` crate
/// - importing here just to make it work on the playground
pub trait InputIter {
  /// Example: `u8` for `&[u8]` or `char` for `&str`
  type Item;
  type IterElem: Iterator<Item = Self::Item>;

  fn iter_elements(&self) -> Self::IterElem;
}

impl<'a> InputIter for RingReader<'a> {
    type Item = u8;
    type IterElem = RingIter<'a>;

    fn iter_elements(&self) -> RingIter<'a> {
        // TODO: How do I define the lifetime's here?
        // - &self is anonymous lifetime?
        let ri = RingIter {
            rb: self,
            cur: 0,
            end: self.len(),
        };
        ri
    }
}

fn main() {
    let buf = [0, 1, 2, 3];
    let ring = RingReader {
        buffer: &buf[..],
        rd: 0,
        wr: 4,
    };

    // This is OK
    for i in ring.iter() {
        println!("got: {:?}", i);
    }
    
    println!("Hello, world!");
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0495]: cannot infer an appropriate lifetime for lifetime parameter `'a` due to conflicting requirements
  --> src/main.rs:73:18
   |
73 |         let ri = RingIter {
   |                  ^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime defined on the method body at 70:22...
  --> src/main.rs:70:22
   |
70 |     fn iter_elements(&self) -> RingIter<'a> {
   |                      ^^^^^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:74:17
   |
74 |             rb: self,
   |                 ^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 66:6...
  --> src/main.rs:66:6
   |
66 | impl<'a> InputIter for RingReader<'a> {
   |      ^^
note: ...so that the expression is assignable
  --> src/main.rs:78:9
   |
78 |         ri
   |         ^^
   = note: expected `RingIter<'a>`
              found `RingIter<'_>`

For more information about this error, try `rustc --explain E0495`.
error: could not compile `playground` due to previous error

[drewkett]

@simpson.eric

impl<'a> InputIter for RingReader<'a>

For this case, the following works

impl<'a> InputIter for &'a RingReader<'a> {
…
}

[simpson.eric]

Fantastic, thanks @drewkett .

To understand why this works, is it with regards to the line below:

@simpson.eric

    fn iter_elements(&self) -> RingIter<'a> {

Does this mean for the &self in iter_elements() this must be a reference whose lifetime is 'a ?

[H2CO3]

Yes, because lifetime elision rules are constructed such that a method taking &self will have all of the unspecified lifetimes in its return type be inferred to the lifetime of Self. Of course, &self isn't guaranteed to live for an arbitrary generic lifetime 'a. If, however, self is itself an &'a Something, then it must live at least as long as 'a.

[simpson.eric]

Makes sense.

As a follow-up, is it even possible to implement the trait for the original non-reference type?

impl<'a> InputIter for RingReader<'a> { .. }

[H2CO3]

To be perfectly honest, I couldn't figure it out even if it is possible. The problem is that you somehow want to tie the lifetime parameter inside the RingIter to the lifetime of &self, but AFAIK there's no way to do that in an associated type declaration.

Why don't you simply make RingIter implement Copy and store it by value? You don't need that extra layer of indirection anyway. All you care about is the lifetime of the underlying slice/buffer, the rest is only making your life artificially difficult. Just pass it by value instead.

[simpson.eric]

I'm not able to select two solutions, but both approaches have been valuable for me.

1. Changing the trait impl to be on a named lifetime as specified by @drewkett

impl<'a> InputIter for &'a RingReader<'a> { .. }

2. Changing the InputIter to take the RingReader<'a> by value rather than reference. This was suggested by @H2CO3 above. To me, the important parts were below:

pub struct RingIter<'a> {
    rb: RingReader<'a>,  // <-- THIS CHANGED TO BY VALUE
    cur: usize,
    end: usize,
}

...
impl<'a> InputIter for RingReader<'a> {
    type Item = u8;
    type IterElem = RingIter<'a>;

    fn iter_elements(&self) -> RingIter<'a> {
        RingIter {
            rb: *self, // <-- NOTE the explicit dereference
            cur: 0,
            end: self.len(),
        }
    }
}

Thanks All.

[drewkett]

Just to follow up. @H2CO3's solution is the better one and more idiomatic. Generally, it's best to avoid references in structs unless you're sure you need them. For data structures that aren't that big that are safe to copy, it's almost always better to just go ahead and store a copy since it probably won't be any slower and it will save a lot of potential trouble with annotating lifetimes.

In your case, you have another lifetime in there, which happens, but the second lifetime due to the reference is not necessary.