Auto merge of #96591 - b-naber:transition-to-valtrees-in-type-system, r=lcnr

Use valtrees as the type-system representation for constant values

This is not quite ready yet, there are still some problems with pretty printing and symbol mangling and `deref_const` seems to not work correctly in all cases.

Mainly opening now for a perf-run (which should be good to go, despite the still existing problems).

r? `@oli-obk`

cc `@lcnr` `@RalfJung`

7 files changed, 129 insertions, 125 deletions

diff --git a/compiler/rustc_const_eval/src/const_eval/error.rs b/compiler/rustc_const_eval/src/const_eval/error.rs
index 3bd092263c1..3eeb0138b37 100644
--- a/compiler/rustc_const_eval/src/const_eval/error.rs
+++ b/compiler/rustc_const_eval/src/const_eval/error.rs
@@ -140,6 +140,7 @@ impl<'tcx> ConstEvalErr<'tcx> {
     ///
     /// If `lint_root.is_some()` report it as a lint, else report it as a hard error.
     /// (Except that for some errors, we ignore all that -- see `must_error` below.)
+    #[instrument(skip(self, tcx, decorate, lint_root), level = "debug")]
     fn struct_generic(
         &self,
         tcx: TyCtxtAt<'tcx>,
@@ -190,6 +191,7 @@ impl<'tcx> ConstEvalErr<'tcx> {
             decorate(err);
         };
 
+        debug!("self.error: {:?}", self.error);
         // Special handling for certain errors
         match &self.error {
             // Don't emit a new diagnostic for these errors
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 0c20324e452..b7e5e7aea49 100644
--- a/compiler/rustc_const_eval/src/const_eval/eval_queries.rs
+++ b/compiler/rustc_const_eval/src/const_eval/eval_queries.rs
@@ -196,7 +196,7 @@ pub(super) fn op_to_const<'tcx>(
 }
 
 #[instrument(skip(tcx), level = "debug")]
-fn turn_into_const_value<'tcx>(
+pub(crate) fn turn_into_const_value<'tcx>(
     tcx: TyCtxt<'tcx>,
     constant: ConstAlloc<'tcx>,
     key: ty::ParamEnvAnd<'tcx, GlobalId<'tcx>>,
@@ -222,6 +222,7 @@ fn turn_into_const_value<'tcx>(
     const_val
 }
 
+#[instrument(skip(tcx), level = "debug")]
 pub fn eval_to_const_value_raw_provider<'tcx>(
     tcx: TyCtxt<'tcx>,
     key: ty::ParamEnvAnd<'tcx, GlobalId<'tcx>>,
@@ -256,6 +257,7 @@ pub fn eval_to_const_value_raw_provider<'tcx>(
     tcx.eval_to_allocation_raw(key).map(|val| turn_into_const_value(tcx, val, key))
 }
 
+#[instrument(skip(tcx), level = "debug")]
 pub fn eval_to_allocation_raw_provider<'tcx>(
     tcx: TyCtxt<'tcx>,
     key: ty::ParamEnvAnd<'tcx, GlobalId<'tcx>>,
diff --git a/compiler/rustc_const_eval/src/const_eval/mod.rs b/compiler/rustc_const_eval/src/const_eval/mod.rs
index 6ee77db4017..a1d2e5cf3ef 100644
--- a/compiler/rustc_const_eval/src/const_eval/mod.rs
+++ b/compiler/rustc_const_eval/src/const_eval/mod.rs
@@ -1,12 +1,11 @@
 // Not in interpret to make sure we do not use private implementation details
 
-use std::convert::TryFrom;
-
 use rustc_hir::Mutability;
 use rustc_middle::mir;
 use rustc_middle::mir::interpret::{EvalToValTreeResult, GlobalId};
 use rustc_middle::ty::{self, TyCtxt};
 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, MemPlaceMeta,
