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