src/librustc/mir/interpret/mod.rs

   1 // Copyright 2018 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! An interpreter for MIR used in CTFE and by miri
  12
  13 #[macro_export]
  14 macro_rules! err {
  15     ($($tt:tt)*) => { Err($crate::mir::interpret::EvalErrorKind::$($tt)*.into()) };
  16 }
  17
  18 mod error;
  19 mod value;
  20 mod allocation;
  21 mod pointer;
  22
  23 pub use self::error::{
  24     EvalError, EvalResult, EvalErrorKind, AssertMessage, ConstEvalErr, struct_error,
  25     FrameInfo, ConstEvalRawResult, ConstEvalResult, ErrorHandled,
  26 };
  27
  28 pub use self::value::{Scalar, ScalarMaybeUndef, RawConst, ConstValue};
  29
  30 pub use self::allocation::{
  31     InboundsCheck, Allocation, AllocationExtra,
  32     Relocations, UndefMask,
  33 };
  34
  35 pub use self::pointer::{Pointer, PointerArithmetic};
  36
  37 use std::fmt;
  38 use mir;
  39 use hir::def_id::DefId;
  40 use ty::{self, TyCtxt, Instance};
  41 use ty::layout::{self, Size};
  42 use middle::region;
  43 use std::io;
  44 use rustc_serialize::{Encoder, Decodable, Encodable};
  45 use rustc_data_structures::fx::FxHashMap;
  46 use rustc_data_structures::sync::{Lock as Mutex, HashMapExt};
  47 use rustc_data_structures::tiny_list::TinyList;
  48 use byteorder::{WriteBytesExt, ReadBytesExt, LittleEndian, BigEndian};
  49 use ty::codec::TyDecoder;
  50 use std::sync::atomic::{AtomicU32, Ordering};
  51 use std::num::NonZeroU32;
  52
  53 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
  54 pub enum Lock {
  55     NoLock,
  56     WriteLock(DynamicLifetime),
  57     /// This should never be empty -- that would be a read lock held and nobody
  58     /// there to release it...
  59     ReadLock(Vec<DynamicLifetime>),
  60 }
  61
  62 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
  63 pub struct DynamicLifetime {
  64     pub frame: usize,
  65     pub region: Option<region::Scope>, // "None" indicates "until the function ends"
  66 }
  67
  68 #[derive(Copy, Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable)]
  69 pub enum AccessKind {
  70     Read,
  71     Write,
  72 }
  73
  74 /// Uniquely identifies a specific constant or static.
  75 #[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, RustcEncodable, RustcDecodable)]
  76 pub struct GlobalId<'tcx> {
  77     /// For a constant or static, the `Instance` of the item itself.
  78     /// For a promoted global, the `Instance` of the function they belong to.
  79     pub instance: ty::Instance<'tcx>,
  80
  81     /// The index for promoted globals within their function's `Mir`.
  82     pub promoted: Option<mir::Promoted>,
  83 }
  84
  85 #[derive(Copy, Clone, Eq, Hash, Ord, PartialEq, PartialOrd, Debug)]
  86 pub struct AllocId(pub u64);
  87
  88 impl ::rustc_serialize::UseSpecializedEncodable for AllocId {}
  89 impl ::rustc_serialize::UseSpecializedDecodable for AllocId {}
  90
  91 #[derive(RustcDecodable, RustcEncodable)]
  92 enum AllocKind {
  93     Alloc,
  94     Fn,
  95     Static,
  96 }
  97
  98 pub fn specialized_encode_alloc_id<
  99     'a, 'tcx,
 100     E: Encoder,
 101 >(
 102     encoder: &mut E,
 103     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 104     alloc_id: AllocId,
 105 ) -> Result<(), E::Error> {
 106     let alloc_type: AllocType<'tcx> =
 107         tcx.alloc_map.lock().get(alloc_id).expect("no value for AllocId");
 108     match alloc_type {
 109         AllocType::Memory(alloc) => {
 110             trace!("encoding {:?} with {:#?}", alloc_id, alloc);
 111             AllocKind::Alloc.encode(encoder)?;
 112             alloc.encode(encoder)?;
 113         }
 114         AllocType::Function(fn_instance) => {
 115             trace!("encoding {:?} with {:#?}", alloc_id, fn_instance);
 116             AllocKind::Fn.encode(encoder)?;
 117             fn_instance.encode(encoder)?;
 118         }
 119         AllocType::Static(did) => {
 120             // referring to statics doesn't need to know about their allocations,
 121             // just about its DefId
 122             AllocKind::Static.encode(encoder)?;
 123             did.encode(encoder)?;
 124         }
 125     }
 126     Ok(())
 127 }
 128
 129 // Used to avoid infinite recursion when decoding cyclic allocations.
 130 type DecodingSessionId = NonZeroU32;
 131
 132 #[derive(Clone)]
 133 enum State {
 134     Empty,
 135     InProgressNonAlloc(TinyList<DecodingSessionId>),
 136     InProgress(TinyList<DecodingSessionId>, AllocId),
 137     Done(AllocId),
 138 }
 139
 140 pub struct AllocDecodingState {
 141     // For each AllocId we keep track of which decoding state it's currently in.
 142     decoding_state: Vec<Mutex<State>>,
 143     // The offsets of each allocation in the data stream.
 144     data_offsets: Vec<u32>,
 145 }
 146
 147 impl AllocDecodingState {
 148
 149     pub fn new_decoding_session(&self) -> AllocDecodingSession<'_> {
 150         static DECODER_SESSION_ID: AtomicU32 = AtomicU32::new(0);
 151         let counter = DECODER_SESSION_ID.fetch_add(1, Ordering::SeqCst);
 152
 153         // Make sure this is never zero
 154         let session_id = DecodingSessionId::new((counter & 0x7FFFFFFF) + 1).unwrap();
 155
 156         AllocDecodingSession {
 157             state: self,
 158             session_id,
 159         }
 160     }
 161
 162     pub fn new(data_offsets: Vec<u32>) -> AllocDecodingState {
 163         let decoding_state = vec![Mutex::new(State::Empty); data_offsets.len()];
 164
 165         AllocDecodingState {
 166             decoding_state,
 167             data_offsets,
 168         }
 169     }
 170 }
 171
 172 #[derive(Copy, Clone)]
 173 pub struct AllocDecodingSession<'s> {
 174     state: &'s AllocDecodingState,
 175     session_id: DecodingSessionId,
 176 }
 177
 178 impl<'s> AllocDecodingSession<'s> {
 179
 180     // Decodes an AllocId in a thread-safe way.
 181     pub fn decode_alloc_id<'a, 'tcx, D>(&self,
 182                                         decoder: &mut D)
 183                                         -> Result<AllocId, D::Error>
 184         where D: TyDecoder<'a, 'tcx>,
 185               'tcx: 'a,
 186     {
 187         // Read the index of the allocation
 188         let idx = decoder.read_u32()? as usize;
 189         let pos = self.state.data_offsets[idx] as usize;
 190
 191         // Decode the AllocKind now so that we know if we have to reserve an
 192         // AllocId.
 193         let (alloc_kind, pos) = decoder.with_position(pos, |decoder| {
 194             let alloc_kind = AllocKind::decode(decoder)?;
 195             Ok((alloc_kind, decoder.position()))
 196         })?;
 197
 198         // Check the decoding state, see if it's already decoded or if we should
 199         // decode it here.
 200         let alloc_id = {
 201             let mut entry = self.state.decoding_state[idx].lock();
 202
 203             match *entry {
 204                 State::Done(alloc_id) => {
 205                     return Ok(alloc_id);
 206                 }
 207                 ref mut entry @ State::Empty => {
 208                     // We are allowed to decode
 209                     match alloc_kind {
 210                         AllocKind::Alloc => {
 211                             // If this is an allocation, we need to reserve an
 212                             // AllocId so we can decode cyclic graphs.
 213                             let alloc_id = decoder.tcx().alloc_map.lock().reserve();
 214                             *entry = State::InProgress(
 215                                 TinyList::new_single(self.session_id),
 216                                 alloc_id);
 217                             Some(alloc_id)
 218                         },
 219                         AllocKind::Fn | AllocKind::Static => {
 220                             // Fns and statics cannot be cyclic and their AllocId
 221                             // is determined later by interning
 222                             *entry = State::InProgressNonAlloc(
 223                                 TinyList::new_single(self.session_id));
 224                             None
 225                         }
 226                     }
 227                 }
 228                 State::InProgressNonAlloc(ref mut sessions) => {
 229                     if sessions.contains(&self.session_id) {
 230                         bug!("This should be unreachable")
 231                     } else {
 232                         // Start decoding concurrently
 233                         sessions.insert(self.session_id);
 234                         None
 235                     }
 236                 }
 237                 State::InProgress(ref mut sessions, alloc_id) => {
 238                     if sessions.contains(&self.session_id) {
 239                         // Don't recurse.
 240                         return Ok(alloc_id)
 241                     } else {
 242                         // Start decoding concurrently
 243                         sessions.insert(self.session_id);
 244                         Some(alloc_id)
 245                     }
 246                 }
 247             }
 248         };
 249
 250         // Now decode the actual data
 251         let alloc_id = decoder.with_position(pos, |decoder| {
 252             match alloc_kind {
 253                 AllocKind::Alloc => {
 254                     let allocation = <&'tcx Allocation as Decodable>::decode(decoder)?;
 255                     // We already have a reserved AllocId.
 256                     let alloc_id = alloc_id.unwrap();
 257                     trace!("decoded alloc {:?} {:#?}", alloc_id, allocation);
 258                     decoder.tcx().alloc_map.lock().set_id_same_memory(alloc_id, allocation);
 259                     Ok(alloc_id)
 260                 },
 261                 AllocKind::Fn => {
 262                     assert!(alloc_id.is_none());
 263                     trace!("creating fn alloc id");
 264                     let instance = ty::Instance::decode(decoder)?;
 265                     trace!("decoded fn alloc instance: {:?}", instance);
 266                     let alloc_id = decoder.tcx().alloc_map.lock().create_fn_alloc(instance);
 267                     Ok(alloc_id)
 268                 },
 269                 AllocKind::Static => {
 270                     assert!(alloc_id.is_none());
 271                     trace!("creating extern static alloc id at");
 272                     let did = DefId::decode(decoder)?;
 273                     let alloc_id = decoder.tcx().alloc_map.lock().intern_static(did);
 274                     Ok(alloc_id)
 275                 }
 276             }
 277         })?;
 278
 279         self.state.decoding_state[idx].with_lock(|entry| {
 280             *entry = State::Done(alloc_id);
 281         });
 282
 283         Ok(alloc_id)
 284     }
 285 }
 286
 287 impl fmt::Display for AllocId {
 288     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 289         write!(f, "{}", self.0)
 290     }
 291 }
 292
 293 #[derive(Debug, Clone, Eq, PartialEq, Hash, RustcDecodable, RustcEncodable)]
 294 pub enum AllocType<'tcx> {
 295     /// The alloc id is used as a function pointer
 296     Function(Instance<'tcx>),
 297     /// The alloc id points to a "lazy" static variable that did not get computed (yet).
 298     /// This is also used to break the cycle in recursive statics.
 299     Static(DefId),
 300     /// The alloc id points to memory
 301     Memory(&'tcx Allocation),
 302 }
 303
 304 pub struct AllocMap<'tcx> {
 305     /// Lets you know what an AllocId refers to
 306     id_to_type: FxHashMap<AllocId, AllocType<'tcx>>,
 307
 308     /// Used to ensure that functions and statics only get one associated AllocId
 309     type_interner: FxHashMap<AllocType<'tcx>, AllocId>,
 310
 311     /// The AllocId to assign to the next requested id.
 312     /// Always incremented, never gets smaller.
 313     next_id: AllocId,
 314 }
 315
 316 impl<'tcx> AllocMap<'tcx> {
 317     pub fn new() -> Self {
 318         AllocMap {
 319             id_to_type: Default::default(),
 320             type_interner: Default::default(),
 321             next_id: AllocId(0),
 322         }
 323     }
 324
 325     /// obtains a new allocation ID that can be referenced but does not
 326     /// yet have an allocation backing it.
 327     pub fn reserve(
 328         &mut self,
 329     ) -> AllocId {
 330         let next = self.next_id;
 331         self.next_id.0 = self.next_id.0
 332             .checked_add(1)
 333             .expect("You overflowed a u64 by incrementing by 1... \
 334                      You've just earned yourself a free drink if we ever meet. \
 335                      Seriously, how did you do that?!");
 336         next
 337     }
 338
 339     fn intern(&mut self, alloc_type: AllocType<'tcx>) -> AllocId {
 340         if let Some(&alloc_id) = self.type_interner.get(&alloc_type) {
 341             return alloc_id;
 342         }
 343         let id = self.reserve();
 344         debug!("creating alloc_type {:?} with id {}", alloc_type, id);
 345         self.id_to_type.insert(id, alloc_type.clone());
 346         self.type_interner.insert(alloc_type, id);
 347         id
 348     }
 349
 350     // FIXME: Check if functions have identity. If not, we should not intern these,
 351     // but instead create a new id per use.
 352     // Alternatively we could just make comparing function pointers an error.
 353     pub fn create_fn_alloc(&mut self, instance: Instance<'tcx>) -> AllocId {
 354         self.intern(AllocType::Function(instance))
 355     }
 356
 357     pub fn get(&self, id: AllocId) -> Option<AllocType<'tcx>> {
 358         self.id_to_type.get(&id).cloned()
 359     }
 360
 361     pub fn unwrap_memory(&self, id: AllocId) -> &'tcx Allocation {
 362         match self.get(id) {
 363             Some(AllocType::Memory(mem)) => mem,
 364             _ => bug!("expected allocation id {} to point to memory", id),
 365         }
 366     }
 367
 368     pub fn intern_static(&mut self, static_id: DefId) -> AllocId {
 369         self.intern(AllocType::Static(static_id))
 370     }
 371
 372     pub fn allocate(&mut self, mem: &'tcx Allocation) -> AllocId {
 373         let id = self.reserve();
 374         self.set_id_memory(id, mem);
 375         id
 376     }
 377
 378     pub fn set_id_memory(&mut self, id: AllocId, mem: &'tcx Allocation) {
 379         if let Some(old) = self.id_to_type.insert(id, AllocType::Memory(mem)) {
 380             bug!("tried to set allocation id {}, but it was already existing as {:#?}", id, old);
 381         }
 382     }
 383
 384     pub fn set_id_same_memory(&mut self, id: AllocId, mem: &'tcx Allocation) {
 385        self.id_to_type.insert_same(id, AllocType::Memory(mem));
 386     }
 387 }
 388
 389 ////////////////////////////////////////////////////////////////////////////////
 390 // Methods to access integers in the target endianness
 391 ////////////////////////////////////////////////////////////////////////////////
 392
 393 pub fn write_target_uint(
 394     endianness: layout::Endian,
 395     mut target: &mut [u8],
 396     data: u128,
 397 ) -> Result<(), io::Error> {
 398     let len = target.len();
 399     match endianness {
 400         layout::Endian::Little => target.write_uint128::<LittleEndian>(data, len),
 401         layout::Endian::Big => target.write_uint128::<BigEndian>(data, len),
 402     }
 403 }
 404
 405 pub fn read_target_uint(endianness: layout::Endian, mut source: &[u8]) -> Result<u128, io::Error> {
 406     match endianness {
 407         layout::Endian::Little => source.read_uint128::<LittleEndian>(source.len()),
 408         layout::Endian::Big => source.read_uint128::<BigEndian>(source.len()),
 409     }
 410 }
 411
 412 ////////////////////////////////////////////////////////////////////////////////
 413 // Methods to facilitate working with signed integers stored in a u128
 414 ////////////////////////////////////////////////////////////////////////////////
 415
 416 pub fn sign_extend(value: u128, size: Size) -> u128 {
 417     let size = size.bits();
 418     // sign extend
 419     let shift = 128 - size;
 420     // shift the unsigned value to the left
 421     // and back to the right as signed (essentially fills with FF on the left)
 422     (((value << shift) as i128) >> shift) as u128
 423 }
 424
 425 pub fn truncate(value: u128, size: Size) -> u128 {
 426     let size = size.bits();
 427     let shift = 128 - size;
 428     // truncate (shift left to drop out leftover values, shift right to fill with zeroes)
 429     (value << shift) >> shift
 430 }