1 //! An interpreter for MIR used in CTFE and by miri.
4 macro_rules! err_unsup {
6 $crate::mir::interpret::InterpError::Unsupported(
7 $crate::mir::interpret::UnsupportedOpInfo::$($tt)*
13 macro_rules! err_unsup_format {
14 ($($tt:tt)*) => { err_unsup!(Unsupported(format!($($tt)*))) };
18 macro_rules! err_inval {
20 $crate::mir::interpret::InterpError::InvalidProgram(
21 $crate::mir::interpret::InvalidProgramInfo::$($tt)*
29 $crate::mir::interpret::InterpError::UndefinedBehavior(
30 $crate::mir::interpret::UndefinedBehaviorInfo::$($tt)*
36 macro_rules! err_ub_format {
37 ($($tt:tt)*) => { err_ub!(Ub(format!($($tt)*))) };
41 macro_rules! err_exhaust {
43 $crate::mir::interpret::InterpError::ResourceExhaustion(
44 $crate::mir::interpret::ResourceExhaustionInfo::$($tt)*
50 macro_rules! err_machine_stop {
52 $crate::mir::interpret::InterpError::MachineStop(Box::new($($tt)*))
56 // In the `throw_*` macros, avoid `return` to make them work with `try {}`.
58 macro_rules! throw_unsup {
59 ($($tt:tt)*) => { Err::<!, _>(err_unsup!($($tt)*))? };
63 macro_rules! throw_unsup_format {
64 ($($tt:tt)*) => { throw_unsup!(Unsupported(format!($($tt)*))) };
68 macro_rules! throw_inval {
69 ($($tt:tt)*) => { Err::<!, _>(err_inval!($($tt)*))? };
73 macro_rules! throw_ub {
74 ($($tt:tt)*) => { Err::<!, _>(err_ub!($($tt)*))? };
78 macro_rules! throw_ub_format {
79 ($($tt:tt)*) => { throw_ub!(Ub(format!($($tt)*))) };
83 macro_rules! throw_exhaust {
84 ($($tt:tt)*) => { Err::<!, _>(err_exhaust!($($tt)*))? };
88 macro_rules! throw_machine_stop {
89 ($($tt:tt)*) => { Err::<!, _>(err_machine_stop!($($tt)*))? };
98 use std::convert::TryFrom;
101 use std::io::{Read, Write};
102 use std::num::NonZeroU32;
103 use std::sync::atomic::{AtomicU32, Ordering};
105 use rustc_ast::LitKind;
106 use rustc_data_structures::fx::FxHashMap;
107 use rustc_data_structures::sync::{HashMapExt, Lock};
108 use rustc_data_structures::tiny_list::TinyList;
109 use rustc_hir::def_id::DefId;
110 use rustc_macros::HashStable;
111 use rustc_middle::ty::print::with_no_trimmed_paths;
112 use rustc_serialize::{Decodable, Encodable};
113 use rustc_target::abi::{Endian, Size};
116 use crate::ty::codec::{TyDecoder, TyEncoder};
117 use crate::ty::subst::GenericArgKind;
118 use crate::ty::{self, Instance, Ty, TyCtxt};
120 pub use self::error::{
121 struct_error, CheckInAllocMsg, ErrorHandled, EvalToAllocationRawResult, EvalToConstValueResult,
122 InterpError, InterpErrorInfo, InterpResult, InvalidProgramInfo, MachineStopType,
123 ResourceExhaustionInfo, UndefinedBehaviorInfo, UninitBytesAccess, UnsupportedOpInfo,
126 pub use self::value::{get_slice_bytes, ConstAlloc, ConstValue, Scalar, ScalarMaybeUninit};
128 pub use self::allocation::{Allocation, AllocationExtra, InitMask, Relocations};
130 pub use self::pointer::{Pointer, PointerArithmetic};
132 /// Uniquely identifies one of the following:
135 /// - A const fn where all arguments (if any) are zero-sized types
136 #[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, TyEncodable, TyDecodable)]
137 #[derive(HashStable, Lift)]
138 pub struct GlobalId<'tcx> {
139 /// For a constant or static, the `Instance` of the item itself.
140 /// For a promoted global, the `Instance` of the function they belong to.
141 pub instance: ty::Instance<'tcx>,
143 /// The index for promoted globals within their function's `mir::Body`.
144 pub promoted: Option<mir::Promoted>,
147 impl GlobalId<'tcx> {
148 pub fn display(self, tcx: TyCtxt<'tcx>) -> String {
149 let instance_name = with_no_trimmed_paths(|| tcx.def_path_str(self.instance.def.def_id()));
150 if let Some(promoted) = self.promoted {
151 format!("{}::{:?}", instance_name, promoted)
158 /// Input argument for `tcx.lit_to_const`.
159 #[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, HashStable)]
160 pub struct LitToConstInput<'tcx> {
161 /// The absolute value of the resultant constant.
162 pub lit: &'tcx LitKind,
163 /// The type of the constant.
165 /// If the constant is negative.
169 /// Error type for `tcx.lit_to_const`.
170 #[derive(Copy, Clone, Debug, Eq, PartialEq, HashStable)]
171 pub enum LitToConstError {
172 /// The literal's inferred type did not match the expected `ty` in the input.
173 /// This is used for graceful error handling (`delay_span_bug`) in
174 /// type checking (`Const::from_anon_const`).
180 #[derive(Copy, Clone, Eq, Hash, Ord, PartialEq, PartialOrd)]
181 pub struct AllocId(pub u64);
183 // We want the `Debug` output to be readable as it is used by `derive(Debug)` for
184 // all the Miri types.
185 impl fmt::Debug for AllocId {
186 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
187 if f.alternate() { write!(f, "a{}", self.0) } else { write!(f, "alloc{}", self.0) }
191 impl fmt::Display for AllocId {
192 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
193 fmt::Debug::fmt(self, f)
197 #[derive(TyDecodable, TyEncodable)]
198 enum AllocDiscriminant {
204 pub fn specialized_encode_alloc_id<'tcx, E: TyEncoder<'tcx>>(
208 ) -> Result<(), E::Error> {
209 match tcx.global_alloc(alloc_id) {
210 GlobalAlloc::Memory(alloc) => {
211 trace!("encoding {:?} with {:#?}", alloc_id, alloc);
212 AllocDiscriminant::Alloc.encode(encoder)?;
213 alloc.encode(encoder)?;
215 GlobalAlloc::Function(fn_instance) => {
216 trace!("encoding {:?} with {:#?}", alloc_id, fn_instance);
217 AllocDiscriminant::Fn.encode(encoder)?;
218 fn_instance.encode(encoder)?;
220 GlobalAlloc::Static(did) => {
221 assert!(!tcx.is_thread_local_static(did));
222 // References to statics doesn't need to know about their allocations,
223 // just about its `DefId`.
224 AllocDiscriminant::Static.encode(encoder)?;
225 did.encode(encoder)?;
231 // Used to avoid infinite recursion when decoding cyclic allocations.
232 type DecodingSessionId = NonZeroU32;
237 InProgressNonAlloc(TinyList<DecodingSessionId>),
238 InProgress(TinyList<DecodingSessionId>, AllocId),
242 pub struct AllocDecodingState {
243 // For each `AllocId`, we keep track of which decoding state it's currently in.
244 decoding_state: Vec<Lock<State>>,
245 // The offsets of each allocation in the data stream.
246 data_offsets: Vec<u32>,
249 impl AllocDecodingState {
250 pub fn new_decoding_session(&self) -> AllocDecodingSession<'_> {
251 static DECODER_SESSION_ID: AtomicU32 = AtomicU32::new(0);
252 let counter = DECODER_SESSION_ID.fetch_add(1, Ordering::SeqCst);
254 // Make sure this is never zero.
255 let session_id = DecodingSessionId::new((counter & 0x7FFFFFFF) + 1).unwrap();
257 AllocDecodingSession { state: self, session_id }
260 pub fn new(data_offsets: Vec<u32>) -> Self {
261 let decoding_state = vec![Lock::new(State::Empty); data_offsets.len()];
263 Self { decoding_state, data_offsets }
267 #[derive(Copy, Clone)]
268 pub struct AllocDecodingSession<'s> {
269 state: &'s AllocDecodingState,
270 session_id: DecodingSessionId,
273 impl<'s> AllocDecodingSession<'s> {
274 /// Decodes an `AllocId` in a thread-safe way.
275 pub fn decode_alloc_id<D>(&self, decoder: &mut D) -> Result<AllocId, D::Error>
279 // Read the index of the allocation.
280 let idx = usize::try_from(decoder.read_u32()?).unwrap();
281 let pos = usize::try_from(self.state.data_offsets[idx]).unwrap();
283 // Decode the `AllocDiscriminant` now so that we know if we have to reserve an
285 let (alloc_kind, pos) = decoder.with_position(pos, |decoder| {
286 let alloc_kind = AllocDiscriminant::decode(decoder)?;
287 Ok((alloc_kind, decoder.position()))
290 // Check the decoding state to see if it's already decoded or if we should
293 let mut entry = self.state.decoding_state[idx].lock();
296 State::Done(alloc_id) => {
299 ref mut entry @ State::Empty => {
300 // We are allowed to decode.
302 AllocDiscriminant::Alloc => {
303 // If this is an allocation, we need to reserve an
304 // `AllocId` so we can decode cyclic graphs.
305 let alloc_id = decoder.tcx().reserve_alloc_id();
307 State::InProgress(TinyList::new_single(self.session_id), alloc_id);
310 AllocDiscriminant::Fn | AllocDiscriminant::Static => {
311 // Fns and statics cannot be cyclic, and their `AllocId`
312 // is determined later by interning.
314 State::InProgressNonAlloc(TinyList::new_single(self.session_id));
319 State::InProgressNonAlloc(ref mut sessions) => {
320 if sessions.contains(&self.session_id) {
321 bug!("this should be unreachable");
323 // Start decoding concurrently.
324 sessions.insert(self.session_id);
328 State::InProgress(ref mut sessions, alloc_id) => {
329 if sessions.contains(&self.session_id) {
333 // Start decoding concurrently.
334 sessions.insert(self.session_id);
341 // Now decode the actual data.
342 let alloc_id = decoder.with_position(pos, |decoder| {
344 AllocDiscriminant::Alloc => {
345 let alloc = <&'tcx Allocation as Decodable<_>>::decode(decoder)?;
346 // We already have a reserved `AllocId`.
347 let alloc_id = alloc_id.unwrap();
348 trace!("decoded alloc {:?}: {:#?}", alloc_id, alloc);
349 decoder.tcx().set_alloc_id_same_memory(alloc_id, alloc);
352 AllocDiscriminant::Fn => {
353 assert!(alloc_id.is_none());
354 trace!("creating fn alloc ID");
355 let instance = ty::Instance::decode(decoder)?;
356 trace!("decoded fn alloc instance: {:?}", instance);
357 let alloc_id = decoder.tcx().create_fn_alloc(instance);
360 AllocDiscriminant::Static => {
361 assert!(alloc_id.is_none());
362 trace!("creating extern static alloc ID");
363 let did = <DefId as Decodable<D>>::decode(decoder)?;
364 trace!("decoded static def-ID: {:?}", did);
365 let alloc_id = decoder.tcx().create_static_alloc(did);
371 self.state.decoding_state[idx].with_lock(|entry| {
372 *entry = State::Done(alloc_id);
379 /// An allocation in the global (tcx-managed) memory can be either a function pointer,
380 /// a static, or a "real" allocation with some data in it.
381 #[derive(Debug, Clone, Eq, PartialEq, Hash, TyDecodable, TyEncodable, HashStable)]
382 pub enum GlobalAlloc<'tcx> {
383 /// The alloc ID is used as a function pointer.
384 Function(Instance<'tcx>),
385 /// The alloc ID points to a "lazy" static variable that did not get computed (yet).
386 /// This is also used to break the cycle in recursive statics.
388 /// The alloc ID points to memory.
389 Memory(&'tcx Allocation),
392 impl GlobalAlloc<'tcx> {
393 /// Panics if the `GlobalAlloc` does not refer to an `GlobalAlloc::Memory`
396 pub fn unwrap_memory(&self) -> &'tcx Allocation {
398 GlobalAlloc::Memory(mem) => mem,
399 _ => bug!("expected memory, got {:?}", self),
403 /// Panics if the `GlobalAlloc` is not `GlobalAlloc::Function`
406 pub fn unwrap_fn(&self) -> Instance<'tcx> {
408 GlobalAlloc::Function(instance) => instance,
409 _ => bug!("expected function, got {:?}", self),
414 crate struct AllocMap<'tcx> {
415 /// Maps `AllocId`s to their corresponding allocations.
416 alloc_map: FxHashMap<AllocId, GlobalAlloc<'tcx>>,
418 /// Used to ensure that statics and functions only get one associated `AllocId`.
419 /// Should never contain a `GlobalAlloc::Memory`!
421 // FIXME: Should we just have two separate dedup maps for statics and functions each?
422 dedup: FxHashMap<GlobalAlloc<'tcx>, AllocId>,
424 /// The `AllocId` to assign to the next requested ID.
425 /// Always incremented; never gets smaller.
429 impl<'tcx> AllocMap<'tcx> {
430 crate fn new() -> Self {
431 AllocMap { alloc_map: Default::default(), dedup: Default::default(), next_id: AllocId(0) }
433 fn reserve(&mut self) -> AllocId {
434 let next = self.next_id;
435 self.next_id.0 = self.next_id.0.checked_add(1).expect(
436 "You overflowed a u64 by incrementing by 1... \
437 You've just earned yourself a free drink if we ever meet. \
438 Seriously, how did you do that?!",
444 impl<'tcx> TyCtxt<'tcx> {
445 /// Obtains a new allocation ID that can be referenced but does not
446 /// yet have an allocation backing it.
448 /// Make sure to call `set_alloc_id_memory` or `set_alloc_id_same_memory` before returning such
449 /// an `AllocId` from a query.
450 pub fn reserve_alloc_id(self) -> AllocId {
451 self.alloc_map.lock().reserve()
454 /// Reserves a new ID *if* this allocation has not been dedup-reserved before.
455 /// Should only be used for function pointers and statics, we don't want
456 /// to dedup IDs for "real" memory!
457 fn reserve_and_set_dedup(self, alloc: GlobalAlloc<'tcx>) -> AllocId {
458 let mut alloc_map = self.alloc_map.lock();
460 GlobalAlloc::Function(..) | GlobalAlloc::Static(..) => {}
461 GlobalAlloc::Memory(..) => bug!("Trying to dedup-reserve memory with real data!"),
463 if let Some(&alloc_id) = alloc_map.dedup.get(&alloc) {
466 let id = alloc_map.reserve();
467 debug!("creating alloc {:?} with id {}", alloc, id);
468 alloc_map.alloc_map.insert(id, alloc.clone());
469 alloc_map.dedup.insert(alloc, id);
473 /// Generates an `AllocId` for a static or return a cached one in case this function has been
474 /// called on the same static before.
475 pub fn create_static_alloc(self, static_id: DefId) -> AllocId {
476 self.reserve_and_set_dedup(GlobalAlloc::Static(static_id))
479 /// Generates an `AllocId` for a function. Depending on the function type,
480 /// this might get deduplicated or assigned a new ID each time.
481 pub fn create_fn_alloc(self, instance: Instance<'tcx>) -> AllocId {
482 // Functions cannot be identified by pointers, as asm-equal functions can get deduplicated
483 // by the linker (we set the "unnamed_addr" attribute for LLVM) and functions can be
484 // duplicated across crates.
485 // We thus generate a new `AllocId` for every mention of a function. This means that
486 // `main as fn() == main as fn()` is false, while `let x = main as fn(); x == x` is true.
487 // However, formatting code relies on function identity (see #58320), so we only do
488 // this for generic functions. Lifetime parameters are ignored.
489 let is_generic = instance.substs.into_iter().any(|kind| match kind.unpack() {
490 GenericArgKind::Lifetime(_) => false,
495 let mut alloc_map = self.alloc_map.lock();
496 let id = alloc_map.reserve();
497 alloc_map.alloc_map.insert(id, GlobalAlloc::Function(instance));
501 self.reserve_and_set_dedup(GlobalAlloc::Function(instance))
505 /// Interns the `Allocation` and return a new `AllocId`, even if there's already an identical
506 /// `Allocation` with a different `AllocId`.
507 /// Statics with identical content will still point to the same `Allocation`, i.e.,
508 /// their data will be deduplicated through `Allocation` interning -- but they
509 /// are different places in memory and as such need different IDs.
510 pub fn create_memory_alloc(self, mem: &'tcx Allocation) -> AllocId {
511 let id = self.reserve_alloc_id();
512 self.set_alloc_id_memory(id, mem);
516 /// Returns `None` in case the `AllocId` is dangling. An `InterpretCx` can still have a
517 /// local `Allocation` for that `AllocId`, but having such an `AllocId` in a constant is
518 /// illegal and will likely ICE.
519 /// This function exists to allow const eval to detect the difference between evaluation-
520 /// local dangling pointers and allocations in constants/statics.
522 pub fn get_global_alloc(self, id: AllocId) -> Option<GlobalAlloc<'tcx>> {
523 self.alloc_map.lock().alloc_map.get(&id).cloned()
528 /// Panics in case the `AllocId` is dangling. Since that is impossible for `AllocId`s in
529 /// constants (as all constants must pass interning and validation that check for dangling
530 /// ids), this function is frequently used throughout rustc, but should not be used within
532 pub fn global_alloc(self, id: AllocId) -> GlobalAlloc<'tcx> {
533 match self.get_global_alloc(id) {
534 Some(alloc) => alloc,
535 None => bug!("could not find allocation for {}", id),
539 /// Freezes an `AllocId` created with `reserve` by pointing it at an `Allocation`. Trying to
540 /// call this function twice, even with the same `Allocation` will ICE the compiler.
541 pub fn set_alloc_id_memory(self, id: AllocId, mem: &'tcx Allocation) {
542 if let Some(old) = self.alloc_map.lock().alloc_map.insert(id, GlobalAlloc::Memory(mem)) {
543 bug!("tried to set allocation ID {}, but it was already existing as {:#?}", id, old);
547 /// Freezes an `AllocId` created with `reserve` by pointing it at an `Allocation`. May be called
548 /// twice for the same `(AllocId, Allocation)` pair.
549 fn set_alloc_id_same_memory(self, id: AllocId, mem: &'tcx Allocation) {
550 self.alloc_map.lock().alloc_map.insert_same(id, GlobalAlloc::Memory(mem));
554 ////////////////////////////////////////////////////////////////////////////////
555 // Methods to access integers in the target endianness
556 ////////////////////////////////////////////////////////////////////////////////
559 pub fn write_target_uint(
561 mut target: &mut [u8],
563 ) -> Result<(), io::Error> {
564 // This u128 holds an "any-size uint" (since smaller uints can fits in it)
565 // So we do not write all bytes of the u128, just the "payload".
567 Endian::Little => target.write(&data.to_le_bytes())?,
568 Endian::Big => target.write(&data.to_be_bytes()[16 - target.len()..])?,
570 debug_assert!(target.len() == 0); // We should have filled the target buffer.
575 pub fn read_target_uint(endianness: Endian, mut source: &[u8]) -> Result<u128, io::Error> {
576 // This u128 holds an "any-size uint" (since smaller uints can fits in it)
577 let mut buf = [0u8; std::mem::size_of::<u128>()];
578 // So we do not read exactly 16 bytes into the u128, just the "payload".
579 let uint = match endianness {
581 source.read(&mut buf)?;
582 Ok(u128::from_le_bytes(buf))
585 source.read(&mut buf[16 - source.len()..])?;
586 Ok(u128::from_be_bytes(buf))
589 debug_assert!(source.len() == 0); // We should have consumed the source buffer.
593 ////////////////////////////////////////////////////////////////////////////////
594 // Methods to facilitate working with signed integers stored in a u128
595 ////////////////////////////////////////////////////////////////////////////////
597 /// Truncates `value` to `size` bits and then sign-extend it to 128 bits
598 /// (i.e., if it is negative, fill with 1's on the left).
600 pub fn sign_extend(value: u128, size: Size) -> u128 {
601 let size = size.bits();
603 // Truncated until nothing is left.
607 let shift = 128 - size;
608 // Shift the unsigned value to the left, then shift back to the right as signed
609 // (essentially fills with FF on the left).
610 (((value << shift) as i128) >> shift) as u128
613 /// Truncates `value` to `size` bits.
615 pub fn truncate(value: u128, size: Size) -> u128 {
616 let size = size.bits();
618 // Truncated until nothing is left.
621 let shift = 128 - size;
622 // Truncate (shift left to drop out leftover values, shift right to fill with zeroes).
623 (value << shift) >> shift
626 /// Computes the unsigned absolute value without wrapping or panicking.
628 pub fn uabs(value: i64) -> u64 {
629 // The only tricky part here is if value == i64::MIN. In that case,
630 // wrapping_abs() returns i64::MIN == -2^63. Casting this value to a u64
631 // gives 2^63, the correct value.
632 value.wrapping_abs() as u64