Exponentially growing impl trait type names


#1

I was working on a project to make existing tokio-socks5 production.

One of the improvements is, I want to use impl Future instead of Box<Future>.

The plan was successful but I need a custom enum type to allow returning from different match arms. Once I did that, I noticed the compile time is significantly increased but don’t know why.

Until yesterday, I started to refactoring a big function body to a set of method chains. (This is usually called “extract method” refactoring). When I was doing so I see an error says the type names is exceeding the limit (to be set to 2,097,152 chars long at the time), and I need a specific attribute in my crate main to increase it. I did that and continue to refactoring, then I received another error says it is now reaching the new limit. I gave up after then.

So, some facts I realized from the excersise:

  • The increased compile time is due to the compiler creates huge type names internally.
  • The refactoring is actually makes this case worse (i.e. it makes the type names longer rather than shorter)
  • The length of type name must being growing exponentially in some scenarios.
  • The exponential growth is not only theoretical, but also practical in real world, as I am only refactoring existing code that worked.

Right now, I am planed to raise an issue to the rust compiler, but to continue the work I am planning to stop the exponentially growing type names.

One way to do so I think is to use closure types in the middle. As I can see so far, the compiler generated closure types would not be too long as it does not contain information about the captured variables. So it is ideal if I want to hide some types inside. As those types will not be visible to the outside, it will then not appearing in the type signature.

This requires me to create a struct to simply wrap a Fn trait inside, and implement Future trait on it. I would try this tonight.

For the long term, I believe the proper solution is to generate a unique type for each impl returns and hiding all component types inside, so if people still get trouble of this, doing extract method refactoring would help rather than making things worse.

Question

As the previous plan does not work, I have to do something else. Now I may have to go back to use Box, but can anyone show me alternatives?


#2

Here is an example that shows the exponentially growing type name:

Playground link

#![feature(core_intrinsics)]

#[derive(Copy,Clone)]
struct Add<T1,T2>(T1,T2) where T1:Copy +Sized, T2:Copy+Sized;

fn addself(a:impl Copy) -> impl Copy {
    Add(Add(a,a),Add(a,a))
}

fn print_type_of<T>(_: &T) {
    println!("{}", unsafe { std::intrinsics::type_name::<T>() });
}

fn main() {
    print_type_of(&addself(addself(addself(11))));
}

This prints 633 characters.


#3

Can you demonstrate this happening with a non-recursive type? The exponential type name goes hand-in-hand with the struct’s data growing exponentially. Perhaps elaborate with a reduced test case of the refactoring you did.


#4

Yes the above version contains types that the size of it is also growing exponentially. But here is another example that have linear size

Playground link

#![feature(core_intrinsics)]

use std::mem::size_of;

enum When<T1,T2>
    where T1:Sync, T2:Sync
{
    Either(T1),
    Or(T2)
}
use When::{Either,Or};

fn roll(a:impl Sync) -> impl Sync {
    if true {Either(a)} else { Or(a) }
    
}
fn roll1(a:impl Sync) -> impl Sync {
    roll(roll(a))
    
}
fn roll2(a:impl Sync) -> impl Sync {
    roll1(roll1(a))
    
}

fn print_type_of<T>(_: T) {
    let s = format!("{}", unsafe { std::intrinsics::type_name::<T>() });
    println!("{}\nsize={}\ntype name length={}", s, size_of::<T>(), s.len());
}

fn main() {
    print_type_of(roll2(roll2(roll2(11))));
}

Output:

When<When<....
size=52
type name length=45048

I believe this is what I was experiencing: I have an enum that works like When above called EitherFuture, and I use it to wrap different Futures returned from different arms of match statements. Each of such attempt, like the above, doubles or almost doubles the size of the type name length, and so eventially exceeded the length limit of the compiler.

By the way, if you want to look at the work I did, check out this. Look at the function serve and image you have replaced all box (it calls mybox function in the code though) with something similar to When above.

(The refactoring and EitherFuture are not submitted yet so you won’t see it now, I may commit tonight once I found a way to use closure to hide concrete type components from type names.)


#5

Unfortunately, I think closure is just making thing worse, not better.

Playground link

(I am a bit curious about why I have to use explicit life time for function roll, should it be automated?)

#![feature(core_intrinsics)]

use std::mem::size_of;


trait Reflactable {
    fn size(&self) -> usize;
    fn type_name_len(&self) -> usize;
    fn type_name(&self) -> String;
}

impl<'a,T> Reflactable for T where T:'a
{
    fn size(&self) -> usize {
        size_of::<Self>()
    }
    fn type_name_len(&self) -> usize {
        self.type_name().len()
    }
    fn type_name(&self) -> String {
        format!("{}", unsafe { std::intrinsics::type_name::<Self>() })
    }
}

enum Stuff<T1,T2>
{
    This(T1),
    That(T2)
}
use Stuff::{This,That};

struct W<F, T>
    where F:FnOnce() -> T + Sized {
    f: F        
}

fn roll<'a>(a:impl Reflactable + 'a) -> impl Reflactable + 'a {
    W{ f:|| if true {This(a)} else { That(a) } }
}

fn main() {
    let v = roll(1);
    println!("({},{})", v.size(), v.type_name_len());
    let v = roll(v);
    println!("{}",v.type_name());
    println!("({},{})", v.size(), v.type_name_len());
    let v = roll(v);
    println!("({},{})", v.size(), v.type_name_len());
    let v = roll(v);
    println!("({},{})", v.size(), v.type_name_len());
    let v = roll(v);
    println!("({},{})", v.size(), v.type_name_len());
    let v = roll(v);
    println!("({},{})", v.size(), v.type_name_len());
}

Output:

(4,60)
W<[closure@src/main.rs:38:10: 38:47 a:W<[closure@src/main.rs:38:10: 38:47 a:i32], Stuff<i32, i32>>], Stuff<W<[closure@src/main.rs:38:10: 38:47 a:i32], Stuff<i32, i32>>, W<[closure@src/main.rs:38:10: 38:47 a:i32], Stuff<i32, i32>>>>
(4,231)
(4,744)
(4,2283)
(4,6900)
(4,20751)

The growth rate is even higher… and the closure didn’t hide any types within, so it didn’t resolve anything.