compiler/rustc_transmute/src/layout/tree.rs

   1 use super::{Byte, Def, Ref};
   2 use std::ops::ControlFlow;
   3
   4 #[cfg(test)]
   5 mod tests;
   6
   7 /// A tree-based representation of a type layout.
   8 ///
   9 /// Invariants:
  10 /// 1. All paths through the layout have the same length (in bytes).
  11 ///
  12 /// Nice-to-haves:
  13 /// 1. An `Alt` is never directly nested beneath another `Alt`.
  14 /// 2. A `Seq` is never directly nested beneath another `Seq`.
  15 /// 3. `Seq`s and `Alt`s with a single member do not exist.
  16 #[derive(Clone, Debug, Hash, PartialEq, Eq)]
  17 pub(crate) enum Tree<D, R>
  18 where
  19     D: Def,
  20     R: Ref,
  21 {
  22     /// A sequence of successive layouts.
  23     Seq(Vec<Self>),
  24     /// A choice between alternative layouts.
  25     Alt(Vec<Self>),
  26     /// A definition node.
  27     Def(D),
  28     /// A reference node.
  29     Ref(R),
  30     /// A byte node.
  31     Byte(Byte),
  32 }
  33
  34 impl<D, R> Tree<D, R>
  35 where
  36     D: Def,
  37     R: Ref,
  38 {
  39     /// A `Tree` consisting only of a definition node.
  40     pub(crate) fn def(def: D) -> Self {
  41         Self::Def(def)
  42     }
  43
  44     /// A `Tree` representing an uninhabited type.
  45     pub(crate) fn uninhabited() -> Self {
  46         Self::Alt(vec![])
  47     }
  48
  49     /// A `Tree` representing a zero-sized type.
  50     pub(crate) fn unit() -> Self {
  51         Self::Seq(Vec::new())
  52     }
  53
  54     /// A `Tree` containing a single, uninitialized byte.
  55     pub(crate) fn uninit() -> Self {
  56         Self::Byte(Byte::Uninit)
  57     }
  58
  59     /// A `Tree` representing the layout of `bool`.
  60     pub(crate) fn bool() -> Self {
  61         Self::from_bits(0x00).or(Self::from_bits(0x01))
  62     }
  63
  64     /// A `Tree` whose layout matches that of a `u8`.
  65     pub(crate) fn u8() -> Self {
  66         Self::Alt((0u8..=255).map(Self::from_bits).collect())
  67     }
  68
  69     /// A `Tree` whose layout accepts exactly the given bit pattern.
  70     pub(crate) fn from_bits(bits: u8) -> Self {
  71         Self::Byte(Byte::Init(bits))
  72     }
  73
  74     /// A `Tree` whose layout is a number of the given width.
  75     pub(crate) fn number(width_in_bytes: usize) -> Self {
  76         Self::Seq(vec![Self::u8(); width_in_bytes])
  77     }
  78
  79     /// A `Tree` whose layout is entirely padding of the given width.
  80     pub(crate) fn padding(width_in_bytes: usize) -> Self {
  81         Self::Seq(vec![Self::uninit(); width_in_bytes])
  82     }
  83
  84     /// Remove all `Def` nodes, and all branches of the layout for which `f` produces false.
  85     pub(crate) fn prune<F>(self, f: &F) -> Tree<!, R>
  86     where
  87         F: Fn(D) -> bool,
  88     {
  89         match self {
  90             Self::Seq(elts) => match elts.into_iter().map(|elt| elt.prune(f)).try_fold(
  91                 Tree::unit(),
  92                 |elts, elt| {
  93                     if elt == Tree::uninhabited() {
  94                         ControlFlow::Break(Tree::uninhabited())
  95                     } else {
  96                         ControlFlow::Continue(elts.then(elt))
  97                     }
  98                 },
  99             ) {
 100                 ControlFlow::Break(node) | ControlFlow::Continue(node) => node,
 101             },
 102             Self::Alt(alts) => alts
 103                 .into_iter()
 104                 .map(|alt| alt.prune(f))
 105                 .fold(Tree::uninhabited(), |alts, alt| alts.or(alt)),
 106             Self::Byte(b) => Tree::Byte(b),
 107             Self::Ref(r) => Tree::Ref(r),
 108             Self::Def(d) => {
 109                 if !f(d) {
 110                     Tree::uninhabited()
 111                 } else {
 112                     Tree::unit()
 113                 }
 114             }
 115         }
 116     }
 117
 118     /// Produces `true` if `Tree` is an inhabited type; otherwise false.
 119     pub(crate) fn is_inhabited(&self) -> bool {
 120         match self {
 121             Self::Seq(elts) => elts.into_iter().all(|elt| elt.is_inhabited()),
 122             Self::Alt(alts) => alts.into_iter().any(|alt| alt.is_inhabited()),
 123             Self::Byte(..) | Self::Ref(..) | Self::Def(..) => true,
 124         }
 125     }
 126 }
 127
 128 impl<D, R> Tree<D, R>
 129 where
 130     D: Def,
 131     R: Ref,
 132 {
 133     /// Produces a new `Tree` where `other` is sequenced after `self`.
 134     pub(crate) fn then(self, other: Self) -> Self {
 135         match (self, other) {
 136             (Self::Seq(elts), other) | (other, Self::Seq(elts)) if elts.len() == 0 => other,
 137             (Self::Seq(mut lhs), Self::Seq(mut rhs)) => {
 138                 lhs.append(&mut rhs);
 139                 Self::Seq(lhs)
 140             }
 141             (Self::Seq(mut lhs), rhs) => {
 142                 lhs.push(rhs);
 143                 Self::Seq(lhs)
 144             }
 145             (lhs, Self::Seq(mut rhs)) => {
 146                 rhs.insert(0, lhs);
 147                 Self::Seq(rhs)
 148             }
 149             (lhs, rhs) => Self::Seq(vec![lhs, rhs]),
 150         }
 151     }
 152
 153     /// Produces a new `Tree` accepting either `self` or `other` as alternative layouts.
 154     pub(crate) fn or(self, other: Self) -> Self {
 155         match (self, other) {
 156             (Self::Alt(alts), other) | (other, Self::Alt(alts)) if alts.len() == 0 => other,
 157             (Self::Alt(mut lhs), Self::Alt(rhs)) => {
 158                 lhs.extend(rhs);
 159                 Self::Alt(lhs)
 160             }
 161             (Self::Alt(mut alts), alt) | (alt, Self::Alt(mut alts)) => {
 162                 alts.push(alt);
 163                 Self::Alt(alts)
 164             }
 165             (lhs, rhs) => Self::Alt(vec![lhs, rhs]),
 166         }
 167     }
 168 }
 169
 170 #[derive(Debug, Copy, Clone)]
 171 pub(crate) enum Err {
 172     /// The layout of the type is unspecified.
 173     Unspecified,
 174     /// This error will be surfaced elsewhere by rustc, so don't surface it.
 175     Unknown,
 176 }
 177
 178 #[cfg(feature = "rustc")]
 179 pub(crate) mod rustc {
 180     use super::{Err, Tree};
 181     use crate::layout::rustc::{Def, Ref};
 182
 183     use rustc_middle::ty;
 184     use rustc_middle::ty::layout::LayoutError;
 185     use rustc_middle::ty::util::Discr;
 186     use rustc_middle::ty::AdtDef;
 187     use rustc_middle::ty::ParamEnv;
 188     use rustc_middle::ty::SubstsRef;
 189     use rustc_middle::ty::Ty;
 190     use rustc_middle::ty::TyCtxt;
 191     use rustc_middle::ty::VariantDef;
 192     use rustc_target::abi::Align;
 193     use std::alloc;
 194
 195     impl<'tcx> From<LayoutError<'tcx>> for Err {
 196         fn from(err: LayoutError<'tcx>) -> Self {
 197             match err {
 198                 LayoutError::Unknown(..) => Self::Unknown,
 199                 err @ _ => unimplemented!("{:?}", err),
 200             }
 201         }
 202     }
 203
 204     trait LayoutExt {
 205         fn clamp_align(&self, min_align: Align, max_align: Align) -> Self;
 206     }
 207
 208     impl LayoutExt for alloc::Layout {
 209         fn clamp_align(&self, min_align: Align, max_align: Align) -> Self {
 210             let min_align = min_align.bytes().try_into().unwrap();
 211             let max_align = max_align.bytes().try_into().unwrap();
 212             Self::from_size_align(self.size(), self.align().clamp(min_align, max_align)).unwrap()
 213         }
 214     }
 215
 216     struct LayoutSummary {
 217         total_align: Align,
 218         total_size: usize,
 219         discriminant_size: usize,
 220         discriminant_align: Align,
 221     }
 222
 223     impl LayoutSummary {
 224         fn from_ty<'tcx>(ty: Ty<'tcx>, ctx: TyCtxt<'tcx>) -> Result<Self, LayoutError<'tcx>> {
 225             use rustc_middle::ty::ParamEnvAnd;
 226             use rustc_target::abi::{TyAndLayout, Variants};
 227
 228             let param_env = ParamEnv::reveal_all();
 229             let param_env_and_type = ParamEnvAnd { param_env, value: ty };
 230             let TyAndLayout { layout, .. } = ctx.layout_of(param_env_and_type)?;
 231
 232             let total_size: usize = layout.size().bytes_usize();
 233             let total_align: Align = layout.align().abi;
 234             let discriminant_align: Align;
 235             let discriminant_size: usize;
 236
 237             if let Variants::Multiple { tag, .. } = layout.variants() {
 238                 discriminant_align = tag.align(&ctx).abi;
 239                 discriminant_size = tag.size(&ctx).bytes_usize();
 240             } else {
 241                 discriminant_align = Align::ONE;
 242                 discriminant_size = 0;
 243             };
 244
 245             Ok(Self { total_align, total_size, discriminant_align, discriminant_size })
 246         }
 247
 248         fn into(&self) -> alloc::Layout {
 249             alloc::Layout::from_size_align(
 250                 self.total_size,
 251                 self.total_align.bytes().try_into().unwrap(),
 252             )
 253             .unwrap()
 254         }
 255     }
 256
 257     impl<'tcx> Tree<Def<'tcx>, Ref<'tcx>> {
 258         pub fn from_ty(ty: Ty<'tcx>, tcx: TyCtxt<'tcx>) -> Result<Self, Err> {
 259             use rustc_middle::ty::FloatTy::*;
 260             use rustc_middle::ty::IntTy::*;
 261             use rustc_middle::ty::UintTy::*;
 262             use rustc_target::abi::HasDataLayout;
 263
 264             let target = tcx.data_layout();
 265
 266             match ty.kind() {
 267                 ty::Bool => Ok(Self::bool()),
 268
 269                 ty::Int(I8) | ty::Uint(U8) => Ok(Self::u8()),
 270                 ty::Int(I16) | ty::Uint(U16) => Ok(Self::number(2)),
 271                 ty::Int(I32) | ty::Uint(U32) | ty::Float(F32) => Ok(Self::number(4)),
 272                 ty::Int(I64) | ty::Uint(U64) | ty::Float(F64) => Ok(Self::number(8)),
 273                 ty::Int(I128) | ty::Uint(U128) => Ok(Self::number(16)),
 274                 ty::Int(Isize) | ty::Uint(Usize) => {
 275                     Ok(Self::number(target.pointer_size.bytes_usize()))
 276                 }
 277
 278                 ty::Tuple(members) => {
 279                     if members.len() == 0 {
 280                         Ok(Tree::unit())
 281                     } else {
 282                         Err(Err::Unspecified)
 283                     }
 284                 }
 285
 286                 ty::Array(ty, len) => {
 287                     let len =
 288                         len.try_eval_usize(tcx, ParamEnv::reveal_all()).ok_or(Err::Unspecified)?;
 289                     let elt = Tree::from_ty(*ty, tcx)?;
 290                     Ok(std::iter::repeat(elt)
 291                         .take(len as usize)
 292                         .fold(Tree::unit(), |tree, elt| tree.then(elt)))
 293                 }
 294
 295                 ty::Adt(adt_def, substs_ref) => {
 296                     use rustc_middle::ty::AdtKind;
 297
 298                     // If the layout is ill-specified, halt.
 299                     if !(adt_def.repr().c() || adt_def.repr().int.is_some()) {
 300                         return Err(Err::Unspecified);
 301                     }
 302
 303                     // Compute a summary of the type's layout.
 304                     let layout_summary = LayoutSummary::from_ty(ty, tcx)?;
 305
 306                     // The layout begins with this adt's visibility.
 307                     let vis = Self::def(Def::Adt(*adt_def));
 308
 309                     // And is followed the layout(s) of its variants
 310                     Ok(vis.then(match adt_def.adt_kind() {
 311                         AdtKind::Struct => Self::from_repr_c_variant(
 312                             ty,
 313                             *adt_def,
 314                             substs_ref,
 315                             &layout_summary,
 316                             None,
 317                             adt_def.non_enum_variant(),
 318                             tcx,
 319                         )?,
 320                         AdtKind::Enum => {
 321                             trace!(?adt_def, "treeifying enum");
 322                             let mut tree = Tree::uninhabited();
 323
 324                             for (idx, discr) in adt_def.discriminants(tcx) {
 325                                 tree = tree.or(Self::from_repr_c_variant(
 326                                     ty,
 327                                     *adt_def,
 328                                     substs_ref,
 329                                     &layout_summary,
 330                                     Some(discr),
 331                                     adt_def.variant(idx),
 332                                     tcx,
 333                                 )?);
 334                             }
 335
 336                             tree
 337                         }
 338                         AdtKind::Union => {
 339                             // is the layout well-defined?
 340                             if !adt_def.repr().c() {
 341                                 return Err(Err::Unspecified);
 342                             }
 343
 344                             let ty_layout = layout_of(tcx, ty)?;
 345
 346                             let mut tree = Tree::uninhabited();
 347
 348                             for field in adt_def.all_fields() {
 349                                 let variant_ty = field.ty(tcx, substs_ref);
 350                                 let variant_layout = layout_of(tcx, variant_ty)?;
 351                                 let padding_needed = ty_layout.size() - variant_layout.size();
 352                                 let variant = Self::def(Def::Field(field))
 353                                     .then(Self::from_ty(variant_ty, tcx)?)
 354                                     .then(Self::padding(padding_needed));
 355
 356                                 tree = tree.or(variant);
 357                             }
 358
 359                             tree
 360                         }
 361                     }))
 362                 }
 363                 _ => Err(Err::Unspecified),
 364             }
 365         }
 366
 367         fn from_repr_c_variant(
 368             ty: Ty<'tcx>,
 369             adt_def: AdtDef<'tcx>,
 370             substs_ref: SubstsRef<'tcx>,
 371             layout_summary: &LayoutSummary,
 372             discr: Option<Discr<'tcx>>,
 373             variant_def: &'tcx VariantDef,
 374             tcx: TyCtxt<'tcx>,
 375         ) -> Result<Self, Err> {
 376             let mut tree = Tree::unit();
 377
 378             let repr = adt_def.repr();
 379             let min_align = repr.align.unwrap_or(Align::ONE);
 380             let max_align = repr.pack.unwrap_or(Align::MAX);
 381
 382             let clamp =
 383                 |align: Align| align.clamp(min_align, max_align).bytes().try_into().unwrap();
 384
 385             let variant_span = trace_span!(
 386                 "treeifying variant",
 387                 min_align = ?min_align,
 388                 max_align = ?max_align,
 389             )
 390             .entered();
 391
 392             let mut variant_layout = alloc::Layout::from_size_align(
 393                 0,
 394                 layout_summary.total_align.bytes().try_into().unwrap(),
 395             )
 396             .unwrap();
 397
 398             // The layout of the variant is prefixed by the discriminant, if any.
 399             if let Some(discr) = discr {
 400                 trace!(?discr, "treeifying discriminant");
 401                 let discr_layout = alloc::Layout::from_size_align(
 402                     layout_summary.discriminant_size,
 403                     clamp(layout_summary.discriminant_align),
 404                 )
 405                 .unwrap();
 406                 trace!(?discr_layout, "computed discriminant layout");
 407                 variant_layout = variant_layout.extend(discr_layout).unwrap().0;
 408                 tree = tree.then(Self::from_discr(discr, tcx, layout_summary.discriminant_size));
 409             }
 410
 411             // Next come fields.
 412             let fields_span = trace_span!("treeifying fields").entered();
 413             for field_def in variant_def.fields.iter() {
 414                 let field_ty = field_def.ty(tcx, substs_ref);
 415                 let _span = trace_span!("treeifying field", field = ?field_ty).entered();
 416
 417                 // begin with the field's visibility
 418                 tree = tree.then(Self::def(Def::Field(field_def)));
 419
 420                 // compute the field's layout characteristics
 421                 let field_layout = layout_of(tcx, field_ty)?.clamp_align(min_align, max_align);
 422
 423                 // next comes the field's padding
 424                 let padding_needed = variant_layout.padding_needed_for(field_layout.align());
 425                 if padding_needed > 0 {
 426                     tree = tree.then(Self::padding(padding_needed));
 427                 }
 428
 429                 // finally, the field's layout
 430                 tree = tree.then(Self::from_ty(field_ty, tcx)?);
 431
 432                 // extend the variant layout with the field layout
 433                 variant_layout = variant_layout.extend(field_layout).unwrap().0;
 434             }
 435             drop(fields_span);
 436
 437             // finally: padding
 438             let padding_span = trace_span!("adding trailing padding").entered();
 439             if layout_summary.total_size > variant_layout.size() {
 440                 let padding_needed = layout_summary.total_size - variant_layout.size();
 441                 tree = tree.then(Self::padding(padding_needed));
 442             };
 443             drop(padding_span);
 444             drop(variant_span);
 445             Ok(tree)
 446         }
 447
 448         pub fn from_discr(discr: Discr<'tcx>, tcx: TyCtxt<'tcx>, size: usize) -> Self {
 449             use rustc_target::abi::Endian;
 450
 451             let bytes: [u8; 16];
 452             let bytes = match tcx.data_layout.endian {
 453                 Endian::Little => {
 454                     bytes = discr.val.to_le_bytes();
 455                     &bytes[..size]
 456                 }
 457                 Endian::Big => {
 458                     bytes = discr.val.to_be_bytes();
 459                     &bytes[bytes.len() - size..]
 460                 }
 461             };
 462             Self::Seq(bytes.iter().map(|&b| Self::from_bits(b)).collect())
 463         }
 464     }
 465
 466     fn layout_of<'tcx>(
 467         ctx: TyCtxt<'tcx>,
 468         ty: Ty<'tcx>,
 469     ) -> Result<alloc::Layout, LayoutError<'tcx>> {
 470         use rustc_middle::ty::ParamEnvAnd;
 471         use rustc_target::abi::TyAndLayout;
 472
 473         let param_env = ParamEnv::reveal_all();
 474         let param_env_and_type = ParamEnvAnd { param_env, value: ty };
 475         let TyAndLayout { layout, .. } = ctx.layout_of(param_env_and_type)?;
 476         let layout = alloc::Layout::from_size_align(
 477             layout.size().bytes_usize(),
 478             layout.align().abi.bytes().try_into().unwrap(),
 479         )
 480         .unwrap();
 481         trace!(?ty, ?layout, "computed layout for type");
 482         Ok(layout)
 483     }
 484 }