transmutability: Support char, NonZeroXxx

Note that `NonZero` support is not wired up, as the author encountered
bugs while attempting this. A future commit will wire up `NonZero`
support.

4 files changed, 213 insertions, 46 deletions

diff --git a/compiler/rustc_transmute/src/layout/mod.rs b/compiler/rustc_transmute/src/layout/mod.rs
index d555ea702a9..4d5f630ae22 100644
--- a/compiler/rustc_transmute/src/layout/mod.rs
+++ b/compiler/rustc_transmute/src/layout/mod.rs
@@ -65,7 +65,12 @@ impl fmt::Debug for Byte {
     }
 }
 
-#[cfg(test)]
+impl From<RangeInclusive<u8>> for Byte {
+    fn from(src: RangeInclusive<u8>) -> Self {
+        Self::new(src)
+    }
+}
+
 impl From<u8> for Byte {
     fn from(src: u8) -> Self {
         Self::from_val(src)
diff --git a/compiler/rustc_transmute/src/layout/tree.rs b/compiler/rustc_transmute/src/layout/tree.rs
index 6a09be18ef9..7cf712ce9e9 100644
--- a/compiler/rustc_transmute/src/layout/tree.rs
+++ b/compiler/rustc_transmute/src/layout/tree.rs
@@ -1,4 +1,4 @@
-use std::ops::ControlFlow;
+use std::ops::{ControlFlow, RangeInclusive};
 
 use super::{Byte, Def, Ref};
 
@@ -32,6 +32,22 @@ where
     Byte(Byte),
 }
 
+#[derive(Debug, Copy, Clone, Eq, PartialEq)]
+pub(crate) enum Endian {
+    Little,
+    Big,
+}
+
+#[cfg(feature = "rustc")]
+impl From<rustc_abi::Endian> for Endian {
+    fn from(order: rustc_abi::Endian) -> Endian {
+        match order {
+            rustc_abi::Endian::Little => Endian::Little,
+            rustc_abi::Endian::Big => Endian::Big,
+        }
+    }
+}
+
 impl<D, R> Tree<D, R>
 where
     D: Def,
@@ -59,22 +75,60 @@ where
 
     /// A `Tree` representing the layout of `bool`.
     pub(crate) fn bool() -> Self {
-        Self::Byte(Byte::new(0x00..=0x01))
+        Self::byte(0x00..=0x01)
     }
 
     /// A `Tree` whose layout matches that of a `u8`.
     pub(crate) fn u8() -> Self {
-        Self::Byte(Byte::new(0x00..=0xFF))
+        Self::byte(0x00..=0xFF)
+    }
+
+    /// A `Tree` whose layout matches that of a `char`.
+    pub(crate) fn char(order: Endian) -> Self {
+        // `char`s can be in the following ranges:
+        // - [0, 0xD7FF]
+        // - [0xE000, 10FFFF]
+        //
+        // All other `char` values are illegal. We can thus represent a `char`
+        // as a union of three possible layouts:
+        // - 00 00 [00, D7] XX
+        // - 00 00 [E0, FF] XX
+        // - 00 [01, 10] XX XX
+
+        const _0: RangeInclusive<u8> = 0..=0;
+        const BYTE: RangeInclusive<u8> = 0x00..=0xFF;
+        let x = Self::from_big_endian(order, [_0, _0, 0x00..=0xD7, BYTE]);
+        let y = Self::from_big_endian(order, [_0, _0, 0xE0..=0xFF, BYTE]);
+        let z = Self::from_big_endian(order, [_0, 0x01..=0x10, BYTE, BYTE]);
+        Self::alt([x, y, z])
     }
 
-    /// A `Tree` whose layout accepts exactly the given bit pattern.
-    pub(crate) fn from_bits(bits: u8) -> Self {
-        Self::Byte(Byte::from_val(bits))
+    /// A `Tree` whose layout matches `std::num::NonZeroXxx`.
+    #[allow(dead_code)]
+    pub(crate) fn nonzero(width_in_bytes: u64) -> Self {
+        const BYTE: RangeInclusive<u8> = 0x00..=0xFF;
+        const NONZERO: RangeInclusive<u8> = 0x01..=0xFF;
+
+        (0..width_in_bytes)
+            .map(|nz_idx| {
+                (0..width_in_bytes)
+                    .map(|pos| Self::byte(if pos == nz_idx { NONZERO } else { BYTE }))
+                    .fold(Self::unit(), Self::then)
+            })
+            .fold(Self::uninhabited(), Self::or)
+    }
+
+    pub(crate) fn bytes<const N: usize, B: Into<Byte>>(bytes: [B; N]) -> Self {
+        Self::seq(bytes.map(B::into).map(Self::Byte))
+    }
+
+    pub(crate) fn byte(byte: impl Into<Byte>) -> Self {
+        Self::Byte(byte.into())
     }
 
     /// A `Tree` whose layout is a number of the given width.
-    pub(crate) fn number(width_in_bytes: usize) -> Self {
-        Self::Seq(vec![Self::u8(); width_in_bytes])
+    pub(crate) fn number(width_in_bytes: u64) -> Self {
+        Self::Seq(vec![Self::u8(); width_in_bytes.try_into().unwrap()])
     }
 
     /// A `Tree` whose layout is entirely padding of the given width.
@@ -125,13 +179,35 @@ where
             Self::Byte(..) | Self::Ref(..) | Self::Def(..) => true,
         }
     }
-}
 
