Pre-eRFC: Let's fix DSTs

[mikeyhew]

DynAligned doesn’t work. The minimal promise a type can give about alignment, if any, is AlignFromMeta. This is because in a DST struct

struct X<T: DynAligned> {
    a: u8,
    b: T,
}

if you need to read &x.b, you’ll first need to find the offset of b, which in turn requires knowing the alignment of b without knowing its pointer value.

I see what you mean. T: DynSized as currently written still works with Box<T>, and can be copied around with no problems, but it doesn’t work with Rc<T>.

In particular, that means that Rc<Thin<dyn Trait>> doesn’t work. I think it’s really important that we get that working, so let’s think about it for a second. Here’s what the monomorphized type RcBox<Thin<dyn Trait>> looks like:

struct RcBox<Thin<dyn Trait> {
    strong: ...,
    weak: ...,
    value: Thin<dyn Trait> {
        meta: <dyn Trait>::Meta, // stored at alignment of <Thin<dyn Trait>>
        data: dyn Trait
    }
}

The problem is, the value field of RcBox, is stored at an offset determined by Thin<dyn Trait>'s alignment, which is only determined by reading value.meta. but value.meta is stored at that alignment, meaning we have a chicken-or-egg problem and have to read value.meta to read value.meta.

The solution, I guess, is to “lift” the meta field out into the containing RcBox struct, and store it at the proper alignment of a <dyn Trait>::Meta. That would look like this:

struct RcBox<Thin<dyn Trait>> {
    strong: ...,
    weak: ...,
    value.meta: <dyn Trait>::Meta, // stored at alignment of <dyn Trait::Meta>
    value: Thin<dyn Trait> {
        data: dyn Trait
    }
}

What we need for Thin to work is a way to tell the compiler that a Thin<T>, when stored as a field in a containing struct, should have the meta field separated out and stored at its own static alignment. A Thin<T> by itself would always be stored at the alignment of the T stored within (assuming it’s larger than the alignment of the T::Meta also stored within), and an RcBox<Thin<T>> would also be stored at the alignment of the T stored within, however the padding between the meta and data field of the Thin<T> could vary depending on whether the Thin<T> is stored by itself or as a field in a struct.

I’m not sure what traits we would need for that. Something to experiment with though.

Unless someone comes up with a better solution. There’s also the option of just creating ThinRc<T>, ThinBox<T> and other Thin*<T> pointer types, but then you have to create a “thin” version of each pointer type.

[F001]

I have a question that why Thin is designed to be a struct. In my mental model, it is better to be a trait. Assume the “field in trait” feature is ready, we could define the Thin trait to be:

trait Thin { 
    type Meta;
    field metadata : Self::Meta;
}

Any concrete type which implemented this trait is guaranteed to contain a metadata. So if T: Thin, &T Box<T> and Rc<T> could make use of this field and themselves could be thin pointers. And if there is a trait Widget: Thin {} , we could make the trait object Box<Widget> a thin pointer too, since the instance of a concrete type T contains a metadata if T: Widget. (Of course, Thin trait must be specially treated by compiler, may be a lang item).

Disclaimer: I don’t know whether it is feasible to design this trait. I just feel the Thin struct is kind of hard to understand for me.

[mikeyhew]

extern { type Pixels };

I sort of like the idea of using extern type for this; that seems to avoid the unsized type syntax that I was floating before.

I’m not really tied to any particular syntax, I was just thinking that, since the extern type syntax is already there, we may as well use it while we’re testing things out

One thing that is part of these traits is what type of non-meta data is expected, right? At least for things like DynSized, the Meta presumably imposes some conditions on what it can be combined with, but those are kind of implicit. That’s maybe OK, just interesting.

I’m sorry, I really have no idea what you’re asking here

I like the Thin<T> setup, that seems elegant, though clearly for any particular dynamically sized type, one could make it thin as well. e.g., it seems relatively straighforward to satisfy @withoutboats’s use case from failure, right?

I like it too, and hopefully we can make it work, although there are some complications with DynAligned as @kennytm pointed out. And yes, the idea is that Thin<T> works for any T: SizeFromMeta (I initially wrote T: DynSized, but I’m gonna change that right now).

