Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

3 files changed, 826 insertions, 0 deletions

diff --git a/compiler/rustc_middle/src/ty/consts/int.rs b/compiler/rustc_middle/src/ty/consts/int.rs
new file mode 100644
index 000000000..7436f0f6f
--- /dev/null
+++ b/compiler/rustc_middle/src/ty/consts/int.rs
@@ -0,0 +1,483 @@
+use rustc_apfloat::ieee::{Double, Single};
+use rustc_apfloat::Float;
+use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
+use rustc_target::abi::Size;
+use std::convert::{TryFrom, TryInto};
+use std::fmt;
+use std::num::NonZeroU8;
+
+use crate::ty::TyCtxt;
+
+#[derive(Copy, Clone)]
+/// A type for representing any integer. Only used for printing.
+pub struct ConstInt {
+    /// The "untyped" variant of `ConstInt`.
+    int: ScalarInt,
+    /// Whether the value is of a signed integer type.
+    signed: bool,
+    /// Whether the value is a `usize` or `isize` type.
+    is_ptr_sized_integral: bool,
+}
+
+impl ConstInt {
+    pub fn new(int: ScalarInt, signed: bool, is_ptr_sized_integral: bool) -> Self {
+        Self { int, signed, is_ptr_sized_integral }
+    }
+}
+
+impl std::fmt::Debug for ConstInt {
+    fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        let Self { int, signed, is_ptr_sized_integral } = *self;
+        let size = int.size().bytes();
+        let raw = int.data;
+        if signed {
+            let bit_size = size * 8;
+            let min = 1u128 << (bit_size - 1);
+            let max = min - 1;
+            if raw == min {
+                match (size, is_ptr_sized_integral) {
+                    (_, true) => write!(fmt, "isize::MIN"),
+                    (1, _) => write!(fmt, "i8::MIN"),
+                    (2, _) => write!(fmt, "i16::MIN"),
+                    (4, _) => write!(fmt, "i32::MIN"),
+                    (8, _) => write!(fmt, "i64::MIN"),
+                    (16, _) => write!(fmt, "i128::MIN"),
+                    _ => bug!("ConstInt 0x{:x} with size = {} and signed = {}", raw, size, signed),
+                }
+            } else if raw == max {
+                match (size, is_ptr_sized_integral) {
+                    (_, true) => write!(fmt, "isize::MAX"),
+                    (1, _) => write!(fmt, "i8::MAX"),
+                    (2, _) => write!(fmt, "i16::MAX"),
+                    (4, _) => write!(fmt, "i32::MAX"),
+                    (8, _) => write!(fmt, "i64::MAX"),
+                    (16, _) => write!(fmt, "i128::MAX"),
+                    _ => bug!("ConstInt 0x{:x} with size = {} and signed = {}", raw, size, signed),
+                }
+            } else {
+                match size {
+                    1 => write!(fmt, "{}", raw as i8)?,
+                    2 => write!(fmt, "{}", raw as i16)?,
+                    4 => write!(fmt, "{}", raw as i32)?,
+                    8 => write!(fmt, "{}", raw as i64)?,
+                    16 => write!(fmt, "{}", raw as i128)?,
+                    _ => bug!("ConstInt 0x{:x} with size = {} and signed = {}", raw, size, signed),
+                }
+                if fmt.alternate() {
+                    match (size, is_ptr_sized_integral) {
+                        (_, true) => write!(fmt, "_isize")?,
+                        (1, _) => write!(fmt, "_i8")?,
+                        (2, _) => write!(fmt, "_i16")?,
+                        (4, _) => write!(fmt, "_i32")?,
+                        (8, _) => write!(fmt, "_i64")?,
+                        (16, _) => write!(fmt, "_i128")?,
+                        _ => bug!(),
+                    }
+                }
+                Ok(())
+            }
+        } else {
+            let max = Size::from_bytes(size).truncate(u128::MAX);
+            if raw == max {
+                match (size, is_ptr_sized_integral) {
+                    (_, true) => write!(fmt, "usize::MAX"),
+                    (1, _) => write!(fmt, "u8::MAX"),
+                    (2, _) => write!(fmt, "u16::MAX"),
+                    (4, _) => write!(fmt, "u32::MAX"),
+                    (8, _) => write!(fmt, "u64::MAX"),
+                    (16, _) => write!(fmt, "u128::MAX"),
+                    _ => bug!("ConstInt 0x{:x} with size = {} and signed = {}", raw, size, signed),
+                }
+            } else {
+                match size {
+                    1 => write!(fmt, "{}", raw as u8)?,
+                    2 => write!(fmt, "{}", raw as u16)?,
+                    4 => write!(fmt, "{}", raw as u32)?,
+                    8 => write!(fmt, "{}", raw as u64)?,
+                    16 => write!(fmt, "{}", raw as u128)?,
+                    _ => bug!("ConstInt 0x{:x} with size = {} and signed = {}", raw, size, signed),
+                }
+                if fmt.alternate() {
+                    match (size, is_ptr_sized_integral) {
+                        (_, true) => write!(fmt, "_usize")?,
+                        (1, _) => write!(fmt, "_u8")?,
+                        (2, _) => write!(fmt, "_u16")?,
+                        (4, _) => write!(fmt, "_u32")?,
+                        (8, _) => write!(fmt, "_u64")?,
+                        (16, _) => write!(fmt, "_u128")?,
+                        _ => bug!(),
+                    }
+                }
+                Ok(())
+            }
+        }
+    }
+}
+
+/// The raw bytes of a simple value.
+///
+/// This is a packed struct in order to allow this type to be optimally embedded in enums
+/// (like Scalar).
+#[derive(Clone, Copy, Eq, PartialEq, Ord, PartialOrd, Hash)]
+#[repr(packed)]
+pub struct ScalarInt {
+    /// The first `size` bytes of `data` are the value.
+    /// Do not try to read less or more bytes than that. The remaining bytes must be 0.
+    data: u128,
+    size: NonZeroU8,
+}
+
+// Cannot derive these, as the derives take references to the fields, and we
+// can't take references to fields of packed structs.
+impl<CTX> crate::ty::HashStable<CTX> for ScalarInt {
+    fn hash_stable(&self, hcx: &mut CTX, hasher: &mut crate::ty::StableHasher) {
+        // Using a block `{self.data}` here to force a copy instead of using `self.data`
+        // directly, because `hash_stable` takes `&self` and would thus borrow `self.data`.
+        // Since `Self` is a packed struct, that would create a possibly unaligned reference,
+        // which is UB.
+        { self.data }.hash_stable(hcx, hasher);
+        self.size.get().hash_stable(hcx, hasher);
+    }
+}
+
+impl<S: Encoder> Encodable<S> for ScalarInt {
+    fn encode(&self, s: &mut S) {
+        s.emit_u128(self.data);
+        s.emit_u8(self.size.get());
+    }
+}
+
+impl<D: Decoder> Decodable<D> for ScalarInt {
+    fn decode(d: &mut D) -> ScalarInt {
+        ScalarInt { data: d.read_u128(), size: NonZeroU8::new(d.read_u8()).unwrap() }
+    }
+}
+
+impl ScalarInt {
+    pub const TRUE: ScalarInt = ScalarInt { data: 1_u128, size: NonZeroU8::new(1).unwrap() };
+
+    pub const FALSE: ScalarInt = ScalarInt { data: 0_u128, size: NonZeroU8::new(1).unwrap() };
+
+    #[inline]
+    pub fn size(self) -> Size {
+        Size::from_bytes(self.size.get())
+    }
+
+    /// Make sure the `data` fits in `size`.
+    /// This is guaranteed by all constructors here, but having had this check saved us from
+    /// bugs many times in the past, so keeping it around is definitely worth it.
+    #[inline(always)]
+    fn check_data(self) {
+        // Using a block `{self.data}` here to force a copy instead of using `self.data`
+        // directly, because `debug_assert_eq` takes references to its arguments and formatting
+        // arguments and would thus borrow `self.data`. Since `Self`
+        // is a packed struct, that would create a possibly unaligned reference, which
+        // is UB.
+        debug_assert_eq!(
+            self.size().truncate(self.data),
+            { self.data },
+            "Scalar value {:#x} exceeds size of {} bytes",
+            { self.data },
+            self.size
+        );
+    }
+
+    #[inline]
+    pub fn null(size: Size) -> Self {
+        Self { data: 0, size: NonZeroU8::new(size.bytes() as u8).unwrap() }
+    }
+
+    #[inline]
+    pub fn is_null(self) -> bool {
+        self.data == 0
+    }
+
+    #[inline]
+    pub fn try_from_uint(i: impl Into<u128>, size: Size) -> Option<Self> {
+        let data = i.into();
+        if size.truncate(data) == data {
+            Some(Self { data, size: NonZeroU8::new(size.bytes() as u8).unwrap() })
+        } else {
+            None
+        }
+    }
+
+    #[inline]
+    pub fn try_from_int(i: impl Into<i128>, size: Size) -> Option<Self> {
+        let i = i.into();
+        // `into` performed sign extension, we have to truncate
+        let truncated = size.truncate(i as u128);
+        if size.sign_extend(truncated) as i128 == i {
+            Some(Self { data: truncated, size: NonZeroU8::new(size.bytes() as u8).unwrap() })
+        } else {
+            None
+        }
+    }
+
+    #[inline]
+    pub fn assert_bits(self, target_size: Size) -> u128 {
+        self.to_bits(target_size).unwrap_or_else(|size| {
+            bug!("expected int of size {}, but got size {}", target_size.bytes(), size.bytes())
+        })
+    }
+
+    #[inline]
+    pub fn to_bits(self, target_size: Size) -> Result<u128, Size> {
+        assert_ne!(target_size.bytes(), 0, "you should never look at the bits of a ZST");
+        if target_size.bytes() == u64::from(self.size.get()) {
+            self.check_data();
+            Ok(self.data)
+        } else {
+            Err(self.size())
+        }
+    }
+
+    #[inline]
+    pub fn try_to_machine_usize<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Result<u64, Size> {
+        Ok(self.to_bits(tcx.data_layout.pointer_size)? as u64)
+    }
+
+    /// Tries to convert the `ScalarInt` to an unsigned integer of the given size.
+    /// Fails if the size of the `ScalarInt` is unequal to `size` and returns the
+    /// `ScalarInt`s size in that case.
+    #[inline]
+    pub fn try_to_uint(self, size: Size) -> Result<u128, Size> {
+        self.to_bits(size)
+    }
+
+    // Tries to convert the `ScalarInt` to `u8`. Fails if the `size` of the `ScalarInt`
+    // in not equal to `Size { raw: 1 }` and returns the `size` value of the `ScalarInt` in
+    // that case.
+    #[inline]
+    pub fn try_to_u8(self) -> Result<u8, Size> {
+        self.to_bits(Size::from_bits(8)).map(|v| u8::try_from(v).unwrap())
+    }
+
+    /// Tries to convert the `ScalarInt` to `u16`. Fails if the size of the `ScalarInt`
+    /// in not equal to `Size { raw: 2 }` and returns the `size` value of the `ScalarInt` in
+    /// that case.
+    #[inline]
+    pub fn try_to_u16(self) -> Result<u16, Size> {
+        self.to_bits(Size::from_bits(16)).map(|v| u16::try_from(v).unwrap())
+    }
+
+    /// Tries to convert the `ScalarInt` to `u32`. Fails if the `size` of the `ScalarInt`
+    /// in not equal to `Size { raw: 4 }` and returns the `size` value of the `ScalarInt` in
+    /// that case.
+    #[inline]
+    pub fn try_to_u32(self) -> Result<u32, Size> {
+        self.to_bits(Size::from_bits(32)).map(|v| u32::try_from(v).unwrap())
+    }
+
+    /// Tries to convert the `ScalarInt` to `u64`. Fails if the `size` of the `ScalarInt`
+    /// in not equal to `Size { raw: 8 }` and returns the `size` value of the `ScalarInt` in
+    /// that case.
+    #[inline]
+    pub fn try_to_u64(self) -> Result<u64, Size> {
+        self.to_bits(Size::from_bits(64)).map(|v| u64::try_from(v).unwrap())
+    }
+
+    /// Tries to convert the `ScalarInt` to `u128`. Fails if the `size` of the `ScalarInt`
+    /// in not equal to `Size { raw: 16 }` and returns the `size` value of the `ScalarInt` in
+    /// that case.
+    #[inline]
+    pub fn try_to_u128(self) -> Result<u128, Size> {
+        self.to_bits(Size::from_bits(128))
+    }
+
+    /// Tries to convert the `ScalarInt` to a signed integer of the given size.
+    /// Fails if the size of the `ScalarInt` is unequal to `size` and returns the
+    /// `ScalarInt`s size in that case.
+    #[inline]
+    pub fn try_to_int(self, size: Size) -> Result<i128, Size> {
+        let b = self.to_bits(size)?;
+        Ok(size.sign_extend(b) as i128)
+    }
+
+    /// Tries to convert the `ScalarInt` to i8.
+    /// Fails if the size of the `ScalarInt` is unequal to `Size { raw: 1 }`
+    /// and returns the `ScalarInt`s size in that case.
+    pub fn try_to_i8(self) -> Result<i8, Size> {
+        self.try_to_int(Size::from_bits(8)).map(|v| i8::try_from(v).unwrap())
+    }
+
+    /// Tries to convert the `ScalarInt` to i16.
+    /// Fails if the size of the `ScalarInt` is unequal to `Size { raw: 2 }`
+    /// and returns the `ScalarInt`s size in that case.
+    pub fn try_to_i16(self) -> Result<i16, Size> {
+        self.try_to_int(Size::from_bits(16)).map(|v| i16::try_from(v).unwrap())
+    }
+
+    /// Tries to convert the `ScalarInt` to i32.
+    /// Fails if the size of the `ScalarInt` is unequal to `Size { raw: 4 }`
+    /// and returns the `ScalarInt`s size in that case.
+    pub fn try_to_i32(self) -> Result<i32, Size> {
+        self.try_to_int(Size::from_bits(32)).map(|v| i32::try_from(v).unwrap())
+    }
+
+    /// Tries to convert the `ScalarInt` to i64.
+    /// Fails if the size of the `ScalarInt` is unequal to `Size { raw: 8 }`
+    /// and returns the `ScalarInt`s size in that case.
+    pub fn try_to_i64(self) -> Result<i64, Size> {
+        self.try_to_int(Size::from_bits(64)).map(|v| i64::try_from(v).unwrap())
+    }
+
+    /// Tries to convert the `ScalarInt` to i128.
+    /// Fails if the size of the `ScalarInt` is unequal to `Size { raw: 16 }`
+    /// and returns the `ScalarInt`s size in that case.
+    pub fn try_to_i128(self) -> Result<i128, Size> {
+        self.try_to_int(Size::from_bits(128)).map(|v| i128::try_from(v).unwrap())
+    }
+}
+
+macro_rules! from {
+    ($($ty:ty),*) => {
+        $(
+            impl From<$ty> for ScalarInt {
+                #[inline]
+                fn from(u: $ty) -> Self {
+                    Self {
+                        data: u128::from(u),
+                        size: NonZeroU8::new(std::mem::size_of::<$ty>() as u8).unwrap(),
+                    }
+                }
+            }
+        )*
+    }
+}
+
+macro_rules! try_from {
+    ($($ty:ty),*) => {
+        $(
+            impl TryFrom<ScalarInt> for $ty {
+                type Error = Size;
+                #[inline]
+                fn try_from(int: ScalarInt) -> Result<Self, Size> {
+                    // The `unwrap` cannot fail because to_bits (if it succeeds)
+                    // is guaranteed to return a value that fits into the size.
+                    int.to_bits(Size::from_bytes(std::mem::size_of::<$ty>()))
+                       .map(|u| u.try_into().unwrap())
+                }
+            }
+        )*
+    }
+}
+
+from!(u8, u16, u32, u64, u128, bool);
+try_from!(u8, u16, u32, u64, u128);
+
+impl TryFrom<ScalarInt> for bool {
+    type Error = Size;
+    #[inline]
+    fn try_from(int: ScalarInt) -> Result<Self, Size> {
+        int.to_bits(Size::from_bytes(1)).and_then(|u| match u {
+            0 => Ok(false),
+            1 => Ok(true),
+            _ => Err(Size::from_bytes(1)),
+        })
+    }
+}
+
+impl From<char> for ScalarInt {
+    #[inline]
+    fn from(c: char) -> Self {
+        Self { data: c as u128, size: NonZeroU8::new(std::mem::size_of::<char>() as u8).unwrap() }
+    }
+}
+
+/// Error returned when a conversion from ScalarInt to char fails.
+#[derive(Debug)]
+pub struct CharTryFromScalarInt;
+
+impl TryFrom<ScalarInt> for char {
+    type Error = CharTryFromScalarInt;
+
+    #[inline]
+    fn try_from(int: ScalarInt) -> Result<Self, Self::Error> {
+        let Ok(bits) = int.to_bits(Size::from_bytes(std::mem::size_of::<char>())) else  {
+            return Err(CharTryFromScalarInt);
+        };
+        match char::from_u32(bits.try_into().unwrap()) {
+            Some(c) => Ok(c),
+            None => Err(CharTryFromScalarInt),
+        }
+    }
+}
+
+impl From<Single> for ScalarInt {
+    #[inline]
+    fn from(f: Single) -> Self {
+        // We trust apfloat to give us properly truncated data.
+        Self { data: f.to_bits(), size: NonZeroU8::new((Single::BITS / 8) as u8).unwrap() }
+    }
+}
+
+impl TryFrom<ScalarInt> for Single {
+    type Error = Size;
+    #[inline]
+    fn try_from(int: ScalarInt) -> Result<Self, Size> {
+        int.to_bits(Size::from_bytes(4)).map(Self::from_bits)
+    }
+}
+
+impl From<Double> for ScalarInt {
+    #[inline]
+    fn from(f: Double) -> Self {
+        // We trust apfloat to give us properly truncated data.
+        Self { data: f.to_bits(), size: NonZeroU8::new((Double::BITS / 8) as u8).unwrap() }
+    }
+}
+
+impl TryFrom<ScalarInt> for Double {
+    type Error = Size;
+    #[inline]
+    fn try_from(int: ScalarInt) -> Result<Self, Size> {
+        int.to_bits(Size::from_bytes(8)).map(Self::from_bits)
+    }
+}
+
+impl fmt::Debug for ScalarInt {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        // Dispatch to LowerHex below.
+        write!(f, "0x{:x}", self)
+    }
+}
+
+impl fmt::LowerHex for ScalarInt {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.check_data();
+        if f.alternate() {
+            // Like regular ints, alternate flag adds leading `0x`.
+            write!(f, "0x")?;
+        }
+        // Format as hex number wide enough to fit any value of the given `size`.
+        // So data=20, size=1 will be "0x14", but with size=4 it'll be "0x00000014".
+        // Using a block `{self.data}` here to force a copy instead of using `self.data`
+        // directly, because `write!` takes references to its formatting arguments and
+        // would thus borrow `self.data`. Since `Self`
+        // is a packed struct, that would create a possibly unaligned reference, which
+        // is UB.
+        write!(f, "{:01$x}", { self.data }, self.size.get() as usize * 2)
+    }
+}
+
+impl fmt::UpperHex for ScalarInt {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.check_data();
+        // Format as hex number wide enough to fit any value of the given `size`.
+        // So data=20, size=1 will be "0x14", but with size=4 it'll be "0x00000014".
+        // Using a block `{self.data}` here to force a copy instead of using `self.data`
+        // directly, because `write!` takes references to its formatting arguments and
+        // would thus borrow `self.data`. Since `Self`
+        // is a packed struct, that would create a possibly unaligned reference, which
+        // is UB.
+        write!(f, "{:01$X}", { self.data }, self.size.get() as usize * 2)
+    }
+}
+
+impl fmt::Display for ScalarInt {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.check_data();
+        write!(f, "{}", { self.data })
+    }
+}
diff --git a/compiler/rustc_middle/src/ty/consts/kind.rs b/compiler/rustc_middle/src/ty/consts/kind.rs
new file mode 100644
index 000000000..cb0137d2e
--- /dev/null
+++ b/compiler/rustc_middle/src/ty/consts/kind.rs
@@ -0,0 +1,239 @@
+use std::convert::TryInto;
+
+use crate::mir::interpret::{AllocId, ConstValue, Scalar};
+use crate::mir::Promoted;
+use crate::ty::subst::{InternalSubsts, SubstsRef};
+use crate::ty::ParamEnv;
+use crate::ty::{self, TyCtxt, TypeVisitable};
+use rustc_errors::ErrorGuaranteed;
+use rustc_hir::def_id::DefId;
+use rustc_macros::HashStable;
+use rustc_target::abi::Size;
+
+use super::ScalarInt;
+/// An unevaluated, potentially generic, constant.
+#[derive(Copy, Clone, Debug, Eq, PartialEq, PartialOrd, Ord, TyEncodable, TyDecodable, Lift)]
+#[derive(Hash, HashStable)]
+pub struct Unevaluated<'tcx, P = Option<Promoted>> {
+    pub def: ty::WithOptConstParam<DefId>,
+    pub substs: SubstsRef<'tcx>,
+    pub promoted: P,
+}
+
+impl<'tcx> Unevaluated<'tcx> {
+    #[inline]
+    pub fn shrink(self) -> Unevaluated<'tcx, ()> {
+        debug_assert_eq!(self.promoted, None);
+        Unevaluated { def: self.def, substs: self.substs, promoted: () }
+    }
+}
+
+impl<'tcx> Unevaluated<'tcx, ()> {
+    #[inline]
+    pub fn expand(self) -> Unevaluated<'tcx> {
+        Unevaluated { def: self.def, substs: self.substs, promoted: None }
+    }
+}
+
+impl<'tcx, P: Default> Unevaluated<'tcx, P> {
+    #[inline]
+    pub fn new(def: ty::WithOptConstParam<DefId>, substs: SubstsRef<'tcx>) -> Unevaluated<'tcx, P> {
+        Unevaluated { def, substs, promoted: Default::default() }
+    }
+}
+
+/// Represents a constant in Rust.
+#[derive(Copy, Clone, Debug, Eq, PartialEq, PartialOrd, Ord, TyEncodable, TyDecodable)]
+#[derive(Hash, HashStable)]
+pub enum ConstKind<'tcx> {
+    /// A const generic parameter.
+    Param(ty::ParamConst),
+
+    /// Infer the value of the const.
+    Infer(InferConst<'tcx>),
+
+    /// Bound const variable, used only when preparing a trait query.
+    Bound(ty::DebruijnIndex, ty::BoundVar),
+
+    /// A placeholder const - universally quantified higher-ranked const.
+    Placeholder(ty::PlaceholderConst<'tcx>),
+
+    /// Used in the HIR by using `Unevaluated` everywhere and later normalizing to one of the other
+    /// variants when the code is monomorphic enough for that.
+    Unevaluated(Unevaluated<'tcx>),
+
+    /// Used to hold computed value.
+    Value(ty::ValTree<'tcx>),
+
+    /// A placeholder for a const which could not be computed; this is
+    /// propagated to avoid useless error messages.
+    Error(ty::DelaySpanBugEmitted),
+}
+
+#[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
+static_assert_size!(ConstKind<'_>, 40);
+
+impl<'tcx> ConstKind<'tcx> {
+    #[inline]
+    pub fn try_to_value(self) -> Option<ty::ValTree<'tcx>> {
+        if let ConstKind::Value(val) = self { Some(val) } else { None }
+    }
+
+    #[inline]
+    pub fn try_to_scalar(self) -> Option<Scalar<AllocId>> {
+        self.try_to_value()?.try_to_scalar()
+    }
+
+    #[inline]
+    pub fn try_to_scalar_int(self) -> Option<ScalarInt> {
+        self.try_to_value()?.try_to_scalar_int()
+    }
+
+    #[inline]
+    pub fn try_to_bits(self, size: Size) -> Option<u128> {
+        self.try_to_scalar_int()?.to_bits(size).ok()
+    }
+
+    #[inline]
+    pub fn try_to_bool(self) -> Option<bool> {
+        self.try_to_scalar_int()?.try_into().ok()
+    }
+
+    #[inline]
+    pub fn try_to_machine_usize(self, tcx: TyCtxt<'tcx>) -> Option<u64> {
+        self.try_to_value()?.try_to_machine_usize(tcx)
+    }
+}
+
+/// An inference variable for a const, for use in const generics.
+#[derive(Copy, Clone, Debug, Eq, PartialEq, PartialOrd, Ord, TyEncodable, TyDecodable, Hash)]
+#[derive(HashStable)]
+pub enum InferConst<'tcx> {
+    /// Infer the value of the const.
+    Var(ty::ConstVid<'tcx>),
+    /// A fresh const variable. See `infer::freshen` for more details.
+    Fresh(u32),
+}
+
+enum EvalMode {
+    Typeck,
+    Mir,
+}
+
+enum EvalResult<'tcx> {
+    ValTree(ty::ValTree<'tcx>),
+    ConstVal(ConstValue<'tcx>),
+}
+
+impl<'tcx> ConstKind<'tcx> {
+    #[inline]
+    /// Tries to evaluate the constant if it is `Unevaluated`. If that doesn't succeed, return the
+    /// unevaluated constant.
+    pub fn eval(self, tcx: TyCtxt<'tcx>, param_env: ParamEnv<'tcx>) -> Self {
+        self.try_eval_for_typeck(tcx, param_env).and_then(Result::ok).map_or(self, ConstKind::Value)
+    }
+
+    #[inline]
+    /// Tries to evaluate the constant if it is `Unevaluated`. If that isn't possible or necessary
+    /// return `None`.
+    // FIXME(@lcnr): Completely rework the evaluation/normalization system for `ty::Const` once valtrees are merged.
+    pub fn try_eval_for_mir(
+        self,
+        tcx: TyCtxt<'tcx>,
+        param_env: ParamEnv<'tcx>,
+    ) -> Option<Result<ConstValue<'tcx>, ErrorGuaranteed>> {
+        match self.try_eval_inner(tcx, param_env, EvalMode::Mir) {
+            Some(Ok(EvalResult::ValTree(_))) => unreachable!(),
+            Some(Ok(EvalResult::ConstVal(v))) => Some(Ok(v)),
+            Some(Err(e)) => Some(Err(e)),
+            None => None,
+        }
+    }
+
+    #[inline]
+    /// Tries to evaluate the constant if it is `Unevaluated`. If that isn't possible or necessary
+    /// return `None`.
+    // FIXME(@lcnr): Completely rework the evaluation/normalization system for `ty::Const` once valtrees are merged.
+    pub fn try_eval_for_typeck(
+        self,
+        tcx: TyCtxt<'tcx>,
+        param_env: ParamEnv<'tcx>,
+    ) -> Option<Result<ty::ValTree<'tcx>, ErrorGuaranteed>> {
+        match self.try_eval_inner(tcx, param_env, EvalMode::Typeck) {
+            Some(Ok(EvalResult::ValTree(v))) => Some(Ok(v)),
+            Some(Ok(EvalResult::ConstVal(_))) => unreachable!(),
+            Some(Err(e)) => Some(Err(e)),
+            None => None,
+        }
+    }
+
+    #[inline]
+    fn try_eval_inner(
+        self,
+        tcx: TyCtxt<'tcx>,
+        param_env: ParamEnv<'tcx>,
+        eval_mode: EvalMode,
+    ) -> Option<Result<EvalResult<'tcx>, ErrorGuaranteed>> {
+        if let ConstKind::Unevaluated(unevaluated) = self {
+            use crate::mir::interpret::ErrorHandled;
+
+            // HACK(eddyb) this erases lifetimes even though `const_eval_resolve`
+            // also does later, but we want to do it before checking for
+            // inference variables.
+            // Note that we erase regions *before* calling `with_reveal_all_normalized`,
+            // so that we don't try to invoke this query with
+            // any region variables.
+            let param_env_and = tcx
+                .erase_regions(param_env)
+                .with_reveal_all_normalized(tcx)
+                .and(tcx.erase_regions(unevaluated));
+
+            // HACK(eddyb) when the query key would contain inference variables,
+            // attempt using identity substs and `ParamEnv` instead, that will succeed
+            // when the expression doesn't depend on any parameters.
+            // FIXME(eddyb, skinny121) pass `InferCtxt` into here when it's available, so that
+            // we can call `infcx.const_eval_resolve` which handles inference variables.
+            let param_env_and = if param_env_and.needs_infer() {
+                tcx.param_env(unevaluated.def.did).and(ty::Unevaluated {
+                    def: unevaluated.def,
+                    substs: InternalSubsts::identity_for_item(tcx, unevaluated.def.did),
+                    promoted: unevaluated.promoted,
+                })
+            } else {
+                param_env_and
+            };
+
+            // FIXME(eddyb) maybe the `const_eval_*` methods should take
+            // `ty::ParamEnvAnd` instead of having them separate.
+            let (param_env, unevaluated) = param_env_and.into_parts();
+            // try to resolve e.g. associated constants to their definition on an impl, and then
+            // evaluate the const.
+            match eval_mode {
+                EvalMode::Typeck => {
+                    match tcx.const_eval_resolve_for_typeck(param_env, unevaluated, None) {
+                        // NOTE(eddyb) `val` contains no lifetimes/types/consts,
+                        // and we use the original type, so nothing from `substs`
+                        // (which may be identity substs, see above),
+                        // can leak through `val` into the const we return.
+                        Ok(val) => Some(Ok(EvalResult::ValTree(val?))),
+                        Err(ErrorHandled::TooGeneric | ErrorHandled::Linted) => None,
+                        Err(ErrorHandled::Reported(e)) => Some(Err(e)),
+                    }
+                }
+                EvalMode::Mir => {
+                    match tcx.const_eval_resolve(param_env, unevaluated, None) {
+                        // NOTE(eddyb) `val` contains no lifetimes/types/consts,
+                        // and we use the original type, so nothing from `substs`
+                        // (which may be identity substs, see above),
+                        // can leak through `val` into the const we return.
+                        Ok(val) => Some(Ok(EvalResult::ConstVal(val))),
+                        Err(ErrorHandled::TooGeneric | ErrorHandled::Linted) => None,
+                        Err(ErrorHandled::Reported(e)) => Some(Err(e)),
+                    }
+                }
+            }
+        } else {
+            None
+        }
+    }
+}
diff --git a/compiler/rustc_middle/src/ty/consts/valtree.rs b/compiler/rustc_middle/src/ty/consts/valtree.rs
new file mode 100644
index 000000000..93707bb18
--- /dev/null
+++ b/compiler/rustc_middle/src/ty/consts/valtree.rs
@@ -0,0 +1,104 @@
+use super::ScalarInt;
+use crate::mir::interpret::{AllocId, Scalar};
+use crate::ty::{self, Ty, TyCtxt};
+use rustc_macros::{HashStable, TyDecodable, TyEncodable};
+
+#[derive(Copy, Clone, Debug, Hash, TyEncodable, TyDecodable, Eq, PartialEq, Ord, PartialOrd)]
+#[derive(HashStable)]
+/// This datastructure is used to represent the value of constants used in the type system.
+///
+/// We explicitly choose a different datastructure from the way values are processed within
+/// CTFE, as in the type system equal values (according to their `PartialEq`) must also have
+/// equal representation (`==` on the rustc data structure, e.g. `ValTree`) and vice versa.
+/// Since CTFE uses `AllocId` to represent pointers, it often happens that two different
+/// `AllocId`s point to equal values. So we may end up with different representations for
+/// two constants whose value is `&42`. Furthermore any kind of struct that has padding will
+/// have arbitrary values within that padding, even if the values of the struct are the same.
+///
+/// `ValTree` does not have this problem with representation, as it only contains integers or
+/// lists of (nested) `ValTree`.
+pub enum ValTree<'tcx> {
+    /// ZSTs, integers, `bool`, `char` are represented as scalars.
+    /// See the `ScalarInt` documentation for how `ScalarInt` guarantees that equal values
+    /// of these types have the same representation.
+    Leaf(ScalarInt),
+
+    //SliceOrStr(ValSlice<'tcx>),
+    // dont use SliceOrStr for now
+    /// The fields of any kind of aggregate. Structs, tuples and arrays are represented by
+    /// listing their fields' values in order.
+    /// Enums are represented by storing their discriminant as a field, followed by all
+    /// the fields of the variant.
+    Branch(&'tcx [ValTree<'tcx>]),
+}
+
+impl<'tcx> ValTree<'tcx> {
+    pub fn zst() -> Self {
+        Self::Branch(&[])
+    }
+
+    #[inline]
+    pub fn unwrap_leaf(self) -> ScalarInt {
+        match self {
+            Self::Leaf(s) => s,
+            _ => bug!("expected leaf, got {:?}", self),
+        }
+    }
+
+    #[inline]
+    pub fn unwrap_branch(self) -> &'tcx [Self] {
+        match self {
+            Self::Branch(branch) => branch,
+            _ => bug!("expected branch, got {:?}", self),
+        }
+    }
+
+    pub fn from_raw_bytes<'a>(tcx: TyCtxt<'tcx>, bytes: &'a [u8]) -> Self {
+        let branches = bytes.iter().map(|b| Self::Leaf(ScalarInt::from(*b)));
+        let interned = tcx.arena.alloc_from_iter(branches);
+
+        Self::Branch(interned)
+    }
+
+    pub fn from_scalar_int(i: ScalarInt) -> Self {
+        Self::Leaf(i)
+    }
+
+    pub fn try_to_scalar(self) -> Option<Scalar<AllocId>> {
+        self.try_to_scalar_int().map(Scalar::Int)
+    }
+
+    pub fn try_to_scalar_int(self) -> Option<ScalarInt> {
+        match self {
+            Self::Leaf(s) => Some(s),
+            Self::Branch(_) => None,
+        }
+    }
+
+    pub fn try_to_machine_usize(self, tcx: TyCtxt<'tcx>) -> Option<u64> {
+        self.try_to_scalar_int().map(|s| s.try_to_machine_usize(tcx).ok()).flatten()
+    }
+
+    /// Get the values inside the ValTree as a slice of bytes. This only works for
+    /// constants with types &str, &[u8], or [u8; _].
+    pub fn try_to_raw_bytes(self, tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> Option<&'tcx [u8]> {
+        match ty.kind() {
+            ty::Ref(_, inner_ty, _) => match inner_ty.kind() {
+                // `&str` can be interpreted as raw bytes
+                ty::Str => {}
+                // `&[u8]` can be interpreted as raw bytes
+                ty::Slice(slice_ty) if *slice_ty == tcx.types.u8 => {}
+                // other `&_` can't be interpreted as raw bytes
+                _ => return None,
+            },
+            // `[u8; N]` can be interpreted as raw bytes
+            ty::Array(array_ty, _) if *array_ty == tcx.types.u8 => {}
+            // Otherwise, type cannot be interpreted as raw bytes
+            _ => return None,
+        }
+
+        Some(tcx.arena.alloc_from_iter(
+            self.unwrap_branch().into_iter().map(|v| v.unwrap_leaf().try_to_u8().unwrap()),
+        ))
+    }
+}