@@ -40,7 +39,7 @@ pub(crate) fn const_caller_location(
 }
 
 // We forbid type-level constants that contain more than `VALTREE_MAX_NODES` nodes.
-const VALTREE_MAX_NODES: usize = 1000;
+const VALTREE_MAX_NODES: usize = 100000;
 
 pub(crate) enum ValTreeCreationError {
     NodesOverflow,
@@ -56,6 +55,8 @@ pub(crate) fn eval_to_valtree<'tcx>(
     cid: GlobalId<'tcx>,
 ) -> EvalToValTreeResult<'tcx> {
     let const_alloc = tcx.eval_to_allocation_raw(param_env.and(cid))?;
+
+    // FIXME Need to provide a span to `eval_to_valtree`
     let ecx = mk_eval_cx(
         tcx, DUMMY_SP, param_env,
         // It is absolutely crucial for soundness that
@@ -90,40 +91,81 @@ pub(crate) fn eval_to_valtree<'tcx>(
     }
 }
 
-/// 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.
+/// Tries to destructure constants of type Array or Adt into the constants
+/// of its fields.
 pub(crate) fn try_destructure_const<'tcx>(
     tcx: TyCtxt<'tcx>,
-    param_env: ty::ParamEnv<'tcx>,
-    val: ty::Const<'tcx>,
-) -> InterpResult<'tcx, mir::DestructuredConst<'tcx>> {
-    trace!("destructure_const: {:?}", val);
-    let ecx = mk_eval_cx(tcx, DUMMY_SP, param_env, false);
-    let op = ecx.const_to_op(val, None)?;
-    // We go to `usize` as we cannot allocate anything bigger anyway.
-    let (field_count, variant, down) = match val.ty().kind() {
-        ty::Array(_, len) => (usize::try_from(len.eval_usize(tcx, param_env)).unwrap(), None, op),
-        // Checks if we have any variants, to avoid downcasting to a non-existing variant (when
-        // there are no variants `read_discriminant` successfully returns a non-existing variant
-        // index).
-        ty::Adt(def, _) if def.variants().is_empty() => throw_ub!(Unreachable),
-        ty::Adt(def, _) => {
-            let variant = ecx.read_discriminant(&op)?.1;
-            let down = ecx.operand_downcast(&op, variant)?;
-            (def.variant(variant).fields.len(), Some(variant), down)
-        }
-        ty::Tuple(substs) => (substs.len(), None, op),
-        _ => bug!("cannot destructure constant {:?}", val),
-    };
-    let fields = (0..field_count)
-        .map(|i| {
-            let field_op = ecx.operand_field(&down, i)?;
-            let val = op_to_const(&ecx, &field_op);
-            Ok(ty::Const::from_value(tcx, val, field_op.layout.ty))
-        })
-        .collect::<InterpResult<'tcx, Vec<_>>>()?;
-    let fields = tcx.arena.alloc_from_iter(fields);
-    Ok(mir::DestructuredConst { variant, fields })
+    const_: ty::Const<'tcx>,
+) -> Option<ty::DestructuredConst<'tcx>> {
+    if let ty::ConstKind::Value(valtree) = const_.kind() {
+        let branches = match valtree {
+            ty::ValTree::Branch(b) => b,
+            _ => return None,
+        };
+
+        let (fields, variant) = match const_.ty().kind() {
+            ty::Array(inner_ty, _) | ty::Slice(inner_ty) => {
+                // construct the consts for the elements of the array/slice
+                let field_consts = branches
+                    .iter()
+                    .map(|b| {
+                        tcx.mk_const(ty::ConstS { kind: ty::ConstKind::Value(*b), ty: *inner_ty })
+                    })
+                    .collect::<Vec<_>>();
+                debug!(?field_consts);
+
+                (field_consts, None)
+            }
+            ty::Adt(def, _) if def.variants().is_empty() => bug!("unreachable"),
+            ty::Adt(def, substs) => {
+                let variant_idx = if def.is_enum() {
+                    VariantIdx::from_u32(branches[0].unwrap_leaf().try_to_u32().ok()?)
+                } else {
+                    VariantIdx::from_u32(0)
+                };
+                let fields = &def.variant(variant_idx).fields;
+                let mut field_consts = Vec::with_capacity(fields.len());
+
+                // Note: First element inValTree corresponds to variant of enum
+                let mut valtree_idx = if def.is_enum() { 1 } else { 0 };
+                for field in fields {
+                    let field_ty = field.ty(tcx, substs);
+                    let field_valtree = branches[valtree_idx]; // first element of branches is variant
+                    let field_const = tcx.mk_const(ty::ConstS {
+                        kind: ty::ConstKind::Value(field_valtree),
+                        ty: field_ty,
+                    });
+                    field_consts.push(field_const);
+                    valtree_idx += 1;
+                }
+                debug!(?field_consts);
+
+                (field_consts, Some(variant_idx))
+            }
+            ty::Tuple(elem_tys) => {
+                let fields = elem_tys
+                    .iter()
+                    .enumerate()
+                    .map(|(i, elem_ty)| {
+                        let elem_valtree = branches[i];
+                        tcx.mk_const(ty::ConstS {
+                            kind: ty::ConstKind::Value(elem_valtree),
+                            ty: elem_ty,
+                        })
+                    })
+                    .collect::<Vec<_>>();
+
+                (fields, None)
+            }
+            _ => bug!("cannot destructure constant {:?}", const_),
+        };
+
+        let fields = tcx.arena.alloc_from_iter(fields.into_iter());
+
+        Some(ty::DestructuredConst { variant, fields })
+    } else {
+        None
+    }
 }
 
 #[instrument(skip(tcx), level = "debug")]
