Rust iterator generics question, can't compile

Question

I'm trying to use generics for iterators in traits and am having a hard time understanding why it does not compile.

struct B {
    values: Vec<(i64, i64)>,
}

pub trait IterableCustom {
    fn get_iterator<'a, I>(&self) -> I
    where
        I: Iterator<Item = &'a (i64, i64)>;
}

impl IterableCustom for B {
    fn get_iterator<'a, I>(&self) -> I
    where
        I: Iterator<Item = &'a (i64, i64)>,
    {
        let rev = self.values.iter().rev();
        rev
    }
}

It throws an error:

error[E0308]: mismatched types
  --> src/lib.rs:17:9
   |
12 |     fn get_iterator<'a, I>(&self) -> I
   |                         -            - expected `I` because of return type
   |                         |
   |                         this type parameter
...
17 |         rev
   |         ^^^ expected type parameter `I`, found struct `Rev`
   |
   = note: expected type parameter `I`
                      found struct `Rev<std::slice::Iter<'_, (i64, i64)>>`

For more information about this error, try `rustc --explain E0308`.

Playground

The very reason std doesn't provide an `Iterable` trait is because it's impossible to express (stably, easily). — Chayim Friedman, Jun 05 '22 at 21:37
Does this answer your question? [Implementing a trait function that returns generic](https://stackoverflow.com/questions/72271000/implementing-a-trait-function-that-returns-generic) — Chayim Friedman, Jun 05 '22 at 21:37

kotatsuyaki · Answer 1 · 2022-06-05T14:11:21.860

4

The only thing we know about I is that I implements Iterator<Item = &'a (i64, i64)>, so I can be any iterator type satisfying the trait bound. Therefore, the type of rev does not always equal to I.

Without GAT or existential types (which are not in stable Rust yet), currently the best way to rewrite it is to return a boxed trait object.

struct B {
    values: Vec<(i64, i64)>,
}

pub trait IterableCustom {
    fn get_iterator(&self) -> Box<dyn Iterator<Item = &(i64, i64)> + '_>;
}

impl IterableCustom for B {
    fn get_iterator(&self) -> Box<dyn Iterator<Item = &(i64, i64)> + '_> {
        let rev = self.values.iter().rev();
        Box::new(rev)
    }
}

Nightly solutions

With generic associated types, the code can be rewritten as such.

#![feature(generic_associated_types)]

struct B {
    values: Vec<(i64, i64)>,
}

pub trait IterableCustom {
    type Iter<'a>: Iterator<Item = &'a (i64, i64)>
    where
        Self: 'a;
    fn get_iterator<'a>(&'a self) -> Self::Iter<'a>;
}

impl IterableCustom for B {
    type Iter<'a> = std::iter::Rev<std::slice::Iter<'a, (i64, i64)>>;
    fn get_iterator<'a>(&'a self) -> Self::Iter<'a> {
        self.values.iter().rev()
    }
}

With existential types, the overly verbose std::iter::Rev<...> type can be further reduced as such.

type Iter<'a> = impl Iterator<Item = &'a (i64, i64)>
where
    Self: 'a;

edited Jun 05 '22 at 14:11

answered Jun 05 '22 at 13:44

kotatsuyaki

1,441
3
10
17

But Box is generally much slower? The intent was to chain different iterators on each other in very generic way, so basically like a directed graph where we choose values on each .next() and iterator, etc, and each node of graph has its own unique .next(). Maybe there is other way to do it? – tradinggy Jun 05 '22 at 13:54
Yes, boxed trait objects do incur performance loss due to heap allocation. Unfortunately, I don't think we have any better solution than `Box`ing in stable Rust yet. – kotatsuyaki Jun 05 '22 at 14:07
I edited this answer to include nightly solutions. – kotatsuyaki Jun 05 '22 at 14:08
Excellent answers, thanks a lot! What are general downsides - if we switch the whole project for some fixed nightly version now? Does that mean that core Rust and std library might have some bugs and we would only run them in Runtime? – tradinggy Jun 05 '22 at 14:27
My experience with nightly is generally stable enough, but the unstable features (e.g. those used in my answer) may change at anytime. It's not a big problem if a pinned version of nightly is used though. See [this answer to *Using Rust nightly in production*](https://stackoverflow.com/a/56067977/12122460) for more info. – kotatsuyaki Jun 05 '22 at 14:42
Okay, i tried more complex example with ''' fn func(x: i64){ x + 1 } impl IterableCustom for B { type Iter<'a> = impl Iterator where Self: 'a; fn get_iterator<'a>(&'a self) -> Self::Iter<'a> { self.values.iter().rev().map(|values| (values.0, values.1)) } ''' looks like with Map function it is completely impossible now? – tradinggy Jun 05 '22 at 18:01
This is more relevant example , since I iterate over primitives, so dont really need references https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=23252e6c7550d91258f3a7312aa116e8 – tradinggy Jun 05 '22 at 18:10
Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/245343/discussion-between-gleb-yarnykh-and-kotatsuyaki). – tradinggy Jun 05 '22 at 18:13
1

I think you should benchmark the performance hit of using `Box` before making assumptions here. I don't think it's worth switching to nightly just to avoid `Box`. Unless you do heavily performance critical things, I doubt that you will even notice the `Box`. – Finomnis Jun 06 '22 at 09:58
Im actually implementing stuff on 500ns - 10 microseconds level for single run, so yes performance is critical – tradinggy Jun 08 '22 at 15:02

Rust iterator generics question, can't compile

1 Answers1

Nightly solutions