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 rustc::ty::{Ty, ParamEnv, self};
7 use rustc::mir::interpret::{InterpResult, ErrorHandled};
9 use rustc::hir::def_id::DefId;
10 use super::validity::RefTracking;
11 use rustc_data_structures::fx::FxHashSet;
13 use syntax::ast::Mutability;
16 ValueVisitor, MemoryKind, AllocId, MPlaceTy, Scalar,
18 use crate::const_eval::{CompileTimeInterpreter, CompileTimeEvalContext};
20 struct InternVisitor<'rt, 'mir, 'tcx> {
21 /// previously encountered safe references
22 ref_tracking: &'rt mut RefTracking<(MPlaceTy<'tcx>, Mutability, InternMode)>,
23 ecx: &'rt mut CompileTimeEvalContext<'mir, 'tcx>,
24 param_env: ParamEnv<'tcx>,
25 /// The root node of the value that we're looking at. This field is never mutated and only used
26 /// for sanity assertions that will ICE when `const_qualif` screws up.
28 /// This field stores the mutability of the value *currently* being checked.
29 /// When encountering a mutable reference, we determine the pointee mutability
30 /// taking into account the mutability of the context: `& &mut i32` is entirely immutable,
31 /// despite the nested mutable reference!
32 /// The field gets updated when an `UnsafeCell` is encountered.
33 mutability: Mutability,
34 /// A list of all encountered relocations. After type-based interning, we traverse this list to
35 /// also intern allocations that are only referenced by a raw pointer or inside a union.
36 leftover_relocations: &'rt mut FxHashSet<AllocId>,
39 #[derive(Copy, Clone, Debug, PartialEq, Hash, Eq)]
41 /// Mutable references must in fact be immutable due to their surrounding immutability in a
42 /// `static`. In a `static mut` we start out as mutable and thus can also contain further `&mut`
43 /// that will actually be treated as mutable.
45 /// UnsafeCell is OK in the value of a constant: `const FOO = Cell::new(0)` creates
46 /// a new cell every time it is used.
48 /// `UnsafeCell` ICEs.
52 /// Signalling data structure to ensure we don't recurse
53 /// into the memory of other constants or statics
56 impl<'rt, 'mir, 'tcx> InternVisitor<'rt, 'mir, 'tcx> {
57 /// Intern an allocation without looking at its children.
58 /// `mutablity` is the mutability of the place to be interned; even if that says
59 /// `immutable` things might become mutable if `ty` is not frozen.
63 mutability: Mutability,
65 ) -> InterpResult<'tcx, Option<IsStaticOrFn>> {
67 "InternVisitor::intern {:?} with {:?}",
71 let tcx = self.ecx.tcx;
72 let memory = self.ecx.memory_mut();
73 let (kind, mut alloc) = match memory.alloc_map.remove(&alloc_id) {
76 // Pointer not found in local memory map. It is either a pointer to the global
78 // If the pointer is dangling (neither in local nor global memory), we leave it
79 // to validation to error. The `delay_span_bug` ensures that we don't forget such
80 // a check in validation.
81 if tcx.alloc_map.lock().get(alloc_id).is_none() {
82 tcx.sess.delay_span_bug(self.ecx.tcx.span, "tried to intern dangling pointer");
84 // treat dangling pointers like other statics
85 // just to stop trying to recurse into them
86 return Ok(Some(IsStaticOrFn));
89 // This match is just a canary for future changes to `MemoryKind`, which most likely need
90 // changes in this function.
92 MemoryKind::Stack | MemoryKind::Vtable => {},
94 // Set allocation mutability as appropriate. This is used by LLVM to put things into
95 // read-only memory, and also by Miri when evluating other constants/statics that
97 if self.mode == InternMode::Static {
98 let frozen = ty.map_or(true, |ty| ty.is_freeze(
103 // For statics, allocation mutability is the combination of the place mutability and
104 // the type mutability.
105 // The entire allocation needs to be mutable if it contains an `UnsafeCell` anywhere.
106 if mutability == Mutability::Immutable && frozen {
107 alloc.mutability = Mutability::Immutable;
109 // Just making sure we are not "upgrading" an immutable allocation to mutable.
110 assert_eq!(alloc.mutability, Mutability::Mutable);
113 // We *could* be non-frozen at `ConstBase`, for constants like `Cell::new(0)`.
114 // But we still intern that as immutable as the memory cannot be changed once the
115 // initial value was computed.
116 // Constants are never mutable.
117 alloc.mutability = Mutability::Immutable;
119 // link the alloc id to the actual allocation
120 let alloc = tcx.intern_const_alloc(alloc);
121 self.leftover_relocations.extend(alloc.relocations().iter().map(|&(_, ((), reloc))| reloc));
122 tcx.alloc_map.lock().set_alloc_id_memory(alloc_id, alloc);
127 impl<'rt, 'mir, 'tcx>
128 ValueVisitor<'mir, 'tcx, CompileTimeInterpreter<'mir, 'tcx>>
130 InternVisitor<'rt, 'mir, 'tcx>
132 type V = MPlaceTy<'tcx>;
135 fn ecx(&self) -> &CompileTimeEvalContext<'mir, 'tcx> {
141 mplace: MPlaceTy<'tcx>,
142 fields: impl Iterator<Item=InterpResult<'tcx, Self::V>>,
143 ) -> InterpResult<'tcx> {
144 if let Some(def) = mplace.layout.ty.ty_adt_def() {
145 if Some(def.did) == self.ecx.tcx.lang_items().unsafe_cell_type() {
146 // We are crossing over an `UnsafeCell`, we can mutate again. This means that
147 // References we encounter inside here are interned as pointing to mutable
149 let old = std::mem::replace(&mut self.mutability, Mutability::Mutable);
151 self.mode, InternMode::Const,
152 "UnsafeCells are not allowed behind references in constants. This should have \
153 been prevented statically by const qualification. If this were allowed one \
154 would be able to change a constant at one use site and other use sites could \
155 observe that mutation.",
157 let walked = self.walk_aggregate(mplace, fields);
158 self.mutability = old;
162 self.walk_aggregate(mplace, fields)
165 fn visit_primitive(&mut self, mplace: MPlaceTy<'tcx>) -> InterpResult<'tcx> {
166 // Handle Reference types, as these are the only relocations supported by const eval.
167 // Raw pointers (and boxes) are handled by the `leftover_relocations` logic.
168 let ty = mplace.layout.ty;
169 if let ty::Ref(_, referenced_ty, mutability) = ty.sty {
170 let value = self.ecx.read_immediate(mplace.into())?;
171 // Handle trait object vtables
172 if let Ok(meta) = value.to_meta() {
173 if let ty::Dynamic(..) =
174 self.ecx.tcx.struct_tail_erasing_lifetimes(referenced_ty, self.param_env).sty
176 if let Ok(vtable) = meta.unwrap().to_ptr() {
177 // explitly choose `Immutable` here, since vtables are immutable, even
178 // if the reference of the fat pointer is mutable
179 self.intern_shallow(vtable.alloc_id, Mutability::Immutable, None)?;
183 let mplace = self.ecx.ref_to_mplace(value)?;
184 // Check if we have encountered this pointer+layout combination before.
185 // Only recurse for allocation-backed pointers.
186 if let Scalar::Ptr(ptr) = mplace.ptr {
187 // We do not have any `frozen` logic here, because it's essentially equivalent to
188 // the mutability except for the outermost item. Only `UnsafeCell` can "unfreeze",
189 // and we check that in `visit_aggregate`.
190 // This is not an inherent limitation, but one that we know to be true, because
191 // const qualification enforces it. We can lift it in the future.
192 match (self.mode, mutability) {
193 // immutable references are fine everywhere
194 (_, hir::Mutability::MutImmutable) => {},
195 // all is "good and well" in the unsoundness of `static mut`
197 // mutable references are ok in `static`. Either they are treated as immutable
198 // because they are behind an immutable one, or they are behind an `UnsafeCell`
200 (InternMode::Static, hir::Mutability::MutMutable) => {},
201 // we statically prevent `&mut T` via `const_qualif` and double check this here
202 (InternMode::ConstBase, hir::Mutability::MutMutable) |
203 (InternMode::Const, hir::Mutability::MutMutable) => {
204 match referenced_ty.sty {
206 if n.eval_usize(self.ecx.tcx.tcx, self.param_env) == 0 => {}
208 if value.to_meta().unwrap().unwrap().to_usize(self.ecx)? == 0 => {}
209 _ => bug!("const qualif failed to prevent mutable references"),
213 // Compute the mutability with which we'll start visiting the allocation. This is
214 // what gets changed when we encounter an `UnsafeCell`
215 let mutability = match (self.mutability, mutability) {
216 // The only way a mutable reference actually works as a mutable reference is
217 // by being in a `static mut` directly or behind another mutable reference.
218 // If there's an immutable reference or we are inside a static, then our
219 // mutable reference is equivalent to an immutable one. As an example:
220 // `&&mut Foo` is semantically equivalent to `&&Foo`
221 (Mutability::Mutable, hir::Mutability::MutMutable) => Mutability::Mutable,
222 _ => Mutability::Immutable,
224 // Recursing behind references changes the intern mode for constants in order to
225 // cause assertions to trigger if we encounter any `UnsafeCell`s.
226 let mode = match self.mode {
227 InternMode::ConstBase => InternMode::Const,
230 match self.intern_shallow(ptr.alloc_id, mutability, Some(mplace.layout.ty))? {
231 // No need to recurse, these are interned already and statics may have
232 // cycles, so we don't want to recurse there
233 Some(IsStaticOrFn) => {},
234 // intern everything referenced by this value. The mutability is taken from the
235 // reference. It is checked above that mutable references only happen in
237 None => self.ref_tracking.track((mplace, mutability, mode), || ()),
245 pub fn intern_const_alloc_recursive(
246 ecx: &mut CompileTimeEvalContext<'mir, 'tcx>,
249 // FIXME(oli-obk): can we scrap the param env? I think we can, the final value of a const eval
250 // must always be monomorphic, right?
251 param_env: ty::ParamEnv<'tcx>,
252 ) -> InterpResult<'tcx> {
254 // this `mutability` is the mutability of the place, ignoring the type
255 let (base_mutability, base_intern_mode) = match tcx.static_mutability(def_id) {
256 Some(hir::Mutability::MutImmutable) => (Mutability::Immutable, InternMode::Static),
257 None => (Mutability::Immutable, InternMode::ConstBase),
258 // `static mut` doesn't care about interior mutability, it's mutable anyway
259 Some(hir::Mutability::MutMutable) => (Mutability::Mutable, InternMode::Static),
262 // type based interning
263 let mut ref_tracking = RefTracking::new((ret, base_mutability, base_intern_mode));
264 let leftover_relocations = &mut FxHashSet::default();
266 // start with the outermost allocation
268 ref_tracking: &mut ref_tracking,
270 mode: base_intern_mode,
271 leftover_relocations,
273 mutability: base_mutability,
274 }.intern_shallow(ret.ptr.to_ptr()?.alloc_id, base_mutability, Some(ret.layout.ty))?;
276 while let Some(((mplace, mutability, mode), _)) = ref_tracking.todo.pop() {
277 let interned = InternVisitor {
278 ref_tracking: &mut ref_tracking,
281 leftover_relocations,
284 }.visit_value(mplace);
285 if let Err(error) = interned {
286 // This can happen when e.g. the tag of an enum is not a valid discriminant. We do have
287 // to read enum discriminants in order to find references in enum variant fields.
288 if let err_unsup!(ValidationFailure(_)) = error.kind {
289 let err = crate::const_eval::error_to_const_error(&ecx, error);
290 match err.struct_error(ecx.tcx, "it is undefined behavior to use this value") {
292 diag.note(crate::const_eval::note_on_undefined_behavior_error());
295 Err(ErrorHandled::TooGeneric) |
296 Err(ErrorHandled::Reported) => {},
302 // Intern the rest of the allocations as mutable. These might be inside unions, padding, raw
303 // pointers, ... So we can't intern them according to their type rules
305 let mut todo: Vec<_> = leftover_relocations.iter().cloned().collect();
306 while let Some(alloc_id) = todo.pop() {
307 if let Some((_, mut alloc)) = ecx.memory_mut().alloc_map.remove(&alloc_id) {
308 // We can't call the `intern_shallow` method here, as its logic is tailored to safe
309 // references. So we hand-roll the interning logic here again.
310 if base_intern_mode != InternMode::Static {
311 // If it's not a static, it *must* be immutable.
312 // We cannot have mutable memory inside a constant.
313 alloc.mutability = Mutability::Immutable;
315 let alloc = tcx.intern_const_alloc(alloc);
316 tcx.alloc_map.lock().set_alloc_id_memory(alloc_id, alloc);
317 for &(_, ((), reloc)) in alloc.relocations().iter() {
318 if leftover_relocations.insert(reloc) {
322 } else if ecx.memory().dead_alloc_map.contains_key(&alloc_id) {
324 throw_unsup!(ValidationFailure("encountered dangling pointer in final constant".into()))