@@ -143,8 +185,8 @@ pub(crate) fn try_destructure_mir_constant<'tcx>(
             throw_ub!(Unreachable)
         }
         ty::Adt(def, _) => {
-            let variant = ecx.read_discriminant(&op).unwrap().1;
-            let down = ecx.operand_downcast(&op, variant).unwrap();
+            let variant = ecx.read_discriminant(&op)?.1;
+            let down = ecx.operand_downcast(&op, variant)?;
             (def.variants()[variant].fields.len(), Some(variant), down)
         }
         ty::Tuple(substs) => (substs.len(), None, op),
@@ -164,43 +206,6 @@ pub(crate) fn try_destructure_mir_constant<'tcx>(
 }
 
 #[instrument(skip(tcx), level = "debug")]
-pub(crate) fn deref_const<'tcx>(
-    tcx: TyCtxt<'tcx>,
-    param_env: ty::ParamEnv<'tcx>,
-    val: ty::Const<'tcx>,
-) -> ty::Const<'tcx> {
-    trace!("deref_const: {:?}", val);
-    let ecx = mk_eval_cx(tcx, DUMMY_SP, param_env, false);
-    let op = ecx.const_to_op(val, None).unwrap();
-    let mplace = ecx.deref_operand(&op).unwrap();
-    if let Some(alloc_id) = mplace.ptr.provenance {
-        assert_eq!(
-            tcx.get_global_alloc(alloc_id).unwrap().unwrap_memory().inner().mutability,
-            Mutability::Not,
-            "deref_const cannot be used with mutable allocations as \
-            that could allow pattern matching to observe mutable statics",
-        );
-    }
-
-    let ty = match mplace.meta {
-        MemPlaceMeta::None => mplace.layout.ty,
-        MemPlaceMeta::Poison => bug!("poison metadata in `deref_const`: {:#?}", mplace),
-        // In case of unsized types, figure out the real type behind.
-        MemPlaceMeta::Meta(scalar) => match mplace.layout.ty.kind() {
-            ty::Str => bug!("there's no sized equivalent of a `str`"),
-            ty::Slice(elem_ty) => tcx.mk_array(*elem_ty, scalar.to_machine_usize(&tcx).unwrap()),
-            _ => bug!(
-                "type {} should not have metadata, but had {:?}",
-                mplace.layout.ty,
-                mplace.meta
-            ),
-        },
-    };
-
-    tcx.mk_const(ty::ConstS { kind: ty::ConstKind::Value(op_to_const(&ecx, &mplace.into())), ty })
-}
-
-#[instrument(skip(tcx), level = "debug")]
 pub(crate) fn deref_mir_constant<'tcx>(
     tcx: TyCtxt<'tcx>,
     param_env: ty::ParamEnv<'tcx>,
