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 use super::validity::RefTracking;
7 use rustc::mir::interpret::{ErrorHandled, InterpResult};
8 use rustc::ty::{self, Ty};
9 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
12 use rustc_ast::ast::Mutability;
14 use super::{AllocId, Allocation, InterpCx, MPlaceTy, Machine, MemoryKind, Scalar, ValueVisitor};
16 pub trait CompileTimeMachine<'mir, 'tcx> = Machine<
24 MemoryMap = FxHashMap<AllocId, (MemoryKind<!>, Allocation)>,
27 struct InternVisitor<'rt, 'mir, 'tcx, M: CompileTimeMachine<'mir, 'tcx>> {
28 /// The ectx from which we intern.
29 ecx: &'rt mut InterpCx<'mir, 'tcx, M>,
30 /// Previously encountered safe references.
31 ref_tracking: &'rt mut RefTracking<(MPlaceTy<'tcx>, Mutability, InternMode)>,
32 /// A list of all encountered allocations. After type-based interning, we traverse this list to
33 /// also intern allocations that are only referenced by a raw pointer or inside a union.
34 leftover_allocations: &'rt mut FxHashSet<AllocId>,
35 /// The root node of the value that we're looking at. This field is never mutated and only used
36 /// for sanity assertions that will ICE when `const_qualif` screws up.
38 /// This field stores the mutability of the value *currently* being checked.
39 /// When encountering a mutable reference, we determine the pointee mutability
40 /// taking into account the mutability of the context: `& &mut i32` is entirely immutable,
41 /// despite the nested mutable reference!
42 /// The field gets updated when an `UnsafeCell` is encountered.
43 mutability: Mutability,
45 /// This flag is to avoid triggering UnsafeCells are not allowed behind references in constants
47 /// It's a copy of `mir::Body`'s ignore_interior_mut_in_const_validation field
48 ignore_interior_mut_in_const_validation: bool,
51 #[derive(Copy, Clone, Debug, PartialEq, Hash, Eq)]
53 /// Mutable references must in fact be immutable due to their surrounding immutability in a
54 /// `static`. In a `static mut` we start out as mutable and thus can also contain further `&mut`
55 /// that will actually be treated as mutable.
57 /// UnsafeCell is OK in the value of a constant: `const FOO = Cell::new(0)` creates
58 /// a new cell every time it is used.
60 /// `UnsafeCell` ICEs.
64 /// Signalling data structure to ensure we don't recurse
65 /// into the memory of other constants or statics
68 /// Intern an allocation without looking at its children.
69 /// `mode` is the mode of the environment where we found this pointer.
70 /// `mutablity` is the mutability of the place to be interned; even if that says
71 /// `immutable` things might become mutable if `ty` is not frozen.
72 /// `ty` can be `None` if there is no potential interior mutability
73 /// to account for (e.g. for vtables).
74 fn intern_shallow<'rt, 'mir, 'tcx, M: CompileTimeMachine<'mir, 'tcx>>(
75 ecx: &'rt mut InterpCx<'mir, 'tcx, M>,
76 leftover_allocations: &'rt mut FxHashSet<AllocId>,
79 mutability: Mutability,
81 ) -> InterpResult<'tcx, Option<IsStaticOrFn>> {
82 trace!("InternVisitor::intern {:?} with {:?}", alloc_id, mutability,);
85 let (kind, mut alloc) = match ecx.memory.alloc_map.remove(&alloc_id) {
88 // Pointer not found in local memory map. It is either a pointer to the global
90 // If the pointer is dangling (neither in local nor global memory), we leave it
91 // to validation to error. The `delay_span_bug` ensures that we don't forget such
92 // a check in validation.
93 if tcx.alloc_map.lock().get(alloc_id).is_none() {
94 tcx.sess.delay_span_bug(ecx.tcx.span, "tried to intern dangling pointer");
96 // treat dangling pointers like other statics
97 // just to stop trying to recurse into them
98 return Ok(Some(IsStaticOrFn));
101 // This match is just a canary for future changes to `MemoryKind`, which most likely need
102 // changes in this function.
104 MemoryKind::Stack | MemoryKind::Vtable | MemoryKind::CallerLocation => {}
106 // Set allocation mutability as appropriate. This is used by LLVM to put things into
107 // read-only memory, and also by Miri when evluating other constants/statics that
109 if mode == InternMode::Static {
110 // When `ty` is `None`, we assume no interior mutability.
111 let frozen = ty.map_or(true, |ty| ty.is_freeze(ecx.tcx.tcx, ecx.param_env, ecx.tcx.span));
112 // For statics, allocation mutability is the combination of the place mutability and
113 // the type mutability.
114 // The entire allocation needs to be mutable if it contains an `UnsafeCell` anywhere.
115 if mutability == Mutability::Not && frozen {
116 alloc.mutability = Mutability::Not;
118 // Just making sure we are not "upgrading" an immutable allocation to mutable.
119 assert_eq!(alloc.mutability, Mutability::Mut);
122 // We *could* be non-frozen at `ConstBase`, for constants like `Cell::new(0)`.
123 // But we still intern that as immutable as the memory cannot be changed once the
124 // initial value was computed.
125 // Constants are never mutable.
129 "Something went very wrong: mutability requested for a constant"
131 alloc.mutability = Mutability::Not;
133 // link the alloc id to the actual allocation
134 let alloc = tcx.intern_const_alloc(alloc);
135 leftover_allocations.extend(alloc.relocations().iter().map(|&(_, ((), reloc))| reloc));
136 tcx.alloc_map.lock().set_alloc_id_memory(alloc_id, alloc);
140 impl<'rt, 'mir, 'tcx, M: CompileTimeMachine<'mir, 'tcx>> InternVisitor<'rt, 'mir, 'tcx, M> {
144 mutability: Mutability,
145 ty: Option<Ty<'tcx>>,
146 ) -> InterpResult<'tcx, Option<IsStaticOrFn>> {
147 intern_shallow(self.ecx, self.leftover_allocations, self.mode, alloc_id, mutability, ty)
151 impl<'rt, 'mir, 'tcx, M: CompileTimeMachine<'mir, 'tcx>> ValueVisitor<'mir, 'tcx, M>
152 for InternVisitor<'rt, 'mir, 'tcx, M>
154 type V = MPlaceTy<'tcx>;
157 fn ecx(&self) -> &InterpCx<'mir, 'tcx, M> {
163 mplace: MPlaceTy<'tcx>,
164 fields: impl Iterator<Item = InterpResult<'tcx, Self::V>>,
165 ) -> InterpResult<'tcx> {
166 if let Some(def) = mplace.layout.ty.ty_adt_def() {
167 if Some(def.did) == self.ecx.tcx.lang_items().unsafe_cell_type() {
168 // We are crossing over an `UnsafeCell`, we can mutate again. This means that
169 // References we encounter inside here are interned as pointing to mutable
171 let old = std::mem::replace(&mut self.mutability, Mutability::Mut);
172 if !self.ignore_interior_mut_in_const_validation {
176 "UnsafeCells are not allowed behind references in constants. This should \
177 have been prevented statically by const qualification. If this were \
178 allowed one would be able to change a constant at one use site and other \
179 use sites could observe that mutation.",
182 let walked = self.walk_aggregate(mplace, fields);
183 self.mutability = old;
187 self.walk_aggregate(mplace, fields)
190 fn visit_primitive(&mut self, mplace: MPlaceTy<'tcx>) -> InterpResult<'tcx> {
191 // Handle Reference types, as these are the only relocations supported by const eval.
192 // Raw pointers (and boxes) are handled by the `leftover_relocations` logic.
193 let ty = mplace.layout.ty;
194 if let ty::Ref(_, referenced_ty, mutability) = ty.kind {
195 let value = self.ecx.read_immediate(mplace.into())?;
196 let mplace = self.ecx.ref_to_mplace(value)?;
197 // Handle trait object vtables.
198 if let ty::Dynamic(..) =
199 self.ecx.tcx.struct_tail_erasing_lifetimes(referenced_ty, self.ecx.param_env).kind
201 // Validation has already errored on an invalid vtable pointer so we can safely not
202 // do anything if this is not a real pointer.
203 if let Scalar::Ptr(vtable) = mplace.meta.unwrap_meta() {
204 // Explicitly choose `Immutable` here, since vtables are immutable, even
205 // if the reference of the fat pointer is mutable.
206 self.intern_shallow(vtable.alloc_id, Mutability::Not, None)?;
208 self.ecx().tcx.sess.delay_span_bug(
209 rustc_span::DUMMY_SP,
210 "vtables pointers cannot be integer pointers",
214 // Check if we have encountered this pointer+layout combination before.
215 // Only recurse for allocation-backed pointers.
216 if let Scalar::Ptr(ptr) = mplace.ptr {
217 // We do not have any `frozen` logic here, because it's essentially equivalent to
218 // the mutability except for the outermost item. Only `UnsafeCell` can "unfreeze",
219 // and we check that in `visit_aggregate`.
220 // This is not an inherent limitation, but one that we know to be true, because
221 // const qualification enforces it. We can lift it in the future.
222 match (self.mode, mutability) {
223 // immutable references are fine everywhere
224 (_, hir::Mutability::Not) => {}
225 // all is "good and well" in the unsoundness of `static mut`
227 // mutable references are ok in `static`. Either they are treated as immutable
228 // because they are behind an immutable one, or they are behind an `UnsafeCell`
230 (InternMode::Static, hir::Mutability::Mut) => {}
231 // we statically prevent `&mut T` via `const_qualif` and double check this here
232 (InternMode::ConstBase, hir::Mutability::Mut)
233 | (InternMode::Const, hir::Mutability::Mut) => match referenced_ty.kind {
235 if n.eval_usize(self.ecx.tcx.tcx, self.ecx.param_env) == 0 => {}
237 if mplace.meta.unwrap_meta().to_machine_usize(self.ecx)? == 0 => {}
238 _ => bug!("const qualif failed to prevent mutable references"),
241 // Compute the mutability with which we'll start visiting the allocation. This is
242 // what gets changed when we encounter an `UnsafeCell`.
244 // The only way a mutable reference actually works as a mutable reference is
245 // by being in a `static mut` directly or behind another mutable reference.
246 // If there's an immutable reference or we are inside a static, then our
247 // mutable reference is equivalent to an immutable one. As an example:
248 // `&&mut Foo` is semantically equivalent to `&&Foo`
249 let mutability = self.mutability.and(mutability);
250 // Recursing behind references changes the intern mode for constants in order to
251 // cause assertions to trigger if we encounter any `UnsafeCell`s.
252 let mode = match self.mode {
253 InternMode::ConstBase => InternMode::Const,
256 match self.intern_shallow(ptr.alloc_id, mutability, Some(mplace.layout.ty))? {
257 // No need to recurse, these are interned already and statics may have
258 // cycles, so we don't want to recurse there
259 Some(IsStaticOrFn) => {}
260 // intern everything referenced by this value. The mutability is taken from the
261 // reference. It is checked above that mutable references only happen in
263 None => self.ref_tracking.track((mplace, mutability, mode), || ()),
271 pub enum InternKind {
272 /// The `mutability` of the static, ignoring the type which may have interior mutability.
273 Static(hir::Mutability),
279 pub fn intern_const_alloc_recursive<M: CompileTimeMachine<'mir, 'tcx>>(
280 ecx: &mut InterpCx<'mir, 'tcx, M>,
281 intern_kind: InternKind,
283 ignore_interior_mut_in_const_validation: bool,
284 ) -> InterpResult<'tcx> {
286 let (base_mutability, base_intern_mode) = match intern_kind {
287 // `static mut` doesn't care about interior mutability, it's mutable anyway
288 InternKind::Static(mutbl) => (mutbl, InternMode::Static),
289 // FIXME: what about array lengths, array initializers?
290 InternKind::Constant | InternKind::ConstProp => (Mutability::Not, InternMode::ConstBase),
291 InternKind::Promoted => (Mutability::Not, InternMode::ConstBase),
294 // Type based interning.
295 // `ref_tracking` tracks typed references we have seen and still need to crawl for
296 // more typed information inside them.
297 // `leftover_allocations` collects *all* allocations we see, because some might not
298 // be available in a typed way. They get interned at the end.
299 let mut ref_tracking = RefTracking::new((ret, base_mutability, base_intern_mode));
300 let leftover_allocations = &mut FxHashSet::default();
302 // start with the outermost allocation
305 leftover_allocations,
307 // The outermost allocation must exist, because we allocated it with
308 // `Memory::allocate`.
309 ret.ptr.assert_ptr().alloc_id,
314 while let Some(((mplace, mutability, mode), _)) = ref_tracking.todo.pop() {
315 let interned = InternVisitor {
316 ref_tracking: &mut ref_tracking,
319 leftover_allocations,
321 ignore_interior_mut_in_const_validation,
323 .visit_value(mplace);
324 if let Err(error) = interned {
325 // This can happen when e.g. the tag of an enum is not a valid discriminant. We do have
326 // to read enum discriminants in order to find references in enum variant fields.
327 if let err_unsup!(ValidationFailure(_)) = error.kind {
328 let err = crate::const_eval::error_to_const_error(&ecx, error);
329 match err.struct_error(
331 "it is undefined behavior to use this value",
333 diag.note(crate::const_eval::note_on_undefined_behavior_error());
337 Ok(()) | Err(ErrorHandled::TooGeneric) | Err(ErrorHandled::Reported) => {}
343 // Intern the rest of the allocations as mutable. These might be inside unions, padding, raw
344 // pointers, ... So we can't intern them according to their type rules
346 let mut todo: Vec<_> = leftover_allocations.iter().cloned().collect();
347 while let Some(alloc_id) = todo.pop() {
348 if let Some((_, mut alloc)) = ecx.memory.alloc_map.remove(&alloc_id) {
349 // We can't call the `intern_shallow` method here, as its logic is tailored to safe
350 // references and a `leftover_allocations` set (where we only have a todo-list here).
351 // So we hand-roll the interning logic here again.
353 // Statics may contain mutable allocations even behind relocations.
354 // Even for immutable statics it would be ok to have mutable allocations behind
355 // raw pointers, e.g. for `static FOO: *const AtomicUsize = &AtomicUsize::new(42)`.
356 InternKind::Static(_) => {}
357 // Raw pointers in promoteds may only point to immutable things so we mark
358 // everything as immutable.
359 // It is UB to mutate through a raw pointer obtained via an immutable reference.
360 // Since all references and pointers inside a promoted must by their very definition
361 // be created from an immutable reference (and promotion also excludes interior
362 // mutability), mutating through them would be UB.
363 // There's no way we can check whether the user is using raw pointers correctly,
364 // so all we can do is mark this as immutable here.
365 InternKind::Promoted => {
366 alloc.mutability = Mutability::Not;
368 InternKind::Constant | InternKind::ConstProp => {
369 // If it's a constant, it *must* be immutable.
370 // We cannot have mutable memory inside a constant.
371 // We use `delay_span_bug` here, because this can be reached in the presence
372 // of fancy transmutes.
373 if alloc.mutability == Mutability::Mut {
374 // For better errors later, mark the allocation as immutable
375 // (on top of the delayed ICE).
376 alloc.mutability = Mutability::Not;
377 ecx.tcx.sess.delay_span_bug(ecx.tcx.span, "mutable allocation in constant");
381 let alloc = tcx.intern_const_alloc(alloc);
382 tcx.alloc_map.lock().set_alloc_id_memory(alloc_id, alloc);
383 for &(_, ((), reloc)) in alloc.relocations().iter() {
384 if leftover_allocations.insert(reloc) {
388 } else if ecx.memory.dead_alloc_map.contains_key(&alloc_id) {
390 throw_unsup!(ValidationFailure("encountered dangling pointer in final constant".into()))
391 } else if ecx.tcx.alloc_map.lock().get(alloc_id).is_none() {
392 // We have hit an `AllocId` that is neither in local or global memory and isn't marked
393 // as dangling by local memory.
394 span_bug!(ecx.tcx.span, "encountered unknown alloc id {:?}", alloc_id);