API design and HKT limitations?

I am trying to design a future adapter, which would take Fn() -> Future<Output=Result> and retry it.
Simple way to do it is plain function, which consumes future generator and produces a future:

impl<FF,F1,F2,R,E1,E2> WithRetry<F2> for FF
    where
        FF: Fn() -> F1,
        FF::Output: Future<Output=Result<R,E1>>,
        F1: Future<Output=Result<R,E1>>,
        F2: Future<Output=Result<R,E2>>,
        E1: ShouldRetry + std::fmt::Debug,
{
    fn with_retry(self, delay: Duration) -> Retry<F2> {
        let f = async {
            loop {
                match self().await {
                    Ok(res) => return Ok(res),
                    Err(e) => match e.should_retry() {
                        true => {
                            debug!("Error, will retry: {:?}", e);
                            tokio::time::sleep(delay).await;
                            continue;
                        }
                        false => return Err(e),
                    }
                }
            }
        };

        Retry(f)
    }
}

Then calling the function in the code, like this:

with_retry(Duration::from_secs(1), (|| async {
   ...
   Ok(result)
}))

Note: the problem I am trying to solve has more to do with education than practical limitations, so I am just trying to understand WHY and not so much HOW.
For ergonomic considerations I want it to be like this:

(|| async {
   ...
   Ok(res)
}).with_retry(Duration::from_secs(1))

The design of this API is called "adapter" can be seen in many places in Rust and consists of introducing a struct, a trait and implementation of trait which links desired type (future generator) to the struct. Then you implement Future for the struct as an adapter. But I am having problem with implementing link between my trait and structure:

pub struct Retry<FF>(FF);

pub trait WithRetry<F> {
    fn with_retry(self, delay: Duration) -> Retry<F>;
}

impl<FF,F1,F2,R,E1,E2> WithRetry<F2> for FF
    where
        FF: Fn() -> F1,
        FF::Output: Future<Output=Result<R,E1>>,
        F1: Future<Output=Result<R,E1>>,
        F2: Future<Output=Result<R,E2>>,
        E1: ShouldRetry + std::fmt::Debug,
{
    fn with_retry(self, delay: Duration) -> Retry<F2> {
        let f = async {
            todo!()
        };

        Retry(f)
    }
}
error[E0308]: mismatched types
  --> src/retry_policy.rs:73:15
   |
48 |   impl<FF,F1,F2,R,E1,E2> WithRetry<F2> for FF
   |              -- this type parameter
...
57 |           let f = async {
   |  _______________________-
58 | |             loop {
59 | |                 match self().await {
60 | |                     Ok(res) => return Ok(res),
...  |
70 | |             }
71 | |         };
   | |_________- the found `async` block
72 | 
73 |           Retry(f)
   |                 ^ expected type parameter `F2`, found opaque type
   | 
  ::: /home/vadym/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/future/mod.rs:61:43
   |
61 |   pub const fn from_generator<T>(gen: T) -> impl Future<Output = T::Return>
   |                                             ------------------------------- the found opaque type
   |
   = note: expected type parameter `F2`
                 found opaque type `impl futures::Future`
   = help: type parameters must be constrained to match other types
   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters

While trying to solve this, I have read rfc-1522
"https://github.com/rust-lang/rfcs/blob/master/text/1522-conservative-impl-trait.md"

However, there is an issue with this, namely that in combinations with generic trait methods, they are effectively equivalent to higher kinded types. Which is an issue because Rust's HKT story is not yet figured out, so any "accidental implementation" might cause unintended fallout.

I start suspecting that I am hitting this exactly limitation. My intuition is as follow: When Rust generics are evaluated, today's rustc requires all generic type to be defined and resolved to concrete types (no traits) by the type caller. Now, because of async, I use and return an anonymous type, and even more, this type is not a concrete but "something that implements Future". Today it is only possible to define "something that implements Trait" via type params and factual type of params must be defined by the caller. Which spells doom on my attempt to build such API because I am trying to build a concrete type in implementation.

Am I right that I am hitting HKT limitations of today's rust?

P.S. Perhaps another way to still achieve desired API would be to use Box<dyn Future<Output=Result<R,E>>? This way no concrete type is generated inside my implementation and R and E are supplied by the type caller?

First of all, a Playground repro for us to toy with.

Note that, as you mentioned, with a simple function the whole problem is simpler, so we can start from there and try to move it to the trait realm:

  1. async fn with_retry<F, Fut, Ok, Err> (
        f: F,
        delay: Duration,
    ) -> Result<Ok, Err>
    where
        F : FnMut() -> Fut,
        Fut : Future<Output = Result<Ok, Err>>,
        Err : ShouldRetry,
    {
        /* body */
    }
    
  2. Now let's unsugar the async out of the function's signature

    fn with_retry<'async_fut, F, Fut, Ok, Err> (
        f: F,
        delay: Duration,
    ) -> impl 'async_fut + Future<Output =
            Result<Ok, Err>
        >
    where
        F : FnMut() -> Fut,
        Fut : Future<Output = Result<Ok, Err>>,
        Err : ShouldRetry,
        F : 'async_fut,
     // Duration : 'async_fut,
    {
        async move {
            let _ = (&f, &delay); // ensure the params are captured by the future.
            /* body */
        }
    }
    
  3. Now let's transform that into a hypothetical inherent method:

    impl F {
        fn with_retry<'async_fut, Fut, Ok, Err> (
            self: Self,
            delay: Duration,
        ) -> impl 'async_fut + Future<Output =
                Result<Ok, Err>
            >
        where
            Self : FnMut() -> Fut,
            Fut : Future<Output = Result<Ok, Err>>,
            Err : ShouldRetry,
            Self : 'async_fut,
        {
            let f = self; // rename.
            async move {
                let _ = (&f, &delay); // ensure the params are captured by the future.
                /* body */
            }
        }
    }
    
  4. Now make a trait out of it + the following impl:

    impl<F> WithRetry for F {}
    trait WithRetry : Sized {
        fn with_retry<'async_fut, Fut, Ok, Err> (
            self: Self,
            delay: Duration,
        ) -> impl 'async_fut + Future<Output =
                Result<Ok, Err>
            >
        where
            Self : FnMut() -> Fut,
            Fut : Future<Output = Result<Ok, Err>>,
            Err : ShouldRetry,
            Self : 'async_fut,
        {
            let f = self; // rename.
            async move {
                let _ = (&f, &delay); // ensure the params are captured by the future.
                /* body */
            }
        }
    }
    

