1use std::ops::{ControlFlow, RangeInclusive};
2
3use super::{Byte, Def, Reference, Region, Type};
4
5#[cfg(test)]
6mod tests;
7
8#[derive(Clone, Debug, Hash, PartialEq, Eq)]
18pub(crate) enum Tree<D, R, T>
19where
20 D: Def,
21 R: Region,
22 T: Type,
23{
24 Seq(Vec<Self>),
26 Alt(Vec<Self>),
28 Def(D),
30 Ref(Reference<R, T>),
32 Byte(Byte),
34}
35
36#[derive(Debug, Copy, Clone, Eq, PartialEq)]
37pub(crate) enum Endian {
38 Little,
39 Big,
40}
41
42#[cfg(feature = "rustc")]
43impl From<rustc_abi::Endian> for Endian {
44 fn from(order: rustc_abi::Endian) -> Endian {
45 match order {
46 rustc_abi::Endian::Little => Endian::Little,
47 rustc_abi::Endian::Big => Endian::Big,
48 }
49 }
50}
51
52impl<D, R, T> Tree<D, R, T>
53where
54 D: Def,
55 R: Region,
56 T: Type,
57{
58 pub(crate) fn def(def: D) -> Self {
60 Self::Def(def)
61 }
62
63 pub(crate) fn uninhabited() -> Self {
65 Self::Alt(vec![])
66 }
67
68 pub(crate) fn unit() -> Self {
70 Self::Seq(Vec::new())
71 }
72
73 pub(crate) fn uninit() -> Self {
75 Self::Byte(Byte::uninit())
76 }
77
78 pub(crate) fn bool() -> Self {
80 Self::byte(0x00..=0x01)
81 }
82
83 pub(crate) fn u8() -> Self {
85 Self::byte(0x00..=0xFF)
86 }
87
88 pub(crate) fn char(order: Endian) -> Self {
90 const _0: RangeInclusive<u8> = 0..=0;
101 const BYTE: RangeInclusive<u8> = 0x00..=0xFF;
102 let x = Self::from_big_endian(order, [_0, _0, 0x00..=0xD7, BYTE]);
103 let y = Self::from_big_endian(order, [_0, _0, 0xE0..=0xFF, BYTE]);
104 let z = Self::from_big_endian(order, [_0, 0x01..=0x10, BYTE, BYTE]);
105 Self::alt([x, y, z])
106 }
107
108 #[allow(dead_code)]
110 pub(crate) fn nonzero(width_in_bytes: u64) -> Self {
111 const BYTE: RangeInclusive<u8> = 0x00..=0xFF;
112 const NONZERO: RangeInclusive<u8> = 0x01..=0xFF;
113
114 (0..width_in_bytes)
115 .map(|nz_idx| {
116 (0..width_in_bytes)
117 .map(|pos| Self::byte(if pos == nz_idx { NONZERO } else { BYTE }))
118 .fold(Self::unit(), Self::then)
119 })
120 .fold(Self::uninhabited(), Self::or)
121 }
122
123 pub(crate) fn bytes<const N: usize, B: Into<Byte>>(bytes: [B; N]) -> Self {
124 Self::seq(bytes.map(B::into).map(Self::Byte))
125 }
126
127 pub(crate) fn byte(byte: impl Into<Byte>) -> Self {
128 Self::Byte(byte.into())
129 }
130
131 pub(crate) fn number(width_in_bytes: u64) -> Self {
133 Self::Seq(vec![Self::u8(); width_in_bytes.try_into().unwrap()])
134 }
135
136 pub(crate) fn padding(width_in_bytes: usize) -> Self {
138 Self::Seq(vec![Self::uninit(); width_in_bytes])
139 }
140
141 pub(crate) fn prune<F>(self, f: &F) -> Tree<!, R, T>
144 where
145 F: Fn(D) -> bool,
146 {
147 match self {
148 Self::Seq(elts) => match elts.into_iter().map(|elt| elt.prune(f)).try_fold(
149 Tree::unit(),
150 |elts, elt| {
151 if elt == Tree::uninhabited() {
152 ControlFlow::Break(Tree::uninhabited())
153 } else {
154 ControlFlow::Continue(elts.then(elt))
155 }
156 },
157 ) {
158 ControlFlow::Break(node) | ControlFlow::Continue(node) => node,
159 },
160 Self::Alt(alts) => alts
161 .into_iter()
162 .map(|alt| alt.prune(f))
163 .fold(Tree::uninhabited(), |alts, alt| alts.or(alt)),
164 Self::Byte(b) => Tree::Byte(b),
165 Self::Ref(r) => Tree::Ref(r),
166 Self::Def(d) => {
167 if f(d) {
168 Tree::uninhabited()
169 } else {
170 Tree::unit()
171 }
172 }
173 }
174 }
175
176 pub(crate) fn is_inhabited(&self) -> bool {
178 match self {
179 Self::Seq(elts) => elts.into_iter().all(|elt| elt.is_inhabited()),
180 Self::Alt(alts) => alts.into_iter().any(|alt| alt.is_inhabited()),
181 Self::Byte(..) | Self::Ref(..) | Self::Def(..) => true,
182 }
183 }
184
185 pub(crate) fn from_big_endian<const N: usize, B: Into<Byte>>(
191 order: Endian,
192 mut bytes: [B; N],
193 ) -> Self {
194 if order == Endian::Little {
195 (&mut bytes[..]).reverse();
196 }
197
198 Self::bytes(bytes)
199 }
200
201 pub(crate) fn seq<const N: usize>(trees: [Tree<D, R, T>; N]) -> Self {
204 trees.into_iter().fold(Tree::unit(), Self::then)
205 }
206
207 pub(crate) fn alt<const N: usize>(trees: [Tree<D, R, T>; N]) -> Self {
210 trees.into_iter().fold(Tree::uninhabited(), Self::or)
211 }
212
213 pub(crate) fn then(self, other: Self) -> Self {
215 match (self, other) {
216 (Self::Seq(elts), other) | (other, Self::Seq(elts)) if elts.len() == 0 => other,
217 (Self::Seq(mut lhs), Self::Seq(mut rhs)) => {
218 lhs.append(&mut rhs);
219 Self::Seq(lhs)
220 }
221 (Self::Seq(mut lhs), rhs) => {
222 lhs.push(rhs);
223 Self::Seq(lhs)
224 }
225 (lhs, Self::Seq(mut rhs)) => {
226 rhs.insert(0, lhs);
227 Self::Seq(rhs)
228 }
229 (lhs, rhs) => Self::Seq(vec![lhs, rhs]),
230 }
231 }
232
233 pub(crate) fn or(self, other: Self) -> Self {
235 match (self, other) {
236 (Self::Alt(alts), other) | (other, Self::Alt(alts)) if alts.len() == 0 => other,
237 (Self::Alt(mut lhs), Self::Alt(rhs)) => {
238 lhs.extend(rhs);
239 Self::Alt(lhs)
240 }
241 (Self::Alt(mut alts), alt) | (alt, Self::Alt(mut alts)) => {
242 alts.push(alt);
243 Self::Alt(alts)
244 }
245 (lhs, rhs) => Self::Alt(vec![lhs, rhs]),
246 }
247 }
248}
249
250#[cfg(feature = "rustc")]
251pub(crate) mod rustc {
252 use rustc_abi::{
253 FieldIdx, FieldsShape, Layout, Size, TagEncoding, TyAndLayout, VariantIdx, Variants,
254 };
255 use rustc_middle::ty::layout::{HasTyCtxt, LayoutCx, LayoutError};
256 use rustc_middle::ty::{
257 self, AdtDef, AdtKind, List, Region, ScalarInt, Ty, TyCtxt, TypeVisitableExt,
258 };
259 use rustc_span::ErrorGuaranteed;
260
261 use super::Tree;
262 use crate::layout::Reference;
263 use crate::layout::rustc::{Def, layout_of};
264
265 #[derive(Debug, Copy, Clone)]
266 pub(crate) enum Err {
267 NotYetSupported,
269 UnknownLayout,
271 SizeOverflow,
273 TypeError(ErrorGuaranteed),
274 }
275
276 impl<'tcx> From<&LayoutError<'tcx>> for Err {
277 fn from(err: &LayoutError<'tcx>) -> Self {
278 match err {
279 LayoutError::Unknown(..)
280 | LayoutError::ReferencesError(..)
281 | LayoutError::TooGeneric(..)
282 | LayoutError::NormalizationFailure(..) => Self::UnknownLayout,
283 LayoutError::SizeOverflow(..) => Self::SizeOverflow,
284 LayoutError::Cycle(err) => Self::TypeError(*err),
285 }
286 }
287 }
288
289 impl<'tcx> Tree<Def<'tcx>, Region<'tcx>, Ty<'tcx>> {
290 pub(crate) fn from_ty(ty: Ty<'tcx>, cx: LayoutCx<'tcx>) -> Result<Self, Err> {
291 use rustc_abi::HasDataLayout;
292 let layout = layout_of(cx, ty)?;
293
294 if let Err(e) = ty.error_reported() {
295 return Err(Err::TypeError(e));
296 }
297
298 let target = cx.data_layout();
299 let pointer_size = target.pointer_size;
300
301 match ty.kind() {
302 ty::Bool => Ok(Self::bool()),
303
304 ty::Float(nty) => {
305 let width = nty.bit_width() / 8;
306 Ok(Self::number(width.try_into().unwrap()))
307 }
308
309 ty::Int(nty) => {
310 let width = nty.normalize(pointer_size.bits() as _).bit_width().unwrap() / 8;
311 Ok(Self::number(width.try_into().unwrap()))
312 }
313
314 ty::Uint(nty) => {
315 let width = nty.normalize(pointer_size.bits() as _).bit_width().unwrap() / 8;
316 Ok(Self::number(width.try_into().unwrap()))
317 }
318
319 ty::Tuple(members) => Self::from_tuple((ty, layout), members, cx),
320
321 ty::Array(inner_ty, _len) => {
322 let FieldsShape::Array { stride, count } = &layout.fields else {
323 return Err(Err::NotYetSupported);
324 };
325 let inner_layout = layout_of(cx, *inner_ty)?;
326 assert_eq!(*stride, inner_layout.size);
327 let elt = Tree::from_ty(*inner_ty, cx)?;
328 Ok(std::iter::repeat(elt)
329 .take(*count as usize)
330 .fold(Tree::unit(), |tree, elt| tree.then(elt)))
331 }
332
333 ty::Adt(adt_def, _args_ref) if !ty.is_box() => {
334 let (lo, hi) = cx.tcx().layout_scalar_valid_range(adt_def.did());
335
336 use core::ops::Bound::*;
337 let is_transparent = adt_def.repr().transparent();
338 match (adt_def.adt_kind(), lo, hi) {
339 (AdtKind::Struct, Unbounded, Unbounded) => {
340 Self::from_struct((ty, layout), *adt_def, cx)
341 }
342 (AdtKind::Struct, Included(1), Included(_hi)) if is_transparent => {
343 Err(Err::NotYetSupported)
350 }
351 (AdtKind::Enum, Unbounded, Unbounded) => {
352 Self::from_enum((ty, layout), *adt_def, cx)
353 }
354 (AdtKind::Union, Unbounded, Unbounded) => {
355 Self::from_union((ty, layout), *adt_def, cx)
356 }
357 _ => Err(Err::NotYetSupported),
358 }
359 }
360
361 ty::Ref(region, ty, mutability) => {
362 let layout = layout_of(cx, *ty)?;
363 let referent_align = layout.align.abi.bytes_usize();
364 let referent_size = layout.size.bytes_usize();
365
366 Ok(Tree::Ref(Reference {
367 region: *region,
368 is_mut: mutability.is_mut(),
369 referent: *ty,
370 referent_align,
371 referent_size,
372 }))
373 }
374
375 ty::Char => Ok(Self::char(cx.tcx().data_layout.endian.into())),
376
377 _ => Err(Err::NotYetSupported),
378 }
379 }
380
381 fn from_tuple(
383 (ty, layout): (Ty<'tcx>, Layout<'tcx>),
384 members: &'tcx List<Ty<'tcx>>,
385 cx: LayoutCx<'tcx>,
386 ) -> Result<Self, Err> {
387 match &layout.fields {
388 FieldsShape::Primitive => {
389 assert_eq!(members.len(), 1);
390 let inner_ty = members[0];
391 Self::from_ty(inner_ty, cx)
392 }
393 FieldsShape::Arbitrary { offsets, .. } => {
394 assert_eq!(offsets.len(), members.len());
395 Self::from_variant(Def::Primitive, None, (ty, layout), layout.size, cx)
396 }
397 FieldsShape::Array { .. } | FieldsShape::Union(_) => Err(Err::NotYetSupported),
398 }
399 }
400
401 fn from_struct(
407 (ty, layout): (Ty<'tcx>, Layout<'tcx>),
408 def: AdtDef<'tcx>,
409 cx: LayoutCx<'tcx>,
410 ) -> Result<Self, Err> {
411 assert!(def.is_struct());
412 let def = Def::Adt(def);
413 Self::from_variant(def, None, (ty, layout), layout.size, cx)
414 }
415
416 fn from_enum(
422 (ty, layout): (Ty<'tcx>, Layout<'tcx>),
423 def: AdtDef<'tcx>,
424 cx: LayoutCx<'tcx>,
425 ) -> Result<Self, Err> {
426 assert!(def.is_enum());
427
428 let layout_of_variant =
430 |index, encoding: Option<TagEncoding<VariantIdx>>| -> Result<Self, Err> {
431 let variant_layout = ty_variant(cx, (ty, layout), index);
432 if variant_layout.is_uninhabited() {
433 return Ok(Self::uninhabited());
434 }
435 let tag = cx.tcx().tag_for_variant(
436 cx.typing_env.as_query_input((cx.tcx().erase_regions(ty), index)),
437 );
438 let variant_def = Def::Variant(def.variant(index));
439 Self::from_variant(
440 variant_def,
441 tag.map(|tag| (tag, index, encoding.unwrap())),
442 (ty, variant_layout),
443 layout.size,
444 cx,
445 )
446 };
447
448 match layout.variants() {
449 Variants::Empty => Ok(Self::uninhabited()),
450 Variants::Single { index } => {
451 layout_of_variant(*index, None)
454 }
455 Variants::Multiple { tag: _, tag_encoding, tag_field, .. } => {
456 assert_eq!(*tag_field, FieldIdx::ZERO);
463
464 let variants = def.discriminants(cx.tcx()).try_fold(
465 Self::uninhabited(),
466 |variants, (idx, _discriminant)| {
467 let variant = layout_of_variant(idx, Some(tag_encoding.clone()))?;
468 Result::<Self, Err>::Ok(variants.or(variant))
469 },
470 )?;
471
472 Ok(Self::def(Def::Adt(def)).then(variants))
473 }
474 }
475 }
476
477 fn from_variant(
487 def: Def<'tcx>,
488 tag: Option<(ScalarInt, VariantIdx, TagEncoding<VariantIdx>)>,
489 (ty, layout): (Ty<'tcx>, Layout<'tcx>),
490 total_size: Size,
491 cx: LayoutCx<'tcx>,
492 ) -> Result<Self, Err> {
493 let FieldsShape::Arbitrary { offsets, memory_index } = layout.fields() else {
496 return Err(Err::NotYetSupported);
497 };
498
499 assert!(layout.size <= total_size);
503
504 let mut size = Size::ZERO;
505 let mut struct_tree = Self::def(def);
506
507 if let Some((tag, index, encoding)) = &tag {
509 match encoding {
510 TagEncoding::Direct => {
511 size += tag.size();
512 }
513 TagEncoding::Niche { niche_variants, .. } => {
514 if !niche_variants.contains(index) {
515 size += tag.size();
516 }
517 }
518 }
519 struct_tree = struct_tree.then(Self::from_tag(*tag, cx.tcx()));
520 }
521
522 let inverse_memory_index = memory_index.invert_bijective_mapping();
524 for &field_idx in inverse_memory_index.iter() {
525 let padding_needed = offsets[field_idx] - size;
527 let padding = Self::padding(padding_needed.bytes_usize());
528
529 let field_ty = ty_field(cx, (ty, layout), field_idx);
530 let field_layout = layout_of(cx, field_ty)?;
531 let field_tree = Self::from_ty(field_ty, cx)?;
532
533 struct_tree = struct_tree.then(padding).then(field_tree);
534
535 size += padding_needed + field_layout.size;
536 }
537
538 let padding_needed = total_size - size;
540 let trailing_padding = Self::padding(padding_needed.bytes_usize());
541
542 Ok(struct_tree.then(trailing_padding))
543 }
544
545 fn from_tag(tag: ScalarInt, tcx: TyCtxt<'tcx>) -> Self {
547 use rustc_abi::Endian;
548 let size = tag.size();
549 let bits = tag.to_bits(size);
550 let bytes: [u8; 16];
551 let bytes = match tcx.data_layout.endian {
552 Endian::Little => {
553 bytes = bits.to_le_bytes();
554 &bytes[..size.bytes_usize()]
555 }
556 Endian::Big => {
557 bytes = bits.to_be_bytes();
558 &bytes[bytes.len() - size.bytes_usize()..]
559 }
560 };
561 Self::Seq(bytes.iter().map(|&b| Self::byte(b)).collect())
562 }
563
564 fn from_union(
570 (ty, layout): (Ty<'tcx>, Layout<'tcx>),
571 def: AdtDef<'tcx>,
572 cx: LayoutCx<'tcx>,
573 ) -> Result<Self, Err> {
574 assert!(def.is_union());
575
576 let FieldsShape::Union(_fields) = layout.fields() else {
579 return Err(Err::NotYetSupported);
580 };
581
582 let fields = &def.non_enum_variant().fields;
583 let fields = fields.iter_enumerated().try_fold(
584 Self::uninhabited(),
585 |fields, (idx, _field_def)| {
586 let field_ty = ty_field(cx, (ty, layout), idx);
587 let field_layout = layout_of(cx, field_ty)?;
588 let field = Self::from_ty(field_ty, cx)?;
589 let trailing_padding_needed = layout.size - field_layout.size;
590 let trailing_padding = Self::padding(trailing_padding_needed.bytes_usize());
591 let field_and_padding = field.then(trailing_padding);
592 Result::<Self, Err>::Ok(fields.or(field_and_padding))
593 },
594 )?;
595
596 Ok(Self::def(Def::Adt(def)).then(fields))
597 }
598 }
599
600 fn ty_field<'tcx>(
601 cx: LayoutCx<'tcx>,
602 (ty, layout): (Ty<'tcx>, Layout<'tcx>),
603 i: FieldIdx,
604 ) -> Ty<'tcx> {
605 match ty.kind() {
610 ty::Adt(def, args) => {
611 match layout.variants {
612 Variants::Single { index } => {
613 let field = &def.variant(index).fields[i];
614 field.ty(cx.tcx(), args)
615 }
616 Variants::Empty => panic!("there is no field in Variants::Empty types"),
617 Variants::Multiple { tag, .. } => {
619 assert_eq!(i.as_usize(), 0);
620 ty::layout::PrimitiveExt::to_ty(&tag.primitive(), cx.tcx())
621 }
622 }
623 }
624 ty::Tuple(fields) => fields[i.as_usize()],
625 kind => unimplemented!(
626 "only a subset of `Ty::ty_and_layout_field`'s functionality is implemented. implementation needed for {:?}",
627 kind
628 ),
629 }
630 }
631
632 fn ty_variant<'tcx>(
633 cx: LayoutCx<'tcx>,
634 (ty, layout): (Ty<'tcx>, Layout<'tcx>),
635 i: VariantIdx,
636 ) -> Layout<'tcx> {
637 let ty = cx.tcx().erase_regions(ty);
638 TyAndLayout { ty, layout }.for_variant(&cx, i).layout
639 }
640}