@@ -213,14 +218,14 @@ pub(crate) fn deref_mir_constant<'tcx>(
         assert_eq!(
             tcx.get_global_alloc(alloc_id).unwrap().unwrap_memory().0.0.mutability,
             Mutability::Not,
-            "deref_const cannot be used with mutable allocations as \
+            "deref_mir_constant cannot be used with mutable allocations as \
             that could allow pattern matching to observe mutable statics",
         );
     }
 
     let ty = match mplace.meta {
         MemPlaceMeta::None => mplace.layout.ty,
-        MemPlaceMeta::Poison => bug!("poison metadata in `deref_const`: {:#?}", mplace),
+        MemPlaceMeta::Poison => bug!("poison metadata in `deref_mir_constant`: {:#?}", mplace),
         // In case of unsized types, figure out the real type behind.
         MemPlaceMeta::Meta(scalar) => match mplace.layout.ty.kind() {
             ty::Str => bug!("there's no sized equivalent of a `str`"),
diff --git a/compiler/rustc_const_eval/src/const_eval/valtrees.rs b/compiler/rustc_const_eval/src/const_eval/valtrees.rs
index 7346d69bb5d..4849a07e3b4 100644
--- a/compiler/rustc_const_eval/src/const_eval/valtrees.rs
+++ b/compiler/rustc_const_eval/src/const_eval/valtrees.rs
@@ -5,13 +5,11 @@ use crate::interpret::{
     intern_const_alloc_recursive, ConstValue, ImmTy, Immediate, InternKind, MemPlaceMeta,
     MemoryKind, PlaceTy, Scalar, ScalarMaybeUninit,
 };
+use crate::interpret::{MPlaceTy, Value};
+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;
-use rustc_middle::ty::{self, ScalarInt, Ty, TyCtxt};
-
 #[instrument(skip(ecx), level = "debug")]
 fn branches<'tcx>(
     ecx: &CompileTimeEvalContext<'tcx, 'tcx>,
@@ -76,13 +74,13 @@ pub(crate) fn const_to_valtree_inner<'tcx>(
     place: &MPlaceTy<'tcx>,
     num_nodes: &mut usize,
 ) -> ValTreeCreationResult<'tcx> {
+    let ty = place.layout.ty;
+    debug!("ty kind: {:?}", ty.kind());
+
     if *num_nodes >= VALTREE_MAX_NODES {
         return Err(ValTreeCreationError::NodesOverflow);
     }
 
-    let ty = place.layout.ty;
-    debug!("ty kind: {:?}", ty.kind());
-
     match ty.kind() {
         ty::FnDef(..) => {
             *num_nodes += 1;
@@ -234,19 +232,15 @@ fn create_pointee_place<'tcx>(
         // 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();
+        let size = size_of_sized_part.checked_add(dst_size, &tcx).unwrap();
+        let align = Align::from_bytes(size.bytes().next_power_of_two()).unwrap();
+        let ptr = ecx.allocate_ptr(size, align, MemoryKind::Stack).unwrap();
         debug!(?ptr);
 
         let place = MPlaceTy::from_aligned_ptr_with_meta(
             ptr.into(),
             layout,
-            MemPlaceMeta::Meta(Scalar::from_u64(num_elems as u64)),
+            MemPlaceMeta::Meta(Scalar::from_machine_usize(num_elems as u64, &tcx)),
         );
         debug!(?place);
 
@@ -262,7 +256,7 @@ fn create_pointee_place<'tcx>(
 #[instrument(skip(tcx), level = "debug")]
 pub fn valtree_to_const_value<'tcx>(
     tcx: TyCtxt<'tcx>,
-    ty: Ty<'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
@@ -272,8 +266,8 @@ pub fn valtree_to_const_value<'tcx>(
     // create inner `MPlace`s which are filled recursively.
     // FIXME Does this need an example?
 
-    let mut ecx = mk_eval_cx(tcx, DUMMY_SP, ty::ParamEnv::empty(), false);
-    let param_env_ty = ty::ParamEnv::empty().and(ty);
+    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(..) => {
@@ -336,7 +330,6 @@ pub fn valtree_to_const_value<'tcx>(
     }
 }
 
-// FIXME Needs a better/correct name
 #[instrument(skip(ecx), level = "debug")]
 fn valtree_into_mplace<'tcx>(
     ecx: &mut CompileTimeEvalContext<'tcx, 'tcx>,
@@ -377,7 +370,8 @@ fn valtree_into_mplace<'tcx>(
             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));
