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
  21 pub use self::error::{
  22     EvalError, EvalResult, EvalErrorKind, AssertMessage, ConstEvalErr, struct_error,
  23     FrameInfo, ConstEvalResult,
  24 };
  25
  26 pub use self::value::{Scalar, ConstValue, ScalarMaybeUndef};
  27
  28 use std::fmt;
  29 use mir;
  30 use hir::def_id::DefId;
  31 use ty::{self, TyCtxt, Instance};
  32 use ty::layout::{self, Align, HasDataLayout, Size};
  33 use middle::region;
  34 use std::iter;
  35 use std::io;
  36 use std::ops::{Deref, DerefMut};
  37 use std::hash::Hash;
  38 use syntax::ast::Mutability;
  39 use rustc_serialize::{Encoder, Decodable, Encodable};
  40 use rustc_data_structures::sorted_map::SortedMap;
  41 use rustc_data_structures::fx::FxHashMap;
  42 use rustc_data_structures::sync::{Lock as Mutex, HashMapExt};
  43 use rustc_data_structures::tiny_list::TinyList;
  44 use byteorder::{WriteBytesExt, ReadBytesExt, LittleEndian, BigEndian};
  45 use ty::codec::TyDecoder;
  46 use std::sync::atomic::{AtomicU32, Ordering};
  47 use std::num::NonZeroU32;
  48
  49 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
  50 pub enum Lock {
  51     NoLock,
  52     WriteLock(DynamicLifetime),
  53     /// This should never be empty -- that would be a read lock held and nobody
  54     /// there to release it...
  55     ReadLock(Vec<DynamicLifetime>),
  56 }
  57
  58 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
  59 pub struct DynamicLifetime {
  60     pub frame: usize,
  61     pub region: Option<region::Scope>, // "None" indicates "until the function ends"
  62 }
  63
  64 #[derive(Copy, Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable)]
  65 pub enum AccessKind {
  66     Read,
  67     Write,
  68 }
  69
  70 /// Uniquely identifies a specific constant or static.
  71 #[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, RustcEncodable, RustcDecodable)]
  72 pub struct GlobalId<'tcx> {
  73     /// For a constant or static, the `Instance` of the item itself.
  74     /// For a promoted global, the `Instance` of the function they belong to.
  75     pub instance: ty::Instance<'tcx>,
  76
  77     /// The index for promoted globals within their function's `Mir`.
  78     pub promoted: Option<mir::Promoted>,
  79 }
  80
  81 ////////////////////////////////////////////////////////////////////////////////
  82 // Pointer arithmetic
  83 ////////////////////////////////////////////////////////////////////////////////
  84
  85 pub trait PointerArithmetic: layout::HasDataLayout {
  86     // These are not supposed to be overridden.
  87
  88     #[inline(always)]
  89     fn pointer_size(self) -> Size {
  90         self.data_layout().pointer_size
  91     }
  92
  93     //// Trunace the given value to the pointer size; also return whether there was an overflow
  94     fn truncate_to_ptr(self, val: u128) -> (u64, bool) {
  95         let max_ptr_plus_1 = 1u128 << self.pointer_size().bits();
  96         ((val % max_ptr_plus_1) as u64, val >= max_ptr_plus_1)
  97     }
  98
  99     // Overflow checking only works properly on the range from -u64 to +u64.
 100     fn overflowing_signed_offset(self, val: u64, i: i128) -> (u64, bool) {
 101         // FIXME: is it possible to over/underflow here?
 102         if i < 0 {
 103             // trickery to ensure that i64::min_value() works fine
 104             // this formula only works for true negative values, it panics for zero!
 105             let n = u64::max_value() - (i as u64) + 1;
 106             val.overflowing_sub(n)
 107         } else {
 108             self.overflowing_offset(val, i as u64)
 109         }
 110     }
 111
 112     fn overflowing_offset(self, val: u64, i: u64) -> (u64, bool) {
 113         let (res, over1) = val.overflowing_add(i);
 114         let (res, over2) = self.truncate_to_ptr(res as u128);
 115         (res, over1 || over2)
 116     }
 117
 118     fn signed_offset<'tcx>(self, val: u64, i: i64) -> EvalResult<'tcx, u64> {
 119         let (res, over) = self.overflowing_signed_offset(val, i as i128);
 120         if over { err!(Overflow(mir::BinOp::Add)) } else { Ok(res) }
 121     }
 122
 123     fn offset<'tcx>(self, val: u64, i: u64) -> EvalResult<'tcx, u64> {
 124         let (res, over) = self.overflowing_offset(val, i);
 125         if over { err!(Overflow(mir::BinOp::Add)) } else { Ok(res) }
 126     }
 127
 128     fn wrapping_signed_offset(self, val: u64, i: i64) -> u64 {
 129         self.overflowing_signed_offset(val, i as i128).0
 130     }
 131 }
 132
 133 impl<T: layout::HasDataLayout> PointerArithmetic for T {}
 134
 135
 136 /// Pointer is generic over the type that represents a reference to Allocations,
 137 /// thus making it possible for the most convenient representation to be used in
 138 /// each context.
 139 ///
 140 /// Defaults to the index based and loosely coupled AllocId.
 141 #[derive(Copy, Clone, Debug, Eq, PartialEq, Ord, PartialOrd, RustcEncodable, RustcDecodable, Hash)]
 142 pub struct Pointer<Id=AllocId> {
 143     pub alloc_id: Id,
 144     pub offset: Size,
 145 }
 146
 147 /// Produces a `Pointer` which points to the beginning of the Allocation
 148 impl From<AllocId> for Pointer {
 149     fn from(alloc_id: AllocId) -> Self {
 150         Pointer::new(alloc_id, Size::ZERO)
 151     }
 152 }
 153
 154 impl<'tcx> Pointer {
 155     pub fn new(alloc_id: AllocId, offset: Size) -> Self {
 156         Pointer { alloc_id, offset }
 157     }
 158
 159     pub fn wrapping_signed_offset<C: HasDataLayout>(self, i: i64, cx: C) -> Self {
 160         Pointer::new(
 161             self.alloc_id,
 162             Size::from_bytes(cx.data_layout().wrapping_signed_offset(self.offset.bytes(), i)),
 163         )
 164     }
 165
 166     pub fn overflowing_signed_offset<C: HasDataLayout>(self, i: i128, cx: C) -> (Self, bool) {
 167         let (res, over) = cx.data_layout().overflowing_signed_offset(self.offset.bytes(), i);
 168         (Pointer::new(self.alloc_id, Size::from_bytes(res)), over)
 169     }
 170
 171     pub fn signed_offset<C: HasDataLayout>(self, i: i64, cx: C) -> EvalResult<'tcx, Self> {
 172         Ok(Pointer::new(
 173             self.alloc_id,
 174             Size::from_bytes(cx.data_layout().signed_offset(self.offset.bytes(), i)?),
 175         ))
 176     }
 177
 178     pub fn overflowing_offset<C: HasDataLayout>(self, i: Size, cx: C) -> (Self, bool) {
 179         let (res, over) = cx.data_layout().overflowing_offset(self.offset.bytes(), i.bytes());
 180         (Pointer::new(self.alloc_id, Size::from_bytes(res)), over)
 181     }
 182
 183     pub fn offset<C: HasDataLayout>(self, i: Size, cx: C) -> EvalResult<'tcx, Self> {
 184         Ok(Pointer::new(
 185             self.alloc_id,
 186             Size::from_bytes(cx.data_layout().offset(self.offset.bytes(), i.bytes())?),
 187         ))
 188     }
 189 }
 190
 191
 192 #[derive(Copy, Clone, Eq, Hash, Ord, PartialEq, PartialOrd, Debug)]
 193 pub struct AllocId(pub u64);
 194
 195 impl ::rustc_serialize::UseSpecializedEncodable for AllocId {}
 196 impl ::rustc_serialize::UseSpecializedDecodable for AllocId {}
 197
 198 #[derive(RustcDecodable, RustcEncodable)]
 199 enum AllocKind {
 200     Alloc,
 201     Fn,
 202     Static,
 203 }
 204
 205 pub fn specialized_encode_alloc_id<
 206     'a, 'tcx,
 207     E: Encoder,
 208 >(
 209     encoder: &mut E,
 210     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 211     alloc_id: AllocId,
 212 ) -> Result<(), E::Error> {
 213     let alloc_type: AllocType<'tcx, &'tcx Allocation> =
 214         tcx.alloc_map.lock().get(alloc_id).expect("no value for AllocId");
 215     match alloc_type {
 216         AllocType::Memory(alloc) => {
 217             trace!("encoding {:?} with {:#?}", alloc_id, alloc);
 218             AllocKind::Alloc.encode(encoder)?;
 219             alloc.encode(encoder)?;
 220         }
 221         AllocType::Function(fn_instance) => {
 222             trace!("encoding {:?} with {:#?}", alloc_id, fn_instance);
 223             AllocKind::Fn.encode(encoder)?;
 224             fn_instance.encode(encoder)?;
 225         }
 226         AllocType::Static(did) => {
 227             // referring to statics doesn't need to know about their allocations,
 228             // just about its DefId
 229             AllocKind::Static.encode(encoder)?;
 230             did.encode(encoder)?;
 231         }
 232     }
 233     Ok(())
 234 }
 235
 236 // Used to avoid infinite recursion when decoding cyclic allocations.
 237 type DecodingSessionId = NonZeroU32;
 238
 239 #[derive(Clone)]
 240 enum State {
 241     Empty,
 242     InProgressNonAlloc(TinyList<DecodingSessionId>),
 243     InProgress(TinyList<DecodingSessionId>, AllocId),
 244     Done(AllocId),
 245 }
 246
 247 pub struct AllocDecodingState {
 248     // For each AllocId we keep track of which decoding state it's currently in.
 249     decoding_state: Vec<Mutex<State>>,
 250     // The offsets of each allocation in the data stream.
 251     data_offsets: Vec<u32>,
 252 }
 253
 254 impl AllocDecodingState {
 255
 256     pub fn new_decoding_session(&self) -> AllocDecodingSession {
 257         static DECODER_SESSION_ID: AtomicU32 = AtomicU32::new(0);
 258         let counter = DECODER_SESSION_ID.fetch_add(1, Ordering::SeqCst);
 259
 260         // Make sure this is never zero
 261         let session_id = DecodingSessionId::new((counter & 0x7FFFFFFF) + 1).unwrap();
 262
 263         AllocDecodingSession {
 264             state: self,
 265             session_id,
 266         }
 267     }
 268
 269     pub fn new(data_offsets: Vec<u32>) -> AllocDecodingState {
 270         let decoding_state: Vec<_> = ::std::iter::repeat(Mutex::new(State::Empty))
 271             .take(data_offsets.len())
 272             .collect();
 273
 274         AllocDecodingState {
 275             decoding_state: decoding_state,
 276             data_offsets,
 277         }
 278     }
 279 }
 280
 281 #[derive(Copy, Clone)]
 282 pub struct AllocDecodingSession<'s> {
 283     state: &'s AllocDecodingState,
 284     session_id: DecodingSessionId,
 285 }
 286
 287 impl<'s> AllocDecodingSession<'s> {
 288
 289     // Decodes an AllocId in a thread-safe way.
 290     pub fn decode_alloc_id<'a, 'tcx, D>(&self,
 291                                         decoder: &mut D)
 292                                         -> Result<AllocId, D::Error>
 293         where D: TyDecoder<'a, 'tcx>,
 294               'tcx: 'a,
 295     {
 296         // Read the index of the allocation
 297         let idx = decoder.read_u32()? as usize;
 298         let pos = self.state.data_offsets[idx] as usize;
 299
 300         // Decode the AllocKind now so that we know if we have to reserve an
 301         // AllocId.
 302         let (alloc_kind, pos) = decoder.with_position(pos, |decoder| {
 303             let alloc_kind = AllocKind::decode(decoder)?;
 304             Ok((alloc_kind, decoder.position()))
 305         })?;
 306
 307         // Check the decoding state, see if it's already decoded or if we should
 308         // decode it here.
 309         let alloc_id = {
 310             let mut entry = self.state.decoding_state[idx].lock();
 311
 312             match *entry {
 313                 State::Done(alloc_id) => {
 314                     return Ok(alloc_id);
 315                 }
 316                 ref mut entry @ State::Empty => {
 317                     // We are allowed to decode
 318                     match alloc_kind {
 319                         AllocKind::Alloc => {
 320                             // If this is an allocation, we need to reserve an
 321                             // AllocId so we can decode cyclic graphs.
 322                             let alloc_id = decoder.tcx().alloc_map.lock().reserve();
 323                             *entry = State::InProgress(
 324                                 TinyList::new_single(self.session_id),
 325                                 alloc_id);
 326                             Some(alloc_id)
 327                         },
 328                         AllocKind::Fn | AllocKind::Static => {
 329                             // Fns and statics cannot be cyclic and their AllocId
 330                             // is determined later by interning
 331                             *entry = State::InProgressNonAlloc(
 332                                 TinyList::new_single(self.session_id));
 333                             None
 334                         }
 335                     }
 336                 }
 337                 State::InProgressNonAlloc(ref mut sessions) => {
 338                     if sessions.contains(&self.session_id) {
 339                         bug!("This should be unreachable")
 340                     } else {
 341                         // Start decoding concurrently
 342                         sessions.insert(self.session_id);
 343                         None
 344                     }
 345                 }
 346                 State::InProgress(ref mut sessions, alloc_id) => {
 347                     if sessions.contains(&self.session_id) {
 348                         // Don't recurse.
 349                         return Ok(alloc_id)
 350                     } else {
 351                         // Start decoding concurrently
 352                         sessions.insert(self.session_id);
 353                         Some(alloc_id)
 354                     }
 355                 }
 356             }
 357         };
 358
 359         // Now decode the actual data
 360         let alloc_id = decoder.with_position(pos, |decoder| {
 361             match alloc_kind {
 362                 AllocKind::Alloc => {
 363                     let allocation = <&'tcx Allocation as Decodable>::decode(decoder)?;
 364                     // We already have a reserved AllocId.
 365                     let alloc_id = alloc_id.unwrap();
 366                     trace!("decoded alloc {:?} {:#?}", alloc_id, allocation);
 367                     decoder.tcx().alloc_map.lock().set_id_same_memory(alloc_id, allocation);
 368                     Ok(alloc_id)
 369                 },
 370                 AllocKind::Fn => {
 371                     assert!(alloc_id.is_none());
 372                     trace!("creating fn alloc id");
 373                     let instance = ty::Instance::decode(decoder)?;
 374                     trace!("decoded fn alloc instance: {:?}", instance);
 375                     let alloc_id = decoder.tcx().alloc_map.lock().create_fn_alloc(instance);
 376                     Ok(alloc_id)
 377                 },
 378                 AllocKind::Static => {
 379                     assert!(alloc_id.is_none());
 380                     trace!("creating extern static alloc id at");
 381                     let did = DefId::decode(decoder)?;
 382                     let alloc_id = decoder.tcx().alloc_map.lock().intern_static(did);
 383                     Ok(alloc_id)
 384                 }
 385             }
 386         })?;
 387
 388         self.state.decoding_state[idx].with_lock(|entry| {
 389             *entry = State::Done(alloc_id);
 390         });
 391
 392         Ok(alloc_id)
 393     }
 394 }
 395
 396 impl fmt::Display for AllocId {
 397     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 398         write!(f, "{}", self.0)
 399     }
 400 }
 401
 402 #[derive(Debug, Clone, Eq, PartialEq, Hash, RustcDecodable, RustcEncodable)]
 403 pub enum AllocType<'tcx, M> {
 404     /// The alloc id is used as a function pointer
 405     Function(Instance<'tcx>),
 406     /// The alloc id points to a "lazy" static variable that did not get computed (yet).
 407     /// This is also used to break the cycle in recursive statics.
 408     Static(DefId),
 409     /// The alloc id points to memory
 410     Memory(M)
 411 }
 412
 413 pub struct AllocMap<'tcx, M> {
 414     /// Lets you know what an AllocId refers to
 415     id_to_type: FxHashMap<AllocId, AllocType<'tcx, M>>,
 416
 417     /// Used to ensure that functions and statics only get one associated AllocId
 418     type_interner: FxHashMap<AllocType<'tcx, M>, AllocId>,
 419
 420     /// The AllocId to assign to the next requested id.
 421     /// Always incremented, never gets smaller.
 422     next_id: AllocId,
 423 }
 424
 425 impl<'tcx, M: fmt::Debug + Eq + Hash + Clone> AllocMap<'tcx, M> {
 426     pub fn new() -> Self {
 427         AllocMap {
 428             id_to_type: FxHashMap(),
 429             type_interner: FxHashMap(),
 430             next_id: AllocId(0),
 431         }
 432     }
 433
 434     /// obtains a new allocation ID that can be referenced but does not
 435     /// yet have an allocation backing it.
 436     pub fn reserve(
 437         &mut self,
 438     ) -> AllocId {
 439         let next = self.next_id;
 440         self.next_id.0 = self.next_id.0
 441             .checked_add(1)
 442             .expect("You overflowed a u64 by incrementing by 1... \
 443                      You've just earned yourself a free drink if we ever meet. \
 444                      Seriously, how did you do that?!");
 445         next
 446     }
 447
 448     fn intern(&mut self, alloc_type: AllocType<'tcx, M>) -> AllocId {
 449         if let Some(&alloc_id) = self.type_interner.get(&alloc_type) {
 450             return alloc_id;
 451         }
 452         let id = self.reserve();
 453         debug!("creating alloc_type {:?} with id {}", alloc_type, id);
 454         self.id_to_type.insert(id, alloc_type.clone());
 455         self.type_interner.insert(alloc_type, id);
 456         id
 457     }
 458
 459     // FIXME: Check if functions have identity. If not, we should not intern these,
 460     // but instead create a new id per use.
 461     // Alternatively we could just make comparing function pointers an error.
 462     pub fn create_fn_alloc(&mut self, instance: Instance<'tcx>) -> AllocId {
 463         self.intern(AllocType::Function(instance))
 464     }
 465
 466     pub fn get(&self, id: AllocId) -> Option<AllocType<'tcx, M>> {
 467         self.id_to_type.get(&id).cloned()
 468     }
 469
 470     pub fn unwrap_memory(&self, id: AllocId) -> M {
 471         match self.get(id) {
 472             Some(AllocType::Memory(mem)) => mem,
 473             _ => bug!("expected allocation id {} to point to memory", id),
 474         }
 475     }
 476
 477     pub fn intern_static(&mut self, static_id: DefId) -> AllocId {
 478         self.intern(AllocType::Static(static_id))
 479     }
 480
 481     pub fn allocate(&mut self, mem: M) -> AllocId {
 482         let id = self.reserve();
 483         self.set_id_memory(id, mem);
 484         id
 485     }
 486
 487     pub fn set_id_memory(&mut self, id: AllocId, mem: M) {
 488         if let Some(old) = self.id_to_type.insert(id, AllocType::Memory(mem)) {
 489             bug!("tried to set allocation id {}, but it was already existing as {:#?}", id, old);
 490         }
 491     }
 492
 493     pub fn set_id_same_memory(&mut self, id: AllocId, mem: M) {
 494        self.id_to_type.insert_same(id, AllocType::Memory(mem));
 495     }
 496 }
 497
 498 #[derive(Clone, Debug, Eq, PartialEq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable)]
 499 pub struct Allocation {
 500     /// The actual bytes of the allocation.
 501     /// Note that the bytes of a pointer represent the offset of the pointer
 502     pub bytes: Vec<u8>,
 503     /// Maps from byte addresses to allocations.
 504     /// Only the first byte of a pointer is inserted into the map; i.e.,
 505     /// every entry in this map applies to `pointer_size` consecutive bytes starting
 506     /// at the given offset.
 507     pub relocations: Relocations,
 508     /// Denotes undefined memory. Reading from undefined memory is forbidden in miri
 509     pub undef_mask: UndefMask,
 510     /// The alignment of the allocation to detect unaligned reads.
 511     pub align: Align,
 512     /// Whether the allocation is mutable.
 513     /// Also used by codegen to determine if a static should be put into mutable memory,
 514     /// which happens for `static mut` and `static` with interior mutability.
 515     pub mutability: Mutability,
 516 }
 517
 518 impl Allocation {
 519     /// Creates a read-only allocation initialized by the given bytes
 520     pub fn from_bytes(slice: &[u8], align: Align) -> Self {
 521         let mut undef_mask = UndefMask::new(Size::ZERO);
 522         undef_mask.grow(Size::from_bytes(slice.len() as u64), true);
 523         Self {
 524             bytes: slice.to_owned(),
 525             relocations: Relocations::new(),
 526             undef_mask,
 527             align,
 528             mutability: Mutability::Immutable,
 529         }
 530     }
 531
 532     pub fn from_byte_aligned_bytes(slice: &[u8]) -> Self {
 533         Allocation::from_bytes(slice, Align::from_bytes(1, 1).unwrap())
 534     }
 535
 536     pub fn undef(size: Size, align: Align) -> Self {
 537         assert_eq!(size.bytes() as usize as u64, size.bytes());
 538         Allocation {
 539             bytes: vec![0; size.bytes() as usize],
 540             relocations: Relocations::new(),
 541             undef_mask: UndefMask::new(size),
 542             align,
 543             mutability: Mutability::Mutable,
 544         }
 545     }
 546 }
 547
 548 impl<'tcx> ::serialize::UseSpecializedDecodable for &'tcx Allocation {}
 549
 550 #[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, RustcEncodable, RustcDecodable)]
 551 pub struct Relocations<Id=AllocId>(SortedMap<Size, Id>);
 552
 553 impl<Id> Relocations<Id> {
 554     pub fn new() -> Self {
 555         Relocations(SortedMap::new())
 556     }
 557
 558     // The caller must guarantee that the given relocations are already sorted
 559     // by address and contain no duplicates.
 560     pub fn from_presorted(r: Vec<(Size, Id)>) -> Self {
 561         Relocations(SortedMap::from_presorted_elements(r))
 562     }
 563 }
 564
 565 impl Deref for Relocations {
 566     type Target = SortedMap<Size, AllocId>;
 567
 568     fn deref(&self) -> &Self::Target {
 569         &self.0
 570     }
 571 }
 572
 573 impl DerefMut for Relocations {
 574     fn deref_mut(&mut self) -> &mut Self::Target {
 575         &mut self.0
 576     }
 577 }
 578
 579 ////////////////////////////////////////////////////////////////////////////////
 580 // Methods to access integers in the target endianness
 581 ////////////////////////////////////////////////////////////////////////////////
 582
 583 pub fn write_target_uint(
 584     endianness: layout::Endian,
 585     mut target: &mut [u8],
 586     data: u128,
 587 ) -> Result<(), io::Error> {
 588     let len = target.len();
 589     match endianness {
 590         layout::Endian::Little => target.write_uint128::<LittleEndian>(data, len),
 591         layout::Endian::Big => target.write_uint128::<BigEndian>(data, len),
 592     }
 593 }
 594
 595 pub fn read_target_uint(endianness: layout::Endian, mut source: &[u8]) -> Result<u128, io::Error> {
 596     match endianness {
 597         layout::Endian::Little => source.read_uint128::<LittleEndian>(source.len()),
 598         layout::Endian::Big => source.read_uint128::<BigEndian>(source.len()),
 599     }
 600 }
 601
 602 ////////////////////////////////////////////////////////////////////////////////
 603 // Methods to faciliate working with signed integers stored in a u128
 604 ////////////////////////////////////////////////////////////////////////////////
 605
 606 pub fn sign_extend(value: u128, size: Size) -> u128 {
 607     let size = size.bits();
 608     // sign extend
 609     let shift = 128 - size;
 610     // shift the unsigned value to the left
 611     // and back to the right as signed (essentially fills with FF on the left)
 612     (((value << shift) as i128) >> shift) as u128
 613 }
 614
 615 pub fn truncate(value: u128, size: Size) -> u128 {
 616     let size = size.bits();
 617     let shift = 128 - size;
 618     // truncate (shift left to drop out leftover values, shift right to fill with zeroes)
 619     (value << shift) >> shift
 620 }
 621
 622 ////////////////////////////////////////////////////////////////////////////////
 623 // Undefined byte tracking
 624 ////////////////////////////////////////////////////////////////////////////////
 625
 626 type Block = u64;
 627 const BLOCK_SIZE: u64 = 64;
 628
 629 #[derive(Clone, Debug, Eq, PartialEq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable)]
 630 pub struct UndefMask {
 631     blocks: Vec<Block>,
 632     len: Size,
 633 }
 634
 635 impl_stable_hash_for!(struct mir::interpret::UndefMask{blocks, len});
 636
 637 impl UndefMask {
 638     pub fn new(size: Size) -> Self {
 639         let mut m = UndefMask {
 640             blocks: vec![],
 641             len: Size::ZERO,
 642         };
 643         m.grow(size, false);
 644         m
 645     }
 646
 647     /// Check whether the range `start..end` (end-exclusive) is entirely defined.
 648     ///
 649     /// Returns `Ok(())` if it's defined. Otherwise returns the index of the byte
 650     /// at which the first undefined access begins.
 651     #[inline]
 652     pub fn is_range_defined(&self, start: Size, end: Size) -> Result<(), Size> {
 653         if end > self.len {
 654             return Err(self.len);
 655         }
 656
 657         let idx = (start.bytes()..end.bytes())
 658             .map(|i| Size::from_bytes(i))
 659             .find(|&i| !self.get(i));
 660
 661         match idx {
 662             Some(idx) => Err(idx),
 663             None => Ok(())
 664         }
 665     }
 666
 667     pub fn set_range(&mut self, start: Size, end: Size, new_state: bool) {
 668         let len = self.len;
 669         if end > len {
 670             self.grow(end - len, new_state);
 671         }
 672         self.set_range_inbounds(start, end, new_state);
 673     }
 674
 675     pub fn set_range_inbounds(&mut self, start: Size, end: Size, new_state: bool) {
 676         for i in start.bytes()..end.bytes() {
 677             self.set(Size::from_bytes(i), new_state);
 678         }
 679     }
 680
 681     #[inline]
 682     pub fn get(&self, i: Size) -> bool {
 683         let (block, bit) = bit_index(i);
 684         (self.blocks[block] & 1 << bit) != 0
 685     }
 686
 687     #[inline]
 688     pub fn set(&mut self, i: Size, new_state: bool) {
 689         let (block, bit) = bit_index(i);
 690         if new_state {
 691             self.blocks[block] |= 1 << bit;
 692         } else {
 693             self.blocks[block] &= !(1 << bit);
 694         }
 695     }
 696
 697     pub fn grow(&mut self, amount: Size, new_state: bool) {
 698         let unused_trailing_bits = self.blocks.len() as u64 * BLOCK_SIZE - self.len.bytes();
 699         if amount.bytes() > unused_trailing_bits {
 700             let additional_blocks = amount.bytes() / BLOCK_SIZE + 1;
 701             assert_eq!(additional_blocks as usize as u64, additional_blocks);
 702             self.blocks.extend(
 703                 iter::repeat(0).take(additional_blocks as usize),
 704             );
 705         }
 706         let start = self.len;
 707         self.len += amount;
 708         self.set_range_inbounds(start, start + amount, new_state);
 709     }
 710 }
 711
 712 #[inline]
 713 fn bit_index(bits: Size) -> (usize, usize) {
 714     let bits = bits.bytes();
 715     let a = bits / BLOCK_SIZE;
 716     let b = bits % BLOCK_SIZE;
 717     assert_eq!(a as usize as u64, a);
 718     assert_eq!(b as usize as u64, b);
 719     (a as usize, b as usize)
 720 }