The size of `(T, Infallible)` is not zero

[EFanZh]

Since Infallible is an empty type, I expect (T, Infallible) also be an empty type, thus they should have the same size. But I noticed that (T, Infallible) have the same size as T, so currently, we have

• mem::size_of::<Option<Infallible>>() == 0
• mem::size_of::<Option<(u32, Infallible)>>() = 8

I guess this is because Rust treats empty type to have size 0, so the size of (T, Infallible) is size of T plus size of Infallible equals size of T. May be we can use something like Option<usize> to represent the size of a type internally, where None means the size of an empty type, in this way, we can distinguish empty types from zero sized types. For example, internally, we can have a function like:

fn internal_size_of<T>() -> Option<usize> { ... }

To keep the current behavior of mem::size_of, it can be implemented as:

fn size_of<T>() {
    internal_size_of::<T>().unwrap_or(0)
}

[vacuus]

(I don't claim to be authoritative on this topic) (I'm using ! but this applies to Infallible just as well)

tl;dr: If you were thinking that size_of::<Option<!>>() == 0 should imply size_of::<Option<(u32, !)>>() = 0, I don't believe there is currently any guarantee for that, and, in any case, the logic for each would be distinct.

The Rustonomicon, which you linked, doesn't seem to guarantee anything about the size of (T, !), and the doc page certainly doesn't. In any case, I don't think it would make sense for the size of (T, !) to be 0. Just like how Result<T, !> effectively removes the Err variant because Err(!) can't be instantiated, (T, !) should effectively be a one-member tuple because the programmer is effectively telling the compiler that the second member can't be instantiated. Monomorphization doesn't completely eliminate Result<T, !> because no such statement has been made about the Ok(_) variant, and similarly, (T, !) makes no statement about the instantiability (lol) of the first member.

Please correct me if I'm wrong!

[scottmcm]

This is intentional; see https://github.com/rust-lang/rust/issues/49298

[RalfJung]

Indeed, the size of (T, Infallible) was 0 at some point and that was critical soundness issue and got fixed.

So I think this issue should probably be closed. The one thing we could do here is improve documentation of this problem, but I am not sure where such docs would go.

[vacuus]

Perhaps the same page of the Rustonomicon that @EFanZh linked at the top?

[RalfJung]

This is intentional; see #49298

As @Ericson2314 pointed out, the example that made this unsound does not compile any more. NLL does not accept thus code so when NLL became mandatory on all editions, this stopped working. That decision was made here; there is an open issue at https://github.com/rust-lang/rust/issues/54987 to re-accept such code.

I will hence re-open this issue to track potentially doing the layout optimization again. That said, clearly that is in conflict with https://github.com/rust-lang/rust/issues/54987, and there might be other soundness issues as well that I am missing.

[RalfJung]

Also see the discussion starting at https://github.com/rust-lang/rust/issues/54987#issuecomment-519131256 for other potential soundness concerns with making (!, T) have size 0. In particular, code like this still works:

let x: (String, !) = (mk_string(), panic!());

and it needs to store the string somewhere (and drop it).

Currently a temporary is created for this (and the tuple constructor is not even anywhere to be seen in the MIR), but I am not sure how intentional that is.

[taralx]

What is the challenge in making -∞ the size of uninhabited types? It makes the math work:

size_of::<!>() = -∞ size_of::<Option<!>>() = LSE(-∞, 0) = 0 size_of::<(u32, !)>() = 4 + -∞ = -∞ size_of::<Option<(u32,!)>>() = LSE(4 + -∞, 0) = 0

[RalfJung]

-∞ is not a number :)

