safe transmute: revise safety analysis

Migrate to a simplified safety analysis that does not use visibility.

Closes https://github.com/rust-lang/project-safe-transmute/issues/15

7 files changed, 168 insertions, 109 deletions

diff --git a/compiler/rustc_transmute/src/layout/mod.rs b/compiler/rustc_transmute/src/layout/mod.rs
index 76d97e0e6e7..0441b49cb14 100644
--- a/compiler/rustc_transmute/src/layout/mod.rs
+++ b/compiler/rustc_transmute/src/layout/mod.rs
@@ -29,14 +29,21 @@ impl fmt::Debug for Byte {
     }
 }
 
-pub(crate) trait Def: Debug + Hash + Eq + PartialEq + Copy + Clone {}
+pub(crate) trait Def: Debug + Hash + Eq + PartialEq + Copy + Clone {
+    fn has_safety_invariants(&self) -> bool;
+}
 pub trait Ref: Debug + Hash + Eq + PartialEq + Copy + Clone {
     fn min_align(&self) -> usize;
 
     fn is_mutable(&self) -> bool;
 }
 
-impl Def for ! {}
+impl Def for ! {
+    fn has_safety_invariants(&self) -> bool {
+        unreachable!()
+    }
+}
+
 impl Ref for ! {
     fn min_align(&self) -> usize {
         unreachable!()
@@ -83,5 +90,12 @@ pub mod rustc {
         Primitive,
     }
 
-    impl<'tcx> super::Def for Def<'tcx> {}
+    impl<'tcx> super::Def for Def<'tcx> {
+        fn has_safety_invariants(&self) -> bool {
+            // Rust presently has no notion of 'unsafe fields', so for now we
+            // make the conservative assumption that everything besides
+            // primitive types carry safety invariants.
+            self != &Self::Primitive
+        }
+    }
 }
diff --git a/compiler/rustc_transmute/src/layout/tree.rs b/compiler/rustc_transmute/src/layout/tree.rs
index 86a077ee808..71b72828e4c 100644
--- a/compiler/rustc_transmute/src/layout/tree.rs
+++ b/compiler/rustc_transmute/src/layout/tree.rs
@@ -81,7 +81,8 @@ where
         Self::Seq(vec![Self::uninit(); width_in_bytes])
     }
 
-    /// Remove all `Def` nodes, and all branches of the layout for which `f` produces false.
+    /// Remove all `Def` nodes, and all branches of the layout for which `f`
+    /// produces `true`.
     pub(crate) fn prune<F>(self, f: &F) -> Tree<!, R>
     where
         F: Fn(D) -> bool,