Ideally, at this point, you'd be having something that works, except that -> impl Trait for traits is not supported yet on stable Rust.


At this point, you have two options:

  • Replace impl with dyn and add any necessary pointer indirection

    impl<F> WithRetry for F {}
    trait WithRetry : Sized {
        fn with_retry<'async_fut, Fut, Ok, Err> (
            self: Self,
            delay: Duration,
    -   ) -> impl 'async_fut + Future<Output =
    +   ) -> Pin<Box<dyn 'async_fut + Future<Output =
                Result<Ok, Err>
    +       >>>
    -       >
        where
            Self : FnMut() -> Fut,
            Fut : Future<Output = Result<Ok, Err>>,
            Err : ShouldRetry,
            Self : 'async_fut,
    -   {
    +   {Box::pin({
            let f = self; // rename.
            async move {
                let _ = (&f, &delay); // ensure the params are captured by the future.
                /* body */
            }
    +   })}
    -   }
    }
    

    which Just Works™

    • Playground

    • FWIW, if you had "just" kept the original async fn signature even though async fns are not allowed for trait methods, and if you had then applied #[async_trait] onto it, that code I've showcased is basically what that macro unsugars to.

  • Use type_alias_impl_trait to emulate being able to name the type of our future

    (this may be what your were trying to attempt, but you used a universal impl Trait rather than an existential one):

    #![feature(min_type_alias_impl_trait, type_alias_impl_trait)]
    
    type WithRetryRet<F, Fut, Ok, Err>
        = impl Future<Output = Result<Ok, Err>>
    ;
    
    fn with_retry<F, Fut, Ok, Err> (
        mut f: F,
        delay: Duration,
    ) -> WithRetryRet<F, Fut, Ok, Err>
    where
        F : FnMut() -> Fut,
        Fut : Future<Output = Result<Ok, Err>>,
        Err : ShouldRetry,
    {
        async move {
            let _ = (&f, &delay); // ensure the params are captured by the future.
            loop {
                match f().await {
                    Err(e) if e.should_retry() => {
                        ::tokio::time::sleep(delay).await;
                        continue;
                    },
                    result => return result,
                }
            }
        }
    }
    
    impl<F> WithRetry for F {}
    trait WithRetry : Sized {
        fn with_retry<Fut, Ok, Err> (
            self: Self,
            delay: Duration,
        ) -> WithRetryRet<Self, Fut, Ok, Err>
        where
            Self : FnMut() -> Fut,
            Fut : Future<Output = Result<Ok, Err>>,
            Err : ShouldRetry,
        {
            with_retry(self, delay)
        }
    }
    
3 Likes

Now, let's go back to your code and see

Why your solution did not work

since you explicitly mentioned being more interested in the why rather than the how.

Let's stop and stare at WithRetry's signature:

trait WithRetry<F> {
    fn with_retry (self: Self, _: Duration)
      -> Retry<F>
    ;
}

Let's compare it with an iterator adaptor:

trait Iterator {
    type Item;

    …

    fn map<B, F>(self: Self, f: F)
      -> Map<Self, F>
    where
        F : FnMut(Self::Item) -> B, 
    ;
}

Notice how the generic params in the return type of map comes from generic params used in input position.

So, in your case, you'd want a signature along those lines (pseudo-code, extra fn bounds ought to be added):

trait WithRetry {
    fn with_retry (self: Self, delay: Duration)
      -> Retry<Self> /* manually impl Future for Retry<F> (manual state machine etc.) */
    {
        Retry(self, delay)
    }
}
// or
trait WithRetry {
    type Ret;
    fn with_retry (self: Self, _: Duration)
      -> impl Future<Output = Ret> + 'some_lifetime
    ;
}
// i.e.,
trait WithRetry {
    type Ret;
    type Fut : Future<Output = Ret>;
    fn with_retry (self: Self, _: Duration)
      -> Self::Fut
    ;
}

Notice how I have already talked about the last two signatures (the one in the middle being the one that we can't write yet, unless we replace impl with dyn, and the last one being the current way, in nightly, to polyfill direct impl). Regarding the first signature, it's an option you could choose if you are able to unsugar the whole async { … } compiler-generated state machine into an explicit one, so as to write its .poll() implementation and thus get a neamable future type on stable Rust :slightly_smiling_face:

2 Likes

Thanks for validating my suspicions on how rust type parameters resolution works. And for super detailed write up of possible options.
From practical point of view, I start thinking Box is the way to go. Usually networking code does not require instruction-level optimization and maybe I even can save something in code size avoiding monomorphisation.

1 Like

Yes, that's definitely the most practical approach. And if you use #[async_trait], it will even be a lightweight / readable one, plus one which could automagically improve in the future should a new alternative arise :slightly_smiling_face:

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.