compiler/rustc_middle/src/mir/interpret/mod.rs - third_party/rust - Git at Google

 //! An interpreter for MIR used in CTFE and by miri.

 #[macro_export]
 macro_rules! err_unsup {
     ($($tt:tt)*) => {
         $crate::mir::interpret::InterpError::Unsupported(
             $crate::mir::interpret::UnsupportedOpInfo::$($tt)*
         )
     };
 }

 #[macro_export]
 macro_rules! err_unsup_format {
     ($($tt:tt)*) => { err_unsup!(Unsupported(format!($($tt)*))) };
 }

 #[macro_export]
 macro_rules! err_inval {
     ($($tt:tt)*) => {
         $crate::mir::interpret::InterpError::InvalidProgram(
             $crate::mir::interpret::InvalidProgramInfo::$($tt)*
         )
     };
 }

 #[macro_export]
 macro_rules! err_ub {
     ($($tt:tt)*) => {
         $crate::mir::interpret::InterpError::UndefinedBehavior(
             $crate::mir::interpret::UndefinedBehaviorInfo::$($tt)*
         )
     };
 }

 #[macro_export]
 macro_rules! err_ub_format {
     ($($tt:tt)*) => { err_ub!(Ub(format!($($tt)*))) };
 }

 #[macro_export]
 macro_rules! err_exhaust {
     ($($tt:tt)*) => {
         $crate::mir::interpret::InterpError::ResourceExhaustion(
             $crate::mir::interpret::ResourceExhaustionInfo::$($tt)*
         )
     };
 }

 #[macro_export]
 macro_rules! err_machine_stop {
     ($($tt:tt)*) => {
         $crate::mir::interpret::InterpError::MachineStop(Box::new($($tt)*))
     };
 }

 // In the `throw_*` macros, avoid `return` to make them work with `try {}`.
 #[macro_export]
 macro_rules! throw_unsup {
     ($($tt:tt)*) => { Err::<!, _>(err_unsup!($($tt)*))? };
 }

 #[macro_export]
 macro_rules! throw_unsup_format {
     ($($tt:tt)*) => { throw_unsup!(Unsupported(format!($($tt)*))) };
 }

 #[macro_export]
 macro_rules! throw_inval {
     ($($tt:tt)*) => { Err::<!, _>(err_inval!($($tt)*))? };
 }

 #[macro_export]
 macro_rules! throw_ub {
     ($($tt:tt)*) => { Err::<!, _>(err_ub!($($tt)*))? };
 }

 #[macro_export]
 macro_rules! throw_ub_format {
     ($($tt:tt)*) => { throw_ub!(Ub(format!($($tt)*))) };
 }

 #[macro_export]
 macro_rules! throw_exhaust {
     ($($tt:tt)*) => { Err::<!, _>(err_exhaust!($($tt)*))? };
 }

 #[macro_export]
 macro_rules! throw_machine_stop {
     ($($tt:tt)*) => { Err::<!, _>(err_machine_stop!($($tt)*))? };
 }

 mod allocation;
 mod error;
 mod pointer;
 mod queries;
 mod value;

 use std::convert::TryFrom;
 use std::fmt;
 use std::io;
 use std::io::{Read, Write};
 use std::num::NonZeroU32;
 use std::sync::atomic::{AtomicU32, Ordering};

 use rustc_ast::LitKind;
 use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::sync::{HashMapExt, Lock};
 use rustc_data_structures::tiny_list::TinyList;
 use rustc_hir::def_id::DefId;
 use rustc_macros::HashStable;
 use rustc_middle::ty::print::with_no_trimmed_paths;
 use rustc_serialize::{Decodable, Encodable};
 use rustc_target::abi::{Endian, Size};

 use crate::mir;
 use crate::ty::codec::{TyDecoder, TyEncoder};
 use crate::ty::subst::GenericArgKind;
 use crate::ty::{self, Instance, Ty, TyCtxt};

 pub use self::error::{
     struct_error, CheckInAllocMsg, ErrorHandled, EvalToAllocationRawResult, EvalToConstValueResult,
     InterpError, InterpErrorInfo, InterpResult, InvalidProgramInfo, MachineStopType,
     ResourceExhaustionInfo, UndefinedBehaviorInfo, UninitBytesAccess, UnsupportedOpInfo,
 };

 pub use self::value::{get_slice_bytes, ConstAlloc, ConstValue, Scalar, ScalarMaybeUninit};

 pub use self::allocation::{Allocation, AllocationExtra, InitMask, Relocations};

 pub use self::pointer::{Pointer, PointerArithmetic};

 /// Uniquely identifies one of the following:
 /// - A constant
 /// - A static
 /// - A const fn where all arguments (if any) are zero-sized types
 #[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, TyEncodable, TyDecodable)]
 #[derive(HashStable, Lift)]
 pub struct GlobalId<'tcx> {
     /// For a constant or static, the `Instance` of the item itself.
     /// For a promoted global, the `Instance` of the function they belong to.
     pub instance: ty::Instance<'tcx>,

     /// The index for promoted globals within their function's `mir::Body`.
     pub promoted: Option<mir::Promoted>,
 }

 impl GlobalId<'tcx> {
     pub fn display(self, tcx: TyCtxt<'tcx>) -> String {
         let instance_name = with_no_trimmed_paths(|| tcx.def_path_str(self.instance.def.def_id()));
         if let Some(promoted) = self.promoted {
             format!("{}::{:?}", instance_name, promoted)
         } else {
             instance_name
         }
     }
 }

 /// Input argument for `tcx.lit_to_const`.
 #[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, HashStable)]
 pub struct LitToConstInput<'tcx> {
     /// The absolute value of the resultant constant.
     pub lit: &'tcx LitKind,
     /// The type of the constant.
     pub ty: Ty<'tcx>,
     /// If the constant is negative.
     pub neg: bool,
 }

 /// Error type for `tcx.lit_to_const`.
 #[derive(Copy, Clone, Debug, Eq, PartialEq, HashStable)]
 pub enum LitToConstError {
     /// The literal's inferred type did not match the expected `ty` in the input.
     /// This is used for graceful error handling (`delay_span_bug`) in
     /// type checking (`Const::from_anon_const`).
     TypeError,
     UnparseableFloat,
     Reported,
 }

 #[derive(Copy, Clone, Eq, Hash, Ord, PartialEq, PartialOrd)]
 pub struct AllocId(pub u64);

 // We want the `Debug` output to be readable as it is used by `derive(Debug)` for
 // all the Miri types.
 impl fmt::Debug for AllocId {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         if f.alternate() { write!(f, "a{}", self.0) } else { write!(f, "alloc{}", self.0) }
     }
 }

 impl fmt::Display for AllocId {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         fmt::Debug::fmt(self, f)
     }
 }

 #[derive(TyDecodable, TyEncodable)]
 enum AllocDiscriminant {
     Alloc,
     Fn,
     Static,
 }

 pub fn specialized_encode_alloc_id<'tcx, E: TyEncoder<'tcx>>(
     encoder: &mut E,
     tcx: TyCtxt<'tcx>,
     alloc_id: AllocId,
 ) -> Result<(), E::Error> {
     match tcx.global_alloc(alloc_id) {
         GlobalAlloc::Memory(alloc) => {
             trace!("encoding {:?} with {:#?}", alloc_id, alloc);
             AllocDiscriminant::Alloc.encode(encoder)?;
             alloc.encode(encoder)?;
         }
         GlobalAlloc::Function(fn_instance) => {
             trace!("encoding {:?} with {:#?}", alloc_id, fn_instance);
             AllocDiscriminant::Fn.encode(encoder)?;
             fn_instance.encode(encoder)?;
         }
         GlobalAlloc::Static(did) => {
             assert!(!tcx.is_thread_local_static(did));
             // References to statics doesn't need to know about their allocations,
             // just about its `DefId`.
             AllocDiscriminant::Static.encode(encoder)?;
             did.encode(encoder)?;
         }
     }
     Ok(())
 }

 // Used to avoid infinite recursion when decoding cyclic allocations.
 type DecodingSessionId = NonZeroU32;

 #[derive(Clone)]
 enum State {
     Empty,
     InProgressNonAlloc(TinyList<DecodingSessionId>),
     InProgress(TinyList<DecodingSessionId>, AllocId),
     Done(AllocId),
 }

 pub struct AllocDecodingState {
     // For each `AllocId`, we keep track of which decoding state it's currently in.
     decoding_state: Vec<Lock<State>>,
     // The offsets of each allocation in the data stream.
     data_offsets: Vec<u32>,
 }

 impl AllocDecodingState {
     pub fn new_decoding_session(&self) -> AllocDecodingSession<'_> {
         static DECODER_SESSION_ID: AtomicU32 = AtomicU32::new(0);
         let counter = DECODER_SESSION_ID.fetch_add(1, Ordering::SeqCst);

         // Make sure this is never zero.
         let session_id = DecodingSessionId::new((counter & 0x7FFFFFFF) + 1).unwrap();

         AllocDecodingSession { state: self, session_id }
     }

     pub fn new(data_offsets: Vec<u32>) -> Self {
         let decoding_state = vec![Lock::new(State::Empty); data_offsets.len()];

         Self { decoding_state, data_offsets }
     }
 }

 #[derive(Copy, Clone)]
 pub struct AllocDecodingSession<'s> {
     state: &'s AllocDecodingState,
     session_id: DecodingSessionId,
 }

 impl<'s> AllocDecodingSession<'s> {
     /// Decodes an `AllocId` in a thread-safe way.
     pub fn decode_alloc_id<D>(&self, decoder: &mut D) -> Result<AllocId, D::Error>
     where
         D: TyDecoder<'tcx>,
     {
         // Read the index of the allocation.
         let idx = usize::try_from(decoder.read_u32()?).unwrap();
         let pos = usize::try_from(self.state.data_offsets[idx]).unwrap();

         // Decode the `AllocDiscriminant` now so that we know if we have to reserve an
         // `AllocId`.
         let (alloc_kind, pos) = decoder.with_position(pos, |decoder| {
             let alloc_kind = AllocDiscriminant::decode(decoder)?;
             Ok((alloc_kind, decoder.position()))
         })?;

         // Check the decoding state to see if it's already decoded or if we should
         // decode it here.
         let alloc_id = {
             let mut entry = self.state.decoding_state[idx].lock();

             match *entry {
                 State::Done(alloc_id) => {
                     return Ok(alloc_id);
                 }
                 ref mut entry @ State::Empty => {
                     // We are allowed to decode.
                     match alloc_kind {
                         AllocDiscriminant::Alloc => {
                             // If this is an allocation, we need to reserve an
                             // `AllocId` so we can decode cyclic graphs.
                             let alloc_id = decoder.tcx().reserve_alloc_id();
                             *entry =
                                 State::InProgress(TinyList::new_single(self.session_id), alloc_id);
                             Some(alloc_id)
                         }
                         AllocDiscriminant::Fn | AllocDiscriminant::Static => {
                             // Fns and statics cannot be cyclic, and their `AllocId`
                             // is determined later by interning.
                             *entry =
                                 State::InProgressNonAlloc(TinyList::new_single(self.session_id));
                             None
                         }
                     }
                 }
                 State::InProgressNonAlloc(ref mut sessions) => {
                     if sessions.contains(&self.session_id) {
                         bug!("this should be unreachable");
                     } else {
                         // Start decoding concurrently.
                         sessions.insert(self.session_id);
                         None
                     }
                 }
                 State::InProgress(ref mut sessions, alloc_id) => {
                     if sessions.contains(&self.session_id) {
                         // Don't recurse.
                         return Ok(alloc_id);
                     } else {
                         // Start decoding concurrently.
                         sessions.insert(self.session_id);
                         Some(alloc_id)
                     }
                 }
             }
         };

         // Now decode the actual data.
         let alloc_id = decoder.with_position(pos, |decoder| {
             match alloc_kind {
                 AllocDiscriminant::Alloc => {
                     let alloc = <&'tcx Allocation as Decodable<_>>::decode(decoder)?;
                     // We already have a reserved `AllocId`.
                     let alloc_id = alloc_id.unwrap();
                     trace!("decoded alloc {:?}: {:#?}", alloc_id, alloc);
                     decoder.tcx().set_alloc_id_same_memory(alloc_id, alloc);
                     Ok(alloc_id)
                 }
                 AllocDiscriminant::Fn => {
                     assert!(alloc_id.is_none());
                     trace!("creating fn alloc ID");
                     let instance = ty::Instance::decode(decoder)?;
                     trace!("decoded fn alloc instance: {:?}", instance);
                     let alloc_id = decoder.tcx().create_fn_alloc(instance);
                     Ok(alloc_id)
                 }
                 AllocDiscriminant::Static => {
                     assert!(alloc_id.is_none());
                     trace!("creating extern static alloc ID");
                     let did = <DefId as Decodable<D>>::decode(decoder)?;
                     trace!("decoded static def-ID: {:?}", did);
                     let alloc_id = decoder.tcx().create_static_alloc(did);
                     Ok(alloc_id)
                 }
             }
         })?;

         self.state.decoding_state[idx].with_lock(|entry| {
             *entry = State::Done(alloc_id);
         });

         Ok(alloc_id)
     }
 }

 /// An allocation in the global (tcx-managed) memory can be either a function pointer,
 /// a static, or a "real" allocation with some data in it.
 #[derive(Debug, Clone, Eq, PartialEq, Hash, TyDecodable, TyEncodable, HashStable)]
 pub enum GlobalAlloc<'tcx> {
     /// The alloc ID is used as a function pointer.
     Function(Instance<'tcx>),
     /// The alloc ID points to a "lazy" static variable that did not get computed (yet).
     /// This is also used to break the cycle in recursive statics.
     Static(DefId),
     /// The alloc ID points to memory.
     Memory(&'tcx Allocation),
 }

 impl GlobalAlloc<'tcx> {
     /// Panics if the `GlobalAlloc` does not refer to an `GlobalAlloc::Memory`
     #[track_caller]
     #[inline]
     pub fn unwrap_memory(&self) -> &'tcx Allocation {
         match *self {
             GlobalAlloc::Memory(mem) => mem,
             _ => bug!("expected memory, got {:?}", self),
         }
     }

     /// Panics if the `GlobalAlloc` is not `GlobalAlloc::Function`
     #[track_caller]
     #[inline]
     pub fn unwrap_fn(&self) -> Instance<'tcx> {
         match *self {
             GlobalAlloc::Function(instance) => instance,
             _ => bug!("expected function, got {:?}", self),
         }
     }
 }

 crate struct AllocMap<'tcx> {
     /// Maps `AllocId`s to their corresponding allocations.
     alloc_map: FxHashMap<AllocId, GlobalAlloc<'tcx>>,

     /// Used to ensure that statics and functions only get one associated `AllocId`.
     /// Should never contain a `GlobalAlloc::Memory`!
     //
     // FIXME: Should we just have two separate dedup maps for statics and functions each?
     dedup: FxHashMap<GlobalAlloc<'tcx>, AllocId>,

     /// The `AllocId` to assign to the next requested ID.
     /// Always incremented; never gets smaller.
     next_id: AllocId,
 }

 impl<'tcx> AllocMap<'tcx> {
     crate fn new() -> Self {
         AllocMap { alloc_map: Default::default(), dedup: Default::default(), next_id: AllocId(0) }
     }
     fn reserve(&mut self) -> AllocId {
         let next = self.next_id;
         self.next_id.0 = self.next_id.0.checked_add(1).expect(
             "You overflowed a u64 by incrementing by 1... \
              You've just earned yourself a free drink if we ever meet. \
              Seriously, how did you do that?!",
         );
         next
     }
 }

 impl<'tcx> TyCtxt<'tcx> {
     /// Obtains a new allocation ID that can be referenced but does not
     /// yet have an allocation backing it.
     ///
     /// Make sure to call `set_alloc_id_memory` or `set_alloc_id_same_memory` before returning such
     /// an `AllocId` from a query.
     pub fn reserve_alloc_id(self) -> AllocId {
         self.alloc_map.lock().reserve()
     }

     /// Reserves a new ID *if* this allocation has not been dedup-reserved before.
     /// Should only be used for function pointers and statics, we don't want
     /// to dedup IDs for "real" memory!
     fn reserve_and_set_dedup(self, alloc: GlobalAlloc<'tcx>) -> AllocId {
         let mut alloc_map = self.alloc_map.lock();
         match alloc {
             GlobalAlloc::Function(..) | GlobalAlloc::Static(..) => {}
             GlobalAlloc::Memory(..) => bug!("Trying to dedup-reserve memory with real data!"),
         }
         if let Some(&alloc_id) = alloc_map.dedup.get(&alloc) {
             return alloc_id;
         }
         let id = alloc_map.reserve();
         debug!("creating alloc {:?} with id {}", alloc, id);
         alloc_map.alloc_map.insert(id, alloc.clone());
         alloc_map.dedup.insert(alloc, id);
         id
     }

     /// Generates an `AllocId` for a static or return a cached one in case this function has been
     /// called on the same static before.
     pub fn create_static_alloc(self, static_id: DefId) -> AllocId {
         self.reserve_and_set_dedup(GlobalAlloc::Static(static_id))
     }

     /// Generates an `AllocId` for a function.  Depending on the function type,
     /// this might get deduplicated or assigned a new ID each time.
     pub fn create_fn_alloc(self, instance: Instance<'tcx>) -> AllocId {
         // Functions cannot be identified by pointers, as asm-equal functions can get deduplicated
         // by the linker (we set the "unnamed_addr" attribute for LLVM) and functions can be
         // duplicated across crates.
         // We thus generate a new `AllocId` for every mention of a function. This means that
         // `main as fn() == main as fn()` is false, while `let x = main as fn(); x == x` is true.
         // However, formatting code relies on function identity (see #58320), so we only do
         // this for generic functions.  Lifetime parameters are ignored.
         let is_generic = instance.substs.into_iter().any(|kind| match kind.unpack() {
             GenericArgKind::Lifetime(_) => false,
             _ => true,
         });
         if is_generic {
             // Get a fresh ID.
             let mut alloc_map = self.alloc_map.lock();
             let id = alloc_map.reserve();
             alloc_map.alloc_map.insert(id, GlobalAlloc::Function(instance));
             id
         } else {
             // Deduplicate.
             self.reserve_and_set_dedup(GlobalAlloc::Function(instance))
         }
     }

     /// Interns the `Allocation` and return a new `AllocId`, even if there's already an identical
     /// `Allocation` with a different `AllocId`.
     /// Statics with identical content will still point to the same `Allocation`, i.e.,
     /// their data will be deduplicated through `Allocation` interning -- but they
     /// are different places in memory and as such need different IDs.
     pub fn create_memory_alloc(self, mem: &'tcx Allocation) -> AllocId {
         let id = self.reserve_alloc_id();
         self.set_alloc_id_memory(id, mem);
         id
     }

     /// Returns `None` in case the `AllocId` is dangling. An `InterpretCx` can still have a
     /// local `Allocation` for that `AllocId`, but having such an `AllocId` in a constant is
     /// illegal and will likely ICE.
     /// This function exists to allow const eval to detect the difference between evaluation-
     /// local dangling pointers and allocations in constants/statics.
     #[inline]
     pub fn get_global_alloc(self, id: AllocId) -> Option<GlobalAlloc<'tcx>> {
         self.alloc_map.lock().alloc_map.get(&id).cloned()
     }

     #[inline]
     #[track_caller]
     /// Panics in case the `AllocId` is dangling. Since that is impossible for `AllocId`s in
     /// constants (as all constants must pass interning and validation that check for dangling
     /// ids), this function is frequently used throughout rustc, but should not be used within
     /// the miri engine.
     pub fn global_alloc(self, id: AllocId) -> GlobalAlloc<'tcx> {
         match self.get_global_alloc(id) {
             Some(alloc) => alloc,
             None => bug!("could not find allocation for {}", id),
         }
     }

     /// Freezes an `AllocId` created with `reserve` by pointing it at an `Allocation`. Trying to
     /// call this function twice, even with the same `Allocation` will ICE the compiler.
     pub fn set_alloc_id_memory(self, id: AllocId, mem: &'tcx Allocation) {
         if let Some(old) = self.alloc_map.lock().alloc_map.insert(id, GlobalAlloc::Memory(mem)) {
             bug!("tried to set allocation ID {}, but it was already existing as {:#?}", id, old);
         }
     }

     /// Freezes an `AllocId` created with `reserve` by pointing it at an `Allocation`. May be called
     /// twice for the same `(AllocId, Allocation)` pair.
     fn set_alloc_id_same_memory(self, id: AllocId, mem: &'tcx Allocation) {
         self.alloc_map.lock().alloc_map.insert_same(id, GlobalAlloc::Memory(mem));
     }
 }

 ////////////////////////////////////////////////////////////////////////////////
 // Methods to access integers in the target endianness
 ////////////////////////////////////////////////////////////////////////////////

 #[inline]
 pub fn write_target_uint(
     endianness: Endian,
     mut target: &mut [u8],
     data: u128,
 ) -> Result<(), io::Error> {
     // This u128 holds an "any-size uint" (since smaller uints can fits in it)
     // So we do not write all bytes of the u128, just the "payload".
     match endianness {
         Endian::Little => target.write(&data.to_le_bytes())?,
         Endian::Big => target.write(&data.to_be_bytes()[16 - target.len()..])?,
     };
     debug_assert!(target.len() == 0); // We should have filled the target buffer.
     Ok(())
 }

 #[inline]
 pub fn read_target_uint(endianness: Endian, mut source: &[u8]) -> Result<u128, io::Error> {
     // This u128 holds an "any-size uint" (since smaller uints can fits in it)
     let mut buf = [0u8; std::mem::size_of::<u128>()];
     // So we do not read exactly 16 bytes into the u128, just the "payload".
     let uint = match endianness {
         Endian::Little => {
             source.read(&mut buf)?;
             Ok(u128::from_le_bytes(buf))
         }
         Endian::Big => {
             source.read(&mut buf[16 - source.len()..])?;
             Ok(u128::from_be_bytes(buf))
         }
     };
     debug_assert!(source.len() == 0); // We should have consumed the source buffer.
     uint
 }

 ////////////////////////////////////////////////////////////////////////////////
 // Methods to facilitate working with signed integers stored in a u128
 ////////////////////////////////////////////////////////////////////////////////

 /// Truncates `value` to `size` bits and then sign-extend it to 128 bits
 /// (i.e., if it is negative, fill with 1's on the left).
 #[inline]
 pub fn sign_extend(value: u128, size: Size) -> u128 {
     let size = size.bits();
     if size == 0 {
         // Truncated until nothing is left.
         return 0;
     }
     // Sign-extend it.
     let shift = 128 - size;
     // Shift the unsigned value to the left, then shift back to the right as signed
     // (essentially fills with FF on the left).
     (((value << shift) as i128) >> shift) as u128
 }

 /// Truncates `value` to `size` bits.
 #[inline]
 pub fn truncate(value: u128, size: Size) -> u128 {
     let size = size.bits();
     if size == 0 {
         // Truncated until nothing is left.
         return 0;
     }
     let shift = 128 - size;
     // Truncate (shift left to drop out leftover values, shift right to fill with zeroes).
     (value << shift) >> shift
 }

 /// Computes the unsigned absolute value without wrapping or panicking.
 #[inline]
 pub fn uabs(value: i64) -> u64 {
     // The only tricky part here is if value == i64::MIN. In that case,
     // wrapping_abs() returns i64::MIN == -2^63. Casting this value to a u64
     // gives 2^63, the correct value.
     value.wrapping_abs() as u64
 }
	//! An interpreter for MIR used in CTFE and by miri.

	#[macro_export]
	macro_rules! err_unsup {
	($($tt:tt)*) => {
	$crate::mir::interpret::InterpError::Unsupported(
	$crate::mir::interpret::UnsupportedOpInfo::$($tt)*
	)
	};
	}

	#[macro_export]
	macro_rules! err_unsup_format {
	($($tt:tt)) => { err_unsup!(Unsupported(format!($($tt)))) };
	}

	#[macro_export]
	macro_rules! err_inval {
	($($tt:tt)*) => {
	$crate::mir::interpret::InterpError::InvalidProgram(
	$crate::mir::interpret::InvalidProgramInfo::$($tt)*
	)
	};
	}

	#[macro_export]
	macro_rules! err_ub {
	($($tt:tt)*) => {
	$crate::mir::interpret::InterpError::UndefinedBehavior(
	$crate::mir::interpret::UndefinedBehaviorInfo::$($tt)*
	)
	};
	}

	#[macro_export]
	macro_rules! err_ub_format {
	($($tt:tt)) => { err_ub!(Ub(format!($($tt)))) };
	}

	#[macro_export]
	macro_rules! err_exhaust {
	($($tt:tt)*) => {
	$crate::mir::interpret::InterpError::ResourceExhaustion(
	$crate::mir::interpret::ResourceExhaustionInfo::$($tt)*
	)
	};
	}

	#[macro_export]
	macro_rules! err_machine_stop {
	($($tt:tt)*) => {
	$crate::mir::interpret::InterpError::MachineStop(Box::new($($tt)*))
	};
	}

	// In the `throw_*` macros, avoid `return` to make them work with `try {}`.
	#[macro_export]
	macro_rules! throw_unsup {
	($($tt:tt)) => { Err::<!, _>(err_unsup!($($tt)))? };
	}

	#[macro_export]
	macro_rules! throw_unsup_format {
	($($tt:tt)) => { throw_unsup!(Unsupported(format!($($tt)))) };
	}

	#[macro_export]
	macro_rules! throw_inval {
	($($tt:tt)) => { Err::<!, _>(err_inval!($($tt)))? };
	}

	#[macro_export]
	macro_rules! throw_ub {
	($($tt:tt)) => { Err::<!, _>(err_ub!($($tt)))? };
	}

	#[macro_export]
	macro_rules! throw_ub_format {
	($($tt:tt)) => { throw_ub!(Ub(format!($($tt)))) };
	}

	#[macro_export]
	macro_rules! throw_exhaust {
	($($tt:tt)) => { Err::<!, _>(err_exhaust!($($tt)))? };
	}

	#[macro_export]
	macro_rules! throw_machine_stop {
	($($tt:tt)) => { Err::<!, _>(err_machine_stop!($($tt)))? };
	}

	mod allocation;
	mod error;
	mod pointer;
	mod queries;
	mod value;

	use std::convert::TryFrom;
	use std::fmt;
	use std::io;
	use std::io::{Read, Write};
	use std::num::NonZeroU32;
	use std::sync::atomic::{AtomicU32, Ordering};

	use rustc_ast::LitKind;
	use rustc_data_structures::fx::FxHashMap;
	use rustc_data_structures::sync::{HashMapExt, Lock};
	use rustc_data_structures::tiny_list::TinyList;
	use rustc_hir::def_id::DefId;
	use rustc_macros::HashStable;
	use rustc_middle::ty::print::with_no_trimmed_paths;
	use rustc_serialize::{Decodable, Encodable};
	use rustc_target::abi::{Endian, Size};

	use crate::mir;
	use crate::ty::codec::{TyDecoder, TyEncoder};
	use crate::ty::subst::GenericArgKind;
	use crate::ty::{self, Instance, Ty, TyCtxt};

	pub use self::error::{
	struct_error, CheckInAllocMsg, ErrorHandled, EvalToAllocationRawResult, EvalToConstValueResult,
	InterpError, InterpErrorInfo, InterpResult, InvalidProgramInfo, MachineStopType,
	ResourceExhaustionInfo, UndefinedBehaviorInfo, UninitBytesAccess, UnsupportedOpInfo,
	};

	pub use self::value::{get_slice_bytes, ConstAlloc, ConstValue, Scalar, ScalarMaybeUninit};

	pub use self::allocation::{Allocation, AllocationExtra, InitMask, Relocations};

	pub use self::pointer::{Pointer, PointerArithmetic};

	/// Uniquely identifies one of the following:
	/// - A constant
	/// - A static
	/// - A const fn where all arguments (if any) are zero-sized types
	#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, TyEncodable, TyDecodable)]
	#[derive(HashStable, Lift)]
	pub struct GlobalId<'tcx> {
	/// For a constant or static, the `Instance` of the item itself.
	/// For a promoted global, the `Instance` of the function they belong to.
	pub instance: ty::Instance<'tcx>,

	/// The index for promoted globals within their function's `mir::Body`.
	pub promoted: Option<mir::Promoted>,
	}

	impl GlobalId<'tcx> {
	pub fn display(self, tcx: TyCtxt<'tcx>) -> String {
	let instance_name = with_no_trimmed_paths(\|\| tcx.def_path_str(self.instance.def.def_id()));
	if let Some(promoted) = self.promoted {
	format!("{}::{:?}", instance_name, promoted)
	} else {
	instance_name
	}
	}
	}

	/// Input argument for `tcx.lit_to_const`.
	#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, HashStable)]
	pub struct LitToConstInput<'tcx> {
	/// The absolute value of the resultant constant.
	pub lit: &'tcx LitKind,
	/// The type of the constant.
	pub ty: Ty<'tcx>,
	/// If the constant is negative.
	pub neg: bool,
	}

	/// Error type for `tcx.lit_to_const`.
	#[derive(Copy, Clone, Debug, Eq, PartialEq, HashStable)]
	pub enum LitToConstError {
	/// The literal's inferred type did not match the expected `ty` in the input.
	/// This is used for graceful error handling (`delay_span_bug`) in
	/// type checking (`Const::from_anon_const`).
	TypeError,
	UnparseableFloat,
	Reported,
	}

	#[derive(Copy, Clone, Eq, Hash, Ord, PartialEq, PartialOrd)]
	pub struct AllocId(pub u64);

	// We want the `Debug` output to be readable as it is used by `derive(Debug)` for
	// all the Miri types.
	impl fmt::Debug for AllocId {
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
	if f.alternate() { write!(f, "a{}", self.0) } else { write!(f, "alloc{}", self.0) }
	}
	}

	impl fmt::Display for AllocId {
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
	fmt::Debug::fmt(self, f)
	}
	}

	#[derive(TyDecodable, TyEncodable)]
	enum AllocDiscriminant {
	Alloc,
	Fn,
	Static,
	}

	pub fn specialized_encode_alloc_id<'tcx, E: TyEncoder<'tcx>>(
	encoder: &mut E,
	tcx: TyCtxt<'tcx>,
	alloc_id: AllocId,
	) -> Result<(), E::Error> {
	match tcx.global_alloc(alloc_id) {
	GlobalAlloc::Memory(alloc) => {
	trace!("encoding {:?} with {:#?}", alloc_id, alloc);
	AllocDiscriminant::Alloc.encode(encoder)?;
	alloc.encode(encoder)?;
	}
	GlobalAlloc::Function(fn_instance) => {
	trace!("encoding {:?} with {:#?}", alloc_id, fn_instance);
	AllocDiscriminant::Fn.encode(encoder)?;
	fn_instance.encode(encoder)?;
	}
	GlobalAlloc::Static(did) => {
	assert!(!tcx.is_thread_local_static(did));
	// References to statics doesn't need to know about their allocations,
	// just about its `DefId`.
	AllocDiscriminant::Static.encode(encoder)?;
	did.encode(encoder)?;
	}
	}
	Ok(())
	}

	// Used to avoid infinite recursion when decoding cyclic allocations.
	type DecodingSessionId = NonZeroU32;

	#[derive(Clone)]
	enum State {
	Empty,
	InProgressNonAlloc(TinyList<DecodingSessionId>),
	InProgress(TinyList<DecodingSessionId>, AllocId),
	Done(AllocId),
	}

	pub struct AllocDecodingState {
	// For each `AllocId`, we keep track of which decoding state it's currently in.
	decoding_state: Vec<Lock<State>>,
	// The offsets of each allocation in the data stream.
	data_offsets: Vec<u32>,
	}

	impl AllocDecodingState {
	pub fn new_decoding_session(&self) -> AllocDecodingSession<'_> {
	static DECODER_SESSION_ID: AtomicU32 = AtomicU32::new(0);
	let counter = DECODER_SESSION_ID.fetch_add(1, Ordering::SeqCst);

	// Make sure this is never zero.
	let session_id = DecodingSessionId::new((counter & 0x7FFFFFFF) + 1).unwrap();

	AllocDecodingSession { state: self, session_id }
	}

	pub fn new(data_offsets: Vec<u32>) -> Self {
	let decoding_state = vec![Lock::new(State::Empty); data_offsets.len()];

	Self { decoding_state, data_offsets }
	}
	}

	#[derive(Copy, Clone)]
	pub struct AllocDecodingSession<'s> {
	state: &'s AllocDecodingState,
	session_id: DecodingSessionId,
	}

	impl<'s> AllocDecodingSession<'s> {
	/// Decodes an `AllocId` in a thread-safe way.
	pub fn decode_alloc_id<D>(&self, decoder: &mut D) -> Result<AllocId, D::Error>
	where
	D: TyDecoder<'tcx>,
	{
	// Read the index of the allocation.
	let idx = usize::try_from(decoder.read_u32()?).unwrap();
	let pos = usize::try_from(self.state.data_offsets[idx]).unwrap();

	// Decode the `AllocDiscriminant` now so that we know if we have to reserve an
	// `AllocId`.
	let (alloc_kind, pos) = decoder.with_position(pos, \|decoder\| {
	let alloc_kind = AllocDiscriminant::decode(decoder)?;
	Ok((alloc_kind, decoder.position()))
	})?;

	// Check the decoding state to see if it's already decoded or if we should
	// decode it here.
	let alloc_id = {
	let mut entry = self.state.decoding_state[idx].lock();

	match *entry {
	State::Done(alloc_id) => {
	return Ok(alloc_id);
	}
	ref mut entry @ State::Empty => {
	// We are allowed to decode.
	match alloc_kind {
	AllocDiscriminant::Alloc => {
	// If this is an allocation, we need to reserve an
	// `AllocId` so we can decode cyclic graphs.
	let alloc_id = decoder.tcx().reserve_alloc_id();
	*entry =
	State::InProgress(TinyList::new_single(self.session_id), alloc_id);
	Some(alloc_id)
	}
	AllocDiscriminant::Fn \| AllocDiscriminant::Static => {
	// Fns and statics cannot be cyclic, and their `AllocId`
	// is determined later by interning.
	*entry =
	State::InProgressNonAlloc(TinyList::new_single(self.session_id));
	None
	}
	}
	}
	State::InProgressNonAlloc(ref mut sessions) => {
	if sessions.contains(&self.session_id) {
	bug!("this should be unreachable");
	} else {
	// Start decoding concurrently.
	sessions.insert(self.session_id);
	None
	}
	}
	State::InProgress(ref mut sessions, alloc_id) => {
	if sessions.contains(&self.session_id) {
	// Don't recurse.
	return Ok(alloc_id);
	} else {
	// Start decoding concurrently.
	sessions.insert(self.session_id);
	Some(alloc_id)
	}
	}
	}
	};

	// Now decode the actual data.
	let alloc_id = decoder.with_position(pos, \|decoder\| {
	match alloc_kind {
	AllocDiscriminant::Alloc => {
	let alloc = <&'tcx Allocation as Decodable<_>>::decode(decoder)?;
	// We already have a reserved `AllocId`.
	let alloc_id = alloc_id.unwrap();
	trace!("decoded alloc {:?}: {:#?}", alloc_id, alloc);
	decoder.tcx().set_alloc_id_same_memory(alloc_id, alloc);
	Ok(alloc_id)
	}
	AllocDiscriminant::Fn => {
	assert!(alloc_id.is_none());
	trace!("creating fn alloc ID");
	let instance = ty::Instance::decode(decoder)?;
	trace!("decoded fn alloc instance: {:?}", instance);
	let alloc_id = decoder.tcx().create_fn_alloc(instance);
	Ok(alloc_id)
	}
	AllocDiscriminant::Static => {
	assert!(alloc_id.is_none());
	trace!("creating extern static alloc ID");
	let did = <DefId as Decodable<D>>::decode(decoder)?;
	trace!("decoded static def-ID: {:?}", did);
	let alloc_id = decoder.tcx().create_static_alloc(did);
	Ok(alloc_id)
	}
	}
	})?;

	self.state.decoding_state[idx].with_lock(\|entry\| {
	*entry = State::Done(alloc_id);
	});

	Ok(alloc_id)
	}
	}

	/// An allocation in the global (tcx-managed) memory can be either a function pointer,
	/// a static, or a "real" allocation with some data in it.
	#[derive(Debug, Clone, Eq, PartialEq, Hash, TyDecodable, TyEncodable, HashStable)]
	pub enum GlobalAlloc<'tcx> {
	/// The alloc ID is used as a function pointer.
	Function(Instance<'tcx>),
	/// The alloc ID points to a "lazy" static variable that did not get computed (yet).
	/// This is also used to break the cycle in recursive statics.
	Static(DefId),
	/// The alloc ID points to memory.
	Memory(&'tcx Allocation),
	}

	impl GlobalAlloc<'tcx> {
	/// Panics if the `GlobalAlloc` does not refer to an `GlobalAlloc::Memory`
	#[track_caller]
	#[inline]
	pub fn unwrap_memory(&self) -> &'tcx Allocation {
	match *self {
	GlobalAlloc::Memory(mem) => mem,
	_ => bug!("expected memory, got {:?}", self),
	}
	}

	/// Panics if the `GlobalAlloc` is not `GlobalAlloc::Function`
	#[track_caller]
	#[inline]
	pub fn unwrap_fn(&self) -> Instance<'tcx> {
	match *self {
	GlobalAlloc::Function(instance) => instance,
	_ => bug!("expected function, got {:?}", self),
	}
	}
	}

	crate struct AllocMap<'tcx> {
	/// Maps `AllocId`s to their corresponding allocations.
	alloc_map: FxHashMap<AllocId, GlobalAlloc<'tcx>>,

	/// Used to ensure that statics and functions only get one associated `AllocId`.
	/// Should never contain a `GlobalAlloc::Memory`!
	//
	// FIXME: Should we just have two separate dedup maps for statics and functions each?
	dedup: FxHashMap<GlobalAlloc<'tcx>, AllocId>,

	/// The `AllocId` to assign to the next requested ID.
	/// Always incremented; never gets smaller.
	next_id: AllocId,
	}

	impl<'tcx> AllocMap<'tcx> {
	crate fn new() -> Self {
	AllocMap { alloc_map: Default::default(), dedup: Default::default(), next_id: AllocId(0) }
	}
	fn reserve(&mut self) -> AllocId {
	let next = self.next_id;
	self.next_id.0 = self.next_id.0.checked_add(1).expect(
	"You overflowed a u64 by incrementing by 1... \
	You've just earned yourself a free drink if we ever meet. \
	Seriously, how did you do that?!",
	);
	next
	}
	}

	impl<'tcx> TyCtxt<'tcx> {
	/// Obtains a new allocation ID that can be referenced but does not
	/// yet have an allocation backing it.
	///
	/// Make sure to call `set_alloc_id_memory` or `set_alloc_id_same_memory` before returning such
	/// an `AllocId` from a query.
	pub fn reserve_alloc_id(self) -> AllocId {
	self.alloc_map.lock().reserve()
	}

	/// Reserves a new ID if this allocation has not been dedup-reserved before.
	/// Should only be used for function pointers and statics, we don't want
	/// to dedup IDs for "real" memory!
	fn reserve_and_set_dedup(self, alloc: GlobalAlloc<'tcx>) -> AllocId {
	let mut alloc_map = self.alloc_map.lock();
	match alloc {
	GlobalAlloc::Function(..) \| GlobalAlloc::Static(..) => {}
	GlobalAlloc::Memory(..) => bug!("Trying to dedup-reserve memory with real data!"),
	}
	if let Some(&alloc_id) = alloc_map.dedup.get(&alloc) {
	return alloc_id;
	}
	let id = alloc_map.reserve();
	debug!("creating alloc {:?} with id {}", alloc, id);
	alloc_map.alloc_map.insert(id, alloc.clone());
	alloc_map.dedup.insert(alloc, id);
	id
	}

	/// Generates an `AllocId` for a static or return a cached one in case this function has been
	/// called on the same static before.
	pub fn create_static_alloc(self, static_id: DefId) -> AllocId {
	self.reserve_and_set_dedup(GlobalAlloc::Static(static_id))
	}

	/// Generates an `AllocId` for a function. Depending on the function type,
	/// this might get deduplicated or assigned a new ID each time.
	pub fn create_fn_alloc(self, instance: Instance<'tcx>) -> AllocId {
	// Functions cannot be identified by pointers, as asm-equal functions can get deduplicated
	// by the linker (we set the "unnamed_addr" attribute for LLVM) and functions can be
	// duplicated across crates.
	// We thus generate a new `AllocId` for every mention of a function. This means that
	// `main as fn() == main as fn()` is false, while `let x = main as fn(); x == x` is true.
	// However, formatting code relies on function identity (see #58320), so we only do
	// this for generic functions. Lifetime parameters are ignored.
	let is_generic = instance.substs.into_iter().any(\|kind\| match kind.unpack() {
	GenericArgKind::Lifetime(_) => false,
	_ => true,
	});
	if is_generic {
	// Get a fresh ID.
	let mut alloc_map = self.alloc_map.lock();
	let id = alloc_map.reserve();
	alloc_map.alloc_map.insert(id, GlobalAlloc::Function(instance));
	id
	} else {
	// Deduplicate.
	self.reserve_and_set_dedup(GlobalAlloc::Function(instance))
	}
	}

	/// Interns the `Allocation` and return a new `AllocId`, even if there's already an identical
	/// `Allocation` with a different `AllocId`.
	/// Statics with identical content will still point to the same `Allocation`, i.e.,
	/// their data will be deduplicated through `Allocation` interning -- but they
	/// are different places in memory and as such need different IDs.
	pub fn create_memory_alloc(self, mem: &'tcx Allocation) -> AllocId {
	let id = self.reserve_alloc_id();
	self.set_alloc_id_memory(id, mem);
	id
	}

	/// Returns `None` in case the `AllocId` is dangling. An `InterpretCx` can still have a
	/// local `Allocation` for that `AllocId`, but having such an `AllocId` in a constant is
	/// illegal and will likely ICE.
	/// This function exists to allow const eval to detect the difference between evaluation-
	/// local dangling pointers and allocations in constants/statics.
	#[inline]
	pub fn get_global_alloc(self, id: AllocId) -> Option<GlobalAlloc<'tcx>> {
	self.alloc_map.lock().alloc_map.get(&id).cloned()
	}

	#[inline]
	#[track_caller]
	/// Panics in case the `AllocId` is dangling. Since that is impossible for `AllocId`s in
	/// constants (as all constants must pass interning and validation that check for dangling
	/// ids), this function is frequently used throughout rustc, but should not be used within
	/// the miri engine.
	pub fn global_alloc(self, id: AllocId) -> GlobalAlloc<'tcx> {
	match self.get_global_alloc(id) {
	Some(alloc) => alloc,
	None => bug!("could not find allocation for {}", id),
	}
	}

	/// Freezes an `AllocId` created with `reserve` by pointing it at an `Allocation`. Trying to
	/// call this function twice, even with the same `Allocation` will ICE the compiler.
	pub fn set_alloc_id_memory(self, id: AllocId, mem: &'tcx Allocation) {
	if let Some(old) = self.alloc_map.lock().alloc_map.insert(id, GlobalAlloc::Memory(mem)) {
	bug!("tried to set allocation ID {}, but it was already existing as {:#?}", id, old);
	}
	}

	/// Freezes an `AllocId` created with `reserve` by pointing it at an `Allocation`. May be called
	/// twice for the same `(AllocId, Allocation)` pair.
	fn set_alloc_id_same_memory(self, id: AllocId, mem: &'tcx Allocation) {
	self.alloc_map.lock().alloc_map.insert_same(id, GlobalAlloc::Memory(mem));
	}
	}

	////////////////////////////////////////////////////////////////////////////////
	// Methods to access integers in the target endianness
	////////////////////////////////////////////////////////////////////////////////

	#[inline]
	pub fn write_target_uint(
	endianness: Endian,
	mut target: &mut [u8],
	data: u128,
	) -> Result<(), io::Error> {
	// This u128 holds an "any-size uint" (since smaller uints can fits in it)
	// So we do not write all bytes of the u128, just the "payload".
	match endianness {
	Endian::Little => target.write(&data.to_le_bytes())?,
	Endian::Big => target.write(&data.to_be_bytes()[16 - target.len()..])?,
	};
	debug_assert!(target.len() == 0); // We should have filled the target buffer.
	Ok(())
	}

	#[inline]
	pub fn read_target_uint(endianness: Endian, mut source: &[u8]) -> Result<u128, io::Error> {
	// This u128 holds an "any-size uint" (since smaller uints can fits in it)
	let mut buf = [0u8; std::mem::size_of::<u128>()];
	// So we do not read exactly 16 bytes into the u128, just the "payload".
	let uint = match endianness {
	Endian::Little => {
	source.read(&mut buf)?;
	Ok(u128::from_le_bytes(buf))
	}
	Endian::Big => {
	source.read(&mut buf[16 - source.len()..])?;
	Ok(u128::from_be_bytes(buf))
	}
	};
	debug_assert!(source.len() == 0); // We should have consumed the source buffer.
	uint
	}

	////////////////////////////////////////////////////////////////////////////////
	// Methods to facilitate working with signed integers stored in a u128
	////////////////////////////////////////////////////////////////////////////////

	/// Truncates `value` to `size` bits and then sign-extend it to 128 bits
	/// (i.e., if it is negative, fill with 1's on the left).
	#[inline]
	pub fn sign_extend(value: u128, size: Size) -> u128 {
	let size = size.bits();
	if size == 0 {
	// Truncated until nothing is left.
	return 0;
	}
	// Sign-extend it.
	let shift = 128 - size;
	// Shift the unsigned value to the left, then shift back to the right as signed
	// (essentially fills with FF on the left).
	(((value << shift) as i128) >> shift) as u128
	}

	/// Truncates `value` to `size` bits.
	#[inline]
	pub fn truncate(value: u128, size: Size) -> u128 {
	let size = size.bits();
	if size == 0 {
	// Truncated until nothing is left.
	return 0;
	}
	let shift = 128 - size;
	// Truncate (shift left to drop out leftover values, shift right to fill with zeroes).
	(value << shift) >> shift
	}

	/// Computes the unsigned absolute value without wrapping or panicking.
	#[inline]
	pub fn uabs(value: i64) -> u64 {
	// The only tricky part here is if value == i64::MIN. In that case,
	// wrapping_abs() returns i64::MIN == -2^63. Casting this value to a u64
	// gives 2^63, the correct value.
	value.wrapping_abs() as u64
	}