Higher-rank trait bounds (HRTBs) with "outer" generic type parameter

help
1

I will start from afar…

Let's assume we have a producer-like trait:

trait Producer {
    type Product;
    fn produce(&self) -> Self::Product;
}

(in the actual code the trait is more complex, with more parameters in product and restrictions on Product, but let's keep it as simple as possible).

And we want to make a mapping adapter (that applies a certain mapping function to the products of a certain base producer and so satisfies Producer):

// Pseudocode:
fn …(base: impl Producer, mapper: impl Fn(…) -> …) -> impl Producer {…}

That's easy to implement:

struct MappingAdapter<
    Base: Producer,
    Mapper: Fn(Base::Product) -> FinalProduct,
    FinalProduct
> {base: Base, mapper: Mapper}
impl<
    Base: Producer,
    Mapper: Fn(Base::Product) -> FinalProduct,
    FinalProduct
> Producer for MappingAdapter<Base, Mapper, FinalProduct> {
    type Product = FinalProduct;
    fn produce(&self) -> Self::Product {(self.mapper)(self.base.produce())}
}

Let's test it:

#[test]
fn test() {
    struct CopyingProducer {gold: usize}
    impl Producer for CopyingProducer {
        type Product = usize;
        fn produce(&self) -> usize {self.gold}
    }

    let adapted_producer = MappingAdapter{
        base: CopyingProducer{gold: 42},
        mapper: |v|(v, v)
    };
    assert_eq!(adapted_producer.produce(), (42, 42))
}

But here's where the question becomes slightly more tricky. What if we want the products of our producer to be possibly dependent on it (e.g. if the producer contains some golden value and references to it are the products)? It's easy to update the Producer trait:

trait Producer {
    type Product<'a> where Self: 'a;
    fn produce<'a>(&'a self) -> Self::Product<'a>;
}

Also, at first glance, it seams to be easy to update the MappingAdaptor:

struct MappingAdapter<
    Base: Producer,
    Mapper: Fn(Base::Product<'_>) -> FinalProduct,
    FinalProduct
> {base: Base, mapper: Mapper}
impl<
    Base: Producer,
    Mapper: Fn(Base::Product<'_>) -> FinalProduct,
    FinalProduct
> Producer for MappingAdapter<Base, Mapper, FinalProduct> {
    type Product<'a> = FinalProduct where Self: 'a;
    fn produce<'a>(&'a self) -> Self::Product<'a> {
        (self.mapper)(self.base.produce())
    }
}

But actual test won't work:

#[test]
fn test() {
    struct Obj {}
    struct ReferencingProducer {gold: Obj}
    impl Producer for ReferencingProducer {
        type Product<'a> = &'a Obj where Self: 'a;
        fn produce<'a>(&'a self) -> &'a Obj {&self.gold}
    }

    fn pair<'a>(value: &'a Obj) -> (&'a Obj, &'a Obj) {(value, value)}
    let adapted_producer = MappingAdapter{
        base: ReferencingProducer{gold: Obj{}},
        mapper: pair
    };
    assert_eq!(
        adapted_producer.produce(),
        //               ^^^^^^^ method cannot be called
        //                       due to unsatisfied trait bounds
        // trait bound `<for<'a> fn(&'a Obj) -> (&'a Obj, &'a Obj) {pair}
        // as FnOnce<(&Obj,)>>::Output = (&Obj, &Obj)` was not satisfied
        (&adapted_producer.base.gold, &adapted_producer.base.gold)
    )
}

If I understand correctly, that's because Mapper: Fn(Base::Product<'_>) -> FinalProduct, which is a shorthand for Mapper: for <'t> Fn(Base::Product<'t>) -> FinalProduct, is able to represent only functions like <'a>(&'a usize) -> usize but not like <'a>(&'a usize) -> &'a usize. I would write something like

Mapper: for <'t> Fn(Base::Product<'t>) -> FinalProduct where FinalProduct: 't,
//                                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

but that syntax is simply not allowed. Any ideas?

2

This is the same problem as there used to be for Fn() -> F: Future, and for that the answer was to wrap the Fn in a trait that can describe the output type:

1 Like
3

Do you mean like this:

trait ProducerProductMapper<P: Producer> {
    type MappedProduct<'a> where Self: 'a, P: 'a;
    fn map<'a>(&self, product: P::Product<'a>) -> Self::MappedProduct<'a>;
}

struct MappingAdapter<
    Base: Producer,
    Mapper: ProducerProductMapper<Base>
> {base: Base, mapper: Mapper}
impl<
    Base: Producer,
    Mapper: ProducerProductMapper<Base>
> Producer for MappingAdapter<Base, Mapper> {
    type Product<'a> = Mapper::MappedProduct<'a> where Self: 'a;
    fn produce<'a>(&'a self) -> Self::Product<'a> {
        self.mapper.map(self.base.produce())
    }
}

?

I hoped I could avoid it.

But thanks anyway.

4

Ah, sorry, I probably have understood your answer only now. You mean to write an own trait that has Fn(…) -> … as a supertrait, right?

But, to be honest, I don't understand how it would help. In your case, you have a requirement that the result type must be a Future. In my case, I have only a lifetime requirement for the result (it should be allowed to outlive the argument). Can you elaborate, please?

5

