compiler/rustc_transmute/src/layout/tree.rs

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