exponential_builder.rs

#![allow(dead_code)]

macro_rules! impl_providers_state {
    (
        struct Container {
            $(
                $field:ident: $field_ty:ident,
            )*
        }
    ) => {
        // Define a struct to hold all of the current values
        #[derive(Default)]
        pub struct Container<$($field_ty,)*> {
            $(
                $field: $field_ty,
            )*
        }

        // Define a trait that converts an opaque `impl Providers` into a `Container`.
        pub trait Providers {
            $(
                type $field_ty: $field::Provider;
            )*

            fn into_container(self) -> Container<$(Self::$field_ty,)*>;
        }

        impl<$($field_ty: $field::Provider,)*> Providers for Container<$($field_ty,)*> {
            $(
                type $field_ty = $field_ty;
            )*

            fn into_container(self) -> Container<$(Self::$field_ty,)*> {
                self
            }
        }

        // Define the default set of providers for Container
        type DefaultProviders = Container<$($field::Default,)*>;

        impl_providers_state!(@with, {}, {$($field: $field_ty),*});
    };
    (@with, { $($prev:ident: $prev_ty:ident),* }, { $field:ident: $field_ty:ident $(, $rest:ident: $rest_ty:ident)* }) => {
        impl<Prev: Providers, New: $field::Provider> $field::With<New> for Builder<Prev> {
            type Output = Container<$(Prev::$prev_ty, )* New $(, Prev::$rest_ty)*>;

            fn with(self, $field: New) -> Self::Output {
                let providers = self.0.into_container();
                Container {
                    $field,
                    $(
                        $prev: providers.$prev,
                    )*
                    $(
                        $rest: providers.$rest,
                    )*
                }
            }
        }
    }
}

impl_providers_state!(
    struct Container {
        a: A,
        b: B,
        c: C,
        d: D,
        e: E,
        f: F,
        g: G,
        h: H,
        i: I,
        j: J,
        k: K,
        l: L,
        m: M,
        n: N,
        o: O,
    }
);

pub mod a {
    // Define a trait for each associated type to implement.
    pub trait Provider {}

    #[derive(Debug, Default)]
    pub struct Default;

    impl Provider for Default {}

    // Define a trait that updates the Container with a new type for `a`.
    pub trait With<T: Provider> {
        type Output;

        fn with(self, provider: T) -> Self::Output;
    }
}
use a as b;
use a as c;
use a as d;
use a as e;
use a as f;
use a as g;
use a as h;
use a as i;
use a as j;
use a as k;
use a as l;
use a as m;
use a as n;
use a as o;

pub struct Builder<Providers>(Providers);

impl Default for Builder<DefaultProviders> {
    fn default() -> Self {
        Builder(Default::default())
    }
}

// Pass `--cfg non_impl` to observe what the compile time should be
#[cfg(not(non_impl))]
macro_rules! ret_type {
    ($u:ident) => {
        impl Providers
    };
}
#[cfg(non_impl)]
macro_rules! ret_type {
    ($u:ident) => {
        $u
    };
}

impl<Prev: Providers> Builder<Prev> {
    /// Returning `Builder<impl Providers>` here causes compile times to exponentially increase with
    /// every additional call to `with_a`. Changing the return type to `U` maintains minimal compile times.
    pub fn with_a<T, U>(self, value: T) -> Builder<ret_type!(U)>
    where
        T: a::Provider,
        U: Providers,
        Self: a::With<T, Output = U>,
    {
        Builder(a::With::with(self, value))
    }
}

// Pass `--cfg 'depth = "N"'` to specify the number of calls to `with_a`. As N increases, compile time increases exponentially.
fn main() {
    #[cfg(depth = "1")]
    Builder::default().with_a(a::Default);

    #[cfg(depth = "3")]
    Builder::default().with_a(a::Default).with_a(a::Default);

    #[cfg(depth = "3")]
    Builder::default()
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default);

    #[cfg(depth = "4")]
    Builder::default()
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default);

    #[cfg(depth = "5")]
    Builder::default()
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default);

    #[cfg(depth = "6")]
    Builder::default()
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default);

    #[cfg(depth = "7")]
    Builder::default()
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default);

    #[cfg(depth = "8")]
    Builder::default()
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default)
        .with_a(a::Default);
}

exponential_builder_expanded.rs

#![allow(dead_code)]