+                    let len_scalar =
+                        ScalarMaybeUninit::Scalar(Scalar::from_machine_usize(len as u64, &tcx));
 
                     Immediate::ScalarPair(
                         ScalarMaybeUninit::from_maybe_pointer((*pointee_place).ptr, &tcx),
@@ -448,7 +442,10 @@ fn valtree_into_mplace<'tcx>(
                         place
                             .offset(
                                 offset,
-                                MemPlaceMeta::Meta(Scalar::from_u64(num_elems as u64)),
+                                MemPlaceMeta::Meta(Scalar::from_machine_usize(
+                                    num_elems as u64,
+                                    &tcx,
+                                )),
                                 inner_layout,
                                 &tcx,
                             )
diff --git a/compiler/rustc_const_eval/src/interpret/operand.rs b/compiler/rustc_const_eval/src/interpret/operand.rs
index 597ca4cfcdd..6b05a49575f 100644
--- a/compiler/rustc_const_eval/src/interpret/operand.rs
+++ b/compiler/rustc_const_eval/src/interpret/operand.rs
@@ -637,7 +637,11 @@ impl<'mir, 'tcx: 'mir, M: Machine<'mir, 'tcx>> InterpCx<'mir, 'tcx, M> {
             ty::ConstKind::Infer(..) | ty::ConstKind::Placeholder(..) => {
                 span_bug!(self.cur_span(), "const_to_op: Unexpected ConstKind {:?}", c)
             }
-            ty::ConstKind::Value(val) => self.const_val_to_op(val, c.ty(), layout),
+            ty::ConstKind::Value(valtree) => {
+                let ty = c.ty();
+                let const_val = self.tcx.valtree_to_const_val((ty, valtree));
+                self.const_val_to_op(const_val, ty, layout)
+            }
         }
     }
 
diff --git a/compiler/rustc_const_eval/src/lib.rs b/compiler/rustc_const_eval/src/lib.rs
index 04410ca3828..64a74e9d7e2 100644
--- a/compiler/rustc_const_eval/src/lib.rs
+++ b/compiler/rustc_const_eval/src/lib.rs
@@ -34,6 +34,7 @@ pub mod interpret;
 pub mod transform;
 pub mod util;
 
