diff options
Diffstat (limited to 'compiler/rustc_transmute/src/layout/tree.rs')
| -rw-r--r-- | compiler/rustc_transmute/src/layout/tree.rs | 471 |
1 files changed, 471 insertions, 0 deletions
diff --git a/compiler/rustc_transmute/src/layout/tree.rs b/compiler/rustc_transmute/src/layout/tree.rs new file mode 100644 index 000000000..70b3ba02b --- /dev/null +++ b/compiler/rustc_transmute/src/layout/tree.rs @@ -0,0 +1,471 @@ +use super::{Byte, Def, Ref}; + +#[cfg(test)] +mod tests; + +/// A tree-based representation of a type layout. +/// +/// Invariants: +/// 1. All paths through the layout have the same length (in bytes). +/// +/// Nice-to-haves: +/// 1. An `Alt` is never directly nested beneath another `Alt`. +/// 2. A `Seq` is never directly nested beneath another `Seq`. +/// 3. `Seq`s and `Alt`s with a single member do not exist. +#[derive(Clone, Debug, Hash, PartialEq, Eq)] +pub(crate) enum Tree<D, R> +where + D: Def, + R: Ref, +{ + /// A sequence of successive layouts. + Seq(Vec<Self>), + /// A choice between alternative layouts. + Alt(Vec<Self>), + /// A definition node. + Def(D), + /// A reference node. + Ref(R), + /// A byte node. + Byte(Byte), +} + +impl<D, R> Tree<D, R> +where + D: Def, + R: Ref, +{ + /// A `Tree` consisting only of a definition node. + pub(crate) fn def(def: D) -> Self { + Self::Def(def) + } + + /// A `Tree` representing an uninhabited type. + pub(crate) fn uninhabited() -> Self { + Self::Alt(vec![]) + } + + /// A `Tree` representing a zero-sized type. + pub(crate) fn unit() -> Self { + Self::Seq(Vec::new()) + } + + /// A `Tree` containing a single, uninitialized byte. + pub(crate) fn uninit() -> Self { + Self::Byte(Byte::Uninit) + } + + /// A `Tree` representing the layout of `bool`. + pub(crate) fn bool() -> Self { + Self::from_bits(0x00).or(Self::from_bits(0x01)) + } + + /// A `Tree` whose layout matches that of a `u8`. + pub(crate) fn u8() -> Self { + Self::Alt((0u8..=255).map(Self::from_bits).collect()) + } + + /// A `Tree` whose layout accepts exactly the given bit pattern. + pub(crate) fn from_bits(bits: u8) -> Self { + Self::Byte(Byte::Init(bits)) + } + + /// A `Tree` whose layout is a number of the given width. + pub(crate) fn number(width_in_bytes: usize) -> Self { + Self::Seq(vec![Self::u8(); width_in_bytes]) + } + + /// A `Tree` whose layout is entirely padding of the given width. + pub(crate) fn padding(width_in_bytes: usize) -> Self { + Self::Seq(vec![Self::uninit(); width_in_bytes]) + } + + /// Remove all `Def` nodes, and all branches of the layout for which `f` produces false. + pub(crate) fn prune<F>(self, f: &F) -> Tree<!, R> + where + F: Fn(D) -> bool, + { + match self { + Self::Seq(elts) => elts + .into_iter() + .map(|elt| elt.prune(f)) + .try_fold(Tree::unit(), |elts, elt| { + if elt == Tree::uninhabited() { + Err(Tree::uninhabited()) + } else { + Ok(elts.then(elt)) + } + }) + .into_ok_or_err(), + Self::Alt(alts) => alts + .into_iter() + .map(|alt| alt.prune(f)) + .fold(Tree::uninhabited(), |alts, alt| alts.or(alt)), + Self::Byte(b) => Tree::Byte(b), + Self::Ref(r) => Tree::Ref(r), + Self::Def(d) => { + if !f(d) { + Tree::uninhabited() + } else { + Tree::unit() + } + } + } + } + + /// Produces `true` if `Tree` is an inhabited type; otherwise false. + pub(crate) fn is_inhabited(&self) -> bool { + match self { + Self::Seq(elts) => elts.into_iter().all(|elt| elt.is_inhabited()), + Self::Alt(alts) => alts.into_iter().any(|alt| alt.is_inhabited()), + Self::Byte(..) | Self::Ref(..) | Self::Def(..) => true, + } + } +} + +impl<D, R> Tree<D, R> +where + D: Def, + R: Ref, +{ + /// Produces a new `Tree` where `other` is sequenced after `self`. + pub(crate) fn then(self, other: Self) -> Self { + match (self, other) { + (Self::Seq(elts), other) | (other, Self::Seq(elts)) if elts.len() == 0 => other, + (Self::Seq(mut lhs), Self::Seq(mut rhs)) => { + lhs.append(&mut rhs); + Self::Seq(lhs) + } + (Self::Seq(mut lhs), rhs) => { + lhs.push(rhs); + Self::Seq(lhs) + } + (lhs, Self::Seq(mut rhs)) => { + rhs.insert(0, lhs); + Self::Seq(rhs) + } + (lhs, rhs) => Self::Seq(vec![lhs, rhs]), + } + } + + /// Produces a new `Tree` accepting either `self` or `other` as alternative layouts. + pub(crate) fn or(self, other: Self) -> Self { + match (self, other) { + (Self::Alt(alts), other) | (other, Self::Alt(alts)) if alts.len() == 0 => other, + (Self::Alt(mut lhs), Self::Alt(rhs)) => { + lhs.extend(rhs); + Self::Alt(lhs) + } + (Self::Alt(mut alts), alt) | (alt, Self::Alt(mut alts)) => { + alts.push(alt); + Self::Alt(alts) + } + (lhs, rhs) => Self::Alt(vec![lhs, rhs]), + } + } +} + +#[derive(Debug, Copy, Clone)] +pub(crate) enum Err { + /// The layout of the type is unspecified. + Unspecified, + /// This error will be surfaced elsewhere by rustc, so don't surface it. + Unknown, +} + +#[cfg(feature = "rustc")] +pub(crate) mod rustc { + use super::{Err, Tree}; + use crate::layout::rustc::{Def, Ref}; + + use rustc_middle::ty; + use rustc_middle::ty::layout::LayoutError; + use rustc_middle::ty::util::Discr; + use rustc_middle::ty::AdtDef; + use rustc_middle::ty::ParamEnv; + use rustc_middle::ty::SubstsRef; + use rustc_middle::ty::Ty; + use rustc_middle::ty::TyCtxt; + use rustc_middle::ty::VariantDef; + use rustc_target::abi::Align; + use std::alloc; + + impl<'tcx> From<LayoutError<'tcx>> for Err { + fn from(err: LayoutError<'tcx>) -> Self { + match err { + LayoutError::Unknown(..) => Self::Unknown, + err @ _ => unimplemented!("{:?}", err), + } + } + } + + trait LayoutExt { + fn clamp_align(&self, min_align: Align, max_align: Align) -> Self; + } + + impl LayoutExt for alloc::Layout { + fn clamp_align(&self, min_align: Align, max_align: Align) -> Self { + let min_align = min_align.bytes().try_into().unwrap(); + let max_align = max_align.bytes().try_into().unwrap(); + Self::from_size_align(self.size(), self.align().clamp(min_align, max_align)).unwrap() + } + } + + struct LayoutSummary { + total_align: Align, + total_size: usize, + discriminant_size: usize, + discriminant_align: Align, + } + + impl LayoutSummary { + fn from_ty<'tcx>(ty: Ty<'tcx>, ctx: TyCtxt<'tcx>) -> Result<Self, LayoutError<'tcx>> { + use rustc_middle::ty::ParamEnvAnd; + use rustc_target::abi::{TyAndLayout, Variants}; + + let param_env = ParamEnv::reveal_all(); + let param_env_and_type = ParamEnvAnd { param_env, value: ty }; + let TyAndLayout { layout, .. } = ctx.layout_of(param_env_and_type)?; + + let total_size: usize = layout.size().bytes_usize(); + let total_align: Align = layout.align().abi; + let discriminant_align: Align; + let discriminant_size: usize; + + if let Variants::Multiple { tag, .. } = layout.variants() { + discriminant_align = tag.align(&ctx).abi; + discriminant_size = tag.size(&ctx).bytes_usize(); + } else { + discriminant_align = Align::ONE; + discriminant_size = 0; + }; + + Ok(Self { total_align, total_size, discriminant_align, discriminant_size }) + } + + fn into(&self) -> alloc::Layout { + alloc::Layout::from_size_align( + self.total_size, + self.total_align.bytes().try_into().unwrap(), + ) + .unwrap() + } + } + + impl<'tcx> Tree<Def<'tcx>, Ref<'tcx>> { + pub fn from_ty(ty: Ty<'tcx>, tcx: TyCtxt<'tcx>) -> Result<Self, Err> { + use rustc_middle::ty::FloatTy::*; + use rustc_middle::ty::IntTy::*; + use rustc_middle::ty::UintTy::*; + use rustc_target::abi::HasDataLayout; + + let target = tcx.data_layout(); + + match ty.kind() { + ty::Bool => Ok(Self::bool()), + + ty::Int(I8) | ty::Uint(U8) => Ok(Self::u8()), + ty::Int(I16) | ty::Uint(U16) => Ok(Self::number(2)), + ty::Int(I32) | ty::Uint(U32) | ty::Float(F32) => Ok(Self::number(4)), + ty::Int(I64) | ty::Uint(U64) | ty::Float(F64) => Ok(Self::number(8)), + ty::Int(I128) | ty::Uint(U128) => Ok(Self::number(16)), + ty::Int(Isize) | ty::Uint(Usize) => { + Ok(Self::number(target.pointer_size.bytes_usize())) + } + + ty::Tuple(members) => { + if members.len() == 0 { + Ok(Tree::unit()) + } else { + Err(Err::Unspecified) + } + } + + ty::Array(ty, len) => { + let len = len.try_eval_usize(tcx, ParamEnv::reveal_all()).unwrap(); + let elt = Tree::from_ty(*ty, tcx)?; + Ok(std::iter::repeat(elt) + .take(len as usize) + .fold(Tree::unit(), |tree, elt| tree.then(elt))) + } + + ty::Adt(adt_def, substs_ref) => { + use rustc_middle::ty::AdtKind; + + // If the layout is ill-specified, halt. + if !(adt_def.repr().c() || adt_def.repr().int.is_some()) { + return Err(Err::Unspecified); + } + + // Compute a summary of the type's layout. + let layout_summary = LayoutSummary::from_ty(ty, tcx)?; + + // The layout begins with this adt's visibility. + let vis = Self::def(Def::Adt(*adt_def)); + + // And is followed the layout(s) of its variants + Ok(vis.then(match adt_def.adt_kind() { + AdtKind::Struct => Self::from_repr_c_variant( + ty, + *adt_def, + substs_ref, + &layout_summary, + None, + adt_def.non_enum_variant(), + tcx, + )?, + AdtKind::Enum => { + tracing::trace!(?adt_def, "treeifying enum"); + let mut tree = Tree::uninhabited(); + + for (idx, discr) in adt_def.discriminants(tcx) { + tree = tree.or(Self::from_repr_c_variant( + ty, + *adt_def, + substs_ref, + &layout_summary, + Some(discr), + adt_def.variant(idx), + tcx, + )?); + } + + tree + } + AdtKind::Union => { + // is the layout well-defined? + if !adt_def.repr().c() { + return Err(Err::Unspecified); + } + + let ty_layout = layout_of(tcx, ty)?; + + let mut tree = Tree::uninhabited(); + + for field in adt_def.all_fields() { + let variant_ty = field.ty(tcx, substs_ref); + let variant_layout = layout_of(tcx, variant_ty)?; + let padding_needed = ty_layout.size() - variant_layout.size(); + let variant = Self::def(Def::Field(field)) + .then(Self::from_ty(variant_ty, tcx)?) + .then(Self::padding(padding_needed)); + + tree = tree.or(variant); + } + + tree + } + })) + } + _ => Err(Err::Unspecified), + } + } + + fn from_repr_c_variant( + ty: Ty<'tcx>, + adt_def: AdtDef<'tcx>, + substs_ref: SubstsRef<'tcx>, + layout_summary: &LayoutSummary, + discr: Option<Discr<'tcx>>, + variant_def: &'tcx VariantDef, + tcx: TyCtxt<'tcx>, + ) -> Result<Self, Err> { + let mut tree = Tree::unit(); + + let repr = adt_def.repr(); + let min_align = repr.align.unwrap_or(Align::ONE); + let max_align = repr.pack.unwrap_or(Align::MAX); + + let clamp = + |align: Align| align.clamp(min_align, max_align).bytes().try_into().unwrap(); + + let variant_span = tracing::trace_span!( + "treeifying variant", + min_align = ?min_align, + max_align = ?max_align, + ) + .entered(); + + let mut variant_layout = alloc::Layout::from_size_align( + 0, + layout_summary.total_align.bytes().try_into().unwrap(), + ) + .unwrap(); + + // The layout of the variant is prefixed by the discriminant, if any. + if let Some(discr) = discr { + tracing::trace!(?discr, "treeifying discriminant"); + let discr_layout = alloc::Layout::from_size_align( + layout_summary.discriminant_size, + clamp(layout_summary.discriminant_align), + ) + .unwrap(); + tracing::trace!(?discr_layout, "computed discriminant layout"); + variant_layout = variant_layout.extend(discr_layout).unwrap().0; + tree = tree.then(Self::from_disr(discr, tcx, layout_summary.discriminant_size)); + } + + // Next come fields. + let fields_span = tracing::trace_span!("treeifying fields").entered(); + for field_def in variant_def.fields.iter() { + let field_ty = field_def.ty(tcx, substs_ref); + let _span = tracing::trace_span!("treeifying field", field = ?field_ty).entered(); + + // begin with the field's visibility + tree = tree.then(Self::def(Def::Field(field_def))); + + // compute the field's layout charactaristics + let field_layout = layout_of(tcx, field_ty)?.clamp_align(min_align, max_align); + + // next comes the field's padding + let padding_needed = variant_layout.padding_needed_for(field_layout.align()); + if padding_needed > 0 { + tree = tree.then(Self::padding(padding_needed)); + } + + // finally, the field's layout + tree = tree.then(Self::from_ty(field_ty, tcx)?); + + // extend the variant layout with the field layout + variant_layout = variant_layout.extend(field_layout).unwrap().0; + } + drop(fields_span); + + // finally: padding + let padding_span = tracing::trace_span!("adding trailing padding").entered(); + let padding_needed = layout_summary.total_size - variant_layout.size(); + if padding_needed > 0 { + tree = tree.then(Self::padding(padding_needed)); + }; + drop(padding_span); + drop(variant_span); + Ok(tree) + } + + pub fn from_disr(discr: Discr<'tcx>, tcx: TyCtxt<'tcx>, size: usize) -> Self { + // FIXME(@jswrenn): I'm certain this is missing needed endian nuance. + let bytes = discr.val.to_ne_bytes(); + let bytes = &bytes[..size]; + Self::Seq(bytes.into_iter().copied().map(|b| Self::from_bits(b)).collect()) + } + } + + fn layout_of<'tcx>( + ctx: TyCtxt<'tcx>, + ty: Ty<'tcx>, + ) -> Result<alloc::Layout, LayoutError<'tcx>> { + use rustc_middle::ty::ParamEnvAnd; + use rustc_target::abi::TyAndLayout; + + let param_env = ParamEnv::reveal_all(); + let param_env_and_type = ParamEnvAnd { param_env, value: ty }; + let TyAndLayout { layout, .. } = ctx.layout_of(param_env_and_type)?; + let layout = alloc::Layout::from_size_align( + layout.size().bytes_usize(), + layout.align().abi.bytes().try_into().unwrap(), + ) + .unwrap(); + tracing::trace!(?ty, ?layout, "computed layout for type"); + Ok(layout) + } +} |