From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- compiler/rustc_transmute/src/layout/dfa.rs | 184 +++++++++ compiler/rustc_transmute/src/layout/mod.rs | 71 ++++ compiler/rustc_transmute/src/layout/nfa.rs | 179 ++++++++ compiler/rustc_transmute/src/layout/tree.rs | 471 ++++++++++++++++++++++ compiler/rustc_transmute/src/layout/tree/tests.rs | 80 ++++ 5 files changed, 985 insertions(+) create mode 100644 compiler/rustc_transmute/src/layout/dfa.rs create mode 100644 compiler/rustc_transmute/src/layout/mod.rs create mode 100644 compiler/rustc_transmute/src/layout/nfa.rs create mode 100644 compiler/rustc_transmute/src/layout/tree.rs create mode 100644 compiler/rustc_transmute/src/layout/tree/tests.rs (limited to 'compiler/rustc_transmute/src/layout') diff --git a/compiler/rustc_transmute/src/layout/dfa.rs b/compiler/rustc_transmute/src/layout/dfa.rs new file mode 100644 index 000000000..b60ea6e7a --- /dev/null +++ b/compiler/rustc_transmute/src/layout/dfa.rs @@ -0,0 +1,184 @@ +use super::{nfa, Byte, Nfa, Ref}; +use crate::Map; +use std::fmt; +use std::sync::atomic::{AtomicU32, Ordering}; + +#[derive(PartialEq, Clone, Debug)] +pub(crate) struct Dfa +where + R: Ref, +{ + pub(crate) transitions: Map>, + pub(crate) start: State, + pub(crate) accepting: State, +} + +#[derive(PartialEq, Clone, Debug)] +pub(crate) struct Transitions +where + R: Ref, +{ + byte_transitions: Map, + ref_transitions: Map, +} + +impl Default for Transitions +where + R: Ref, +{ + fn default() -> Self { + Self { byte_transitions: Map::default(), ref_transitions: Map::default() } + } +} + +impl Transitions +where + R: Ref, +{ + fn insert(&mut self, transition: Transition, state: State) { + match transition { + Transition::Byte(b) => { + self.byte_transitions.insert(b, state); + } + Transition::Ref(r) => { + self.ref_transitions.insert(r, state); + } + } + } +} + +/// The states in a `Nfa` represent byte offsets. +#[derive(Hash, Eq, PartialEq, PartialOrd, Ord, Copy, Clone)] +pub(crate) struct State(u32); + +#[derive(Hash, Eq, PartialEq, Clone, Copy)] +pub(crate) enum Transition +where + R: Ref, +{ + Byte(Byte), + Ref(R), +} + +impl fmt::Debug for State { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "S_{}", self.0) + } +} + +impl fmt::Debug for Transition +where + R: Ref, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match &self { + Self::Byte(b) => b.fmt(f), + Self::Ref(r) => r.fmt(f), + } + } +} + +impl Dfa +where + R: Ref, +{ + pub(crate) fn unit() -> Self { + let transitions: Map> = Map::default(); + let start = State::new(); + let accepting = start; + + Self { transitions, start, accepting } + } + + #[cfg(test)] + pub(crate) fn bool() -> Self { + let mut transitions: Map> = Map::default(); + let start = State::new(); + let accepting = State::new(); + + transitions.entry(start).or_default().insert(Transition::Byte(Byte::Init(0x00)), accepting); + + transitions.entry(start).or_default().insert(Transition::Byte(Byte::Init(0x01)), accepting); + + Self { transitions, start, accepting } + } + + #[instrument(level = "debug")] + #[cfg_attr(feature = "rustc", allow(rustc::potential_query_instability))] + pub(crate) fn from_nfa(nfa: Nfa) -> Self { + let Nfa { transitions: nfa_transitions, start: nfa_start, accepting: nfa_accepting } = nfa; + + let mut dfa_transitions: Map> = Map::default(); + let mut nfa_to_dfa: Map = Map::default(); + let dfa_start = State::new(); + nfa_to_dfa.insert(nfa_start, dfa_start); + + let mut queue = vec![(nfa_start, dfa_start)]; + + while let Some((nfa_state, dfa_state)) = queue.pop() { + if nfa_state == nfa_accepting { + continue; + } + + for (nfa_transition, next_nfa_states) in nfa_transitions[&nfa_state].iter() { + let dfa_transitions = + dfa_transitions.entry(dfa_state).or_insert_with(Default::default); + + let mapped_state = next_nfa_states.iter().find_map(|x| nfa_to_dfa.get(x).copied()); + + let next_dfa_state = match nfa_transition { + &nfa::Transition::Byte(b) => *dfa_transitions + .byte_transitions + .entry(b) + .or_insert_with(|| mapped_state.unwrap_or_else(State::new)), + &nfa::Transition::Ref(r) => *dfa_transitions + .ref_transitions + .entry(r) + .or_insert_with(|| mapped_state.unwrap_or_else(State::new)), + }; + + for &next_nfa_state in next_nfa_states { + nfa_to_dfa.entry(next_nfa_state).or_insert_with(|| { + queue.push((next_nfa_state, next_dfa_state)); + next_dfa_state + }); + } + } + } + + let dfa_accepting = nfa_to_dfa[&nfa_accepting]; + + Self { transitions: dfa_transitions, start: dfa_start, accepting: dfa_accepting } + } + + pub(crate) fn bytes_from(&self, start: State) -> Option<&Map> { + Some(&self.transitions.get(&start)?.byte_transitions) + } + + pub(crate) fn byte_from(&self, start: State, byte: Byte) -> Option { + self.transitions.get(&start)?.byte_transitions.get(&byte).copied() + } + + pub(crate) fn refs_from(&self, start: State) -> Option<&Map> { + Some(&self.transitions.get(&start)?.ref_transitions) + } +} + +impl State { + pub(crate) fn new() -> Self { + static COUNTER: AtomicU32 = AtomicU32::new(0); + Self(COUNTER.fetch_add(1, Ordering::SeqCst)) + } +} + +impl From> for Transition +where + R: Ref, +{ + fn from(nfa_transition: nfa::Transition) -> Self { + match nfa_transition { + nfa::Transition::Byte(byte) => Transition::Byte(byte), + nfa::Transition::Ref(r) => Transition::Ref(r), + } + } +} diff --git a/compiler/rustc_transmute/src/layout/mod.rs b/compiler/rustc_transmute/src/layout/mod.rs new file mode 100644 index 000000000..07035ebdf --- /dev/null +++ b/compiler/rustc_transmute/src/layout/mod.rs @@ -0,0 +1,71 @@ +use std::fmt::{self, Debug}; +use std::hash::Hash; + +pub(crate) mod tree; +pub(crate) use tree::Tree; + +pub(crate) mod nfa; +pub(crate) use nfa::Nfa; + +pub(crate) mod dfa; +pub(crate) use dfa::Dfa; + +#[derive(Debug)] +pub(crate) struct Uninhabited; + +/// An instance of a byte is either initialized to a particular value, or uninitialized. +#[derive(Hash, Eq, PartialEq, Clone, Copy)] +pub(crate) enum Byte { + Uninit, + Init(u8), +} + +impl fmt::Debug for Byte { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match &self { + Self::Uninit => f.write_str("??u8"), + Self::Init(b) => write!(f, "{:#04x}u8", b), + } + } +} + +pub(crate) trait Def: Debug + Hash + Eq + PartialEq + Copy + Clone {} +pub trait Ref: Debug + Hash + Eq + PartialEq + Copy + Clone {} + +impl Def for ! {} +impl Ref for ! {} + +#[cfg(feature = "rustc")] +pub(crate) mod rustc { + use rustc_middle::mir::Mutability; + use rustc_middle::ty; + use rustc_middle::ty::Region; + use rustc_middle::ty::Ty; + + /// A reference in the layout. + #[derive(Debug, Hash, Eq, PartialEq, PartialOrd, Ord, Clone, Copy)] + pub struct Ref<'tcx> { + lifetime: Region<'tcx>, + ty: Ty<'tcx>, + mutability: Mutability, + } + + impl<'tcx> super::Ref for Ref<'tcx> {} + + impl<'tcx> Ref<'tcx> { + pub fn min_align(&self) -> usize { + todo!() + } + } + + /// A visibility node in the layout. + #[derive(Debug, Hash, Eq, PartialEq, Clone, Copy)] + pub enum Def<'tcx> { + Adt(ty::AdtDef<'tcx>), + Variant(&'tcx ty::VariantDef), + Field(&'tcx ty::FieldDef), + Primitive, + } + + impl<'tcx> super::Def for Def<'tcx> {} +} diff --git a/compiler/rustc_transmute/src/layout/nfa.rs b/compiler/rustc_transmute/src/layout/nfa.rs new file mode 100644 index 000000000..f25e3c1fd --- /dev/null +++ b/compiler/rustc_transmute/src/layout/nfa.rs @@ -0,0 +1,179 @@ +use super::{Byte, Ref, Tree, Uninhabited}; +use crate::{Map, Set}; +use std::fmt; +use std::sync::atomic::{AtomicU32, Ordering}; + +/// A non-deterministic finite automaton (NFA) that represents the layout of a type. +/// The transmutability of two given types is computed by comparing their `Nfa`s. +#[derive(PartialEq, Debug)] +pub(crate) struct Nfa +where + R: Ref, +{ + pub(crate) transitions: Map, Set>>, + pub(crate) start: State, + pub(crate) accepting: State, +} + +/// The states in a `Nfa` represent byte offsets. +#[derive(Hash, Eq, PartialEq, PartialOrd, Ord, Copy, Clone)] +pub(crate) struct State(u32); + +/// The transitions between states in a `Nfa` reflect bit validity. +#[derive(Hash, Eq, PartialEq, Clone, Copy)] +pub(crate) enum Transition +where + R: Ref, +{ + Byte(Byte), + Ref(R), +} + +impl fmt::Debug for State { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "S_{}", self.0) + } +} + +impl fmt::Debug for Transition +where + R: Ref, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match &self { + Self::Byte(b) => b.fmt(f), + Self::Ref(r) => r.fmt(f), + } + } +} + +impl Nfa +where + R: Ref, +{ + pub(crate) fn unit() -> Self { + let transitions: Map, Set>> = Map::default(); + let start = State::new(); + let accepting = start; + + Nfa { transitions, start, accepting } + } + + pub(crate) fn from_byte(byte: Byte) -> Self { + let mut transitions: Map, Set>> = Map::default(); + let start = State::new(); + let accepting = State::new(); + + let source = transitions.entry(start).or_default(); + let edge = source.entry(Transition::Byte(byte)).or_default(); + edge.insert(accepting); + + Nfa { transitions, start, accepting } + } + + pub(crate) fn from_ref(r: R) -> Self { + let mut transitions: Map, Set>> = Map::default(); + let start = State::new(); + let accepting = State::new(); + + let source = transitions.entry(start).or_default(); + let edge = source.entry(Transition::Ref(r)).or_default(); + edge.insert(accepting); + + Nfa { transitions, start, accepting } + } + + pub(crate) fn from_tree(tree: Tree) -> Result { + Ok(match tree { + Tree::Byte(b) => Self::from_byte(b), + Tree::Def(..) => unreachable!(), + Tree::Ref(r) => Self::from_ref(r), + Tree::Alt(alts) => { + let mut alts = alts.into_iter().map(Self::from_tree); + let mut nfa = alts.next().ok_or(Uninhabited)??; + for alt in alts { + nfa = nfa.union(alt?); + } + nfa + } + Tree::Seq(elts) => { + let mut nfa = Self::unit(); + for elt in elts.into_iter().map(Self::from_tree) { + nfa = nfa.concat(elt?); + } + nfa + } + }) + } + + /// Concatenate two `Nfa`s. + pub(crate) fn concat(self, other: Self) -> Self { + if self.start == self.accepting { + return other; + } else if other.start == other.accepting { + return self; + } + + let start = self.start; + let accepting = other.accepting; + + let mut transitions: Map, Set>> = self.transitions; + + // the iteration order doesn't matter + #[cfg_attr(feature = "rustc", allow(rustc::potential_query_instability))] + for (source, transition) in other.transitions { + let fix_state = |state| if state == other.start { self.accepting } else { state }; + let entry = transitions.entry(fix_state(source)).or_default(); + for (edge, destinations) in transition { + let entry = entry.entry(edge.clone()).or_default(); + for destination in destinations { + entry.insert(fix_state(destination)); + } + } + } + + Self { transitions, start, accepting } + } + + /// Compute the union of two `Nfa`s. + pub(crate) fn union(self, other: Self) -> Self { + let start = self.start; + let accepting = self.accepting; + + let mut transitions: Map, Set>> = self.transitions.clone(); + + // the iteration order doesn't matter + #[cfg_attr(feature = "rustc", allow(rustc::potential_query_instability))] + for (&(mut source), transition) in other.transitions.iter() { + // if source is starting state of `other`, replace with starting state of `self` + if source == other.start { + source = self.start; + } + let entry = transitions.entry(source).or_default(); + for (edge, destinations) in transition { + let entry = entry.entry(edge.clone()).or_default(); + // the iteration order doesn't matter + #[cfg_attr(feature = "rustc", allow(rustc::potential_query_instability))] + for &(mut destination) in destinations { + // if dest is accepting state of `other`, replace with accepting state of `self` + if destination == other.accepting { + destination = self.accepting; + } + entry.insert(destination); + } + } + } + Self { transitions, start, accepting } + } + + pub(crate) fn edges_from(&self, start: State) -> Option<&Map, Set>> { + self.transitions.get(&start) + } +} + +impl State { + pub(crate) fn new() -> Self { + static COUNTER: AtomicU32 = AtomicU32::new(0); + Self(COUNTER.fetch_add(1, Ordering::SeqCst)) + } +} diff --git a/compiler/rustc_transmute/src/layout/tree.rs b/compiler/rustc_transmute/src/layout/tree.rs new file mode 100644 index 000000000..70b3ba02b --- /dev/null +++ b/compiler/rustc_transmute/src/layout/tree.rs @@ -0,0 +1,471 @@ +use super::{Byte, Def, Ref}; + +#[cfg(test)] +mod tests; + +/// A tree-based representation of a type layout. +/// +/// Invariants: +/// 1. All paths through the layout have the same length (in bytes). +/// +/// Nice-to-haves: +/// 1. An `Alt` is never directly nested beneath another `Alt`. +/// 2. A `Seq` is never directly nested beneath another `Seq`. +/// 3. `Seq`s and `Alt`s with a single member do not exist. +#[derive(Clone, Debug, Hash, PartialEq, Eq)] +pub(crate) enum Tree +where + D: Def, + R: Ref, +{ + /// A sequence of successive layouts. + Seq(Vec), + /// A choice between alternative layouts. + Alt(Vec), + /// A definition node. + Def(D), + /// A reference node. + Ref(R), + /// A byte node. + Byte(Byte), +} + +impl Tree +where + D: Def, + R: Ref, +{ + /// A `Tree` consisting only of a definition node. + pub(crate) fn def(def: D) -> Self { + Self::Def(def) + } + + /// A `Tree` representing an uninhabited type. + pub(crate) fn uninhabited() -> Self { + Self::Alt(vec![]) + } + + /// A `Tree` representing a zero-sized type. + pub(crate) fn unit() -> Self { + Self::Seq(Vec::new()) + } + + /// A `Tree` containing a single, uninitialized byte. + pub(crate) fn uninit() -> Self { + Self::Byte(Byte::Uninit) + } + + /// A `Tree` representing the layout of `bool`. + pub(crate) fn bool() -> Self { + Self::from_bits(0x00).or(Self::from_bits(0x01)) + } + + /// A `Tree` whose layout matches that of a `u8`. + pub(crate) fn u8() -> Self { + Self::Alt((0u8..=255).map(Self::from_bits).collect()) + } + + /// A `Tree` whose layout accepts exactly the given bit pattern. + pub(crate) fn from_bits(bits: u8) -> Self { + Self::Byte(Byte::Init(bits)) + } + + /// A `Tree` whose layout is a number of the given width. + pub(crate) fn number(width_in_bytes: usize) -> Self { + Self::Seq(vec![Self::u8(); width_in_bytes]) + } + + /// A `Tree` whose layout is entirely padding of the given width. + pub(crate) fn padding(width_in_bytes: usize) -> Self { + Self::Seq(vec![Self::uninit(); width_in_bytes]) + } + + /// Remove all `Def` nodes, and all branches of the layout for which `f` produces false. + pub(crate) fn prune(self, f: &F) -> Tree + where + F: Fn(D) -> bool, + { + match self { + Self::Seq(elts) => elts + .into_iter() + .map(|elt| elt.prune(f)) + .try_fold(Tree::unit(), |elts, elt| { + if elt == Tree::uninhabited() { + Err(Tree::uninhabited()) + } else { + Ok(elts.then(elt)) + } + }) + .into_ok_or_err(), + 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() + } + } + } + } + + /// Produces `true` if `Tree` is an inhabited type; otherwise false. + 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 Tree +where + D: Def, + R: Ref, +{ + /// Produces a new `Tree` where `other` is sequenced after `self`. + 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]), + } + } + + /// Produces a new `Tree` accepting either `self` or `other` as alternative layouts. + 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]), + } + } +} + +#[derive(Debug, Copy, Clone)] +pub(crate) enum Err { + /// The layout of the type is unspecified. + Unspecified, + /// This error will be surfaced elsewhere by rustc, so don't surface it. + Unknown, +} + +#[cfg(feature = "rustc")] +pub(crate) mod rustc { + use super::{Err, Tree}; + use crate::layout::rustc::{Def, Ref}; + + use rustc_middle::ty; + use rustc_middle::ty::layout::LayoutError; + use rustc_middle::ty::util::Discr; + use rustc_middle::ty::AdtDef; + use rustc_middle::ty::ParamEnv; + use rustc_middle::ty::SubstsRef; + use rustc_middle::ty::Ty; + use rustc_middle::ty::TyCtxt; + use rustc_middle::ty::VariantDef; + use rustc_target::abi::Align; + use std::alloc; + + impl<'tcx> From> for Err { + fn from(err: LayoutError<'tcx>) -> Self { + match err { + LayoutError::Unknown(..) => Self::Unknown, + err @ _ => unimplemented!("{:?}", err), + } + } + } + + trait LayoutExt { + fn clamp_align(&self, min_align: Align, max_align: Align) -> Self; + } + + impl LayoutExt for alloc::Layout { + fn clamp_align(&self, min_align: Align, max_align: Align) -> Self { + let min_align = min_align.bytes().try_into().unwrap(); + let max_align = max_align.bytes().try_into().unwrap(); + Self::from_size_align(self.size(), self.align().clamp(min_align, max_align)).unwrap() + } + } + + struct LayoutSummary { + total_align: Align, + total_size: usize, + discriminant_size: usize, + discriminant_align: Align, + } + + impl LayoutSummary { + fn from_ty<'tcx>(ty: Ty<'tcx>, ctx: TyCtxt<'tcx>) -> Result> { + use rustc_middle::ty::ParamEnvAnd; + use rustc_target::abi::{TyAndLayout, Variants}; + + let param_env = ParamEnv::reveal_all(); + let param_env_and_type = ParamEnvAnd { param_env, value: ty }; + let TyAndLayout { layout, .. } = ctx.layout_of(param_env_and_type)?; + + let total_size: usize = layout.size().bytes_usize(); + let total_align: Align = layout.align().abi; + let discriminant_align: Align; + let discriminant_size: usize; + + if let Variants::Multiple { tag, .. } = layout.variants() { + discriminant_align = tag.align(&ctx).abi; + discriminant_size = tag.size(&ctx).bytes_usize(); + } else { + discriminant_align = Align::ONE; + discriminant_size = 0; + }; + + Ok(Self { total_align, total_size, discriminant_align, discriminant_size }) + } + + fn into(&self) -> alloc::Layout { + alloc::Layout::from_size_align( + self.total_size, + self.total_align.bytes().try_into().unwrap(), + ) + .unwrap() + } + } + + impl<'tcx> Tree, Ref<'tcx>> { + pub fn from_ty(ty: Ty<'tcx>, tcx: TyCtxt<'tcx>) -> Result { + use rustc_middle::ty::FloatTy::*; + use rustc_middle::ty::IntTy::*; + use rustc_middle::ty::UintTy::*; + use rustc_target::abi::HasDataLayout; + + let target = tcx.data_layout(); + + match ty.kind() { + ty::Bool => Ok(Self::bool()), + + ty::Int(I8) | ty::Uint(U8) => Ok(Self::u8()), + ty::Int(I16) | ty::Uint(U16) => Ok(Self::number(2)), + ty::Int(I32) | ty::Uint(U32) | ty::Float(F32) => Ok(Self::number(4)), + ty::Int(I64) | ty::Uint(U64) | ty::Float(F64) => Ok(Self::number(8)), + ty::Int(I128) | ty::Uint(U128) => Ok(Self::number(16)), + ty::Int(Isize) | ty::Uint(Usize) => { + Ok(Self::number(target.pointer_size.bytes_usize())) + } + + ty::Tuple(members) => { + if members.len() == 0 { + Ok(Tree::unit()) + } else { + Err(Err::Unspecified) + } + } + + ty::Array(ty, len) => { + let len = len.try_eval_usize(tcx, ParamEnv::reveal_all()).unwrap(); + let elt = Tree::from_ty(*ty, tcx)?; + Ok(std::iter::repeat(elt) + .take(len as usize) + .fold(Tree::unit(), |tree, elt| tree.then(elt))) + } + + ty::Adt(adt_def, substs_ref) => { + use rustc_middle::ty::AdtKind; + + // If the layout is ill-specified, halt. + if !(adt_def.repr().c() || adt_def.repr().int.is_some()) { + return Err(Err::Unspecified); + } + + // Compute a summary of the type's layout. + let layout_summary = LayoutSummary::from_ty(ty, tcx)?; + + // The layout begins with this adt's visibility. + let vis = Self::def(Def::Adt(*adt_def)); + + // And is followed the layout(s) of its variants + Ok(vis.then(match adt_def.adt_kind() { + AdtKind::Struct => Self::from_repr_c_variant( + ty, + *adt_def, + substs_ref, + &layout_summary, + None, + adt_def.non_enum_variant(), + tcx, + )?, + AdtKind::Enum => { + tracing::trace!(?adt_def, "treeifying enum"); + let mut tree = Tree::uninhabited(); + + for (idx, discr) in adt_def.discriminants(tcx) { + tree = tree.or(Self::from_repr_c_variant( + ty, + *adt_def, + substs_ref, + &layout_summary, + Some(discr), + adt_def.variant(idx), + tcx, + )?); + } + + tree + } + AdtKind::Union => { + // is the layout well-defined? + if !adt_def.repr().c() { + return Err(Err::Unspecified); + } + + let ty_layout = layout_of(tcx, ty)?; + + let mut tree = Tree::uninhabited(); + + for field in adt_def.all_fields() { + let variant_ty = field.ty(tcx, substs_ref); + let variant_layout = layout_of(tcx, variant_ty)?; + let padding_needed = ty_layout.size() - variant_layout.size(); + let variant = Self::def(Def::Field(field)) + .then(Self::from_ty(variant_ty, tcx)?) + .then(Self::padding(padding_needed)); + + tree = tree.or(variant); + } + + tree + } + })) + } + _ => Err(Err::Unspecified), + } + } + + fn from_repr_c_variant( + ty: Ty<'tcx>, + adt_def: AdtDef<'tcx>, + substs_ref: SubstsRef<'tcx>, + layout_summary: &LayoutSummary, + discr: Option>, + variant_def: &'tcx VariantDef, + tcx: TyCtxt<'tcx>, + ) -> Result { + let mut tree = Tree::unit(); + + let repr = adt_def.repr(); + let min_align = repr.align.unwrap_or(Align::ONE); + let max_align = repr.pack.unwrap_or(Align::MAX); + + let clamp = + |align: Align| align.clamp(min_align, max_align).bytes().try_into().unwrap(); + + let variant_span = tracing::trace_span!( + "treeifying variant", + min_align = ?min_align, + max_align = ?max_align, + ) + .entered(); + + let mut variant_layout = alloc::Layout::from_size_align( + 0, + layout_summary.total_align.bytes().try_into().unwrap(), + ) + .unwrap(); + + // The layout of the variant is prefixed by the discriminant, if any. + if let Some(discr) = discr { + tracing::trace!(?discr, "treeifying discriminant"); + let discr_layout = alloc::Layout::from_size_align( + layout_summary.discriminant_size, + clamp(layout_summary.discriminant_align), + ) + .unwrap(); + tracing::trace!(?discr_layout, "computed discriminant layout"); + variant_layout = variant_layout.extend(discr_layout).unwrap().0; + tree = tree.then(Self::from_disr(discr, tcx, layout_summary.discriminant_size)); + } + + // Next come fields. + let fields_span = tracing::trace_span!("treeifying fields").entered(); + for field_def in variant_def.fields.iter() { + let field_ty = field_def.ty(tcx, substs_ref); + let _span = tracing::trace_span!("treeifying field", field = ?field_ty).entered(); + + // begin with the field's visibility + tree = tree.then(Self::def(Def::Field(field_def))); + + // compute the field's layout charactaristics + let field_layout = layout_of(tcx, field_ty)?.clamp_align(min_align, max_align); + + // next comes the field's padding + let padding_needed = variant_layout.padding_needed_for(field_layout.align()); + if padding_needed > 0 { + tree = tree.then(Self::padding(padding_needed)); + } + + // finally, the field's layout + tree = tree.then(Self::from_ty(field_ty, tcx)?); + + // extend the variant layout with the field layout + variant_layout = variant_layout.extend(field_layout).unwrap().0; + } + drop(fields_span); + + // finally: padding + let padding_span = tracing::trace_span!("adding trailing padding").entered(); + let padding_needed = layout_summary.total_size - variant_layout.size(); + if padding_needed > 0 { + tree = tree.then(Self::padding(padding_needed)); + }; + drop(padding_span); + drop(variant_span); + Ok(tree) + } + + pub fn from_disr(discr: Discr<'tcx>, tcx: TyCtxt<'tcx>, size: usize) -> Self { + // FIXME(@jswrenn): I'm certain this is missing needed endian nuance. + let bytes = discr.val.to_ne_bytes(); + let bytes = &bytes[..size]; + Self::Seq(bytes.into_iter().copied().map(|b| Self::from_bits(b)).collect()) + } + } + + fn layout_of<'tcx>( + ctx: TyCtxt<'tcx>, + ty: Ty<'tcx>, + ) -> Result> { + use rustc_middle::ty::ParamEnvAnd; + use rustc_target::abi::TyAndLayout; + + let param_env = ParamEnv::reveal_all(); + let param_env_and_type = ParamEnvAnd { param_env, value: ty }; + let TyAndLayout { layout, .. } = ctx.layout_of(param_env_and_type)?; + let layout = alloc::Layout::from_size_align( + layout.size().bytes_usize(), + layout.align().abi.bytes().try_into().unwrap(), + ) + .unwrap(); + tracing::trace!(?ty, ?layout, "computed layout for type"); + Ok(layout) + } +} diff --git a/compiler/rustc_transmute/src/layout/tree/tests.rs b/compiler/rustc_transmute/src/layout/tree/tests.rs new file mode 100644 index 000000000..90515e92f --- /dev/null +++ b/compiler/rustc_transmute/src/layout/tree/tests.rs @@ -0,0 +1,80 @@ +use super::Tree; + +#[derive(Debug, Hash, Eq, PartialEq, Clone, Copy)] +pub enum Def { + Visible, + Invisible, +} + +impl super::Def for Def {} + +mod prune { + use super::*; + + mod should_simplify { + use super::*; + + #[test] + fn seq_1() { + let layout: Tree = Tree::def(Def::Visible).then(Tree::from_bits(0x00)); + assert_eq!(layout.prune(&|d| matches!(d, Def::Visible)), Tree::from_bits(0x00)); + } + + #[test] + fn seq_2() { + let layout: Tree = + Tree::from_bits(0x00).then(Tree::def(Def::Visible)).then(Tree::from_bits(0x01)); + + assert_eq!( + layout.prune(&|d| matches!(d, Def::Visible)), + Tree::from_bits(0x00).then(Tree::from_bits(0x01)) + ); + } + } + + mod should_reject { + use super::*; + + #[test] + fn invisible_def() { + let layout: Tree = Tree::def(Def::Invisible); + assert_eq!(layout.prune(&|d| matches!(d, Def::Visible)), Tree::uninhabited()); + } + + #[test] + fn invisible_def_in_seq_len_2() { + let layout: Tree = Tree::def(Def::Visible).then(Tree::def(Def::Invisible)); + assert_eq!(layout.prune(&|d| matches!(d, Def::Visible)), Tree::uninhabited()); + } + + #[test] + fn invisible_def_in_seq_len_3() { + let layout: Tree = + Tree::def(Def::Visible).then(Tree::from_bits(0x00)).then(Tree::def(Def::Invisible)); + assert_eq!(layout.prune(&|d| matches!(d, Def::Visible)), Tree::uninhabited()); + } + } + + mod should_accept { + use super::*; + + #[test] + fn visible_def() { + let layout: Tree = Tree::def(Def::Visible); + assert_eq!(layout.prune(&|d| matches!(d, Def::Visible)), Tree::unit()); + } + + #[test] + fn visible_def_in_seq_len_2() { + let layout: Tree = Tree::def(Def::Visible).then(Tree::def(Def::Visible)); + assert_eq!(layout.prune(&|d| matches!(d, Def::Visible)), Tree::unit()); + } + + #[test] + fn visible_def_in_seq_len_3() { + let layout: Tree = + Tree::def(Def::Visible).then(Tree::from_bits(0x00)).then(Tree::def(Def::Visible)); + assert_eq!(layout.prune(&|d| matches!(d, Def::Visible)), Tree::from_bits(0x00)); + } + } +} -- cgit v1.2.3