// Define a struct to hold all of the current values
#[derive(Default)]
pub struct Container<A, B, C, D, E, F, G, H, I, J, K, L, M, N, O> {
    a: A,
    b: B,
    c: C,
    d: D,
    e: E,
    f: F,
    g: G,
    h: H,
    i: I,
    j: J,
    k: K,
    l: L,
    m: M,
    n: N,
    o: O,
}

// Define a trait that converts an opaque `impl Providers` into a `Container`.
pub trait Providers {
    type A: Provider;
    type B: Provider;
    type C: Provider;
    type D: Provider;
    type E: Provider;
    type F: Provider;
    type G: Provider;
    type H: Provider;
    type I: Provider;
    type J: Provider;
    type K: Provider;
    type L: Provider;
    type M: Provider;
    type N: Provider;
    type O: Provider;
    fn into_container(
        self,
    ) -> Container<
        Self::A,
        Self::B,
        Self::C,
        Self::D,
        Self::E,
        Self::F,
        Self::G,
        Self::H,
        Self::I,
        Self::J,
        Self::K,
        Self::L,
        Self::M,
        Self::N,
        Self::O,
    >;
}

impl<
        A: Provider,
        B: Provider,
        C: Provider,
        D: Provider,
        E: Provider,
        F: Provider,
        G: Provider,
        H: Provider,
        I: Provider,
        J: Provider,
        K: Provider,
        L: Provider,
        M: Provider,
        N: Provider,
        O: Provider,
    > Providers for Container<A, B, C, D, E, F, G, H, I, J, K, L, M, N, O>
{
    type A = A;
    type B = B;
    type C = C;
    type D = D;
    type E = E;
    type F = F;
    type G = G;
    type H = H;
    type I = I;
    type J = J;
    type K = K;
    type L = L;
    type M = M;
    type N = N;
    type O = O;
    fn into_container(
        self,
    ) -> Container<
        Self::A,
        Self::B,
        Self::C,
        Self::D,
        Self::E,
        Self::F,
        Self::G,
        Self::H,
        Self::I,
        Self::J,
        Self::K,
        Self::L,
        Self::M,
        Self::N,
        Self::O,
    > {
        self
    }
}

// Define a trait for each associated type to implement.
pub trait Provider {}

// Define a default provider
#[derive(Debug, Default)]
pub struct Dp;

impl Provider for Dp {}

// Define the default set of providers for Container
type DefaultProviders = Container<Dp, Dp, Dp, Dp, Dp, Dp, Dp, Dp, Dp, Dp, Dp, Dp, Dp, Dp, Dp>;

// Create a wrapper struct to hold the `impl Providers`.
pub struct Builder<Providers>(Providers);

impl Default for Builder<DefaultProviders> {
    fn default() -> Self {
        Self(Default::default())
    }
}

// Define a trait that updates the Container with a new type for `a`.
pub trait WithA<T: Provider> {
    type Output;

    fn with_a(self, provider: T) -> Self::Output;
}

impl<P: Providers, New: Provider> WithA<New> for Builder<P> {
    type Output = Container<
        New,
        P::B,
        P::C,
        P::D,
        P::E,
        P::F,
        P::G,
        P::H,
        P::I,
        P::J,
        P::K,
        P::L,
        P::M,
        P::N,
        P::O,
    >;
    fn with_a(self, a: New) -> Self::Output {
        let c = self.0.into_container();
        Container {
            a,
            b: c.b,
            c: c.c,
            d: c.d,
            e: c.e,
            f: c.f,
            g: c.g,
            h: c.h,
            i: c.i,
            j: c.j,
            k: c.k,
            l: c.l,
            m: c.m,
            n: c.n,
            o: c.o,
        }
    }
}

// Pass `--cfg non_impl` to observe what the compile time should be
#[cfg(not(non_impl))]
macro_rules! ret_type {
    ($u:ident) => {
        impl Providers
    };
}
#[cfg(non_impl)]
macro_rules! ret_type {
    ($u:ident) => {
        $u
    };
}

impl<P: Providers> Builder<P> {
    /// Returning `Builder<impl Providers>` here causes compile times to exponentially increase with
    /// every additional call to `with_a`. Changing the return type to `U` maintains minimal compile times.
    pub fn with_a<T, U>(self, value: T) -> Builder<ret_type!(U)>
    where
        T: Provider,
        U: Providers,
        Self: WithA<T, Output = U>,
    {
        Builder(WithA::with_a(self, value))
    }
}

