Auto merge of #95976 - b-naber:valtree-constval-conversion, r=oli-obk

Implement Valtree to ConstValue conversion

Once we start to use `ValTree`s in the type system we will need to be able to convert them into `ConstValue` instances, which we want to continue to use after MIR construction.

r? `@oli-obk`

cc `@RalfJung`

15 files changed, 667 insertions, 162 deletions

diff --git a/compiler/rustc_const_eval/src/const_eval/eval_queries.rs b/compiler/rustc_const_eval/src/const_eval/eval_queries.rs
index 7cca6178ab2..38fecf7232e 100644
--- a/compiler/rustc_const_eval/src/const_eval/eval_queries.rs
+++ b/compiler/rustc_const_eval/src/const_eval/eval_queries.rs
@@ -106,6 +106,7 @@ pub(super) fn mk_eval_cx<'mir, 'tcx>(
 
 /// This function converts an interpreter value into a constant that is meant for use in the
 /// type system.
+#[instrument(skip(ecx), level = "debug")]
 pub(super) fn op_to_const<'tcx>(
     ecx: &CompileTimeEvalContext<'_, 'tcx>,
     op: &OpTy<'tcx>,
@@ -140,21 +141,26 @@ pub(super) fn op_to_const<'tcx>(
         op.try_as_mplace()
     };
 
+    debug!(?immediate);
+
     // We know `offset` is relative to the allocation, so we can use `into_parts`.
-    let to_const_value = |mplace: &MPlaceTy<'_>| match mplace.ptr.into_parts() {
-        (Some(alloc_id), offset) => {
-            let alloc = ecx.tcx.global_alloc(alloc_id).unwrap_memory();
-            ConstValue::ByRef { alloc, offset }
-        }
-        (None, offset) => {
-            assert!(mplace.layout.is_zst());
-            assert_eq!(
-                offset.bytes() % mplace.layout.align.abi.bytes(),
-                0,
-                "this MPlaceTy must come from a validated constant, thus we can assume the \
+    let to_const_value = |mplace: &MPlaceTy<'_>| {
+        debug!("to_const_value(mplace: {:?})", mplace);
+        match mplace.ptr.into_parts() {
+            (Some(alloc_id), offset) => {
+                let alloc = ecx.tcx.global_alloc(alloc_id).unwrap_memory();
+                ConstValue::ByRef { alloc, offset }
+            }
+            (None, offset) => {
+                assert!(mplace.layout.is_zst());
+                assert_eq!(
+                    offset.bytes() % mplace.layout.align.abi.bytes(),
+                    0,
+                    "this MPlaceTy must come from a validated constant, thus we can assume the \
                 alignment is correct",
-            );
-            ConstValue::Scalar(Scalar::ZST)
+                );
+                ConstValue::Scalar(Scalar::ZST)
+            }
         }
     };
     match immediate {
@@ -166,6 +172,7 @@ pub(super) fn op_to_const<'tcx>(
                 ScalarMaybeUninit::Uninit => to_const_value(&op.assert_mem_place()),
             },
             Immediate::ScalarPair(a, b) => {
+                debug!("ScalarPair(a: {:?}, b: {:?})", a, b);
                 // We know `offset` is relative to the allocation, so we can use `into_parts`.
                 let (data, start) =
                     match ecx.scalar_to_ptr(a.check_init().unwrap()).unwrap().into_parts() {
@@ -209,7 +216,10 @@ fn turn_into_const_value<'tcx>(
     );
 
     // Turn this into a proper constant.
-    op_to_const(&ecx, &mplace.into())
+    let const_val = op_to_const(&ecx, &mplace.into());
+    debug!(?const_val);
+
+    const_val
 }
 
 pub fn eval_to_const_value_raw_provider<'tcx>(
diff --git a/compiler/rustc_const_eval/src/const_eval/mod.rs b/compiler/rustc_const_eval/src/const_eval/mod.rs
index 68f9bee593f..96c18d488ee 100644
--- a/compiler/rustc_const_eval/src/const_eval/mod.rs
+++ b/compiler/rustc_const_eval/src/const_eval/mod.rs
@@ -3,29 +3,26 @@
 use std::convert::TryFrom;
 
 use rustc_hir::Mutability;
-use rustc_middle::ty::layout::HasTyCtxt;
+use rustc_middle::mir;
 use rustc_middle::ty::{self, TyCtxt};
-use rustc_middle::{
-    mir::{self, interpret::ConstAlloc},
-    ty::ScalarInt,
-};
 use rustc_span::{source_map::DUMMY_SP, symbol::Symbol};
-use rustc_target::abi::VariantIdx;
 
 use crate::interpret::{
-    intern_const_alloc_recursive, ConstValue, InternKind, InterpCx, InterpResult, MPlaceTy,
-    MemPlaceMeta, Scalar,
+    intern_const_alloc_recursive, ConstValue, InternKind, InterpCx, InterpResult, MemPlaceMeta,
+    Scalar,
 };
 
 mod error;
 mod eval_queries;
 mod fn_queries;
 mod machine;
+mod valtrees;
 
 pub use error::*;
 pub use eval_queries::*;
 pub use fn_queries::*;
 pub use machine::*;
