Auto merge of #110662 - bryangarza:safe-transmute-reference-types, r=compiler-errors

Safe Transmute: Enable handling references

This patch enables support for references in Safe Transmute, by generating nested obligations during trait selection. Specifically, when we call `confirm_transmutability_candidate(...)`, we now recursively traverse the `rustc_transmute::Answer` tree and create obligations for all the `Answer` variants, some of which include multiple nested `Answer`s.

32 files changed, 789 insertions, 206 deletions

diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs
index e01187bcd3c..a8a0e1ebfb4 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs
@@ -709,6 +709,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         scope: Ty<'tcx>,
         assume: rustc_transmute::Assume,
     ) -> Result<Certainty, NoSolution> {
+        use rustc_transmute::Answer;
         // FIXME(transmutability): This really should be returning nested goals for `Answer::If*`
         match rustc_transmute::TransmuteTypeEnv::new(self.infcx).is_transmutable(
             ObligationCause::dummy(),
@@ -716,11 +717,8 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             scope,
             assume,
         ) {
-            rustc_transmute::Answer::Yes => Ok(Certainty::Yes),
-            rustc_transmute::Answer::No(_)
-            | rustc_transmute::Answer::IfTransmutable { .. }
-            | rustc_transmute::Answer::IfAll(_)
-            | rustc_transmute::Answer::IfAny(_) => Err(NoSolution),
+            Answer::Yes => Ok(Certainty::Yes),
+            Answer::No(_) | Answer::If(_) => Err(NoSolution),
         }
     }
 
diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
index c4481b39e14..1bc4599377a 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
@@ -66,6 +66,11 @@ pub struct ImplCandidate<'tcx> {
     pub similarity: CandidateSimilarity,
 }
 
+enum GetSafeTransmuteErrorAndReason {
+    Silent,
+    Error { err_msg: String, safe_transmute_explanation: String },
+}
+
 pub trait InferCtxtExt<'tcx> {
     /// Given some node representing a fn-like thing in the HIR map,
     /// returns a span and `ArgKind` information that describes the
