Compute transmutability from `rustc_target::abi::Layout`

In its first step of computing transmutability, `rustc_transmutability`
constructs a byte-level representation of type layout (`Tree`). Previously, this
representation was computed for ADTs by inspecting the ADT definition and
performing our own layout computations. This process was error-prone, verbose,
and limited our ability to analyze many types (particularly default-repr types).

In this PR, we instead construct `Tree`s from `rustc_target::abi::Layout`s. This
helps ensure that layout optimizations are reflected our analyses, and increases
the kinds of types we can now analyze, including:
- default repr ADTs
- transparent unions
- `UnsafeCell`-containing types

Overall, this PR expands the expressvity of `rustc_transmutability` to be much
closer to the transmutability analysis performed by miri. Future PRs will work
to close the remaining gaps (e.g., support for `Box`, raw pointers, `NonZero*`,
coroutines, etc.).

4 files changed, 33 insertions, 283 deletions

diff --git a/tests/ui/transmutability/structs/repr/should_require_well_defined_layout.rs b/tests/ui/transmutability/structs/repr/should_handle_all.rs
index 2e673601baf..52c24eecf12 100644
--- a/tests/ui/transmutability/structs/repr/should_require_well_defined_layout.rs
+++ b/tests/ui/transmutability/structs/repr/should_handle_all.rs
@@ -1,3 +1,4 @@
+//@ check-pass
 //! A struct must have a well-defined layout to participate in a transmutation.
 
 #![crate_type = "lib"]
@@ -20,47 +21,47 @@ mod assert {
     {}
 }
 
-fn should_reject_repr_rust()
+fn should_accept_repr_rust()
 {
     fn unit() {
         struct repr_rust;
-        assert::is_maybe_transmutable::<repr_rust, ()>(); //~ ERROR cannot be safely transmuted
-        assert::is_maybe_transmutable::<u128, repr_rust>(); //~ ERROR cannot be safely transmuted
+        assert::is_maybe_transmutable::<repr_rust, ()>();
+        assert::is_maybe_transmutable::<u128, repr_rust>();
     }
 
     fn tuple() {
         struct repr_rust();
-        assert::is_maybe_transmutable::<repr_rust, ()>(); //~ ERROR cannot be safely transmuted
-        assert::is_maybe_transmutable::<u128, repr_rust>(); //~ ERROR cannot be safely transmuted
+        assert::is_maybe_transmutable::<repr_rust, ()>();
+        assert::is_maybe_transmutable::<u128, repr_rust>();
     }
 
     fn braces() {
         struct repr_rust{}
-        assert::is_maybe_transmutable::<repr_rust, ()>(); //~ ERROR cannot be safely transmuted
-        assert::is_maybe_transmutable::<u128, repr_rust>(); //~ ERROR cannot be safely transmuted
+        assert::is_maybe_transmutable::<repr_rust, ()>();
+        assert::is_maybe_transmutable::<u128, repr_rust>();
     }
 
     fn aligned() {
         #[repr(align(1))] struct repr_rust{}
-        assert::is_maybe_transmutable::<repr_rust, ()>(); //~ ERROR cannot be safely transmuted
-        assert::is_maybe_transmutable::<u128, repr_rust>(); //~ ERROR cannot be safely transmuted
+        assert::is_maybe_transmutable::<repr_rust, ()>();
+        assert::is_maybe_transmutable::<u128, repr_rust>();
     }
 
     fn packed() {
         #[repr(packed)] struct repr_rust{}
-        assert::is_maybe_transmutable::<repr_rust, ()>(); //~ ERROR cannot be safely transmuted
-        assert::is_maybe_transmutable::<u128, repr_rust>(); //~ ERROR cannot be safely transmuted
+        assert::is_maybe_transmutable::<repr_rust, ()>();
+        assert::is_maybe_transmutable::<u128, repr_rust>();
     }
 
     fn nested() {
         struct repr_rust;
         #[repr(C)] struct repr_c(repr_rust);
-        assert::is_maybe_transmutable::<repr_c, ()>(); //~ ERROR cannot be safely transmuted
-        assert::is_maybe_transmutable::<u128, repr_c>(); //~ ERROR cannot be safely transmuted
+        assert::is_maybe_transmutable::<repr_c, ()>();
+        assert::is_maybe_transmutable::<u128, repr_c>();
     }
 }
 
