Bug: quadratic time on deeply nested types

[Nadrieril]

#![allow(unused)]
fn main() {}

trait Iterator {
    fn chain<P>(self, p: P) -> Chain<Self, P>
    where
        Self: Sized,
    {
        Chain(self, p)
    }
}

struct Chain<L, R>(L, R);

impl<L, R> Iterator for Chain<L, R> {}

fn test() {
    Chain(0, 0)
        //
        .chain(0)
        .chain(0)
        .chain(0)
        .chain(0)
        .chain(0)
        .chain(0);
}

This takes time worse than quadratic in the number of calls to chain, even with --no-serialize --hide-marker-traits --ullbc. This goes away if we do struct Chain<L: ?Sized, R: ?Sized>(PhantomData<L>, PhantomData<R>);.

This is therefore caused by the quadratically-sized annoyance of Sized trait bounds:

let x = Chain(0, 0).chain(0).chain(0);

we get the following type for x:

Chain<
    Chain<
        Chain<i32, i32>[core::marker::Sized<i32>, core::marker::Sized<i32>],
        i32
    >[
        core::marker::Sized<Chain<i32, i32>[core::marker::Sized<i32>, core::marker::Sized<i32>]>,
        core::marker::Sized<i32>
    ],
    i32
>[
    core::marker::Sized<
        Chain<
            Chain<i32, i32>[core::marker::Sized<i32>, core::marker::Sized<i32>],
            i32
        >[
            core::marker::Sized<Chain<i32, i32>[core::marker::Sized<i32>, core::marker::Sized<i32>]>,
            core::marker::Sized<i32>
        ]
    >,
    core::marker::Sized<i32>
]

[sonmarcho]

This is annoying. Do you have an idea about how to solve this?

[Nadrieril]

We'll have to do more deduplication, in particular for passes that traverse a type.

[Nadrieril]

Actually the first step would be to hash-cons TraitRefs in both hax and charon so we can piggy-back on rustc's interning to only translate each ref once.

Second step would be to deduplicate the serialized output so we only serialize each unique Ty/TraitRef once. Maybe with a flag to recover the plain serialization for easier debugging (that's exactly what hax does).

Third step would be to somehow avoid applying the same modification to a type multiple times. That sounds very tricky; possibly I might need to unify the various type-modifying passes first so that common logic can be reused. Expect binder shenanigans.