Rollup merge of #110615 - WaffleLapkin:impl_tag, r=cjgillot

Add `impl_tag!` macro to implement `Tag` for tagged pointer easily

r? `@Nilstrieb`

This should also lifts the need to think about safety from the callers (`impl_tag!` is robust (ish, see the macro issue)) and removes the possibility of making a "weird" `Tag` impl.

4 files changed, 204 insertions, 6 deletions

diff --git a/compiler/rustc_data_structures/src/lib.rs b/compiler/rustc_data_structures/src/lib.rs
index 426d2c4034b..004017ec5f3 100644
--- a/compiler/rustc_data_structures/src/lib.rs
+++ b/compiler/rustc_data_structures/src/lib.rs
@@ -31,6 +31,7 @@
 #![feature(unwrap_infallible)]
 #![feature(strict_provenance)]
 #![feature(ptr_alignment_type)]
+#![feature(macro_metavar_expr)]
 #![allow(rustc::default_hash_types)]
 #![allow(rustc::potential_query_instability)]
 #![deny(rustc::untranslatable_diagnostic)]
diff --git a/compiler/rustc_data_structures/src/tagged_ptr.rs b/compiler/rustc_data_structures/src/tagged_ptr.rs
index 8568aac67c0..2914eece679 100644
--- a/compiler/rustc_data_structures/src/tagged_ptr.rs
+++ b/compiler/rustc_data_structures/src/tagged_ptr.rs
@@ -24,6 +24,7 @@ use crate::aligned::Aligned;
 
 mod copy;
 mod drop;
+mod impl_tag;
 
 pub use copy::CopyTaggedPtr;
 pub use drop::TaggedPtr;
@@ -141,6 +142,30 @@ pub unsafe trait Tag: Copy {
     unsafe fn from_usize(tag: usize) -> Self;
 }
 
+/// Returns the number of bits available for use for tags in a pointer to `T`
+/// (this is based on `T`'s alignment).
+pub const fn bits_for<T: ?Sized + Aligned>() -> u32 {
+    crate::aligned::align_of::<T>().as_nonzero().trailing_zeros()
+}
+
+/// Returns the correct [`Tag::BITS`] constant for a set of tag values.
+pub const fn bits_for_tags(mut tags: &[usize]) -> u32 {
+    let mut bits = 0;
+
+    while let &[tag, ref rest @ ..] = tags {
+        tags = rest;
+
+        // bits required to represent `tag`,
+        // position of the most significant 1
+        let b = usize::BITS - tag.leading_zeros();
+        if b > bits {
+            bits = b;
+        }
+    }
+
+    bits
+}
+
 unsafe impl<T: ?Sized + Aligned> Pointer for Box<T> {
     const BITS: u32 = bits_for::<Self::Target>();
 
@@ -221,12 +246,6 @@ unsafe impl<'a, T: 'a + ?Sized + Aligned> Pointer for &'a mut T {
     }
 }
 
-/// Returns the number of bits available for use for tags in a pointer to `T`
-/// (this is based on `T`'s alignment).
-pub const fn bits_for<T: ?Sized + Aligned>() -> u32 {
-    crate::aligned::align_of::<T>().as_nonzero().trailing_zeros()
-}
-
 /// A tag type used in [`CopyTaggedPtr`] and [`TaggedPtr`] tests.
 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 #[cfg(test)]
