1 use super::{Byte, Def, Ref};
2 use std::ops::ControlFlow;
7 /// A tree-based representation of a type layout.
10 /// 1. All paths through the layout have the same length (in bytes).
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>
22 /// A sequence of successive layouts.
24 /// A choice between alternative layouts.
26 /// A definition node.
39 /// A `Tree` consisting only of a definition node.
40 pub(crate) fn def(def: D) -> Self {
44 /// A `Tree` representing an uninhabited type.
45 pub(crate) fn uninhabited() -> Self {
49 /// A `Tree` representing a zero-sized type.
50 pub(crate) fn unit() -> Self {
54 /// A `Tree` containing a single, uninitialized byte.
55 pub(crate) fn uninit() -> Self {
56 Self::Byte(Byte::Uninit)
59 /// A `Tree` representing the layout of `bool`.
60 pub(crate) fn bool() -> Self {
61 Self::from_bits(0x00).or(Self::from_bits(0x01))
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())
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))
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])
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])
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>
90 Self::Seq(elts) => match elts.into_iter().map(|elt| elt.prune(f)).try_fold(
93 if elt == Tree::uninhabited() {
94 ControlFlow::Break(Tree::uninhabited())
96 ControlFlow::Continue(elts.then(elt))
100 ControlFlow::Break(node) | ControlFlow::Continue(node) => node,
102 Self::Alt(alts) => alts
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),
118 /// Produces `true` if `Tree` is an inhabited type; otherwise false.
119 pub(crate) fn is_inhabited(&self) -> bool {
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,
128 impl<D, R> Tree<D, R>
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);
141 (Self::Seq(mut lhs), rhs) => {
145 (lhs, Self::Seq(mut rhs)) => {
149 (lhs, rhs) => Self::Seq(vec![lhs, rhs]),
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)) => {
161 (Self::Alt(mut alts), alt) | (alt, Self::Alt(mut alts)) => {
165 (lhs, rhs) => Self::Alt(vec![lhs, rhs]),
170 #[derive(Debug, Copy, Clone)]
171 pub(crate) enum Err {
172 /// The layout of the type is unspecified.
174 /// This error will be surfaced elsewhere by rustc, so don't surface it.
178 #[cfg(feature = "rustc")]
179 pub(crate) mod rustc {
180 use super::{Err, Tree};
181 use crate::layout::rustc::{Def, Ref};
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;
195 impl<'tcx> From<LayoutError<'tcx>> for Err {
196 fn from(err: LayoutError<'tcx>) -> Self {
198 LayoutError::Unknown(..) => Self::Unknown,
199 err @ _ => unimplemented!("{:?}", err),
205 fn clamp_align(&self, min_align: Align, max_align: Align) -> Self;
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()
216 struct LayoutSummary {
219 discriminant_size: usize,
220 discriminant_align: Align,
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};
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)?;
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;
237 if let Variants::Multiple { tag, .. } = layout.variants() {
238 discriminant_align = tag.align(&ctx).abi;
239 discriminant_size = tag.size(&ctx).bytes_usize();
241 discriminant_align = Align::ONE;
242 discriminant_size = 0;
245 Ok(Self { total_align, total_size, discriminant_align, discriminant_size })
248 fn into(&self) -> alloc::Layout {
249 alloc::Layout::from_size_align(
251 self.total_align.bytes().try_into().unwrap(),
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;
264 let target = tcx.data_layout();
267 ty::Bool => Ok(Self::bool()),
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()))
278 ty::Tuple(members) => {
279 if members.len() == 0 {
282 Err(Err::Unspecified)
286 ty::Array(ty, len) => {
287 let len = len.try_eval_usize(tcx, ParamEnv::reveal_all()).unwrap();
288 let elt = Tree::from_ty(*ty, tcx)?;
289 Ok(std::iter::repeat(elt)
291 .fold(Tree::unit(), |tree, elt| tree.then(elt)))
294 ty::Adt(adt_def, substs_ref) => {
295 use rustc_middle::ty::AdtKind;
297 // If the layout is ill-specified, halt.
298 if !(adt_def.repr().c() || adt_def.repr().int.is_some()) {
299 return Err(Err::Unspecified);
302 // Compute a summary of the type's layout.
303 let layout_summary = LayoutSummary::from_ty(ty, tcx)?;
305 // The layout begins with this adt's visibility.
306 let vis = Self::def(Def::Adt(*adt_def));
308 // And is followed the layout(s) of its variants
309 Ok(vis.then(match adt_def.adt_kind() {
310 AdtKind::Struct => Self::from_repr_c_variant(
316 adt_def.non_enum_variant(),
320 trace!(?adt_def, "treeifying enum");
321 let mut tree = Tree::uninhabited();
323 for (idx, discr) in adt_def.discriminants(tcx) {
324 tree = tree.or(Self::from_repr_c_variant(
330 adt_def.variant(idx),
338 // is the layout well-defined?
339 if !adt_def.repr().c() {
340 return Err(Err::Unspecified);
343 let ty_layout = layout_of(tcx, ty)?;
345 let mut tree = Tree::uninhabited();
347 for field in adt_def.all_fields() {
348 let variant_ty = field.ty(tcx, substs_ref);
349 let variant_layout = layout_of(tcx, variant_ty)?;
350 let padding_needed = ty_layout.size() - variant_layout.size();
351 let variant = Self::def(Def::Field(field))
352 .then(Self::from_ty(variant_ty, tcx)?)
353 .then(Self::padding(padding_needed));
355 tree = tree.or(variant);
362 _ => Err(Err::Unspecified),
366 fn from_repr_c_variant(
368 adt_def: AdtDef<'tcx>,
369 substs_ref: SubstsRef<'tcx>,
370 layout_summary: &LayoutSummary,
371 discr: Option<Discr<'tcx>>,
372 variant_def: &'tcx VariantDef,
374 ) -> Result<Self, Err> {
375 let mut tree = Tree::unit();
377 let repr = adt_def.repr();
378 let min_align = repr.align.unwrap_or(Align::ONE);
379 let max_align = repr.pack.unwrap_or(Align::MAX);
382 |align: Align| align.clamp(min_align, max_align).bytes().try_into().unwrap();
384 let variant_span = trace_span!(
385 "treeifying variant",
386 min_align = ?min_align,
387 max_align = ?max_align,
391 let mut variant_layout = alloc::Layout::from_size_align(
393 layout_summary.total_align.bytes().try_into().unwrap(),
397 // The layout of the variant is prefixed by the discriminant, if any.
398 if let Some(discr) = discr {
399 trace!(?discr, "treeifying discriminant");
400 let discr_layout = alloc::Layout::from_size_align(
401 layout_summary.discriminant_size,
402 clamp(layout_summary.discriminant_align),
405 trace!(?discr_layout, "computed discriminant layout");
406 variant_layout = variant_layout.extend(discr_layout).unwrap().0;
407 tree = tree.then(Self::from_discr(discr, tcx, layout_summary.discriminant_size));
411 let fields_span = trace_span!("treeifying fields").entered();
412 for field_def in variant_def.fields.iter() {
413 let field_ty = field_def.ty(tcx, substs_ref);
414 let _span = trace_span!("treeifying field", field = ?field_ty).entered();
416 // begin with the field's visibility
417 tree = tree.then(Self::def(Def::Field(field_def)));
419 // compute the field's layout characteristics
420 let field_layout = layout_of(tcx, field_ty)?.clamp_align(min_align, max_align);
422 // next comes the field's padding
423 let padding_needed = variant_layout.padding_needed_for(field_layout.align());
424 if padding_needed > 0 {
425 tree = tree.then(Self::padding(padding_needed));
428 // finally, the field's layout
429 tree = tree.then(Self::from_ty(field_ty, tcx)?);
431 // extend the variant layout with the field layout
432 variant_layout = variant_layout.extend(field_layout).unwrap().0;
437 let padding_span = trace_span!("adding trailing padding").entered();
438 let padding_needed = layout_summary.total_size - variant_layout.size();
439 if padding_needed > 0 {
440 tree = tree.then(Self::padding(padding_needed));
447 pub fn from_discr(discr: Discr<'tcx>, tcx: TyCtxt<'tcx>, size: usize) -> Self {
448 use rustc_target::abi::Endian;
451 let bytes = match tcx.data_layout.endian {
453 bytes = discr.val.to_le_bytes();
457 bytes = discr.val.to_be_bytes();
458 &bytes[bytes.len() - size..]
461 Self::Seq(bytes.iter().map(|&b| Self::from_bits(b)).collect())
468 ) -> Result<alloc::Layout, LayoutError<'tcx>> {
469 use rustc_middle::ty::ParamEnvAnd;
470 use rustc_target::abi::TyAndLayout;
472 let param_env = ParamEnv::reveal_all();
473 let param_env_and_type = ParamEnvAnd { param_env, value: ty };
474 let TyAndLayout { layout, .. } = ctx.layout_of(param_env_and_type)?;
475 let layout = alloc::Layout::from_size_align(
476 layout.size().bytes_usize(),
477 layout.align().abi.bytes().try_into().unwrap(),
480 trace!(?ty, ?layout, "computed layout for type");