@@ -739,11 +744,17 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> {
                             == self.tcx.lang_items().transmute_trait()
                         {
                             // Recompute the safe transmute reason and use that for the error reporting
-                            self.get_safe_transmute_error_and_reason(
+                            match self.get_safe_transmute_error_and_reason(
                                 obligation.clone(),
                                 trait_ref,
                                 span,
-                            )
+                            ) {
+                                GetSafeTransmuteErrorAndReason::Silent => return,
+                                GetSafeTransmuteErrorAndReason::Error {
+                                    err_msg,
+                                    safe_transmute_explanation,
+                                } => (err_msg, Some(safe_transmute_explanation)),
+                            }
                         } else {
                             (err_msg, None)
                         };
@@ -1403,7 +1414,7 @@ trait InferCtxtPrivExt<'tcx> {
         obligation: PredicateObligation<'tcx>,
         trait_ref: ty::PolyTraitRef<'tcx>,
         span: Span,
-    ) -> (String, Option<String>);
+    ) -> GetSafeTransmuteErrorAndReason;
 
     fn add_tuple_trait_message(
         &self,
@@ -2850,7 +2861,9 @@ impl<'tcx> InferCtxtPrivExt<'tcx> for TypeErrCtxt<'_, 'tcx> {
         obligation: PredicateObligation<'tcx>,
         trait_ref: ty::PolyTraitRef<'tcx>,
         span: Span,
-    ) -> (String, Option<String>) {
+    ) -> GetSafeTransmuteErrorAndReason {
+        use rustc_transmute::Answer;
+
         // Erase regions because layout code doesn't particularly care about regions.
         let trait_ref = self.tcx.erase_regions(self.tcx.erase_late_bound_regions(trait_ref));
 
@@ -2863,19 +2876,20 @@ impl<'tcx> InferCtxtPrivExt<'tcx> for TypeErrCtxt<'_, 'tcx> {
             rustc_transmute::Assume::from_const(self.infcx.tcx, obligation.param_env, trait_ref.substs.const_at(3)) else {
                 span_bug!(span, "Unable to construct rustc_transmute::Assume where it was previously possible");
             };
+
         match rustc_transmute::TransmuteTypeEnv::new(self.infcx).is_transmutable(
             obligation.cause,
             src_and_dst,
             scope,
             assume,
         ) {
-            rustc_transmute::Answer::No(reason) => {
+            Answer::No(reason) => {
                 let dst = trait_ref.substs.type_at(0);
                 let src = trait_ref.substs.type_at(1);
-                let custom_err_msg = format!(
+                let err_msg = format!(
                     "`{src}` cannot be safely transmuted into `{dst}` in the defining scope of `{scope}`"
                 );
-                let reason_msg = match reason {
+                let safe_transmute_explanation = match reason {
                     rustc_transmute::Reason::SrcIsUnspecified => {
                         format!("`{src}` does not have a well-specified layout")
                     }
@@ -2891,19 +2905,39 @@ impl<'tcx> InferCtxtPrivExt<'tcx> for TypeErrCtxt<'_, 'tcx> {
                     rustc_transmute::Reason::DstIsPrivate => format!(
                         "`{dst}` is or contains a type or field that is not visible in that scope"
                     ),
-                    // FIXME(bryangarza): Include the number of bytes of src and dst
                     rustc_transmute::Reason::DstIsTooBig => {
                         format!("The size of `{src}` is smaller than the size of `{dst}`")
                     }
+                    rustc_transmute::Reason::DstHasStricterAlignment {
+                        src_min_align,
+                        dst_min_align,
+                    } => {
+                        format!(
+                            "The minimum alignment of `{src}` ({src_min_align}) should be greater than that of `{dst}` ({dst_min_align})"
+                        )
+                    }
+                    rustc_transmute::Reason::DstIsMoreUnique => {
+                        format!("`{src}` is a shared reference, but `{dst}` is a unique reference")
+                    }
+                    // Already reported by rustc
+                    rustc_transmute::Reason::TypeError => {
+                        return GetSafeTransmuteErrorAndReason::Silent;
+                    }
+                    rustc_transmute::Reason::SrcLayoutUnknown => {
+                        format!("`{src}` has an unknown layout")
+                    }
+                    rustc_transmute::Reason::DstLayoutUnknown => {
+                        format!("`{dst}` has an unknown layout")
+                    }
                 };
-                (custom_err_msg, Some(reason_msg))
+                GetSafeTransmuteErrorAndReason::Error { err_msg, safe_transmute_explanation }
             }
             // Should never get a Yes at this point! We already ran it before, and did not get a Yes.
-            rustc_transmute::Answer::Yes => span_bug!(
+            Answer::Yes => span_bug!(
                 span,
                 "Inconsistent rustc_transmute::is_transmutable(...) result, got Yes",
             ),
-            _ => span_bug!(span, "Unsupported rustc_transmute::Reason variant"),
+            other => span_bug!(span, "Unsupported rustc_transmute::Answer variant: `{other:?}`"),
         }
     }
 
diff --git a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
index 4e961c3ee73..7853af959ad 100644
--- a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
@@ -6,6 +6,7 @@
 //!
 //! [rustc dev guide]:
 //! https://rustc-dev-guide.rust-lang.org/traits/resolution.html#confirmation
+use rustc_ast::Mutability;
 use rustc_data_structures::stack::ensure_sufficient_stack;
 use rustc_hir::lang_items::LangItem;
 use rustc_infer::infer::LateBoundRegionConversionTime::HigherRankedType;
@@ -13,7 +14,7 @@ use rustc_infer::infer::{DefineOpaqueTypes, InferOk};
 use rustc_middle::traits::SelectionOutputTypeParameterMismatch;
 use rustc_middle::ty::{
     self, Binder, GenericParamDefKind, InternalSubsts, SubstsRef, ToPolyTraitRef, ToPredicate,
-    TraitRef, Ty, TyCtxt, TypeVisitableExt,
+    TraitPredicate, TraitRef, Ty, TyCtxt, TypeVisitableExt,
 };
 use rustc_session::config::TraitSolver;
 use rustc_span::def_id::DefId;
@@ -279,11 +280,60 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         ImplSourceBuiltinData { nested: obligations }
     }
 
+    #[instrument(level = "debug", skip(self))]
     fn confirm_transmutability_candidate(
         &mut self,
         obligation: &TraitObligation<'tcx>,
     ) -> Result<ImplSourceBuiltinData<PredicateObligation<'tcx>>, SelectionError<'tcx>> {
-        debug!(?obligation, "confirm_transmutability_candidate");
+        use rustc_transmute::{Answer, Condition};
+        #[instrument(level = "debug", skip(tcx, obligation, predicate))]
+        fn flatten_answer_tree<'tcx>(
+            tcx: TyCtxt<'tcx>,
+            obligation: &TraitObligation<'tcx>,
+            predicate: TraitPredicate<'tcx>,
+            cond: Condition<rustc_transmute::layout::rustc::Ref<'tcx>>,
+        ) -> Vec<PredicateObligation<'tcx>> {
+            match cond {
+                // FIXME(bryangarza): Add separate `IfAny` case, instead of treating as `IfAll`
+                // Not possible until the trait solver supports disjunctions of obligations
+                Condition::IfAll(conds) | Condition::IfAny(conds) => conds
+                    .into_iter()
+                    .flat_map(|cond| flatten_answer_tree(tcx, obligation, predicate, cond))
+                    .collect(),
+                Condition::IfTransmutable { src, dst } => {
+                    let trait_def_id = obligation.predicate.def_id();
+                    let scope = predicate.trait_ref.substs.type_at(2);
+                    let assume_const = predicate.trait_ref.substs.const_at(3);
+                    let make_obl = |from_ty, to_ty| {
+                        let trait_ref1 = ty::TraitRef::new(
+                            tcx,
+                            trait_def_id,
+                            [
+                                ty::GenericArg::from(to_ty),
+                                ty::GenericArg::from(from_ty),
+                                ty::GenericArg::from(scope),
+                                ty::GenericArg::from(assume_const),
+                            ],
+                        );
+                        Obligation::with_depth(
+                            tcx,
+                            obligation.cause.clone(),
+                            obligation.recursion_depth + 1,
+                            obligation.param_env,
+                            trait_ref1,
+                        )
+                    };
+
+                    // If Dst is mutable, check bidirectionally.
+                    // For example, transmuting bool -> u8 is OK as long as you can't update that u8
+                    // to be > 1, because you could later transmute the u8 back to a bool and get UB.
+                    match dst.mutability {
+                        Mutability::Not => vec![make_obl(src.ty, dst.ty)],
+                        Mutability::Mut => vec![make_obl(src.ty, dst.ty), make_obl(dst.ty, src.ty)],
+                    }
+                }
+            }
+        }
 
         // We erase regions here because transmutability calls layout queries,
         // which does not handle inference regions and doesn't particularly
@@ -301,21 +351,25 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             return Err(Unimplemented);
         };
 
+        let dst = predicate.trait_ref.substs.type_at(0);
+        let src = predicate.trait_ref.substs.type_at(1);
+        debug!(?src, ?dst);
         let mut transmute_env = rustc_transmute::TransmuteTypeEnv::new(self.infcx);
         let maybe_transmutable = transmute_env.is_transmutable(
             obligation.cause.clone(),
-            rustc_transmute::Types {
-                dst: predicate.trait_ref.substs.type_at(0),
-                src: predicate.trait_ref.substs.type_at(1),
-            },
+            rustc_transmute::Types { dst, src },
             predicate.trait_ref.substs.type_at(2),
             assume,
         );
 
-        match maybe_transmutable {
-            rustc_transmute::Answer::Yes => Ok(ImplSourceBuiltinData { nested: vec![] }),
-            _ => Err(Unimplemented),
-        }
+        let fully_flattened = match maybe_transmutable {
+            Answer::No(_) => Err(Unimplemented)?,
+            Answer::If(cond) => flatten_answer_tree(self.tcx(), obligation, predicate, cond),
+            Answer::Yes => vec![],
+        };
+
+        debug!(?fully_flattened);
+        Ok(ImplSourceBuiltinData { nested: fully_flattened })
     }
 
     /// This handles the case where an `auto trait Foo` impl is being used.
diff --git a/compiler/rustc_transmute/src/layout/mod.rs b/compiler/rustc_transmute/src/layout/mod.rs
index f8d05bc89d2..76d97e0e6e7 100644
--- a/compiler/rustc_transmute/src/layout/mod.rs
+++ b/compiler/rustc_transmute/src/layout/mod.rs
@@ -30,33 +30,49 @@ impl fmt::Debug for Byte {
 }
 
 pub(crate) trait Def: Debug + Hash + Eq + PartialEq + Copy + Clone {}
-pub trait Ref: Debug + Hash + Eq + PartialEq + Copy + Clone {}
+pub trait Ref: Debug + Hash + Eq + PartialEq + Copy + Clone {
+    fn min_align(&self) -> usize;
+
+    fn is_mutable(&self) -> bool;
+}
 
 impl Def for ! {}
-impl Ref for ! {}
+impl Ref for ! {
+    fn min_align(&self) -> usize {
+        unreachable!()
+    }
+    fn is_mutable(&self) -> bool {
+        unreachable!()
+    }
+}
 
 #[cfg(feature = "rustc")]
-pub(crate) mod rustc {
+pub mod rustc {
     use rustc_middle::mir::Mutability;
-    use rustc_middle::ty;
-    use rustc_middle::ty::Region;
-    use rustc_middle::ty::Ty;
+    use rustc_middle::ty::{self, 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,
+        pub lifetime: ty::Region<'tcx>,
+        pub ty: Ty<'tcx>,
+        pub mutability: Mutability,
+        pub align: usize,
     }
 
-    impl<'tcx> super::Ref for Ref<'tcx> {}
+    impl<'tcx> super::Ref for Ref<'tcx> {
+        fn min_align(&self) -> usize {
+            self.align
+        }
 
-    impl<'tcx> Ref<'tcx> {
-        pub fn min_align(&self) -> usize {
-            todo!()
+        fn is_mutable(&self) -> bool {
+            match self.mutability {
+                Mutability::Mut => true,
+                Mutability::Not => false,
+            }
         }
     }
+    impl<'tcx> Ref<'tcx> {}
 
     /// A visibility node in the layout.
     #[derive(Debug, Hash, Eq, PartialEq, Clone, Copy)]
diff --git a/compiler/rustc_transmute/src/layout/tree.rs b/compiler/rustc_transmute/src/layout/tree.rs
index a6d88b1342a..6b718be7b15 100644
--- a/compiler/rustc_transmute/src/layout/tree.rs
+++ b/compiler/rustc_transmute/src/layout/tree.rs
@@ -188,14 +188,14 @@ pub(crate) mod rustc {
         /// The layout of the type is unspecified.
         Unspecified,
         /// This error will be surfaced elsewhere by rustc, so don't surface it.
-        Unknown,
+        UnknownLayout,
         TypeError(ErrorGuaranteed),
     }
 
     impl<'tcx> From<LayoutError<'tcx>> for Err {
         fn from(err: LayoutError<'tcx>) -> Self {
             match err {
-                LayoutError::Unknown(..) => Self::Unknown,
+                LayoutError::Unknown(..) => Self::UnknownLayout,
                 err => unimplemented!("{:?}", err),
             }
         }
@@ -365,6 +365,17 @@ pub(crate) mod rustc {
                         }
                     }))
                 }
+
+                ty::Ref(lifetime, ty, mutability) => {
+                    let align = layout_of(tcx, *ty)?.align();
+                    Ok(Tree::Ref(Ref {
+                        lifetime: *lifetime,
+                        ty: *ty,
+                        mutability: *mutability,
+                        align,
+                    }))
+                }
+
                 _ => Err(Err::Unspecified),
             }
         }
diff --git a/compiler/rustc_transmute/src/lib.rs b/compiler/rustc_transmute/src/lib.rs
index 77c0526e3aa..34ad6bd8c69 100644
--- a/compiler/rustc_transmute/src/lib.rs
+++ b/compiler/rustc_transmute/src/lib.rs
@@ -8,7 +8,7 @@ extern crate tracing;
 
 pub(crate) use rustc_data_structures::fx::{FxIndexMap as Map, FxIndexSet as Set};
 
-pub(crate) mod layout;
+pub mod layout;
 pub(crate) mod maybe_transmutable;
 
 #[derive(Default)]
@@ -19,29 +19,29 @@ pub struct Assume {
     pub validity: bool,
 }
 
-/// The type encodes answers to the question: "Are these types transmutable?"
-#[derive(Debug, Hash, Eq, PartialEq, PartialOrd, Ord, Clone)]
-pub enum Answer<R>
-where
-    R: layout::Ref,
-{
-    /// `Src` is transmutable into `Dst`.
+/// Either we have an error, transmutation is allowed, or we have an optional
+/// Condition that must hold.
+#[derive(Debug, Hash, Eq, PartialEq, Clone)]
+pub enum Answer<R> {
     Yes,
-
-    /// `Src` is NOT transmutable into `Dst`.
     No(Reason),
+    If(Condition<R>),
+}
 
+/// A condition which must hold for safe transmutation to be possible.
+#[derive(Debug, Hash, Eq, PartialEq, Clone)]
+pub enum Condition<R> {
     /// `Src` is transmutable into `Dst`, if `src` is transmutable into `dst`.
     IfTransmutable { src: R, dst: R },
 
     /// `Src` is transmutable into `Dst`, if all of the enclosed requirements are met.
-    IfAll(Vec<Answer<R>>),
+    IfAll(Vec<Condition<R>>),
 
     /// `Src` is transmutable into `Dst` if any of the enclosed requirements are met.
-    IfAny(Vec<Answer<R>>),
+    IfAny(Vec<Condition<R>>),
 }
 
-/// Answers: Why wasn't the source type transmutable into the destination type?
+/// Answers "why wasn't the source type transmutable into the destination type?"
 #[derive(Debug, Hash, Eq, PartialEq, PartialOrd, Ord, Clone)]
 pub enum Reason {
     /// The layout of the source type is unspecified.
@@ -54,6 +54,16 @@ pub enum Reason {
     DstIsPrivate,
     /// `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.
+    DstHasStricterAlignment { src_min_align: usize, dst_min_align: usize },
+    /// Can't go from shared pointer to unique pointer
+    DstIsMoreUnique,
+    /// Encountered a type error
+    TypeError,
+    /// The layout of src is unknown
+    SrcLayoutUnknown,
+    /// The layout of dst is unknown
+    DstLayoutUnknown,
 }
 
 #[cfg(feature = "rustc")]
diff --git a/compiler/rustc_transmute/src/maybe_transmutable/mod.rs b/compiler/rustc_transmute/src/maybe_transmutable/mod.rs
index 2e2fb90e71c..b223a90f751 100644
--- a/compiler/rustc_transmute/src/maybe_transmutable/mod.rs
+++ b/compiler/rustc_transmute/src/maybe_transmutable/mod.rs
@@ -1,13 +1,13 @@
-use crate::Map;
-use crate::{Answer, Reason};
-
+pub(crate) mod query_context;
 #[cfg(test)]
 mod tests;
 
-mod query_context;
-use query_context::QueryContext;
+use crate::{
+    layout::{self, dfa, Byte, Dfa, Nfa, Ref, Tree, Uninhabited},
+    maybe_transmutable::query_context::QueryContext,
+    Answer, Condition, Map, Reason,
+};
 
-use crate::layout::{self, dfa, Byte, Dfa, Nfa, Tree, Uninhabited};
 pub(crate) struct MaybeTransmutableQuery<L, C>
 where
     C: QueryContext,
@@ -33,6 +33,7 @@ where
         Self { src, dst, scope, assume, context }
     }
 
+    // FIXME(bryangarza): Delete this when all usages are removed
     pub(crate) fn map_layouts<F, M>(
         self,
         f: F,
@@ -53,6 +54,7 @@ where
     }
 }
 
+// FIXME: Nix this cfg, so we can write unit tests independently of rustc
 #[cfg(feature = "rustc")]
 mod rustc {
     use super::*;
@@ -66,30 +68,26 @@ 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 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);
-                let dst = Tree::from_ty(dst, context);
-
-                match (src, dst) {
-                    // Answer `Yes` here, because 'unknown layout' and type errors will already
-                    // be reported by rustc. No need to spam the user with more errors.
-                    (Err(Err::TypeError(_)), _) => Err(Answer::Yes),
-                    (_, Err(Err::TypeError(_))) => Err(Answer::Yes),
-                    (Err(Err::Unknown), _) => Err(Answer::Yes),
-                    (_, Err(Err::Unknown)) => Err(Answer::Yes),
-                    (Err(Err::Unspecified), _) => Err(Answer::No(Reason::SrcIsUnspecified)),
-                    (_, Err(Err::Unspecified)) => Err(Answer::No(Reason::DstIsUnspecified)),
-                    (Ok(src), Ok(dst)) => Ok((src, dst)),
-                }
-            });
+            let Self { src, dst, scope, assume, context } = self;
+
+            // 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);
+            let dst = Tree::from_ty(dst, context);
 
