use super::{Byte, Def, Ref};
use std::ops::ControlFlow;
#[cfg(test)]
mod tests;
#[derive(Clone, Debug, Hash, PartialEq, Eq)]
pub(crate) enum Tree<D, R>
where
D: Def,
R: Ref,
{
Seq(Vec<Self>),
Alt(Vec<Self>),
Def(D),
Ref(R),
Byte(Byte),
}
impl<D, R> Tree<D, R>
where
D: Def,
R: Ref,
{
pub(crate) fn def(def: D) -> Self {
Self::Def(def)
}
pub(crate) fn uninhabited() -> Self {
Self::Alt(vec![])
}
pub(crate) fn unit() -> Self {
Self::Seq(Vec::new())
}
pub(crate) fn uninit() -> Self {
Self::Byte(Byte::Uninit)
}
pub(crate) fn bool() -> Self {
Self::from_bits(0x00).or(Self::from_bits(0x01))
}
pub(crate) fn u8() -> Self {
Self::Alt((0u8..=255).map(Self::from_bits).collect())
}
pub(crate) fn from_bits(bits: u8) -> Self {
Self::Byte(Byte::Init(bits))
}
pub(crate) fn number(width_in_bytes: usize) -> Self {
Self::Seq(vec![Self::u8(); width_in_bytes])
}
pub(crate) fn padding(width_in_bytes: usize) -> Self {
Self::Seq(vec![Self::uninit(); width_in_bytes])
}
pub(crate) fn prune<F>(self, f: &F) -> Tree<!, R>
where
F: Fn(D) -> bool,
{
match self {
Self::Seq(elts) => match elts.into_iter().map(|elt| elt.prune(f)).try_fold(
Tree::unit(),
|elts, elt| {
if elt == Tree::uninhabited() {
ControlFlow::Break(Tree::uninhabited())
} else {
ControlFlow::Continue(elts.then(elt))
}
},
) {
ControlFlow::Break(node) | ControlFlow::Continue(node) => node,
},
Self::Alt(alts) => alts
.into_iter()
.map(|alt| alt.prune(f))
.fold(Tree::uninhabited(), |alts, alt| alts.or(alt)),
Self::Byte(b) => Tree::Byte(b),
Self::Ref(r) => Tree::Ref(r),
Self::Def(d) => {
if f(d) {
Tree::uninhabited()
} else {
Tree::unit()
}
}
}
}
pub(crate) fn is_inhabited(&self) -> bool {
match self {
Self::Seq(elts) => elts.into_iter().all(|elt| elt.is_inhabited()),
Self::Alt(alts) => alts.into_iter().any(|alt| alt.is_inhabited()),
Self::Byte(..) | Self::Ref(..) | Self::Def(..) => true,
}
}
}
impl<D, R> Tree<D, R>
where
D: Def,
R: Ref,
{
pub(crate) fn then(self, other: Self) -> Self {
match (self, other) {
(Self::Seq(elts), other) | (other, Self::Seq(elts)) if elts.len() == 0 => other,
(Self::Seq(mut lhs), Self::Seq(mut rhs)) => {
lhs.append(&mut rhs);
Self::Seq(lhs)
}
(Self::Seq(mut lhs), rhs) => {
lhs.push(rhs);
Self::Seq(lhs)
}
(lhs, Self::Seq(mut rhs)) => {
rhs.insert(0, lhs);
Self::Seq(rhs)
}
(lhs, rhs) => Self::Seq(vec![lhs, rhs]),
}
}
pub(crate) fn or(self, other: Self) -> Self {
match (self, other) {
(Self::Alt(alts), other) | (other, Self::Alt(alts)) if alts.len() == 0 => other,
(Self::Alt(mut lhs), Self::Alt(rhs)) => {
lhs.extend(rhs);
Self::Alt(lhs)
}
(Self::Alt(mut alts), alt) | (alt, Self::Alt(mut alts)) => {
alts.push(alt);
Self::Alt(alts)
}
(lhs, rhs) => Self::Alt(vec![lhs, rhs]),
}
}
}
#[cfg(feature = "rustc")]
pub(crate) mod rustc {
use super::Tree;
use crate::layout::rustc::{Def, Ref};
use rustc_middle::ty::layout::HasTyCtxt;
use rustc_middle::ty::layout::LayoutCx;
use rustc_middle::ty::layout::LayoutError;
use rustc_middle::ty::layout::LayoutOf;
use rustc_middle::ty::AdtDef;
use rustc_middle::ty::AdtKind;
use rustc_middle::ty::List;
use rustc_middle::ty::ScalarInt;
use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitableExt};
use rustc_span::ErrorGuaranteed;
use rustc_target::abi::FieldsShape;
use rustc_target::abi::Size;
use rustc_target::abi::TyAndLayout;
use rustc_target::abi::Variants;
#[derive(Debug, Copy, Clone)]
pub(crate) enum Err {
NotYetSupported,
UnknownLayout,
SizeOverflow,
TypeError(ErrorGuaranteed),
}
impl<'tcx> From<&LayoutError<'tcx>> for Err {
fn from(err: &LayoutError<'tcx>) -> Self {
match err {
LayoutError::Unknown(..) | LayoutError::ReferencesError(..) => Self::UnknownLayout,
LayoutError::SizeOverflow(..) => Self::SizeOverflow,
LayoutError::Cycle(err) => Self::TypeError(*err),
err => unimplemented!("{:?}", err),
}
}
}
impl<'tcx> Tree<Def<'tcx>, Ref<'tcx>> {
pub fn from_ty(
ty_and_layout: TyAndLayout<'tcx, Ty<'tcx>>,
cx: LayoutCx<'tcx, TyCtxt<'tcx>>,
) -> Result<Self, Err> {
use rustc_target::abi::HasDataLayout;
if let Err(e) = ty_and_layout.ty.error_reported() {
return Err(Err::TypeError(e));
}
let target = cx.tcx.data_layout();
let pointer_size = target.pointer_size;
match ty_and_layout.ty.kind() {
ty::Bool => Ok(Self::bool()),
ty::Float(nty) => {
let width = nty.bit_width() / 8;
Ok(Self::number(width as _))
}
ty::Int(nty) => {
let width = nty.normalize(pointer_size.bits() as _).bit_width().unwrap() / 8;
Ok(Self::number(width as _))
}
ty::Uint(nty) => {
let width = nty.normalize(pointer_size.bits() as _).bit_width().unwrap() / 8;
Ok(Self::number(width as _))
}
ty::Tuple(members) => Self::from_tuple(ty_and_layout, members, cx),
ty::Array(inner_ty, len) => {
let FieldsShape::Array { stride, count } = &ty_and_layout.fields else {
return Err(Err::NotYetSupported);
};
let inner_ty_and_layout = cx.layout_of(*inner_ty)?;
assert_eq!(*stride, inner_ty_and_layout.size);
let elt = Tree::from_ty(inner_ty_and_layout, cx)?;
Ok(std::iter::repeat(elt)
.take(*count as usize)
.fold(Tree::unit(), |tree, elt| tree.then(elt)))
}
ty::Adt(adt_def, _args_ref) if !ty_and_layout.ty.is_box() => {
match adt_def.adt_kind() {
AdtKind::Struct => Self::from_struct(ty_and_layout, *adt_def, cx),
AdtKind::Enum => Self::from_enum(ty_and_layout, *adt_def, cx),
AdtKind::Union => Self::from_union(ty_and_layout, *adt_def, cx),
}
}
ty::Ref(lifetime, ty, mutability) => {
let ty_and_layout = cx.layout_of(*ty)?;
let align = ty_and_layout.align.abi.bytes_usize();
let size = ty_and_layout.size.bytes_usize();
Ok(Tree::Ref(Ref {
lifetime: *lifetime,
ty: *ty,
mutability: *mutability,
align,
size,
}))
}
_ => Err(Err::NotYetSupported),
}
}
fn from_tuple(
ty_and_layout: TyAndLayout<'tcx, Ty<'tcx>>,
members: &'tcx List<Ty<'tcx>>,
cx: LayoutCx<'tcx, TyCtxt<'tcx>>,
) -> Result<Self, Err> {
match &ty_and_layout.fields {
FieldsShape::Primitive => {
assert_eq!(members.len(), 1);
let inner_ty = members[0];
let inner_ty_and_layout = cx.layout_of(inner_ty)?;
assert_eq!(ty_and_layout.layout, inner_ty_and_layout.layout);
Self::from_ty(inner_ty_and_layout, cx)
}
FieldsShape::Arbitrary { offsets, .. } => {
assert_eq!(offsets.len(), members.len());
Self::from_variant(Def::Primitive, None, ty_and_layout, ty_and_layout.size, cx)
}
FieldsShape::Array { .. } | FieldsShape::Union(_) => Err(Err::NotYetSupported),
}
}
fn from_struct(
ty_and_layout: TyAndLayout<'tcx, Ty<'tcx>>,
def: AdtDef<'tcx>,
cx: LayoutCx<'tcx, TyCtxt<'tcx>>,
) -> Result<Self, Err> {
assert!(def.is_struct());
let def = Def::Adt(def);
Self::from_variant(def, None, ty_and_layout, ty_and_layout.size, cx)
}
fn from_enum(
ty_and_layout: TyAndLayout<'tcx, Ty<'tcx>>,
def: AdtDef<'tcx>,
cx: LayoutCx<'tcx, TyCtxt<'tcx>>,
) -> Result<Self, Err> {
assert!(def.is_enum());
let layout = ty_and_layout.layout;
if let Variants::Multiple { tag_field, .. } = layout.variants() {
assert_eq!(*tag_field, 0);
}
let variants = def.discriminants(cx.tcx()).try_fold(
Self::uninhabited(),
|variants, (idx, ref discriminant)| {
let tag = cx.tcx.tag_for_variant((ty_and_layout.ty, idx));
let variant_def = Def::Variant(def.variant(idx));
let variant_ty_and_layout = ty_and_layout.for_variant(&cx, idx);
let variant = Self::from_variant(
variant_def,
tag,
variant_ty_and_layout,
layout.size,
cx,
)?;
Result::<Self, Err>::Ok(variants.or(variant))
},
)?;
return Ok(Self::def(Def::Adt(def)).then(variants));
}
fn from_variant(
def: Def<'tcx>,
tag: Option<ScalarInt>,
ty_and_layout: TyAndLayout<'tcx, Ty<'tcx>>,
total_size: Size,
cx: LayoutCx<'tcx, TyCtxt<'tcx>>,
) -> Result<Self, Err> {
let FieldsShape::Arbitrary { offsets, memory_index } = ty_and_layout.layout.fields()
else {
return Err(Err::NotYetSupported);
};
assert!(ty_and_layout.size <= total_size);
let mut size = Size::ZERO;
let mut struct_tree = Self::def(def);
if let Some(tag) = tag {
size += tag.size();
struct_tree = struct_tree.then(Self::from_tag(tag, cx.tcx));
}
let inverse_memory_index = memory_index.invert_bijective_mapping();
for (memory_idx, field_idx) in inverse_memory_index.iter_enumerated() {
let padding_needed = offsets[*field_idx] - size;
let padding = Self::padding(padding_needed.bytes_usize());
let field_ty_and_layout = ty_and_layout.field(&cx, field_idx.as_usize());
let field_tree = Self::from_ty(field_ty_and_layout, cx)?;
struct_tree = struct_tree.then(padding).then(field_tree);
size += padding_needed + field_ty_and_layout.size;
}
let padding_needed = total_size - size;
let trailing_padding = Self::padding(padding_needed.bytes_usize());
Ok(struct_tree.then(trailing_padding))
}
fn from_tag(tag: ScalarInt, tcx: TyCtxt<'tcx>) -> Self {
use rustc_target::abi::Endian;
let size = tag.size();
let bits = tag.assert_bits(size);
let bytes: [u8; 16];
let bytes = match tcx.data_layout.endian {
Endian::Little => {
bytes = bits.to_le_bytes();
&bytes[..size.bytes_usize()]
}
Endian::Big => {
bytes = bits.to_be_bytes();
&bytes[bytes.len() - size.bytes_usize()..]
}
};
Self::Seq(bytes.iter().map(|&b| Self::from_bits(b)).collect())
}
fn from_union(
ty_and_layout: TyAndLayout<'tcx, Ty<'tcx>>,
def: AdtDef<'tcx>,
cx: LayoutCx<'tcx, TyCtxt<'tcx>>,
) -> Result<Self, Err> {
assert!(def.is_union());
let union_layout = ty_and_layout.layout;
let FieldsShape::Union(fields) = union_layout.fields() else {
return Err(Err::NotYetSupported);
};
let fields = &def.non_enum_variant().fields;
let fields = fields.iter_enumerated().try_fold(
Self::uninhabited(),
|fields, (idx, ref field_def)| {
let field_def = Def::Field(field_def);
let field_ty_and_layout = ty_and_layout.field(&cx, idx.as_usize());
let field = Self::from_ty(field_ty_and_layout, cx)?;
let trailing_padding_needed = union_layout.size - field_ty_and_layout.size;
let trailing_padding = Self::padding(trailing_padding_needed.bytes_usize());
let field_and_padding = field.then(trailing_padding);
Result::<Self, Err>::Ok(fields.or(field_and_padding))
},
)?;
Ok(Self::def(Def::Adt(def)).then(fields))
}
}
}