[mikeyhew]

Deprecating ?Sized in favor of a white-list of special traits is interesting. As you mentioned, I have some worry about the interaction with Move though. Would this mean T: Sized becomes T: Sized + ?Move? Wouldn’t it break backward compatibility?

An alternative idea is to make ? means ?Sized — T: DynSized + ?. The + ? looks very cryptic, but is still better than the Sized + ?Sized nonsense (this means ?Move).

I definitely agree that the cognitive costs of ?Traits are problematic. I think that the idea of having a “family” of Sized-related traits helps somewhat here, where picking one from that family kind of disables the others, helps somewhat here; it’s not a complete solution (but there may not exist a complete one).

Do you have any further thoughts on this? Just as a contrary data point, to me it feels like an accident - though I don’t have any specific, concrete thoughts about it (either).

I’m glad to see that you’re all enthusiastically discussing how we can make all these traits as ergonomic as possible. However, since discussion is already taking place on basically that topic in https://github.com/rust-lang/rfcs/issues/2255, it’s kind of awkward to be discussing the same thing in two places at once.

How about this: we keep the discussion about ergonomics confined to the GitHub issue, and for now, in this topic, focus on which traits we actually need, and assume we’ll figure out an ergonomic way to deal with them. (I know, this is my fault, since I’m the one that started talking about it here.)

[glaebhoerl]

(I wasn’t talking about ergonomics personally, but the relationship (if any) between the sizedness traits and ownership, which seems like a more fundamental matter)

[mikeyhew]

The reason that Thin<T> is a generic struct is so that it can work for any type T: SizeFromMeta, and in particular, any trait object type. Thin as a trait, if it works, would only work for traits with Thin as a super trait. Which would be fine for object-oriented style hierarchies like Widget, but isn’t general enough to support most traits in Rust.

[parched]

How might “sizeless types” defined in Arm C language extension for SVE fit in here?

Informally, sizeless types can be used in the following situations:

• as the type of an object with automatic storage duration;
• as a function parameter or return type;
• …
• as the target of a pointer or reference type; and
• as a template type argument.

Sizeless types may not be used in the following situations:

• as the type of a variable with static or thread-local storage duration (regardless of whether the variable is being defined or just declared);
• as the type of an array element;
• as the operand to a new expression; and
• as the type of object being deleted by a delete expression.

In all other respects, sizeless types have the same restrictions as the standard-defined incomplete types. This specifically includes (but is not limited to) the following:

• The argument to sizeof and _Alignof cannot be a sizeless type, or an object of sizeless type.
• It is not possible to perform arithmetic on pointers to sizeless types. (This affects the +, -, ++ and – operators.)
• Members of unions, structures and classes cannot have sizeless type.
• _Atomic variables cannot have sizeless type.
• It is not possible to throw or catch objects of sizeless type.
• Lambda expressions cannot capture sizeless types by value, although they can capture them by reference. (This is a corollary of not allowing member variables to have sizeless type.) Standard library containers like std::vector cannot have a sizeless value_type.

[kornel]

When is it useful to have alignment determined at run time?

I might be lacking imagination, but I need DSTs for things like multidimensional slices and custom fat pointers, and for all of them I’d be OK with just hardcoded usize alignment.

[mikeyhew]

@kornel The obvious case is trait objects – they have the alignment of the erased type.

std::mem::align_of_val(&5i32 as &::std::any::Any) // => 4
std::mem::align_of_val(&5i64 as &::std::any::Any) // => 8

[kornel]

In that case, would this work?

Thin<dyn Trait> {
     meta: <dyn Trait>::Meta, // stored at alignment of Meta
     variable_padding: [u8; ?],
     data: Trait,  // stored at alignment of trait's implementation
}

The Thin struct would have compile-time constant alignment of its Meta and a variable length. The data alignment would be stored in Meta and you’d have to read it to compute the data pointer.

[kennytm]

Consider the type Thin<u64x2> where u64x2 has 128-bit (16-byte) alignment. The Thin type according to your scheme would be arranged as

struct Thin {
    meta: &'static Vtable,   // size = 8 bytes
    padding: [u8; 8],
    data: u64x2,             // offset = 16
}

