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