+pub(crate) use valtrees::{const_to_valtree, valtree_to_const_value};
 
 pub(crate) fn const_caller_location(
     tcx: TyCtxt<'_>,
@@ -41,128 +38,6 @@ pub(crate) fn const_caller_location(
     ConstValue::Scalar(Scalar::from_maybe_pointer(loc_place.ptr, &tcx))
 }
 
-/// Convert an evaluated constant to a type level constant
-pub(crate) fn const_to_valtree<'tcx>(
-    tcx: TyCtxt<'tcx>,
-    param_env: ty::ParamEnv<'tcx>,
-    raw: ConstAlloc<'tcx>,
-) -> Option<ty::ValTree<'tcx>> {
-    let ecx = mk_eval_cx(
-        tcx, DUMMY_SP, param_env,
-        // It is absolutely crucial for soundness that
-        // we do not read from static items or other mutable memory.
-        false,
-    );
-    let place = ecx.raw_const_to_mplace(raw).unwrap();
-    const_to_valtree_inner(&ecx, &place)
-}
-
-#[instrument(skip(ecx), level = "debug")]
-fn branches<'tcx>(
-    ecx: &CompileTimeEvalContext<'tcx, 'tcx>,
-    place: &MPlaceTy<'tcx>,
-    n: usize,
-    variant: Option<VariantIdx>,
-) -> Option<ty::ValTree<'tcx>> {
-    let place = match variant {
-        Some(variant) => ecx.mplace_downcast(&place, variant).unwrap(),
-        None => *place,
-    };
-    let variant = variant.map(|variant| Some(ty::ValTree::Leaf(ScalarInt::from(variant.as_u32()))));
-    debug!(?place, ?variant);
-
-    let fields = (0..n).map(|i| {
-        let field = ecx.mplace_field(&place, i).unwrap();
-        const_to_valtree_inner(ecx, &field)
-    });
-    // For enums, we prepend their variant index before the variant's fields so we can figure out
-    // the variant again when just seeing a valtree.
-    let branches = variant.into_iter().chain(fields);
-    Some(ty::ValTree::Branch(ecx.tcx.arena.alloc_from_iter(branches.collect::<Option<Vec<_>>>()?)))
-}
-
-fn slice_branches<'tcx>(
-    ecx: &CompileTimeEvalContext<'tcx, 'tcx>,
-    place: &MPlaceTy<'tcx>,
-) -> Option<ty::ValTree<'tcx>> {
-    let n = place.len(&ecx.tcx()).expect(&format!("expected to use len of place {:?}", place));
-    let branches = (0..n).map(|i| {
-        let place_elem = ecx.mplace_index(place, i).unwrap();
-        const_to_valtree_inner(ecx, &place_elem)
-    });
-
-    Some(ty::ValTree::Branch(ecx.tcx.arena.alloc_from_iter(branches.collect::<Option<Vec<_>>>()?)))
-}
-
-#[instrument(skip(ecx), level = "debug")]
-fn const_to_valtree_inner<'tcx>(
-    ecx: &CompileTimeEvalContext<'tcx, 'tcx>,
-    place: &MPlaceTy<'tcx>,
-) -> Option<ty::ValTree<'tcx>> {
-    match place.layout.ty.kind() {
-        ty::FnDef(..) => Some(ty::ValTree::zst()),
-        ty::Bool | ty::Int(_) | ty::Uint(_) | ty::Float(_) | ty::Char => {
-            let val = ecx.read_immediate(&place.into()).unwrap();
-            let val = val.to_scalar().unwrap();
-            Some(ty::ValTree::Leaf(val.assert_int()))
-        }
-
-        // Raw pointers are not allowed in type level constants, as we cannot properly test them for
-        // equality at compile-time (see `ptr_guaranteed_eq`/`_ne`).
-        // Technically we could allow function pointers (represented as `ty::Instance`), but this is not guaranteed to
-        // agree with runtime equality tests.
-        ty::FnPtr(_) | ty::RawPtr(_) => None,
-
-        ty::Ref(_, _, _)  => {
-            let derefd_place = ecx.deref_operand(&place.into()).unwrap_or_else(|e| bug!("couldn't deref {:?}, error: {:?}", place, e));
-            debug!(?derefd_place);
-
-            const_to_valtree_inner(ecx, &derefd_place)
-        }
-
-        ty::Str | ty::Slice(_) | ty::Array(_, _) => {
-            let valtree = slice_branches(ecx, place);
-            debug!(?valtree);
-
-            valtree
-        }
-        // Trait objects are not allowed in type level constants, as we have no concept for
-        // resolving their backing type, even if we can do that at const eval time. We may
-        // hypothetically be able to allow `dyn StructuralEq` trait objects in the future,
-        // but it is unclear if this is useful.
-        ty::Dynamic(..) => None,
-
-        ty::Tuple(substs) => branches(ecx, place, substs.len(), None),
-
-        ty::Adt(def, _) => {
-            if def.variants().is_empty() {
-                bug!("uninhabited types should have errored and never gotten converted to valtree")
-            }
-
-            let variant = ecx.read_discriminant(&place.into()).unwrap().1;
-
-            branches(ecx, place, def.variant(variant).fields.len(), def.is_enum().then_some(variant))
-        }
-
-        ty::Never
-        | ty::Error(_)
-        | ty::Foreign(..)
-        | ty::Infer(ty::FreshIntTy(_))
-        | ty::Infer(ty::FreshFloatTy(_))
-        | ty::Projection(..)
-        | ty::Param(_)
-        | ty::Bound(..)
-        | ty::Placeholder(..)
-        // FIXME(oli-obk): we could look behind opaque types
-        | ty::Opaque(..)
-        | ty::Infer(_)
-        // FIXME(oli-obk): we can probably encode closures just like structs
-        | ty::Closure(..)
-        | ty::Generator(..)
-        | ty::GeneratorWitness(..) => None,
-    }
-}
-
 /// This function should never fail for validated constants. However, it is also invoked from the
 /// pretty printer which might attempt to format invalid constants and in that case it might fail.
 pub(crate) fn try_destructure_const<'tcx>(
@@ -202,6 +77,7 @@ pub(crate) fn try_destructure_const<'tcx>(
     Ok(mir::DestructuredConst { variant, fields })
 }
 
+#[instrument(skip(tcx), level = "debug")]
 pub(crate) fn deref_const<'tcx>(
     tcx: TyCtxt<'tcx>,
     param_env: ty::ParamEnv<'tcx>,
