overflow => generics that produce trans errors depending on type parameters

[comex]

In which we sneakily define a type that contains itself:

(EDIT: Actually, this one didn't depend on specialization. There was previously a default impl of Tr2 not depending on Tr, but it wasn't necessary. The second one does seem to depend on it.)

trait Tr {
    type X;
}
trait Tr2 {
    type Y;
}

struct S<T: ?Sized + Tr> {
    x: <<T as Tr>::X as Tr2>::Y,
}

impl<T: Tr> Tr2 for T {
    type Y = S<T>;
}

impl<T> Tr for T { type X = T; }

fn func<T>() {
    let _: S<T> = panic!();
}

fn main() {
    func::<u32>();
}

produces:

error: overflow representing the type S<u32>

This error comes from trans, and it goes away if either the call to func or func's usage of S<T> is commented out. In other words, func claims to allow instantiation with any type but actually supports no types. (By adding more specializations it could be made to support only certain types.)

A similar issue is when overflow occurs while determining whether a given specialization applies:

#![feature(specialization)]

trait Tr {
    type Other;
}
struct S<T>(T);
impl<T> Tr for T {
    default type Other = <S<T> as Tr>::Other;
}
impl Tr for S<S<S<S<u32>>>> {
    type Other = u32;
}
fn func<T>() {
    let _: <T as Tr>::Other = panic!();
}

fn main() {
    func::<u32>();
}

This happens to compile, but if the u32 in main is changed to u64, I get:

error: overflow evaluating the requirement <S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<u64>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> as Tr>::Other

Is this a known consequence of specialization? I haven't seen it discussed. It seems to violate Rust's normal policy of type-safe generics, and I'm not sure what a rule to prevent it upfront would look like (especially considering that the patterns can in some cases be split across multiple crates).

[pnkfelix]

triage: I-nominated

[pnkfelix]

cc @aturon

[arielb1]

This is possible even without specialization. At least, it used to be with the old Sized rules.

[comex]

I made a mistake: the first example doesn't actually require specialization, and the simplified version I edited into the original post works the same way on stable.

Though I think it may be more difficult to fix in the presence of specialization: the only reason func can instantiate S<T>, which requires Tr, with its T, which doesn't, is the blanket impl on Tr, but that blanket impl could also be consulted to "see through" the X in <<T as Tr>::X as Tr2>::Y - writing <T as Tr2>::Y already produces the (somewhat dubiously worded) pre-trans error "overflow evaluating the requirement <T as Tr2>::Y". However, with specialization, there can be both a blanket impl and many specific impls; the compiler could check every possibility, but I don't think this can work correctly with impls split across crates, and in any case it would have exponentially many possibilities as the number of nested projections grows, and might be annoyingly conservative. Disclaimer: I don't know much about compiler internals so I could be completely misguided.

[pnkfelix]

triage: P-high to investigate

[aturon]

So, I see the first example as a case that we should ultimately try to catch and give a better error for (as we do for more direct circular structs). But I don't think it's terribly urgent, personally.

For the second case: I suspect that this is fundamental. That is, the proof search for traits fundamentally relies on an overflow cutoff to avoid infinite loops, and the fact that specialization lets you dispatch on types will always mean that you can selectively create these overflowing situations. I see the "blame" here as mostly the fact that the trait system can fail due to overflow, but that's inevitable in having as powerful of a system as we do.

I'm going to renominate for triage of the bug listed in the top comment, which we could try to provide a better error for. I suggest that this is P-low, however.

triage: I-nominated

[nikomatsakis]

triage: P-low

@aturon's summary seems accurate.

[deavid]

I got the same while playing around with Rust:

struct L<T> {
    n: Option<T>,
}
type L8<T> = L<L<L<L<L<L<L<L<T>>>>>>>>;
type L64<T> = L8<L8<L8<L8<T>>>>;

fn main() {
    use std::mem::size_of;
    // This prints "128: 1":
    println!("128: {}", size_of::<L64<L64<()>>>()); 
    // This line does not compile: error: overflow representing the type std::option::Option<()>
    println!("129: {}", size_of::<L<L64<L64<()>>>>()); 
}

While something like this might not make much sense in real programs I thought it might be useful to you to have a minimal source that demonstrates the problem.

Option is not needed here, but it cuts down the amount of "recursivity" in half. So it seems there is some kind of limit of 256 levels when building a struct.

I wonder if it's possible to reach the limit with real-life programs. Most recursive or complex structs hold pointers, not actual data, so I guess it's not a problem for most people.

[bstrie]

deavid's minimized reproduction compiles and runs for me (Rust 1.53). comex's original example still fails, but the error messages are different, and it's no longer possible to bypass the error by commenting out usage. Since this bug report is less along the lines of "types should be allowed to recurse indefinitely" and more along the lines of "too-large types shouldn't require usage in order to be rejected", I suspect this can be closed. However, a UI test might be nice.

[Dylan-DPC]

Closing this based on the [comment](#32498 (comment)