-            match query_or_answer {
-                Ok(query) => query.answer(),
-                Err(answer) => answer,
+            match (src, dst) {
+                (Err(Err::TypeError(_)), _) | (_, Err(Err::TypeError(_))) => {
+                    Answer::No(Reason::TypeError)
+                }
+                (Err(Err::UnknownLayout), _) => Answer::No(Reason::SrcLayoutUnknown),
+                (_, Err(Err::UnknownLayout)) => Answer::No(Reason::DstLayoutUnknown),
+                (Err(Err::Unspecified), _) => Answer::No(Reason::SrcIsUnspecified),
+                (_, Err(Err::Unspecified)) => Answer::No(Reason::DstIsUnspecified),
+                (Ok(src), Ok(dst)) => {
+                    MaybeTransmutableQuery { src, dst, scope, assume, context }.answer()
+                }
             }
         }
     }
@@ -107,6 +105,7 @@ where
     #[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;
+        // FIXME(bryangarza): Refactor this code to get rid of `map_layouts`
         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);
@@ -155,6 +154,7 @@ 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> {
+        // FIXME(bryangarza): Refactor this code to get rid of `map_layouts`
         let query_or_answer = self
             .map_layouts(|src, dst, scope, context| Ok((Dfa::from_nfa(src), Dfa::from_nfa(dst))));
 
@@ -203,8 +203,29 @@ where
         if let Some(answer) = cache.get(&(src_state, dst_state)) {
             answer.clone()
         } else {
+            debug!(?src_state, ?dst_state);
+            debug!(src = ?self.src);
+            debug!(dst = ?self.dst);
+            debug!(
+                src_transitions_len = self.src.transitions.len(),
+                dst_transitions_len = self.dst.transitions.len()
+            );
             let answer = if dst_state == self.dst.accepting {
                 // truncation: `size_of(Src) >= size_of(Dst)`
+                //
+                // Why is truncation OK to do? Because even though the Src is bigger, all we care about
+                // is whether we have enough data for the Dst to be valid in accordance with what its
+                // type dictates.
+                // For example, in a u8 to `()` transmutation, we have enough data available from the u8
+                // to transmute it to a `()` (though in this case does `()` really need any data to
+                // begin with? It doesn't). Same thing with u8 to fieldless struct.
+                // Now then, why is something like u8 to bool not allowed? That is not because the bool
+                // is smaller in size, but rather because those 2 bits that we are re-interpreting from
+                // the u8 could introduce invalid states for the bool type.
+                //
+                // So, if it's possible to transmute to a smaller Dst by truncating, and we can guarantee
+                // that none of the actually-used data can introduce an invalid state for Dst's type, we
+                // are able to safely transmute, even with truncation.
                 Answer::Yes
             } else if src_state == self.src.accepting {
                 // extension: `size_of(Src) >= size_of(Dst)`
@@ -214,108 +235,201 @@ where
                     Answer::No(Reason::DstIsTooBig)
                 }
             } else {
-                let src_quantification = if self.assume.validity {
+                let src_quantifier = 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
+                    Quantifier::ThereExists
                 } 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
+                    // then there must exist at least one transition out of `dst_state` such that the transmute is viable...
+                    Quantifier::ForAll
+                };
+
+                let bytes_answer = src_quantifier.apply(
+                    // for each of the byte transitions out of the `src_state`...
+                    self.src.bytes_from(src_state).unwrap_or(&Map::default()).into_iter().map(
+                        |(&src_validity, &src_state_prime)| {
+                            // ...try to find a matching transition out of `dst_state`.
+                            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) =
+                                // otherwise, see if `dst_state` has any outgoing `Uninit` transitions
+                                // (any init byte is a valid uninit byte)
+                                self.dst.byte_from(dst_state, Byte::Uninit)
+                            {
+                                self.answer_memo(cache, src_state_prime, dst_state_prime)
+                            } else {
+                                // otherwise, we've exhausted our options.
+                                // the DFAs, from this point onwards, are bit-incompatible.
+                                Answer::No(Reason::DstIsBitIncompatible)
+                            }
+                        },
+                    ),
+                );
+
+                // The below early returns reflect how this code would behave:
+                //   if self.assume.validity {
+                //       or(bytes_answer, refs_answer)
+                //   } else {
+                //       and(bytes_answer, refs_answer)
+                //   }
+                // ...if `refs_answer` was computed lazily. The below early
+                // returns can be deleted without impacting the correctness of
+                // the algoritm; only its performance.
+                debug!(?bytes_answer);
+                match bytes_answer {
+                    Answer::No(_) if !self.assume.validity => return bytes_answer,
+                    Answer::Yes if self.assume.validity => return bytes_answer,
+                    _ => {}
                 };
 