+use rustc_middle::ty;
 use rustc_middle::ty::query::Providers;
 
 pub fn provide(providers: &mut Providers) {
@@ -41,10 +42,7 @@ pub fn provide(providers: &mut Providers) {
     providers.eval_to_const_value_raw = const_eval::eval_to_const_value_raw_provider;
     providers.eval_to_allocation_raw = const_eval::eval_to_allocation_raw_provider;
     providers.const_caller_location = const_eval::const_caller_location;
-    providers.try_destructure_const = |tcx, param_env_and_val| {
-        let (param_env, c) = param_env_and_val.into_parts();
-        const_eval::try_destructure_const(tcx, param_env, c).ok()
-    };
+    providers.try_destructure_const = |tcx, val| const_eval::try_destructure_const(tcx, val);
     providers.eval_to_valtree = |tcx, param_env_and_value| {
         let (param_env, raw) = param_env_and_value.into_parts();
         const_eval::eval_to_valtree(tcx, param_env, raw)
@@ -53,11 +51,8 @@ pub fn provide(providers: &mut Providers) {
         let (param_env, value) = param_env_and_value.into_parts();
         const_eval::try_destructure_mir_constant(tcx, param_env, value).ok()
     };
-    providers.valtree_to_const_val =
-        |tcx, (ty, valtree)| const_eval::valtree_to_const_value(tcx, 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)
+    providers.valtree_to_const_val = |tcx, (ty, valtree)| {
+        const_eval::valtree_to_const_value(tcx, ty::ParamEnv::empty().and(ty), valtree)
     };
     providers.deref_mir_constant = |tcx, param_env_and_value| {
         let (param_env, value) = param_env_and_value.into_parts();
diff --git a/compiler/rustc_const_eval/src/transform/promote_consts.rs b/compiler/rustc_const_eval/src/transform/promote_consts.rs
index 67a356918d1..3595a488d0c 100644
--- a/compiler/rustc_const_eval/src/transform/promote_consts.rs
+++ b/compiler/rustc_const_eval/src/transform/promote_consts.rs
@@ -765,7 +765,7 @@ impl<'a, 'tcx> Promoter<'a, 'tcx> {
                         let unit = Rvalue::Use(Operand::Constant(Box::new(Constant {
                             span: statement.source_info.span,
                             user_ty: None,
-                            literal: ty::Const::zero_sized(self.tcx, self.tcx.types.unit).into(),
+                            literal: ConstantKind::zero_sized(self.tcx.types.unit),
                         })));
                         mem::replace(rhs, unit)
                     },
@@ -835,26 +835,25 @@ impl<'a, 'tcx> Promoter<'a, 'tcx> {
             let mut promoted_operand = |ty, span| {
                 promoted.span = span;
                 promoted.local_decls[RETURN_PLACE] = LocalDecl::new(ty, span);
+                let _const = tcx.mk_const(ty::ConstS {
+                    ty,
+                    kind: ty::ConstKind::Unevaluated(ty::Unevaluated {
+                        def,
+                        substs: InternalSubsts::for_item(tcx, def.did, |param, _| {
+                            if let ty::GenericParamDefKind::Lifetime = param.kind {
+                                tcx.lifetimes.re_erased.into()
+                            } else {
+                                tcx.mk_param_from_def(param)
+                            }
+                        }),
+                        promoted: Some(promoted_id),
+                    }),
+                });
 
                 Operand::Constant(Box::new(Constant {
                     span,
                     user_ty: None,
-                    literal: tcx
-                        .mk_const(ty::ConstS {
-                            ty,
-                            kind: ty::ConstKind::Unevaluated(ty::Unevaluated {
-                                def,
-                                substs: InternalSubsts::for_item(tcx, def.did, |param, _| {
-                                    if let ty::GenericParamDefKind::Lifetime = param.kind {
-                                        tcx.lifetimes.re_erased.into()
-                                    } else {
-                                        tcx.mk_param_from_def(param)
-                                    }
-                                }),
-                                promoted: Some(promoted_id),
-                            }),
-                        })
-                        .into(),
+                    literal: ConstantKind::from_const(_const, tcx),
                 }))
             };
             let (blocks, local_decls) = self.source.basic_blocks_and_local_decls_mut();