1 //! This module specifies the type based interner for constants.
3 //! After a const evaluation has computed a value, before we destroy the const evaluator's session
4 //! memory, we need to extract all memory allocations to the global memory pool so they stay around.
6 //! In principle, this is not very complicated: we recursively walk the final value, follow all the
7 //! pointers, and move all reachable allocations to the global `tcx` memory. The only complication
8 //! is picking the right mutability for the allocations in a `static` initializer: we want to make
9 //! as many allocations as possible immutable so LLVM can put them into read-only memory. At the
10 //! same time, we need to make memory that could be mutated by the program mutable to avoid
11 //! incorrect compilations. To achieve this, we do a type-based traversal of the final value,
12 //! tracking mutable and shared references and `UnsafeCell` to determine the current mutability.
13 //! (In principle, we could skip this type-based part for `const` and promoteds, as they need to be
14 //! always immutable. At least for `const` however we use this opportunity to reject any `const`
15 //! that contains allocations whose mutability we cannot identify.)
17 use super::validity
::RefTracking
;
18 use rustc_data_structures
::fx
::{FxIndexMap, FxIndexSet}
;
19 use rustc_errors
::ErrorGuaranteed
;
21 use rustc_middle
::mir
::interpret
::InterpResult
;
22 use rustc_middle
::ty
::{self, layout::TyAndLayout, Ty}
;
24 use rustc_ast
::Mutability
;
27 AllocId
, Allocation
, InterpCx
, MPlaceTy
, Machine
, MemoryKind
, PlaceTy
, Projectable
,
30 use crate::const_eval
;
31 use crate::errors
::{DanglingPtrInFinal, UnsupportedUntypedPointer}
;
33 pub trait CompileTimeMachine
<'mir
, 'tcx
: 'mir
, T
> = Machine
<
41 MemoryMap
= FxIndexMap
<AllocId
, (MemoryKind
<T
>, Allocation
)>,
44 struct InternVisitor
<'rt
, 'mir
, 'tcx
, M
: CompileTimeMachine
<'mir
, 'tcx
, const_eval
::MemoryKind
>> {
45 /// The ectx from which we intern.
46 ecx
: &'rt
mut InterpCx
<'mir
, 'tcx
, M
>,
47 /// Previously encountered safe references.
48 ref_tracking
: &'rt
mut RefTracking
<(MPlaceTy
<'tcx
>, InternMode
)>,
49 /// A list of all encountered allocations. After type-based interning, we traverse this list to
50 /// also intern allocations that are only referenced by a raw pointer or inside a union.
51 leftover_allocations
: &'rt
mut FxIndexSet
<AllocId
>,
52 /// The root kind of the value that we're looking at. This field is never mutated for a
53 /// particular allocation. It is primarily used to make as many allocations as possible
54 /// read-only so LLVM can place them in const memory.
56 /// This field stores whether we are *currently* inside an `UnsafeCell`. This can affect
57 /// the intern mode of references we encounter.
58 inside_unsafe_cell
: bool
,
61 #[derive(Copy, Clone, Debug, PartialEq, Hash, Eq)]
63 /// A static and its current mutability. Below shared references inside a `static mut`,
64 /// this is *immutable*, and below mutable references inside an `UnsafeCell`, this
66 Static(hir
::Mutability
),
71 /// Signalling data structure to ensure we don't recurse
72 /// into the memory of other constants or statics
75 /// Intern an allocation without looking at its children.
76 /// `mode` is the mode of the environment where we found this pointer.
77 /// `mutability` is the mutability of the place to be interned; even if that says
78 /// `immutable` things might become mutable if `ty` is not frozen.
79 /// `ty` can be `None` if there is no potential interior mutability
80 /// to account for (e.g. for vtables).
81 fn intern_shallow
<'rt
, 'mir
, 'tcx
, M
: CompileTimeMachine
<'mir
, 'tcx
, const_eval
::MemoryKind
>>(
82 ecx
: &'rt
mut InterpCx
<'mir
, 'tcx
, M
>,
83 leftover_allocations
: &'rt
mut FxIndexSet
<AllocId
>,
87 ) -> Option
<IsStaticOrFn
> {
88 trace
!("intern_shallow {:?} with {:?}", alloc_id
, mode
);
91 let Some((kind
, mut alloc
)) = ecx
.memory
.alloc_map
.remove(&alloc_id
) else {
92 // Pointer not found in local memory map. It is either a pointer to the global
94 // If the pointer is dangling (neither in local nor global memory), we leave it
95 // to validation to error -- it has the much better error messages, pointing out where
96 // in the value the dangling reference lies.
97 // The `delay_span_bug` ensures that we don't forget such a check in validation.
98 if tcx
.try_get_global_alloc(alloc_id
).is_none() {
99 tcx
.sess
.delay_span_bug(ecx
.tcx
.span
, "tried to intern dangling pointer");
101 // treat dangling pointers like other statics
102 // just to stop trying to recurse into them
103 return Some(IsStaticOrFn
);
105 // This match is just a canary for future changes to `MemoryKind`, which most likely need
106 // changes in this function.
109 | MemoryKind
::Machine(const_eval
::MemoryKind
::Heap
)
110 | MemoryKind
::CallerLocation
=> {}
112 // Set allocation mutability as appropriate. This is used by LLVM to put things into
113 // read-only memory, and also by Miri when evaluating other globals that
115 if let InternMode
::Static(mutability
) = mode
{
116 // For this, we need to take into account `UnsafeCell`. When `ty` is `None`, we assume
117 // no interior mutability.
118 let frozen
= ty
.map_or(true, |ty
| ty
.is_freeze(*ecx
.tcx
, ecx
.param_env
));
119 // For statics, allocation mutability is the combination of place mutability and
121 // The entire allocation needs to be mutable if it contains an `UnsafeCell` anywhere.
122 let immutable
= mutability
== Mutability
::Not
&& frozen
;
124 alloc
.mutability
= Mutability
::Not
;
126 // Just making sure we are not "upgrading" an immutable allocation to mutable.
127 assert_eq
!(alloc
.mutability
, Mutability
::Mut
);
130 // No matter what, *constants are never mutable*. Mutating them is UB.
131 // See const_eval::machine::MemoryExtra::can_access_statics for why
132 // immutability is so important.
134 // Validation will ensure that there is no `UnsafeCell` on an immutable allocation.
135 alloc
.mutability
= Mutability
::Not
;
137 // link the alloc id to the actual allocation
138 leftover_allocations
.extend(alloc
.provenance().ptrs().iter().map(|&(_
, alloc_id
)| alloc_id
));
139 let alloc
= tcx
.mk_const_alloc(alloc
);
140 tcx
.set_alloc_id_memory(alloc_id
, alloc
);
144 impl<'rt
, 'mir
, 'tcx
, M
: CompileTimeMachine
<'mir
, 'tcx
, const_eval
::MemoryKind
>>
145 InternVisitor
<'rt
, 'mir
, 'tcx
, M
>
151 ty
: Option
<Ty
<'tcx
>>,
152 ) -> Option
<IsStaticOrFn
> {
153 intern_shallow(self.ecx
, self.leftover_allocations
, alloc_id
, mode
, ty
)
157 impl<'rt
, 'mir
, 'tcx
: 'mir
, M
: CompileTimeMachine
<'mir
, 'tcx
, const_eval
::MemoryKind
>>
158 ValueVisitor
<'mir
, 'tcx
, M
> for InternVisitor
<'rt
, 'mir
, 'tcx
, M
>
160 type V
= MPlaceTy
<'tcx
>;
163 fn ecx(&self) -> &InterpCx
<'mir
, 'tcx
, M
> {
167 fn visit_value(&mut self, mplace
: &MPlaceTy
<'tcx
>) -> InterpResult
<'tcx
> {
168 // Handle Reference types, as these are the only types with provenance supported by const eval.
169 // Raw pointers (and boxes) are handled by the `leftover_allocations` logic.
170 let tcx
= self.ecx
.tcx
;
171 let ty
= mplace
.layout
.ty
;
172 if let ty
::Ref(_
, referenced_ty
, ref_mutability
) = *ty
.kind() {
173 let value
= self.ecx
.read_immediate(mplace
)?
;
174 let mplace
= self.ecx
.ref_to_mplace(&value
)?
;
175 assert_eq
!(mplace
.layout
.ty
, referenced_ty
);
176 // Handle trait object vtables.
177 if let ty
::Dynamic(_
, _
, ty
::Dyn
) =
178 tcx
.struct_tail_erasing_lifetimes(referenced_ty
, self.ecx
.param_env
).kind()
180 let ptr
= mplace
.meta().unwrap_meta().to_pointer(&tcx
)?
;
181 if let Some(alloc_id
) = ptr
.provenance
{
182 // Explicitly choose const mode here, since vtables are immutable, even
183 // if the reference of the fat pointer is mutable.
184 self.intern_shallow(alloc_id
, InternMode
::Const
, None
);
186 // Validation will error (with a better message) on an invalid vtable pointer.
187 // Let validation show the error message, but make sure it *does* error.
189 .delay_span_bug(tcx
.span
, "vtables pointers cannot be integer pointers");
192 // Check if we have encountered this pointer+layout combination before.
193 // Only recurse for allocation-backed pointers.
194 if let Some(alloc_id
) = mplace
.ptr().provenance
{
195 // Compute the mode with which we intern this. Our goal here is to make as many
196 // statics as we can immutable so they can be placed in read-only memory by LLVM.
197 let ref_mode
= match self.mode
{
198 InternMode
::Static(mutbl
) => {
199 // In statics, merge outer mutability with reference mutability and
200 // take into account whether we are in an `UnsafeCell`.
202 // The only way a mutable reference actually works as a mutable reference is
203 // by being in a `static mut` directly or behind another mutable reference.
204 // If there's an immutable reference or we are inside a `static`, then our
205 // mutable reference is equivalent to an immutable one. As an example:
206 // `&&mut Foo` is semantically equivalent to `&&Foo`
207 match ref_mutability
{
208 _
if self.inside_unsafe_cell
=> {
209 // Inside an `UnsafeCell` is like inside a `static mut`, the "outer"
210 // mutability does not matter.
211 InternMode
::Static(ref_mutability
)
214 // A shared reference, things become immutable.
215 // We do *not* consider `freeze` here: `intern_shallow` considers
216 // `freeze` for the actual mutability of this allocation; the intern
217 // mode for references contained in this allocation is tracked more
218 // precisely when traversing the referenced data (by tracking
219 // `UnsafeCell`). This makes sure that `&(&i32, &Cell<i32>)` still
220 // has the left inner reference interned into a read-only
222 InternMode
::Static(Mutability
::Not
)
225 // Mutable reference.
226 InternMode
::Static(mutbl
)
230 InternMode
::Const
=> {
231 // Ignore `UnsafeCell`, everything is immutable. Validity does some sanity
232 // checking for mutable references that we encounter -- they must all be
237 match self.intern_shallow(alloc_id
, ref_mode
, Some(referenced_ty
)) {
238 // No need to recurse, these are interned already and statics may have
239 // cycles, so we don't want to recurse there
240 Some(IsStaticOrFn
) => {}
241 // intern everything referenced by this value. The mutability is taken from the
242 // reference. It is checked above that mutable references only happen in
244 None
=> self.ref_tracking
.track((mplace
, ref_mode
), || ()),
249 // Not a reference. Check if we want to recurse.
250 let is_walk_needed
= |mplace
: &MPlaceTy
<'tcx
>| -> InterpResult
<'tcx
, bool
> {
251 // ZSTs cannot contain pointers, we can avoid the interning walk.
252 if mplace
.layout
.is_zst() {
256 // Now, check whether this allocation could contain references.
258 // Note, this check may sometimes not be cheap, so we only do it when the walk we'd like
259 // to avoid could be expensive: on the potentially larger types, arrays and slices,
260 // rather than on all aggregates unconditionally.
261 if matches
!(mplace
.layout
.ty
.kind(), ty
::Array(..) | ty
::Slice(..)) {
262 let Some((size
, _align
)) = self.ecx
.size_and_align_of_mplace(&mplace
)?
else {
263 // We do the walk if we can't determine the size of the mplace: we may be
264 // dealing with extern types here in the future.
268 // If there is no provenance in this allocation, it does not contain references
269 // that point to another allocation, and we can avoid the interning walk.
270 if let Some(alloc
) = self.ecx
.get_ptr_alloc(mplace
.ptr(), size
)?
{
271 if !alloc
.has_provenance() {
275 // We're encountering a ZST here, and can avoid the walk as well.
280 // In the general case, we do the walk.
284 // If this allocation contains no references to intern, we avoid the potentially costly
287 // We can do this before the checks for interior mutability below, because only references
288 // are relevant in that situation, and we're checking if there are any here.
289 if !is_walk_needed(mplace
)?
{
293 if let Some(def
) = mplace
.layout
.ty
.ty_adt_def() {
294 if def
.is_unsafe_cell() {
295 // We are crossing over an `UnsafeCell`, we can mutate again. This means that
296 // References we encounter inside here are interned as pointing to mutable
298 // Remember the `old` value to handle nested `UnsafeCell`.
299 let old
= std
::mem
::replace(&mut self.inside_unsafe_cell
, true);
300 let walked
= self.walk_value(mplace
);
301 self.inside_unsafe_cell
= old
;
306 self.walk_value(mplace
)
311 /// How a constant value should be interned.
312 #[derive(Copy, Clone, Debug, PartialEq, Hash, Eq)]
313 pub enum InternKind
{
314 /// The `mutability` of the static, ignoring the type which may have interior mutability.
315 Static(hir
::Mutability
),
321 /// Intern `ret` and everything it references.
323 /// This *cannot raise an interpreter error*. Doing so is left to validation, which
324 /// tracks where in the value we are and thus can show much better error messages.
325 #[instrument(level = "debug", skip(ecx))]
326 pub fn intern_const_alloc_recursive
<
329 M
: CompileTimeMachine
<'mir
, 'tcx
, const_eval
::MemoryKind
>,
331 ecx
: &mut InterpCx
<'mir
, 'tcx
, M
>,
332 intern_kind
: InternKind
,
333 ret
: &MPlaceTy
<'tcx
>,
334 ) -> Result
<(), ErrorGuaranteed
> {
336 let base_intern_mode
= match intern_kind
{
337 InternKind
::Static(mutbl
) => InternMode
::Static(mutbl
),
338 // `Constant` includes array lengths.
339 InternKind
::Constant
| InternKind
::Promoted
=> InternMode
::Const
,
342 // Type based interning.
343 // `ref_tracking` tracks typed references we have already interned and still need to crawl for
344 // more typed information inside them.
345 // `leftover_allocations` collects *all* allocations we see, because some might not
346 // be available in a typed way. They get interned at the end.
347 let mut ref_tracking
= RefTracking
::empty();
348 let leftover_allocations
= &mut FxIndexSet
::default();
350 // start with the outermost allocation
353 leftover_allocations
,
354 // The outermost allocation must exist, because we allocated it with
355 // `Memory::allocate`.
356 ret
.ptr().provenance
.unwrap(),
361 ref_tracking
.track((ret
.clone(), base_intern_mode
), || ());
363 while let Some(((mplace
, mode
), _
)) = ref_tracking
.todo
.pop() {
364 let res
= InternVisitor
{
365 ref_tracking
: &mut ref_tracking
,
368 leftover_allocations
,
369 inside_unsafe_cell
: false,
371 .visit_value(&mplace
);
372 // We deliberately *ignore* interpreter errors here. When there is a problem, the remaining
373 // references are "leftover"-interned, and later validation will show a proper error
374 // and point at the right part of the value causing the problem.
378 ecx
.tcx
.sess
.delay_span_bug(
381 "error during interning should later cause validation failure: {}",
382 ecx
.format_error(error
),
389 // Intern the rest of the allocations as mutable. These might be inside unions, padding, raw
390 // pointers, ... So we can't intern them according to their type rules
392 let mut todo
: Vec
<_
> = leftover_allocations
.iter().cloned().collect();
394 debug
!("dead_alloc_map: {:#?}", ecx
.memory
.dead_alloc_map
);
395 while let Some(alloc_id
) = todo
.pop() {
396 if let Some((_
, mut alloc
)) = ecx
.memory
.alloc_map
.remove(&alloc_id
) {
397 // We can't call the `intern_shallow` method here, as its logic is tailored to safe
398 // references and a `leftover_allocations` set (where we only have a todo-list here).
399 // So we hand-roll the interning logic here again.
401 // Statics may point to mutable allocations.
402 // Even for immutable statics it would be ok to have mutable allocations behind
403 // raw pointers, e.g. for `static FOO: *const AtomicUsize = &AtomicUsize::new(42)`.
404 InternKind
::Static(_
) => {}
405 // Raw pointers in promoteds may only point to immutable things so we mark
406 // everything as immutable.
407 // It is UB to mutate through a raw pointer obtained via an immutable reference:
408 // Since all references and pointers inside a promoted must by their very definition
409 // be created from an immutable reference (and promotion also excludes interior
410 // mutability), mutating through them would be UB.
411 // There's no way we can check whether the user is using raw pointers correctly,
412 // so all we can do is mark this as immutable here.
413 InternKind
::Promoted
=> {
414 // See const_eval::machine::MemoryExtra::can_access_statics for why
415 // immutability is so important.
416 alloc
.mutability
= Mutability
::Not
;
418 // If it's a constant, we should not have any "leftovers" as everything
419 // is tracked by const-checking.
420 // FIXME: downgrade this to a warning? It rejects some legitimate consts,
421 // such as `const CONST_RAW: *const Vec<i32> = &Vec::new() as *const _;`.
423 // NOTE: it looks likes this code path is only reachable when we try to intern
424 // something that cannot be promoted, which in constants means values that have
425 // drop glue, such as the example above.
426 InternKind
::Constant
=> {
427 ecx
.tcx
.sess
.emit_err(UnsupportedUntypedPointer { span: ecx.tcx.span }
);
428 // For better errors later, mark the allocation as immutable.
429 alloc
.mutability
= Mutability
::Not
;
432 let alloc
= tcx
.mk_const_alloc(alloc
);
433 tcx
.set_alloc_id_memory(alloc_id
, alloc
);
434 for &(_
, alloc_id
) in alloc
.inner().provenance().ptrs().iter() {
435 if leftover_allocations
.insert(alloc_id
) {
439 } else if ecx
.memory
.dead_alloc_map
.contains_key(&alloc_id
) {
440 // Codegen does not like dangling pointers, and generally `tcx` assumes that
441 // all allocations referenced anywhere actually exist. So, make sure we error here.
442 let reported
= ecx
.tcx
.sess
.emit_err(DanglingPtrInFinal { span: ecx.tcx.span }
);
443 return Err(reported
);
444 } else if ecx
.tcx
.try_get_global_alloc(alloc_id
).is_none() {
445 // We have hit an `AllocId` that is neither in local or global memory and isn't
446 // marked as dangling by local memory. That should be impossible.
447 span_bug
!(ecx
.tcx
.span
, "encountered unknown alloc id {:?}", alloc_id
);
453 /// Intern `ret`. This function assumes that `ret` references no other allocation.
454 #[instrument(level = "debug", skip(ecx))]
455 pub fn intern_const_alloc_for_constprop
<
459 M
: CompileTimeMachine
<'mir
, 'tcx
, T
>,
461 ecx
: &mut InterpCx
<'mir
, 'tcx
, M
>,
463 ) -> InterpResult
<'tcx
, ()> {
464 // Move allocation to `tcx`.
465 let Some((_
, mut alloc
)) = ecx
.memory
.alloc_map
.remove(&alloc_id
) else {
466 // Pointer not found in local memory map. It is either a pointer to the global
468 if ecx
.tcx
.try_get_global_alloc(alloc_id
).is_none() {
471 // The constant is already in global memory. Do nothing.
475 alloc
.mutability
= Mutability
::Not
;
477 // We are not doing recursive interning, so we don't currently support provenance.
478 // (If this assertion ever triggers, we should just implement a
479 // proper recursive interning loop.)
480 assert
!(alloc
.provenance().ptrs().is_empty());
482 // Link the alloc id to the actual allocation
483 let alloc
= ecx
.tcx
.mk_const_alloc(alloc
);
484 ecx
.tcx
.set_alloc_id_memory(alloc_id
, alloc
);
489 impl<'mir
, 'tcx
: 'mir
, M
: super::intern
::CompileTimeMachine
<'mir
, 'tcx
, !>>
490 InterpCx
<'mir
, 'tcx
, M
>
492 /// A helper function that allocates memory for the layout given and gives you access to mutate
493 /// it. Once your own mutation code is done, the backing `Allocation` is removed from the
494 /// current `Memory` and interned as read-only into the global memory.
495 pub fn intern_with_temp_alloc(
497 layout
: TyAndLayout
<'tcx
>,
499 &mut InterpCx
<'mir
, 'tcx
, M
>,
500 &PlaceTy
<'tcx
, M
::Provenance
>,
501 ) -> InterpResult
<'tcx
, ()>,
502 ) -> InterpResult
<'tcx
, AllocId
> {
503 // `allocate` picks a fresh AllocId that we will associate with its data below.
504 let dest
= self.allocate(layout
, MemoryKind
::Stack
)?
;
505 f(self, &dest
.clone().into())?
;
506 let mut alloc
= self.memory
.alloc_map
.remove(&dest
.ptr().provenance
.unwrap()).unwrap().1;
507 alloc
.mutability
= Mutability
::Not
;
508 let alloc
= self.tcx
.mk_const_alloc(alloc
);
509 let alloc_id
= dest
.ptr().provenance
.unwrap(); // this was just allocated, it must have provenance
510 self.tcx
.set_alloc_id_memory(alloc_id
, alloc
);