@@ -106,7 +107,7 @@ where
             Self::Byte(b) => Tree::Byte(b),
             Self::Ref(r) => Tree::Ref(r),
             Self::Def(d) => {
-                if !f(d) {
+                if f(d) {
                     Tree::uninhabited()
                 } else {
                     Tree::unit()
diff --git a/compiler/rustc_transmute/src/layout/tree/tests.rs b/compiler/rustc_transmute/src/layout/tree/tests.rs
index 90515e92f7a..3cb47517c21 100644
--- a/compiler/rustc_transmute/src/layout/tree/tests.rs
+++ b/compiler/rustc_transmute/src/layout/tree/tests.rs
@@ -2,11 +2,15 @@ use super::Tree;
 
 #[derive(Debug, Hash, Eq, PartialEq, Clone, Copy)]
 pub enum Def {
-    Visible,
-    Invisible,
+    NoSafetyInvariants,
+    HasSafetyInvariants,
 }
 
-impl super::Def for Def {}
+impl super::Def for Def {
+    fn has_safety_invariants(&self) -> bool {
+        self == &Self::HasSafetyInvariants
+    }
+}
 
 mod prune {
     use super::*;
@@ -16,17 +20,22 @@ mod prune {
 
         #[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));
+            let layout: Tree<Def, !> =
+                Tree::def(Def::NoSafetyInvariants).then(Tree::from_bits(0x00));
+            assert_eq!(
+                layout.prune(&|d| matches!(d, Def::HasSafetyInvariants)),
+                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));
+            let layout: Tree<Def, !> = Tree::from_bits(0x00)
+                .then(Tree::def(Def::NoSafetyInvariants))
+                .then(Tree::from_bits(0x01));
 
             assert_eq!(
-                layout.prune(&|d| matches!(d, Def::Visible)),
+                layout.prune(&|d| matches!(d, Def::HasSafetyInvariants)),
                 Tree::from_bits(0x00).then(Tree::from_bits(0x01))
             );
         }
@@ -37,21 +46,32 @@ mod prune {
 
         #[test]
         fn invisible_def() {
-            let layout: Tree<Def, !> = Tree::def(Def::Invisible);
-            assert_eq!(layout.prune(&|d| matches!(d, Def::Visible)), Tree::uninhabited());
+            let layout: Tree<Def, !> = Tree::def(Def::HasSafetyInvariants);
+            assert_eq!(
+                layout.prune(&|d| matches!(d, Def::HasSafetyInvariants)),
+                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());
+            let layout: Tree<Def, !> =
+                Tree::def(Def::NoSafetyInvariants).then(Tree::def(Def::HasSafetyInvariants));
+            assert_eq!(
+                layout.prune(&|d| matches!(d, Def::HasSafetyInvariants)),
+                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());
+            let layout: Tree<Def, !> = Tree::def(Def::NoSafetyInvariants)
+                .then(Tree::from_bits(0x00))
+                .then(Tree::def(Def::HasSafetyInvariants));
+            assert_eq!(
+                layout.prune(&|d| matches!(d, Def::HasSafetyInvariants)),
+                Tree::uninhabited()
+            );
         }
     }
 
@@ -60,21 +80,26 @@ mod prune {
 
         #[test]
         fn visible_def() {
-            let layout: Tree<Def, !> = Tree::def(Def::Visible);
-            assert_eq!(layout.prune(&|d| matches!(d, Def::Visible)), Tree::unit());
+            let layout: Tree<Def, !> = Tree::def(Def::NoSafetyInvariants);
+            assert_eq!(layout.prune(&|d| matches!(d, Def::HasSafetyInvariants)), 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());
+            let layout: Tree<Def, !> =
+                Tree::def(Def::NoSafetyInvariants).then(Tree::def(Def::NoSafetyInvariants));
+            assert_eq!(layout.prune(&|d| matches!(d, Def::HasSafetyInvariants)), 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));
+            let layout: Tree<Def, !> = Tree::def(Def::NoSafetyInvariants)
+                .then(Tree::from_bits(0x00))
+                .then(Tree::def(Def::NoSafetyInvariants));
+            assert_eq!(
+                layout.prune(&|d| matches!(d, Def::HasSafetyInvariants)),
+                Tree::from_bits(0x00)
+            );
         }
     }
 }
diff --git a/compiler/rustc_transmute/src/lib.rs b/compiler/rustc_transmute/src/lib.rs
index ac4f67d1b55..fefce2640eb 100644
--- a/compiler/rustc_transmute/src/lib.rs
+++ b/compiler/rustc_transmute/src/lib.rs
@@ -49,8 +49,8 @@ pub enum Reason {
     DstIsUnspecified,
     /// The layout of the destination type is bit-incompatible with the source type.
     DstIsBitIncompatible,
-    /// There aren't any public constructors for `Dst`.
-    DstIsPrivate,
+    /// The destination type may carry safety invariants.
+    DstMayHaveSafetyInvariants,
     /// `Dst` is larger than `Src`, and the excess bytes were not exclusively uninitialized.
     DstIsTooBig,
     /// Src should have a stricter alignment than Dst, but it does not.
@@ -106,13 +106,11 @@ mod rustc {
             &mut self,
             cause: ObligationCause<'tcx>,
             types: Types<'tcx>,
-            scope: Ty<'tcx>,
             assume: crate::Assume,
         ) -> crate::Answer<crate::layout::rustc::Ref<'tcx>> {
             crate::maybe_transmutable::MaybeTransmutableQuery::new(
                 types.src,
                 types.dst,
-                scope,
                 assume,
                 self.infcx.tcx,
             )
diff --git a/compiler/rustc_transmute/src/maybe_transmutable/mod.rs b/compiler/rustc_transmute/src/maybe_transmutable/mod.rs
index bf3c390c800..0e05aa4d3b2 100644
--- a/compiler/rustc_transmute/src/maybe_transmutable/mod.rs
+++ b/compiler/rustc_transmute/src/maybe_transmutable/mod.rs
@@ -3,7 +3,7 @@ pub(crate) mod query_context;
 mod tests;
 
 use crate::{
-    layout::{self, dfa, Byte, Dfa, Nfa, Ref, Tree, Uninhabited},
+    layout::{self, dfa, Byte, Def, Dfa, Nfa, Ref, Tree, Uninhabited},
     maybe_transmutable::query_context::QueryContext,
     Answer, Condition, Map, Reason,
 };
@@ -14,7 +14,6 @@ where
 {
     src: L,
     dst: L,
-    scope: <C as QueryContext>::Scope,
     assume: crate::Assume,
     context: C,
 }
@@ -23,14 +22,8 @@ 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 new(src: L, dst: L, assume: crate::Assume, context: C) -> Self {
+        Self { src, dst, assume, context }
     }
 }
 
@@ -48,7 +41,7 @@ mod rustc {
         /// then computes an answer using those trees.
         #[instrument(level = "debug", skip(self), fields(src = ?self.src, dst = ?self.dst))]
         pub fn answer(self) -> Answer<<TyCtxt<'tcx> as QueryContext>::Ref> {
-            let Self { src, dst, scope, assume, context } = self;
+            let Self { src, dst, assume, context } = self;
 
             // Convert `src` and `dst` from their rustc representations, to `Tree`-based
             // representations. If these conversions fail, conclude that the transmutation is
@@ -67,9 +60,7 @@ mod rustc {
                 (_, Err(Err::Unspecified)) => Answer::No(Reason::DstIsUnspecified),
                 (Err(Err::SizeOverflow), _) => Answer::No(Reason::SrcSizeOverflow),
                 (_, Err(Err::SizeOverflow)) => Answer::No(Reason::DstSizeOverflow),
-                (Ok(src), Ok(dst)) => {
-                    MaybeTransmutableQuery { src, dst, scope, assume, context }.answer()
-                }
+                (Ok(src), Ok(dst)) => MaybeTransmutableQuery { src, dst, assume, context }.answer(),
             }
         }
     }