-                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)
-                        }
-                    },
-                )
+                let refs_answer = src_quantifier.apply(
+                    // for each reference transition out of `src_state`...
+                    self.src.refs_from(src_state).unwrap_or(&Map::default()).into_iter().map(
+                        |(&src_ref, &src_state_prime)| {
+                            // ...there exists a reference transition out of `dst_state`...
+                            Quantifier::ThereExists.apply(
+                                self.dst
+                                    .refs_from(dst_state)
+                                    .unwrap_or(&Map::default())
+                                    .into_iter()
+                                    .map(|(&dst_ref, &dst_state_prime)| {
+                                        if !src_ref.is_mutable() && dst_ref.is_mutable() {
+                                            Answer::No(Reason::DstIsMoreUnique)
+                                        } else if !self.assume.alignment
+                                            && src_ref.min_align() < dst_ref.min_align()
+                                        {
+                                            Answer::No(Reason::DstHasStricterAlignment {
+                                                src_min_align: src_ref.min_align(),
+                                                dst_min_align: dst_ref.min_align(),
+                                            })
+                                        } else {
+                                            // ...such that `src` is transmutable into `dst`, if
+                                            // `src_ref` is transmutability into `dst_ref`.
+                                            and(
+                                                Answer::If(Condition::IfTransmutable {
+                                                    src: src_ref,
+                                                    dst: dst_ref,
+                                                }),
+                                                self.answer_memo(
+                                                    cache,
+                                                    src_state_prime,
+                                                    dst_state_prime,
+                                                ),
+                                            )
+                                        }
+                                    }),
+                            )
+                        },
+                    ),
+                );
+
+                if self.assume.validity {
+                    or(bytes_answer, refs_answer)
+                } else {
+                    and(bytes_answer, refs_answer)
+                }
             };
-            cache.insert((src_state, dst_state), answer.clone());
+            if let Some(..) = cache.insert((src_state, dst_state), answer.clone()) {
+                panic!("failed to correctly cache transmutability")
+            }
             answer
         }
     }
 }
 
-impl<R> Answer<R>
+fn and<R>(lhs: Answer<R>, rhs: Answer<R>) -> Answer<R>
 where
-    R: layout::Ref,
+    R: PartialEq,
 {
-    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]),
+    match (lhs, rhs) {
+        // If both are errors, then we should return the more specific one
+        (Answer::No(Reason::DstIsBitIncompatible), Answer::No(reason))
+        | (Answer::No(reason), Answer::No(_))
+        // If either is an error, return it
+        | (Answer::No(reason), _) | (_, Answer::No(reason)) => Answer::No(reason),
+        // If only one side has a condition, pass it along
+        | (Answer::Yes, other) | (other, Answer::Yes) => other,
+        // If both sides have IfAll conditions, merge them
+        (Answer::If(Condition::IfAll(mut lhs)), Answer::If(Condition::IfAll(ref mut rhs))) => {
+            lhs.append(rhs);
+            Answer::If(Condition::IfAll(lhs))
         }
-    }
-
-    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]),
+        // If only one side is an IfAll, add the other Condition to it
+        (Answer::If(cond), Answer::If(Condition::IfAll(mut conds)))
+        | (Answer::If(Condition::IfAll(mut conds)), Answer::If(cond)) => {
+            conds.push(cond);
+            Answer::If(Condition::IfAll(conds))
         }
+        // Otherwise, both lhs and rhs conditions can be combined in a parent IfAll
+        (Answer::If(lhs), Answer::If(rhs)) => Answer::If(Condition::IfAll(vec![lhs, rhs])),
     }
 }
 
-pub fn for_all<R, I, F>(iter: I, f: F) -> Answer<R>
+fn or<R>(lhs: Answer<R>, rhs: Answer<R>) -> Answer<R>
 where
-    R: layout::Ref,
-    I: IntoIterator,
-    F: FnMut(<I as IntoIterator>::Item) -> Answer<R>,
+    R: PartialEq,
 {
-    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
+    match (lhs, rhs) {
+        // If both are errors, then we should return the more specific one
+        (Answer::No(Reason::DstIsBitIncompatible), Answer::No(reason))
+        | (Answer::No(reason), Answer::No(_)) => Answer::No(reason),
+        // Otherwise, errors can be ignored for the rest of the pattern matching
+        (Answer::No(_), other) | (other, Answer::No(_)) => or(other, Answer::Yes),
+        // If only one side has a condition, pass it along
+        (Answer::Yes, other) | (other, Answer::Yes) => other,
+        // If both sides have IfAny conditions, merge them
+        (Answer::If(Condition::IfAny(mut lhs)), Answer::If(Condition::IfAny(ref mut rhs))) => {
+            lhs.append(rhs);
+            Answer::If(Condition::IfAny(lhs))
+        }
+        // If only one side is an IfAny, add the other Condition to it
+        (Answer::If(cond), Answer::If(Condition::IfAny(mut conds)))
+        | (Answer::If(Condition::IfAny(mut conds)), Answer::If(cond)) => {
+            conds.push(cond);
+            Answer::If(Condition::IfAny(conds))
+        }
+        // Otherwise, both lhs and rhs conditions can be combined in a parent IfAny
+        (Answer::If(lhs), Answer::If(rhs)) => Answer::If(Condition::IfAny(vec![lhs, rhs])),
+    }
 }
 
-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
+pub enum Quantifier {
+    ThereExists,
+    ForAll,
+}
+
+impl Quantifier {
+    pub fn apply<R, I>(&self, iter: I) -> Answer<R>
+    where
+        R: layout::Ref,
+        I: IntoIterator<Item = Answer<R>>,
+    {
+        use std::ops::ControlFlow::{Break, Continue};
+
+        let (init, try_fold_f): (_, fn(_, _) -> _) = match self {
+            Self::ThereExists => {
+                (Answer::No(Reason::DstIsBitIncompatible), |accum: Answer<R>, next| {
+                    match or(accum, next) {
+                        Answer::Yes => Break(Answer::Yes),
+                        maybe => Continue(maybe),
+                    }
+                })
+            }
+            Self::ForAll => (Answer::Yes, |accum: Answer<R>, next| {
+                let answer = and(accum, next);
+                match answer {
+                    Answer::No(_) => Break(answer),
+                    maybe => Continue(maybe),
+                }
+            }),
+        };
+
+        let (Continue(result) | Break(result)) = iter.into_iter().try_fold(init, try_fold_f);
+        result
+    }
 }
diff --git a/compiler/rustc_transmute/src/maybe_transmutable/tests.rs b/compiler/rustc_transmute/src/maybe_transmutable/tests.rs
index a8675f4ae37..e49bebf571d 100644
--- a/compiler/rustc_transmute/src/maybe_transmutable/tests.rs
+++ b/compiler/rustc_transmute/src/maybe_transmutable/tests.rs
@@ -1,9 +1,11 @@
 use super::query_context::test::{Def, UltraMinimal};
 use crate::maybe_transmutable::MaybeTransmutableQuery;
