Pre-eRFC: Let's fix DSTs

[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.

[parched]

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

Having now skimmed the unsized rvalues RFC, it seems these will be very close to DynSized. The difference is the size is a runtime constant (it is unknown at compile time but is constant at runtime) so the following rules for DynSized can be relaxed.

1. The following expressions must always return a Sized type:

   1. Function calls, method calls, operator expressions implementing unsized return values for function calls would require the called function to do the alloca in our stack frame.

2. The RHS of assignment expressions must always have a Sized type. Assigning an unsized type is impossible because we don’t know how much memory is available at the destination. This applies to ExprAssign assignments and not to StmtLet let-statements.

These types aren’t in upstream LLVM yet last time I checked, so maybe nothing needs to be done now. Nevertheless, it should be kept in mind that another trait between Sized and DynSized, say RuntimeSized, will probably need to be added at some stage.

[mikeyhew]

A couple of questions:

1. What do you mean by “runtime constant”? Would the Pixels example from above be an instance of this or not, and why?

2. What would the difference between DynSized and RuntimeSized be?

[parched]

Basically it means std::mem::size_of exists for the type but it isn’t const.

[mikeyhew]

it feels very “significant” to me that T: Referent / T: ?DynSized basically corresponds to a non-owned T

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).

Well, I don’t think it’s an accident, but the idea may indeed be a sort of dead-end. On the one hand, the main reasons I can think of to know the size of something all correspond to ownership:

You need to free it (i.e., you own it), and hence want to call dealloc

You want to copy it to your stack frame (i.e., you want to take ownership of it) and need to know how much stack space to allocate

However, there is one other place where we really need to know the size: if you have a type like &[A], you are borrowing those A values, but you still need to know their size to compute their offset. Similar things could apply for other types – the main reason this isn’t true for structs is that we restrict DST types to being in the final position layout-wise, so we only need to know their alignment to compute their offset.

So I know I said that I wanted to talk about this in the other issue, but the ownership stuff is at least somewhat on-topic, and it’s a lot easier to reply here, so that’s what I’m gonna do

My opinion is that any correspondence between ownership (whether you can pass something by value or just by reference) and sizedness (whether something’s size is known at compile time, run time or not at all) is an accident of the way things are in Rust today. OK, that’s not entirely true – you will never be able to pass something by value without knowing its size. However, the fact that you can’t pass ownership of something to a function without knowing its size is, in my opinion, an unnecessary restriction, and one of my DST-related goals is to have this restriction lifted.

Currently, there are two main ways of passing ownership of a value to a function:

1. By value. This works for Sized + Move types, and with the unsized rvalues RFC would work for DynSized + Move types as well, by using &move-reference under the hood
2. By boxed value. This works for any DynSized type, but would not work for every Referent type because there is no way to deallocate the boxed value without knowing its size

There is a potential third way of passing ownership that works for any Referent type: explicit &move-references. With &move T, we can pass ownership of a value, without needing to allocate it on the heap, and without needing to know its size. Whereas the unsized rvalue sugar would presumably only support types that are Move + DynSized, &move T works for any T.

[parched]

A couple of questions:

1. What do you mean by “runtime constant”? Would the Pixels example from above be an instance of this or not, and why?

2. What would the difference between DynSized and RuntimeSized be?

1. No, the difference is the metadata for sizing is per type not per value, and this metadata can only be determined at runtime unlike a Sized type.

2. It can be returned by value and assigned like a Sized type, but it can’t do anything that requires the size known at compile time.

[kennytm]

Have some thought about DST enum again.

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?

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

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

The representation of *mut (dyn Trait) type is currently the 2-tuple (*mut (), &'static Vtable<dyn Trait>), where Vtable<_> is the struct:

#[repr(C)]
struct Vtable<D: TraitObject> {
    destroy: fn(*mut ()),
    size: usize,
    align: usize,
    methods: D::Methods,
}

IIUC @eddyb, what you mean is that for a DST enum *mut Option<dyn Trait>, it will be represented as a 3-tuple (*mut void, &'static Vtable<dyn Trait>, &'static EnumFields<1>), where EnumFields is the struct:

#[repr(C)]
struct EnumFields<const number_of_fields: usize> {
    discriminant: fn(*const ()) -> u64,
    field_offsets: [usize; number_of_fields],
}

---

As an alternative, I think it is possible to make *mut Option<dyn Trait> still a 2-tuple (*mut (), &'static Vtable<dyn Trait>) by implementing the entire niche-filling algorithm at runtime.

1. Modify the Vtable<_> struct by encoding the entire rustc::ty::LayoutDetails:

   #[repr(C)]
   struct Vtable<D: TraitObject> {
       destroy: fn(*mut ()),
       size: usize,
       align: usize,
       layout_details: (Variants, FieldPlacement, Abi),  
       //^ new.
       // could store the minimal analyzed information just enough to 
       // compute the discriminant offset+size and field offsets
       methods: D::Methods,
   }
   

2. The DynSized trait will add a layout_details_of_val method

   trait DynSized {
       fn layout_details_of_val(r: &Self) -> (Variants, FieldPlacement, Abi);
       //^ or maybe restrict to `Self::Meta`
       // I haven't checked the implication of taking `&Self` yet
   }
   

3. Change mem::discriminant<T> to a runtime implementation of rustc_mir::interpret::EvalContext::read_discriminant_value, based on {layout_details,size,align}_of_val() of each variant of T.

4. Similarly, the offsets in a variant is to be calculated at runtime using {layout_details,size,align}_of_val() of that variant.

We’d likely disallow customized implementation of layout_details_of_val() in a custom DST.

Cons of this approach:

• The vtables will become one-word larger even if DST enum is never used.
• Needs more space to store the layout details as well.
• Duplicating logic between compile-time and runtime.

[eddyb]

by implementing the entire niche-filling algorithm at runtime.

IMO this requires too much reflection machinery up-front (even if you don’t need it), whereas my idea “just” monomorphizes a function like mem::discriminant.
It’s also more expensive to do a recursive search through the reflected layout just to call .is_some() or .as_ref().

It’d be nice to have a pointer-sized metadata even in this case, but I don’t know how we could reasonably do it efficiently or without reflecting the layout.

[SimonSapin]

I’ve submitted a Pointer metadata & VTable RFC that would problem #2. It is mostly a subset of this proposal.

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.