Exponential Expansion of Shared Type Aliases

[Sahilgill24]

Project version

0.7.2

Project

compiler

What happened?

The compiler can represent nested type aliases very compactly by sharing their underlying Arc nodes. This means a sequence of aliases such as:

type A0 = u8;
type A1 = (A0, A0);
type A2 = (A1, A1);
type A3 = (A2, A2);
...

forms a small DAG rather than storing the fully expanded type. With N aliases, the stored representation is therefore roughly linear in size.

when this type is later used impl From<&ResolvedType> for StructuralType (src/types.rs:1175) traverses the type using post_order_iter(). The TreeLike implementation for &ResolvedType (src/types.rs:571) returns the child Arcs, but the traversal does not deduplicate already-seen nodes by pointer identity.

As a result, when the same alias is referenced multiple times, the compiler walks the same underlying subtree again for every path that reaches it. So a depth of N can therefore result in roughly 2^N leaf visits.
This was my observation.

depth 16: 0.39 s
depth 20: 5.74 s
depth 22: 23.9 s

Minimal reproduction steps

This is one of the examples that demonstrates the bug

type A0 = u8;
type A1 = (A0, A0);
type A2 = (A1, A1);
type A3 = (A2, A2);
type A4 = (A3, A3);
type A5 = (A4, A4);
type A6 = (A5, A5);
type A7 = (A6, A6);
type A8 = (A7, A7);
type A9 = (A8, A8);
...
type A30 = (A29, A29);
fn main() { let _x: A30 = witness::W; }

trying to compile this leads to the compiler being hung.

[apoelstra]

Neat! We will need to implement a SharingTracker for type aliases.

I have a PR that I will open right after #388 which refactors the type system. I would like to get that in first, and then I can fix this.

[apoelstra]

FYI rustc has the same bug. (Although I still agree that we ought to fix it.)

type A0 = ();
type A1 = (A0, A0);
type A2 = (A1, A1);
type A3 = (A2, A2);
type A4 = (A3, A3);
type A5 = (A4, A4);
type A6 = (A5, A5);
type A7 = (A6, A6);
type A8 = (A7, A7);
type A9 = (A8, A8);
type A10 = (A9, A9);
type A11 = (A10, A10);
type A12 = (A11, A11);
type A13 = (A12, A12);
type A14 = (A13, A13);
type A15 = (A14, A14);
type A16 = (A15, A15);
type A17 = (A16, A16);
type A18 = (A17, A17);
type A19 = (A18, A18);
type A20 = (A19, A19);
type A21 = (A20, A20);
type A22 = (A21, A21);
type A23 = (A22, A22);
type A24 = (A23, A23);
type A25 = (A24, A24);
type A26 = (A25, A25);
type A27 = (A26, A26);
type A28 = (A27, A27);
type A29 = (A28, A28);
type A30 = (A29, A29);

fn main() {
    let _x: A30 = core::mem::transmute(());
    let _y: A29 = _x;
}

rustc bomb.rs  # will take all your memory and crash

[apoelstra]

Ah, if you delete the contents of main rustc will spin for a minute or two (but not forever) and not consume much memory. It's the transmute line, where we actually construct a value, that kills it. The second line is unnecessary but I suspect will exhibit a separate bug (trying to unify two exponentially-sized types that differ only in their leaves).

It's kinda hard to see how any compiler can do anything sensible with code like this.

I wonder if we need to cap the number of nodes that exist in types, or something.

[stringhandler]

Tuple values are slow in parsing. Similar to #410. This could be the same issue or different.

This (depth 18) takes 8 seconds to compile. Depth 20 takes 35 seconds.

fn main() {
    let x: ((((((((((((((((((u32,),),),),),),),),),),),),),),),),),) = ((((((((((((((((((0,),),),),),),),),),),),),),),),),),);
}

[stringhandler]

Created separate issue #411