diff --git a/compiler/rustc_const_eval/src/const_eval/valtrees.rs b/compiler/rustc_const_eval/src/const_eval/valtrees.rs
new file mode 100644
index 00000000000..374179d0cc2
--- /dev/null
+++ b/compiler/rustc_const_eval/src/const_eval/valtrees.rs
@@ -0,0 +1,459 @@
+use super::eval_queries::{mk_eval_cx, op_to_const};
+use super::machine::CompileTimeEvalContext;
+use crate::interpret::{
+    intern_const_alloc_recursive, ConstValue, ImmTy, Immediate, InternKind, MemPlaceMeta,
+    MemoryKind, PlaceTy, Scalar, ScalarMaybeUninit,
+};
+use rustc_middle::mir::interpret::ConstAlloc;
+use rustc_middle::ty::{self, ScalarInt, Ty, TyCtxt};
+use rustc_span::source_map::DUMMY_SP;
+use rustc_target::abi::{Align, VariantIdx};
+
+use crate::interpret::MPlaceTy;
+use crate::interpret::Value;
+
+/// Convert an evaluated constant to a type level constant
+#[instrument(skip(tcx), level = "debug")]
+pub(crate) fn const_to_valtree<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    param_env: ty::ParamEnv<'tcx>,
+    raw: ConstAlloc<'tcx>,
+) -> Option<ty::ValTree<'tcx>> {
+    let ecx = mk_eval_cx(
+        tcx, DUMMY_SP, param_env,
+        // It is absolutely crucial for soundness that
+        // we do not read from static items or other mutable memory.
+        false,
+    );
+    let place = ecx.raw_const_to_mplace(raw).unwrap();
+    const_to_valtree_inner(&ecx, &place)
+}
+
+#[instrument(skip(ecx), level = "debug")]
+fn branches<'tcx>(
+    ecx: &CompileTimeEvalContext<'tcx, 'tcx>,
+    place: &MPlaceTy<'tcx>,
+    n: usize,
+    variant: Option<VariantIdx>,
+) -> Option<ty::ValTree<'tcx>> {
+    let place = match variant {
+        Some(variant) => ecx.mplace_downcast(&place, variant).unwrap(),
+        None => *place,
+    };
+    let variant = variant.map(|variant| Some(ty::ValTree::Leaf(ScalarInt::from(variant.as_u32()))));
+    debug!(?place, ?variant);
+
+    let fields = (0..n).map(|i| {
+        let field = ecx.mplace_field(&place, i).unwrap();
+        const_to_valtree_inner(ecx, &field)
+    });
+    // For enums, we preped their variant index before the variant's fields so we can figure out
+    // the variant again when just seeing a valtree.
+    let branches = variant.into_iter().chain(fields);
+    Some(ty::ValTree::Branch(ecx.tcx.arena.alloc_from_iter(branches.collect::<Option<Vec<_>>>()?)))
+}
+
+#[instrument(skip(ecx), level = "debug")]
+fn slice_branches<'tcx>(
+    ecx: &CompileTimeEvalContext<'tcx, 'tcx>,
+    place: &MPlaceTy<'tcx>,
+) -> Option<ty::ValTree<'tcx>> {
+    let n = place.len(&ecx.tcx.tcx).expect(&format!("expected to use len of place {:?}", place));
+    let branches = (0..n).map(|i| {
+        let place_elem = ecx.mplace_index(place, i).unwrap();
+        const_to_valtree_inner(ecx, &place_elem)
+    });
+
+    Some(ty::ValTree::Branch(ecx.tcx.arena.alloc_from_iter(branches.collect::<Option<Vec<_>>>()?)))
+}
+
+#[instrument(skip(ecx), level = "debug")]
+fn const_to_valtree_inner<'tcx>(
+    ecx: &CompileTimeEvalContext<'tcx, 'tcx>,
+    place: &MPlaceTy<'tcx>,
+) -> Option<ty::ValTree<'tcx>> {
+    match place.layout.ty.kind() {
+        ty::FnDef(..) => Some(ty::ValTree::zst()),
+        ty::Bool | ty::Int(_) | ty::Uint(_) | ty::Float(_) | ty::Char => {
+            let val = ecx.read_immediate(&place.into()).unwrap();
+            let val = val.to_scalar().unwrap();
+            Some(ty::ValTree::Leaf(val.assert_int()))
+        }
+
+        // Raw pointers are not allowed in type level constants, as we cannot properly test them for
+        // equality at compile-time (see `ptr_guaranteed_eq`/`_ne`).
+        // Technically we could allow function pointers (represented as `ty::Instance`), but this is not guaranteed to
+        // agree with runtime equality tests.
+        ty::FnPtr(_) | ty::RawPtr(_) => None,
+
+        ty::Ref(_, _, _)  => {
+            let derefd_place = ecx.deref_operand(&place.into()).unwrap_or_else(|e| bug!("couldn't deref {:?}, error: {:?}", place, e));
+            debug!(?derefd_place);
+
+            const_to_valtree_inner(ecx, &derefd_place)
+        }
+
+        ty::Str | ty::Slice(_) | ty::Array(_, _) => {
+            let valtree = slice_branches(ecx, place);
+            debug!(?valtree);
+
+            valtree
+        }
+        // Trait objects are not allowed in type level constants, as we have no concept for
+        // resolving their backing type, even if we can do that at const eval time. We may
+        // hypothetically be able to allow `dyn StructuralEq` trait objects in the future,
+        // but it is unclear if this is useful.
+        ty::Dynamic(..) => None,
+
+        ty::Tuple(substs) => branches(ecx, place, substs.len(), None),
+
+        ty::Adt(def, _) => {
+            if def.is_union() {
+                return None
+            } else if def.variants().is_empty() {
+                bug!("uninhabited types should have errored and never gotten converted to valtree")
+            }
+
+            let variant = ecx.read_discriminant(&place.into()).unwrap().1;
+
+            branches(ecx, place, def.variant(variant).fields.len(), def.is_enum().then_some(variant))
+        }
+
+        ty::Never
+        | ty::Error(_)
+        | ty::Foreign(..)
+        | ty::Infer(ty::FreshIntTy(_))
+        | ty::Infer(ty::FreshFloatTy(_))
+        | ty::Projection(..)
+        | ty::Param(_)
+        | ty::Bound(..)
+        | ty::Placeholder(..)
+        // FIXME(oli-obk): we could look behind opaque types
+        | ty::Opaque(..)
+        | ty::Infer(_)
+        // FIXME(oli-obk): we can probably encode closures just like structs
+        | ty::Closure(..)
+        | ty::Generator(..)
+        | ty::GeneratorWitness(..) => None,
+    }
+}
+
+#[instrument(skip(ecx), level = "debug")]
+fn create_mplace_from_layout<'tcx>(
+    ecx: &mut CompileTimeEvalContext<'tcx, 'tcx>,
+    ty: Ty<'tcx>,
+) -> MPlaceTy<'tcx> {
+    let tcx = ecx.tcx;
+    let param_env = ecx.param_env;
+    let layout = tcx.layout_of(param_env.and(ty)).unwrap();
+    debug!(?layout);
+
+    ecx.allocate(layout, MemoryKind::Stack).unwrap()
+}
+
+// Walks custom DSTs and gets the type of the unsized field and the number of elements
+// in the unsized field.
+fn get_info_on_unsized_field<'tcx>(
+    ty: Ty<'tcx>,
+    valtree: ty::ValTree<'tcx>,
+    tcx: TyCtxt<'tcx>,
+) -> (Ty<'tcx>, usize) {
+    let mut last_valtree = valtree;
+    let tail = tcx.struct_tail_with_normalize(
+        ty,
+        |ty| ty,
+        || {
+            let branches = last_valtree.unwrap_branch();
+            last_valtree = branches[branches.len() - 1];
+            debug!(?branches, ?last_valtree);
+        },
+    );
+    let unsized_inner_ty = match tail.kind() {
+        ty::Slice(t) => *t,
+        ty::Str => tail,
+        _ => bug!("expected Slice or Str"),
+    };
+
+    // Have to adjust type for ty::Str
+    let unsized_inner_ty = match unsized_inner_ty.kind() {
+        ty::Str => tcx.mk_ty(ty::Uint(ty::UintTy::U8)),
+        _ => unsized_inner_ty,
+    };
+
+    // Get the number of elements in the unsized field
+    let num_elems = last_valtree.unwrap_branch().len();
+
+    (unsized_inner_ty, num_elems)
+}
+
+#[instrument(skip(ecx), level = "debug")]
+fn create_pointee_place<'tcx>(
+    ecx: &mut CompileTimeEvalContext<'tcx, 'tcx>,
+    ty: Ty<'tcx>,
+    valtree: ty::ValTree<'tcx>,
+) -> MPlaceTy<'tcx> {
+    let tcx = ecx.tcx.tcx;
+
+    if !ty.is_sized(ecx.tcx, ty::ParamEnv::empty()) {
+        // We need to create `Allocation`s for custom DSTs
+
+        let (unsized_inner_ty, num_elems) = get_info_on_unsized_field(ty, valtree, tcx);
+        let unsized_inner_ty = match unsized_inner_ty.kind() {
+            ty::Str => tcx.mk_ty(ty::Uint(ty::UintTy::U8)),
+            _ => unsized_inner_ty,
+        };
+        let unsized_inner_ty_size =
+            tcx.layout_of(ty::ParamEnv::empty().and(unsized_inner_ty)).unwrap().layout.size();
+        debug!(?unsized_inner_ty, ?unsized_inner_ty_size, ?num_elems);
+
+        // for custom DSTs only the last field/element is unsized, but we need to also allocate
+        // space for the other fields/elements
+        let layout = tcx.layout_of(ty::ParamEnv::empty().and(ty)).unwrap();
+        let size_of_sized_part = layout.layout.size();
+
+        // Get the size of the memory behind the DST
+        let dst_size = unsized_inner_ty_size.checked_mul(num_elems as u64, &tcx).unwrap();
+
+        let ptr = ecx
+            .allocate_ptr(
+                size_of_sized_part.checked_add(dst_size, &tcx).unwrap(),
+                Align::from_bytes(1).unwrap(),
+                MemoryKind::Stack,
+            )
+            .unwrap();
+        debug!(?ptr);
+
+        let mut place = MPlaceTy::from_aligned_ptr(ptr.into(), layout);
+        place.meta = MemPlaceMeta::Meta(Scalar::from_u64(num_elems as u64));
+        debug!(?place);
+
+        place
+    } else {
+        create_mplace_from_layout(ecx, ty)
+    }
+}
+
+/// Converts a `ValTree` to a `ConstValue`, which is needed after mir
+/// construction has finished.
+// FIXME Merge `valtree_to_const_value` and `fill_place_recursively` into one function
+#[instrument(skip(tcx), level = "debug")]
+pub fn valtree_to_const_value<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    param_env_ty: ty::ParamEnvAnd<'tcx, Ty<'tcx>>,
+    valtree: ty::ValTree<'tcx>,
+) -> ConstValue<'tcx> {
+    // Basic idea: We directly construct `Scalar` values from trivial `ValTree`s
+    // (those for constants with type bool, int, uint, float or char).
+    // For all other types we create an `MPlace` and fill that by walking
+    // the `ValTree` and using `place_projection` and `place_field` to
+    // create inner `MPlace`s which are filled recursively.
+    // FIXME Does this need an example?
+
+    let (param_env, ty) = param_env_ty.into_parts();
+    let mut ecx = mk_eval_cx(tcx, DUMMY_SP, param_env, false);
+
+    match ty.kind() {
+        ty::FnDef(..) => {
+            assert!(valtree.unwrap_branch().is_empty());
+            ConstValue::Scalar(Scalar::ZST)
+        }
+        ty::Bool | ty::Int(_) | ty::Uint(_) | ty::Float(_) | ty::Char => match valtree {
+            ty::ValTree::Leaf(scalar_int) => ConstValue::Scalar(Scalar::Int(scalar_int)),
+            ty::ValTree::Branch(_) => bug!(
+                "ValTrees for Bool, Int, Uint, Float or Char should have the form ValTree::Leaf"
+            ),
+        },
+        ty::Ref(_, _, _) | ty::Tuple(_) | ty::Array(_, _) | ty::Adt(..) => {
+            let mut place = match ty.kind() {
+                ty::Ref(_, inner_ty, _) => {
+                    // Need to create a place for the pointee to fill for Refs
+                    create_pointee_place(&mut ecx, *inner_ty, valtree)
+                }
+                _ => create_mplace_from_layout(&mut ecx, ty),
+            };
+            debug!(?place);
+
+            fill_place_recursively(&mut ecx, &mut place, valtree);
+            dump_place(&ecx, place.into());
+            intern_const_alloc_recursive(&mut ecx, InternKind::Constant, &place).unwrap();
+
+            let const_val = match ty.kind() {
+                ty::Ref(_, _, _) => {
+                    let ref_place = place.to_ref(&tcx);
+                    let imm =
+                        ImmTy::from_immediate(ref_place, tcx.layout_of(param_env_ty).unwrap());
+
+                    op_to_const(&ecx, &imm.into())
+                }
+                _ => op_to_const(&ecx, &place.into()),
+            };
+            debug!(?const_val);
+
+            const_val
+        }
+        ty::Never
+        | ty::Error(_)
+        | ty::Foreign(..)
+        | ty::Infer(ty::FreshIntTy(_))
+        | ty::Infer(ty::FreshFloatTy(_))
+        | ty::Projection(..)
+        | ty::Param(_)
+        | ty::Bound(..)
+        | ty::Placeholder(..)
+        | ty::Opaque(..)
+        | ty::Infer(_)
+        | ty::Closure(..)
+        | ty::Generator(..)
+        | ty::GeneratorWitness(..)
+        | ty::FnPtr(_)
+        | ty::RawPtr(_)
+        | ty::Str
+        | ty::Slice(_)
+        | ty::Dynamic(..) => bug!("no ValTree should have been created for type {:?}", ty.kind()),
+    }
+}
+
+// FIXME Needs a better/correct name
+#[instrument(skip(ecx), level = "debug")]
+fn fill_place_recursively<'tcx>(
+    ecx: &mut CompileTimeEvalContext<'tcx, 'tcx>,
+    place: &mut MPlaceTy<'tcx>,
+    valtree: ty::ValTree<'tcx>,
+) {
+    // This will match on valtree and write the value(s) corresponding to the ValTree
+    // inside the place recursively.
+
+    let tcx = ecx.tcx.tcx;
+    let ty = place.layout.ty;
+
+    match ty.kind() {
+        ty::FnDef(_, _) => {
+            ecx.write_immediate(
+                Immediate::Scalar(ScalarMaybeUninit::Scalar(Scalar::ZST)),
+                &(*place).into(),
+            )
+            .unwrap();
+        }
+        ty::Bool | ty::Int(_) | ty::Uint(_) | ty::Float(_) | ty::Char => {
+            let scalar_int = valtree.unwrap_leaf();
+            debug!("writing trivial valtree {:?} to place {:?}", scalar_int, place);
+            ecx.write_immediate(
+                Immediate::Scalar(ScalarMaybeUninit::Scalar(scalar_int.into())),
+                &(*place).into(),
+            )
+            .unwrap();
+        }
+        ty::Ref(_, inner_ty, _) => {
+            let mut pointee_place = create_pointee_place(ecx, *inner_ty, valtree);
+            debug!(?pointee_place);
+
+            fill_place_recursively(ecx, &mut pointee_place, valtree);
+            dump_place(ecx, pointee_place.into());
+            intern_const_alloc_recursive(ecx, InternKind::Constant, &pointee_place).unwrap();
+
+            let imm = match inner_ty.kind() {
+                ty::Slice(_) | ty::Str => {
+                    let len = valtree.unwrap_branch().len();
+                    let len_scalar = ScalarMaybeUninit::Scalar(Scalar::from_u64(len as u64));
+
+                    Immediate::ScalarPair(
+                        ScalarMaybeUninit::from_maybe_pointer((*pointee_place).ptr, &tcx),
+                        len_scalar,
+                    )
+                }
+                _ => pointee_place.to_ref(&tcx),
+            };
+            debug!(?imm);
+
+            ecx.write_immediate(imm, &(*place).into()).unwrap();
+        }
+        ty::Adt(_, _) | ty::Tuple(_) | ty::Array(_, _) | ty::Str | ty::Slice(_) => {
+            let branches = valtree.unwrap_branch();
+
+            // Need to downcast place for enums
+            let (place_adjusted, branches, variant_idx) = match ty.kind() {
+                ty::Adt(def, _) if def.is_enum() => {
+                    // First element of valtree corresponds to variant
+                    let scalar_int = branches[0].unwrap_leaf();
+                    let variant_idx = VariantIdx::from_u32(scalar_int.try_to_u32().unwrap());
+                    let variant = def.variant(variant_idx);
+                    debug!(?variant);
+
+                    (
+                        place.project_downcast(ecx, variant_idx).unwrap(),
+                        &branches[1..],
+                        Some(variant_idx),
+                    )
+                }
+                _ => (*place, branches, None),
+            };
+            debug!(?place_adjusted, ?branches);
+
+            // Create the places (by indexing into `place`) for the fields and fill
+            // them recursively
+            for (i, inner_valtree) in branches.iter().enumerate() {
+                debug!(?i, ?inner_valtree);
+
+                let mut place_inner = match ty.kind() {
+                    ty::Str | ty::Slice(_) => ecx.mplace_index(&place, i as u64).unwrap(),
+                    _ if !ty.is_sized(ecx.tcx, ty::ParamEnv::empty())
+                        && i == branches.len() - 1 =>
+                    {
+                        // Note: For custom DSTs we need to manually process the last unsized field.
+                        // We created a `Pointer` for the `Allocation` of the complete sized version of
+                        // the Adt in `create_pointee_place` and now we fill that `Allocation` with the
+                        // values in the ValTree. For the unsized field we have to additionally add the meta
+                        // data.
+
+                        let (unsized_inner_ty, num_elems) =
+                            get_info_on_unsized_field(ty, valtree, tcx);
+                        debug!(?unsized_inner_ty);
+
+                        let inner_ty = match ty.kind() {
+                            ty::Adt(def, substs) => {
+                                def.variant(VariantIdx::from_u32(0)).fields[i].ty(tcx, substs)
+                            }
+                            ty::Tuple(inner_tys) => inner_tys[i],
+                            _ => bug!("unexpected unsized type {:?}", ty),
+                        };
+
+                        let inner_layout =
+                            tcx.layout_of(ty::ParamEnv::empty().and(inner_ty)).unwrap();
+                        debug!(?inner_layout);
+
+                        let offset = place_adjusted.layout.fields.offset(i);
+                        place
+                            .offset(
+                                offset,
+                                MemPlaceMeta::Meta(Scalar::from_u64(num_elems as u64)),
+                                inner_layout,
+                                &tcx,
+                            )
+                            .unwrap()
+                    }
+                    _ => ecx.mplace_field(&place_adjusted, i).unwrap(),
+                };
+
+                debug!(?place_inner);
+                fill_place_recursively(ecx, &mut place_inner, *inner_valtree);
+                dump_place(&ecx, place_inner.into());
+            }
+
+            debug!("dump of place_adjusted:");
+            dump_place(ecx, place_adjusted.into());
+
+            if let Some(variant_idx) = variant_idx {
+                // don't forget filling the place with the discriminant of the enum
+                ecx.write_discriminant(variant_idx, &(*place).into()).unwrap();
+            }
+
+            debug!("dump of place after writing discriminant:");
+            dump_place(ecx, (*place).into());
+        }
+        _ => bug!("shouldn't have created a ValTree for {:?}", ty),
+    }
+}
+
+fn dump_place<'tcx>(ecx: &CompileTimeEvalContext<'tcx, 'tcx>, place: PlaceTy<'tcx>) {
+    trace!("{:?}", ecx.dump_place(*place));
+}
diff --git a/compiler/rustc_const_eval/src/interpret/mod.rs b/compiler/rustc_const_eval/src/interpret/mod.rs
index 2b9fe565997..69d6c8470a2 100644
--- a/compiler/rustc_const_eval/src/interpret/mod.rs
+++ b/compiler/rustc_const_eval/src/interpret/mod.rs
@@ -27,7 +27,7 @@ pub use self::memory::{AllocCheck, AllocRef, AllocRefMut, FnVal, Memory, MemoryK
 pub use self::operand::{ImmTy, Immediate, OpTy, Operand};
 pub use self::place::{MPlaceTy, MemPlace, MemPlaceMeta, Place, PlaceTy};
 pub use self::validity::{CtfeValidationMode, RefTracking};
-pub use self::visitor::{MutValueVisitor, ValueVisitor};
+pub use self::visitor::{MutValueVisitor, Value, ValueVisitor};
 
 crate use self::intrinsics::eval_nullary_intrinsic;
 use eval_context::{from_known_layout, mir_assign_valid_types};
diff --git a/compiler/rustc_const_eval/src/interpret/operand.rs b/compiler/rustc_const_eval/src/interpret/operand.rs
index dfc0028e87f..f2d833b3202 100644
--- a/compiler/rustc_const_eval/src/interpret/operand.rs
+++ b/compiler/rustc_const_eval/src/interpret/operand.rs
@@ -424,6 +424,7 @@ impl<'mir, 'tcx: 'mir, M: Machine<'mir, 'tcx>> InterpCx<'mir, 'tcx, M> {
         })
     }
 