@@ -86,43 +77,51 @@ where
     #[inline(always)]
     #[instrument(level = "debug", skip(self), fields(src = ?self.src, dst = ?self.dst))]
     pub(crate) fn answer(self) -> Answer<<C as QueryContext>::Ref> {
-        let assume_visibility = self.assume.safety;
-
-        let Self { src, dst, scope, assume, context } = self;
+        let Self { src, dst, assume, context } = self;
 
-        // Remove all `Def` nodes from `src`, without checking their visibility.
-        let src = src.prune(&|def| true);
+        // Unconditionally all `Def` nodes from `src`, without pruning away the
+        // branches they appear in. This is valid to do for value-to-value
+        // transmutations, but not for `&mut T` to `&mut U`; we will need to be
+        // more sophisticated to handle transmutations between mutable
+        // references.
+        let src = src.prune(&|def| false);
 
         trace!(?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)
+        let dst = if assume.safety {
+            // ...if safety is assumed, don't check if they carry safety
+            // invariants; retain all paths.
+            dst.prune(&|def| false)
         } else {
-            // ...otherwise, prune away all unreachable paths through the `Dst` layout.
-            dst.prune(&|def| context.is_accessible_from(def, scope))
+            // ...otherwise, prune away all paths with safety invariants from
+            // the `Dst` layout.
+            dst.prune(&|def| def.has_safety_invariants())
         };
 
         trace!(?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.
+        // 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 = match Nfa::from_tree(src) {
             Ok(src) => src,
             Err(Uninhabited) => return 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.
+        // 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. Valid instances of
+        // the `dst` type do not exist, either because it's genuinely
+        // uninhabited, or because there are no branches of the tree that are
+        // free of safety invariants.
         let dst = match Nfa::from_tree(dst) {
             Ok(dst) => dst,
-            Err(Uninhabited) => return Answer::No(Reason::DstIsPrivate),
+            Err(Uninhabited) => return Answer::No(Reason::DstMayHaveSafetyInvariants),
         };
 
-        MaybeTransmutableQuery { src, dst, scope, assume, context }.answer()
+        MaybeTransmutableQuery { src, dst, assume, context }.answer()
     }
 }
 
