Blanket implementation of Iterator for a generic trait

Hello everyone,

I have a simple trait with a type parameter:

pub trait BufferGet<T> {
    fn get(&mut self) -> Option<T>;
}

I want to blanket implement Iterator<Item=T> for all types having this trait:

impl<T, B> Iterator for B
where
    B: BufferGet<T>,
{
    type Item = T;
    // ...
}

This breaks with rustc complaining about T being unconstrained: "error[E0207]: the type parameter T is not constrained by the impl trait, self type, or predicates".

I've read through the error explanation and I kind of understand that even though all of my B type do actually depend on T via the trait, Rust doesn't recognize them as such.

How do I do this?

Playground: Rust Playground

1 Like

Even without the unconstrained T, you can't write a blanket implementation for non-local traits.

Instead, you could have something like struct BufferIter<T, B>, and perhaps add an iter() method in your trait BufferGet to create that iterator.

Even without the unconstrained T , you can't write a blanket implementation for non-local traits.

Oh, I didn't know that, thanks. All my actual B-types are local, so I thought I was good on that. But now I understand there could be a potential conflict.

Instead, you could have something like struct BufferIter<T, B> , and perhaps add an iter() method in your trait BufferGet to create that iterator.

I was going to do that anyway, even if only by convention. I just wanted to play with the idea of direct implementation and didn't understand why it wasn't working.

Thanks!

If you're okay with dynamic dispatch, you could

impl<T> Iterator for dyn BufferGet<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.get()
    }
}

This probably has a similar hit (?):

pub fn as_iter<T, BG: BufferGet<T>>(bg: &mut BG) -> impl Iterator<Item=T> + '_ {
    std::iter::from_fn(move || bg.get())
}

I did glance a dyn variant in the suggestion, yes! But again, I just wanted to understand why the static one didn't want to work.

Thanks for from_fn! I'll probably use that one.

1 Like

I think I can illustrate why you're getting E0207. Consider I create a new type Mog and implement BufferGet<T> with two different types.

struct Mog {}

impl BufferGet<i32> for Mog {
    fn get(&mut self) -> Option<i32> {
        Some(32)
    }
}

impl BufferGet<String> for Mog {
    fn get(mut self) -> Option<String> {
        Some("blah".to_string())
    }
}

Now, the blanket implementation as you currently have:

impl<T, B> Iterator for B
where
    B: BufferGet<T>,
{ // snip....

Will apply to Mog's implementation of BufferGet<i32> and Buffer<String>. Under the hood, when Rust calls a method/function of an implemented trait, it uses the fully qualified syntax of <ConcreteType as Trait>::myfunc(&some_var). In our example, this might look like:

fn main() {
    let m = Mog {}

    // Mog implements both Iterator due to blanket implementation
    <Mog as Iterator>::next(&m); // Error
    /*
        Compiler doesn't know how to choose between:
          - Mog -> BufferGet<i32> -> Iterator
          - Mog -> BufferGet<String> -> Iterator
    */
    println!("Hello, world!");
}

When we try to call next() as defined by the Iterator trait in your blanket implementation, how can the compiler figure out the correct chain of types you want? It can't, so it disallows this particular blanket implementation.

If you want to keep the generic behavior your're looking for, I think @quinedot has good suggestions. Otherwise, you'd have to force your BufferGet trait to implement on one type via an associated type.

Thanks, that's very useful! I had a vague idea that something like this would be happening, but couldn't quite visualize it, so you did it for me :slight_smile:

Otherwise, you'd have to force your BufferGet trait to implement on one type via an associated type.

Which is exactly what I did. This trait returns things from a buffer and it doesn't make sense for it to be implemented for arbitrary types, it has to be the buffer's data type. So now I finally got my lesson on when one would use associated types vs. type parameters.

In fact, until I did that I couldn't implement .iter() returning an iterating wrapper like @cuviper suggested. I kept running into the original error. But with the associated type everything clicked into place more or less naturally.

Here's the actual code if anyone's interested: isagalaev/debounce: src/buffer.rs (lines 36-65, BufferGet renamed Get).

1 Like

Very cool :slight_smile: Out of curiosity, what does the : syntax represent in your Get trait? I tried looking around the Rust Book and wasn't able to find anything regarding it.

/// Common interface for getting events out of debouncing buffers.
pub trait Get: Sized {  // What does Get: Sized mean??

This is a list of requirements for this trait. It says "types implementing this trait must also implement these traits".

I did it because of an error on the method returning an iterator:

fn iter(&mut self) -> BufferIter<Self>

Turns out it implicitly has where Self: Sized (I don't really know why).

So I had to either a) explicitly require my buffer types to be Sized (which they happen to be), or b) explicitly relax this requirement on the BufferIter struct itself, like:

pub struct BufferIter<'a, B: Get + ?Sized>(&'a mut B);

I'm not really sure why I chose one over the other :slight_smile:

1 Like

Here's a similar example of this : syntax from std, where Ord requires its types to also be Eq and PartialOrd:

pub trait Ord: Eq + PartialOrd<Self>

https://doc.rust-lang.org/std/cmp/trait.Ord.html#

1 Like

Type parameters are Sized by default, so B: Get is implicitly B: Get + Sized, whereas traits are ?Sized by default to let them be used as unsized trait objects. So your trait needs an explicit Sized constraint to let it fill the type parameter in BufferIter<Self>.

2 Likes

Do you know why type parameters are Sized by default? From the language design point of view, I mean.

I'm not sure, but my impression is that type parameters have always been Sized, and RFC 546 is what made Self: ?Sized for traits.

1 Like

From the design point of view, if it weren't the default, you'd need an explicit : Sized bound a lot more places. E.g.

  • Taking type parameters by value
  • Returning type parameters by value
  • Having more than one type parameter in a struct
  • Passing on a type parameter to another generic type that requires Sized

Also, adding a Sized bound where there wasn't is a major breaking change, while removing one with ?Sized is a minor change.

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.