-impl<D, R> Tree<D, R>
-where
-    D: Def,
-    R: Ref,
-{
+    /// Produces a `Tree` which represents a sequence of bytes stored in
+    /// `order`.
+    ///
+    /// `bytes` is taken to be in big-endian byte order, and its order will be
+    /// swapped if `order == Endian::Little`.
+    pub(crate) fn from_big_endian<const N: usize, B: Into<Byte>>(
+        order: Endian,
+        mut bytes: [B; N],
+    ) -> Self {
+        if order == Endian::Little {
+            (&mut bytes[..]).reverse();
+        }
+
+        Self::bytes(bytes)
+    }
+
+    /// Produces a `Tree` where each of the trees in `trees` are sequenced one
+    /// after another.
+    pub(crate) fn seq<const N: usize>(trees: [Tree<D, R>; N]) -> Self {
+        trees.into_iter().fold(Tree::unit(), Self::then)
+    }
+
+    /// Produces a `Tree` where each of the trees in `trees` are accepted as
+    /// alternative layouts.
+    pub(crate) fn alt<const N: usize>(trees: [Tree<D, R>; N]) -> Self {
+        trees.into_iter().fold(Tree::uninhabited(), Self::or)
+    }
+
     /// Produces a new `Tree` where `other` is sequenced after `self`.
     pub(crate) fn then(self, other: Self) -> Self {
         match (self, other) {
@@ -222,17 +298,17 @@ pub(crate) mod rustc {
 
                 ty::Float(nty) => {
                     let width = nty.bit_width() / 8;
-                    Ok(Self::number(width as _))
+                    Ok(Self::number(width.try_into().unwrap()))
                 }
 
                 ty::Int(nty) => {
                     let width = nty.normalize(pointer_size.bits() as _).bit_width().unwrap() / 8;
-                    Ok(Self::number(width as _))
+                    Ok(Self::number(width.try_into().unwrap()))
                 }
 
                 ty::Uint(nty) => {
                     let width = nty.normalize(pointer_size.bits() as _).bit_width().unwrap() / 8;
-                    Ok(Self::number(width as _))
+                    Ok(Self::number(width.try_into().unwrap()))
                 }
 
                 ty::Tuple(members) => Self::from_tuple((ty, layout), members, cx),
@@ -249,11 +325,33 @@ pub(crate) mod rustc {
                         .fold(Tree::unit(), |tree, elt| tree.then(elt)))
                 }
 
-                ty::Adt(adt_def, _args_ref) if !ty.is_box() => match adt_def.adt_kind() {
-                    AdtKind::Struct => Self::from_struct((ty, layout), *adt_def, cx),
-                    AdtKind::Enum => Self::from_enum((ty, layout), *adt_def, cx),
-                    AdtKind::Union => Self::from_union((ty, layout), *adt_def, cx),
-                },
+                ty::Adt(adt_def, _args_ref) if !ty.is_box() => {
+                    let (lo, hi) = cx.tcx().layout_scalar_valid_range(adt_def.did());
+
+                    use core::ops::Bound::*;
+                    let is_transparent = adt_def.repr().transparent();
+                    match (adt_def.adt_kind(), lo, hi) {
+                        (AdtKind::Struct, Unbounded, Unbounded) => {
+                            Self::from_struct((ty, layout), *adt_def, cx)
+                        }
+                        (AdtKind::Struct, Included(1), Included(_hi)) if is_transparent => {
+                            // FIXME(@joshlf): Support `NonZero` types:
+                            // - Check to make sure that the first field is
+                            //   numerical
+                            // - Check to make sure that the upper bound is the
+                            //   maximum value for the field's type
+                            // - Construct `Self::nonzero`
+                            Err(Err::NotYetSupported)
+                        }
+                        (AdtKind::Enum, Unbounded, Unbounded) => {
+                            Self::from_enum((ty, layout), *adt_def, cx)
+                        }
+                        (AdtKind::Union, Unbounded, Unbounded) => {
+                            Self::from_union((ty, layout), *adt_def, cx)
+                        }
+                        _ => Err(Err::NotYetSupported),
+                    }
+                }
 
                 ty::Ref(lifetime, ty, mutability) => {
                     let layout = layout_of(cx, *ty)?;
@@ -268,6 +366,8 @@ pub(crate) mod rustc {
                     }))
                 }
 
+                ty::Char => Ok(Self::char(cx.tcx().data_layout.endian.into())),
+
                 _ => Err(Err::NotYetSupported),
             }
         }