@@ -136,10 +135,10 @@ where
     #[inline(always)]
     #[instrument(level = "debug", skip(self), fields(src = ?self.src, dst = ?self.dst))]
     pub(crate) fn answer(self) -> Answer<<C as QueryContext>::Ref> {
-        let Self { src, dst, scope, assume, context } = self;
+        let Self { src, dst, assume, context } = self;
         let src = Dfa::from_nfa(src);
         let dst = Dfa::from_nfa(dst);
-        MaybeTransmutableQuery { src, dst, scope, assume, context }.answer()
+        MaybeTransmutableQuery { src, dst, assume, context }.answer()
     }
 }
 
diff --git a/compiler/rustc_transmute/src/maybe_transmutable/query_context.rs b/compiler/rustc_transmute/src/maybe_transmutable/query_context.rs
index 0cae0377ee8..54ed03d44e6 100644
--- a/compiler/rustc_transmute/src/maybe_transmutable/query_context.rs
+++ b/compiler/rustc_transmute/src/maybe_transmutable/query_context.rs
@@ -6,9 +6,6 @@ pub(crate) trait QueryContext {
     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;
 }
 
@@ -20,21 +17,21 @@ pub(crate) mod test {
 
     #[derive(Debug, Hash, Eq, PartialEq, Clone, Copy)]
     pub(crate) enum Def {
-        Visible,
-        Invisible,
+        HasSafetyInvariants,
+        NoSafetyInvariants,
     }
 
-    impl crate::layout::Def for Def {}
+    impl crate::layout::Def for Def {
+        fn has_safety_invariants(&self) -> bool {
+            self == &Self::HasSafetyInvariants
+        }
+    }
 
     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!()
         }
