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>

3 files changed, 528 insertions, 0 deletions

diff --git a/compiler/rustc_transmute/src/maybe_transmutable/mod.rs b/compiler/rustc_transmute/src/maybe_transmutable/mod.rs
new file mode 100644
index 00000000000..ef3852001a8
--- /dev/null
+++ b/compiler/rustc_transmute/src/maybe_transmutable/mod.rs
@@ -0,0 +1,320 @@
+use crate::Map;
+use crate::{Answer, Reason};
+
+#[cfg(test)]
+mod tests;
+
+mod query_context;
+use query_context::QueryContext;
+
+use crate::layout::{self, dfa, Byte, Dfa, Nfa, Tree, Uninhabited};
+pub(crate) struct MaybeTransmutableQuery<L, C>
+where
+    C: QueryContext,
+{
+    src: L,
+    dst: L,
+    scope: <C as QueryContext>::Scope,
+    assume: crate::Assume,
+    context: C,
+}
+
+impl<L, C> MaybeTransmutableQuery<L, C>
+where
+    C: QueryContext,
+{
+    pub(crate) fn new(
+        src: L,
+        dst: L,
+        scope: <C as QueryContext>::Scope,
+        assume: crate::Assume,
+        context: C,
+    ) -> Self {
+        Self { src, dst, scope, assume, context }
+    }
+
+    pub(crate) fn map_layouts<F, M>(
+        self,
+        f: F,
+    ) -> Result<MaybeTransmutableQuery<M, C>, Answer<<C as QueryContext>::Ref>>
+    where
+        F: FnOnce(
+            L,
+            L,
+            <C as QueryContext>::Scope,
+            &C,
+        ) -> Result<(M, M), Answer<<C as QueryContext>::Ref>>,
+    {
+        let Self { src, dst, scope, assume, context } = self;
+
+        let (src, dst) = f(src, dst, scope, &context)?;
+
+        Ok(MaybeTransmutableQuery { src, dst, scope, assume, context })
+    }
+}
+
+#[cfg(feature = "rustc")]
+mod rustc {
+    use super::*;
+    use crate::layout::tree::Err;
+
+    use rustc_middle::ty::Ty;
+    use rustc_middle::ty::TyCtxt;
+
+    impl<'tcx> MaybeTransmutableQuery<Ty<'tcx>, TyCtxt<'tcx>> {
+        /// This method begins by converting `src` and `dst` from `Ty`s to `Tree`s,
+        /// then computes an answer using those trees.
+        #[tracing::instrument(skip(self), fields(src = ?self.src, dst = ?self.dst))]
+        pub fn answer(self) -> Answer<<TyCtxt<'tcx> as QueryContext>::Ref> {
+            let query_or_answer = self.map_layouts(|src, dst, scope, &context| {
+                // Convert `src` and `dst` from their rustc representations, to `Tree`-based
+                // representations. If these conversions fail, conclude that the transmutation is
+                // unacceptable; the layouts of both the source and destination types must be
+                // well-defined.
+                let src = Tree::from_ty(src, context).map_err(|err| match err {
+                    // Answer `Yes` here, because "Unknown Type" will already be reported by
+                    // rustc. No need to spam the user with more errors.
+                    Err::Unknown => Answer::Yes,
+                    Err::Unspecified => Answer::No(Reason::SrcIsUnspecified),
+                })?;
+
+                let dst = Tree::from_ty(dst, context).map_err(|err| match err {
+                    Err::Unknown => Answer::Yes,
+                    Err::Unspecified => Answer::No(Reason::DstIsUnspecified),
+                })?;
+
+                Ok((src, dst))
+            });
+
+            match query_or_answer {
+                Ok(query) => query.answer(),
+                Err(answer) => answer,
+            }
+        }
+    }
+}
+
+impl<C> MaybeTransmutableQuery<Tree<<C as QueryContext>::Def, <C as QueryContext>::Ref>, C>
+where
+    C: QueryContext,
+{
+    /// Answers whether a `Tree` is transmutable into another `Tree`.
+    ///
+    /// This method begins by de-def'ing `src` and `dst`, and prunes private paths from `dst`,
+    /// then converts `src` and `dst` to `Nfa`s, and computes an answer using those NFAs.
+    #[inline(always)]
+    #[tracing::instrument(skip(self), fields(src = ?self.src, dst = ?self.dst))]
+    pub(crate) fn answer(self) -> Answer<<C as QueryContext>::Ref> {
+        let assume_visibility = self.assume.visibility;
+        let query_or_answer = self.map_layouts(|src, dst, scope, context| {
+            // Remove all `Def` nodes from `src`, without checking their visibility.
+            let src = src.prune(&|def| true);
+
+            tracing::trace!(src = ?src, "pruned src");
+
+            // Remove all `Def` nodes from `dst`, additionally...
+            let dst = if assume_visibility {
+                // ...if visibility is assumed, don't check their visibility.
+                dst.prune(&|def| true)
+            } else {
+                // ...otherwise, prune away all unreachable paths through the `Dst` layout.
+                dst.prune(&|def| context.is_accessible_from(def, scope))
+            };
+
+            tracing::trace!(dst = ?dst, "pruned dst");
+
+            // Convert `src` from a tree-based representation to an NFA-based representation.
+            // If the conversion fails because `src` is uninhabited, conclude that the transmutation
+            // is acceptable, because instances of the `src` type do not exist.
+            let src = Nfa::from_tree(src).map_err(|Uninhabited| Answer::Yes)?;
+
+            // Convert `dst` from a tree-based representation to an NFA-based representation.
+            // If the conversion fails because `src` is uninhabited, conclude that the transmutation
+            // is unacceptable, because instances of the `dst` type do not exist.
+            let dst =
+                Nfa::from_tree(dst).map_err(|Uninhabited| Answer::No(Reason::DstIsPrivate))?;
+
+            Ok((src, dst))
+        });
+
+        match query_or_answer {
+            Ok(query) => query.answer(),
+            Err(answer) => answer,
+        }
+    }
+}
+
+impl<C> MaybeTransmutableQuery<Nfa<<C as QueryContext>::Ref>, C>
+where
+    C: QueryContext,
+{
+    /// Answers whether a `Nfa` is transmutable into another `Nfa`.
+    ///
+    /// This method converts `src` and `dst` to DFAs, then computes an answer using those DFAs.
+    #[inline(always)]
+    #[tracing::instrument(skip(self), fields(src = ?self.src, dst = ?self.dst))]
+    pub(crate) fn answer(self) -> Answer<<C as QueryContext>::Ref> {
+        let query_or_answer = self
+            .map_layouts(|src, dst, scope, context| Ok((Dfa::from_nfa(src), Dfa::from_nfa(dst))));
+
+        match query_or_answer {
+            Ok(query) => query.answer(),
+            Err(answer) => answer,
+        }
+    }
+}
+
+impl<C> MaybeTransmutableQuery<Dfa<<C as QueryContext>::Ref>, C>
+where
+    C: QueryContext,
+{
+    /// Answers whether a `Nfa` is transmutable into another `Nfa`.
+    ///
+    /// This method converts `src` and `dst` to DFAs, then computes an answer using those DFAs.
+    pub(crate) fn answer(self) -> Answer<<C as QueryContext>::Ref> {
+        MaybeTransmutableQuery {
+            src: &self.src,
+            dst: &self.dst,
+            scope: self.scope,
+            assume: self.assume,
+            context: self.context,
+        }
+        .answer()
+    }
+}
+
+impl<'l, C> MaybeTransmutableQuery<&'l Dfa<<C as QueryContext>::Ref>, C>
+where
+    C: QueryContext,
+{
+    pub(crate) fn answer(&mut self) -> Answer<<C as QueryContext>::Ref> {
+        self.answer_memo(&mut Map::default(), self.src.start, self.dst.start)
+    }
+
+    #[inline(always)]
+    #[tracing::instrument(skip(self))]
+    fn answer_memo(
+        &self,
+        cache: &mut Map<(dfa::State, dfa::State), Answer<<C as QueryContext>::Ref>>,
+        src_state: dfa::State,
+        dst_state: dfa::State,
+    ) -> Answer<<C as QueryContext>::Ref> {
+        if let Some(answer) = cache.get(&(src_state, dst_state)) {
+            answer.clone()
+        } else {
+            let answer = if dst_state == self.dst.accepting {
+                // truncation: `size_of(Src) >= size_of(Dst)`
+                Answer::Yes
+            } else if src_state == self.src.accepting {
+                // extension: `size_of(Src) >= size_of(Dst)`
+                if let Some(dst_state_prime) = self.dst.byte_from(dst_state, Byte::Uninit) {
+                    self.answer_memo(cache, src_state, dst_state_prime)
+                } else {
+                    Answer::No(Reason::DstIsTooBig)
+                }
+            } else {
+                let src_quantification = if self.assume.validity {
+                    // if the compiler may assume that the programmer is doing additional validity checks,
+                    // (e.g.: that `src != 3u8` when the destination type is `bool`)
+                    // then there must exist at least one transition out of `src_state` such that the transmute is viable...
+                    there_exists
+                } else {
+                    // if the compiler cannot assume that the programmer is doing additional validity checks,
+                    // then for all transitions out of `src_state`, such that the transmute is viable...
+                    // then there must exist at least one transition out of `src_state` such that the transmute is viable...
+                    for_all
+                };
+
+                src_quantification(
+                    self.src.bytes_from(src_state).unwrap_or(&Map::default()),
+                    |(&src_validity, &src_state_prime)| {
+                        if let Some(dst_state_prime) = self.dst.byte_from(dst_state, src_validity) {
+                            self.answer_memo(cache, src_state_prime, dst_state_prime)
+                        } else if let Some(dst_state_prime) =
+                            self.dst.byte_from(dst_state, Byte::Uninit)
+                        {
+                            self.answer_memo(cache, src_state_prime, dst_state_prime)
+                        } else {
+                            Answer::No(Reason::DstIsBitIncompatible)
+                        }
+                    },
+                )
+            };
+            cache.insert((src_state, dst_state), answer.clone());
+            answer
+        }
+    }
+}
+
+impl<R> Answer<R>
+where
+    R: layout::Ref,
+{
+    pub(crate) fn and(self, rhs: Self) -> Self {
+        match (self, rhs) {
+            (Self::No(reason), _) | (_, Self::No(reason)) => Self::No(reason),
+            (Self::Yes, Self::Yes) => Self::Yes,
+            (Self::IfAll(mut lhs), Self::IfAll(ref mut rhs)) => {
+                lhs.append(rhs);
+                Self::IfAll(lhs)
+            }
+            (constraint, Self::IfAll(mut constraints))
+            | (Self::IfAll(mut constraints), constraint) => {
+                constraints.push(constraint);
+                Self::IfAll(constraints)
+            }
+            (lhs, rhs) => Self::IfAll(vec![lhs, rhs]),
+        }
+    }
+
+    pub(crate) fn or(self, rhs: Self) -> Self {
+        match (self, rhs) {
+            (Self::Yes, _) | (_, Self::Yes) => Self::Yes,
+            (Self::No(lhr), Self::No(rhr)) => Self::No(lhr),
+            (Self::IfAny(mut lhs), Self::IfAny(ref mut rhs)) => {
+                lhs.append(rhs);
+                Self::IfAny(lhs)
+            }
+            (constraint, Self::IfAny(mut constraints))
+            | (Self::IfAny(mut constraints), constraint) => {
+                constraints.push(constraint);
+                Self::IfAny(constraints)
+            }
+            (lhs, rhs) => Self::IfAny(vec![lhs, rhs]),
+        }
+    }
+}
+
+pub fn for_all<R, I, F>(iter: I, f: F) -> Answer<R>
+where
+    R: layout::Ref,
+    I: IntoIterator,
+    F: FnMut(<I as IntoIterator>::Item) -> Answer<R>,
+{
+    use std::ops::ControlFlow::{Break, Continue};
+    let (Continue(result) | Break(result)) =
+        iter.into_iter().map(f).try_fold(Answer::Yes, |constraints, constraint| {
+            match constraint.and(constraints) {
+                Answer::No(reason) => Break(Answer::No(reason)),
+                maybe => Continue(maybe),
+            }
+        });
+    result
+}
+
+pub fn there_exists<R, I, F>(iter: I, f: F) -> Answer<R>
+where
+    R: layout::Ref,
+    I: IntoIterator,
+    F: FnMut(<I as IntoIterator>::Item) -> Answer<R>,
+{
+    use std::ops::ControlFlow::{Break, Continue};
+    let (Continue(result) | Break(result)) = iter.into_iter().map(f).try_fold(
+        Answer::No(Reason::DstIsBitIncompatible),
+        |constraints, constraint| match constraint.or(constraints) {
+            Answer::Yes => Break(Answer::Yes),
+            maybe => Continue(maybe),
+        },
+    );
+    result
+}
diff --git a/compiler/rustc_transmute/src/maybe_transmutable/query_context.rs b/compiler/rustc_transmute/src/maybe_transmutable/query_context.rs
new file mode 100644
index 00000000000..ab9bcd232f0
--- /dev/null
+++ b/compiler/rustc_transmute/src/maybe_transmutable/query_context.rs
@@ -0,0 +1,93 @@
+use crate::layout;
+
+/// Context necessary to answer the question "Are these types transmutable?".
+pub(crate) trait QueryContext {
+    type Def: layout::Def;
+    type Ref: layout::Ref;
+    type Scope: Copy;
+
+    /// Is `def` accessible from the defining module of `scope`?
+    fn is_accessible_from(&self, def: Self::Def, scope: Self::Scope) -> bool;
+
+    fn min_align(&self, reference: Self::Ref) -> usize;
+}
+
+#[cfg(test)]
+pub(crate) mod test {
+    use super::QueryContext;
+
+    pub(crate) struct UltraMinimal;
+
+    #[derive(Debug, Hash, Eq, PartialEq, Clone, Copy)]
+    pub(crate) enum Def {
+        Visible,
+        Invisible,
+    }
+
+    impl crate::layout::Def for Def {}
+
+    impl QueryContext for UltraMinimal {
+        type Def = Def;
+        type Ref = !;
+        type Scope = ();
+
+        fn is_accessible_from(&self, def: Def, scope: ()) -> bool {
+            matches!(Def::Visible, def)
+        }
+
+        fn min_align(&self, reference: !) -> usize {
+            unimplemented!()
+        }
+    }
+}
+
+#[cfg(feature = "rustc")]
+mod rustc {
+    use super::*;
+    use rustc_middle::ty::{Ty, TyCtxt};
+
+    impl<'tcx> super::QueryContext for TyCtxt<'tcx> {
+        type Def = layout::rustc::Def<'tcx>;
+        type Ref = layout::rustc::Ref<'tcx>;
+
+        type Scope = Ty<'tcx>;
+
+        #[tracing::instrument(skip(self))]
+        fn is_accessible_from(&self, def: Self::Def, scope: Self::Scope) -> bool {
+            use layout::rustc::Def;
+            use rustc_middle::ty;
+
+            let parent = if let ty::Adt(adt_def, ..) = scope.kind() {
+                use rustc_middle::ty::DefIdTree;
+                let parent = self.parent(adt_def.did());
+                parent
+            } else {
+                // Is this always how we want to handle a non-ADT scope?
+                return false;
+            };
+
+            let def_id = match def {
+                Def::Adt(adt_def) => adt_def.did(),
+                Def::Variant(variant_def) => variant_def.def_id,
+                Def::Field(field_def) => field_def.did,
+                Def::Primitive => {
+                    // primitives do not have a def_id, but they're always accessible
+                    return true;
+                }
+            };
+
+            let ret = if self.visibility(def_id).is_accessible_from(parent, *self) {
+                true
+            } else {
+                false
+            };
+
+            tracing::trace!(ret = ?ret, "ret");
+            ret
+        }
+
+        fn min_align(&self, reference: Self::Ref) -> usize {
+            unimplemented!()
+        }
+    }
+}
diff --git a/compiler/rustc_transmute/src/maybe_transmutable/tests.rs b/compiler/rustc_transmute/src/maybe_transmutable/tests.rs
new file mode 100644
index 00000000000..d9d125687f6
--- /dev/null
+++ b/compiler/rustc_transmute/src/maybe_transmutable/tests.rs
@@ -0,0 +1,115 @@
+use super::query_context::test::{Def, UltraMinimal};
+use crate::maybe_transmutable::MaybeTransmutableQuery;
+use crate::{layout, Answer, Reason, Set};
+use itertools::Itertools;
+
+mod bool {
+    use super::*;
+
+    #[test]
+    fn should_permit_identity_transmutation_tree() {
+        println!("{:?}", layout::Tree::<!, !>::bool());
+        let answer = crate::maybe_transmutable::MaybeTransmutableQuery::new(
+            layout::Tree::<Def, !>::bool(),
+            layout::Tree::<Def, !>::bool(),
+            (),
+            crate::Assume { alignment: false, lifetimes: false, validity: true, visibility: false },
+            UltraMinimal,
+        )
+        .answer();
+        assert_eq!(answer, Answer::Yes);
+    }
+
+    #[test]
+    fn should_permit_identity_transmutation_dfa() {
+        let answer = crate::maybe_transmutable::MaybeTransmutableQuery::new(
+            layout::Dfa::<!>::bool(),
+            layout::Dfa::<!>::bool(),
+            (),
+            crate::Assume { alignment: false, lifetimes: false, validity: true, visibility: false },
+            UltraMinimal,
+        )
+        .answer();
+        assert_eq!(answer, Answer::Yes);
+    }
+
+    #[test]
+    fn should_permit_validity_expansion_and_reject_contraction() {
+        let un = layout::Tree::<Def, !>::uninhabited();
+        let b0 = layout::Tree::<Def, !>::from_bits(0);
+        let b1 = layout::Tree::<Def, !>::from_bits(1);
+        let b2 = layout::Tree::<Def, !>::from_bits(2);
+
+        let alts = [b0, b1, b2];
+
+        let into_layout = |alts: Vec<_>| {
+            alts.into_iter().fold(layout::Tree::<Def, !>::uninhabited(), layout::Tree::<Def, !>::or)
+        };
+
+        let into_set = |alts: Vec<_>| {
+            #[cfg(feature = "rustc")]
+            let mut set = Set::default();
+            #[cfg(not(feature = "rustc"))]
+            let mut set = Set::new();
+            set.extend(alts);
+            set
+        };
+
+        for src_alts in alts.clone().into_iter().powerset() {
+            let src_layout = into_layout(src_alts.clone());
+            let src_set = into_set(src_alts.clone());
+
+            for dst_alts in alts.clone().into_iter().powerset().filter(|alts| !alts.is_empty()) {
+                let dst_layout = into_layout(dst_alts.clone());
+                let dst_set = into_set(dst_alts.clone());
+
+                if src_set.is_subset(&dst_set) {
+                    assert_eq!(
+                        Answer::Yes,
+                        MaybeTransmutableQuery::new(
+                            src_layout.clone(),
+                            dst_layout.clone(),
+                            (),
+                            crate::Assume { validity: false, ..crate::Assume::default() },
+                            UltraMinimal,
+                        )
+                        .answer(),
+                        "{:?} SHOULD be transmutable into {:?}",
+                        src_layout,
+                        dst_layout
+                    );
+                } else if !src_set.is_disjoint(&dst_set) {
+                    assert_eq!(
+                        Answer::Yes,
+                        MaybeTransmutableQuery::new(
+                            src_layout.clone(),
+                            dst_layout.clone(),
+                            (),
+                            crate::Assume { validity: true, ..crate::Assume::default() },
+                            UltraMinimal,
+                        )
+                        .answer(),
+                        "{:?} SHOULD be transmutable (assuming validity) into {:?}",
+                        src_layout,
+                        dst_layout
+                    );
+                } else {
+                    assert_eq!(
+                        Answer::No(Reason::DstIsBitIncompatible),
+                        MaybeTransmutableQuery::new(
+                            src_layout.clone(),
+                            dst_layout.clone(),
+                            (),
+                            crate::Assume { validity: false, ..crate::Assume::default() },
+                            UltraMinimal,
+                        )
+                        .answer(),
+                        "{:?} should NOT be transmutable into {:?}",
+                        src_layout,
+                        dst_layout
+                    );
+                }
+            }
+        }
+    }
+}