However, the alignment of Thin would only be 8,

struct Foo {
   a: u8,
   b: Thin<u64x2>,   // offset = 8
}

here foo.b's offset can only be 8, which means the offset of foo.b.data would be 24, making access to foo.b.data misaligned.

We could fix it by making that “variable padding” depends on the run-time pointer value of self in additional to the alignment deriving from meta. The drawback is that ptr::copy will require two separate calls to memcpy.

[mikeyhew]

@kennytm Your use of a non-trait-object type with thin reminded me of something that I’ve been meaning to point out: the definition of Thin that I wrote earlier needs another type parameter in order to support unsizing:

struct Thin<T: SizeFromMeta, U: Unsize<T> + SizeFromMeta = T> {
    meta: <T as Referent>::Meta,
    data: U
}

[mikeyhew]

Can’t the necessary information become part of the fat pointer?

That… would work (e.g. a mem::discriminant::<Enum<T>> function pointer for unsizing Enum<T>).

It would make the fat pointer larger, but maybe that’s an alright trade-off?

Are you sure? I think this may be a counter-example:

let foo: RefCell<Option<&i32>> = RefCell::new(Some(&34));

// bar has pointer metadata for an `Option<Any>`, including discriminant
// EDIT: updated to replace `&Any` with `Any`
let bar: &RefCell<Option<Any>> = &foo as &RefCell<Option<Any>>;

// allowed because `bar` is only a shared borrow of the `RefCell`,
// and not the contained `Option`
foo.replace(None);
println!("{}", *bar.borrow().is_some());
// prints "true" because the pointer metadata still says that
// `Some` is the active variant
// It's easy to cause UB here

[eddyb]

Not the discriminant, but mem::discriminant::<Enum<T>> the function (as a fn pointer, to be exact).

As in, how to obtain the discriminant. You don’t need to know how to change it, since you can’t do that after unsizing through the unsized type - as you show, by using foo instead of bar (I think you don’t need RefCell, btw, Cell should work fine).

Also, did you mean to write Any instead of &Any?

[mikeyhew]

Oh, I see. And yes, Any should be there in place of &Any, good point. EDIT: fixed the error in the original comment

[arielb1]

Not the discriminant, but mem::discriminant::<Enum<T>> the function (as a fn pointer, to be exact).

Won’t you also need to be able to get the field offsets? e.g. for Option<T>, the T might be in both offsets 0 and 8.

[eddyb]

Okay, yeah, you probably need something closer to a vtable for “virtual fields”, I was oversimplifying then I said “a function pointer”.

[Diggsey]

Can’t you just disable layout optimisations for enums containing potentially dynamically sized variants?

[eddyb]

I mentioned this as the original trade-off. It would mean we can’t ever allow T: ?Sized for Option<T> (because we guarantee layout optimizations for it to unsafe code etc.).

[mikeyhew]

Once upon a time we also had ideas about nifty things like “nested DSTs”, e.g. &[[T]] would contain two pieces of metadata in the fat pointer - the size of the outer [] and of the inner - resulting in a regular (rectangular) 2D array. Likewise, &[Trait] would be a homogeneous slice of an unknown type that implements Trait. And even just (this is no longer nested, only nifty) unsizing Vec<Type> into Vec<Trait>, with the Vec itself being a kind of smart pointer (just, to multiple values), and fattening up to store the additional vtable pointer. (Vec<Trait> itself may not be that useful, because you won’t be able to push any new items onto it, so maybe it’s not the best possible example; but the point is that anything which doesn’t store T unboxed, rather only through pointers, could/should/would be able to behave “like a smart pointer” from the perspective of DSTs.)

Can these kind of things be accomodated by the plan (even if just to the extent of not ruling them out)?

Hopefully the Custom DST implementation that we come up with would allow experimenting with stuff like that in a library, without needing to add special support and syntax to the compiler. I can definitely see something like [Trait] being doable – I would call it ErasedSlice<T> where T: SizeFromMeta, with its metadata is a (usize, T::Meta) tuple. I’m not so sure how useful a nested slice [[T]] would be, since it would have to be contiguous, but it should be doable in a third-party library.