Bogus error in beta and nightly: recursive type has infinite size

[jorendorff]

trait Front {
    type Back;
}

impl<T> Front for Vec<T> {
    type Back = Vec<T>;
}

struct PtrBack<T: Front>(*mut T::Back);

struct M(PtrBack<Vec<M>>);

fn main() {
    println!("{}", std::mem::size_of::<M>());
}

This program prints 8 in Stable (1.5.0), but in Beta and Nightly compilation fails with:

<anon>:11:1: 11:27 error: recursive type `M` has infinite size [E0072]
<anon>:11 struct M(PtrBack<Vec<M>>);
          ^~~~~~~~~~~~~~~~~~~~~~~~~~
<anon>:11:1: 11:27 help: see the detailed explanation for E0072
<anon>:11:1: 11:27 help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `M` representable
<anon>:11:1: 11:27 note: type `M` is embedded within `PtrBack<collections::vec::Vec<M>>`...
<anon>:11:1: 11:27 note: ...which in turn is embedded within `PtrBack<collections::vec::Vec<M>>`...
<anon>:11:1: 11:27 note: ...which in turn is embedded within `M`, completing the cycle.

From 8 bytes to infinity would seem to be a serious memory usage regression.

[jorendorff]

Same error if I change the pointer to a Box.

[jonas-schievink]

cc @nikomatsakis since I think he touched that code last

[arielb1]

Mini (no Vec needed - Vec is quite internally complex for some reason):

trait Front { type Back; }
impl<T> Front for T { type Back = T; }
struct PtrBack<T: Front>(*mut T::Back);
struct M(PtrBack<M>);

fn main() {
    println!("{}", std::mem::size_of::<M>());
}

[arielb1]

This is fallout from inductiveness

In the OC, the problem is that:

*) M: Sized if (sized)
*) PtrBack<M>: Sized if (sized)
*) *mut <M as Front>::Back: Sized if (sized)
*) M: Front if (impl)
*) M: Sized 

This could potentially be fixed by lazy normalization.

A harder case is:

trait Front { type Back; }
impl<T> Front for T { type Back = *mut T; /* note *mut is here */ }
struct PtrBack<T: Front>(T::Back);
struct M(PtrBack<M>);

fn main() {
    println!("{}", std::mem::size_of::<M>());
}

The cycle is similar:

*) M: Sized if (sized)
*) PtrBack<M>: Sized if (sized)
*) <M as Front>::Back: Sized if (sized)
*) M: Front if (impl)
*) M: Sized 

However, not even lazy normalization can save us here.

I admit the infinite type detection here is just plain wrong.

[Aatch]

@arielb1 those sequences are kinda hard to understand. However, I'm not sure why Sized is that relevant here. Unless the "infinite sized type" error is just a red herring and it's mis-reporting the recursive dependency for Sized vs. non-Sized?

[nikomatsakis]

@Aatch the message is basically a special-cased variant targeting the case where computing whether T: Sized is implemented requires that we recursively compute T: Sized. That usually (but not always) means an infinitely sized type, hence the message.

This is pretty related to how we can formalize auto traits. I'd been debating about a formalization that basically inserted one (automatically generated) impl for each auto trait, but those impls worked the same way as all other impls (this is not how it works today, but how it works today is unsound). However, I realized that this could fail, and my example was exactly the one that @jorendorff gives here -- one where the recursion arises through a projection. In the Obligation Forest PR, I considered whether to make Sized co-inductive, but @aturon and I decided we could avoid it. This may not have been correct.

So it may be that the correct fix is to have auto traits have a more complex, co-inductive proving semantics and -- since Sized is entirely builtin -- also give it those same semantics.

[Aatch]

@nikomatsakis so to be clear, the error message is wrong here, the problem is that we have "T meets Sized if T meets Sized" being reported as "T has infinite size". Makes sense given that in the absence of projection the only way that recursion could happen is if T contained T without indirection. Just want to make sure there's a version of this problem written in language understandable to those not super-familiar with the compiler's type-system internals.

[nikomatsakis]

@Aatch I agree the message is wrong, I didn't consider this case when phrasing it -- but I think ideally we wouldn't be reporting an error here at all. I guess the question is if there is a way to achieve that.

[arielb1]

auto trait = OIBIT right?

I'd been debating about a formalization that basically inserted one (automatically generated) impl for each auto trait

What's the difference between that and what we have today? That auto traits are coinductive?

If we forbid coinductive traits from having supertraits and associated types/constants we should be fine, as they can only be inputs of trait selection and not outputs.

[nikomatsakis]

triage: P-high

[nikomatsakis]

It's not clear what the best fix here is. One option is to change how we process the Sized trait to make it coinductive -- this may cause an issue with adding an associated constant Size, but maybe not. At minimum we ought to improve the error message. But we should make some decisions, given that this is a regression, hence the P-high categorization.

[nikomatsakis]

I think that for now the best thing here is to fix the error message, leaving ourselves the freedom to make this legal again in the future if we decide it won't undermine the type system. :)

[jorendorff]

@areilb1 Would you mind explaining your *) notation?

I'm trying to understand what's causing the loop. It seemed to me like it might be

• let's check if struct M(PtrBack<Vec<M>>); is a reasonable thing to say
• that requires that M is a valid parameter to Vec<_>
• that requires that M: Sized (implicit bound)
• that requires that all M's fields have valid types
• that requires that M is a valid parameter to Vec<_> (closing the loop)

But that can't be right, because struct M(Vec<M>); compiles just fine. The trait must be involved in the loop somehow. And I know you've already posted the answer. I just can't read it. :)

@nikomatsakis While we're here - I have feels about the wording "has infinite size" in error messages. It feels like it's attributing a deeply ridiculous intent to me, the user. Instead of saying "you did a typo" rustc is saying "oh, you want an infinitely large struct, I'm sorry, I can't do that". It must think I'm some kind of genius-level doofus. The message would be a little insulting, if the compiler were constructed by actual people who are actually smarter than me... waaaait a minute...

[Aatch]

@jorendorff so the message you get about "infinite size" there is actually wrong, it's actually the issue that we have the requirement M is Sized if M is Sized. Though that's not technically true here, either, hence @arielb1 stating that the error goes away if you tweak when normalization (turning T::Foo into an actual type) happens. Though it doesn't solve the issue in all cases.

As for the general problem of "infinite size" in errors, I see your point, but the error has to explain why it's incorrect somehow. I mean, what would an alternative error message look like? "You appear to have made a mistake, trying adding indirection in this type"? What mistake? What's the issue? Why would adding indirection help?

[arielb1]

infinite size

The expectation was that you encounter this error when you try to make a recursive type (say a tree or something) without using a Box. In that case, the error message tells you exactly what went wrong, and how you fix it.

I think that's a general problem with error messages. When code with a typo attempts to do something silly, you will get an error message about the silly thing.

There's a bug here that we report this error message with no infinite-sized type in sight. @nikomatsakis is working on fixing this (I think). Its just a recursive trait evaluation error.

[jorendorff]

Sorry I mentioned it. Filed #31683 for the pet peeve.

[nikomatsakis]

I'm assigning this to @arielb1 since I believe that his pending PR (#33138) will fix it.

[nikomatsakis]

This is now fixed (just verified) by #33138. Closing.