rustc_transmute/layout/
tree.rs

1use std::ops::{ControlFlow, RangeInclusive};
2
3use super::{Byte, Def, Reference, Region, Type};
4
5#[cfg(test)]
6mod tests;
7
8/// A tree-based representation of a type layout.
9///
10/// Invariants:
11/// 1. All paths through the layout have the same length (in bytes).
12///
13/// Nice-to-haves:
14/// 1. An `Alt` is never directly nested beneath another `Alt`.
15/// 2. A `Seq` is never directly nested beneath another `Seq`.
16/// 3. `Seq`s and `Alt`s with a single member do not exist.
17#[derive(Clone, Debug, Hash, PartialEq, Eq)]
18pub(crate) enum Tree<D, R, T>
19where
20    D: Def,
21    R: Region,
22    T: Type,
23{
24    /// A sequence of successive layouts.
25    Seq(Vec<Self>),
26    /// A choice between alternative layouts.
27    Alt(Vec<Self>),
28    /// A definition node.
29    Def(D),
30    /// A reference node.
31    Ref(Reference<R, T>),
32    /// A byte node.
33    Byte(Byte),
34}
35
36#[derive(Debug, Copy, Clone, Eq, PartialEq)]
37pub(crate) enum Endian {
38    Little,
39    Big,
40}
41
42#[cfg(feature = "rustc")]
43impl From<rustc_abi::Endian> for Endian {
44    fn from(order: rustc_abi::Endian) -> Endian {
45        match order {
46            rustc_abi::Endian::Little => Endian::Little,
47            rustc_abi::Endian::Big => Endian::Big,
48        }
49    }
50}
51
52impl<D, R, T> Tree<D, R, T>
53where
54    D: Def,
55    R: Region,
56    T: Type,
57{
58    /// A `Tree` consisting only of a definition node.
59    pub(crate) fn def(def: D) -> Self {
60        Self::Def(def)
61    }
62
63    /// A `Tree` representing an uninhabited type.
64    pub(crate) fn uninhabited() -> Self {
65        Self::Alt(vec![])
66    }
67
68    /// A `Tree` representing a zero-sized type.
69    pub(crate) fn unit() -> Self {
70        Self::Seq(Vec::new())
71    }
72
73    /// A `Tree` containing a single, uninitialized byte.
74    pub(crate) fn uninit() -> Self {
75        Self::Byte(Byte::uninit())
76    }
77
78    /// A `Tree` representing the layout of `bool`.
79    pub(crate) fn bool() -> Self {
80        Self::byte(0x00..=0x01)
81    }
82
83    /// A `Tree` whose layout matches that of a `u8`.
84    pub(crate) fn u8() -> Self {
85        Self::byte(0x00..=0xFF)
86    }
87
88    /// A `Tree` whose layout matches that of a `char`.
89    pub(crate) fn char(order: Endian) -> Self {
90        // `char`s can be in the following ranges:
91        // - [0, 0xD7FF]
92        // - [0xE000, 10FFFF]
93        //
94        // All other `char` values are illegal. We can thus represent a `char`
95        // as a union of three possible layouts:
96        // - 00 00 [00, D7] XX
97        // - 00 00 [E0, FF] XX
98        // - 00 [01, 10] XX XX
99
100        const _0: RangeInclusive<u8> = 0..=0;
101        const BYTE: RangeInclusive<u8> = 0x00..=0xFF;
102        let x = Self::from_big_endian(order, [_0, _0, 0x00..=0xD7, BYTE]);
103        let y = Self::from_big_endian(order, [_0, _0, 0xE0..=0xFF, BYTE]);
104        let z = Self::from_big_endian(order, [_0, 0x01..=0x10, BYTE, BYTE]);
105        Self::alt([x, y, z])
106    }
107
108    /// A `Tree` whose layout matches `std::num::NonZeroXxx`.
109    #[allow(dead_code)]
110    pub(crate) fn nonzero(width_in_bytes: u64) -> Self {
111        const BYTE: RangeInclusive<u8> = 0x00..=0xFF;
112        const NONZERO: RangeInclusive<u8> = 0x01..=0xFF;
113
114        (0..width_in_bytes)
115            .map(|nz_idx| {
116                (0..width_in_bytes)
117                    .map(|pos| Self::byte(if pos == nz_idx { NONZERO } else { BYTE }))
118                    .fold(Self::unit(), Self::then)
119            })
120            .fold(Self::uninhabited(), Self::or)
121    }
122
123    pub(crate) fn bytes<const N: usize, B: Into<Byte>>(bytes: [B; N]) -> Self {
124        Self::seq(bytes.map(B::into).map(Self::Byte))
125    }
126
127    pub(crate) fn byte(byte: impl Into<Byte>) -> Self {
128        Self::Byte(byte.into())
129    }
130
131    /// A `Tree` whose layout is a number of the given width.
132    pub(crate) fn number(width_in_bytes: u64) -> Self {
133        Self::Seq(vec![Self::u8(); width_in_bytes.try_into().unwrap()])
134    }
135
136    /// A `Tree` whose layout is entirely padding of the given width.
137    pub(crate) fn padding(width_in_bytes: usize) -> Self {
138        Self::Seq(vec![Self::uninit(); width_in_bytes])
139    }
140
141    /// Remove all `Def` nodes, and all branches of the layout for which `f`
142    /// produces `true`.
143    pub(crate) fn prune<F>(self, f: &F) -> Tree<!, R, T>
144    where
145        F: Fn(D) -> bool,
146    {
147        match self {
148            Self::Seq(elts) => match elts.into_iter().map(|elt| elt.prune(f)).try_fold(
149                Tree::unit(),
150                |elts, elt| {
151                    if elt == Tree::uninhabited() {
152                        ControlFlow::Break(Tree::uninhabited())
153                    } else {
154                        ControlFlow::Continue(elts.then(elt))
155                    }
156                },
157            ) {
158                ControlFlow::Break(node) | ControlFlow::Continue(node) => node,
159            },
160            Self::Alt(alts) => alts
161                .into_iter()
162                .map(|alt| alt.prune(f))
163                .fold(Tree::uninhabited(), |alts, alt| alts.or(alt)),
164            Self::Byte(b) => Tree::Byte(b),
165            Self::Ref(r) => Tree::Ref(r),
166            Self::Def(d) => {
167                if f(d) {
168                    Tree::uninhabited()
169                } else {
170                    Tree::unit()
171                }
172            }
173        }
174    }
175
176    /// Produces `true` if `Tree` is an inhabited type; otherwise false.
177    pub(crate) fn is_inhabited(&self) -> bool {
178        match self {
179            Self::Seq(elts) => elts.into_iter().all(|elt| elt.is_inhabited()),
180            Self::Alt(alts) => alts.into_iter().any(|alt| alt.is_inhabited()),
181            Self::Byte(..) | Self::Ref(..) | Self::Def(..) => true,
182        }
183    }
184
185    /// Produces a `Tree` which represents a sequence of bytes stored in
186    /// `order`.
187    ///
188    /// `bytes` is taken to be in big-endian byte order, and its order will be
189    /// swapped if `order == Endian::Little`.
190    pub(crate) fn from_big_endian<const N: usize, B: Into<Byte>>(
191        order: Endian,
192        mut bytes: [B; N],
193    ) -> Self {
194        if order == Endian::Little {
195            (&mut bytes[..]).reverse();
196        }
197
198        Self::bytes(bytes)
199    }
200
201    /// Produces a `Tree` where each of the trees in `trees` are sequenced one
202    /// after another.
203    pub(crate) fn seq<const N: usize>(trees: [Tree<D, R, T>; N]) -> Self {
204        trees.into_iter().fold(Tree::unit(), Self::then)
205    }
206
207    /// Produces a `Tree` where each of the trees in `trees` are accepted as
208    /// alternative layouts.
209    pub(crate) fn alt<const N: usize>(trees: [Tree<D, R, T>; N]) -> Self {
210        trees.into_iter().fold(Tree::uninhabited(), Self::or)
211    }
212
213    /// Produces a new `Tree` where `other` is sequenced after `self`.
214    pub(crate) fn then(self, other: Self) -> Self {
215        match (self, other) {
216            (Self::Seq(elts), other) | (other, Self::Seq(elts)) if elts.len() == 0 => other,
217            (Self::Seq(mut lhs), Self::Seq(mut rhs)) => {
218                lhs.append(&mut rhs);
219                Self::Seq(lhs)
220            }
221            (Self::Seq(mut lhs), rhs) => {
222                lhs.push(rhs);
223                Self::Seq(lhs)
224            }
225            (lhs, Self::Seq(mut rhs)) => {
226                rhs.insert(0, lhs);
227                Self::Seq(rhs)
228            }
229            (lhs, rhs) => Self::Seq(vec![lhs, rhs]),
230        }
231    }
232
233    /// Produces a new `Tree` accepting either `self` or `other` as alternative layouts.
234    pub(crate) fn or(self, other: Self) -> Self {
235        match (self, other) {
236            (Self::Alt(alts), other) | (other, Self::Alt(alts)) if alts.len() == 0 => other,
237            (Self::Alt(mut lhs), Self::Alt(rhs)) => {
238                lhs.extend(rhs);
239                Self::Alt(lhs)
240            }
241            (Self::Alt(mut alts), alt) | (alt, Self::Alt(mut alts)) => {
242                alts.push(alt);
243                Self::Alt(alts)
244            }
245            (lhs, rhs) => Self::Alt(vec![lhs, rhs]),
246        }
247    }
248}
249
250#[cfg(feature = "rustc")]
251pub(crate) mod rustc {
252    use rustc_abi::{
253        FieldIdx, FieldsShape, Layout, Size, TagEncoding, TyAndLayout, VariantIdx, Variants,
254    };
255    use rustc_middle::ty::layout::{HasTyCtxt, LayoutCx, LayoutError};
256    use rustc_middle::ty::{
257        self, AdtDef, AdtKind, List, Region, ScalarInt, Ty, TyCtxt, TypeVisitableExt,
258    };
259    use rustc_span::ErrorGuaranteed;
260
261    use super::Tree;
262    use crate::layout::Reference;
263    use crate::layout::rustc::{Def, layout_of};
264
265    #[derive(Debug, Copy, Clone)]
266    pub(crate) enum Err {
267        /// The layout of the type is not yet supported.
268        NotYetSupported,
269        /// This error will be surfaced elsewhere by rustc, so don't surface it.
270        UnknownLayout,
271        /// Overflow size
272        SizeOverflow,
273        TypeError(ErrorGuaranteed),
274    }
275
276    impl<'tcx> From<&LayoutError<'tcx>> for Err {
277        fn from(err: &LayoutError<'tcx>) -> Self {
278            match err {
279                LayoutError::Unknown(..)
280                | LayoutError::ReferencesError(..)
281                | LayoutError::TooGeneric(..)
282                | LayoutError::NormalizationFailure(..) => Self::UnknownLayout,
283                LayoutError::SizeOverflow(..) => Self::SizeOverflow,
284                LayoutError::Cycle(err) => Self::TypeError(*err),
285            }
286        }
287    }
288
289    impl<'tcx> Tree<Def<'tcx>, Region<'tcx>, Ty<'tcx>> {
290        pub(crate) fn from_ty(ty: Ty<'tcx>, cx: LayoutCx<'tcx>) -> Result<Self, Err> {
291            use rustc_abi::HasDataLayout;
292            let layout = layout_of(cx, ty)?;
293
294            if let Err(e) = ty.error_reported() {
295                return Err(Err::TypeError(e));
296            }
297
298            let target = cx.data_layout();
299            let pointer_size = target.pointer_size();
300
301            match ty.kind() {
302                ty::Bool => Ok(Self::bool()),
303
304                ty::Float(nty) => {
305                    let width = nty.bit_width() / 8;
306                    Ok(Self::number(width.try_into().unwrap()))
307                }
308
309                ty::Int(nty) => {
310                    let width = nty.normalize(pointer_size.bits() as _).bit_width().unwrap() / 8;
311                    Ok(Self::number(width.try_into().unwrap()))
312                }
313
314                ty::Uint(nty) => {
315                    let width = nty.normalize(pointer_size.bits() as _).bit_width().unwrap() / 8;
316                    Ok(Self::number(width.try_into().unwrap()))
317                }
318
319                ty::Tuple(members) => Self::from_tuple((ty, layout), members, cx),
320
321                ty::Array(inner_ty, _len) => {
322                    let FieldsShape::Array { stride, count } = &layout.fields else {
323                        return Err(Err::NotYetSupported);
324                    };
325                    let inner_layout = layout_of(cx, *inner_ty)?;
326                    assert_eq!(*stride, inner_layout.size);
327                    let elt = Tree::from_ty(*inner_ty, cx)?;
328                    Ok(std::iter::repeat(elt)
329                        .take(*count as usize)
330                        .fold(Tree::unit(), |tree, elt| tree.then(elt)))
331                }
332
333                ty::Adt(adt_def, _args_ref) if !ty.is_box() => {
334                    let (lo, hi) = cx.tcx().layout_scalar_valid_range(adt_def.did());
335
336                    use core::ops::Bound::*;
337                    let is_transparent = adt_def.repr().transparent();
338                    match (adt_def.adt_kind(), lo, hi) {
339                        (AdtKind::Struct, Unbounded, Unbounded) => {
340                            Self::from_struct((ty, layout), *adt_def, cx)
341                        }
342                        (AdtKind::Struct, Included(1), Included(_hi)) if is_transparent => {
343                            // FIXME(@joshlf): Support `NonZero` types:
344                            // - Check to make sure that the first field is
345                            //   numerical
346                            // - Check to make sure that the upper bound is the
347                            //   maximum value for the field's type
348                            // - Construct `Self::nonzero`
349                            Err(Err::NotYetSupported)
350                        }
351                        (AdtKind::Enum, Unbounded, Unbounded) => {
352                            Self::from_enum((ty, layout), *adt_def, cx)
353                        }
354                        (AdtKind::Union, Unbounded, Unbounded) => {
355                            Self::from_union((ty, layout), *adt_def, cx)
356                        }
357                        _ => Err(Err::NotYetSupported),
358                    }
359                }
360
361                ty::Ref(region, ty, mutability) => {
362                    let layout = layout_of(cx, *ty)?;
363                    let referent_align = layout.align.abi.bytes_usize();
364                    let referent_size = layout.size.bytes_usize();
365
366                    Ok(Tree::Ref(Reference {
367                        region: *region,
368                        is_mut: mutability.is_mut(),
369                        referent: *ty,
370                        referent_align,
371                        referent_size,
372                    }))
373                }
374
375                ty::Char => Ok(Self::char(cx.tcx().data_layout.endian.into())),
376
377                _ => Err(Err::NotYetSupported),
378            }
379        }
380
381        /// Constructs a `Tree` from a tuple.
382        fn from_tuple(
383            (ty, layout): (Ty<'tcx>, Layout<'tcx>),
384            members: &'tcx List<Ty<'tcx>>,
385            cx: LayoutCx<'tcx>,
386        ) -> Result<Self, Err> {
387            match &layout.fields {
388                FieldsShape::Primitive => {
389                    assert_eq!(members.len(), 1);
390                    let inner_ty = members[0];
391                    Self::from_ty(inner_ty, cx)
392                }
393                FieldsShape::Arbitrary { offsets, .. } => {
394                    assert_eq!(offsets.len(), members.len());
395                    Self::from_variant(Def::Primitive, None, (ty, layout), layout.size, cx)
396                }
397                FieldsShape::Array { .. } | FieldsShape::Union(_) => Err(Err::NotYetSupported),
398            }
399        }
400
401        /// Constructs a `Tree` from a struct.
402        ///
403        /// # Panics
404        ///
405        /// Panics if `def` is not a struct definition.
406        fn from_struct(
407            (ty, layout): (Ty<'tcx>, Layout<'tcx>),
408            def: AdtDef<'tcx>,
409            cx: LayoutCx<'tcx>,
410        ) -> Result<Self, Err> {
411            assert!(def.is_struct());
412            let def = Def::Adt(def);
413            Self::from_variant(def, None, (ty, layout), layout.size, cx)
414        }
415
416        /// Constructs a `Tree` from an enum.
417        ///
418        /// # Panics
419        ///
420        /// Panics if `def` is not an enum definition.
421        fn from_enum(
422            (ty, layout): (Ty<'tcx>, Layout<'tcx>),
423            def: AdtDef<'tcx>,
424            cx: LayoutCx<'tcx>,
425        ) -> Result<Self, Err> {
426            assert!(def.is_enum());
427
428            // Computes the layout of a variant.
429            let layout_of_variant =
430                |index, encoding: Option<TagEncoding<VariantIdx>>| -> Result<Self, Err> {
431                    let variant_layout = ty_variant(cx, (ty, layout), index);
432                    if variant_layout.is_uninhabited() {
433                        return Ok(Self::uninhabited());
434                    }
435                    let tag = cx.tcx().tag_for_variant(
436                        cx.typing_env.as_query_input((cx.tcx().erase_regions(ty), index)),
437                    );
438                    let variant_def = Def::Variant(def.variant(index));
439                    Self::from_variant(
440                        variant_def,
441                        tag.map(|tag| (tag, index, encoding.unwrap())),
442                        (ty, variant_layout),
443                        layout.size,
444                        cx,
445                    )
446                };
447
448            match layout.variants() {
449                Variants::Empty => Ok(Self::uninhabited()),
450                Variants::Single { index } => {
451                    // `Variants::Single` on enums with variants denotes that
452                    // the enum delegates its layout to the variant at `index`.
453                    layout_of_variant(*index, None)
454                }
455                Variants::Multiple { tag: _, tag_encoding, tag_field, .. } => {
456                    // `Variants::Multiple` denotes an enum with multiple
457                    // variants. The layout of such an enum is the disjunction
458                    // of the layouts of its tagged variants.
459
460                    // For enums (but not coroutines), the tag field is
461                    // currently always the first field of the layout.
462                    assert_eq!(*tag_field, FieldIdx::ZERO);
463
464                    let variants = def.discriminants(cx.tcx()).try_fold(
465                        Self::uninhabited(),
466                        |variants, (idx, _discriminant)| {
467                            let variant = layout_of_variant(idx, Some(tag_encoding.clone()))?;
468                            Result::<Self, Err>::Ok(variants.or(variant))
469                        },
470                    )?;
471
472                    Ok(Self::def(Def::Adt(def)).then(variants))
473                }
474            }
475        }
476
477        /// Constructs a `Tree` from a 'variant-like' layout.
478        ///
479        /// A 'variant-like' layout includes those of structs and, of course,
480        /// enum variants. Pragmatically speaking, this method supports anything
481        /// with `FieldsShape::Arbitrary`.
482        ///
483        /// Note: This routine assumes that the optional `tag` is the first
484        /// field, and enum callers should check that `tag_field` is, in fact,
485        /// `0`.
486        fn from_variant(
487            def: Def<'tcx>,
488            tag: Option<(ScalarInt, VariantIdx, TagEncoding<VariantIdx>)>,
489            (ty, layout): (Ty<'tcx>, Layout<'tcx>),
490            total_size: Size,
491            cx: LayoutCx<'tcx>,
492        ) -> Result<Self, Err> {
493            // This constructor does not support non-`FieldsShape::Arbitrary`
494            // layouts.
495            let FieldsShape::Arbitrary { offsets, memory_index } = layout.fields() else {
496                return Err(Err::NotYetSupported);
497            };
498
499            // When this function is invoked with enum variants,
500            // `ty_and_layout.size` does not encompass the entire size of the
501            // enum. We rely on `total_size` for this.
502            assert!(layout.size <= total_size);
503
504            let mut size = Size::ZERO;
505            let mut struct_tree = Self::def(def);
506
507            // If a `tag` is provided, place it at the start of the layout.
508            if let Some((tag, index, encoding)) = &tag {
509                match encoding {
510                    TagEncoding::Direct => {
511                        size += tag.size();
512                    }
513                    TagEncoding::Niche { niche_variants, .. } => {
514                        if !niche_variants.contains(index) {
515                            size += tag.size();
516                        }
517                    }
518                }
519                struct_tree = struct_tree.then(Self::from_tag(*tag, cx.tcx()));
520            }
521
522            // Append the fields, in memory order, to the layout.
523            let inverse_memory_index = memory_index.invert_bijective_mapping();
524            for &field_idx in inverse_memory_index.iter() {
525                // Add interfield padding.
526                let padding_needed = offsets[field_idx] - size;
527                let padding = Self::padding(padding_needed.bytes_usize());
528
529                let field_ty = ty_field(cx, (ty, layout), field_idx);
530                let field_layout = layout_of(cx, field_ty)?;
531                let field_tree = Self::from_ty(field_ty, cx)?;
532
533                struct_tree = struct_tree.then(padding).then(field_tree);
534
535                size += padding_needed + field_layout.size;
536            }
537
538            // Add trailing padding.
539            let padding_needed = total_size - size;
540            let trailing_padding = Self::padding(padding_needed.bytes_usize());
541
542            Ok(struct_tree.then(trailing_padding))
543        }
544
545        /// Constructs a `Tree` representing the value of a enum tag.
546        fn from_tag(tag: ScalarInt, tcx: TyCtxt<'tcx>) -> Self {
547            use rustc_abi::Endian;
548            let size = tag.size();
549            let bits = tag.to_bits(size);
550            let bytes: [u8; 16];
551            let bytes = match tcx.data_layout.endian {
552                Endian::Little => {
553                    bytes = bits.to_le_bytes();
554                    &bytes[..size.bytes_usize()]
555                }
556                Endian::Big => {
557                    bytes = bits.to_be_bytes();
558                    &bytes[bytes.len() - size.bytes_usize()..]
559                }
560            };
561            Self::Seq(bytes.iter().map(|&b| Self::byte(b)).collect())
562        }
563
564        /// Constructs a `Tree` from a union.
565        ///
566        /// # Panics
567        ///
568        /// Panics if `def` is not a union definition.
569        fn from_union(
570            (ty, layout): (Ty<'tcx>, Layout<'tcx>),
571            def: AdtDef<'tcx>,
572            cx: LayoutCx<'tcx>,
573        ) -> Result<Self, Err> {
574            assert!(def.is_union());
575
576            // This constructor does not support non-`FieldsShape::Union`
577            // layouts. Fields of this shape are all placed at offset 0.
578            let FieldsShape::Union(_fields) = layout.fields() else {
579                return Err(Err::NotYetSupported);
580            };
581
582            let fields = &def.non_enum_variant().fields;
583            let fields = fields.iter_enumerated().try_fold(
584                Self::uninhabited(),
585                |fields, (idx, _field_def)| {
586                    let field_ty = ty_field(cx, (ty, layout), idx);
587                    let field_layout = layout_of(cx, field_ty)?;
588                    let field = Self::from_ty(field_ty, cx)?;
589                    let trailing_padding_needed = layout.size - field_layout.size;
590                    let trailing_padding = Self::padding(trailing_padding_needed.bytes_usize());
591                    let field_and_padding = field.then(trailing_padding);
592                    Result::<Self, Err>::Ok(fields.or(field_and_padding))
593                },
594            )?;
595
596            Ok(Self::def(Def::Adt(def)).then(fields))
597        }
598    }
599
600    fn ty_field<'tcx>(
601        cx: LayoutCx<'tcx>,
602        (ty, layout): (Ty<'tcx>, Layout<'tcx>),
603        i: FieldIdx,
604    ) -> Ty<'tcx> {
605        // We cannot use `ty_and_layout_field` to retrieve the field type, since
606        // `ty_and_layout_field` erases regions in the returned type. We must
607        // not erase regions here, since we may need to ultimately emit outlives
608        // obligations as a consequence of the transmutability analysis.
609        match ty.kind() {
610            ty::Adt(def, args) => {
611                match layout.variants {
612                    Variants::Single { index } => {
613                        let field = &def.variant(index).fields[i];
614                        field.ty(cx.tcx(), args)
615                    }
616                    Variants::Empty => panic!("there is no field in Variants::Empty types"),
617                    // Discriminant field for enums (where applicable).
618                    Variants::Multiple { tag, .. } => {
619                        assert_eq!(i.as_usize(), 0);
620                        ty::layout::PrimitiveExt::to_ty(&tag.primitive(), cx.tcx())
621                    }
622                }
623            }
624            ty::Tuple(fields) => fields[i.as_usize()],
625            kind => unimplemented!(
626                "only a subset of `Ty::ty_and_layout_field`'s functionality is implemented. implementation needed for {:?}",
627                kind
628            ),
629        }
630    }
631
632    fn ty_variant<'tcx>(
633        cx: LayoutCx<'tcx>,
634        (ty, layout): (Ty<'tcx>, Layout<'tcx>),
635        i: VariantIdx,
636    ) -> Layout<'tcx> {
637        let ty = cx.tcx().erase_regions(ty);
638        TyAndLayout { ty, layout }.for_variant(&cx, i).layout
639    }
640}
rustc_transmute/layout/tree.rs

rustc_transmute/layout/
tree.rs
