rustc_const_eval/const_eval/
valtrees.rs

1use rustc_abi::{BackendRepr, FieldIdx, VariantIdx};
2use rustc_data_structures::stack::ensure_sufficient_stack;
3use rustc_middle::mir::interpret::{EvalToValTreeResult, GlobalId, ValTreeCreationError};
4use rustc_middle::traits::ObligationCause;
5use rustc_middle::ty::layout::{LayoutCx, TyAndLayout};
6use rustc_middle::ty::{self, Ty, TyCtxt};
7use rustc_middle::{bug, mir};
8use rustc_span::DUMMY_SP;
9use tracing::{debug, instrument, trace};
10
11use super::VALTREE_MAX_NODES;
12use super::eval_queries::{mk_eval_cx_to_read_const_val, op_to_const};
13use super::machine::CompileTimeInterpCx;
14use crate::const_eval::CanAccessMutGlobal;
15use crate::interpret::{
16    ImmTy, Immediate, InternKind, MPlaceTy, MemPlaceMeta, MemoryKind, PlaceTy, Projectable, Scalar,
17    intern_const_alloc_recursive,
18};
19
20#[instrument(skip(ecx), level = "debug")]
21fn branches<'tcx>(
22    ecx: &CompileTimeInterpCx<'tcx>,
23    place: &MPlaceTy<'tcx>,
24    field_count: usize,
25    variant: Option<VariantIdx>,
26    num_nodes: &mut usize,
27) -> EvalToValTreeResult<'tcx> {
28    let place = match variant {
29        Some(variant) => ecx.project_downcast(place, variant).unwrap(),
30        None => place.clone(),
31    };
32    debug!(?place);
33
34    let mut branches = Vec::with_capacity(field_count + variant.is_some() as usize);
35
36    // For enums, we prepend their variant index before the variant's fields so we can figure out
37    // the variant again when just seeing a valtree.
38    if let Some(variant) = variant {
39        branches.push(ty::ValTree::from_scalar_int(*ecx.tcx, variant.as_u32().into()));
40    }
41
42    for i in 0..field_count {
43        let field = ecx.project_field(&place, FieldIdx::from_usize(i)).unwrap();
44        let valtree = const_to_valtree_inner(ecx, &field, num_nodes)?;
45        branches.push(valtree);
46    }
47
48    // Have to account for ZSTs here
49    if branches.len() == 0 {
50        *num_nodes += 1;
51    }
52
53    Ok(ty::ValTree::from_branches(*ecx.tcx, branches))
54}
55
56#[instrument(skip(ecx), level = "debug")]
57fn slice_branches<'tcx>(
58    ecx: &CompileTimeInterpCx<'tcx>,
59    place: &MPlaceTy<'tcx>,
60    num_nodes: &mut usize,
61) -> EvalToValTreeResult<'tcx> {
62    let n = place.len(ecx).unwrap_or_else(|_| panic!("expected to use len of place {place:?}"));
63
64    let mut elems = Vec::with_capacity(n as usize);
65    for i in 0..n {
66        let place_elem = ecx.project_index(place, i).unwrap();
67        let valtree = const_to_valtree_inner(ecx, &place_elem, num_nodes)?;
68        elems.push(valtree);
69    }
70
71    Ok(ty::ValTree::from_branches(*ecx.tcx, elems))
72}
73
74#[instrument(skip(ecx), level = "debug")]
75fn const_to_valtree_inner<'tcx>(
76    ecx: &CompileTimeInterpCx<'tcx>,
77    place: &MPlaceTy<'tcx>,
78    num_nodes: &mut usize,
79) -> EvalToValTreeResult<'tcx> {
80    let tcx = *ecx.tcx;
81    let ty = place.layout.ty;
82    debug!("ty kind: {:?}", ty.kind());
83
84    if *num_nodes >= VALTREE_MAX_NODES {
85        return Err(ValTreeCreationError::NodesOverflow);
86    }
87
88    match ty.kind() {
89        ty::FnDef(..) => {
90            *num_nodes += 1;
91            Ok(ty::ValTree::zst(tcx))
92        }
93        ty::Bool | ty::Int(_) | ty::Uint(_) | ty::Float(_) | ty::Char => {
94            let val = ecx.read_immediate(place).report_err()?;
95            let val = val.to_scalar_int().unwrap();
96            *num_nodes += 1;
97
98            Ok(ty::ValTree::from_scalar_int(tcx, val))
99        }
100
101        ty::Pat(base, ..) => {
102            let mut place = place.clone();
103            // The valtree of the base type is the same as the valtree of the pattern type.
104            // Since the returned valtree does not contain the type or layout, we can just
105            // switch to the base type.
106            place.layout = ecx.layout_of(*base).unwrap();
107            ensure_sufficient_stack(|| const_to_valtree_inner(ecx, &place, num_nodes))
108        },
109
110
111        ty::RawPtr(_, _) => {
112            // Not all raw pointers are allowed, as we cannot properly test them for
113            // equality at compile-time (see `ptr_guaranteed_cmp`).
114            // However we allow those that are just integers in disguise.
115            // First, get the pointer. Remember it might be wide!
116            let val = ecx.read_immediate(place).report_err()?;
117            // We could allow wide raw pointers where both sides are integers in the future,
118            // but for now we reject them.
119            if matches!(val.layout.backend_repr, BackendRepr::ScalarPair(..)) {
120                return Err(ValTreeCreationError::NonSupportedType(ty));
121            }
122            let val = val.to_scalar();
123            // We are in the CTFE machine, so ptr-to-int casts will fail.
124            // This can only be `Ok` if `val` already is an integer.
125            let Ok(val) = val.try_to_scalar_int() else {
126                return Err(ValTreeCreationError::NonSupportedType(ty));
127            };
128            // It's just a ScalarInt!
129            Ok(ty::ValTree::from_scalar_int(tcx, val))
130        }
131
132        // Technically we could allow function pointers (represented as `ty::Instance`), but this is not guaranteed to
133        // agree with runtime equality tests.
134        ty::FnPtr(..) => Err(ValTreeCreationError::NonSupportedType(ty)),
135
136        ty::Ref(_, _, _)  => {
137            let derefd_place = ecx.deref_pointer(place).report_err()?;
138            const_to_valtree_inner(ecx, &derefd_place, num_nodes)
139        }
140
141        ty::Str | ty::Slice(_) | ty::Array(_, _) => {
142            slice_branches(ecx, place, num_nodes)
143        }
144        // Trait objects are not allowed in type level constants, as we have no concept for
145        // resolving their backing type, even if we can do that at const eval time. We may
146        // hypothetically be able to allow `dyn StructuralPartialEq` trait objects in the future,
147        // but it is unclear if this is useful.
148        ty::Dynamic(..) => Err(ValTreeCreationError::NonSupportedType(ty)),
149
150        ty::Tuple(elem_tys) => {
151            branches(ecx, place, elem_tys.len(), None, num_nodes)
152        }
153
154        ty::Adt(def, _) => {
155            if def.is_union() {
156                return Err(ValTreeCreationError::NonSupportedType(ty));
157            } else if def.variants().is_empty() {
158                bug!("uninhabited types should have errored and never gotten converted to valtree")
159            }
160
161            let variant = ecx.read_discriminant(place).report_err()?;
162            branches(ecx, place, def.variant(variant).fields.len(), def.is_enum().then_some(variant), num_nodes)
163        }
164
165        ty::Never
166        | ty::Error(_)
167        | ty::Foreign(..)
168        | ty::Infer(ty::FreshIntTy(_))
169        | ty::Infer(ty::FreshFloatTy(_))
170        // FIXME(oli-obk): we could look behind opaque types
171        | ty::Alias(..)
172        | ty::Param(_)
173        | ty::Bound(..)
174        | ty::Placeholder(..)
175        | ty::Infer(_)
176        // FIXME(oli-obk): we can probably encode closures just like structs
177        | ty::Closure(..)
178        | ty::CoroutineClosure(..)
179        | ty::Coroutine(..)
180        | ty::CoroutineWitness(..)
181        | ty::UnsafeBinder(_) => Err(ValTreeCreationError::NonSupportedType(ty)),
182    }
183}
184
185/// Valtrees don't store the `MemPlaceMeta` that all dynamically sized values have in the interpreter.
186/// This function reconstructs it.
187fn reconstruct_place_meta<'tcx>(
188    layout: TyAndLayout<'tcx>,
189    valtree: ty::ValTree<'tcx>,
190    tcx: TyCtxt<'tcx>,
191) -> MemPlaceMeta {
192    if layout.is_sized() {
193        return MemPlaceMeta::None;
194    }
195
196    let mut last_valtree = valtree;
197    // Traverse the type, and update `last_valtree` as we go.
198    let tail = tcx.struct_tail_raw(
199        layout.ty,
200        &ObligationCause::dummy(),
201        |ty| ty,
202        || {
203            let branches = last_valtree.unwrap_branch();
204            last_valtree = *branches.last().unwrap();
205            debug!(?branches, ?last_valtree);
206        },
207    );
208    // Sanity-check that we got a tail we support.
209    match tail.kind() {
210        ty::Slice(..) | ty::Str => {}
211        _ => bug!("unsized tail of a valtree must be Slice or Str"),
212    };
213
214    // Get the number of elements in the unsized field.
215    let num_elems = last_valtree.unwrap_branch().len();
216    MemPlaceMeta::Meta(Scalar::from_target_usize(num_elems as u64, &tcx))
217}
218
219#[instrument(skip(ecx), level = "debug", ret)]
220fn create_valtree_place<'tcx>(
221    ecx: &mut CompileTimeInterpCx<'tcx>,
222    layout: TyAndLayout<'tcx>,
223    valtree: ty::ValTree<'tcx>,
224) -> MPlaceTy<'tcx> {
225    let meta = reconstruct_place_meta(layout, valtree, ecx.tcx.tcx);
226    ecx.allocate_dyn(layout, MemoryKind::Stack, meta).unwrap()
227}
228
229/// Evaluates a constant and turns it into a type-level constant value.
230pub(crate) fn eval_to_valtree<'tcx>(
231    tcx: TyCtxt<'tcx>,
232    typing_env: ty::TypingEnv<'tcx>,
233    cid: GlobalId<'tcx>,
234) -> EvalToValTreeResult<'tcx> {
235    // Const eval always happens in PostAnalysis mode . See the comment in
236    // `InterpCx::new` for more details.
237    debug_assert_eq!(typing_env.typing_mode, ty::TypingMode::PostAnalysis);
238    let const_alloc = tcx.eval_to_allocation_raw(typing_env.as_query_input(cid))?;
239
240    // FIXME Need to provide a span to `eval_to_valtree`
241    let ecx = mk_eval_cx_to_read_const_val(
242        tcx,
243        DUMMY_SP,
244        typing_env,
245        // It is absolutely crucial for soundness that
246        // we do not read from mutable memory.
247        CanAccessMutGlobal::No,
248    );
249    let place = ecx.raw_const_to_mplace(const_alloc).unwrap();
250    debug!(?place);
251
252    let mut num_nodes = 0;
253    const_to_valtree_inner(&ecx, &place, &mut num_nodes)
254}
255
256/// Converts a `ValTree` to a `ConstValue`, which is needed after mir
257/// construction has finished.
258// FIXME(valtrees): Merge `valtree_to_const_value` and `valtree_into_mplace` into one function
259#[instrument(skip(tcx), level = "debug", ret)]
260pub fn valtree_to_const_value<'tcx>(
261    tcx: TyCtxt<'tcx>,
262    typing_env: ty::TypingEnv<'tcx>,
263    cv: ty::Value<'tcx>,
264) -> mir::ConstValue {
265    // Basic idea: We directly construct `Scalar` values from trivial `ValTree`s
266    // (those for constants with type bool, int, uint, float or char).
267    // For all other types we create an `MPlace` and fill that by walking
268    // the `ValTree` and using `place_projection` and `place_field` to
269    // create inner `MPlace`s which are filled recursively.
270    // FIXME: Does this need an example?
271    match *cv.ty.kind() {
272        ty::FnDef(..) => {
273            assert!(cv.valtree.is_zst());
274            mir::ConstValue::ZeroSized
275        }
276        ty::Bool | ty::Int(_) | ty::Uint(_) | ty::Float(_) | ty::Char | ty::RawPtr(_, _) => {
277            mir::ConstValue::Scalar(Scalar::Int(cv.valtree.unwrap_leaf()))
278        }
279        ty::Pat(ty, _) => {
280            let cv = ty::Value { valtree: cv.valtree, ty };
281            valtree_to_const_value(tcx, typing_env, cv)
282        }
283        ty::Ref(_, inner_ty, _) => {
284            let mut ecx =
285                mk_eval_cx_to_read_const_val(tcx, DUMMY_SP, typing_env, CanAccessMutGlobal::No);
286            let imm = valtree_to_ref(&mut ecx, cv.valtree, inner_ty);
287            let imm = ImmTy::from_immediate(
288                imm,
289                tcx.layout_of(typing_env.as_query_input(cv.ty)).unwrap(),
290            );
291            op_to_const(&ecx, &imm.into(), /* for diagnostics */ false)
292        }
293        ty::Tuple(_) | ty::Array(_, _) | ty::Adt(..) => {
294            let layout = tcx.layout_of(typing_env.as_query_input(cv.ty)).unwrap();
295            if layout.is_zst() {
296                // Fast path to avoid some allocations.
297                return mir::ConstValue::ZeroSized;
298            }
299            if layout.backend_repr.is_scalar()
300                && (matches!(cv.ty.kind(), ty::Tuple(_))
301                    || matches!(cv.ty.kind(), ty::Adt(def, _) if def.is_struct()))
302            {
303                // A Scalar tuple/struct; we can avoid creating an allocation.
304                let branches = cv.valtree.unwrap_branch();
305                // Find the non-ZST field. (There can be aligned ZST!)
306                for (i, &inner_valtree) in branches.iter().enumerate() {
307                    let field = layout.field(&LayoutCx::new(tcx, typing_env), i);
308                    if !field.is_zst() {
309                        let cv = ty::Value { valtree: inner_valtree, ty: field.ty };
310                        return valtree_to_const_value(tcx, typing_env, cv);
311                    }
312                }
313                bug!("could not find non-ZST field during in {layout:#?}");
314            }
315
316            let mut ecx =
317                mk_eval_cx_to_read_const_val(tcx, DUMMY_SP, typing_env, CanAccessMutGlobal::No);
318
319            // Need to create a place for this valtree.
320            let place = create_valtree_place(&mut ecx, layout, cv.valtree);
321
322            valtree_into_mplace(&mut ecx, &place, cv.valtree);
323            dump_place(&ecx, &place);
324            intern_const_alloc_recursive(&mut ecx, InternKind::Constant, &place).unwrap();
325
326            op_to_const(&ecx, &place.into(), /* for diagnostics */ false)
327        }
328        ty::Never
329        | ty::Error(_)
330        | ty::Foreign(..)
331        | ty::Infer(ty::FreshIntTy(_))
332        | ty::Infer(ty::FreshFloatTy(_))
333        | ty::Alias(..)
334        | ty::Param(_)
335        | ty::Bound(..)
336        | ty::Placeholder(..)
337        | ty::Infer(_)
338        | ty::Closure(..)
339        | ty::CoroutineClosure(..)
340        | ty::Coroutine(..)
341        | ty::CoroutineWitness(..)
342        | ty::FnPtr(..)
343        | ty::Str
344        | ty::Slice(_)
345        | ty::Dynamic(..)
346        | ty::UnsafeBinder(_) => {
347            bug!("no ValTree should have been created for type {:?}", cv.ty.kind())
348        }
349    }
350}
351
352/// Put a valtree into memory and return a reference to that.
353fn valtree_to_ref<'tcx>(
354    ecx: &mut CompileTimeInterpCx<'tcx>,
355    valtree: ty::ValTree<'tcx>,
356    pointee_ty: Ty<'tcx>,
357) -> Immediate {
358    let pointee_place = create_valtree_place(ecx, ecx.layout_of(pointee_ty).unwrap(), valtree);
359    debug!(?pointee_place);
360
361    valtree_into_mplace(ecx, &pointee_place, valtree);
362    dump_place(ecx, &pointee_place);
363    intern_const_alloc_recursive(ecx, InternKind::Constant, &pointee_place).unwrap();
364
365    pointee_place.to_ref(&ecx.tcx)
366}
367
368#[instrument(skip(ecx), level = "debug")]
369fn valtree_into_mplace<'tcx>(
370    ecx: &mut CompileTimeInterpCx<'tcx>,
371    place: &MPlaceTy<'tcx>,
372    valtree: ty::ValTree<'tcx>,
373) {
374    // This will match on valtree and write the value(s) corresponding to the ValTree
375    // inside the place recursively.
376
377    let ty = place.layout.ty;
378
379    match ty.kind() {
380        ty::FnDef(_, _) => {
381            // Zero-sized type, nothing to do.
382        }
383        ty::Bool | ty::Int(_) | ty::Uint(_) | ty::Float(_) | ty::Char | ty::RawPtr(..) => {
384            let scalar_int = valtree.unwrap_leaf();
385            debug!("writing trivial valtree {:?} to place {:?}", scalar_int, place);
386            ecx.write_immediate(Immediate::Scalar(scalar_int.into()), place).unwrap();
387        }
388        ty::Ref(_, inner_ty, _) => {
389            let imm = valtree_to_ref(ecx, valtree, *inner_ty);
390            debug!(?imm);
391            ecx.write_immediate(imm, place).unwrap();
392        }
393        ty::Adt(_, _) | ty::Tuple(_) | ty::Array(_, _) | ty::Str | ty::Slice(_) => {
394            let branches = valtree.unwrap_branch();
395
396            // Need to downcast place for enums
397            let (place_adjusted, branches, variant_idx) = match ty.kind() {
398                ty::Adt(def, _) if def.is_enum() => {
399                    // First element of valtree corresponds to variant
400                    let scalar_int = branches[0].unwrap_leaf();
401                    let variant_idx = VariantIdx::from_u32(scalar_int.to_u32());
402                    let variant = def.variant(variant_idx);
403                    debug!(?variant);
404
405                    (
406                        ecx.project_downcast(place, variant_idx).unwrap(),
407                        &branches[1..],
408                        Some(variant_idx),
409                    )
410                }
411                _ => (place.clone(), branches, None),
412            };
413            debug!(?place_adjusted, ?branches);
414
415            // Create the places (by indexing into `place`) for the fields and fill
416            // them recursively
417            for (i, inner_valtree) in branches.iter().enumerate() {
418                debug!(?i, ?inner_valtree);
419
420                let place_inner = match ty.kind() {
421                    ty::Str | ty::Slice(_) | ty::Array(..) => {
422                        ecx.project_index(place, i as u64).unwrap()
423                    }
424                    _ => ecx.project_field(&place_adjusted, FieldIdx::from_usize(i)).unwrap(),
425                };
426
427                debug!(?place_inner);
428                valtree_into_mplace(ecx, &place_inner, *inner_valtree);
429                dump_place(ecx, &place_inner);
430            }
431
432            debug!("dump of place_adjusted:");
433            dump_place(ecx, &place_adjusted);
434
435            if let Some(variant_idx) = variant_idx {
436                // don't forget filling the place with the discriminant of the enum
437                ecx.write_discriminant(variant_idx, place).unwrap();
438            }
439
440            debug!("dump of place after writing discriminant:");
441            dump_place(ecx, place);
442        }
443        _ => bug!("shouldn't have created a ValTree for {:?}", ty),
444    }
445}
446
447fn dump_place<'tcx>(ecx: &CompileTimeInterpCx<'tcx>, place: &MPlaceTy<'tcx>) {
448    trace!("{:?}", ecx.dump_place(&PlaceTy::from(place.clone())));
449}
rustc_const_eval/const_eval/valtrees.rs

rustc_const_eval/const_eval/
valtrees.rs