@@ -450,7 +550,7 @@ pub(crate) mod rustc {
                     &bytes[bytes.len() - size.bytes_usize()..]
                 }
             };
-            Self::Seq(bytes.iter().map(|&b| Self::from_bits(b)).collect())
+            Self::Seq(bytes.iter().map(|&b| Self::byte(b)).collect())
         }
 
         /// Constructs a `Tree` from a union.
diff --git a/compiler/rustc_transmute/src/layout/tree/tests.rs b/compiler/rustc_transmute/src/layout/tree/tests.rs
index 44f50a25c93..8c3dbbe37ab 100644
--- a/compiler/rustc_transmute/src/layout/tree/tests.rs
+++ b/compiler/rustc_transmute/src/layout/tree/tests.rs
@@ -20,23 +20,18 @@ mod prune {
 
         #[test]
         fn seq_1() {
-            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)
-            );
+            let layout: Tree<Def, !> = Tree::def(Def::NoSafetyInvariants).then(Tree::byte(0x00));
+            assert_eq!(layout.prune(&|d| matches!(d, Def::HasSafetyInvariants)), Tree::byte(0x00));
         }
 
         #[test]
         fn seq_2() {
-            let layout: Tree<Def, !> = Tree::from_bits(0x00)
-                .then(Tree::def(Def::NoSafetyInvariants))
-                .then(Tree::from_bits(0x01));
+            let layout: Tree<Def, !> =
+                Tree::byte(0x00).then(Tree::def(Def::NoSafetyInvariants)).then(Tree::byte(0x01));
 
             assert_eq!(
                 layout.prune(&|d| matches!(d, Def::HasSafetyInvariants)),
-                Tree::from_bits(0x00).then(Tree::from_bits(0x01))
+                Tree::byte(0x00).then(Tree::byte(0x01))
             );
         }
     }