+    #[instrument(skip(self), level = "debug")]
     pub fn operand_projection(
         &self,
         base: &OpTy<'tcx, M::PointerTag>,
diff --git a/compiler/rustc_const_eval/src/interpret/place.rs b/compiler/rustc_const_eval/src/interpret/place.rs
index e4660fe090c..380eb526361 100644
--- a/compiler/rustc_const_eval/src/interpret/place.rs
+++ b/compiler/rustc_const_eval/src/interpret/place.rs
@@ -115,6 +115,12 @@ impl<'tcx, Tag: Provenance> std::ops::Deref for MPlaceTy<'tcx, Tag> {
     }
 }
 
+impl<'tcx, Tag: Provenance> std::ops::DerefMut for MPlaceTy<'tcx, Tag> {
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        &mut self.mplace
+    }
+}
+
 impl<'tcx, Tag: Provenance> From<MPlaceTy<'tcx, Tag>> for PlaceTy<'tcx, Tag> {
     #[inline(always)]
     fn from(mplace: MPlaceTy<'tcx, Tag>) -> Self {
@@ -294,6 +300,7 @@ where
 
     /// Take an operand, representing a pointer, and dereference it to a place -- that
     /// will always be a MemPlace.  Lives in `place.rs` because it creates a place.
+    #[instrument(skip(self), level = "debug")]
     pub fn deref_operand(
         &self,
         src: &OpTy<'tcx, M::PointerTag>,
@@ -487,7 +494,8 @@ where
     }
 
     /// Project into an mplace
-    pub(super) fn mplace_projection(
+    #[instrument(skip(self), level = "debug")]
+    pub(crate) fn mplace_projection(
         &self,
         base: &MPlaceTy<'tcx, M::PointerTag>,
         proj_elem: mir::PlaceElem<'tcx>,
@@ -548,6 +556,7 @@ where
     /// Just a convenience function, but used quite a bit.
     /// This is the only projection that might have a side-effect: We cannot project
     /// into the field of a local `ScalarPair`, we have to first allocate it.
+    #[instrument(skip(self), level = "debug")]
     pub fn place_field(
         &mut self,
         base: &PlaceTy<'tcx, M::PointerTag>,
@@ -617,6 +626,7 @@ where
 
     /// Computes a place. You should only use this if you intend to write into this
     /// place; for reading, a more efficient alternative is `eval_place_for_read`.
+    #[instrument(skip(self), level = "debug")]
     pub fn eval_place(
         &mut self,
         place: mir::Place<'tcx>,
@@ -646,6 +656,7 @@ where
 
     /// Write an immediate to a place
     #[inline(always)]
+    #[instrument(skip(self), level = "debug")]
     pub fn write_immediate(
         &mut self,
         src: Immediate<M::PointerTag>,
@@ -830,6 +841,7 @@ where
     /// Copies the data from an operand to a place. This does not support transmuting!
     /// Use `copy_op_transmute` if the layouts could disagree.
     #[inline(always)]
+    #[instrument(skip(self), level = "debug")]
     pub fn copy_op(
         &mut self,
         src: &OpTy<'tcx, M::PointerTag>,
@@ -849,6 +861,7 @@ where
     /// Use `copy_op_transmute` if the layouts could disagree.
     /// Also, if you use this you are responsible for validating that things get copied at the
     /// right type.
+    #[instrument(skip(self), level = "debug")]
     fn copy_op_no_validate(
         &mut self,
         src: &OpTy<'tcx, M::PointerTag>,
@@ -955,6 +968,7 @@ where
     /// This supports unsized types and returns the computed size to avoid some
     /// redundant computation when copying; use `force_allocation` for a simpler, sized-only
     /// version.
+    #[instrument(skip(self), level = "debug")]
     pub fn force_allocation_maybe_sized(
         &mut self,
         place: &PlaceTy<'tcx, M::PointerTag>,
@@ -1037,6 +1051,7 @@ where
     }
 
     /// Writes the discriminant of the given variant.
+    #[instrument(skip(self), level = "debug")]
     pub fn write_discriminant(
         &mut self,
         variant_index: VariantIdx,
diff --git a/compiler/rustc_const_eval/src/lib.rs b/compiler/rustc_const_eval/src/lib.rs
index d688331ae0a..34a00452519 100644
--- a/compiler/rustc_const_eval/src/lib.rs
+++ b/compiler/rustc_const_eval/src/lib.rs
@@ -35,6 +35,7 @@ pub mod transform;
 pub mod util;
 
 use rustc_middle::ty::query::Providers;
+use rustc_middle::ty::ParamEnv;
 
 pub fn provide(providers: &mut Providers) {
     const_eval::provide(providers);
@@ -49,6 +50,9 @@ pub fn provide(providers: &mut Providers) {
         let (param_env, raw) = param_env_and_value.into_parts();
         const_eval::const_to_valtree(tcx, param_env, raw)
     };
+    providers.valtree_to_const_val = |tcx, (ty, valtree)| {
+        const_eval::valtree_to_const_value(tcx, ParamEnv::empty().and(ty), valtree)
+    };
     providers.deref_const = |tcx, param_env_and_value| {
         let (param_env, value) = param_env_and_value.into_parts();
         const_eval::deref_const(tcx, param_env, value)
diff --git a/compiler/rustc_middle/src/mir/interpret/allocation.rs b/compiler/rustc_middle/src/mir/interpret/allocation.rs
index c628406064f..8cfc5ed0a95 100644
--- a/compiler/rustc_middle/src/mir/interpret/allocation.rs
+++ b/compiler/rustc_middle/src/mir/interpret/allocation.rs
@@ -418,6 +418,7 @@ impl<Tag: Provenance, Extra> Allocation<Tag, Extra> {
     ///
     /// It is the caller's responsibility to check bounds and alignment beforehand.
     /// Most likely, you want to call `InterpCx::write_scalar` instead of this method.
+    #[instrument(skip(self, cx), level = "debug")]
     pub fn write_scalar(
         &mut self,
         cx: &impl HasDataLayout,
diff --git a/compiler/rustc_middle/src/query/mod.rs b/compiler/rustc_middle/src/query/mod.rs
index d8586a8a77d..cc80ab8f16e 100644
--- a/compiler/rustc_middle/src/query/mod.rs
+++ b/compiler/rustc_middle/src/query/mod.rs
@@ -936,6 +936,11 @@ rustc_queries! {
         remap_env_constness
     }
 
+    /// Converts a type level constant value into `ConstValue`
+    query valtree_to_const_val(key: (Ty<'tcx>, ty::ValTree<'tcx>)) -> ConstValue<'tcx> {
+        desc { "convert type-level constant value to mir constant value"}
+    }
+
     /// Destructure a constant ADT or array into its variant index and its
     /// field values or return `None` if constant is invalid.
     ///
diff --git a/compiler/rustc_middle/src/ty/consts/int.rs b/compiler/rustc_middle/src/ty/consts/int.rs
index 72623ba54ee..a3ce674c115 100644
--- a/compiler/rustc_middle/src/ty/consts/int.rs
+++ b/compiler/rustc_middle/src/ty/consts/int.rs
@@ -237,6 +237,98 @@ impl ScalarInt {
     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 {
diff --git a/compiler/rustc_middle/src/ty/consts/valtree.rs b/compiler/rustc_middle/src/ty/consts/valtree.rs
index 195760c0590..418848f69d7 100644
--- a/compiler/rustc_middle/src/ty/consts/valtree.rs
+++ b/compiler/rustc_middle/src/ty/consts/valtree.rs
@@ -20,6 +20,9 @@ pub enum ValTree<'tcx> {
     /// 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
@@ -31,4 +34,20 @@ 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),
+        }
+    }
 }
diff --git a/compiler/rustc_middle/src/ty/sty.rs b/compiler/rustc_middle/src/ty/sty.rs
index 5a13216846d..1509de0e930 100644
--- a/compiler/rustc_middle/src/ty/sty.rs
+++ b/compiler/rustc_middle/src/ty/sty.rs
@@ -2273,7 +2273,7 @@ impl<'tcx> Ty<'tcx> {
         tcx: TyCtxt<'tcx>,
         normalize: impl FnMut(Ty<'tcx>) -> Ty<'tcx>,
     ) -> (Ty<'tcx>, bool) {
-        let tail = tcx.struct_tail_with_normalize(self, normalize);
+        let tail = tcx.struct_tail_with_normalize(self, normalize, || {});
         match tail.kind() {
             // Sized types
             ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
diff --git a/compiler/rustc_middle/src/ty/util.rs b/compiler/rustc_middle/src/ty/util.rs
index 39038e85b11..918fe49e8e3 100644
--- a/compiler/rustc_middle/src/ty/util.rs
+++ b/compiler/rustc_middle/src/ty/util.rs
@@ -187,7 +187,7 @@ impl<'tcx> TyCtxt<'tcx> {
     /// if input `ty` is not a structure at all.
     pub fn struct_tail_without_normalization(self, ty: Ty<'tcx>) -> Ty<'tcx> {
         let tcx = self;
-        tcx.struct_tail_with_normalize(ty, |ty| ty)
+        tcx.struct_tail_with_normalize(ty, |ty| ty, || {})
     }
 
     /// Returns the deeply last field of nested structures, or the same type if
@@ -203,7 +203,7 @@ impl<'tcx> TyCtxt<'tcx> {
         param_env: ty::ParamEnv<'tcx>,
     ) -> Ty<'tcx> {
         let tcx = self;
-        tcx.struct_tail_with_normalize(ty, |ty| tcx.normalize_erasing_regions(param_env, ty))
+        tcx.struct_tail_with_normalize(ty, |ty| tcx.normalize_erasing_regions(param_env, ty), || {})
     }
 
     /// Returns the deeply last field of nested structures, or the same type if
@@ -220,6 +220,10 @@ impl<'tcx> TyCtxt<'tcx> {
         self,
         mut ty: Ty<'tcx>,
         mut normalize: impl FnMut(Ty<'tcx>) -> Ty<'tcx>,
+        // This is currently used to allow us to walk a ValTree
+        // in lockstep with the type in order to get the ValTree branch that
+        // corresponds to an unsized field.
+        mut f: impl FnMut() -> (),
     ) -> Ty<'tcx> {
         let recursion_limit = self.recursion_limit();
         for iteration in 0.. {
@@ -235,12 +239,16 @@ impl<'tcx> TyCtxt<'tcx> {
                         break;
                     }
                     match def.non_enum_variant().fields.last() {
-                        Some(f) => ty = f.ty(self, substs),
+                        Some(field) => {
+                            f();
+                            ty = field.ty(self, substs);
+                        }
                         None => break,
                     }
                 }
 
                 ty::Tuple(tys) if let Some((&last_ty, _)) = tys.split_last() => {
+                    f();
                     ty = last_ty;
                 }
 
diff --git a/compiler/rustc_query_impl/src/keys.rs b/compiler/rustc_query_impl/src/keys.rs
index f1f83a7299c..3f0f856b5dd 100644
--- a/compiler/rustc_query_impl/src/keys.rs
+++ b/compiler/rustc_query_impl/src/keys.rs
@@ -502,3 +502,14 @@ impl<'tcx> Key for (ty::Instance<'tcx>, &'tcx ty::List<Ty<'tcx>>) {
         self.0.default_span(tcx)
     }
 }
+
+impl<'tcx> Key for (Ty<'tcx>, ty::ValTree<'tcx>) {
+    #[inline(always)]
+    fn query_crate_is_local(&self) -> bool {
+        true
+    }
+
+    fn default_span(&self, _: TyCtxt<'_>) -> Span {
+        DUMMY_SP
+    }
+}
diff --git a/compiler/rustc_trait_selection/src/traits/project.rs b/compiler/rustc_trait_selection/src/traits/project.rs
index 8ba390c71db..c7a61cbe25a 100644
--- a/compiler/rustc_trait_selection/src/traits/project.rs
+++ b/compiler/rustc_trait_selection/src/traits/project.rs
@@ -1519,18 +1519,22 @@ fn assemble_candidates_from_impls<'cx, 'tcx>(
                 // Any type with multiple potential metadata types is therefore not eligible.
                 let self_ty = selcx.infcx().shallow_resolve(obligation.predicate.self_ty());
 
-                let tail = selcx.tcx().struct_tail_with_normalize(self_ty, |ty| {
-                    // We throw away any obligations we get from this, since we normalize
-                    // and confirm these obligations once again during confirmation
-                    normalize_with_depth(
-                        selcx,
-                        obligation.param_env,
-                        obligation.cause.clone(),
-                        obligation.recursion_depth + 1,
-                        ty,
-                    )
-                    .value
-                });
+                let tail = selcx.tcx().struct_tail_with_normalize(
+                    self_ty,
+                    |ty| {
+                        // We throw away any obligations we get from this, since we normalize
+                        // and confirm these obligations once again during confirmation
+                        normalize_with_depth(
+                            selcx,
+                            obligation.param_env,
+                            obligation.cause.clone(),
+                            obligation.recursion_depth + 1,
+                            ty,
+                        )
+                        .value
+                    },
+                    || {},
+                );
 
                 match tail.kind() {
                     ty::Bool