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