// Pass `--cfg 'depth = "N"'` to specify the number of calls to `with_a`. As N increases, compile time increases exponentially.
fn main() {
    #[cfg(depth = "1")]
    Builder::default().with_a(Dp);

    #[cfg(depth = "3")]
    Builder::default().with_a(Dp).with_a(Dp);

    #[cfg(depth = "3")]
    Builder::default().with_a(Dp).with_a(Dp).with_a(Dp);

    #[cfg(depth = "4")]
    Builder::default()
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp);

    #[cfg(depth = "5")]
    Builder::default()
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp);

    #[cfg(depth = "6")]
    Builder::default()
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp);

    #[cfg(depth = "7")]
    Builder::default()
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp);

    #[cfg(depth = "8")]
    Builder::default()
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp)
        .with_a(Dp);
}

rustc_1_35.txt

rustc 1.35.0 (3c235d560 2019-05-20)
binary: rustc
commit-hash: 3c235d5600393dfe6c36eeed34042efad8d4f26e
commit-date: 2019-05-20
host: x86_64-apple-darwin
release: 1.35.0
LLVM version: 8.0
--------------
depth = 1

real	0m0.178s
user	0m0.140s
sys	0m0.031s
non-impl

real	0m0.184s
user	0m0.147s
sys	0m0.031s
--------------
depth = 2

real	0m0.182s
user	0m0.145s
sys	0m0.032s
non-impl

real	0m0.178s
user	0m0.141s
sys	0m0.030s
--------------
depth = 3

real	0m0.247s
user	0m0.206s
sys	0m0.035s
non-impl

real	0m0.176s
user	0m0.140s
sys	0m0.029s
--------------
depth = 4

real	0m0.962s
user	0m0.895s
sys	0m0.059s
non-impl

real	0m0.175s
user	0m0.139s
sys	0m0.031s
--------------
depth = 5

real	0m12.253s
user	0m11.635s
sys	0m0.573s
non-impl

real	0m0.173s
user	0m0.138s
sys	0m0.028s
--------------
depth = 6

real	3m20.304s
user	3m1.123s
sys	0m17.460s
non-impl

real	0m0.217s
user	0m0.147s
sys	0m0.039s

rustc_1_63.txt

rustc 1.63.0 (4b91a6ea7 2022-08-08)
binary: rustc
commit-hash: 4b91a6ea7258a947e59c6522cd5898e7c0a6a88f
commit-date: 2022-08-08
host: x86_64-apple-darwin
release: 1.63.0
LLVM version: 14.0.5
--------------
depth = 1

real	0m0.123s
user	0m0.089s
sys	0m0.026s
non-impl

real	0m0.124s
user	0m0.089s
sys	0m0.028s
--------------
depth = 2

real	0m0.128s
user	0m0.093s
sys	0m0.029s
non-impl

real	0m0.125s
user	0m0.091s
sys	0m0.027s
--------------
depth = 3

real	0m0.133s
user	0m0.098s
sys	0m0.029s
non-impl

real	0m0.124s
user	0m0.090s
sys	0m0.027s
--------------
depth = 4

real	0m0.151s
user	0m0.117s
sys	0m0.028s
non-impl

real	0m0.121s
user	0m0.088s
sys	0m0.027s
--------------
depth = 5

real	0m0.442s
user	0m0.408s
sys	0m0.028s
non-impl

real	0m0.116s
user	0m0.082s
sys	0m0.026s
--------------
depth = 6

real	0m5.449s
user	0m5.395s
sys	0m0.037s
non-impl

real	0m0.117s
user	0m0.083s
sys	0m0.026s
--------------
depth = 7

real	1m10.219s
user	1m9.805s
sys	0m0.184s
non-impl

real	0m0.119s
user	0m0.084s
sys	0m0.026s

test.sh

#!/usr/bin/env bash

function t() {
    echo "--------------"
    echo "depth = $1"
    time rustc src/main.rs --emit=metadata --cfg "depth = \"$1\""
    echo "non-impl"
    time rustc src/main.rs --emit=metadata --cfg "depth = \"$1\"" --cfg non_impl
}

rustc --version --verbose

t 1
t 2
t 3
t 4
t 5
t 6
t 7