@@ -66,7 +61,7 @@ mod prune {
         #[test]
         fn invisible_def_in_seq_len_3() {
             let layout: Tree<Def, !> = Tree::def(Def::NoSafetyInvariants)
-                .then(Tree::from_bits(0x00))
+                .then(Tree::byte(0x00))
                 .then(Tree::def(Def::HasSafetyInvariants));
             assert_eq!(
                 layout.prune(&|d| matches!(d, Def::HasSafetyInvariants)),
@@ -94,12 +89,9 @@ mod prune {
         #[test]
         fn visible_def_in_seq_len_3() {
             let layout: Tree<Def, !> = Tree::def(Def::NoSafetyInvariants)
-                .then(Tree::from_bits(0x00))
+                .then(Tree::byte(0x00))
                 .then(Tree::def(Def::NoSafetyInvariants));
-            assert_eq!(
-                layout.prune(&|d| matches!(d, Def::HasSafetyInvariants)),
-                Tree::from_bits(0x00)
-            );
+            assert_eq!(layout.prune(&|d| matches!(d, Def::HasSafetyInvariants)), Tree::byte(0x00));
         }
     }
 }
diff --git a/compiler/rustc_transmute/src/maybe_transmutable/tests.rs b/compiler/rustc_transmute/src/maybe_transmutable/tests.rs
index 24e2a1acadd..992fcb7cc4c 100644
--- a/compiler/rustc_transmute/src/maybe_transmutable/tests.rs
+++ b/compiler/rustc_transmute/src/maybe_transmutable/tests.rs
@@ -177,9 +177,9 @@ mod bool {
 
     #[test]
     fn should_permit_validity_expansion_and_reject_contraction() {
-        let b0 = layout::Tree::<Def, !>::from_bits(0);
-        let b1 = layout::Tree::<Def, !>::from_bits(1);
-        let b2 = layout::Tree::<Def, !>::from_bits(2);
+        let b0 = layout::Tree::<Def, !>::byte(0);
+        let b1 = layout::Tree::<Def, !>::byte(1);
+        let b2 = layout::Tree::<Def, !>::byte(2);
 
         let alts = [b0, b1, b2];
 
@@ -279,8 +279,8 @@ mod alt {
     fn should_permit_identity_transmutation() {
         type Tree = layout::Tree<Def, !>;
 
-        let x = Tree::Seq(vec![Tree::from_bits(0), Tree::from_bits(0)]);
-        let y = Tree::Seq(vec![Tree::bool(), Tree::from_bits(1)]);
+        let x = Tree::Seq(vec![Tree::byte(0), Tree::byte(0)]);
+        let y = Tree::Seq(vec![Tree::bool(), Tree::byte(1)]);
         let layout = Tree::Alt(vec![x, y]);
 
         let answer = crate::maybe_transmutable::MaybeTransmutableQuery::new(
@@ -323,6 +323,76 @@ mod union {
     }
 }
 
+mod char {
+    use super::*;
+    use crate::layout::tree::Endian;
+
+    #[test]
+    fn should_permit_valid_transmutation() {
+        for order in [Endian::Big, Endian::Little] {
+            use Answer::*;
+            let char_layout = layout::Tree::<Def, !>::char(order);
+
+            // `char`s can be in the following ranges:
+            // - [0, 0xD7FF]
+            // - [0xE000, 10FFFF]
+            //
+            // This loop synthesizes a singleton-validity type for the extremes
+            // of each range, and for one past the end of the extremes of each
+            // range.
+            let no = No(Reason::DstIsBitIncompatible);
+            for (src, answer) in [
+                (0u32, Yes),
+                (0xD7FF, Yes),
+                (0xD800, no.clone()),
+                (0xDFFF, no.clone()),
+                (0xE000, Yes),
+                (0x10FFFF, Yes),
+                (0x110000, no.clone()),
+                (0xFFFF0000, no.clone()),
+                (0xFFFFFFFF, no),
+            ] {
+                let src_layout =
+                    layout::tree::Tree::<Def, !>::from_big_endian(order, src.to_be_bytes());
+
+                let a = is_transmutable(&src_layout, &char_layout, Assume::default());
+                assert_eq!(a, answer, "endian:{order:?},\nsrc:{src:x}");
+            }
+        }
+    }
+}
+
+mod nonzero {
+    use super::*;
+    use crate::{Answer, Reason};
+
+    const NONZERO_BYTE_WIDTHS: [u64; 5] = [1, 2, 4, 8, 16];
+
+    #[test]
+    fn should_permit_identity_transmutation() {
+        for width in NONZERO_BYTE_WIDTHS {
+            let layout = layout::Tree::<Def, !>::nonzero(width);
+            assert_eq!(is_transmutable(&layout, &layout, Assume::default()), Answer::Yes);
+        }
+    }
+
+    #[test]
+    fn should_permit_valid_transmutation() {
+        for width in NONZERO_BYTE_WIDTHS {
+            use Answer::*;
+
+            let num = layout::Tree::<Def, !>::number(width);
+            let nz = layout::Tree::<Def, !>::nonzero(width);
+
+            let a = is_transmutable(&num, &nz, Assume::default());
+            assert_eq!(a, No(Reason::DstIsBitIncompatible), "width:{width}");
+
+            let a = is_transmutable(&nz, &num, Assume::default());
+            assert_eq!(a, Yes, "width:{width}");
+        }
+    }
+}
+
 mod r#ref {
     use super::*;
 
@@ -330,7 +400,7 @@ mod r#ref {
     fn should_permit_identity_transmutation() {
         type Tree = crate::layout::Tree<Def, [(); 1]>;
 
-        let layout = Tree::Seq(vec![Tree::from_bits(0), Tree::Ref([()])]);
+        let layout = Tree::Seq(vec![Tree::byte(0x00), Tree::Ref([()])]);
 
         let answer = crate::maybe_transmutable::MaybeTransmutableQuery::new(
             layout.clone(),