Expotential compile time with recursive trait bounds

[weiznich]

While developing diesel we've hit a surprising increase in compile time caused by our trait impls for tuples. See diesel-rs/diesel#2480 for details. I've extracted a somewhat minimal example here. There is an option to control the tuple size up to which traits should be implemented in line 861. For a size of 16 the compilation of the example succeeds in less then 2 seconds using the rust-playground + the current stable compiler. For a tuple size > 20 the playground is terminated. (Diesel takes ~30s to build while implementing traits for tuples up to 16 elements, and 17 minutes while implementing traits for tuples up to 32 elements for my local setup).

I suspect that this is caused by the combination of a having a recursive trait bound here + enforcing that bound for each tuple size here. Diesel itself has not only one trait that requires Self: SqlType, but probably the problem is increased by that.

[weiznich]

Replacing the impl_sql_type with

macro_rules! impl_sql_type {
    (
        @build
        start_ts = [$($ST: ident,)*],
        ts = [$T1: ident,],
        bounds = [$($bounds: tt)*],
        is_null = [$($is_null: tt)*],
    )=> {
        impl<$($ST,)*> SqlType for ($($ST,)*)
        where
            $($ST: SqlType,)*
            $($bounds)*https://github.com/diesel-rs/diesel/pull/2485
            $T1::IsNull: OneIsNullable<$($is_null)*>,
        {
            type IsNull = <$T1::IsNull as OneIsNullable<$($is_null)*>>::Out;
        }

    };
    (
        @build
        start_ts = [$($ST: ident,)*],
        ts = [$T1: ident, $($T: ident,)+],
        bounds = [$($bounds: tt)*],
        is_null = [$($is_null: tt)*],
    )=> {
        impl_sql_type!{
            @build
            start_ts = [$($ST,)*],
            ts = [$($T,)*],
            bounds = [$($bounds)* $T1::IsNull: OneIsNullable<$($is_null)*>,],
            is_null = [<$T1::IsNull as OneIsNullable<$($is_null)*>>::Out],
        }
    };
    ($T1: ident, $($T: ident,)+) => {
        impl_sql_type!{
            @build
            start_ts = [$T1, $($T,)*],
            ts = [$($T,)*],
            bounds = [],
            is_null = [$T1::IsNull],
        }
    };
    ($T1: ident,) => {
        impl<$T1> SqlType for ($T1,)
        where $T1: SqlType,
        {
            type IsNull = $T1::IsNull;
        }
    }
}

speeds up the compile time for large tuples drastically. This is only replacing the recursive "calculation" of the associated type with an explicit version for each tuple size, so instead of having type IsNull = <FirstTupleElement as OneIsNullable<<(All, Other Tuple, Elements, …) as SqlType>::IsNull>::Out; we write now type IsNull = <FirstTupleElement as OneIsNullable<<SecondTupleElement as OneIsNullable<…>>::Out>>::Out;