-fn should_accept_repr_C()
+fn should_accept_repr_c()
 {
     fn unit() {
         #[repr(C)] struct repr_c;
diff --git a/tests/ui/transmutability/structs/repr/should_require_well_defined_layout.stderr b/tests/ui/transmutability/structs/repr/should_require_well_defined_layout.stderr
deleted file mode 100644
index 77788f72c21..00000000000
--- a/tests/ui/transmutability/structs/repr/should_require_well_defined_layout.stderr
+++ /dev/null
@@ -1,267 +0,0 @@
-error[E0277]: `should_reject_repr_rust::unit::repr_rust` cannot be safely transmuted into `()`
-  --> $DIR/should_require_well_defined_layout.rs:27:52
-   |
-LL |         assert::is_maybe_transmutable::<repr_rust, ()>();
-   |                                                    ^^ analyzing the transmutability of `should_reject_repr_rust::unit::repr_rust` is not yet supported.
-   |
-note: required by a bound in `is_maybe_transmutable`
-  --> $DIR/should_require_well_defined_layout.rs:12:14
-   |
-LL |       pub fn is_maybe_transmutable<Src, Dst>()
-   |              --------------------- required by a bound in this function
-LL |       where
-LL |           Dst: BikeshedIntrinsicFrom<Src, {
-   |  ______________^
-LL | |             Assume {
-LL | |                 alignment: true,
-LL | |                 lifetimes: true,
-...  |
-LL | |             }
-LL | |         }>
-   | |__________^ required by this bound in `is_maybe_transmutable`
-
-error[E0277]: `u128` cannot be safely transmuted into `should_reject_repr_rust::unit::repr_rust`
-  --> $DIR/should_require_well_defined_layout.rs:28:47
-   |
-LL |         assert::is_maybe_transmutable::<u128, repr_rust>();
-   |                                               ^^^^^^^^^ analyzing the transmutability of `should_reject_repr_rust::unit::repr_rust` is not yet supported.
-   |
-note: required by a bound in `is_maybe_transmutable`
-  --> $DIR/should_require_well_defined_layout.rs:12:14
-   |
-LL |       pub fn is_maybe_transmutable<Src, Dst>()
-   |              --------------------- required by a bound in this function
-LL |       where
-LL |           Dst: BikeshedIntrinsicFrom<Src, {
-   |  ______________^
-LL | |             Assume {
-LL | |                 alignment: true,
-LL | |                 lifetimes: true,
-...  |
-LL | |             }
-LL | |         }>
-   | |__________^ required by this bound in `is_maybe_transmutable`
-
-error[E0277]: `should_reject_repr_rust::tuple::repr_rust` cannot be safely transmuted into `()`
-  --> $DIR/should_require_well_defined_layout.rs:33:52
-   |
-LL |         assert::is_maybe_transmutable::<repr_rust, ()>();
-   |                                                    ^^ analyzing the transmutability of `should_reject_repr_rust::tuple::repr_rust` is not yet supported.
-   |
-note: required by a bound in `is_maybe_transmutable`
-  --> $DIR/should_require_well_defined_layout.rs:12:14
-   |
-LL |       pub fn is_maybe_transmutable<Src, Dst>()
-   |              --------------------- required by a bound in this function
-LL |       where
-LL |           Dst: BikeshedIntrinsicFrom<Src, {
-   |  ______________^
-LL | |             Assume {
-LL | |                 alignment: true,
-LL | |                 lifetimes: true,
-...  |
-LL | |             }
-LL | |         }>
-   | |__________^ required by this bound in `is_maybe_transmutable`
-
-error[E0277]: `u128` cannot be safely transmuted into `should_reject_repr_rust::tuple::repr_rust`
-  --> $DIR/should_require_well_defined_layout.rs:34:47
-   |
-LL |         assert::is_maybe_transmutable::<u128, repr_rust>();
-   |                                               ^^^^^^^^^ analyzing the transmutability of `should_reject_repr_rust::tuple::repr_rust` is not yet supported.
-   |
-note: required by a bound in `is_maybe_transmutable`
-  --> $DIR/should_require_well_defined_layout.rs:12:14
-   |
-LL |       pub fn is_maybe_transmutable<Src, Dst>()
-   |              --------------------- required by a bound in this function
-LL |       where
-LL |           Dst: BikeshedIntrinsicFrom<Src, {
-   |  ______________^
-LL | |             Assume {
-LL | |                 alignment: true,
-LL | |                 lifetimes: true,
-...  |
-LL | |             }
-LL | |         }>
-   | |__________^ required by this bound in `is_maybe_transmutable`
-
-error[E0277]: `should_reject_repr_rust::braces::repr_rust` cannot be safely transmuted into `()`
-  --> $DIR/should_require_well_defined_layout.rs:39:52
-   |
-LL |         assert::is_maybe_transmutable::<repr_rust, ()>();
-   |                                                    ^^ analyzing the transmutability of `should_reject_repr_rust::braces::repr_rust` is not yet supported.
-   |
-note: required by a bound in `is_maybe_transmutable`
-  --> $DIR/should_require_well_defined_layout.rs:12:14
-   |
-LL |       pub fn is_maybe_transmutable<Src, Dst>()
-   |              --------------------- required by a bound in this function
-LL |       where
-LL |           Dst: BikeshedIntrinsicFrom<Src, {
-   |  ______________^
-LL | |             Assume {
-LL | |                 alignment: true,
-LL | |                 lifetimes: true,
-...  |
-LL | |             }
-LL | |         }>
-   | |__________^ required by this bound in `is_maybe_transmutable`
-
-error[E0277]: `u128` cannot be safely transmuted into `should_reject_repr_rust::braces::repr_rust`
-  --> $DIR/should_require_well_defined_layout.rs:40:47
-   |
-LL |         assert::is_maybe_transmutable::<u128, repr_rust>();
-   |                                               ^^^^^^^^^ analyzing the transmutability of `should_reject_repr_rust::braces::repr_rust` is not yet supported.
-   |
-note: required by a bound in `is_maybe_transmutable`
-  --> $DIR/should_require_well_defined_layout.rs:12:14
-   |
-LL |       pub fn is_maybe_transmutable<Src, Dst>()
-   |              --------------------- required by a bound in this function
-LL |       where
-LL |           Dst: BikeshedIntrinsicFrom<Src, {
-   |  ______________^
-LL | |             Assume {
-LL | |                 alignment: true,
-LL | |                 lifetimes: true,
-...  |
-LL | |             }
-LL | |         }>
-   | |__________^ required by this bound in `is_maybe_transmutable`
-
-error[E0277]: `aligned::repr_rust` cannot be safely transmuted into `()`
-  --> $DIR/should_require_well_defined_layout.rs:45:52
-   |
-LL |         assert::is_maybe_transmutable::<repr_rust, ()>();
-   |                                                    ^^ analyzing the transmutability of `aligned::repr_rust` is not yet supported.
-   |
-note: required by a bound in `is_maybe_transmutable`
-  --> $DIR/should_require_well_defined_layout.rs:12:14
-   |
-LL |       pub fn is_maybe_transmutable<Src, Dst>()
-   |              --------------------- required by a bound in this function
-LL |       where
-LL |           Dst: BikeshedIntrinsicFrom<Src, {
-   |  ______________^
-LL | |             Assume {
-LL | |                 alignment: true,
-LL | |                 lifetimes: true,
-...  |
-LL | |             }
-LL | |         }>
-   | |__________^ required by this bound in `is_maybe_transmutable`
-
-error[E0277]: `u128` cannot be safely transmuted into `aligned::repr_rust`
-  --> $DIR/should_require_well_defined_layout.rs:46:47
-   |
-LL |         assert::is_maybe_transmutable::<u128, repr_rust>();
-   |                                               ^^^^^^^^^ analyzing the transmutability of `aligned::repr_rust` is not yet supported.
-   |
-note: required by a bound in `is_maybe_transmutable`
-  --> $DIR/should_require_well_defined_layout.rs:12:14
-   |
-LL |       pub fn is_maybe_transmutable<Src, Dst>()
-   |              --------------------- required by a bound in this function
-LL |       where
-LL |           Dst: BikeshedIntrinsicFrom<Src, {
-   |  ______________^
-LL | |             Assume {
-LL | |                 alignment: true,
-LL | |                 lifetimes: true,
-...  |
-LL | |             }
-LL | |         }>
-   | |__________^ required by this bound in `is_maybe_transmutable`
-
-error[E0277]: `packed::repr_rust` cannot be safely transmuted into `()`
-  --> $DIR/should_require_well_defined_layout.rs:51:52
-   |
-LL |         assert::is_maybe_transmutable::<repr_rust, ()>();
-   |                                                    ^^ analyzing the transmutability of `packed::repr_rust` is not yet supported.
-   |
-note: required by a bound in `is_maybe_transmutable`
-  --> $DIR/should_require_well_defined_layout.rs:12:14
-   |
-LL |       pub fn is_maybe_transmutable<Src, Dst>()
-   |              --------------------- required by a bound in this function
-LL |       where
-LL |           Dst: BikeshedIntrinsicFrom<Src, {
-   |  ______________^
-LL | |             Assume {
-LL | |                 alignment: true,
-LL | |                 lifetimes: true,
-...  |
-LL | |             }
-LL | |         }>
-   | |__________^ required by this bound in `is_maybe_transmutable`
-
-error[E0277]: `u128` cannot be safely transmuted into `packed::repr_rust`
-  --> $DIR/should_require_well_defined_layout.rs:52:47
-   |
-LL |         assert::is_maybe_transmutable::<u128, repr_rust>();
-   |                                               ^^^^^^^^^ analyzing the transmutability of `packed::repr_rust` is not yet supported.
-   |
-note: required by a bound in `is_maybe_transmutable`
-  --> $DIR/should_require_well_defined_layout.rs:12:14
-   |
-LL |       pub fn is_maybe_transmutable<Src, Dst>()
-   |              --------------------- required by a bound in this function
-LL |       where
-LL |           Dst: BikeshedIntrinsicFrom<Src, {
-   |  ______________^
-LL | |             Assume {
-LL | |                 alignment: true,
-LL | |                 lifetimes: true,
-...  |
-LL | |             }
-LL | |         }>
-   | |__________^ required by this bound in `is_maybe_transmutable`
-
-error[E0277]: `nested::repr_c` cannot be safely transmuted into `()`
-  --> $DIR/should_require_well_defined_layout.rs:58:49
-   |
-LL |         assert::is_maybe_transmutable::<repr_c, ()>();
-   |                                                 ^^ analyzing the transmutability of `nested::repr_c` is not yet supported.
-   |
-note: required by a bound in `is_maybe_transmutable`
-  --> $DIR/should_require_well_defined_layout.rs:12:14
-   |
-LL |       pub fn is_maybe_transmutable<Src, Dst>()
-   |              --------------------- required by a bound in this function
-LL |       where
-LL |           Dst: BikeshedIntrinsicFrom<Src, {
-   |  ______________^
-LL | |             Assume {
-LL | |                 alignment: true,
-LL | |                 lifetimes: true,
-...  |
-LL | |             }
-LL | |         }>
-   | |__________^ required by this bound in `is_maybe_transmutable`
-
-error[E0277]: `u128` cannot be safely transmuted into `nested::repr_c`
-  --> $DIR/should_require_well_defined_layout.rs:59:47
-   |
-LL |         assert::is_maybe_transmutable::<u128, repr_c>();
-   |                                               ^^^^^^ analyzing the transmutability of `nested::repr_c` is not yet supported.
-   |
-note: required by a bound in `is_maybe_transmutable`
-  --> $DIR/should_require_well_defined_layout.rs:12:14
-   |
-LL |       pub fn is_maybe_transmutable<Src, Dst>()
-   |              --------------------- required by a bound in this function
-LL |       where
-LL |           Dst: BikeshedIntrinsicFrom<Src, {
-   |  ______________^
-LL | |             Assume {
-LL | |                 alignment: true,
-LL | |                 lifetimes: true,
-...  |
-LL | |             }
-LL | |         }>
-   | |__________^ required by this bound in `is_maybe_transmutable`
-
-error: aborting due to 12 previous errors
-
-For more information about this error, try `rustc --explain E0277`.
diff --git a/tests/ui/transmutability/structs/repr/transmute_infinitely_recursive_type.rs b/tests/ui/transmutability/structs/repr/transmute_infinitely_recursive_type.rs
index 4c285a616b3..64110753832 100644
--- a/tests/ui/transmutability/structs/repr/transmute_infinitely_recursive_type.rs
+++ b/tests/ui/transmutability/structs/repr/transmute_infinitely_recursive_type.rs
@@ -22,4 +22,5 @@ fn should_pad_explicitly_packed_field() {
     //~^ ERROR: recursive type
 
     assert::is_maybe_transmutable::<ExplicitlyPadded, ()>();
+    //~^ ERROR: cannot be safely transmuted
 }
diff --git a/tests/ui/transmutability/structs/repr/transmute_infinitely_recursive_type.stderr b/tests/ui/transmutability/structs/repr/transmute_infinitely_recursive_type.stderr
index 7fb051f6625..ebfb5361143 100644
--- a/tests/ui/transmutability/structs/repr/transmute_infinitely_recursive_type.stderr
+++ b/tests/ui/transmutability/structs/repr/transmute_infinitely_recursive_type.stderr
@@ -15,7 +15,22 @@ error[E0391]: cycle detected when computing layout of `should_pad_explicitly_pac
    = note: cycle used when evaluating trait selection obligation `(): core::mem::transmutability::BikeshedIntrinsicFrom<should_pad_explicitly_packed_field::ExplicitlyPadded, core::mem::transmutability::Assume { alignment: false, lifetimes: false, safety: false, validity: false }>`
    = note: see https://rustc-dev-guide.rust-lang.org/overview.html#queries and https://rustc-dev-guide.rust-lang.org/query.html for more information
 
-error: aborting due to 2 previous errors
+error[E0277]: `ExplicitlyPadded` cannot be safely transmuted into `()`
+  --> $DIR/transmute_infinitely_recursive_type.rs:24:55
+   |
+LL |     assert::is_maybe_transmutable::<ExplicitlyPadded, ()>();
+   |                                                       ^^ analyzing the transmutability of `ExplicitlyPadded` is not yet supported
+   |
+note: required by a bound in `is_maybe_transmutable`
+  --> $DIR/transmute_infinitely_recursive_type.rs:14:14
+   |
+LL |     pub fn is_maybe_transmutable<Src, Dst>()
+   |            --------------------- required by a bound in this function
+LL |     where
+LL |         Dst: BikeshedIntrinsicFrom<Src>,
+   |              ^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `is_maybe_transmutable`
+
+error: aborting due to 3 previous errors
 
-Some errors have detailed explanations: E0072, E0391.
+Some errors have detailed explanations: E0072, E0277, E0391.
 For more information about an error, try `rustc --explain E0072`.