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.
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.
11 //! An interpreter for MIR used in CTFE and by miri
15 ($($tt:tt)*) => { Err($crate::mir::interpret::EvalErrorKind::$($tt)*.into()) };
21 pub use self::error::{
22 EvalError, EvalResult, EvalErrorKind, AssertMessage, ConstEvalErr, struct_error,
23 FrameInfo, ConstEvalResult,
26 pub use self::value::{Scalar, ConstValue, ScalarMaybeUndef};
30 use hir::def_id::DefId;
31 use ty::{self, TyCtxt, Instance};
32 use ty::layout::{self, Align, HasDataLayout, Size};
36 use std::ops::{Deref, DerefMut};
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;
49 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
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>),
58 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
59 pub struct DynamicLifetime {
61 pub region: Option<region::Scope>, // "None" indicates "until the function ends"
64 #[derive(Copy, Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable)]
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>,
77 /// The index for promoted globals within their function's `Mir`.
78 pub promoted: Option<mir::Promoted>,
81 ////////////////////////////////////////////////////////////////////////////////
83 ////////////////////////////////////////////////////////////////////////////////
85 pub trait PointerArithmetic: layout::HasDataLayout {
86 // These are not supposed to be overridden.
89 fn pointer_size(self) -> Size {
90 self.data_layout().pointer_size
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)
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?
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)
108 self.overflowing_offset(val, i as u64)
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)
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) }
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) }
128 fn wrapping_signed_offset(self, val: u64, i: i64) -> u64 {
129 self.overflowing_signed_offset(val, i as i128).0
133 impl<T: layout::HasDataLayout> PointerArithmetic for T {}
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
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> {
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)
155 pub fn new(alloc_id: AllocId, offset: Size) -> Self {
156 Pointer { alloc_id, offset }
159 pub fn wrapping_signed_offset<C: HasDataLayout>(self, i: i64, cx: C) -> Self {
162 Size::from_bytes(cx.data_layout().wrapping_signed_offset(self.offset.bytes(), i)),
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)
171 pub fn signed_offset<C: HasDataLayout>(self, i: i64, cx: C) -> EvalResult<'tcx, Self> {
174 Size::from_bytes(cx.data_layout().signed_offset(self.offset.bytes(), i)?),
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)
183 pub fn offset<C: HasDataLayout>(self, i: Size, cx: C) -> EvalResult<'tcx, Self> {
186 Size::from_bytes(cx.data_layout().offset(self.offset.bytes(), i.bytes())?),
192 #[derive(Copy, Clone, Eq, Hash, Ord, PartialEq, PartialOrd, Debug)]
193 pub struct AllocId(pub u64);
195 impl ::rustc_serialize::UseSpecializedEncodable for AllocId {}
196 impl ::rustc_serialize::UseSpecializedDecodable for AllocId {}
198 #[derive(RustcDecodable, RustcEncodable)]
205 pub fn specialized_encode_alloc_id<
210 tcx: TyCtxt<'a, 'tcx, 'tcx>,
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");
216 AllocType::Memory(alloc) => {
217 trace!("encoding {:?} with {:#?}", alloc_id, alloc);
218 AllocKind::Alloc.encode(encoder)?;
219 alloc.encode(encoder)?;
221 AllocType::Function(fn_instance) => {
222 trace!("encoding {:?} with {:#?}", alloc_id, fn_instance);
223 AllocKind::Fn.encode(encoder)?;
224 fn_instance.encode(encoder)?;
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)?;
236 // Used to avoid infinite recursion when decoding cyclic allocations.
237 type DecodingSessionId = NonZeroU32;
242 InProgressNonAlloc(TinyList<DecodingSessionId>),
243 InProgress(TinyList<DecodingSessionId>, AllocId),
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>,
254 impl AllocDecodingState {
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);
260 // Make sure this is never zero
261 let session_id = DecodingSessionId::new((counter & 0x7FFFFFFF) + 1).unwrap();
263 AllocDecodingSession {
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())
275 decoding_state: decoding_state,
281 #[derive(Copy, Clone)]
282 pub struct AllocDecodingSession<'s> {
283 state: &'s AllocDecodingState,
284 session_id: DecodingSessionId,
287 impl<'s> AllocDecodingSession<'s> {
289 // Decodes an AllocId in a thread-safe way.
290 pub fn decode_alloc_id<'a, 'tcx, D>(&self,
292 -> Result<AllocId, D::Error>
293 where D: TyDecoder<'a, 'tcx>,
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;
300 // Decode the AllocKind now so that we know if we have to reserve an
302 let (alloc_kind, pos) = decoder.with_position(pos, |decoder| {
303 let alloc_kind = AllocKind::decode(decoder)?;
304 Ok((alloc_kind, decoder.position()))
307 // Check the decoding state, see if it's already decoded or if we should
310 let mut entry = self.state.decoding_state[idx].lock();
313 State::Done(alloc_id) => {
316 ref mut entry @ State::Empty => {
317 // We are allowed to decode
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),
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));
337 State::InProgressNonAlloc(ref mut sessions) => {
338 if sessions.contains(&self.session_id) {
339 bug!("This should be unreachable")
341 // Start decoding concurrently
342 sessions.insert(self.session_id);
346 State::InProgress(ref mut sessions, alloc_id) => {
347 if sessions.contains(&self.session_id) {
351 // Start decoding concurrently
352 sessions.insert(self.session_id);
359 // Now decode the actual data
360 let alloc_id = decoder.with_position(pos, |decoder| {
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);
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);
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);
388 self.state.decoding_state[idx].with_lock(|entry| {
389 *entry = State::Done(alloc_id);
396 impl fmt::Display for AllocId {
397 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
398 write!(f, "{}", self.0)
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.
409 /// The alloc id points to memory
413 pub struct AllocMap<'tcx, M> {
414 /// Lets you know what an AllocId refers to
415 id_to_type: FxHashMap<AllocId, AllocType<'tcx, M>>,
417 /// Used to ensure that functions and statics only get one associated AllocId
418 type_interner: FxHashMap<AllocType<'tcx, M>, AllocId>,
420 /// The AllocId to assign to the next requested id.
421 /// Always incremented, never gets smaller.
425 impl<'tcx, M: fmt::Debug + Eq + Hash + Clone> AllocMap<'tcx, M> {
426 pub fn new() -> Self {
428 id_to_type: FxHashMap(),
429 type_interner: FxHashMap(),
434 /// obtains a new allocation ID that can be referenced but does not
435 /// yet have an allocation backing it.
439 let next = self.next_id;
440 self.next_id.0 = self.next_id.0
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?!");
448 fn intern(&mut self, alloc_type: AllocType<'tcx, M>) -> AllocId {
449 if let Some(&alloc_id) = self.type_interner.get(&alloc_type) {
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);
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))
466 pub fn get(&self, id: AllocId) -> Option<AllocType<'tcx, M>> {
467 self.id_to_type.get(&id).cloned()
470 pub fn unwrap_memory(&self, id: AllocId) -> M {
472 Some(AllocType::Memory(mem)) => mem,
473 _ => bug!("expected allocation id {} to point to memory", id),
477 pub fn intern_static(&mut self, static_id: DefId) -> AllocId {
478 self.intern(AllocType::Static(static_id))
481 pub fn allocate(&mut self, mem: M) -> AllocId {
482 let id = self.reserve();
483 self.set_id_memory(id, mem);
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);
493 pub fn set_id_same_memory(&mut self, id: AllocId, mem: M) {
494 self.id_to_type.insert_same(id, AllocType::Memory(mem));
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
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.
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,
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);
524 bytes: slice.to_owned(),
525 relocations: Relocations::new(),
528 mutability: Mutability::Immutable,
532 pub fn from_byte_aligned_bytes(slice: &[u8]) -> Self {
533 Allocation::from_bytes(slice, Align::from_bytes(1, 1).unwrap())
536 pub fn undef(size: Size, align: Align) -> Self {
537 assert_eq!(size.bytes() as usize as u64, size.bytes());
539 bytes: vec![0; size.bytes() as usize],
540 relocations: Relocations::new(),
541 undef_mask: UndefMask::new(size),
543 mutability: Mutability::Mutable,
548 impl<'tcx> ::serialize::UseSpecializedDecodable for &'tcx Allocation {}
550 #[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, RustcEncodable, RustcDecodable)]
551 pub struct Relocations<Id=AllocId>(SortedMap<Size, Id>);
553 impl<Id> Relocations<Id> {
554 pub fn new() -> Self {
555 Relocations(SortedMap::new())
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))
565 impl Deref for Relocations {
566 type Target = SortedMap<Size, AllocId>;
568 fn deref(&self) -> &Self::Target {
573 impl DerefMut for Relocations {
574 fn deref_mut(&mut self) -> &mut Self::Target {
579 ////////////////////////////////////////////////////////////////////////////////
580 // Methods to access integers in the target endianness
581 ////////////////////////////////////////////////////////////////////////////////
583 pub fn write_target_uint(
584 endianness: layout::Endian,
585 mut target: &mut [u8],
587 ) -> Result<(), io::Error> {
588 let len = target.len();
590 layout::Endian::Little => target.write_uint128::<LittleEndian>(data, len),
591 layout::Endian::Big => target.write_uint128::<BigEndian>(data, len),
595 pub fn read_target_uint(endianness: layout::Endian, mut source: &[u8]) -> Result<u128, io::Error> {
597 layout::Endian::Little => source.read_uint128::<LittleEndian>(source.len()),
598 layout::Endian::Big => source.read_uint128::<BigEndian>(source.len()),
602 ////////////////////////////////////////////////////////////////////////////////
603 // Methods to faciliate working with signed integers stored in a u128
604 ////////////////////////////////////////////////////////////////////////////////
606 pub fn sign_extend(value: u128, size: Size) -> u128 {
607 let size = size.bits();
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
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
622 ////////////////////////////////////////////////////////////////////////////////
623 // Undefined byte tracking
624 ////////////////////////////////////////////////////////////////////////////////
627 const BLOCK_SIZE: u64 = 64;
629 #[derive(Clone, Debug, Eq, PartialEq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable)]
630 pub struct UndefMask {
635 impl_stable_hash_for!(struct mir::interpret::UndefMask{blocks, len});
638 pub fn new(size: Size) -> Self {
639 let mut m = UndefMask {
647 /// Check whether the range `start..end` (end-exclusive) is entirely defined.
649 /// Returns `Ok(())` if it's defined. Otherwise returns the index of the byte
650 /// at which the first undefined access begins.
652 pub fn is_range_defined(&self, start: Size, end: Size) -> Result<(), Size> {
654 return Err(self.len);
657 let idx = (start.bytes()..end.bytes())
658 .map(|i| Size::from_bytes(i))
659 .find(|&i| !self.get(i));
662 Some(idx) => Err(idx),
667 pub fn set_range(&mut self, start: Size, end: Size, new_state: bool) {
670 self.grow(end - len, new_state);
672 self.set_range_inbounds(start, end, new_state);
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);
682 pub fn get(&self, i: Size) -> bool {
683 let (block, bit) = bit_index(i);
684 (self.blocks[block] & 1 << bit) != 0
688 pub fn set(&mut self, i: Size, new_state: bool) {
689 let (block, bit) = bit_index(i);
691 self.blocks[block] |= 1 << bit;
693 self.blocks[block] &= !(1 << bit);
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);
703 iter::repeat(0).take(additional_blocks as usize),
706 let start = self.len;
708 self.set_range_inbounds(start, start + amount, new_state);
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)