And anyway computing the layout of a type involves a lot more than computing its size, so it's not like somehow changing the size of ! would magically make anything easier. The trouble isn't having layout computation make (!, i32) a ZST -- that in fact was already implemented at some point in the past, but got reverted due to soundness issues (and that was referenced above: https://github.com/rust-lang/rust/issues/49298). The trouble is figuring out if doing so will cause problems elsewhere.

[Ericson2314]

-∞ is I still think morally on the right track, namely we should not conflate the layout of ! and (). Calling them both "ZSTs" just adds more special cases later. What we have is something like

struct InhabittedLayout { size: usize, align: usize }
enum Layout {
   Uninhabitted,
   Inhabitted(InhabittedLayout),
}

and thus a Inhabitted(InhabittedLayout { size: 0, align: 0 }) vs Uninhabitted distinction.

Per https://en.wikipedia.org/wiki/Tropical_geometry layout and the divisibility lattice, layout computation does have nice algebraic properties.

[RalfJung]

we should not conflate the layout of ! and ()

Yeah, and they have different Layout in Rust. That doesn't need to be reflected in size and alignment though.

[Ericson2314]

let x: (String, !) = (mk_string(), panic!());

My understanding is we evaluate the right and side, it diverges, and so we don't care what the left hand side looks like.

let (a, b): (String, !) = (mk_string(), panic!());

Splitting into separate lets doesn't change the behavior of the program, even if it does expose a new location where we didn't have one before.

#![feature(never_type)]

fn main() {
    let x: !;
    println!("asdf");
    x = panic!();
}

Does work today, and cracks me up.

Basically, for spooky reasons of polarity of the sort discussed in many papers of at https://www.pauldownen.com/#publications , I think ! really is just a valid type for "(r) values" (not unlike the original restriction, ironically enough!) and so it "nukes" any locations it touches, per the homormophic layout rules.

The problem with things like let x: !; is that an unitialized variable I think is "morally" a different type Uninitialized<A> instead of A (and the "moral types" of locations changes throughout the control flow graph). When A is inhabited, Uninitialized<A> and A have the same layout, but when A isn't they don't because the whole point of Uninitialized<A> is that it is a "fat" (), and so always inhabited. This absurdity is why uninitialized uninhabitted types should just be banned --- do that, and I will bet a few beers all problems go away.

MaybeUninit, being union, is always inhabited, so MaybeUninit<!> is fine but useless, and MaybeUninit<(!, usize)> is fine but just as useless. (Still cannot do anything with second field of the tuple because the tuple is a ZST, too bad.) This might upset people, but follows from the rules so I am OK with it.

[RalfJung]

This absurdity is why uninitialized uninhabitted types should just be banned --- do that, and I will bet a few beers all problems go away.

I am suspicious of any calculus that ends up not being able to treat uninhabited types properly. let x: T; should work in generic code for any T, ergo it should work for ! as well. If that is a problem for some formal calculus, IMO that shows a flaw in the calculus.

[Ericson2314]

The key word there is "properly". The point of the literature of the sort I linked is not to just ban all the scary stuff, but introduce a little bureaucracy once to get back nice things, like eta rules, de Morgan's laws, etc. etc. I am not proposing that ! locations just be abandoned, just that they must always be initialized. That makes allows us to avoid worrying about what they look like since no code and ever access them. (And *const ! and friends of course doesn't say anything useful about what lies behind the pointer in the type.)

The previous method of breaking the layout algebra by making ! annihilate sums only outside of products I consider a hack to avoid the consequences of what ! "wants to mean". I suppose back in the day making mem::forget kosher because panicking is very analogous to making !'s layout non-algebraic because partial initialization. The "more linearity, less mem::forget" world is pretty well closed off to us at this point, but the "! layout is algebraic" world is still accessible as long as we only reintroduce partial initialization carefully.

[Ericson2314]

If it sounds any better, I don't think there is problem with let x: (!, usize); per se. The problem is trying to project back out the location of the usize. x.0 is fine because whatever, we don't actually "write" ! anywhere that's a good fiction. Hell, x as ! is fine with me too. x.1 however is no good, because the ! has annihilated the whole product.

[RalfJung]

only reintroduce partial initialization carefully

I have not disagreed with that. But I think nothing is wrong with

fn main() {
    let x: !;
    println!("asdf");
    x = panic!();
}

and we should keep it working. This is not in contradiction with layout optimizations for (!, String). You said it is in contradiction to your favorite calculus, and that's IMO a point against that calculus -- and your reply doesn't even respond to this argument.