diff --git a/compiler/rustc_data_structures/src/tagged_ptr/impl_tag.rs b/compiler/rustc_data_structures/src/tagged_ptr/impl_tag.rs
new file mode 100644
index 00000000000..cb7f7d318dc
--- /dev/null
+++ b/compiler/rustc_data_structures/src/tagged_ptr/impl_tag.rs
@@ -0,0 +1,144 @@
+/// Implements [`Tag`] for a given type.
+///
+/// You can use `impl_tag` on structs and enums.
+/// You need to specify the type and all its possible values,
+/// which can only be paths with optional fields.
+///
+/// [`Tag`]: crate::tagged_ptr::Tag
+///
+/// # Examples
+///
+/// Basic usage:
+///
+/// ```
+/// #![feature(macro_metavar_expr)]
+/// use rustc_data_structures::{impl_tag, tagged_ptr::Tag};
+///
+/// #[derive(Copy, Clone, PartialEq, Debug)]
+/// enum SomeTag {
+///     A,
+///     B,
+///     X { v: bool },
+///     Y(bool, bool),
+/// }
+///
+/// impl_tag! {
+///     // The type for which the `Tag` will be implemented
+///     impl Tag for SomeTag;
+///     // You need to specify all possible tag values:
+///     SomeTag::A, // 0
+///     SomeTag::B, // 1
+///     // For variants with fields, you need to specify the fields:
+///     SomeTag::X { v: true  }, // 2
+///     SomeTag::X { v: false }, // 3
+///     // For tuple variants use named syntax:
+///     SomeTag::Y { 0: true,  1: true  }, // 4
+///     SomeTag::Y { 0: false, 1: true  }, // 5
+///     SomeTag::Y { 0: true,  1: false }, // 6
+///     SomeTag::Y { 0: false, 1: false }, // 7
+/// }
+///
+/// // Tag values are assigned in order:
+/// assert_eq!(SomeTag::A.into_usize(), 0);
+/// assert_eq!(SomeTag::X { v: false }.into_usize(), 3);
+/// assert_eq!(SomeTag::Y(false, true).into_usize(), 5);
+///
+/// assert_eq!(unsafe { SomeTag::from_usize(1) }, SomeTag::B);
+/// assert_eq!(unsafe { SomeTag::from_usize(2) }, SomeTag::X { v: true });
+/// assert_eq!(unsafe { SomeTag::from_usize(7) }, SomeTag::Y(false, false));
+/// ```
+///
+/// Structs are supported:
+///
+/// ```
+/// #![feature(macro_metavar_expr)]
+/// # use rustc_data_structures::impl_tag;
+/// #[derive(Copy, Clone)]
+/// struct Flags { a: bool, b: bool }
+///
+/// impl_tag! {
+///     impl Tag for Flags;
+///     Flags { a: true,  b: true  },
+///     Flags { a: false, b: true  },
+///     Flags { a: true,  b: false },
+///     Flags { a: false, b: false },
+/// }
+/// ```
+///
+/// Not specifying all values results in a compile error:
+///
+/// ```compile_fail,E0004
+/// #![feature(macro_metavar_expr)]
+/// # use rustc_data_structures::impl_tag;
+/// #[derive(Copy, Clone)]
+/// enum E {
+///     A,
+///     B,
+/// }
+///
+/// impl_tag! {
+///     impl Tag for E;
+///     E::A,
+/// }
+/// ```
+#[macro_export]
+macro_rules! impl_tag {
+    (
+        impl Tag for $Self:ty;
+        $(
+            $($path:ident)::* $( { $( $fields:tt )* })?,
+        )*
+    ) => {
+        // Safety:
+        // `bits_for_tags` is called on the same `${index()}`-es as
+        // `into_usize` returns, thus `BITS` constant is correct.
+        unsafe impl $crate::tagged_ptr::Tag for $Self {
+            const BITS: u32 = $crate::tagged_ptr::bits_for_tags(&[
+                $(
+                    ${index()},
+                    $( ${ignore(path)} )*
+                )*
+            ]);
+
+            #[inline]
+            fn into_usize(self) -> usize {
+                // This forbids use of repeating patterns (`Enum::V`&`Enum::V`, etc)
+                // (or at least it should, see <https://github.com/rust-lang/rust/issues/110613>)
+                #[forbid(unreachable_patterns)]
+                match self {
+                    // `match` is doing heavy lifting here, by requiring exhaustiveness
+                    $(
+                        $($path)::* $( { $( $fields )* } )? => ${index()},
+                    )*
+                }
+            }
+
+            #[inline]
+            unsafe fn from_usize(tag: usize) -> Self {
+                match tag {
+                    $(
+                        ${index()} => $($path)::* $( { $( $fields )* } )?,
+                    )*
+
+                    // Safety:
+                    // `into_usize` only returns `${index()}` of the same
+                    // repetition as we are filtering above, thus if this is
+                    // reached, the safety contract of this function was
+                    // already breached.
+                    _ => unsafe {
+                        debug_assert!(
+                            false,
+                            "invalid tag: {tag}\
+                             (this is a bug in the caller of `from_usize`)"
+                        );
+                        std::hint::unreachable_unchecked()
+                    },
+                }
+            }
+
+        }
+    };
+}
+
+#[cfg(test)]
+mod tests;
diff --git a/compiler/rustc_data_structures/src/tagged_ptr/impl_tag/tests.rs b/compiler/rustc_data_structures/src/tagged_ptr/impl_tag/tests.rs
new file mode 100644
index 00000000000..62c926153e1
--- /dev/null
+++ b/compiler/rustc_data_structures/src/tagged_ptr/impl_tag/tests.rs
@@ -0,0 +1,34 @@
+#[test]
+fn bits_constant() {
+    use crate::tagged_ptr::Tag;
+
+    #[derive(Copy, Clone)]
+    struct Unit;
+    impl_tag! { impl Tag for Unit; Unit, }
+    assert_eq!(Unit::BITS, 0);
+
+    #[derive(Copy, Clone)]
+    enum Enum3 {
+        A,
+        B,
+        C,
+    }
+    impl_tag! { impl Tag for Enum3; Enum3::A, Enum3::B, Enum3::C, }
+    assert_eq!(Enum3::BITS, 2);
+
+    #[derive(Copy, Clone)]
+    struct Eight(bool, bool, bool);
+    impl_tag! {
+        impl Tag for Eight;
+        Eight { 0: true,  1: true,  2: true  },
+        Eight { 0: true,  1: true,  2: false },
+        Eight { 0: true,  1: false, 2: true  },
+        Eight { 0: true,  1: false, 2: false },
+        Eight { 0: false, 1: true,  2: true  },
+        Eight { 0: false, 1: true,  2: false },
+        Eight { 0: false, 1: false, 2: true  },
+        Eight { 0: false, 1: false, 2: false },
+    }
+
+    assert_eq!(Eight::BITS, 3);
+}