Exponential Type Blowup when wrapping function

[gakonst]

I am implementing a service architecture, where each service can be thought of as middleware. It makes sense to define complex services which need to manage their own complex state as their own structs and implement my Service trait for each one. However, for simple operations, e.g. logging or manipulating some argument in place, it makes more sense to have a wrapper service which receives the previous service's "request", does whatever it needs to do, and passes it on. The wrapper service also implements the Service trait.

The problem here is that there is an exponential type length complexity blowup when passing in the function.

Probably related: #54540, note how there's no closure in my example

MVCE below: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=17d88bb1e552b2cc285ced44777e726b

(complex services: BaseService / MyService, stateless services: logger, doubler)

// The objective is to be able to wrap existing services with simple functions, without
// having to define a new service each time we want to perform a very minimal action
// on the data flow. We could define a LoggerService and a DoublingService, but that
// is _a lot_ of boilerplate.
fn main() {
    let s = BaseService;
    // We can create as many new services as we want,
    // the type length increases linearly, as expected
    let s = MyService::new(s);
    let s = MyService::new(s);
    // The type length of `s` doubles
    let s = WrappedService::new(s, stateless_log);
    // if you try to wrap a few times, your code hits the type length limit
    let s = WrappedService::new(s, stateless_double);
    let s = WrappedService::new(s, stateless_double);
    let s = WrappedService::new(s, stateless_double);
    let s = WrappedService::new(s, stateless_double);
    let s = WrappedService::new(s, stateless_double);
    let s = WrappedService::new(s, stateless_double);
    let s = WrappedService::new(s, stateless_double);
    let s = WrappedService::new(s, stateless_double);
    let s = WrappedService::new(s, stateless_double)
}

type Request = u64;
type MyResult = Result<(), ()>;

pub trait Service {
    fn handle(&mut self, request: Request) -> MyResult;
}

// A simple service which we we use as our base
#[derive(Clone)]
pub struct BaseService;
impl Service for BaseService {
    fn handle(&mut self, _request: Request) -> MyResult {
        Ok(())
    }
}

// A service that takes another service (and could have more state)
#[derive(Clone)]
pub struct MyService<O> {
    next: O,
}
impl<O> MyService<O>
where
    O: Service + Clone + Send,
{
    pub fn new(next: O) -> Self {
        MyService { next }
    }
}
impl<O> Service for MyService<O>
where
    O: Service + Clone + Send,
{
    fn handle(&mut self, request: Request) -> MyResult {
        self.next.handle(request)
    }
}

/// =========== Stateless Services =========

use std::sync::Arc;

// We have to store the service onion so far, and the function we want to inject
#[derive(Clone)]
pub struct WrappedService<F, I> {
    f: F,
    inner: Arc<I>,
}
impl<F, S> WrappedService<F, S>
where
    F: Fn(S, Request) -> MyResult,
    S: Service + Clone,
{
    pub fn new(inner: S, f: F) -> Self {
        WrappedService {
            f,
            inner: Arc::new(inner),
        }
    }
}
impl<F, S> Service for WrappedService<F, S>
where
    F: Fn(S, Request) -> MyResult,
    S: Service + Clone,
{
    fn handle(&mut self, request: Request) -> MyResult {
        (self.f)((*self.inner).clone(), request)
    }
}

// Is there a way to convert these to a service, without having to go through a lot of boilerplate?
pub fn stateless_log<O: Service + Clone>(mut next: O, request: Request) -> MyResult {
    println!("sending request");
    let result = next.handle(request);
    println!("got result");
    result
}

pub fn stateless_double<O: Service + Clone>(mut next: O, request: Request) -> MyResult {
    let request = 2 * request;
    let result = next.handle(request);
    result
}

(Playground)

[gakonst]

Converting the function's argument to a Boxed trait object as a workaround did the trick: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=68c09468854a00faa2b5b9fb000e578b

75,76c75,76
<     F: Fn(S, Request) -> MyResult,
<     S: Service + Clone,
---
>     F: Fn(Box<dyn Service>, Request) -> MyResult,2
>     S: Service + Clone + 'static,
87,88c87,88
<     F: Fn(S, Request) -> MyResult,
<     S: Service + Clone,
---
>     F: Fn(Box<dyn Service>, Request) -> MyResult,
>     S: Service + Clone + 'static,
91c91
<         (self.f)((*self.inner).clone(), request)
---
>         (self.f)(Box::new((*self.inner).clone()), request)
96c96
< pub fn stateless_log<O: Service + Clone>(mut next: O, request: Request) -> MyResult {
---
> pub fn stateless_log(mut next: Box<dyn Service>, request: Request) -> MyResult {
103c103
< pub fn stateless_double<O: Service + Clone>(mut next: O, request: Request) -> MyResult {
---
> pub fn stateless_double(mut next: Box<dyn Service>, request: Request) -> MyResult {

[bstrie]

Last year we had shown the aforementioned service architecture and its compilation-time woes to @nikomatsakis , who expressed some interest in hearing about whether we could manage to find a solution. (Though he may have been more interested in the fact that we were needing to introduce ever-escalating #![type_length_limit = "5000000"] attributes in order to even compile at all. :P ) We had previously tried boxing plenty of things in a relatively haphazard way without much luck at addressing or discovering the underlying problem. However, with the boxing strategy shown here we seem to have cut our typical compilation times in half (though we have not yet successfully rid ourselves of the type_length_limit attributes, whose values still somehow seem to keep rising...).

[davidpdrsn]

I’m seeing a similar issue when using Tower and impl Trait. Made issue on rust-analyzer but “cargo build” is also slow so probably also a rust issue rust-lang/rust-analyzer#7403

it includes a reproduction script.