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
26fn 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 let is_1zst = fields.iter().all(|f| f.is_1zst());
41 uninhabited && is_1zst
42}
43
44enum NicheBias {
46 Start,
47 End,
48}
49
50#[derive(Copy, Clone, Debug, PartialEq, Eq)]
51pub enum LayoutCalculatorError<F> {
52 UnexpectedUnsized(F),
59
60 SizeOverflow,
62
63 EmptyUnion,
65
66 ReprConflict,
68
69 ZeroLengthSimdType,
71
72 OversizedSimdType { max_lanes: u64 },
74
75 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 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>, ) -> 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 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 (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 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 if let Ok(layout) = &layout {
247 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 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 None if is_enum => {
329 return Ok(LayoutData::never_type(&self.cx));
330 }
331 None => VariantIdx::new(0),
334 };
335
336 if !is_enum ||
338 (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 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 struct AbiMismatch;
376 let mut common_non_zst_repr_and_align = if repr.inhibits_union_abi_opt() {
377 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 continue;
398 }
399
400 if let Ok(common) = common_non_zst_repr_and_align {
401 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 common_non_zst_repr_and_align = Err(AbiMismatch);
408 } else {
409 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 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 let unadjusted_abi_align = align;
431 if let Some(repr_align) = repr.align {
432 align = align.max(repr_align);
433 }
434 let align = align;
436
437 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 BackendRepr::Scalar(_) | BackendRepr::ScalarPair(_, _)
444 if repr.scalar_align(dl).unwrap() != align =>
445 {
446 BackendRepr::Memory { sized: true }
447 }
448 BackendRepr::SimdVector { element, count: _ } if element.align(dl).abi > align => {
450 BackendRepr::Memory { sized: true }
451 }
452 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 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 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 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 let max_value = scalar.size(dl).unsigned_int_max();
546 if let Bound::Included(start) = start {
547 assert!(start <= max_value, "{start} > {max_value}");
550 scalar.valid_range_mut().start = start;
551 }
552 if let Bound::Included(end) = end {
553 assert!(end <= max_value, "{end} > {max_value}");
556 scalar.valid_range_mut().end = end;
557 }
558
559 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 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 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 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 return true;
659 }
660
661 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 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 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 BackendRepr::Scalar(_) => BackendRepr::Scalar(niche_scalar),
708 BackendRepr::ScalarPair(first, second) => {
709 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 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 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 =
781 discriminants.clone().chain(valid_discriminants.first().copied()).skip(1);
782 let discriminants = discriminants.zip(next_discriminants);
785 let largest_niche = discriminants.max_by_key(|&(start, end)| {
786 trace!(?start, ?end);
787 let dist = if start > end {
790 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 end.wrapping_sub(start) as u128
804 };
805 trace!(?dist);
806 dist
807 });
808 trace!(?largest_niche);
809
810 let (max, min) = largest_niche
813 .unwrap_or((0, 0));
815 let (min_ity, signed) = discr_range_of_repr(min, max); 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 let mut start_align = Align::from_bytes(256).unwrap();
825 assert_eq!(Integer::for_align(dl, start_align), None);
826
827 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 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 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 size = size.align_to(align);
870
871 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 panic!(
888 "layout decided on a larger discriminant type ({min_ity:?}) than typeck ({typeck_ity:?})"
889 );
890 }
893
894 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 ity <= min_ity {
913 ity = min_ity;
914 } else {
915 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 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 abi = BackendRepr::Scalar(tag);
954 } else {
955 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 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 if offset != common_offset {
991 common_prim = None;
992 break;
993 }
994 let new_prim = match (old_prim, prim) {
998 (x, y) if x == y => x,
1000 (p @ Primitive::Int(x, _), Primitive::Int(y, _)) if x == y => p,
1003 (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 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 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 abi = pair.backend_repr;
1049 }
1050 }
1051 }
1052
1053 if matches!(abi, BackendRepr::Scalar(..) | BackendRepr::ScalarPair(..)) {
1057 for variant in &mut layout_variants {
1058 if variant.fields.count() > 0
1061 && matches!(variant.backend_repr, BackendRepr::Memory { .. })
1062 {
1063 variant.backend_repr = abi;
1064 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 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 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 repr.can_randomize_type_layout() && cfg!(feature = "randomize") {
1152 #[cfg(feature = "randomize")]
1153 {
1154 use rand::SeedableRng;
1155 use rand::seq::SliceRandom;
1156 let mut rng = rand_xoshiro::Xoshiro128StarStar::seed_from_u64(
1159 field_seed.wrapping_add(repr.field_shuffle_seed).as_u64(),
1160 );
1161
1162 optimizing.shuffle(&mut rng);
1164 }
1165 } else {
1167 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 let alignment_group_key = |layout: &F| {
1181 if let Some(pack) = pack {
1185 layout.align.abi.min(pack).bytes()
1187 } else {
1188 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 let size_as_align = align.max(size).trailing_zeros();
1195 let size_as_align = if largest_niche_size > 0 {
1196 match niche_bias {
1197 NicheBias::Start => {
1201 max_field_align.trailing_zeros().min(size_as_align)
1202 }
1203 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 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 NicheBias::Start => !niche_size,
1235 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 cmp::Reverse(alignment_group_key(f)),
1248 niche_size_key,
1251 inner_niche_offset_key,
1254 )
1255 });
1256 }
1257
1258 StructKind::Prefixed(..) => {
1259 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 }
1274 }
1275 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 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 let prefer_new_niche = match niche_bias {
1323 NicheBias::Start => available > largest_niche_available,
1324 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 let unadjusted_abi_align = align;
1341 if let Some(repr_align) = repr.align {
1342 align = align.max(repr_align);
1343 }
1344 let align = align;
1346
1347 debug!("univariant min_size: {:?}", offset);
1348 let min_size = offset;
1349 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 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 if sized && size.bytes() > 0 {
1374 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 (Some((i, field)), None, None) => {
1381 layout_of_single_non_zst_field = Some(field);
1382
1383 if offsets[i].bytes() == 0 && align == field.align.abi && size == field.size {
1385 match field.backend_repr {
1386 BackendRepr::Scalar(_) | BackendRepr::SimdVector { .. }
1389 if optimize_abi =>
1390 {
1391 abi = field.backend_repr;
1392 }
1393 BackendRepr::ScalarPair(..) => {
1396 abi = field.backend_repr;
1397 }
1398 _ => {}
1399 }
1400 }
1401 }
1402
1403 (Some((i, a)), Some((j, b)), None) => {
1405 match (a.backend_repr, b.backend_repr) {
1406 (BackendRepr::Scalar(a), BackendRepr::Scalar(b)) => {
1407 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 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 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}