IOW, partial initialization seems like such a niche feature that if we have to trade it off against making more layout optimizations, the layout optimizations win. We agree on that, even if we don't agree on the reasons for agreeing. :)

However, there are other algebraic properties that are broken by these layout optimizations, so contrary to what you seem to claim it's not like algebra clearly favors one way over the other. Specifically, currently code working on generic MaybeUninit<(T, U)> can do the usual dance to get raw pointers to these two fields and everything will be fine. If we "annihilate" products to ZSTs when either type is uninhabited, that will no longer work. IOW, the general truth that "(T, U) contains memory to independently store a T and U" is broken by this layout optimization.

I don't know if this is a concern in practice, but it is worrying since this affects unsafe code and we would not be able to easily detect when such code gets broken.

[Ericson2314]

It was funny to me, but

fn main() {
    let x: !;
    println!("asdf");
    x = panic!();
}

I don't have a problem with. If MaybeUninit<AnyUninhabittedThing> is a ()-like ZST that is fine and by analogy the above is fine too.

With the recasting I wrote in the prior comment, it is just trying to project the "annihilated" locations (when they aren't also ZSTs) from the (uninitialized) location that is the issue.

x = panic!(); is not projecting such a type, so there is no issue.

fn main() {
    let x: !;
    println!("asdf");
    *(&writeOnly x as &writeOnly ZST) = ZST {};
}

This is even fine too!

Only

fn main() {
    let x: (!, usize);
    println!("asdf");
    x.1 = 5;
}

is a problem because of the x.1 projection, and the nontriviality of usize.

[Ericson2314]

Specifically, currently code working on generic MaybeUninit<(T, U)> can do the usual dance to get raw pointers to these two fields and everything will be fine. If we "annihilate" products to ZSTs when either type is uninhabited, that will no longer work. IOW, the general truth that "(T, U) contains memory to independently store a T and U" is broken by this layout optimization.

I don't know if this is a concern in practice, but it is worrying since this affects unsafe code and we would not be able to easily detect when such code gets broken.

Yes, that is worrisome. One option is

1. Make a ?Inhabitted default bounded (and new such trait), to be used if we
2. Make some syntax for declaring whether empty enums are formally uninhabited
3. Some future edition, change the default
4. Either Infallible is different than the new stable ! (sobs), or one carefully flips its definition to work the new way, and some code might stop compiling (shreeks).

?Inhabitted might someday also be useful for partial initialization, but in the short term just keeps the new annihilating empty types away from generic code that didn't opt-in.

[Ericson2314]

Ah! So one more point, I think it is a bit artificial to exclude sums types from partial initialization. Consider Option::some

pub fn insert(&mut self, value: T) -> &mut T;

If we had out pointers, we could likewise imagine

pub fn set_some(&out self) -> &out T;

This would, given an uninitalized Option<T>, set the Some tag and return the output pointer to the T. This is something I've wanted in low level code before, it's not at all artificial to me.

However! Note that it basically going further down this path precludes even the Option<!> we do today, because it wants the tag to exist. (Technically, the tag is not observable, but once we understand partially initialized sum types, it is natural to then want what the tag of a partially initialized sum tag is.)

The partial initializations we have today I consider just a "second class" form of &out, i.e. uninitalized locations/lvlaue but no corresponding pointer type. So the "second class" inline way to write set_some would be something like:

let x: Option<T> = Some(_);
x.0 = makeT(); // OK because we "know" it's `Some`.

I bring this up to show that partial initialization is the enemy of empty types everywhere, not just in the special case of products where we used to allow. Basically, unrestricted partial initializing is saying that every type must admit a non-standard element called "uninitialized", and thus pessimizes the layout rules across the board.

Because I indeed want all 3 of

• Product partial initialization for non-empty typse, close to like like before
• Sum partial initialization as sketched above sketched above
• The ideal optimized layout which does not care about accommodating uninitialized states

The ?Inhabitted strategy is very attractive to me. Given performance, expressive power, avoiding new opt-out trait, I always pick the first two :).

[RalfJung]

However! Note that it basically precludes even the Option<T!> we do today, because it wants the tag to exist.

