Implementing a trait function that returns generic

Question

In the following code, the trait called LimitCollection has a function that returns a type that implements Iterator trait.

struct Limit {}

impl Limit {
    fn is_violated(&self) -> bool {
        todo!()
    }
}

trait LimitCollection {
    fn get_violated_limits<'a, I>(&'a self) -> I
    where
        I: Iterator<Item = &'a Limit>;
}

Now I'd like to make something that implements the trait but the compiler complains that there is mismatch between the type that I return and the generic return type: "expected type parameter I, found struct Filter"

struct ConcreteLimitCollection {
    limits: Vec<Limit>,
}

impl LimitCollection for ConcreteLimitCollection {
    fn get_violated_limits<'a, I>(&'a self) -> I
    where
        I: Iterator<Item = &'a Limit>,
    {
        self.limits.iter().filter(Limit::is_violated)
    }
}

Is there any way to make this construct work, preferably without resorting to dynamic allocation?

Netwave · Accepted Answer · 2022-05-17T14:43:47.430

4

Usually you would use an associated type , in this case we would have some lifetimes involved (we need a GAT, generic associated type). Sadly what it is needed is not stabilized yet:

#![feature(generic_associated_types)]

struct Limit {}

impl Limit {
    fn is_violated(&self) -> bool {
        todo!()
    }
}

trait LimitCollection {
    type Output<'a>: Iterator<Item = &'a Limit> where Self: 'a;
    fn get_violated_limits<'a>(&'a self) -> Self::Output<'a>;
}

struct ConcreteLimitCollection {
    limits: Vec<Limit>,
}

impl LimitCollection for ConcreteLimitCollection {
    type Output<'a> = Box<dyn Iterator<Item = &'a Limit> + 'a> where Self: 'a;
    
    fn get_violated_limits<'a>(&'a self) -> Self::Output<'a> {
        Box::new(self.limits.iter().filter(|l| l.is_violated()))
    }
}

Playground

Disclaimer, I used Box<dyn Iterator<Item = &'a Limit> + 'a> even if you did not wanted to use dinamic allocation, but in this case you would just have to fulfill the whole Filter<...> type. Just did used a Boxed iterator for the example simplicity.

@SvenMarnach fitted the types :

impl LimitCollection for ConcreteLimitCollection {
    type Output<'a> = std::iter::Filter<std::slice::Iter<'a, Limit>, fn(&&Limit) -> bool>;
    
    fn get_violated_limits<'a>(&'a self) -> Self::Output<'a> {
        self.limits.iter().filter(|l| l.is_violated())
    }
}

Playground

edited May 17 '22 at 14:43

answered May 17 '22 at 09:09

Netwave

40,134
6
50
93

I don't think it's possible to fully specify the type in this case. – Sven Marnach May 17 '22 at 09:56
@SvenMarnach, yeah, it would be complicated and convoluted saying the least. – Netwave May 17 '22 at 10:30
It's not actually that complicated – I think the type could be described as `Filter, fn(&Limit) -> bool>` – but I think you will hit some limit of the type system here. – Sven Marnach May 17 '22 at 11:25
@SvenMarnach, yes, would need some lifetimes magic fit, not sure how to do it actually: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=5b49f85eacfa377937c3bfe8cd02e1a9 – Netwave May 17 '22 at 11:30
The `'a` lifetime is definitely wrong for the function parameter. It should be `for<'r> fn(&'r Limit) -> bool`, which is actually the same as `fn(&Limit) -> bool` due to lifetime elision rules. However, that doesn't compile either, which may be due to one of the remaining bugs in GATs. – Sven Marnach May 17 '22 at 11:33
@Netwave given the current limitations that you mention, would it be a sound design decision to implement get_violated_limits as function returning vector or a function taking closure that would be called for each violated limit? Would such design be considered idiomatic? – kyku May 17 '22 at 12:19
@kyku I would use the dynamic dispatch in this case, sincerely. It would depend the case, but you could also create a wrapper over the vector, and implement the filtering over that, no trait ofc. – Netwave May 17 '22 at 12:29
1

@SvenMarnach This is not a GAT problem, just that `filter()`'s callback takes `&Self::Item` and `Self::Item` is `&Limit`, so two references. The fully-specified type is `for<'b> fn(&'b &'a Limit) -> bool`. https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=9a4bfa8dba04d14d248fead0d381df42. Of course, this uses a function pointer; the real type is a closure and needs TAIT. – Chayim Friedman May 17 '22 at 13:45
1

@ChayimFriedman Indeed, this is just a double reference. The closure does not capture anything, so it coerces to a function pointer. Using `fn(&&Limit) -> bool`, this actully [works just fine](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=0fe930100ee33ea2ebc7bed3266602da). – Sven Marnach May 17 '22 at 14:41
@SvenMarnach I added your example :) – Netwave May 17 '22 at 14:44
I know it coerces, it is just not the most performant (though it'll be 99% de-virtualized). It is interesting that it doesn't require `fn(&&'a Limit) -> bool`, though. – Chayim Friedman May 17 '22 at 14:46

score 2 · Answer 2 · answered May 17 '22 at 09:11

Is there any way to make this construct work, preferably without resorting to dynamic allocation?

A generic type means the caller decides what the type is, because I (the type) is an input parameter so the caller should be able to pass in whatever they want as long as it fulfills the constraints.

But that's not the case here, you give the caller no choice.

The way to give the caller no choice, but to give the trait implementer a choice is an associated type.

Sadly as Netwave notes, here this requires a generic associated type (as Iterator is generic over the 'a lifetime), and GATs are not stable.

Two ways around that are to parameterize the trait itself, and to implement the trait for a reference rather than the type. https://stackoverflow.com/a/33756123/8182118 has examples and discussions of the possibilities.

Implementing a trait function that returns generic

2 Answers2

Linked