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");