` even mean?).
* * *
Also I scared myself temporarily about _`Unsize`_ on enums, which would be quite problematic in the face of enum discriminant optimizations/niching.
---
### Author:  [@CraftSpider](https://internals.rust-lang.org/u/CraftSpider)
#### Post date: [June 23, 2022, 6:02pm UTC](https://internals.rust-lang.org/t/pre-rfc-improved-unsizing/16861/13 "2022-06-23T18:02:34Z")
Updated all but the repr commentary. I'm not 100% on the best way to resolve that, as I'm not super familiar with Rust's current layout algorithm. My instinct for it not causing issues is that the field to unsize must be the last one in the struct. That means that there will never be a field _after_ it that would want to reorder to _before_ it. Thus any that it would re-order before will either fill the padding exactly either way, or, would require the end be padded to length anyways. So this is a safe restriction as long as it only applies to the final field.
```rust
// This has size 4 either way
struct Foo {
a: u8,
b: u8,
c: [u16; 2],
}
// The tail has no size - no advantage to moving it
struct Bar {
a: u8,
c: [u64; 0],
}
```
---
### Author:  [@CAD97](https://internals.rust-lang.org/u/CAD97)
#### Post date: [June 24, 2022, 6:22am UTC](https://internals.rust-lang.org/t/pre-rfc-improved-unsizing/16861/14 "2022-06-24T06:22:49Z")
> [@CraftSpider](#):
>
> That means that there will never be a field _after_ it that would want to reorder to _before_ it.
There could be a field _before_ it that wants to reorder _after_ it to minimize padding.
The theorem to prove is that given any layout, you can construct a layout at least as good with the desired field in the unsizing location.
> **A failed partial proof**
>
> In the document, we use the definition of `a mod b` for integer `a`, positive integer `b` as the smallest _nonnegative_ integer `x` where `(a - x) / b = 0`.
>
> For convenience, we define `a amod b` as `-a mod b`.
>
> For convenience, we define `a ~ b` as the smallest integer `x ≥ a` where `x mod b = 0`.
>
> Lemma 1: `a ~ b = a + (a amod b)`.
>
> Proof left to the reader.
>
> Lemma 2: For any nonnegative `a`:
> Lemma 2.1: `a mod b ≤ a`.
> Lemma 2.2: `a amod b ≤ a`.
> Lemma 2.3: `a mod b ≤ b`.
> Lemma 2.4: `a amod b ≤ b`.
>
> Proof left to the reader. Trivial.
>
> Theorem: It is always possible to reorder a critical type in alignment padded structure layout such that all non-padding fields come before it without increasing structure size.
>
> We split the problem into three cases. In all cases, our critical type is Tail(size A, align B), and our structure has alignment Q, which is assumed to be sufficiently aligned for all fields.
>
> Case 1:
>
> All other fields are before the tail.
>
> The layout can be broken into four parts:
>
> - Before(size X, align Y)
> - Padding to B
> - Tail(size A, align B)
> - Padding to Q
>
> ```rust
> struct(size N1, align Q) {
> // align Q
> Before(size X, align Y)
> Padding(size X amod B)
> // align B
> Tail(size A, align B)
> Padding(size ((X ~ B) + A) amod Q)
> // align Q
> }
>
> where
> N1 = ((X ~ B) + A) ~ Q)
>
> ```
>
> All non-padding fields are before the critical type, thus this layout already satisfies our desired condition.
>
> Case 2:
>
> All other fields are after the tail.
>
> The layout can be broken into four parts:
>
> - Tail(size A, align B)
> - Padding to Y
> - After(size X, align Y)
> - Padding to Q
>
> ```struct
> struct(size N2, align Q) {
> // align Q
> Tail(size A, align B)
> Padding(size A amod Y)
> // align Y
> After(size X, align Y)
> Padding(size ((A ~ Y) + X) amod Q)
> // align Q
> }
>
> where
> N2 = ((A ~ Y) + X) ~ Q
>
> ```
>
> By definition:
> `B ≤ Q`.
> `Q mod B = 0`.
> `A mod B = 0`. `Y ≤ Q`.
> `Q mod Y = 0`.
> `X mod Y = 0`.
> `N1 mod Q = 0`.
> `N2 mod Q = 0`.
>
> > **failure**
> >
> > We can convert this to the layout in case 1 by setting `Before(size X, align Y) = After(size X, align Y)`. We prove this does not increase the size.
> >
> > Proof:
> >
> > ```rust
> > N1 ≤ N2
> > ((X ~ B) + A) ~ Q) ≤ ((A ~ Y) + X) ~ Q)
> > let N'1 = (X ~ B) + A
> > = X + (X amod B) + A
> > let N'2 = (A ~ Y) + X
> > = A + (A amod Y) + X
> > N'1 ~ Q ≤ N'2 ~ Q
> > N'1 + (N'1 amod Q) ≤ N'2 + (N'2 amod Q)
> > (N'1 amod Q) - (N'2 amod Q) ≤ N'2 - N'1
> > (N'1 amod Q) - (N'2 amod Q) ≤ A + (A amod Y) + X - (X + (X amod B) + A)
> > (N'1 amod Q) - (N'2 amod Q) ≤ (A amod Y) - (X amod B)
> > ???
> >
> > ```
>
> > **failure**
> >
> > Reorder to
> >
> > - After(size X, align Y)
> > - Padding(size ((A ~ Y) + X) amod Q)
> > - Tail(size A, align B)
> > - Padding(size A amod Y)
> >
> > The overall size/align trivially stays the same, and we only need to prove that Tail is sufficiently aligned to B.
> >
> > ```rust
> > (X + (((A ~ Y) + X) amod Q)) mod B = 0
> > ???
> >
> > ```
>
> Case 3:
>
> There are fields before and after the tail.
>
> The layout can be broken into six parts:
>
> - Prior(size I, align J)
> - Padding to B
> - Tail(size A, align B)
> - Padding to V
> - Latter(size U, align V)
> - Padding to Q
>
> Strategy: switch Prior/Tail along with padding to maybe reduce to case 2?
Fridge thought even though it's way too late to be doing formal proofs: I was assuming that the noncritical blobs also had a size multiple of alignment, and that's not necessarily the case. Additionally, a following field blob is not necessarily aligned to the maximum of its internal field allotments.
Even forgetting these things I got horribly stuck to not remembering how to do this kind of modular reasoning over multiple rings simultaneously — if I ever knew at that
---
### Author:  [@CAD97](https://internals.rust-lang.org/u/CAD97)
#### Post date: [June 24, 2022, 6:49am UTC](https://internals.rust-lang.org/t/pre-rfc-improved-unsizing/16861/15 "2022-06-24T06:49:35Z")
The main thing that needs to be provoked for a counterexample is an unsizable tail with padding after it (this occurs to pad to the whole structure alignment). The hard part is doing so with a structure where enough fields can be niched into that space to save an alignment size. The spare unused capacity after the unsizable tail is by definition capped at `align_of(Whole) - align_of(Tail)`, so to save an alignment size, some padding before the tail must exist to be able to combine with the trailing padding to make enough space to shrink the type.
---
### Author:  [@bjorn3](https://internals.rust-lang.org/u/bjorn3)
#### Post date: [June 24, 2022, 7:17am UTC](https://internals.rust-lang.org/t/pre-rfc-improved-unsizing/16861/16 "2022-06-24T07:17:26Z")
The unsizable field is always last. For structs the padding before the field can be easily calculated using a field offset and the alignment stored in the metadata. For enums it would require reading which variant is the current variant and matching on this. This is a lot more complex and means that taking the address of a field requires a read of the pointee, which may be invalid for raw pointers.
---
### Author:  [@quaternic](https://internals.rust-lang.org/u/quaternic)
#### Post date: [June 24, 2022, 9:15am UTC](https://internals.rust-lang.org/t/pre-rfc-improved-unsizing/16861/17 "2022-06-24T09:15:02Z")
> [@CAD97](#):
>
> The theorem to prove is that given any layout, you can construct a layout at least as good with the desired field in the unsizing location.
Assuming I understood the problem correctly, here's an algorithmic proof:
Suppose the type's alignment requirement is B.
for A in [1,2,4,...,B/4,B/2]:
1. Gather the fields with alignment A together.
2. If their total size is not a multiple of the next alignment (2A), add one A-byte padding element to fix that
3. Reorder these fields arbitrarily (they have the same alignment)
4. Replace these fields (including the possible padding element) with a single tuple with 2A-alignment (this will be included in step 1 on the next iteration)
When done you only have fields of the maximum alignment B, so no more padding is required. Total padding added is at most `1+2+4+...+B/4+B/2 = B-1` bytes, so it is minimal as the padded size must be a multiple of B. Any specific field can be made the last in the struct by doing so in every step 3. (You can get much more freedom in step 4 by pairing the fields into multiple chunks, each a multiple of 2A in size.)
---
### Author:  [@CraftSpider](https://internals.rust-lang.org/u/CraftSpider)
#### Post date: [June 24, 2022, 2:59pm UTC](https://internals.rust-lang.org/t/pre-rfc-improved-unsizing/16861/18 "2022-06-24T14:59:36Z")
I'm not 100%, but I think that works? If the last field is unsize, we can always align it into last, and if not, we just don't care. And depending on when layout is decided, we may even be able to only do it when `Unsize` is implemented.
---
### Author:  [@CraftSpider](https://internals.rust-lang.org/u/CraftSpider)
#### Post date: [June 24, 2022, 3:06pm UTC](https://internals.rust-lang.org/t/pre-rfc-improved-unsizing/16861/19 "2022-06-24T15:06:15Z")
I realized I didn't respond to the last thing, about 'future ideas' - I have vague ideas about some `#[metadata]` attribute or something, but I think your `DynSized` proposal would fulfill that requirement, and combined with this, may even entirely fulfill my usability desires.
---
### Author:  [@InfernoDeity](https://internals.rust-lang.org/u/InfernoDeity)
#### Post date: [June 24, 2022, 10:45pm UTC](https://internals.rust-lang.org/t/pre-rfc-improved-unsizing/16861/20 "2022-06-24T22:45:46Z")
I'd note that in this case, it's entirely possible that `Object` and `SizedObject` use different layouts, and in particular: `fields` be at a different offset in `SizedObject` and `Object`. As a practical example, if `*const Field` was something with more alignment (say, a simd type), then then using alignment-sorting, `fields` would come before `name` in `SizedObject`, but not in `Object`. This change would effectively enjoin the compiler from ever reordering the last field of a structure relative to any other field, which can have significant impact on its ability to lay types out the most efficiently.
[Next page](https://internals.rust-lang.org/t/pre-rfc-improved-unsizing/16861.md?page=2)