Definition like this lets you write for<'a> AsyncFn<Output = Type<'a>> that otherwise would be syntactically impossible if you had to write Output: Type<'a> as a separate trait bound.

I'm suggesting to copy that definition, but replace Future with your custom trait that you want.

6

But, technically, in the MappingAdapter I assume I should have, there's no FinalProduct<'a> (only FinalProduct). Though, maybe you suggest would a better definition for MappingAdapter (where FinalProduct<'a> would be available)?

But I don't expect the output to be any custom trait (at least not a one with <'a> parameter).

My goal is just to have MappingAdapter definition that would allow to do pass a fn f<'a>(v: &'a str) -> &'a str {v}-like function as mapper (not only a fn f<'a>(v: &'a str) -> String {v.to_owned()}-like one).

7

Maybe this could work for you:

trait ProductMapper<'a, P: Producer + 'a, Guard = &'a P>: Fn(P::Product<'a>) -> <Self as ProductMapper<'a, P, Guard>>::Output {
    type Output;
}
impl<'a, P: Producer, R, F: ?Sized + Fn(P::Product<'a>) -> R> ProductMapper<'a, P> for F {
    type Output = R;
}

and then you can:

struct MappingAdapter<
    Base: Producer,
    Mapper: for<'a> ProductMapper<'a, Base>,
> {base: Base, mapper: Mapper}
impl<
    Base: Producer,
    Mapper: for<'a> ProductMapper<'a, Base>,
> Producer for MappingAdapter<Base, Mapper> {
    type Product<'a> = <Mapper as ProductMapper<'a, Base>>::Output where Base: 'a, Mapper: 'a;
    fn produce<'a>(&'a self) -> Self::Product<'a> {
        (self.mapper)(self.base.produce())
    }
}

then your test works almost unmodified (I only added the #[derive(...)])

#[test]
fn test() {
    #[derive(PartialEq, Debug)]  // this is the only line I added
    struct Obj {}
    struct ReferencingProducer {gold: Obj}
    impl Producer for ReferencingProducer {
        type Product<'a> = &'a Obj where Self: 'a;
        fn produce<'a>(&'a self) -> &'a Obj {&self.gold}
    }

    fn pair<'a>(value: &'a Obj) -> (&'a Obj, &'a Obj) {(value, value)}
    let adapted_producer = MappingAdapter{
        base: ReferencingProducer{gold: Obj{}},
        mapper: pair
    };
    assert_eq!(
        adapted_producer.produce(),
        //               ^^^^^^^ method cannot be called
        //                       due to unsatisfied trait bounds
        // trait bound `<for<'a> fn(&'a Obj) -> (&'a Obj, &'a Obj) {pair}
        // as FnOnce<(&Obj,)>>::Output = (&Obj, &Obj)` was not satisfied
        (&adapted_producer.base.gold, &adapted_producer.base.gold)
    )
}

The ProductMapper trait allows you to move the function return type to associated type position where it can depend on lifetime. The Guard parameter is there to work around the lack of constrained HRTBs. Then you can properly formulate the HRTBs on impl Producer for MappingAdapter and you can use it with "normal" functions and closures directly.

1 Like
8

Thanks, that's great!

(Starting from some point, I pessimistically assumed that nothing except ProductMapper trait for explicit implementation is really possible in Rust for now. Despite your way is maybe not so elegant as I initially wanted (the perfect way would be probably to have ProductMapper not being aware of the Producer trait at all, i.e. when ProductMapper would deal purely with products), but it's a good compromise between the trait-for-explicit-implementation way (that I wanted to avoid) and the perfect way (impossible in Rust for now). Kornel probably was suggesting something like that, but I was unable to understand his answer without additional details.)

Thanks again.

9

Well, now that you mention it, I thought this wouldn't work, but apparently it does: [1]

trait MapperFn<P>: Fn(P) -> <Self as MapperFn<P>>::Output {
    type Output;
}
impl<P, R, F: ?Sized + Fn(P) -> R> MapperFn<P> for F {
    type Output = R;
}

struct MappingAdapter<
    Base: Producer,
    Mapper: for<'a> MapperFn<Base::Product<'a>>,
> {base: Base, mapper: Mapper}
impl<
    Base: Producer,
    Mapper: for<'a> MapperFn<Base::Product<'a>>,
> Producer for MappingAdapter<Base, Mapper> {
    type Product<'a> = <Mapper as MapperFn<Base::Product<'a>>>::Output where Base: 'a, Mapper: 'a;
    fn produce<'a>(&'a self) -> Self::Product<'a> {
        (self.mapper)(self.base.produce())
    }
}

So only extracting the function return type to associated type position was needed. Or maybe I am missing something and it is not that easy. Anyway it worked with your test, so you may want to try this too.

Ok, now I see the problem. This, as well as my previous approach work well as long as your producers are 'static, i.e. do not contain references (or other forms of borrows). [2] Otherwise it won't and you will need more magic (likely everything in the article I linked, as your Producer trait is almost the same as lending iterator).

Aaaand as I could not get it out of my head, here is an example of failing borrowing producer (same thing happens with my previous approach):

and here is a working example with modified Producer trait:

  1. I renamed the trait to MapperFn as now it has nothing to do with products, producers or anything ↩︎

  2. And in that case my previous approach seems overcomplicated, the Guard parameter does nothing. ↩︎