I don't think it does? The tag relies on valid bit-patterns of T, so any value of T that is written to the returned out reference will implicitly "set the tag" correctly.

So as long as out references guarantee that some value is written before the lifetime ends, this is all fine even in the presence of layout optimizations and uninhabited types, I think?

[Ericson2314]

Sorry I wrote that vary misleading. The &out thing alone doesn't require the tag for the reason you are saying --- even ignoring lifetimes / questions when the data is initialized, if it is impossible to write to &out ! the &out ! need to point to a valid location, and we the tag need not exist.

Very confusingly in the parenthetical, only if people want to read back what they wrote:

let x: Option<T> = Some(_);
match x {
    Some(_) /* must be _ */ => true,
    None => false,
}

do we run into issues. I think that is probably a logical thing to expect to work if we can also do

let x: (bool, T);
x.0 = false;
if x.0 { "foo" } { "bar" }

but it is certainly not a practical killer feature the way set_some is, so the pure practicality argument for the status quo semi-pessimistic layout is still in tact.

[Ericson2314]

And just to spell it out, with Inhabitted we could write something like:

// Magic type integrating with borrow checker's tracking initializedness
type Uninit<Ty: Inhabitted>;

impl<T: Inhabitted> Option<Uninit<T>> {
    fn is_some(&self) -> bool {
        match x {
            Some(_) /* must be _ */ => true,
            None => false,
        }
    }
}

impl<T, U: Inhabitted> (T, Uninit<U>> {
    fn first(&mut self) -> &mut T {
        &mut x.0
    }
}

[scottmcm]

The ?Inhabitted strategy is very attractive to me.

With my lang hat on, I'll note that it's incredibly unlikely that such a proposal would be accepted. We're not looking to have more ?Foo bounds, because of the training and ecosystem impacts of them. (It's not impossible that one could happen, but the bar is extraordinarily high.)

Given performance

Can you show an example where the size of a struct with an uninhabited field is a "performance" problem in practice? While I agree that it's conceptually-nice to say an uninhabited type has -∞ size, I've only seen theoretical cleanliness-based arguments for it, not anything showing it being an issue in real code.

It seems fundamentally-unlikely to be a real problem, because any code that fully-initializes such a type is necessarily dead. And if it's not dead because it's only partially-initialized, then the product type not being a ZST is useful, not a problem at all.

