rustc_abi/
layout.rs

1use std::collections::BTreeSet;
2use std::fmt::{self, Write};
3use std::ops::{Bound, Deref};
4use std::{cmp, iter};
5
6use rustc_hashes::Hash64;
7use rustc_index::Idx;
8use rustc_index::bit_set::BitMatrix;
9use tracing::{debug, trace};
10
11use crate::{
12    AbiAlign, Align, BackendRepr, FieldsShape, HasDataLayout, IndexSlice, IndexVec, Integer,
13    LayoutData, Niche, NonZeroUsize, Primitive, ReprOptions, Scalar, Size, StructKind, TagEncoding,
14    Variants, WrappingRange,
15};
16
17mod coroutine;
18mod simple;
19
20#[cfg(feature = "nightly")]
21mod ty;
22
23#[cfg(feature = "nightly")]
24pub use ty::{FIRST_VARIANT, FieldIdx, Layout, TyAbiInterface, TyAndLayout, VariantIdx};
25
26// A variant is absent if it's uninhabited and only has ZST fields.
27// Present uninhabited variants only require space for their fields,
28// but *not* an encoding of the discriminant (e.g., a tag value).
29// See issue #49298 for more details on the need to leave space
30// for non-ZST uninhabited data (mostly partial initialization).
31fn absent<'a, FieldIdx, VariantIdx, F>(fields: &IndexSlice<FieldIdx, F>) -> bool
32where
33    FieldIdx: Idx,
34    VariantIdx: Idx,
35    F: Deref<Target = &'a LayoutData<FieldIdx, VariantIdx>> + fmt::Debug,
36{
37    let uninhabited = fields.iter().any(|f| f.is_uninhabited());
38    // We cannot ignore alignment; that might lead us to entirely discard a variant and
39    // produce an enum that is less aligned than it should be!
40    let is_1zst = fields.iter().all(|f| f.is_1zst());
41    uninhabited && is_1zst
42}
43
44/// Determines towards which end of a struct layout optimizations will try to place the best niches.
45enum NicheBias {
46    Start,
47    End,
48}
49
50#[derive(Copy, Clone, Debug, PartialEq, Eq)]
51pub enum LayoutCalculatorError<F> {
52    /// An unsized type was found in a location where a sized type was expected.
53    ///
54    /// This is not always a compile error, for example if there is a `[T]: Sized`
55    /// bound in a where clause.
56    ///
57    /// Contains the field that was unexpectedly unsized.
58    UnexpectedUnsized(F),
59
60    /// A type was too large for the target platform.
61    SizeOverflow,
62
63    /// A union had no fields.
64    EmptyUnion,
65
66    /// The fields or variants have irreconcilable reprs
67    ReprConflict,
68
69    /// The length of an SIMD type is zero
70    ZeroLengthSimdType,
71
72    /// The length of an SIMD type exceeds the maximum number of lanes
73    OversizedSimdType { max_lanes: u64 },
74
75    /// An element type of an SIMD type isn't a primitive
76    NonPrimitiveSimdType(F),
77}
78
79impl<F> LayoutCalculatorError<F> {
80    pub fn without_payload(&self) -> LayoutCalculatorError<()> {
81        use LayoutCalculatorError::*;
82        match *self {
83            UnexpectedUnsized(_) => UnexpectedUnsized(()),
84            SizeOverflow => SizeOverflow,
85            EmptyUnion => EmptyUnion,
86            ReprConflict => ReprConflict,
87            ZeroLengthSimdType => ZeroLengthSimdType,
88            OversizedSimdType { max_lanes } => OversizedSimdType { max_lanes },
89            NonPrimitiveSimdType(_) => NonPrimitiveSimdType(()),
90        }
91    }
92
93    /// Format an untranslated diagnostic for this type
94    ///
95    /// Intended for use by rust-analyzer, as neither it nor `rustc_abi` depend on fluent infra.
96    pub fn fallback_fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
97        use LayoutCalculatorError::*;
98        f.write_str(match self {
99            UnexpectedUnsized(_) => "an unsized type was found where a sized type was expected",
100            SizeOverflow => "size overflow",
101            EmptyUnion => "type is a union with no fields",
102            ReprConflict => "type has an invalid repr",
103            ZeroLengthSimdType | OversizedSimdType { .. } | NonPrimitiveSimdType(_) => {
104                "invalid simd type definition"
105            }
106        })
107    }
108}
109
110type LayoutCalculatorResult<FieldIdx, VariantIdx, F> =
111    Result<LayoutData<FieldIdx, VariantIdx>, LayoutCalculatorError<F>>;
112
113#[derive(Clone, Copy, Debug)]
114pub struct LayoutCalculator<Cx> {
115    pub cx: Cx,
116}
117
118impl<Cx: HasDataLayout> LayoutCalculator<Cx> {
119    pub fn new(cx: Cx) -> Self {
120        Self { cx }
121    }
122
123    pub fn array_like<FieldIdx: Idx, VariantIdx: Idx, F>(
124        &self,
125        element: &LayoutData<FieldIdx, VariantIdx>,
126        count_if_sized: Option<u64>, // None for slices
127    ) -> LayoutCalculatorResult<FieldIdx, VariantIdx, F> {
128        let count = count_if_sized.unwrap_or(0);
129        let size =
130            element.size.checked_mul(count, &self.cx).ok_or(LayoutCalculatorError::SizeOverflow)?;
131
132        Ok(LayoutData {
133            variants: Variants::Single { index: VariantIdx::new(0) },
134            fields: FieldsShape::Array { stride: element.size, count },
135            backend_repr: BackendRepr::Memory { sized: count_if_sized.is_some() },
136            largest_niche: element.largest_niche.filter(|_| count != 0),
137            uninhabited: element.uninhabited && count != 0,
138            align: element.align,
139            size,
140            max_repr_align: None,
141            unadjusted_abi_align: element.align.abi,
142            randomization_seed: element.randomization_seed.wrapping_add(Hash64::new(count)),
143        })
144    }
145
146    pub fn simd_type<
147        FieldIdx: Idx,
148        VariantIdx: Idx,
149        F: AsRef<LayoutData<FieldIdx, VariantIdx>> + fmt::Debug,
150    >(
151        &self,
152        element: F,
153        count: u64,
154        repr_packed: bool,
155    ) -> LayoutCalculatorResult<FieldIdx, VariantIdx, F> {
156        let elt = element.as_ref();
157        if count == 0 {
158            return Err(LayoutCalculatorError::ZeroLengthSimdType);
159        } else if count > crate::MAX_SIMD_LANES {
160            return Err(LayoutCalculatorError::OversizedSimdType {
161                max_lanes: crate::MAX_SIMD_LANES,
162            });
163        }
164
165        let BackendRepr::Scalar(e_repr) = elt.backend_repr else {
166            return Err(LayoutCalculatorError::NonPrimitiveSimdType(element));
167        };
168
169        // Compute the size and alignment of the vector
170        let dl = self.cx.data_layout();
171        let size =
172            elt.size.checked_mul(count, dl).ok_or_else(|| LayoutCalculatorError::SizeOverflow)?;
173        let (repr, align) = if repr_packed && !count.is_power_of_two() {
174            // Non-power-of-two vectors have padding up to the next power-of-two.
175            // If we're a packed repr, remove the padding while keeping the alignment as close
176            // to a vector as possible.
177            (BackendRepr::Memory { sized: true }, Align::max_aligned_factor(size))
178        } else {
179            (BackendRepr::SimdVector { element: e_repr, count }, dl.llvmlike_vector_align(size))
180        };
181        let size = size.align_to(align);
182
183        Ok(LayoutData {
184            variants: Variants::Single { index: VariantIdx::new(0) },
185            fields: FieldsShape::Arbitrary {
186                offsets: [Size::ZERO].into(),
187                memory_index: [0].into(),
188            },
189            backend_repr: repr,
190            largest_niche: elt.largest_niche,
191            uninhabited: false,
192            size,
193            align: AbiAlign::new(align),
194            max_repr_align: None,
195            unadjusted_abi_align: elt.align.abi,
196            randomization_seed: elt.randomization_seed.wrapping_add(Hash64::new(count)),
197        })
198    }
199
200    /// Compute the layout for a coroutine.
201    ///
202    /// This uses dedicated code instead of [`Self::layout_of_struct_or_enum`], as coroutine
203    /// fields may be shared between multiple variants (see the [`coroutine`] module for details).
204    pub fn coroutine<
205        'a,
206        F: Deref<Target = &'a LayoutData<FieldIdx, VariantIdx>> + fmt::Debug + Copy,
207        VariantIdx: Idx,
208        FieldIdx: Idx,
209        LocalIdx: Idx,
210    >(
211        &self,
212        local_layouts: &IndexSlice<LocalIdx, F>,
213        prefix_layouts: IndexVec<FieldIdx, F>,
214        variant_fields: &IndexSlice<VariantIdx, IndexVec<FieldIdx, LocalIdx>>,
215        storage_conflicts: &BitMatrix<LocalIdx, LocalIdx>,
216        tag_to_layout: impl Fn(Scalar) -> F,
217    ) -> LayoutCalculatorResult<FieldIdx, VariantIdx, F> {
218        coroutine::layout(
219            self,
220            local_layouts,
221            prefix_layouts,
222            variant_fields,
223            storage_conflicts,
224            tag_to_layout,
225        )
226    }
227
228    pub fn univariant<
229        'a,
230        FieldIdx: Idx,
231        VariantIdx: Idx,
232        F: Deref<Target = &'a LayoutData<FieldIdx, VariantIdx>> + fmt::Debug + Copy,
233    >(
234        &self,
235        fields: &IndexSlice<FieldIdx, F>,
236        repr: &ReprOptions,
237        kind: StructKind,
238    ) -> LayoutCalculatorResult<FieldIdx, VariantIdx, F> {
239        let dl = self.cx.data_layout();
240        let layout = self.univariant_biased(fields, repr, kind, NicheBias::Start);
241        // Enums prefer niches close to the beginning or the end of the variants so that other
242        // (smaller) data-carrying variants can be packed into the space after/before the niche.
243        // If the default field ordering does not give us a niche at the front then we do a second
244        // run and bias niches to the right and then check which one is closer to one of the
245        // struct's edges.
246        if let Ok(layout) = &layout {
247            // Don't try to calculate an end-biased layout for unsizable structs,
248            // otherwise we could end up with different layouts for
249            // Foo<Type> and Foo<dyn Trait> which would break unsizing.
250            if !matches!(kind, StructKind::MaybeUnsized) {
251                if let Some(niche) = layout.largest_niche {
252                    let head_space = niche.offset.bytes();
253                    let niche_len = niche.value.size(dl).bytes();
254                    let tail_space = layout.size.bytes() - head_space - niche_len;
255
256                    // This may end up doing redundant work if the niche is already in the last
257                    // field (e.g. a trailing bool) and there is tail padding. But it's non-trivial
258                    // to get the unpadded size so we try anyway.
259                    if fields.len() > 1 && head_space != 0 && tail_space > 0 {
260                        let alt_layout = self
261                            .univariant_biased(fields, repr, kind, NicheBias::End)
262                            .expect("alt layout should always work");
263                        let alt_niche = alt_layout
264                            .largest_niche
265                            .expect("alt layout should have a niche like the regular one");
266                        let alt_head_space = alt_niche.offset.bytes();
267                        let alt_niche_len = alt_niche.value.size(dl).bytes();
268                        let alt_tail_space =
269                            alt_layout.size.bytes() - alt_head_space - alt_niche_len;
270
271                        debug_assert_eq!(layout.size.bytes(), alt_layout.size.bytes());
272
273                        let prefer_alt_layout =
274                            alt_head_space > head_space && alt_head_space > tail_space;
275
276                        debug!(
277                            "sz: {}, default_niche_at: {}+{}, default_tail_space: {}, alt_niche_at/head_space: {}+{}, alt_tail: {}, num_fields: {}, better: {}\n\
278                            layout: {}\n\
279                            alt_layout: {}\n",
280                            layout.size.bytes(),
281                            head_space,
282                            niche_len,
283                            tail_space,
284                            alt_head_space,
285                            alt_niche_len,
286                            alt_tail_space,
287                            layout.fields.count(),
288                            prefer_alt_layout,
289                            self.format_field_niches(layout, fields),
290                            self.format_field_niches(&alt_layout, fields),
291                        );
292
293                        if prefer_alt_layout {
294                            return Ok(alt_layout);
295                        }
296                    }
297                }
298            }
299        }
300        layout
301    }
302
303    pub fn layout_of_struct_or_enum<
304        'a,
305        FieldIdx: Idx,
306        VariantIdx: Idx,
307        F: Deref<Target = &'a LayoutData<FieldIdx, VariantIdx>> + fmt::Debug + Copy,
308    >(
309        &self,
310        repr: &ReprOptions,
311        variants: &IndexSlice<VariantIdx, IndexVec<FieldIdx, F>>,
312        is_enum: bool,
313        is_special_no_niche: bool,
314        scalar_valid_range: (Bound<u128>, Bound<u128>),
315        discr_range_of_repr: impl Fn(i128, i128) -> (Integer, bool),
316        discriminants: impl Iterator<Item = (VariantIdx, i128)>,
317        always_sized: bool,
318    ) -> LayoutCalculatorResult<FieldIdx, VariantIdx, F> {
319        let (present_first, present_second) = {
320            let mut present_variants = variants
321                .iter_enumerated()
322                .filter_map(|(i, v)| if !repr.c() && absent(v) { None } else { Some(i) });
323            (present_variants.next(), present_variants.next())
324        };
325        let present_first = match present_first {
326            Some(present_first) => present_first,
327            // Uninhabited because it has no variants, or only absent ones.
328            None if is_enum => {
329                return Ok(LayoutData::never_type(&self.cx));
330            }
331            // If it's a struct, still compute a layout so that we can still compute the
332            // field offsets.
333            None => VariantIdx::new(0),
334        };
335
336        // take the struct path if it is an actual struct
337        if !is_enum ||
338            // or for optimizing univariant enums
339            (present_second.is_none() && !repr.inhibit_enum_layout_opt())
340        {
341            self.layout_of_struct(
342                repr,
343                variants,
344                is_enum,
345                is_special_no_niche,
346                scalar_valid_range,
347                always_sized,
348                present_first,
349            )
350        } else {
351            // At this point, we have handled all unions and
352            // structs. (We have also handled univariant enums
353            // that allow representation optimization.)
354            assert!(is_enum);
355            self.layout_of_enum(repr, variants, discr_range_of_repr, discriminants)
356        }
357    }
358
359    pub fn layout_of_union<
360        'a,
361        FieldIdx: Idx,
362        VariantIdx: Idx,
363        F: Deref<Target = &'a LayoutData<FieldIdx, VariantIdx>> + fmt::Debug + Copy,
364    >(
365        &self,
366        repr: &ReprOptions,
367        variants: &IndexSlice<VariantIdx, IndexVec<FieldIdx, F>>,
368    ) -> LayoutCalculatorResult<FieldIdx, VariantIdx, F> {
369        let dl = self.cx.data_layout();
370        let mut align = if repr.pack.is_some() { dl.i8_align } else { dl.aggregate_align };
371        let mut max_repr_align = repr.align;
372
373        // If all the non-ZST fields have the same repr and union repr optimizations aren't
374        // disabled, we can use that common repr for the union as a whole.
375        struct AbiMismatch;
376        let mut common_non_zst_repr_and_align = if repr.inhibits_union_abi_opt() {
377            // Can't optimize
378            Err(AbiMismatch)
379        } else {
380            Ok(None)
381        };
382
383        let mut size = Size::ZERO;
384        let only_variant_idx = VariantIdx::new(0);
385        let only_variant = &variants[only_variant_idx];
386        for field in only_variant {
387            if field.is_unsized() {
388                return Err(LayoutCalculatorError::UnexpectedUnsized(*field));
389            }
390
391            align = align.max(field.align.abi);
392            max_repr_align = max_repr_align.max(field.max_repr_align);
393            size = cmp::max(size, field.size);
394
395            if field.is_zst() {
396                // Nothing more to do for ZST fields
397                continue;
398            }
399
400            if let Ok(common) = common_non_zst_repr_and_align {
401                // Discard valid range information and allow undef
402                let field_abi = field.backend_repr.to_union();
403
404                if let Some((common_abi, common_align)) = common {
405                    if common_abi != field_abi {
406                        // Different fields have different ABI: disable opt
407                        common_non_zst_repr_and_align = Err(AbiMismatch);
408                    } else {
409                        // Fields with the same non-Aggregate ABI should also
410                        // have the same alignment
411                        if !matches!(common_abi, BackendRepr::Memory { .. }) {
412                            assert_eq!(
413                                common_align, field.align.abi,
414                                "non-Aggregate field with matching ABI but differing alignment"
415                            );
416                        }
417                    }
418                } else {
419                    // First non-ZST field: record its ABI and alignment
420                    common_non_zst_repr_and_align = Ok(Some((field_abi, field.align.abi)));
421                }
422            }
423        }
424
425        if let Some(pack) = repr.pack {
426            align = align.min(pack);
427        }
428        // The unadjusted ABI alignment does not include repr(align), but does include repr(pack).
429        // See documentation on `LayoutData::unadjusted_abi_align`.
430        let unadjusted_abi_align = align;
431        if let Some(repr_align) = repr.align {
432            align = align.max(repr_align);
433        }
434        // `align` must not be modified after this, or `unadjusted_abi_align` could be inaccurate.
435        let align = align;
436
437        // If all non-ZST fields have the same ABI, we may forward that ABI
438        // for the union as a whole, unless otherwise inhibited.
439        let backend_repr = match common_non_zst_repr_and_align {
440            Err(AbiMismatch) | Ok(None) => BackendRepr::Memory { sized: true },
441            Ok(Some((repr, _))) => match repr {
442                // Mismatched alignment (e.g. union is #[repr(packed)]): disable opt
443                BackendRepr::Scalar(_) | BackendRepr::ScalarPair(_, _)
444                    if repr.scalar_align(dl).unwrap() != align =>
445                {
446                    BackendRepr::Memory { sized: true }
447                }
448                // Vectors require at least element alignment, else disable the opt
449                BackendRepr::SimdVector { element, count: _ } if element.align(dl).abi > align => {
450                    BackendRepr::Memory { sized: true }
451                }
452                // the alignment tests passed and we can use this
453                BackendRepr::Scalar(..)
454                | BackendRepr::ScalarPair(..)
455                | BackendRepr::SimdVector { .. }
456                | BackendRepr::Memory { .. } => repr,
457            },
458        };
459
460        let Some(union_field_count) = NonZeroUsize::new(only_variant.len()) else {
461            return Err(LayoutCalculatorError::EmptyUnion);
462        };
463
464        let combined_seed = only_variant
465            .iter()
466            .map(|v| v.randomization_seed)
467            .fold(repr.field_shuffle_seed, |acc, seed| acc.wrapping_add(seed));
468
469        Ok(LayoutData {
470            variants: Variants::Single { index: only_variant_idx },
471            fields: FieldsShape::Union(union_field_count),
472            backend_repr,
473            largest_niche: None,
474            uninhabited: false,
475            align: AbiAlign::new(align),
476            size: size.align_to(align),
477            max_repr_align,
478            unadjusted_abi_align,
479            randomization_seed: combined_seed,
480        })
481    }
482
483    /// single-variant enums are just structs, if you think about it
484    fn layout_of_struct<
485        'a,
486        FieldIdx: Idx,
487        VariantIdx: Idx,
488        F: Deref<Target = &'a LayoutData<FieldIdx, VariantIdx>> + fmt::Debug + Copy,
489    >(
490        &self,
491        repr: &ReprOptions,
492        variants: &IndexSlice<VariantIdx, IndexVec<FieldIdx, F>>,
493        is_enum: bool,
494        is_special_no_niche: bool,
495        scalar_valid_range: (Bound<u128>, Bound<u128>),
496        always_sized: bool,
497        present_first: VariantIdx,
498    ) -> LayoutCalculatorResult<FieldIdx, VariantIdx, F> {
499        // Struct, or univariant enum equivalent to a struct.
500        // (Typechecking will reject discriminant-sizing attrs.)
501
502        let dl = self.cx.data_layout();
503        let v = present_first;
504        let kind = if is_enum || variants[v].is_empty() || always_sized {
505            StructKind::AlwaysSized
506        } else {
507            StructKind::MaybeUnsized
508        };
509
510        let mut st = self.univariant(&variants[v], repr, kind)?;
511        st.variants = Variants::Single { index: v };
512
513        if is_special_no_niche {
514            let hide_niches = |scalar: &mut _| match scalar {
515                Scalar::Initialized { value, valid_range } => {
516                    *valid_range = WrappingRange::full(value.size(dl))
517                }
518                // Already doesn't have any niches
519                Scalar::Union { .. } => {}
520            };
521            match &mut st.backend_repr {
522                BackendRepr::Scalar(scalar) => hide_niches(scalar),
523                BackendRepr::ScalarPair(a, b) => {
524                    hide_niches(a);
525                    hide_niches(b);
526                }
527                BackendRepr::SimdVector { element, count: _ } => hide_niches(element),
528                BackendRepr::Memory { sized: _ } => {}
529            }
530            st.largest_niche = None;
531            return Ok(st);
532        }
533
534        let (start, end) = scalar_valid_range;
535        match st.backend_repr {
536            BackendRepr::Scalar(ref mut scalar) | BackendRepr::ScalarPair(ref mut scalar, _) => {
537                // Enlarging validity ranges would result in missed
538                // optimizations, *not* wrongly assuming the inner
539                // value is valid. e.g. unions already enlarge validity ranges,
540                // because the values may be uninitialized.
541                //
542                // Because of that we only check that the start and end
543                // of the range is representable with this scalar type.
544
545                let max_value = scalar.size(dl).unsigned_int_max();
546                if let Bound::Included(start) = start {
547                    // FIXME(eddyb) this might be incorrect - it doesn't
548                    // account for wrap-around (end < start) ranges.
549                    assert!(start <= max_value, "{start} > {max_value}");
550                    scalar.valid_range_mut().start = start;
551                }
552                if let Bound::Included(end) = end {
553                    // FIXME(eddyb) this might be incorrect - it doesn't
554                    // account for wrap-around (end < start) ranges.
555                    assert!(end <= max_value, "{end} > {max_value}");
556                    scalar.valid_range_mut().end = end;
557                }
558
559                // Update `largest_niche` if we have introduced a larger niche.
560                let niche = Niche::from_scalar(dl, Size::ZERO, *scalar);
561                if let Some(niche) = niche {
562                    match st.largest_niche {
563                        Some(largest_niche) => {
564                            // Replace the existing niche even if they're equal,
565                            // because this one is at a lower offset.
566                            if largest_niche.available(dl) <= niche.available(dl) {
567                                st.largest_niche = Some(niche);
568                            }
569                        }
570                        None => st.largest_niche = Some(niche),
571                    }
572                }
573            }
574            _ => assert!(
575                start == Bound::Unbounded && end == Bound::Unbounded,
576                "nonscalar layout for layout_scalar_valid_range type: {st:#?}",
577            ),
578        }
579
580        Ok(st)
581    }
582
583    fn layout_of_enum<
584        'a,
585        FieldIdx: Idx,
586        VariantIdx: Idx,
587        F: Deref<Target = &'a LayoutData<FieldIdx, VariantIdx>> + fmt::Debug + Copy,
588    >(
589        &self,
590        repr: &ReprOptions,
591        variants: &IndexSlice<VariantIdx, IndexVec<FieldIdx, F>>,
592        discr_range_of_repr: impl Fn(i128, i128) -> (Integer, bool),
593        discriminants: impl Iterator<Item = (VariantIdx, i128)>,
594    ) -> LayoutCalculatorResult<FieldIdx, VariantIdx, F> {
595        let dl = self.cx.data_layout();
596        // bail if the enum has an incoherent repr that cannot be computed
597        if repr.packed() {
598            return Err(LayoutCalculatorError::ReprConflict);
599        }
600
601        let calculate_niche_filling_layout = || -> Option<LayoutData<FieldIdx, VariantIdx>> {
602            if repr.inhibit_enum_layout_opt() {
603                return None;
604            }
605
606            if variants.len() < 2 {
607                return None;
608            }
609
610            let mut align = dl.aggregate_align;
611            let mut max_repr_align = repr.align;
612            let mut unadjusted_abi_align = align;
613
614            let mut variant_layouts = variants
615                .iter_enumerated()
616                .map(|(j, v)| {
617                    let mut st = self.univariant(v, repr, StructKind::AlwaysSized).ok()?;
618                    st.variants = Variants::Single { index: j };
619
620                    align = align.max(st.align.abi);
621                    max_repr_align = max_repr_align.max(st.max_repr_align);
622                    unadjusted_abi_align = unadjusted_abi_align.max(st.unadjusted_abi_align);
623
624                    Some(st)
625                })
626                .collect::<Option<IndexVec<VariantIdx, _>>>()?;
627
628            let largest_variant_index = variant_layouts
629                .iter_enumerated()
630                .max_by_key(|(_i, layout)| layout.size.bytes())
631                .map(|(i, _layout)| i)?;
632
633            let all_indices = variants.indices();
634            let needs_disc =
635                |index: VariantIdx| index != largest_variant_index && !absent(&variants[index]);
636            let niche_variants = all_indices.clone().find(|v| needs_disc(*v)).unwrap()
637                ..=all_indices.rev().find(|v| needs_disc(*v)).unwrap();
638
639            let count =
640                (niche_variants.end().index() as u128 - niche_variants.start().index() as u128) + 1;
641
642            // Use the largest niche in the largest variant.
643            let niche = variant_layouts[largest_variant_index].largest_niche?;
644            let (niche_start, niche_scalar) = niche.reserve(dl, count)?;
645            let niche_offset = niche.offset;
646            let niche_size = niche.value.size(dl);
647            let size = variant_layouts[largest_variant_index].size.align_to(align);
648
649            let all_variants_fit = variant_layouts.iter_enumerated_mut().all(|(i, layout)| {
650                if i == largest_variant_index {
651                    return true;
652                }
653
654                layout.largest_niche = None;
655
656                if layout.size <= niche_offset {
657                    // This variant will fit before the niche.
658                    return true;
659                }
660
661                // Determine if it'll fit after the niche.
662                let this_align = layout.align.abi;
663                let this_offset = (niche_offset + niche_size).align_to(this_align);
664
665                if this_offset + layout.size > size {
666                    return false;
667                }
668
669                // It'll fit, but we need to make some adjustments.
670                match layout.fields {
671                    FieldsShape::Arbitrary { ref mut offsets, .. } => {
672                        for offset in offsets.iter_mut() {
673                            *offset += this_offset;
674                        }
675                    }
676                    FieldsShape::Primitive | FieldsShape::Array { .. } | FieldsShape::Union(..) => {
677                        panic!("Layout of fields should be Arbitrary for variants")
678                    }
679                }
680
681                // It can't be a Scalar or ScalarPair because the offset isn't 0.
682                if !layout.is_uninhabited() {
683                    layout.backend_repr = BackendRepr::Memory { sized: true };
684                }
685                layout.size += this_offset;
686
687                true
688            });
689
690            if !all_variants_fit {
691                return None;
692            }
693
694            let largest_niche = Niche::from_scalar(dl, niche_offset, niche_scalar);
695
696            let others_zst = variant_layouts
697                .iter_enumerated()
698                .all(|(i, layout)| i == largest_variant_index || layout.size == Size::ZERO);
699            let same_size = size == variant_layouts[largest_variant_index].size;
700            let same_align = align == variant_layouts[largest_variant_index].align.abi;
701
702            let uninhabited = variant_layouts.iter().all(|v| v.is_uninhabited());
703            let abi = if same_size && same_align && others_zst {
704                match variant_layouts[largest_variant_index].backend_repr {
705                    // When the total alignment and size match, we can use the
706                    // same ABI as the scalar variant with the reserved niche.
707                    BackendRepr::Scalar(_) => BackendRepr::Scalar(niche_scalar),
708                    BackendRepr::ScalarPair(first, second) => {
709                        // Only the niche is guaranteed to be initialised,
710                        // so use union layouts for the other primitive.
711                        if niche_offset == Size::ZERO {
712                            BackendRepr::ScalarPair(niche_scalar, second.to_union())
713                        } else {
714                            BackendRepr::ScalarPair(first.to_union(), niche_scalar)
715                        }
716                    }
717                    _ => BackendRepr::Memory { sized: true },
718                }
719            } else {
720                BackendRepr::Memory { sized: true }
721            };
722
723            let combined_seed = variant_layouts
724                .iter()
725                .map(|v| v.randomization_seed)
726                .fold(repr.field_shuffle_seed, |acc, seed| acc.wrapping_add(seed));
727
728            let layout = LayoutData {
729                variants: Variants::Multiple {
730                    tag: niche_scalar,
731                    tag_encoding: TagEncoding::Niche {
732                        untagged_variant: largest_variant_index,
733                        niche_variants,
734                        niche_start,
735                    },
736                    tag_field: FieldIdx::new(0),
737                    variants: variant_layouts,
738                },
739                fields: FieldsShape::Arbitrary {
740                    offsets: [niche_offset].into(),
741                    memory_index: [0].into(),
742                },
743                backend_repr: abi,
744                largest_niche,
745                uninhabited,
746                size,
747                align: AbiAlign::new(align),
748                max_repr_align,
749                unadjusted_abi_align,
750                randomization_seed: combined_seed,
751            };
752
753            Some(layout)
754        };
755
756        let niche_filling_layout = calculate_niche_filling_layout();
757
758        let discr_type = repr.discr_type();
759        let discr_int = Integer::from_attr(dl, discr_type);
760        // Because we can only represent one range of valid values, we'll look for the
761        // largest range of invalid values and pick everything else as the range of valid
762        // values.
763
764        // First we need to sort the possible discriminant values so that we can look for the largest gap:
765        let valid_discriminants: BTreeSet<i128> = discriminants
766            .filter(|&(i, _)| repr.c() || variants[i].iter().all(|f| !f.is_uninhabited()))
767            .map(|(_, val)| {
768                if discr_type.is_signed() {
769                    // sign extend the raw representation to be an i128
770                    // FIXME: do this at the discriminant iterator creation sites
771                    discr_int.size().sign_extend(val as u128)
772                } else {
773                    val
774                }
775            })
776            .collect();
777        trace!(?valid_discriminants);
778        let discriminants = valid_discriminants.iter().copied();
779        //let next_discriminants = discriminants.clone().cycle().skip(1);
780        let next_discriminants =
781            discriminants.clone().chain(valid_discriminants.first().copied()).skip(1);
782        // Iterate over pairs of each discriminant together with the next one.
783        // Since they were sorted, we can now compute the niche sizes and pick the largest.
784        let discriminants = discriminants.zip(next_discriminants);
785        let largest_niche = discriminants.max_by_key(|&(start, end)| {
786            trace!(?start, ?end);
787            // If this is a wraparound range, the niche size is `MAX - abs(diff)`, as the diff between
788            // the two end points is actually the size of the valid discriminants.
789            let dist = if start > end {
790                // Overflow can happen for 128 bit discriminants if `end` is negative.
791                // But in that case casting to `u128` still gets us the right value,
792                // as the distance must be positive if the lhs of the subtraction is larger than the rhs.
793                let dist = start.wrapping_sub(end);
794                if discr_type.is_signed() {
795                    discr_int.signed_max().wrapping_sub(dist) as u128
796                } else {
797                    discr_int.size().unsigned_int_max() - dist as u128
798                }
799            } else {
800                // Overflow can happen for 128 bit discriminants if `start` is negative.
801                // But in that case casting to `u128` still gets us the right value,
802                // as the distance must be positive if the lhs of the subtraction is larger than the rhs.
803                end.wrapping_sub(start) as u128
804            };
805            trace!(?dist);
806            dist
807        });
808        trace!(?largest_niche);
809
810        // `max` is the last valid discriminant before the largest niche
811        // `min` is the first valid discriminant after the largest niche
812        let (max, min) = largest_niche
813            // We might have no inhabited variants, so pretend there's at least one.
814            .unwrap_or((0, 0));
815        let (min_ity, signed) = discr_range_of_repr(min, max); //Integer::repr_discr(tcx, ty, &repr, min, max);
816
817        let mut align = dl.aggregate_align;
818        let mut max_repr_align = repr.align;
819        let mut unadjusted_abi_align = align;
820
821        let mut size = Size::ZERO;
822
823        // We're interested in the smallest alignment, so start large.
824        let mut start_align = Align::from_bytes(256).unwrap();
825        assert_eq!(Integer::for_align(dl, start_align), None);
826
827        // repr(C) on an enum tells us to make a (tag, union) layout,
828        // so we need to grow the prefix alignment to be at least
829        // the alignment of the union. (This value is used both for
830        // determining the alignment of the overall enum, and the
831        // determining the alignment of the payload after the tag.)
832        let mut prefix_align = min_ity.align(dl).abi;
833        if repr.c() {
834            for fields in variants {
835                for field in fields {
836                    prefix_align = prefix_align.max(field.align.abi);
837                }
838            }
839        }
840
841        // Create the set of structs that represent each variant.
842        let mut layout_variants = variants
843            .iter_enumerated()
844            .map(|(i, field_layouts)| {
845                let mut st = self.univariant(
846                    field_layouts,
847                    repr,
848                    StructKind::Prefixed(min_ity.size(), prefix_align),
849                )?;
850                st.variants = Variants::Single { index: i };
851                // Find the first field we can't move later
852                // to make room for a larger discriminant.
853                for field_idx in st.fields.index_by_increasing_offset() {
854                    let field = &field_layouts[FieldIdx::new(field_idx)];
855                    if !field.is_1zst() {
856                        start_align = start_align.min(field.align.abi);
857                        break;
858                    }
859                }
860                size = cmp::max(size, st.size);
861                align = align.max(st.align.abi);
862                max_repr_align = max_repr_align.max(st.max_repr_align);
863                unadjusted_abi_align = unadjusted_abi_align.max(st.unadjusted_abi_align);
864                Ok(st)
865            })
866            .collect::<Result<IndexVec<VariantIdx, _>, _>>()?;
867
868        // Align the maximum variant size to the largest alignment.
869        size = size.align_to(align);
870
871        // FIXME(oli-obk): deduplicate and harden these checks
872        if size.bytes() >= dl.obj_size_bound() {
873            return Err(LayoutCalculatorError::SizeOverflow);
874        }
875
876        let typeck_ity = Integer::from_attr(dl, repr.discr_type());
877        if typeck_ity < min_ity {
878            // It is a bug if Layout decided on a greater discriminant size than typeck for
879            // some reason at this point (based on values discriminant can take on). Mostly
880            // because this discriminant will be loaded, and then stored into variable of
881            // type calculated by typeck. Consider such case (a bug): typeck decided on
882            // byte-sized discriminant, but layout thinks we need a 16-bit to store all
883            // discriminant values. That would be a bug, because then, in codegen, in order
884            // to store this 16-bit discriminant into 8-bit sized temporary some of the
885            // space necessary to represent would have to be discarded (or layout is wrong
886            // on thinking it needs 16 bits)
887            panic!(
888                "layout decided on a larger discriminant type ({min_ity:?}) than typeck ({typeck_ity:?})"
889            );
890            // However, it is fine to make discr type however large (as an optimisation)
891            // after this point – we’ll just truncate the value we load in codegen.
892        }
893
894        // Check to see if we should use a different type for the
895        // discriminant. We can safely use a type with the same size
896        // as the alignment of the first field of each variant.
897        // We increase the size of the discriminant to avoid LLVM copying
898        // padding when it doesn't need to. This normally causes unaligned
899        // load/stores and excessive memcpy/memset operations. By using a
900        // bigger integer size, LLVM can be sure about its contents and
901        // won't be so conservative.
902
903        // Use the initial field alignment
904        let mut ity = if repr.c() || repr.int.is_some() {
905            min_ity
906        } else {
907            Integer::for_align(dl, start_align).unwrap_or(min_ity)
908        };
909
910        // If the alignment is not larger than the chosen discriminant size,
911        // don't use the alignment as the final size.
912        if ity <= min_ity {
913            ity = min_ity;
914        } else {
915            // Patch up the variants' first few fields.
916            let old_ity_size = min_ity.size();
917            let new_ity_size = ity.size();
918            for variant in &mut layout_variants {
919                match variant.fields {
920                    FieldsShape::Arbitrary { ref mut offsets, .. } => {
921                        for i in offsets {
922                            if *i <= old_ity_size {
923                                assert_eq!(*i, old_ity_size);
924                                *i = new_ity_size;
925                            }
926                        }
927                        // We might be making the struct larger.
928                        if variant.size <= old_ity_size {
929                            variant.size = new_ity_size;
930                        }
931                    }
932                    FieldsShape::Primitive | FieldsShape::Array { .. } | FieldsShape::Union(..) => {
933                        panic!("encountered a non-arbitrary layout during enum layout")
934                    }
935                }
936            }
937        }
938
939        let tag_mask = ity.size().unsigned_int_max();
940        let tag = Scalar::Initialized {
941            value: Primitive::Int(ity, signed),
942            valid_range: WrappingRange {
943                start: (min as u128 & tag_mask),
944                end: (max as u128 & tag_mask),
945            },
946        };
947        let mut abi = BackendRepr::Memory { sized: true };
948
949        let uninhabited = layout_variants.iter().all(|v| v.is_uninhabited());
950        if tag.size(dl) == size {
951            // Make sure we only use scalar layout when the enum is entirely its
952            // own tag (i.e. it has no padding nor any non-ZST variant fields).
953            abi = BackendRepr::Scalar(tag);
954        } else {
955            // Try to use a ScalarPair for all tagged enums.
956            // That's possible only if we can find a common primitive type for all variants.
957            let mut common_prim = None;
958            let mut common_prim_initialized_in_all_variants = true;
959            for (field_layouts, layout_variant) in iter::zip(variants, &layout_variants) {
960                let FieldsShape::Arbitrary { ref offsets, .. } = layout_variant.fields else {
961                    panic!("encountered a non-arbitrary layout during enum layout");
962                };
963                // We skip *all* ZST here and later check if we are good in terms of alignment.
964                // This lets us handle some cases involving aligned ZST.
965                let mut fields = iter::zip(field_layouts, offsets).filter(|p| !p.0.is_zst());
966                let (field, offset) = match (fields.next(), fields.next()) {
967                    (None, None) => {
968                        common_prim_initialized_in_all_variants = false;
969                        continue;
970                    }
971                    (Some(pair), None) => pair,
972                    _ => {
973                        common_prim = None;
974                        break;
975                    }
976                };
977                let prim = match field.backend_repr {
978                    BackendRepr::Scalar(scalar) => {
979                        common_prim_initialized_in_all_variants &=
980                            matches!(scalar, Scalar::Initialized { .. });
981                        scalar.primitive()
982                    }
983                    _ => {
984                        common_prim = None;
985                        break;
986                    }
987                };
988                if let Some((old_prim, common_offset)) = common_prim {
989                    // All variants must be at the same offset
990                    if offset != common_offset {
991                        common_prim = None;
992                        break;
993                    }
994                    // This is pretty conservative. We could go fancier
995                    // by realising that (u8, u8) could just cohabit with
996                    // u16 or even u32.
997                    let new_prim = match (old_prim, prim) {
998                        // Allow all identical primitives.
999                        (x, y) if x == y => x,
1000                        // Allow integers of the same size with differing signedness.
1001                        // We arbitrarily choose the signedness of the first variant.
1002                        (p @ Primitive::Int(x, _), Primitive::Int(y, _)) if x == y => p,
1003                        // Allow integers mixed with pointers of the same layout.
1004                        // We must represent this using a pointer, to avoid
1005                        // roundtripping pointers through ptrtoint/inttoptr.
1006                        (p @ Primitive::Pointer(_), i @ Primitive::Int(..))
1007                        | (i @ Primitive::Int(..), p @ Primitive::Pointer(_))
1008                            if p.size(dl) == i.size(dl) && p.align(dl) == i.align(dl) =>
1009                        {
1010                            p
1011                        }
1012                        _ => {
1013                            common_prim = None;
1014                            break;
1015                        }
1016                    };
1017                    // We may be updating the primitive here, for example from int->ptr.
1018                    common_prim = Some((new_prim, common_offset));
1019                } else {
1020                    common_prim = Some((prim, offset));
1021                }
1022            }
1023            if let Some((prim, offset)) = common_prim {
1024                let prim_scalar = if common_prim_initialized_in_all_variants {
1025                    let size = prim.size(dl);
1026                    assert!(size.bits() <= 128);
1027                    Scalar::Initialized { value: prim, valid_range: WrappingRange::full(size) }
1028                } else {
1029                    // Common prim might be uninit.
1030                    Scalar::Union { value: prim }
1031                };
1032                let pair =
1033                    LayoutData::<FieldIdx, VariantIdx>::scalar_pair(&self.cx, tag, prim_scalar);
1034                let pair_offsets = match pair.fields {
1035                    FieldsShape::Arbitrary { ref offsets, ref memory_index } => {
1036                        assert_eq!(memory_index.raw, [0, 1]);
1037                        offsets
1038                    }
1039                    _ => panic!("encountered a non-arbitrary layout during enum layout"),
1040                };
1041                if pair_offsets[FieldIdx::new(0)] == Size::ZERO
1042                    && pair_offsets[FieldIdx::new(1)] == *offset
1043                    && align == pair.align.abi
1044                    && size == pair.size
1045                {
1046                    // We can use `ScalarPair` only when it matches our
1047                    // already computed layout (including `#[repr(C)]`).
1048                    abi = pair.backend_repr;
1049                }
1050            }
1051        }
1052
1053        // If we pick a "clever" (by-value) ABI, we might have to adjust the ABI of the
1054        // variants to ensure they are consistent. This is because a downcast is
1055        // semantically a NOP, and thus should not affect layout.
1056        if matches!(abi, BackendRepr::Scalar(..) | BackendRepr::ScalarPair(..)) {
1057            for variant in &mut layout_variants {
1058                // We only do this for variants with fields; the others are not accessed anyway.
1059                // Also do not overwrite any already existing "clever" ABIs.
1060                if variant.fields.count() > 0
1061                    && matches!(variant.backend_repr, BackendRepr::Memory { .. })
1062                {
1063                    variant.backend_repr = abi;
1064                    // Also need to bump up the size and alignment, so that the entire value fits
1065                    // in here.
1066                    variant.size = cmp::max(variant.size, size);
1067                    variant.align.abi = cmp::max(variant.align.abi, align);
1068                }
1069            }
1070        }
1071
1072        let largest_niche = Niche::from_scalar(dl, Size::ZERO, tag);
1073
1074        let combined_seed = layout_variants
1075            .iter()
1076            .map(|v| v.randomization_seed)
1077            .fold(repr.field_shuffle_seed, |acc, seed| acc.wrapping_add(seed));
1078
1079        let tagged_layout = LayoutData {
1080            variants: Variants::Multiple {
1081                tag,
1082                tag_encoding: TagEncoding::Direct,
1083                tag_field: FieldIdx::new(0),
1084                variants: layout_variants,
1085            },
1086            fields: FieldsShape::Arbitrary {
1087                offsets: [Size::ZERO].into(),
1088                memory_index: [0].into(),
1089            },
1090            largest_niche,
1091            uninhabited,
1092            backend_repr: abi,
1093            align: AbiAlign::new(align),
1094            size,
1095            max_repr_align,
1096            unadjusted_abi_align,
1097            randomization_seed: combined_seed,
1098        };
1099
1100        let best_layout = match (tagged_layout, niche_filling_layout) {
1101            (tl, Some(nl)) => {
1102                // Pick the smaller layout; otherwise,
1103                // pick the layout with the larger niche; otherwise,
1104                // pick tagged as it has simpler codegen.
1105                use cmp::Ordering::*;
1106                let niche_size = |l: &LayoutData<FieldIdx, VariantIdx>| {
1107                    l.largest_niche.map_or(0, |n| n.available(dl))
1108                };
1109                match (tl.size.cmp(&nl.size), niche_size(&tl).cmp(&niche_size(&nl))) {
1110                    (Greater, _) => nl,
1111                    (Equal, Less) => nl,
1112                    _ => tl,
1113                }
1114            }
1115            (tl, None) => tl,
1116        };
1117
1118        Ok(best_layout)
1119    }
1120
1121    fn univariant_biased<
1122        'a,
1123        FieldIdx: Idx,
1124        VariantIdx: Idx,
1125        F: Deref<Target = &'a LayoutData<FieldIdx, VariantIdx>> + fmt::Debug + Copy,
1126    >(
1127        &self,
1128        fields: &IndexSlice<FieldIdx, F>,
1129        repr: &ReprOptions,
1130        kind: StructKind,
1131        niche_bias: NicheBias,
1132    ) -> LayoutCalculatorResult<FieldIdx, VariantIdx, F> {
1133        let dl = self.cx.data_layout();
1134        let pack = repr.pack;
1135        let mut align = if pack.is_some() { dl.i8_align } else { dl.aggregate_align };
1136        let mut max_repr_align = repr.align;
1137        let mut inverse_memory_index: IndexVec<u32, FieldIdx> = fields.indices().collect();
1138        let optimize_field_order = !repr.inhibit_struct_field_reordering();
1139        let end = if let StructKind::MaybeUnsized = kind { fields.len() - 1 } else { fields.len() };
1140        let optimizing = &mut inverse_memory_index.raw[..end];
1141        let fields_excluding_tail = &fields.raw[..end];
1142        // unsizable tail fields are excluded so that we use the same seed for the sized and unsized layouts.
1143        let field_seed = fields_excluding_tail
1144            .iter()
1145            .fold(Hash64::ZERO, |acc, f| acc.wrapping_add(f.randomization_seed));
1146
1147        if optimize_field_order && fields.len() > 1 {
1148            // If `-Z randomize-layout` was enabled for the type definition we can shuffle
1149            // the field ordering to try and catch some code making assumptions about layouts
1150            // we don't guarantee.
1151            if repr.can_randomize_type_layout() && cfg!(feature = "randomize") {
1152                #[cfg(feature = "randomize")]
1153                {
1154                    use rand::SeedableRng;
1155                    use rand::seq::SliceRandom;
1156                    // `ReprOptions.field_shuffle_seed` is a deterministic seed we can use to randomize field
1157                    // ordering.
1158                    let mut rng = rand_xoshiro::Xoshiro128StarStar::seed_from_u64(
1159                        field_seed.wrapping_add(repr.field_shuffle_seed).as_u64(),
1160                    );
1161
1162                    // Shuffle the ordering of the fields.
1163                    optimizing.shuffle(&mut rng);
1164                }
1165                // Otherwise we just leave things alone and actually optimize the type's fields
1166            } else {
1167                // To allow unsizing `&Foo<Type>` -> `&Foo<dyn Trait>`, the layout of the struct must
1168                // not depend on the layout of the tail.
1169                let max_field_align =
1170                    fields_excluding_tail.iter().map(|f| f.align.bytes()).max().unwrap_or(1);
1171                let largest_niche_size = fields_excluding_tail
1172                    .iter()
1173                    .filter_map(|f| f.largest_niche)
1174                    .map(|n| n.available(dl))
1175                    .max()
1176                    .unwrap_or(0);
1177
1178                // Calculates a sort key to group fields by their alignment or possibly some
1179                // size-derived pseudo-alignment.
1180                let alignment_group_key = |layout: &F| {
1181                    // The two branches here return values that cannot be meaningfully compared with
1182                    // each other. However, we know that consistently for all executions of
1183                    // `alignment_group_key`, one or the other branch will be taken, so this is okay.
1184                    if let Some(pack) = pack {
1185                        // Return the packed alignment in bytes.
1186                        layout.align.abi.min(pack).bytes()
1187                    } else {
1188                        // Returns `log2(effective-align)`. The calculation assumes that size is an
1189                        // integer multiple of align, except for ZSTs.
1190                        let align = layout.align.bytes();
1191                        let size = layout.size.bytes();
1192                        let niche_size = layout.largest_niche.map(|n| n.available(dl)).unwrap_or(0);
1193                        // Group [u8; 4] with align-4 or [u8; 6] with align-2 fields.
1194                        let size_as_align = align.max(size).trailing_zeros();
1195                        let size_as_align = if largest_niche_size > 0 {
1196                            match niche_bias {
1197                                // Given `A(u8, [u8; 16])` and `B(bool, [u8; 16])` we want to bump the
1198                                // array to the front in the first case (for aligned loads) but keep
1199                                // the bool in front in the second case for its niches.
1200                                NicheBias::Start => {
1201                                    max_field_align.trailing_zeros().min(size_as_align)
1202                                }
1203                                // When moving niches towards the end of the struct then for
1204                                // A((u8, u8, u8, bool), (u8, bool, u8)) we want to keep the first tuple
1205                                // in the align-1 group because its bool can be moved closer to the end.
1206                                NicheBias::End if niche_size == largest_niche_size => {
1207                                    align.trailing_zeros()
1208                                }
1209                                NicheBias::End => size_as_align,
1210                            }
1211                        } else {
1212                            size_as_align
1213                        };
1214                        size_as_align as u64
1215                    }
1216                };
1217
1218                match kind {
1219                    StructKind::AlwaysSized | StructKind::MaybeUnsized => {
1220                        // Currently `LayoutData` only exposes a single niche so sorting is usually
1221                        // sufficient to get one niche into the preferred position. If it ever
1222                        // supported multiple niches then a more advanced pick-and-pack approach could
1223                        // provide better results. But even for the single-niche cache it's not
1224                        // optimal. E.g. for A(u32, (bool, u8), u16) it would be possible to move the
1225                        // bool to the front but it would require packing the tuple together with the
1226                        // u16 to build a 4-byte group so that the u32 can be placed after it without
1227                        // padding. This kind of packing can't be achieved by sorting.
1228                        optimizing.sort_by_key(|&x| {
1229                            let f = &fields[x];
1230                            let field_size = f.size.bytes();
1231                            let niche_size = f.largest_niche.map_or(0, |n| n.available(dl));
1232                            let niche_size_key = match niche_bias {
1233                                // large niche first
1234                                NicheBias::Start => !niche_size,
1235                                // large niche last
1236                                NicheBias::End => niche_size,
1237                            };
1238                            let inner_niche_offset_key = match niche_bias {
1239                                NicheBias::Start => f.largest_niche.map_or(0, |n| n.offset.bytes()),
1240                                NicheBias::End => f.largest_niche.map_or(0, |n| {
1241                                    !(field_size - n.value.size(dl).bytes() - n.offset.bytes())
1242                                }),
1243                            };
1244
1245                            (
1246                                // Then place largest alignments first.
1247                                cmp::Reverse(alignment_group_key(f)),
1248                                // Then prioritize niche placement within alignment group according to
1249                                // `niche_bias_start`.
1250                                niche_size_key,
1251                                // Then among fields with equally-sized niches prefer the ones
1252                                // closer to the start/end of the field.
1253                                inner_niche_offset_key,
1254                            )
1255                        });
1256                    }
1257
1258                    StructKind::Prefixed(..) => {
1259                        // Sort in ascending alignment so that the layout stays optimal
1260                        // regardless of the prefix.
1261                        // And put the largest niche in an alignment group at the end
1262                        // so it can be used as discriminant in jagged enums
1263                        optimizing.sort_by_key(|&x| {
1264                            let f = &fields[x];
1265                            let niche_size = f.largest_niche.map_or(0, |n| n.available(dl));
1266                            (alignment_group_key(f), niche_size)
1267                        });
1268                    }
1269                }
1270
1271                // FIXME(Kixiron): We can always shuffle fields within a given alignment class
1272                //                 regardless of the status of `-Z randomize-layout`
1273            }
1274        }
1275        // inverse_memory_index holds field indices by increasing memory offset.
1276        // That is, if field 5 has offset 0, the first element of inverse_memory_index is 5.
1277        // We now write field offsets to the corresponding offset slot;
1278        // field 5 with offset 0 puts 0 in offsets[5].
1279        // At the bottom of this function, we invert `inverse_memory_index` to
1280        // produce `memory_index` (see `invert_mapping`).
1281        let mut unsized_field = None::<&F>;
1282        let mut offsets = IndexVec::from_elem(Size::ZERO, fields);
1283        let mut offset = Size::ZERO;
1284        let mut largest_niche = None;
1285        let mut largest_niche_available = 0;
1286        if let StructKind::Prefixed(prefix_size, prefix_align) = kind {
1287            let prefix_align =
1288                if let Some(pack) = pack { prefix_align.min(pack) } else { prefix_align };
1289            align = align.max(prefix_align);
1290            offset = prefix_size.align_to(prefix_align);
1291        }
1292        for &i in &inverse_memory_index {
1293            let field = &fields[i];
1294            if let Some(unsized_field) = unsized_field {
1295                return Err(LayoutCalculatorError::UnexpectedUnsized(*unsized_field));
1296            }
1297
1298            if field.is_unsized() {
1299                if let StructKind::MaybeUnsized = kind {
1300                    unsized_field = Some(field);
1301                } else {
1302                    return Err(LayoutCalculatorError::UnexpectedUnsized(*field));
1303                }
1304            }
1305
1306            // Invariant: offset < dl.obj_size_bound() <= 1<<61
1307            let field_align = if let Some(pack) = pack {
1308                field.align.min(AbiAlign::new(pack))
1309            } else {
1310                field.align
1311            };
1312            offset = offset.align_to(field_align.abi);
1313            align = align.max(field_align.abi);
1314            max_repr_align = max_repr_align.max(field.max_repr_align);
1315
1316            debug!("univariant offset: {:?} field: {:#?}", offset, field);
1317            offsets[i] = offset;
1318
1319            if let Some(mut niche) = field.largest_niche {
1320                let available = niche.available(dl);
1321                // Pick up larger niches.
1322                let prefer_new_niche = match niche_bias {
1323                    NicheBias::Start => available > largest_niche_available,
1324                    // if there are several niches of the same size then pick the last one
1325                    NicheBias::End => available >= largest_niche_available,
1326                };
1327                if prefer_new_niche {
1328                    largest_niche_available = available;
1329                    niche.offset += offset;
1330                    largest_niche = Some(niche);
1331                }
1332            }
1333
1334            offset =
1335                offset.checked_add(field.size, dl).ok_or(LayoutCalculatorError::SizeOverflow)?;
1336        }
1337
1338        // The unadjusted ABI alignment does not include repr(align), but does include repr(pack).
1339        // See documentation on `LayoutData::unadjusted_abi_align`.
1340        let unadjusted_abi_align = align;
1341        if let Some(repr_align) = repr.align {
1342            align = align.max(repr_align);
1343        }
1344        // `align` must not be modified after this point, or `unadjusted_abi_align` could be inaccurate.
1345        let align = align;
1346
1347        debug!("univariant min_size: {:?}", offset);
1348        let min_size = offset;
1349        // As stated above, inverse_memory_index holds field indices by increasing offset.
1350        // This makes it an already-sorted view of the offsets vec.
1351        // To invert it, consider:
1352        // If field 5 has offset 0, offsets[0] is 5, and memory_index[5] should be 0.
1353        // Field 5 would be the first element, so memory_index is i:
1354        // Note: if we didn't optimize, it's already right.
1355        let memory_index = if optimize_field_order {
1356            inverse_memory_index.invert_bijective_mapping()
1357        } else {
1358            debug_assert!(inverse_memory_index.iter().copied().eq(fields.indices()));
1359            inverse_memory_index.into_iter().map(|it| it.index() as u32).collect()
1360        };
1361        let size = min_size.align_to(align);
1362        // FIXME(oli-obk): deduplicate and harden these checks
1363        if size.bytes() >= dl.obj_size_bound() {
1364            return Err(LayoutCalculatorError::SizeOverflow);
1365        }
1366        let mut layout_of_single_non_zst_field = None;
1367        let sized = unsized_field.is_none();
1368        let mut abi = BackendRepr::Memory { sized };
1369
1370        let optimize_abi = !repr.inhibit_newtype_abi_optimization();
1371
1372        // Try to make this a Scalar/ScalarPair.
1373        if sized && size.bytes() > 0 {
1374            // We skip *all* ZST here and later check if we are good in terms of alignment.
1375            // This lets us handle some cases involving aligned ZST.
1376            let mut non_zst_fields = fields.iter_enumerated().filter(|&(_, f)| !f.is_zst());
1377
1378            match (non_zst_fields.next(), non_zst_fields.next(), non_zst_fields.next()) {
1379                // We have exactly one non-ZST field.
1380                (Some((i, field)), None, None) => {
1381                    layout_of_single_non_zst_field = Some(field);
1382
1383                    // Field fills the struct and it has a scalar or scalar pair ABI.
1384                    if offsets[i].bytes() == 0 && align == field.align.abi && size == field.size {
1385                        match field.backend_repr {
1386                            // For plain scalars, or vectors of them, we can't unpack
1387                            // newtypes for `#[repr(C)]`, as that affects C ABIs.
1388                            BackendRepr::Scalar(_) | BackendRepr::SimdVector { .. }
1389                                if optimize_abi =>
1390                            {
1391                                abi = field.backend_repr;
1392                            }
1393                            // But scalar pairs are Rust-specific and get
1394                            // treated as aggregates by C ABIs anyway.
1395                            BackendRepr::ScalarPair(..) => {
1396                                abi = field.backend_repr;
1397                            }
1398                            _ => {}
1399                        }
1400                    }
1401                }
1402
1403                // Two non-ZST fields, and they're both scalars.
1404                (Some((i, a)), Some((j, b)), None) => {
1405                    match (a.backend_repr, b.backend_repr) {
1406                        (BackendRepr::Scalar(a), BackendRepr::Scalar(b)) => {
1407                            // Order by the memory placement, not source order.
1408                            let ((i, a), (j, b)) = if offsets[i] < offsets[j] {
1409                                ((i, a), (j, b))
1410                            } else {
1411                                ((j, b), (i, a))
1412                            };
1413                            let pair =
1414                                LayoutData::<FieldIdx, VariantIdx>::scalar_pair(&self.cx, a, b);
1415                            let pair_offsets = match pair.fields {
1416                                FieldsShape::Arbitrary { ref offsets, ref memory_index } => {
1417                                    assert_eq!(memory_index.raw, [0, 1]);
1418                                    offsets
1419                                }
1420                                FieldsShape::Primitive
1421                                | FieldsShape::Array { .. }
1422                                | FieldsShape::Union(..) => {
1423                                    panic!("encountered a non-arbitrary layout during enum layout")
1424                                }
1425                            };
1426                            if offsets[i] == pair_offsets[FieldIdx::new(0)]
1427                                && offsets[j] == pair_offsets[FieldIdx::new(1)]
1428                                && align == pair.align.abi
1429                                && size == pair.size
1430                            {
1431                                // We can use `ScalarPair` only when it matches our
1432                                // already computed layout (including `#[repr(C)]`).
1433                                abi = pair.backend_repr;
1434                            }
1435                        }
1436                        _ => {}
1437                    }
1438                }
1439
1440                _ => {}
1441            }
1442        }
1443        let uninhabited = fields.iter().any(|f| f.is_uninhabited());
1444
1445        let unadjusted_abi_align = if repr.transparent() {
1446            match layout_of_single_non_zst_field {
1447                Some(l) => l.unadjusted_abi_align,
1448                None => {
1449                    // `repr(transparent)` with all ZST fields.
1450                    align
1451                }
1452            }
1453        } else {
1454            unadjusted_abi_align
1455        };
1456
1457        let seed = field_seed.wrapping_add(repr.field_shuffle_seed);
1458
1459        Ok(LayoutData {
1460            variants: Variants::Single { index: VariantIdx::new(0) },
1461            fields: FieldsShape::Arbitrary { offsets, memory_index },
1462            backend_repr: abi,
1463            largest_niche,
1464            uninhabited,
1465            align: AbiAlign::new(align),
1466            size,
1467            max_repr_align,
1468            unadjusted_abi_align,
1469            randomization_seed: seed,
1470        })
1471    }
1472
1473    fn format_field_niches<
1474        'a,
1475        FieldIdx: Idx,
1476        VariantIdx: Idx,
1477        F: Deref<Target = &'a LayoutData<FieldIdx, VariantIdx>> + fmt::Debug,
1478    >(
1479        &self,
1480        layout: &LayoutData<FieldIdx, VariantIdx>,
1481        fields: &IndexSlice<FieldIdx, F>,
1482    ) -> String {
1483        let dl = self.cx.data_layout();
1484        let mut s = String::new();
1485        for i in layout.fields.index_by_increasing_offset() {
1486            let offset = layout.fields.offset(i);
1487            let f = &fields[FieldIdx::new(i)];
1488            write!(s, "[o{}a{}s{}", offset.bytes(), f.align.bytes(), f.size.bytes()).unwrap();
1489            if let Some(n) = f.largest_niche {
1490                write!(
1491                    s,
1492                    " n{}b{}s{}",
1493                    n.offset.bytes(),
1494                    n.available(dl).ilog2(),
1495                    n.value.size(dl).bytes()
1496                )
1497                .unwrap();
1498            }
1499            write!(s, "] ").unwrap();
1500        }
1501        s
1502    }
1503}