-use crate::{layout, Answer, Reason};
+use crate::{layout, Reason};
 use itertools::Itertools;
 
 mod bool {
+    use crate::Answer;
+
     use super::*;
 
     #[test]
diff --git a/tests/ui/transmutability/alignment/align-fail.rs b/tests/ui/transmutability/alignment/align-fail.rs
new file mode 100644
index 00000000000..7f6090a6e4d
--- /dev/null
+++ b/tests/ui/transmutability/alignment/align-fail.rs
@@ -0,0 +1,23 @@
+// check-fail
+#![feature(transmutability)]
+
+mod assert {
+    use std::mem::{Assume, BikeshedIntrinsicFrom};
+    pub struct Context;
+
+    pub fn is_maybe_transmutable<Src, Dst>()
+    where
+        Dst: BikeshedIntrinsicFrom<Src, Context, {
+            Assume {
+                alignment: false,
+                lifetimes: true,
+                safety: true,
+                validity: true,
+            }
+        }>
+    {}
+}
+
+fn main() {
+    assert::is_maybe_transmutable::<&'static [u8; 0], &'static [u16; 0]>(); //~ ERROR `&[u8; 0]` cannot be safely transmuted into `&[u16; 0]`
+}
diff --git a/tests/ui/transmutability/alignment/align-fail.stderr b/tests/ui/transmutability/alignment/align-fail.stderr
new file mode 100644
index 00000000000..59246fb1b03
--- /dev/null
+++ b/tests/ui/transmutability/alignment/align-fail.stderr
@@ -0,0 +1,30 @@
+error[E0277]: `&[u8; 0]` cannot be safely transmuted into `&[u16; 0]` in the defining scope of `assert::Context`
+  --> $DIR/align-fail.rs:22:55
+   |
+LL | ...tatic [u8; 0], &'static [u16; 0]>();
+   |                   ^^^^^^^^^^^^^^^^^ The minimum alignment of `&[u8; 0]` (1) should be greater than that of `&[u16; 0]` (2)
+   |
+note: required by a bound in `is_maybe_transmutable`
+  --> $DIR/align-fail.rs:10:14
+   |
+LL |       pub fn is_maybe_transmutable<Src, Dst>()
+   |              --------------------- required by a bound in this function
+LL |       where
+LL |           Dst: BikeshedIntrinsicFrom<Src, Context, {
+   |  ______________^
+LL | |             Assume {
+LL | |                 alignment: false,
+LL | |                 lifetimes: true,
+...  |
+LL | |             }
+LL | |         }>
+   | |__________^ required by this bound in `is_maybe_transmutable`
+help: consider removing the leading `&`-reference
+   |
+LL -     assert::is_maybe_transmutable::<&'static [u8; 0], &'static [u16; 0]>();
+LL +     assert::is_maybe_transmutable::<&'static [u8; 0], [u16; 0]>();
+   |
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0277`.
diff --git a/tests/ui/transmutability/alignment/align-pass.rs b/tests/ui/transmutability/alignment/align-pass.rs
new file mode 100644
index 00000000000..62dc672eacb
--- /dev/null
+++ b/tests/ui/transmutability/alignment/align-pass.rs
@@ -0,0 +1,23 @@
+// check-pass
+#![feature(transmutability)]
+
+mod assert {
+    use std::mem::{Assume, BikeshedIntrinsicFrom};
+    pub struct Context;
+
+    pub fn is_maybe_transmutable<Src, Dst>()
+    where
+        Dst: BikeshedIntrinsicFrom<Src, Context, {
+            Assume {
+                alignment: false,
+                lifetimes: false,
+                safety: true,
+                validity: false,
+            }
+        }>
+    {}
+}
+
+fn main() {
+    assert::is_maybe_transmutable::<&'static [u16; 0], &'static [u8; 0]>();
+}
diff --git a/tests/ui/transmutability/enums/repr/primitive_reprs_should_have_correct_length.stderr b/tests/ui/transmutability/enums/repr/primitive_reprs_should_have_correct_length.stderr
index 9877a6606a9..46cdaa92563 100644
--- a/tests/ui/transmutability/enums/repr/primitive_reprs_should_have_correct_length.stderr
+++ b/tests/ui/transmutability/enums/repr/primitive_reprs_should_have_correct_length.stderr
@@ -90,7 +90,7 @@ error[E0277]: `u8` cannot be safely transmuted into `V0i16` in the defining scop
   --> $DIR/primitive_reprs_should_have_correct_length.rs:72:44
    |
 LL |         assert::is_transmutable::<Smaller, Current, Context>();
-   |                                            ^^^^^^^ At least one value of `u8` isn't a bit-valid value of `V0i16`
+   |                                            ^^^^^^^ The size of `u8` is smaller than the size of `V0i16`
    |
 note: required by a bound in `is_transmutable`
   --> $DIR/primitive_reprs_should_have_correct_length.rs:12:14
@@ -134,7 +134,7 @@ error[E0277]: `u8` cannot be safely transmuted into `V0u16` in the defining scop
   --> $DIR/primitive_reprs_should_have_correct_length.rs:80:44
    |
 LL |         assert::is_transmutable::<Smaller, Current, Context>();
-   |                                            ^^^^^^^ At least one value of `u8` isn't a bit-valid value of `V0u16`
+   |                                            ^^^^^^^ The size of `u8` is smaller than the size of `V0u16`
    |
 note: required by a bound in `is_transmutable`
   --> $DIR/primitive_reprs_should_have_correct_length.rs:12:14
@@ -178,7 +178,7 @@ error[E0277]: `u16` cannot be safely transmuted into `V0i32` in the defining sco
   --> $DIR/primitive_reprs_should_have_correct_length.rs:96:44
    |
 LL |         assert::is_transmutable::<Smaller, Current, Context>();
-   |                                            ^^^^^^^ At least one value of `u16` isn't a bit-valid value of `V0i32`
+   |                                            ^^^^^^^ The size of `u16` is smaller than the size of `V0i32`
    |
 note: required by a bound in `is_transmutable`
   --> $DIR/primitive_reprs_should_have_correct_length.rs:12:14
@@ -222,7 +222,7 @@ error[E0277]: `u16` cannot be safely transmuted into `V0u32` in the defining sco
   --> $DIR/primitive_reprs_should_have_correct_length.rs:104:44
    |
 LL |         assert::is_transmutable::<Smaller, Current, Context>();
-   |                                            ^^^^^^^ At least one value of `u16` isn't a bit-valid value of `V0u32`
+   |                                            ^^^^^^^ The size of `u16` is smaller than the size of `V0u32`
    |
 note: required by a bound in `is_transmutable`
   --> $DIR/primitive_reprs_should_have_correct_length.rs:12:14
@@ -266,7 +266,7 @@ error[E0277]: `u32` cannot be safely transmuted into `V0i64` in the defining sco
   --> $DIR/primitive_reprs_should_have_correct_length.rs:120:44
    |
 LL |         assert::is_transmutable::<Smaller, Current, Context>();
-   |                                            ^^^^^^^ At least one value of `u32` isn't a bit-valid value of `V0i64`
+   |                                            ^^^^^^^ The size of `u32` is smaller than the size of `V0i64`
    |
 note: required by a bound in `is_transmutable`
   --> $DIR/primitive_reprs_should_have_correct_length.rs:12:14
@@ -310,7 +310,7 @@ error[E0277]: `u32` cannot be safely transmuted into `V0u64` in the defining sco
   --> $DIR/primitive_reprs_should_have_correct_length.rs:128:44
    |
 LL |         assert::is_transmutable::<Smaller, Current, Context>();
-   |                                            ^^^^^^^ At least one value of `u32` isn't a bit-valid value of `V0u64`
+   |                                            ^^^^^^^ The size of `u32` is smaller than the size of `V0u64`
    |
 note: required by a bound in `is_transmutable`
   --> $DIR/primitive_reprs_should_have_correct_length.rs:12:14
@@ -354,7 +354,7 @@ error[E0277]: `u8` cannot be safely transmuted into `V0isize` in the defining sc
   --> $DIR/primitive_reprs_should_have_correct_length.rs:144:44
    |
 LL |         assert::is_transmutable::<Smaller, Current, Context>();
-   |                                            ^^^^^^^ At least one value of `u8` isn't a bit-valid value of `V0isize`
+   |                                            ^^^^^^^ The size of `u8` is smaller than the size of `V0isize`
    |
 note: required by a bound in `is_transmutable`
   --> $DIR/primitive_reprs_should_have_correct_length.rs:12:14
@@ -398,7 +398,7 @@ error[E0277]: `u8` cannot be safely transmuted into `V0usize` in the defining sc
   --> $DIR/primitive_reprs_should_have_correct_length.rs:152:44
    |
 LL |         assert::is_transmutable::<Smaller, Current, Context>();
-   |                                            ^^^^^^^ At least one value of `u8` isn't a bit-valid value of `V0usize`
+   |                                            ^^^^^^^ The size of `u8` is smaller than the size of `V0usize`
    |
 note: required by a bound in `is_transmutable`
   --> $DIR/primitive_reprs_should_have_correct_length.rs:12:14
diff --git a/tests/ui/transmutability/malformed-program-gracefulness/unknown_src_field.rs b/tests/ui/transmutability/malformed-program-gracefulness/unknown_src_field.rs
index ebe34e13432..8d19cabc0f9 100644
--- a/tests/ui/transmutability/malformed-program-gracefulness/unknown_src_field.rs
+++ b/tests/ui/transmutability/malformed-program-gracefulness/unknown_src_field.rs
@@ -18,5 +18,5 @@ fn should_gracefully_handle_unknown_dst_field() {
     struct Context;
     #[repr(C)] struct Src;
     #[repr(C)] struct Dst(Missing); //~ cannot find type
-    assert::is_transmutable::<Src, Dst, Context>();
+    assert::is_transmutable::<Src, Dst, Context>(); //~ ERROR cannot be safely transmuted
 }
diff --git a/tests/ui/transmutability/malformed-program-gracefulness/unknown_src_field.stderr b/tests/ui/transmutability/malformed-program-gracefulness/unknown_src_field.stderr
index 475e6f429f3..c2df398b8ff 100644
--- a/tests/ui/transmutability/malformed-program-gracefulness/unknown_src_field.stderr
+++ b/tests/ui/transmutability/malformed-program-gracefulness/unknown_src_field.stderr
@@ -4,6 +4,22 @@ error[E0412]: cannot find type `Missing` in this scope
 LL |     #[repr(C)] struct Dst(Missing);
    |                           ^^^^^^^ not found in this scope
 
-error: aborting due to previous error
+error[E0277]: `Src` cannot be safely transmuted into `Dst` in the defining scope of `should_gracefully_handle_unknown_dst_field::Context`
+  --> $DIR/unknown_src_field.rs:21:36
+   |
+LL |     assert::is_transmutable::<Src, Dst, Context>();
+   |                                    ^^^ `Dst` has an unknown layout
+   |
+note: required by a bound in `is_transmutable`
+  --> $DIR/unknown_src_field.rs:13:14
+   |
+LL |     pub fn is_transmutable<Src, Dst, Context>()
+   |            --------------- required by a bound in this function
+LL |     where
+LL |         Dst: BikeshedIntrinsicFrom<Src, Context>
+   |              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `is_transmutable`
+
+error: aborting due to 2 previous errors
 
-For more information about this error, try `rustc --explain E0412`.
+Some errors have detailed explanations: E0277, E0412.
+For more information about an error, try `rustc --explain E0277`.
diff --git a/tests/ui/transmutability/primitives/bool-mut.rs b/tests/ui/transmutability/primitives/bool-mut.rs
new file mode 100644
index 00000000000..49dbe90e4b8
--- /dev/null
+++ b/tests/ui/transmutability/primitives/bool-mut.rs
@@ -0,0 +1,17 @@
+// check-fail
+//[next] compile-flags: -Ztrait-solver=next
+
+#![feature(transmutability)]
+mod assert {
+    use std::mem::{Assume, BikeshedIntrinsicFrom};
+    pub struct Context;
+
+    pub fn is_transmutable<Src, Dst>()
+    where
+        Dst: BikeshedIntrinsicFrom<Src, Context, { Assume::SAFETY }>
+    {}
+}
+
+fn main() {
+    assert::is_transmutable::<&'static mut bool, &'static mut u8>() //~ ERROR cannot be safely transmuted
+}
diff --git a/tests/ui/transmutability/primitives/bool-mut.stderr b/tests/ui/transmutability/primitives/bool-mut.stderr
new file mode 100644
index 00000000000..b36991e1c01
--- /dev/null
+++ b/tests/ui/transmutability/primitives/bool-mut.stderr
@@ -0,0 +1,18 @@
+error[E0277]: `u8` cannot be safely transmuted into `bool` in the defining scope of `assert::Context`
+  --> $DIR/bool-mut.rs:16:50
+   |
+LL |     assert::is_transmutable::<&'static mut bool, &'static mut u8>()
+   |                                                  ^^^^^^^^^^^^^^^ At least one value of `u8` isn't a bit-valid value of `bool`
+   |
+note: required by a bound in `is_transmutable`
+  --> $DIR/bool-mut.rs:11:14
+   |
+LL |     pub fn is_transmutable<Src, Dst>()
+   |            --------------- required by a bound in this function
+LL |     where
+LL |         Dst: BikeshedIntrinsicFrom<Src, Context, { Assume::SAFETY }>
+   |              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `is_transmutable`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0277`.
diff --git a/tests/ui/transmutability/primitives/bool.current.stderr b/tests/ui/transmutability/primitives/bool.current.stderr
index 47c8438a251..4b3eb6c517d 100644
--- a/tests/ui/transmutability/primitives/bool.current.stderr
+++ b/tests/ui/transmutability/primitives/bool.current.stderr
@@ -1,11 +1,11 @@
 error[E0277]: `u8` cannot be safely transmuted into `bool` in the defining scope of `assert::Context`
-  --> $DIR/bool.rs:24:35
+  --> $DIR/bool.rs:21:35
    |
 LL |     assert::is_transmutable::<u8, bool>();
    |                                   ^^^^ At least one value of `u8` isn't a bit-valid value of `bool`
    |
 note: required by a bound in `is_transmutable`
-  --> $DIR/bool.rs:14:14
+  --> $DIR/bool.rs:11:14
    |
 LL |     pub fn is_transmutable<Src, Dst>()
    |            --------------- required by a bound in this function
diff --git a/tests/ui/transmutability/primitives/bool.next.stderr b/tests/ui/transmutability/primitives/bool.next.stderr
index 47c8438a251..4b3eb6c517d 100644
--- a/tests/ui/transmutability/primitives/bool.next.stderr
+++ b/tests/ui/transmutability/primitives/bool.next.stderr
@@ -1,11 +1,11 @@
 error[E0277]: `u8` cannot be safely transmuted into `bool` in the defining scope of `assert::Context`
-  --> $DIR/bool.rs:24:35
+  --> $DIR/bool.rs:21:35
    |
 LL |     assert::is_transmutable::<u8, bool>();
    |                                   ^^^^ At least one value of `u8` isn't a bit-valid value of `bool`
    |
 note: required by a bound in `is_transmutable`
-  --> $DIR/bool.rs:14:14
+  --> $DIR/bool.rs:11:14
    |
 LL |     pub fn is_transmutable<Src, Dst>()
    |            --------------- required by a bound in this function
diff --git a/tests/ui/transmutability/primitives/bool.rs b/tests/ui/transmutability/primitives/bool.rs
index de77cfc78aa..654e7b47ede 100644
--- a/tests/ui/transmutability/primitives/bool.rs
+++ b/tests/ui/transmutability/primitives/bool.rs
@@ -1,10 +1,7 @@
 // revisions: current next
 //[next] compile-flags: -Ztrait-solver=next
 
-#![crate_type = "lib"]
 #![feature(transmutability)]
-#![allow(dead_code)]
-#![allow(incomplete_features)]
 mod assert {
     use std::mem::{Assume, BikeshedIntrinsicFrom};
     pub struct Context;
@@ -20,7 +17,7 @@ mod assert {
     {}
 }
 
-fn contrast_with_u8() {
+fn main() {
     assert::is_transmutable::<u8, bool>(); //~ ERROR cannot be safely transmuted
     assert::is_maybe_transmutable::<u8, bool>();
     assert::is_transmutable::<bool, u8>();
diff --git a/tests/ui/transmutability/references/recursive-wrapper-types-bit-compatible-mut.rs b/tests/ui/transmutability/references/recursive-wrapper-types-bit-compatible-mut.rs
new file mode 100644
index 00000000000..a6e2889d3f2
--- /dev/null
+++ b/tests/ui/transmutability/references/recursive-wrapper-types-bit-compatible-mut.rs
@@ -0,0 +1,25 @@
+// check-fail
+#![feature(transmutability)]
+
+mod assert {
+    use std::mem::{Assume, BikeshedIntrinsicFrom};
+    pub struct Context;
+
+    pub fn is_maybe_transmutable<Src, Dst>()
+    where
+        Dst: BikeshedIntrinsicFrom<Src, Context, {
+            Assume {
+                alignment: true,
+                lifetimes: false,
+                safety: true,
+                validity: false,
+            }
+        }>
+    {}
+}
+
+fn main() {
+    #[repr(C)] struct A(bool, &'static A);
+    #[repr(C)] struct B(u8, &'static B);
+    assert::is_maybe_transmutable::<&'static A, &'static mut B>(); //~ ERROR cannot be safely transmuted
+}
diff --git a/tests/ui/transmutability/references/recursive-wrapper-types-bit-compatible-mut.stderr b/tests/ui/transmutability/references/recursive-wrapper-types-bit-compatible-mut.stderr
new file mode 100644
index 00000000000..4b4d6ad0298
--- /dev/null
+++ b/tests/ui/transmutability/references/recursive-wrapper-types-bit-compatible-mut.stderr
@@ -0,0 +1,25 @@
+error[E0277]: `&A` cannot be safely transmuted into `&mut B` in the defining scope of `assert::Context`
+  --> $DIR/recursive-wrapper-types-bit-compatible-mut.rs:24:49
+   |
+LL |     assert::is_maybe_transmutable::<&'static A, &'static mut B>();
+   |                                                 ^^^^^^^^^^^^^^ `&A` is a shared reference, but `&mut B` is a unique reference
+   |
+note: required by a bound in `is_maybe_transmutable`
+  --> $DIR/recursive-wrapper-types-bit-compatible-mut.rs:10:14
+   |
+LL |       pub fn is_maybe_transmutable<Src, Dst>()
+   |              --------------------- required by a bound in this function
+LL |       where
+LL |           Dst: BikeshedIntrinsicFrom<Src, Context, {
+   |  ______________^
+LL | |             Assume {
+LL | |                 alignment: true,
+LL | |                 lifetimes: false,
+...  |
+LL | |             }
+LL | |         }>
+   | |__________^ required by this bound in `is_maybe_transmutable`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0277`.
diff --git a/tests/ui/transmutability/references/recursive-wrapper-types-bit-compatible.rs b/tests/ui/transmutability/references/recursive-wrapper-types-bit-compatible.rs
new file mode 100644
index 00000000000..3ea80173afa
--- /dev/null
+++ b/tests/ui/transmutability/references/recursive-wrapper-types-bit-compatible.rs
@@ -0,0 +1,26 @@
+// check-fail
+// FIXME(bryangarza): Change to check-pass when coinduction is supported for BikeshedIntrinsicFrom
+#![feature(transmutability)]
+
+mod assert {
+    use std::mem::{Assume, BikeshedIntrinsicFrom};
+    pub struct Context;
+
+    pub fn is_maybe_transmutable<Src, Dst>()
+    where
+        Dst: BikeshedIntrinsicFrom<Src, Context, {
+            Assume {
+                alignment: true,
+                lifetimes: false,
+                safety: true,
+                validity: false,
+            }
+        }>
+    {}
+}
+
+fn main() {
+    #[repr(C)] struct A(bool, &'static A);
+    #[repr(C)] struct B(u8, &'static B);
+    assert::is_maybe_transmutable::<&'static A, &'static B>(); //~ ERROR overflow evaluating the requirement
+}
diff --git a/tests/ui/transmutability/references/recursive-wrapper-types-bit-compatible.stderr b/tests/ui/transmutability/references/recursive-wrapper-types-bit-compatible.stderr
new file mode 100644
index 00000000000..fae332e6af9
--- /dev/null
+++ b/tests/ui/transmutability/references/recursive-wrapper-types-bit-compatible.stderr
@@ -0,0 +1,25 @@
+error[E0275]: overflow evaluating the requirement `B: BikeshedIntrinsicFrom<A, assert::Context, Assume { alignment: true, lifetimes: false, safety: true, validity: false }>`
+  --> $DIR/recursive-wrapper-types-bit-compatible.rs:25:5
+   |
+LL |     assert::is_maybe_transmutable::<&'static A, &'static B>();
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+   |
+note: required by a bound in `is_maybe_transmutable`
+  --> $DIR/recursive-wrapper-types-bit-compatible.rs:11:14
+   |
+LL |       pub fn is_maybe_transmutable<Src, Dst>()
+   |              --------------------- required by a bound in this function
+LL |       where
+LL |           Dst: BikeshedIntrinsicFrom<Src, Context, {
+   |  ______________^
+LL | |             Assume {
+LL | |                 alignment: true,
+LL | |                 lifetimes: false,
+...  |
+LL | |             }
+LL | |         }>
+   | |__________^ required by this bound in `is_maybe_transmutable`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0275`.
diff --git a/tests/ui/transmutability/references/recursive-wrapper-types-bit-incompatible.rs b/tests/ui/transmutability/references/recursive-wrapper-types-bit-incompatible.rs
new file mode 100644
index 00000000000..e8582d2fd02
--- /dev/null
+++ b/tests/ui/transmutability/references/recursive-wrapper-types-bit-incompatible.rs
@@ -0,0 +1,25 @@
+// check-fail
+#![feature(transmutability)]
+
+mod assert {
+    use std::mem::{Assume, BikeshedIntrinsicFrom};
+    pub struct Context;
+
+    pub fn is_maybe_transmutable<Src, Dst>()
+    where
+        Dst: BikeshedIntrinsicFrom<Src, Context, {
+            Assume {
+                alignment: true,
+                lifetimes: false,
+                safety: true,
+                validity: false,
+            }
+        }>
+    {}
+}
+
+fn main() {
+    #[repr(C)] struct A(bool, &'static A);
+    #[repr(C)] struct B(u8, &'static B);
+    assert::is_maybe_transmutable::<&'static B, &'static A>(); //~ ERROR cannot be safely transmuted
+}
diff --git a/tests/ui/transmutability/references/recursive-wrapper-types-bit-incompatible.stderr b/tests/ui/transmutability/references/recursive-wrapper-types-bit-incompatible.stderr
new file mode 100644
index 00000000000..ecfe4865962
--- /dev/null
+++ b/tests/ui/transmutability/references/recursive-wrapper-types-bit-incompatible.stderr
@@ -0,0 +1,25 @@
+error[E0277]: `B` cannot be safely transmuted into `A` in the defining scope of `assert::Context`
+  --> $DIR/recursive-wrapper-types-bit-incompatible.rs:24:49
+   |
+LL |     assert::is_maybe_transmutable::<&'static B, &'static A>();
+   |                                                 ^^^^^^^^^^ At least one value of `B` isn't a bit-valid value of `A`
+   |
+note: required by a bound in `is_maybe_transmutable`
+  --> $DIR/recursive-wrapper-types-bit-incompatible.rs:10:14
+   |
+LL |       pub fn is_maybe_transmutable<Src, Dst>()
+   |              --------------------- required by a bound in this function
+LL |       where
+LL |           Dst: BikeshedIntrinsicFrom<Src, Context, {
+   |  ______________^
+LL | |             Assume {
+LL | |                 alignment: true,
+LL | |                 lifetimes: false,
+...  |
+LL | |             }
+LL | |         }>
+   | |__________^ required by this bound in `is_maybe_transmutable`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0277`.
diff --git a/tests/ui/transmutability/references/recursive-wrapper-types.rs b/tests/ui/transmutability/references/recursive-wrapper-types.rs
new file mode 100644
index 00000000000..59d1ad84a5d
--- /dev/null
+++ b/tests/ui/transmutability/references/recursive-wrapper-types.rs
@@ -0,0 +1,27 @@
+// check-fail
+// FIXME(bryangarza): Change to check-pass when coinduction is supported for BikeshedIntrinsicFrom
+#![feature(transmutability)]
+
+mod assert {
+    use std::mem::{Assume, BikeshedIntrinsicFrom};
+    pub struct Context;
+
+    pub fn is_maybe_transmutable<Src, Dst>()
+    where
+        Dst: BikeshedIntrinsicFrom<Src, Context, {
+            Assume {
+                alignment: true,
+                lifetimes: false,
+                safety: true,
+                validity: false,
+            }
+        }>
+    {}
+}
+
+fn main() {
+    #[repr(C)] struct A(&'static B);
+    #[repr(C)] struct B(&'static A);
+    assert::is_maybe_transmutable::<&'static A, &'static B>(); //~ overflow evaluating the requirement
+    assert::is_maybe_transmutable::<&'static B, &'static A>();
+}
diff --git a/tests/ui/transmutability/references.next.stderr b/tests/ui/transmutability/references/recursive-wrapper-types.stderr
index 819c9b92bc8..35a60c22643 100644
--- a/tests/ui/transmutability/references.next.stderr
+++ b/tests/ui/transmutability/references/recursive-wrapper-types.stderr
@@ -1,11 +1,11 @@
-error[E0277]: `&Unit` cannot be safely transmuted into `&Unit` in the defining scope of `assert::Context`
-  --> $DIR/references.rs:29:52
+error[E0275]: overflow evaluating the requirement `A: BikeshedIntrinsicFrom<B, assert::Context, Assume { alignment: true, lifetimes: false, safety: true, validity: false }>`
+  --> $DIR/recursive-wrapper-types.rs:25:5
    |
-LL |     assert::is_maybe_transmutable::<&'static Unit, &'static Unit>();
-   |                                                    ^^^^^^^^^^^^^ `&Unit` does not have a well-specified layout
+LL |     assert::is_maybe_transmutable::<&'static A, &'static B>();
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
 note: required by a bound in `is_maybe_transmutable`
-  --> $DIR/references.rs:16:14
+  --> $DIR/recursive-wrapper-types.rs:11:14
    |
 LL |       pub fn is_maybe_transmutable<Src, Dst>()
    |              --------------------- required by a bound in this function
@@ -14,7 +14,7 @@ LL |           Dst: BikeshedIntrinsicFrom<Src, Context, {
    |  ______________^
 LL | |             Assume {
 LL | |                 alignment: true,
-LL | |                 lifetimes: true,
+LL | |                 lifetimes: false,
 ...  |
 LL | |             }
 LL | |         }>
@@ -22,4 +22,4 @@ LL | |         }>
 
 error: aborting due to previous error
 
-For more information about this error, try `rustc --explain E0277`.
+For more information about this error, try `rustc --explain E0275`.
diff --git a/tests/ui/transmutability/references/u8-to-unit.rs b/tests/ui/transmutability/references/u8-to-unit.rs
new file mode 100644
index 00000000000..8b37492bd6b
--- /dev/null
+++ b/tests/ui/transmutability/references/u8-to-unit.rs
@@ -0,0 +1,24 @@
+// check-pass
+#![feature(transmutability)]
+
+mod assert {
+    use std::mem::{Assume, BikeshedIntrinsicFrom};
+    pub struct Context;
+
+    pub fn is_maybe_transmutable<Src, Dst>()
+    where
+        Dst: BikeshedIntrinsicFrom<Src, Context, {
+            Assume {
+                alignment: false,
+                lifetimes: true,
+                safety: true,
+                validity: false,
+            }
+        }>
+    {}
+}
+
+fn main() {
+    #[repr(C)] struct Unit;
+    assert::is_maybe_transmutable::<&'static u8, &'static Unit>();
+}
diff --git a/tests/ui/transmutability/references.rs b/tests/ui/transmutability/references/unit-to-itself.rs
index 8c2b25ebba1..04a7e16d7cc 100644
--- a/tests/ui/transmutability/references.rs
+++ b/tests/ui/transmutability/references/unit-to-itself.rs
@@ -1,11 +1,5 @@
-// revisions: current next
-//[next] compile-flags: -Ztrait-solver=next
-
-//! Transmutations involving references are not yet supported.
-
-#![crate_type = "lib"]
+// check-pass
 #![feature(transmutability)]
-#![allow(dead_code, incomplete_features, non_camel_case_types)]
 
 mod assert {
     use std::mem::{Assume, BikeshedIntrinsicFrom};
@@ -16,15 +10,15 @@ mod assert {
         Dst: BikeshedIntrinsicFrom<Src, Context, {
             Assume {
                 alignment: true,
-                lifetimes: true,
+                lifetimes: false,
                 safety: true,
-                validity: true,
+                validity: false,
             }
         }>
     {}
 }
 
-fn not_yet_implemented() {
+fn main() {
     #[repr(C)] struct Unit;
-    assert::is_maybe_transmutable::<&'static Unit, &'static Unit>(); //~ ERROR cannot be safely transmuted
+    assert::is_maybe_transmutable::<&'static Unit, &'static Unit>();
 }
diff --git a/tests/ui/transmutability/references/unit-to-u8.rs b/tests/ui/transmutability/references/unit-to-u8.rs
new file mode 100644
index 00000000000..eff516e9a96
--- /dev/null
+++ b/tests/ui/transmutability/references/unit-to-u8.rs
@@ -0,0 +1,24 @@
+// check-fail
+#![feature(transmutability)]
+
+mod assert {
+    use std::mem::{Assume, BikeshedIntrinsicFrom};
+    pub struct Context;
+
+    pub fn is_maybe_transmutable<Src, Dst>()
+    where
+        Dst: BikeshedIntrinsicFrom<Src, Context, {
+            Assume {
+                alignment: true,
+                lifetimes: true,
+                safety: true,
+                validity: false,
+            }
+        }>
+    {}
+}
+
+fn main() {
+    #[repr(C)] struct Unit;
+    assert::is_maybe_transmutable::<&'static Unit, &'static u8>(); //~ ERROR cannot be safely transmuted
+}
diff --git a/tests/ui/transmutability/references.current.stderr b/tests/ui/transmutability/references/unit-to-u8.stderr
index 819c9b92bc8..f2b72357f79 100644
--- a/tests/ui/transmutability/references.current.stderr
+++ b/tests/ui/transmutability/references/unit-to-u8.stderr
@@ -1,11 +1,11 @@
-error[E0277]: `&Unit` cannot be safely transmuted into `&Unit` in the defining scope of `assert::Context`
-  --> $DIR/references.rs:29:52
+error[E0277]: `Unit` cannot be safely transmuted into `u8` in the defining scope of `assert::Context`
+  --> $DIR/unit-to-u8.rs:23:52
    |
-LL |     assert::is_maybe_transmutable::<&'static Unit, &'static Unit>();
-   |                                                    ^^^^^^^^^^^^^ `&Unit` does not have a well-specified layout
+LL |     assert::is_maybe_transmutable::<&'static Unit, &'static u8>();
+   |                                                    ^^^^^^^^^^^ The size of `Unit` is smaller than the size of `u8`
    |
 note: required by a bound in `is_maybe_transmutable`
-  --> $DIR/references.rs:16:14
+  --> $DIR/unit-to-u8.rs:10:14
    |
 LL |       pub fn is_maybe_transmutable<Src, Dst>()
    |              --------------------- required by a bound in this function
diff --git a/tests/ui/transmutability/region-infer.stderr b/tests/ui/transmutability/region-infer.stderr
index d6b65e9e4a0..307d0dfe50d 100644
--- a/tests/ui/transmutability/region-infer.stderr
+++ b/tests/ui/transmutability/region-infer.stderr
@@ -2,7 +2,7 @@ error[E0277]: `()` cannot be safely transmuted into `W<'_>` in the defining scop
   --> $DIR/region-infer.rs:20:5
    |
 LL |     test();
-   |     ^^^^ `W<'_>` does not have a well-specified layout
+   |     ^^^^ The size of `()` is smaller than the size of `W<'_>`
    |
 note: required by a bound in `test`
   --> $DIR/region-infer.rs:11:12