@@ -52,34 +49,6 @@ mod rustc {
 
         type Scope = Ty<'tcx>;
 
-        #[instrument(level = "debug", 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() {
-                self.parent(adt_def.did())
-            } 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: bool = self.visibility(def_id).is_accessible_from(parent, *self);
-
-            trace!(?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
index e49bebf571d..9c7abf1cbd6 100644
--- a/compiler/rustc_transmute/src/maybe_transmutable/tests.rs
+++ b/compiler/rustc_transmute/src/maybe_transmutable/tests.rs
@@ -3,6 +3,65 @@ use crate::maybe_transmutable::MaybeTransmutableQuery;
 use crate::{layout, Reason};
 use itertools::Itertools;
 
+mod safety {
+    use crate::Answer;
+
+    use super::*;
+
+    type Tree = layout::Tree<Def, !>;
+
+    const DST_HAS_SAFETY_INVARIANTS: Answer<!> =
+        Answer::No(crate::Reason::DstMayHaveSafetyInvariants);
+
+    fn is_transmutable(src: &Tree, dst: &Tree, assume_safety: bool) -> crate::Answer<!> {
+        let src = src.clone();
+        let dst = dst.clone();
+        // The only dimension of the transmutability analysis we want to test
+        // here is the safety analysis. To ensure this, we disable all other
+        // toggleable aspects of the transmutability analysis.
+        let assume = crate::Assume {
+            alignment: true,
+            lifetimes: true,
+            validity: true,
+            safety: assume_safety,
+        };
+        crate::maybe_transmutable::MaybeTransmutableQuery::new(src, dst, assume, UltraMinimal)
+            .answer()
+    }
+
+    #[test]
+    fn src_safe_dst_safe() {
+        let src = Tree::Def(Def::NoSafetyInvariants).then(Tree::u8());
+        let dst = Tree::Def(Def::NoSafetyInvariants).then(Tree::u8());
+        assert_eq!(is_transmutable(&src, &dst, false), Answer::Yes);
+        assert_eq!(is_transmutable(&src, &dst, true), Answer::Yes);
+    }
+
+    #[test]
+    fn src_safe_dst_unsafe() {
+        let src = Tree::Def(Def::NoSafetyInvariants).then(Tree::u8());
+        let dst = Tree::Def(Def::HasSafetyInvariants).then(Tree::u8());
+        assert_eq!(is_transmutable(&src, &dst, false), DST_HAS_SAFETY_INVARIANTS);
+        assert_eq!(is_transmutable(&src, &dst, true), Answer::Yes);
+    }
+
+    #[test]
+    fn src_unsafe_dst_safe() {
+        let src = Tree::Def(Def::HasSafetyInvariants).then(Tree::u8());
+        let dst = Tree::Def(Def::NoSafetyInvariants).then(Tree::u8());
+        assert_eq!(is_transmutable(&src, &dst, false), Answer::Yes);
+        assert_eq!(is_transmutable(&src, &dst, true), Answer::Yes);
+    }
+
+    #[test]
+    fn src_unsafe_dst_unsafe() {
+        let src = Tree::Def(Def::HasSafetyInvariants).then(Tree::u8());
+        let dst = Tree::Def(Def::HasSafetyInvariants).then(Tree::u8());
+        assert_eq!(is_transmutable(&src, &dst, false), DST_HAS_SAFETY_INVARIANTS);
+        assert_eq!(is_transmutable(&src, &dst, true), Answer::Yes);
+    }
+}
+
 mod bool {
     use crate::Answer;
 
@@ -10,11 +69,9 @@ mod bool {
 
     #[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, safety: false },
             UltraMinimal,
         )
@@ -27,7 +84,6 @@ mod bool {
         let answer = crate::maybe_transmutable::MaybeTransmutableQuery::new(
             layout::Dfa::<!>::bool(),
             layout::Dfa::<!>::bool(),
-            (),
             crate::Assume { alignment: false, lifetimes: false, validity: true, safety: false },
             UltraMinimal,
         )
@@ -71,7 +127,6 @@ mod bool {
                         MaybeTransmutableQuery::new(
                             src_layout.clone(),
                             dst_layout.clone(),
-                            (),
                             crate::Assume { validity: false, ..crate::Assume::default() },
                             UltraMinimal,
                         )
@@ -86,7 +141,6 @@ mod bool {
                         MaybeTransmutableQuery::new(
                             src_layout.clone(),
                             dst_layout.clone(),
-                            (),
                             crate::Assume { validity: true, ..crate::Assume::default() },
                             UltraMinimal,
                         )
@@ -101,7 +155,6 @@ mod bool {
                         MaybeTransmutableQuery::new(
                             src_layout.clone(),
                             dst_layout.clone(),
-                            (),
                             crate::Assume { validity: false, ..crate::Assume::default() },
                             UltraMinimal,
                         )