rustc_transmute/layout/
tree.rs

Help
1use std::ops::ControlFlow;
2
3use super::{Byte, Def, Ref};
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>
19where
20    D: Def,
21    R: Ref,
22{
23    /// A sequence of successive layouts.
24    Seq(Vec<Self>),
25    /// A choice between alternative layouts.
26    Alt(Vec<Self>),
27    /// A definition node.
28    Def(D),
29    /// A reference node.
30    Ref(R),
31    /// A byte node.
32    Byte(Byte),
33}
34
35impl<D, R> Tree<D, R>
36where
37    D: Def,
38    R: Ref,
39{
40    /// A `Tree` consisting only of a definition node.
41    pub(crate) fn def(def: D) -> Self {
42        Self::Def(def)
43    }
44
45    /// A `Tree` representing an uninhabited type.
46    pub(crate) fn uninhabited() -> Self {
47        Self::Alt(vec![])
48    }
49
50    /// A `Tree` representing a zero-sized type.
51    pub(crate) fn unit() -> Self {
52        Self::Seq(Vec::new())
53    }
54
55    /// A `Tree` containing a single, uninitialized byte.
56    pub(crate) fn uninit() -> Self {
57        Self::Byte(Byte::Uninit)
58    }
59
60    /// A `Tree` representing the layout of `bool`.
61    pub(crate) fn bool() -> Self {
62        Self::from_bits(0x00).or(Self::from_bits(0x01))
63    }
64
65    /// A `Tree` whose layout matches that of a `u8`.
66    pub(crate) fn u8() -> Self {
67        Self::Alt((0u8..=255).map(Self::from_bits).collect())
68    }
69
70    /// A `Tree` whose layout accepts exactly the given bit pattern.
71    pub(crate) fn from_bits(bits: u8) -> Self {
72        Self::Byte(Byte::Init(bits))
73    }
74
75    /// A `Tree` whose layout is a number of the given width.
76    pub(crate) fn number(width_in_bytes: usize) -> Self {
77        Self::Seq(vec![Self::u8(); width_in_bytes])
78    }
79
80    /// A `Tree` whose layout is entirely padding of the given width.
81    pub(crate) fn padding(width_in_bytes: usize) -> Self {
82        Self::Seq(vec![Self::uninit(); width_in_bytes])
83    }
84
85    /// Remove all `Def` nodes, and all branches of the layout for which `f`
86    /// produces `true`.
87    pub(crate) fn prune<F>(self, f: &F) -> Tree<!, R>
88    where
89        F: Fn(D) -> bool,
90    {
91        match self {
92            Self::Seq(elts) => match elts.into_iter().map(|elt| elt.prune(f)).try_fold(
93                Tree::unit(),
94                |elts, elt| {
95                    if elt == Tree::uninhabited() {
96                        ControlFlow::Break(Tree::uninhabited())
97                    } else {
98                        ControlFlow::Continue(elts.then(elt))
99                    }
100                },
101            ) {
102                ControlFlow::Break(node) | ControlFlow::Continue(node) => node,
103            },
104            Self::Alt(alts) => alts
105                .into_iter()
106                .map(|alt| alt.prune(f))
107                .fold(Tree::uninhabited(), |alts, alt| alts.or(alt)),
108            Self::Byte(b) => Tree::Byte(b),
109            Self::Ref(r) => Tree::Ref(r),
110            Self::Def(d) => {
111                if f(d) {
112                    Tree::uninhabited()
113                } else {
114                    Tree::unit()
115                }
116            }
117        }
118    }
119
120    /// Produces `true` if `Tree` is an inhabited type; otherwise false.
121    pub(crate) fn is_inhabited(&self) -> bool {
122        match self {
123            Self::Seq(elts) => elts.into_iter().all(|elt| elt.is_inhabited()),
124            Self::Alt(alts) => alts.into_iter().any(|alt| alt.is_inhabited()),
125            Self::Byte(..) | Self::Ref(..) | Self::Def(..) => true,
126        }
127    }
128}
129
130impl<D, R> Tree<D, R>
131where
132    D: Def,
133    R: Ref,
134{
135    /// Produces a new `Tree` where `other` is sequenced after `self`.
136    pub(crate) fn then(self, other: Self) -> Self {
137        match (self, other) {
138            (Self::Seq(elts), other) | (other, Self::Seq(elts)) if elts.len() == 0 => other,
139            (Self::Seq(mut lhs), Self::Seq(mut rhs)) => {
140                lhs.append(&mut rhs);
141                Self::Seq(lhs)
142            }
143            (Self::Seq(mut lhs), rhs) => {
144                lhs.push(rhs);
145                Self::Seq(lhs)
146            }
147            (lhs, Self::Seq(mut rhs)) => {
148                rhs.insert(0, lhs);
149                Self::Seq(rhs)
150            }
151            (lhs, rhs) => Self::Seq(vec![lhs, rhs]),
152        }
153    }
154
155    /// Produces a new `Tree` accepting either `self` or `other` as alternative layouts.
156    pub(crate) fn or(self, other: Self) -> Self {
157        match (self, other) {
158            (Self::Alt(alts), other) | (other, Self::Alt(alts)) if alts.len() == 0 => other,
159            (Self::Alt(mut lhs), Self::Alt(rhs)) => {
160                lhs.extend(rhs);
161                Self::Alt(lhs)
162            }
163            (Self::Alt(mut alts), alt) | (alt, Self::Alt(mut alts)) => {
164                alts.push(alt);
165                Self::Alt(alts)
166            }
167            (lhs, rhs) => Self::Alt(vec![lhs, rhs]),
168        }
169    }
170}
171
172#[cfg(feature = "rustc")]
173pub(crate) mod rustc {
174    use rustc_abi::{
175        FieldIdx, FieldsShape, Layout, Size, TagEncoding, TyAndLayout, VariantIdx, Variants,
176    };
177    use rustc_middle::ty::layout::{HasTyCtxt, LayoutCx, LayoutError};
178    use rustc_middle::ty::{self, AdtDef, AdtKind, List, ScalarInt, Ty, TyCtxt, TypeVisitableExt};
179    use rustc_span::ErrorGuaranteed;
180
181    use super::Tree;
182    use crate::layout::rustc::{Def, Ref, layout_of};
183
184    #[derive(Debug, Copy, Clone)]
185    pub(crate) enum Err {
186        /// The layout of the type is not yet supported.
187        NotYetSupported,
188        /// This error will be surfaced elsewhere by rustc, so don't surface it.
189        UnknownLayout,
190        /// Overflow size
191        SizeOverflow,
192        TypeError(ErrorGuaranteed),
193    }
194
195    impl<'tcx> From<&LayoutError<'tcx>> for Err {
196        fn from(err: &LayoutError<'tcx>) -> Self {
197            match err {
198                LayoutError::Unknown(..)
199                | LayoutError::ReferencesError(..)
200                | LayoutError::TooGeneric(..)
201                | LayoutError::NormalizationFailure(..) => Self::UnknownLayout,
202                LayoutError::SizeOverflow(..) => Self::SizeOverflow,
203                LayoutError::Cycle(err) => Self::TypeError(*err),
204            }
205        }
206    }
207
208    impl<'tcx> Tree<Def<'tcx>, Ref<'tcx>> {
209        pub(crate) fn from_ty(ty: Ty<'tcx>, cx: LayoutCx<'tcx>) -> Result<Self, Err> {
210            use rustc_abi::HasDataLayout;
211            let layout = layout_of(cx, ty)?;
212
213            if let Err(e) = ty.error_reported() {
214                return Err(Err::TypeError(e));
215            }
216
217            let target = cx.data_layout();
218            let pointer_size = target.pointer_size;
219
220            match ty.kind() {
221                ty::Bool => Ok(Self::bool()),
222
223                ty::Float(nty) => {
224                    let width = nty.bit_width() / 8;
225                    Ok(Self::number(width as _))
226                }
227
228                ty::Int(nty) => {
229                    let width = nty.normalize(pointer_size.bits() as _).bit_width().unwrap() / 8;
230                    Ok(Self::number(width as _))
231                }
232
233                ty::Uint(nty) => {
234                    let width = nty.normalize(pointer_size.bits() as _).bit_width().unwrap() / 8;
235                    Ok(Self::number(width as _))
236                }
237
238                ty::Tuple(members) => Self::from_tuple((ty, layout), members, cx),
239
240                ty::Array(inner_ty, len) => {
241                    let FieldsShape::Array { stride, count } = &layout.fields else {
242                        return Err(Err::NotYetSupported);
243                    };
244                    let inner_layout = layout_of(cx, *inner_ty)?;
245                    assert_eq!(*stride, inner_layout.size);
246                    let elt = Tree::from_ty(*inner_ty, cx)?;
247                    Ok(std::iter::repeat(elt)
248                        .take(*count as usize)
249                        .fold(Tree::unit(), |tree, elt| tree.then(elt)))
250                }
251
252                ty::Adt(adt_def, _args_ref) if !ty.is_box() => match adt_def.adt_kind() {
253                    AdtKind::Struct => Self::from_struct((ty, layout), *adt_def, cx),
254                    AdtKind::Enum => Self::from_enum((ty, layout), *adt_def, cx),
255                    AdtKind::Union => Self::from_union((ty, layout), *adt_def, cx),
256                },
257
258                ty::Ref(lifetime, ty, mutability) => {
259                    let layout = layout_of(cx, *ty)?;
260                    let align = layout.align.abi.bytes_usize();
261                    let size = layout.size.bytes_usize();
262                    Ok(Tree::Ref(Ref {
263                        lifetime: *lifetime,
264                        ty: *ty,
265                        mutability: *mutability,
266                        align,
267                        size,
268                    }))
269                }
270
271                _ => Err(Err::NotYetSupported),
272            }
273        }
274
275        /// Constructs a `Tree` from a tuple.
276        fn from_tuple(
277            (ty, layout): (Ty<'tcx>, Layout<'tcx>),
278            members: &'tcx List<Ty<'tcx>>,
279            cx: LayoutCx<'tcx>,
280        ) -> Result<Self, Err> {
281            match &layout.fields {
282                FieldsShape::Primitive => {
283                    assert_eq!(members.len(), 1);
284                    let inner_ty = members[0];
285                    let inner_layout = layout_of(cx, inner_ty)?;
286                    Self::from_ty(inner_ty, cx)
287                }
288                FieldsShape::Arbitrary { offsets, .. } => {
289                    assert_eq!(offsets.len(), members.len());
290                    Self::from_variant(Def::Primitive, None, (ty, layout), layout.size, cx)
291                }
292                FieldsShape::Array { .. } | FieldsShape::Union(_) => Err(Err::NotYetSupported),
293            }
294        }
295
296        /// Constructs a `Tree` from a struct.
297        ///
298        /// # Panics
299        ///
300        /// Panics if `def` is not a struct definition.
301        fn from_struct(
302            (ty, layout): (Ty<'tcx>, Layout<'tcx>),
303            def: AdtDef<'tcx>,
304            cx: LayoutCx<'tcx>,
305        ) -> Result<Self, Err> {
306            assert!(def.is_struct());
307            let def = Def::Adt(def);
308            Self::from_variant(def, None, (ty, layout), layout.size, cx)
309        }
310
311        /// Constructs a `Tree` from an enum.
312        ///
313        /// # Panics
314        ///
315        /// Panics if `def` is not an enum definition.
316        fn from_enum(
317            (ty, layout): (Ty<'tcx>, Layout<'tcx>),
318            def: AdtDef<'tcx>,
319            cx: LayoutCx<'tcx>,
320        ) -> Result<Self, Err> {
321            assert!(def.is_enum());
322
323            // Computes the layout of a variant.
324            let layout_of_variant =
325                |index, encoding: Option<TagEncoding<VariantIdx>>| -> Result<Self, Err> {
326                    let variant_layout = ty_variant(cx, (ty, layout), index);
327                    if variant_layout.is_uninhabited() {
328                        return Ok(Self::uninhabited());
329                    }
330                    let tag = cx.tcx().tag_for_variant((cx.tcx().erase_regions(ty), index));
331                    let variant_def = Def::Variant(def.variant(index));
332                    Self::from_variant(
333                        variant_def,
334                        tag.map(|tag| (tag, index, encoding.unwrap())),
335                        (ty, variant_layout),
336                        layout.size,
337                        cx,
338                    )
339                };
340
341            match layout.variants() {
342                Variants::Empty => Ok(Self::uninhabited()),
343                Variants::Single { index } => {
344                    // `Variants::Single` on enums with variants denotes that
345                    // the enum delegates its layout to the variant at `index`.
346                    layout_of_variant(*index, None)
347                }
348                Variants::Multiple { tag, tag_encoding, tag_field, .. } => {
349                    // `Variants::Multiple` denotes an enum with multiple
350                    // variants. The layout of such an enum is the disjunction
351                    // of the layouts of its tagged variants.
352
353                    // For enums (but not coroutines), the tag field is
354                    // currently always the first field of the layout.
355                    assert_eq!(*tag_field, 0);
356
357                    let variants = def.discriminants(cx.tcx()).try_fold(
358                        Self::uninhabited(),
359                        |variants, (idx, ref discriminant)| {
360                            let variant = layout_of_variant(idx, Some(tag_encoding.clone()))?;
361                            Result::<Self, Err>::Ok(variants.or(variant))
362                        },
363                    )?;
364
365                    Ok(Self::def(Def::Adt(def)).then(variants))
366                }
367            }
368        }
369
370        /// Constructs a `Tree` from a 'variant-like' layout.
371        ///
372        /// A 'variant-like' layout includes those of structs and, of course,
373        /// enum variants. Pragmatically speaking, this method supports anything
374        /// with `FieldsShape::Arbitrary`.
375        ///
376        /// Note: This routine assumes that the optional `tag` is the first
377        /// field, and enum callers should check that `tag_field` is, in fact,
378        /// `0`.
379        fn from_variant(
380            def: Def<'tcx>,
381            tag: Option<(ScalarInt, VariantIdx, TagEncoding<VariantIdx>)>,
382            (ty, layout): (Ty<'tcx>, Layout<'tcx>),
383            total_size: Size,
384            cx: LayoutCx<'tcx>,
385        ) -> Result<Self, Err> {
386            // This constructor does not support non-`FieldsShape::Arbitrary`
387            // layouts.
388            let FieldsShape::Arbitrary { offsets, memory_index } = layout.fields() else {
389                return Err(Err::NotYetSupported);
390            };
391
392            // When this function is invoked with enum variants,
393            // `ty_and_layout.size` does not encompass the entire size of the
394            // enum. We rely on `total_size` for this.
395            assert!(layout.size <= total_size);
396
397            let mut size = Size::ZERO;
398            let mut struct_tree = Self::def(def);
399
400            // If a `tag` is provided, place it at the start of the layout.
401            if let Some((tag, index, encoding)) = &tag {
402                match encoding {
403                    TagEncoding::Direct => {
404                        size += tag.size();
405                    }
406                    TagEncoding::Niche { niche_variants, .. } => {
407                        if !niche_variants.contains(index) {
408                            size += tag.size();
409                        }
410                    }
411                }
412                struct_tree = struct_tree.then(Self::from_tag(*tag, cx.tcx()));
413            }
414
415            // Append the fields, in memory order, to the layout.
416            let inverse_memory_index = memory_index.invert_bijective_mapping();
417            for (memory_idx, &field_idx) in inverse_memory_index.iter_enumerated() {
418                // Add interfield padding.
419                let padding_needed = offsets[field_idx] - size;
420                let padding = Self::padding(padding_needed.bytes_usize());
421
422                let field_ty = ty_field(cx, (ty, layout), field_idx);
423                let field_layout = layout_of(cx, field_ty)?;
424                let field_tree = Self::from_ty(field_ty, cx)?;
425
426                struct_tree = struct_tree.then(padding).then(field_tree);
427
428                size += padding_needed + field_layout.size;
429            }
430
431            // Add trailing padding.
432            let padding_needed = total_size - size;
433            let trailing_padding = Self::padding(padding_needed.bytes_usize());
434
435            Ok(struct_tree.then(trailing_padding))
436        }
437
438        /// Constructs a `Tree` representing the value of a enum tag.
439        fn from_tag(tag: ScalarInt, tcx: TyCtxt<'tcx>) -> Self {
440            use rustc_abi::Endian;
441            let size = tag.size();
442            let bits = tag.to_bits(size);
443            let bytes: [u8; 16];
444            let bytes = match tcx.data_layout.endian {
445                Endian::Little => {
446                    bytes = bits.to_le_bytes();
447                    &bytes[..size.bytes_usize()]
448                }
449                Endian::Big => {
450                    bytes = bits.to_be_bytes();
451                    &bytes[bytes.len() - size.bytes_usize()..]
452                }
453            };
454            Self::Seq(bytes.iter().map(|&b| Self::from_bits(b)).collect())
455        }
456
457        /// Constructs a `Tree` from a union.
458        ///
459        /// # Panics
460        ///
461        /// Panics if `def` is not a union definition.
462        fn from_union(
463            (ty, layout): (Ty<'tcx>, Layout<'tcx>),
464            def: AdtDef<'tcx>,
465            cx: LayoutCx<'tcx>,
466        ) -> Result<Self, Err> {
467            assert!(def.is_union());
468
469            // This constructor does not support non-`FieldsShape::Union`
470            // layouts. Fields of this shape are all placed at offset 0.
471            let FieldsShape::Union(fields) = layout.fields() else {
472                return Err(Err::NotYetSupported);
473            };
474
475            let fields = &def.non_enum_variant().fields;
476            let fields = fields.iter_enumerated().try_fold(
477                Self::uninhabited(),
478                |fields, (idx, field_def)| {
479                    let field_def = Def::Field(field_def);
480                    let field_ty = ty_field(cx, (ty, layout), idx);
481                    let field_layout = layout_of(cx, field_ty)?;
482                    let field = Self::from_ty(field_ty, cx)?;
483                    let trailing_padding_needed = layout.size - field_layout.size;
484                    let trailing_padding = Self::padding(trailing_padding_needed.bytes_usize());
485                    let field_and_padding = field.then(trailing_padding);
486                    Result::<Self, Err>::Ok(fields.or(field_and_padding))
487                },
488            )?;
489
490            Ok(Self::def(Def::Adt(def)).then(fields))
491        }
492    }
493
494    fn ty_field<'tcx>(
495        cx: LayoutCx<'tcx>,
496        (ty, layout): (Ty<'tcx>, Layout<'tcx>),
497        i: FieldIdx,
498    ) -> Ty<'tcx> {
499        // We cannot use `ty_and_layout_field` to retrieve the field type, since
500        // `ty_and_layout_field` erases regions in the returned type. We must
501        // not erase regions here, since we may need to ultimately emit outlives
502        // obligations as a consequence of the transmutability analysis.
503        match ty.kind() {
504            ty::Adt(def, args) => {
505                match layout.variants {
506                    Variants::Single { index } => {
507                        let field = &def.variant(index).fields[i];
508                        field.ty(cx.tcx(), args)
509                    }
510                    Variants::Empty => panic!("there is no field in Variants::Empty types"),
511                    // Discriminant field for enums (where applicable).
512                    Variants::Multiple { tag, .. } => {
513                        assert_eq!(i.as_usize(), 0);
514                        ty::layout::PrimitiveExt::to_ty(&tag.primitive(), cx.tcx())
515                    }
516                }
517            }
518            ty::Tuple(fields) => fields[i.as_usize()],
519            kind @ _ => unimplemented!(
520                "only a subset of `Ty::ty_and_layout_field`'s functionality is implemented. implementation needed for {:?}",
521                kind
522            ),
523        }
524    }
525
526    fn ty_variant<'tcx>(
527        cx: LayoutCx<'tcx>,
528        (ty, layout): (Ty<'tcx>, Layout<'tcx>),
529        i: VariantIdx,
530    ) -> Layout<'tcx> {
531        let ty = cx.tcx().erase_regions(ty);
532        TyAndLayout { ty, layout }.for_variant(&cx, i).layout
533    }
534}
rustc_transmute/layout/tree.rs

rustc_transmute/layout/
tree.rs
