Initial (incomplete) implementation of transmutability trait.

This initial implementation handles transmutations between types with specified layouts, except when references are involved.

Co-authored-by: Igor null <m1el.2027@gmail.com>

5 files changed, 993 insertions, 0 deletions

diff --git a/compiler/rustc_transmute/src/layout/dfa.rs b/compiler/rustc_transmute/src/layout/dfa.rs
new file mode 100644
index 00000000000..cdd3195712d
--- /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::{AtomicU64, Ordering};
+
+#[derive(PartialEq, Clone, Debug)]
+pub(crate) struct Dfa<R>
+where
+    R: Ref,
+{
+    pub(crate) transitions: Map<State, Transitions<R>>,
+    pub(crate) start: State,
+    pub(crate) accepting: State,
+}
+
+#[derive(PartialEq, Clone, Debug)]
+pub(crate) struct Transitions<R>
+where
+    R: Ref,
+{
+    byte_transitions: Map<Byte, State>,
+    ref_transitions: Map<R, State>,
+}
+
+impl<R> Default for Transitions<R>
+where
+    R: Ref,
+{
+    fn default() -> Self {
+        Self { byte_transitions: Map::default(), ref_transitions: Map::default() }
+    }
+}
+
+impl<R> Transitions<R>
+where
+    R: Ref,
+{
+    fn insert(&mut self, transition: Transition<R>, 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(u64);
+
+#[derive(Hash, Eq, PartialEq, Clone, Copy)]
+pub(crate) enum Transition<R>
+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<R> fmt::Debug for Transition<R>
+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<R> Dfa<R>
+where
+    R: Ref,
+{
+    pub(crate) fn unit() -> Self {
+        let transitions: Map<State, Transitions<R>> = Map::default();
+        let start = State::new();
+        let accepting = start;
+
+        Self { transitions, start, accepting }
+    }
+
+    #[cfg(test)]
+    pub(crate) fn bool() -> Self {
+        let mut transitions: Map<State, Transitions<R>> = 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 }
+    }
+
+    #[tracing::instrument]
+    #[cfg_attr(feature = "rustc", allow(rustc::potential_query_instability))]
+    pub(crate) fn from_nfa(nfa: Nfa<R>) -> Self {
+        let Nfa { transitions: nfa_transitions, start: nfa_start, accepting: nfa_accepting } = nfa;
+
+        let mut dfa_transitions: Map<State, Transitions<R>> = Map::default();
+        let mut nfa_to_dfa: Map<nfa::State, State> = 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<Byte, State>> {
+        Some(&self.transitions.get(&start)?.byte_transitions)
+    }
+
+    pub(crate) fn byte_from(&self, start: State, byte: Byte) -> Option<State> {
+        self.transitions.get(&start)?.byte_transitions.get(&byte).copied()
+    }
+
+    pub(crate) fn refs_from(&self, start: State) -> Option<&Map<R, State>> {
+        Some(&self.transitions.get(&start)?.ref_transitions)
+    }
+}
+
+impl State {
+    pub(crate) fn new() -> Self {
+        static COUNTER: AtomicU64 = AtomicU64::new(0);
+        Self(COUNTER.fetch_add(1, Ordering::SeqCst))
+    }
+}
+
+impl<R> From<nfa::Transition<R>> for Transition<R>
+where
+    R: Ref,
+{
+    fn from(nfa_transition: nfa::Transition<R>) -> 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 00000000000..cbf92bdacd6
--- /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 [`Nfa`].
+    #[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 [`Nfa`].
+    #[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 00000000000..817e426ba27
--- /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::{AtomicU64, 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<R>
+where
+    R: Ref,
+{
+    pub(crate) transitions: Map<State, Map<Transition<R>, Set<State>>>,
+    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(u64);
+
+/// The transitions between states in a `Nfa` reflect bit validity.
+#[derive(Hash, Eq, PartialEq, Clone, Copy)]
+pub(crate) enum Transition<R>
+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<R> fmt::Debug for Transition<R>
+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<R> Nfa<R>
+where
+    R: Ref,
+{
+    pub(crate) fn unit() -> Self {
+        let transitions: Map<State, Map<Transition<R>, Set<State>>> = 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<State, Map<Transition<R>, Set<State>>> = 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<State, Map<Transition<R>, Set<State>>> = 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<!, R>) -> Result<Self, Uninhabited> {
+        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<State, Map<Transition<R>, Set<State>>> = 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<State, Map<Transition<R>, Set<State>>> = 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<Transition<R>, Set<State>>> {
+        self.transitions.get(&start)
+    }
+}
+
+impl State {
+    pub(crate) fn new() -> Self {
+        static COUNTER: AtomicU64 = AtomicU64::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 00000000000..67b401855d4
--- /dev/null
+++ b/compiler/rustc_transmute/src/layout/tree.rs
@@ -0,0 +1,479 @@
+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<D, R>
+where
+    D: Def,
+    R: Ref,
+{
+    /// A sequence of successive layouts.
+    Seq(Vec<Self>),
+    /// A choice between alternative layouts.
+    Alt(Vec<Self>),
+    /// A definition node.
+    Def(D),
+    /// A reference node.
+    Ref(R),
+    /// A byte node.
+    Byte(Byte),
+}
+
+impl<D, R> Tree<D, R>
+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.
+    #[tracing::instrument]
+    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<F>(self, f: &F) -> Tree<!, R>
+    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<D, R> Tree<D, R>
+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<LayoutError<'tcx>> 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<Self, LayoutError<'tcx>> {
+            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<Def<'tcx>, Ref<'tcx>> {
+        pub fn from_ty(ty: Ty<'tcx>, tcx: TyCtxt<'tcx>) -> Result<Self, Err> {
+            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 = ?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<Discr<'tcx>>,
+            variant_def: &'tcx VariantDef,
+            tcx: TyCtxt<'tcx>,
+        ) -> Result<Self, Err> {
+            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 = ?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 = ?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<alloc::Layout, LayoutError<'tcx>> {
+        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 = ?ty,
+            layout = ?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 00000000000..90515e92f7a
--- /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<Def, !> = 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<Def, !> =
+                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<Def, !> = 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<Def, !> = 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<Def, !> =
+                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<Def, !> = 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<Def, !> = 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<Def, !> =
+                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));
+        }
+    }
+}