src/librustc/mir/interpret/mod.rs

   1 //! An interpreter for MIR used in CTFE and by miri
   2
   3 #[macro_export]
   4 macro_rules! err {
   5     ($($tt:tt)*) => { Err($crate::mir::interpret::InterpError::$($tt)*.into()) };
   6 }
   7
   8 mod error;
   9 mod value;
  10 mod allocation;
  11 mod pointer;
  12
  13 pub use self::error::{
  14     InterpErrorInfo, InterpResult, InterpError, AssertMessage, ConstEvalErr, struct_error,
  15     FrameInfo, ConstEvalRawResult, ConstEvalResult, ErrorHandled,
  16 };
  17
  18 pub use self::value::{Scalar, ScalarMaybeUndef, RawConst, ConstValue};
  19
  20 pub use self::allocation::{Allocation, AllocationExtra, Relocations, UndefMask};
  21
  22 pub use self::pointer::{Pointer, PointerArithmetic, CheckInAllocMsg};
  23
  24 use std::fmt;
  25 use crate::mir;
  26 use crate::hir::def_id::DefId;
  27 use crate::ty::{self, TyCtxt, Instance, subst::UnpackedKind};
  28 use crate::ty::layout::{self, Size};
  29 use std::io;
  30 use rustc_serialize::{Encoder, Decodable, Encodable};
  31 use rustc_data_structures::fx::FxHashMap;
  32 use rustc_data_structures::sync::{Lock as Mutex, HashMapExt};
  33 use rustc_data_structures::tiny_list::TinyList;
  34 use rustc_macros::HashStable;
  35 use byteorder::{WriteBytesExt, ReadBytesExt, LittleEndian, BigEndian};
  36 use crate::ty::codec::TyDecoder;
  37 use std::sync::atomic::{AtomicU32, Ordering};
  38 use std::num::NonZeroU32;
  39
  40 /// Uniquely identifies a specific constant or static.
  41 #[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, RustcEncodable, RustcDecodable, HashStable)]
  42 pub struct GlobalId<'tcx> {
  43     /// For a constant or static, the `Instance` of the item itself.
  44     /// For a promoted global, the `Instance` of the function they belong to.
  45     pub instance: ty::Instance<'tcx>,
  46
  47     /// The index for promoted globals within their function's `mir::Body`.
  48     pub promoted: Option<mir::Promoted>,
  49 }
  50
  51 #[derive(Copy, Clone, Eq, Hash, Ord, PartialEq, PartialOrd, Debug)]
  52 pub struct AllocId(pub u64);
  53
  54 impl rustc_serialize::UseSpecializedEncodable for AllocId {}
  55 impl rustc_serialize::UseSpecializedDecodable for AllocId {}
  56
  57 #[derive(RustcDecodable, RustcEncodable)]
  58 enum AllocDiscriminant {
  59     Alloc,
  60     Fn,
  61     Static,
  62 }
  63
  64 pub fn specialized_encode_alloc_id<'tcx, E: Encoder>(
  65     encoder: &mut E,
  66     tcx: TyCtxt<'tcx>,
  67     alloc_id: AllocId,
  68 ) -> Result<(), E::Error> {
  69     let alloc: GlobalAlloc<'tcx> =
  70         tcx.alloc_map.lock().get(alloc_id).expect("no value for AllocId");
  71     match alloc {
  72         GlobalAlloc::Memory(alloc) => {
  73             trace!("encoding {:?} with {:#?}", alloc_id, alloc);
  74             AllocDiscriminant::Alloc.encode(encoder)?;
  75             alloc.encode(encoder)?;
  76         }
  77         GlobalAlloc::Function(fn_instance) => {
  78             trace!("encoding {:?} with {:#?}", alloc_id, fn_instance);
  79             AllocDiscriminant::Fn.encode(encoder)?;
  80             fn_instance.encode(encoder)?;
  81         }
  82         GlobalAlloc::Static(did) => {
  83             // referring to statics doesn't need to know about their allocations,
  84             // just about its DefId
  85             AllocDiscriminant::Static.encode(encoder)?;
  86             did.encode(encoder)?;
  87         }
  88     }
  89     Ok(())
  90 }
  91
  92 // Used to avoid infinite recursion when decoding cyclic allocations.
  93 type DecodingSessionId = NonZeroU32;
  94
  95 #[derive(Clone)]
  96 enum State {
  97     Empty,
  98     InProgressNonAlloc(TinyList<DecodingSessionId>),
  99     InProgress(TinyList<DecodingSessionId>, AllocId),
 100     Done(AllocId),
 101 }
 102
 103 pub struct AllocDecodingState {
 104     // For each AllocId we keep track of which decoding state it's currently in.
 105     decoding_state: Vec<Mutex<State>>,
 106     // The offsets of each allocation in the data stream.
 107     data_offsets: Vec<u32>,
 108 }
 109
 110 impl AllocDecodingState {
 111
 112     pub fn new_decoding_session(&self) -> AllocDecodingSession<'_> {
 113         static DECODER_SESSION_ID: AtomicU32 = AtomicU32::new(0);
 114         let counter = DECODER_SESSION_ID.fetch_add(1, Ordering::SeqCst);
 115
 116         // Make sure this is never zero
 117         let session_id = DecodingSessionId::new((counter & 0x7FFFFFFF) + 1).unwrap();
 118
 119         AllocDecodingSession {
 120             state: self,
 121             session_id,
 122         }
 123     }
 124
 125     pub fn new(data_offsets: Vec<u32>) -> AllocDecodingState {
 126         let decoding_state = vec![Mutex::new(State::Empty); data_offsets.len()];
 127
 128         AllocDecodingState {
 129             decoding_state,
 130             data_offsets,
 131         }
 132     }
 133 }
 134
 135 #[derive(Copy, Clone)]
 136 pub struct AllocDecodingSession<'s> {
 137     state: &'s AllocDecodingState,
 138     session_id: DecodingSessionId,
 139 }
 140
 141 impl<'s> AllocDecodingSession<'s> {
 142     // Decodes an AllocId in a thread-safe way.
 143     pub fn decode_alloc_id<D>(&self, decoder: &mut D) -> Result<AllocId, D::Error>
 144     where
 145         D: TyDecoder<'tcx>,
 146     {
 147         // Read the index of the allocation
 148         let idx = decoder.read_u32()? as usize;
 149         let pos = self.state.data_offsets[idx] as usize;
 150
 151         // Decode the AllocDiscriminant now so that we know if we have to reserve an
 152         // AllocId.
 153         let (alloc_kind, pos) = decoder.with_position(pos, |decoder| {
 154             let alloc_kind = AllocDiscriminant::decode(decoder)?;
 155             Ok((alloc_kind, decoder.position()))
 156         })?;
 157
 158         // Check the decoding state, see if it's already decoded or if we should
 159         // decode it here.
 160         let alloc_id = {
 161             let mut entry = self.state.decoding_state[idx].lock();
 162
 163             match *entry {
 164                 State::Done(alloc_id) => {
 165                     return Ok(alloc_id);
 166                 }
 167                 ref mut entry @ State::Empty => {
 168                     // We are allowed to decode
 169                     match alloc_kind {
 170                         AllocDiscriminant::Alloc => {
 171                             // If this is an allocation, we need to reserve an
 172                             // AllocId so we can decode cyclic graphs.
 173                             let alloc_id = decoder.tcx().alloc_map.lock().reserve();
 174                             *entry = State::InProgress(
 175                                 TinyList::new_single(self.session_id),
 176                                 alloc_id);
 177                             Some(alloc_id)
 178                         },
 179                         AllocDiscriminant::Fn | AllocDiscriminant::Static => {
 180                             // Fns and statics cannot be cyclic and their AllocId
 181                             // is determined later by interning
 182                             *entry = State::InProgressNonAlloc(
 183                                 TinyList::new_single(self.session_id));
 184                             None
 185                         }
 186                     }
 187                 }
 188                 State::InProgressNonAlloc(ref mut sessions) => {
 189                     if sessions.contains(&self.session_id) {
 190                         bug!("This should be unreachable")
 191                     } else {
 192                         // Start decoding concurrently
 193                         sessions.insert(self.session_id);
 194                         None
 195                     }
 196                 }
 197                 State::InProgress(ref mut sessions, alloc_id) => {
 198                     if sessions.contains(&self.session_id) {
 199                         // Don't recurse.
 200                         return Ok(alloc_id)
 201                     } else {
 202                         // Start decoding concurrently
 203                         sessions.insert(self.session_id);
 204                         Some(alloc_id)
 205                     }
 206                 }
 207             }
 208         };
 209
 210         // Now decode the actual data
 211         let alloc_id = decoder.with_position(pos, |decoder| {
 212             match alloc_kind {
 213                 AllocDiscriminant::Alloc => {
 214                     let allocation = <&'tcx Allocation as Decodable>::decode(decoder)?;
 215                     // We already have a reserved AllocId.
 216                     let alloc_id = alloc_id.unwrap();
 217                     trace!("decoded alloc {:?} {:#?}", alloc_id, allocation);
 218                     decoder.tcx().alloc_map.lock().set_alloc_id_same_memory(alloc_id, allocation);
 219                     Ok(alloc_id)
 220                 },
 221                 AllocDiscriminant::Fn => {
 222                     assert!(alloc_id.is_none());
 223                     trace!("creating fn alloc id");
 224                     let instance = ty::Instance::decode(decoder)?;
 225                     trace!("decoded fn alloc instance: {:?}", instance);
 226                     let alloc_id = decoder.tcx().alloc_map.lock().create_fn_alloc(instance);
 227                     Ok(alloc_id)
 228                 },
 229                 AllocDiscriminant::Static => {
 230                     assert!(alloc_id.is_none());
 231                     trace!("creating extern static alloc id at");
 232                     let did = DefId::decode(decoder)?;
 233                     let alloc_id = decoder.tcx().alloc_map.lock().create_static_alloc(did);
 234                     Ok(alloc_id)
 235                 }
 236             }
 237         })?;
 238
 239         self.state.decoding_state[idx].with_lock(|entry| {
 240             *entry = State::Done(alloc_id);
 241         });
 242
 243         Ok(alloc_id)
 244     }
 245 }
 246
 247 impl fmt::Display for AllocId {
 248     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 249         write!(f, "{}", self.0)
 250     }
 251 }
 252
 253 /// An allocation in the global (tcx-managed) memory can be either a function pointer,
 254 /// a static, or a "real" allocation with some data in it.
 255 #[derive(Debug, Clone, Eq, PartialEq, Hash, RustcDecodable, RustcEncodable, HashStable)]
 256 pub enum GlobalAlloc<'tcx> {
 257     /// The alloc ID is used as a function pointer
 258     Function(Instance<'tcx>),
 259     /// The alloc ID points to a "lazy" static variable that did not get computed (yet).
 260     /// This is also used to break the cycle in recursive statics.
 261     Static(DefId),
 262     /// The alloc ID points to memory.
 263     Memory(&'tcx Allocation),
 264 }
 265
 266 pub struct AllocMap<'tcx> {
 267     /// Lets you know what an `AllocId` refers to.
 268     alloc_map: FxHashMap<AllocId, GlobalAlloc<'tcx>>,
 269
 270     /// Used to ensure that statics and functions only get one associated `AllocId`.
 271     /// Should never contain a `GlobalAlloc::Memory`!
 272     /// FIXME: Should we just have two separate dedup maps for statics and functions each?
 273     dedup: FxHashMap<GlobalAlloc<'tcx>, AllocId>,
 274
 275     /// The `AllocId` to assign to the next requested ID.
 276     /// Always incremented, never gets smaller.
 277     next_id: AllocId,
 278 }
 279
 280 impl<'tcx> AllocMap<'tcx> {
 281     pub fn new() -> Self {
 282         AllocMap {
 283             alloc_map: Default::default(),
 284             dedup: Default::default(),
 285             next_id: AllocId(0),
 286         }
 287     }
 288
 289     /// Obtains a new allocation ID that can be referenced but does not
 290     /// yet have an allocation backing it.
 291     ///
 292     /// Make sure to call `set_alloc_id_memory` or `set_alloc_id_same_memory` before returning such
 293     /// an `AllocId` from a query.
 294     pub fn reserve(
 295         &mut self,
 296     ) -> AllocId {
 297         let next = self.next_id;
 298         self.next_id.0 = self.next_id.0
 299             .checked_add(1)
 300             .expect("You overflowed a u64 by incrementing by 1... \
 301                      You've just earned yourself a free drink if we ever meet. \
 302                      Seriously, how did you do that?!");
 303         next
 304     }
 305
 306     /// Reserve a new ID *if* this allocation has not been dedup-reserved before.
 307     /// Should only be used for function pointers and statics, we don't want
 308     /// to dedup IDs for "real" memory!
 309     fn reserve_and_set_dedup(&mut self, alloc: GlobalAlloc<'tcx>) -> AllocId {
 310         match alloc {
 311             GlobalAlloc::Function(..) | GlobalAlloc::Static(..) => {},
 312             GlobalAlloc::Memory(..) => bug!("Trying to dedup-reserve memory with real data!"),
 313         }
 314         if let Some(&alloc_id) = self.dedup.get(&alloc) {
 315             return alloc_id;
 316         }
 317         let id = self.reserve();
 318         debug!("creating alloc {:?} with id {}", alloc, id);
 319         self.alloc_map.insert(id, alloc.clone());
 320         self.dedup.insert(alloc, id);
 321         id
 322     }
 323
 324     /// Generates an `AllocId` for a static or return a cached one in case this function has been
 325     /// called on the same static before.
 326     pub fn create_static_alloc(&mut self, static_id: DefId) -> AllocId {
 327         self.reserve_and_set_dedup(GlobalAlloc::Static(static_id))
 328     }
 329
 330     /// Generates an `AllocId` for a function.  Depending on the function type,
 331     /// this might get deduplicated or assigned a new ID each time.
 332     pub fn create_fn_alloc(&mut self, instance: Instance<'tcx>) -> AllocId {
 333         // Functions cannot be identified by pointers, as asm-equal functions can get deduplicated
 334         // by the linker (we set the "unnamed_addr" attribute for LLVM) and functions can be
 335         // duplicated across crates.
 336         // We thus generate a new `AllocId` for every mention of a function. This means that
 337         // `main as fn() == main as fn()` is false, while `let x = main as fn(); x == x` is true.
 338         // However, formatting code relies on function identity (see #58320), so we only do
 339         // this for generic functions.  Lifetime parameters are ignored.
 340         let is_generic = instance.substs.into_iter().any(|kind| {
 341             match kind.unpack() {
 342                 UnpackedKind::Lifetime(_) => false,
 343                 _ => true,
 344             }
 345         });
 346         if is_generic {
 347             // Get a fresh ID
 348             let id = self.reserve();
 349             self.alloc_map.insert(id, GlobalAlloc::Function(instance));
 350             id
 351         } else {
 352             // Deduplicate
 353             self.reserve_and_set_dedup(GlobalAlloc::Function(instance))
 354         }
 355     }
 356
 357     /// Intern the `Allocation` and return a new `AllocId`, even if there's already an identical
 358     /// `Allocation` with a different `AllocId`.
 359     /// Statics with identical content will still point to the same `Allocation`, i.e.,
 360     /// their data will be deduplicated through `Allocation` interning -- but they
 361     /// are different places in memory and as such need different IDs.
 362     pub fn create_memory_alloc(&mut self, mem: &'tcx Allocation) -> AllocId {
 363         let id = self.reserve();
 364         self.set_alloc_id_memory(id, mem);
 365         id
 366     }
 367
 368     /// Returns `None` in case the `AllocId` is dangling. An `InterpretCx` can still have a
 369     /// local `Allocation` for that `AllocId`, but having such an `AllocId` in a constant is
 370     /// illegal and will likely ICE.
 371     /// This function exists to allow const eval to detect the difference between evaluation-
 372     /// local dangling pointers and allocations in constants/statics.
 373     #[inline]
 374     pub fn get(&self, id: AllocId) -> Option<GlobalAlloc<'tcx>> {
 375         self.alloc_map.get(&id).cloned()
 376     }
 377
 378     /// Panics if the `AllocId` does not refer to an `Allocation`
 379     pub fn unwrap_memory(&self, id: AllocId) -> &'tcx Allocation {
 380         match self.get(id) {
 381             Some(GlobalAlloc::Memory(mem)) => mem,
 382             _ => bug!("expected allocation id {} to point to memory", id),
 383         }
 384     }
 385
 386     /// Freeze an `AllocId` created with `reserve` by pointing it at an `Allocation`. Trying to
 387     /// call this function twice, even with the same `Allocation` will ICE the compiler.
 388     pub fn set_alloc_id_memory(&mut self, id: AllocId, mem: &'tcx Allocation) {
 389         if let Some(old) = self.alloc_map.insert(id, GlobalAlloc::Memory(mem)) {
 390             bug!("tried to set allocation id {}, but it was already existing as {:#?}", id, old);
 391         }
 392     }
 393
 394     /// Freeze an `AllocId` created with `reserve` by pointing it at an `Allocation`. May be called
 395     /// twice for the same `(AllocId, Allocation)` pair.
 396     fn set_alloc_id_same_memory(&mut self, id: AllocId, mem: &'tcx Allocation) {
 397         self.alloc_map.insert_same(id, GlobalAlloc::Memory(mem));
 398     }
 399 }
 400
 401 ////////////////////////////////////////////////////////////////////////////////
 402 // Methods to access integers in the target endianness
 403 ////////////////////////////////////////////////////////////////////////////////
 404
 405 #[inline]
 406 pub fn write_target_uint(
 407     endianness: layout::Endian,
 408     mut target: &mut [u8],
 409     data: u128,
 410 ) -> Result<(), io::Error> {
 411     let len = target.len();
 412     match endianness {
 413         layout::Endian::Little => target.write_uint128::<LittleEndian>(data, len),
 414         layout::Endian::Big => target.write_uint128::<BigEndian>(data, len),
 415     }
 416 }
 417
 418 #[inline]
 419 pub fn read_target_uint(endianness: layout::Endian, mut source: &[u8]) -> Result<u128, io::Error> {
 420     match endianness {
 421         layout::Endian::Little => source.read_uint128::<LittleEndian>(source.len()),
 422         layout::Endian::Big => source.read_uint128::<BigEndian>(source.len()),
 423     }
 424 }
 425
 426 ////////////////////////////////////////////////////////////////////////////////
 427 // Methods to facilitate working with signed integers stored in a u128
 428 ////////////////////////////////////////////////////////////////////////////////
 429
 430 /// Truncate `value` to `size` bits and then sign-extend it to 128 bits
 431 /// (i.e., if it is negative, fill with 1's on the left).
 432 #[inline]
 433 pub fn sign_extend(value: u128, size: Size) -> u128 {
 434     let size = size.bits();
 435     if size == 0 {
 436         // Truncated until nothing is left.
 437         return 0;
 438     }
 439     // sign extend
 440     let shift = 128 - size;
 441     // shift the unsigned value to the left
 442     // and back to the right as signed (essentially fills with FF on the left)
 443     (((value << shift) as i128) >> shift) as u128
 444 }
 445
 446 /// Truncate `value` to `size` bits.
 447 #[inline]
 448 pub fn truncate(value: u128, size: Size) -> u128 {
 449     let size = size.bits();
 450     if size == 0 {
 451         // Truncated until nothing is left.
 452         return 0;
 453     }
 454     let shift = 128 - size;
 455     // truncate (shift left to drop out leftover values, shift right to fill with zeroes)
 456     (value << shift) >> shift
 457 }