(It would also fall under "layout optimizations for repr rust" anyway, which are generally not guaranteed, so any code you write wouldn't be correct to depend on it even if it did happen.)

[RalfJung]

do we run into issues

I'm sorry I do not understand which issues you are referring to here.

[Ericson2314]

@RalfJung

let x: Option<T> = Some(_);
match x {
    Some(_) => println!("foo"),
    None => println!("bar"),
}

I mean if this is to be allowed, where the field of the Some is never written or read, but the tag is written and read, then the tag needs to be stored. If the tag can be written by only read when the fields are initialized, then yes indeed the tag can be dropped the fields are impossible to write to.

[Ericson2314]

@scottmcm

With my lang hat on, I'll note that it's incredibly unlikely that such a proposal would be accepted.

Yes I am aware the Lang Team is dead set against more opt out traits. I think that is extremely unfortunate because I keep on finding problems where they would help (here, Advanced FFI, with the likes of Swift and C++ (see near https://twitter.com/ericson2314_/status/1504477340625084423, DynSized for #43467). I used to morn the policy, but now I just point out the new cases as they arrive, for posterity and in hopes that someday in the next few years the scale tips.

performance

(T, Infallible) is obscure outside of generic code interactions that are hard to anticipate occuring or not occuring. But the sume and partial initialization that is mentioned here would be very useful in low level code, to avoid safety performance tradeoffs.

(I have written code that used tons of Options because we didn't have out pointers, then used lots of Option::insert to reduce the number of pointless tag checks, and had to write the unsafe equivalent of Option::insert for my own sum types. I would like all that to go away. This code was sort of like hand-rollled async for embedded, so I imagine the same techniques might also be useful for async runtimes.)

I think the problem is less shrinking (T, Infallible), but trying to ahead of time make sure future layout and future output / uninitialized tricks won't conflict. The pre NLL compromise is rather sketchy in this regard because it is not even clear it is conservative enough to not rule out issue with future flexible initializing tricks.

?Inhabitted with no near term plan to stabilize I think is nice because is keeps the door open going forward. No need to each unstable thing, can always try the optimized aggressive layout and go back to the current one while ?Inhabitted is unstable. Likewise for trying to make new sorts of partial initialization legal or illegal again.

It's nice to keep all that flexibility for our future selves!

[RalfJung]

I mean if this is to be allowed

Oh I see... honestly I don't think we should allow this. The tag is sufficiently different from "normal fields" that treating it differently is justified, and I don't think this comes up often enough to warrant all that complexity.

That said, this is quite similar to @eddyb's concern at https://github.com/rust-lang/rust/issues/49298#issuecomment-380615281, "partial initialization of enum variants" -- except Eddy's comment only really applies to things like Result<i32, (!, i32)> (and interestingly, we do not seem to layout-optimize those).

I have written code that used tons of Options because we didn't have out pointers

I agree out pointers would be useful. But those would then probably entirely avoid Option for most cases, so that does not serve as motivation for "initializing only the tag of an enum (in safe code)".

[Ericson2314]

@RalfJung Yes the options go way, but the other enums were were state machines, were I would incrementally set the next state before "yielding" in some fashion. Those would stay enums, and so it would be nice to set their tag bit first.

I do not need to read their tag bits before they were fully initialized, however, so dropping the tag write in the case of an empty variant is perhaps OK.

[Ericson2314]

Yeah the https://github.com/rust-lang/rust/issues/49298#issuecomment-380615281 is the one that I would make illegal to split into two separate loads with ?Inhabited.

The original program might be fine if RHS eval first means there must be a temporary, but the optimization would not be able to project the non-temporary location to write the string to because the type of the containing outer location (the tuple) is not Inhabited.

[zakarumych]

I imagine that partial initialization would be kinda like syntactic sugar. Where given type

struct Foo { a: u8, b: String }

additional "type" is defined

struct PartiallyInitializedFoo { a: MaybeUninit<u8>, b: MaybeUninit<String> }

and which fields are initialized is tracked separately.

Therefore if uninhabited field zeroes size of struct, partially initialized version of that struct would have unoptimized size, with space to store all inhabited fields. For normal structs sizes of partially initialized version of the struct would matches initialized version. And with uninhabited fields fully initialized version struct doesn't need to have a layout at all.

[eddyb]

I imagine that partial initialization would be kinda like syntactic sugar.

If we actually had syntax to do it and that was the only way it could occur, sure, you could imagine it as syntactic sugar, and transform it appropriately (IIRC generators, which underpin async fn, do something like that? it may have been to avoid false positives in miri checks).

But what happens is that every time you write anything like (foo(), bar()), the MIR is roughly:

let tmp1 = foo();
let tmp2 = bar();
dest = (tmp1, tmp2);

but given the right circumstances, the goal has ~always been to optimize that to:

dest.0 = foo();
dest.1 = bar();

bar's return type can be generic in the MIR body this is happening in (i.e. could potentially be instantiated to ! or another uninhabited type), and you can't guarantee that whatever dest is can have its layout modified, but the optimization would be otherwise fine.

One relatively simple example is to make dest the return place:

fn foobar<T, U>(foo: impl FnOnce() -> T, bar: impl FnOnce() -> U) -> (T, U) {
   (foo(), bar()) 
}

We want to always optimize functions like the above to something like this:

return.0 = foo();
return.1 = bar();
return;

(in more interesting situations it should be possible to even end up with e.g. a modify_foo(&mut return.0) call in the middle, but I didn't want to overcomplicate this example)

But the caller of foobar will allocate memory for the layout of (T, U), and, in the general case, pass a pointer to that memory to foobar.

[zakarumych]

If return type is uninhabited there's no reason to place partially initialized return value in return place, function diverges anyway.

But I get the idea. If the goal is to make the following code acceptable and non-panicking

union Foo {
  a: u8,
  b: (u32, !),
}

fn foo(foo: &mut Foo) {
  foo.b.0 = 1;
  assert!(ptr::eq(&*foo, &*foo.b.0));
}

Then keeping size_of::<Foo>() == 1 would be impossible. Because then 1 would be stored on stack and address would differ.

I wouldn't think about it if you didn't mention modify_foo(&mut return.0) call ^_^

[eddyb]

If return type is uninhabited there's no reason to place partially initialized return value in return place, function diverges anyway.

The way to think about this is that the foo and bar calls may be worlds apart.

With more components/functions: (a(), b(), c(), d(), e(), ..., z()).

Let's say you learn, during monomorphization/codegen, that z() always diverges, but what does that mean for every call before it? Not much, they still have to execute.

If, say, d panics, then the values returned by a(), b() and c() have to be dropped.

And z itself might not even be a failure mode, but e.g. || std::process::exit(0).

Either way, by the time you know everything about z, MIR optimizations must have executed in absentia (on the generic definition), and so they may then rely on return.{0,...,25} existing, and being useful as general-purpose scratch space (even for monomorphizations where the function doesn't return).

[Nadrieril]

Hi! I was under the impression that this question was well settled in the direction of "(T, !) has space for T". I can't find a good source though, what's the status of this? If this hasn't been done yet, could we get a binding decision from T-lang on this matter in one direction or the other? (I'm hoping to resurrect https://github.com/rust-lang/rust/issues/54987)

[RalfJung]

I don't think that was ever officially decided. It just happens to be the case currently and MIR building relies on it so when (T, !) was accidentally made zero-sized that led to a soundness issue.

If you want to get a T-lang decision, I suggest you write up the motivation and what you want to have decided, and nominate that for T-lang discussion.

[scottmcm]

@Nadrieril As far as I know, the lang team thinks that an example like this https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=a7c3a6f3fce6347f33948a7f86e9761a

use core::mem::MaybeUninit;
pub fn make_tuple<A, B>(a: impl FnOnce() -> A, b: impl FnOnce() -> B) -> (A, B) {
    unsafe {
        let mut m: MaybeUninit<(A, B)> = MaybeUninit::uninit();
        std::ptr::addr_of_mut!((*m.as_mut_ptr()).0).write(a());
        std::ptr::addr_of_mut!((*m.as_mut_ptr()).1).write(b());
        m.assume_init()
    }
}

enum Never {}

fn main() {
    let x = make_tuple(|| "hello".to_string(), || "world".to_string());
    dbg!(x);

    let _y: (String, Never) = make_tuple(|| "yup".to_string(), || panic!());
}

should not be UB, even though make_tuple::<String, Never> like that must always diverge. (The example leaks, but that could be fixed -- the point is that it's not UB to write a non-ZST into the storage for m.)

So long as that's the case -- basically meaning that field projecting inside a MaybeUninit like that is legal -- I think that precludes making (String, Never) a ZST.

(Existing layout guarantees https://doc.rust-lang.org/std/mem/union.MaybeUninit.html#layout-1 prevent us from saying that MaybeUninit<(String, Never)> is a non-ZST but (String, Never) is a ZST. And I don't think I'd want to try to split that hair even if we could.)

So if you wanted to write that up in some appropriate document form (RFC, like the provenance one? Dunno) I think it could be accepted relatively easily.

[RalfJung]

Note however that that example only decides the case for tuples. We could still make this a ZST

struct S(String, !);

You can't write code that is generic over structs.

But possibly the lang team intents that example to also apply to non-generic cases, for an arbitrary struct.

[jplatte]

IMHO, it would be pretty weird if for

struct St<T>(T, !);
struct StU8(u8, !);

St<u8> and StU8 had different sizes. I think it might be the the first case where substituting generics "by hand" would lead to significantly different codegen.

[RalfJung]

We certainly explicitly reserve the right for differences like that.

[Nadrieril]

Pattern types are specifically considering such a difference in fact

[RalfJung]

Maybe a first step would be to add this to the lang team's "frequently requested changes" and explain there that this is not going to happen. That should be sufficient to close this issue.