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()) };
23 pub use self::error::{
24 EvalError, EvalResult, EvalErrorKind, AssertMessage, ConstEvalErr, struct_error,
25 FrameInfo, ConstEvalRawResult, ConstEvalResult, ErrorHandled,
28 pub use self::value::{Scalar, ScalarMaybeUndef, RawConst, ConstValue};
30 pub use self::allocation::{
31 InboundsCheck, Allocation, AllocationExtra,
32 Relocations, UndefMask,
35 pub use self::pointer::{Pointer, PointerArithmetic};
39 use hir::def_id::DefId;
40 use ty::{self, TyCtxt, Instance};
41 use ty::layout::{self, Size};
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;
53 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
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>),
62 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
63 pub struct DynamicLifetime {
65 pub region: Option<region::Scope>, // "None" indicates "until the function ends"
68 #[derive(Copy, Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable)]
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>,
81 /// The index for promoted globals within their function's `Mir`.
82 pub promoted: Option<mir::Promoted>,
85 #[derive(Copy, Clone, Eq, Hash, Ord, PartialEq, PartialOrd, Debug)]
86 pub struct AllocId(pub u64);
88 impl ::rustc_serialize::UseSpecializedEncodable for AllocId {}
89 impl ::rustc_serialize::UseSpecializedDecodable for AllocId {}
91 #[derive(RustcDecodable, RustcEncodable)]
98 pub fn specialized_encode_alloc_id<
103 tcx: TyCtxt<'a, 'tcx, 'tcx>,
105 ) -> Result<(), E::Error> {
106 let alloc_type: AllocType<'tcx> =
107 tcx.alloc_map.lock().get(alloc_id).expect("no value for AllocId");
109 AllocType::Memory(alloc) => {
110 trace!("encoding {:?} with {:#?}", alloc_id, alloc);
111 AllocKind::Alloc.encode(encoder)?;
112 alloc.encode(encoder)?;
114 AllocType::Function(fn_instance) => {
115 trace!("encoding {:?} with {:#?}", alloc_id, fn_instance);
116 AllocKind::Fn.encode(encoder)?;
117 fn_instance.encode(encoder)?;
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)?;
129 // Used to avoid infinite recursion when decoding cyclic allocations.
130 type DecodingSessionId = NonZeroU32;
135 InProgressNonAlloc(TinyList<DecodingSessionId>),
136 InProgress(TinyList<DecodingSessionId>, AllocId),
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>,
147 impl AllocDecodingState {
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);
153 // Make sure this is never zero
154 let session_id = DecodingSessionId::new((counter & 0x7FFFFFFF) + 1).unwrap();
156 AllocDecodingSession {
162 pub fn new(data_offsets: Vec<u32>) -> AllocDecodingState {
163 let decoding_state = vec![Mutex::new(State::Empty); data_offsets.len()];
172 #[derive(Copy, Clone)]
173 pub struct AllocDecodingSession<'s> {
174 state: &'s AllocDecodingState,
175 session_id: DecodingSessionId,
178 impl<'s> AllocDecodingSession<'s> {
180 // Decodes an AllocId in a thread-safe way.
181 pub fn decode_alloc_id<'a, 'tcx, D>(&self,
183 -> Result<AllocId, D::Error>
184 where D: TyDecoder<'a, 'tcx>,
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;
191 // Decode the AllocKind now so that we know if we have to reserve an
193 let (alloc_kind, pos) = decoder.with_position(pos, |decoder| {
194 let alloc_kind = AllocKind::decode(decoder)?;
195 Ok((alloc_kind, decoder.position()))
198 // Check the decoding state, see if it's already decoded or if we should
201 let mut entry = self.state.decoding_state[idx].lock();
204 State::Done(alloc_id) => {
207 ref mut entry @ State::Empty => {
208 // We are allowed to decode
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),
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));
228 State::InProgressNonAlloc(ref mut sessions) => {
229 if sessions.contains(&self.session_id) {
230 bug!("This should be unreachable")
232 // Start decoding concurrently
233 sessions.insert(self.session_id);
237 State::InProgress(ref mut sessions, alloc_id) => {
238 if sessions.contains(&self.session_id) {
242 // Start decoding concurrently
243 sessions.insert(self.session_id);
250 // Now decode the actual data
251 let alloc_id = decoder.with_position(pos, |decoder| {
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);
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);
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);
279 self.state.decoding_state[idx].with_lock(|entry| {
280 *entry = State::Done(alloc_id);
287 impl fmt::Display for AllocId {
288 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
289 write!(f, "{}", self.0)
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.
300 /// The alloc id points to memory
301 Memory(&'tcx Allocation),
304 pub struct AllocMap<'tcx> {
305 /// Lets you know what an AllocId refers to
306 id_to_type: FxHashMap<AllocId, AllocType<'tcx>>,
308 /// Used to ensure that statics only get one associated AllocId
309 type_interner: FxHashMap<AllocType<'tcx>, AllocId>,
311 /// The AllocId to assign to the next requested id.
312 /// Always incremented, never gets smaller.
316 impl<'tcx> AllocMap<'tcx> {
317 pub fn new() -> Self {
319 id_to_type: Default::default(),
320 type_interner: Default::default(),
325 /// obtains a new allocation ID that can be referenced but does not
326 /// yet have an allocation backing it.
330 let next = self.next_id;
331 self.next_id.0 = self.next_id.0
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?!");
339 fn intern(&mut self, alloc_type: AllocType<'tcx>) -> AllocId {
340 if let Some(&alloc_id) = self.type_interner.get(&alloc_type) {
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);
350 /// Functions cannot be identified by pointers, as asm-equal functions can get deduplicated
351 /// by the linker and functions can be duplicated across crates.
352 /// We thus generate a new `AllocId` for every mention of a function. This means that
353 /// `main as fn() == main as fn()` is false, while `let x = main as fn(); x == x` is true.
354 pub fn create_fn_alloc(&mut self, instance: Instance<'tcx>) -> AllocId {
355 let id = self.reserve();
356 self.id_to_type.insert(id, AllocType::Function(instance));
360 pub fn get(&self, id: AllocId) -> Option<AllocType<'tcx>> {
361 self.id_to_type.get(&id).cloned()
364 pub fn unwrap_memory(&self, id: AllocId) -> &'tcx Allocation {
366 Some(AllocType::Memory(mem)) => mem,
367 _ => bug!("expected allocation id {} to point to memory", id),
371 pub fn intern_static(&mut self, static_id: DefId) -> AllocId {
372 self.intern(AllocType::Static(static_id))
375 pub fn allocate(&mut self, mem: &'tcx Allocation) -> AllocId {
376 let id = self.reserve();
377 self.set_id_memory(id, mem);
381 pub fn set_id_memory(&mut self, id: AllocId, mem: &'tcx Allocation) {
382 if let Some(old) = self.id_to_type.insert(id, AllocType::Memory(mem)) {
383 bug!("tried to set allocation id {}, but it was already existing as {:#?}", id, old);
387 pub fn set_id_same_memory(&mut self, id: AllocId, mem: &'tcx Allocation) {
388 self.id_to_type.insert_same(id, AllocType::Memory(mem));
392 ////////////////////////////////////////////////////////////////////////////////
393 // Methods to access integers in the target endianness
394 ////////////////////////////////////////////////////////////////////////////////
396 pub fn write_target_uint(
397 endianness: layout::Endian,
398 mut target: &mut [u8],
400 ) -> Result<(), io::Error> {
401 let len = target.len();
403 layout::Endian::Little => target.write_uint128::<LittleEndian>(data, len),
404 layout::Endian::Big => target.write_uint128::<BigEndian>(data, len),
408 pub fn read_target_uint(endianness: layout::Endian, mut source: &[u8]) -> Result<u128, io::Error> {
410 layout::Endian::Little => source.read_uint128::<LittleEndian>(source.len()),
411 layout::Endian::Big => source.read_uint128::<BigEndian>(source.len()),
415 ////////////////////////////////////////////////////////////////////////////////
416 // Methods to facilitate working with signed integers stored in a u128
417 ////////////////////////////////////////////////////////////////////////////////
419 pub fn sign_extend(value: u128, size: Size) -> u128 {
420 let size = size.bits();
422 let shift = 128 - size;
423 // shift the unsigned value to the left
424 // and back to the right as signed (essentially fills with FF on the left)
425 (((value << shift) as i128) >> shift) as u128
428 pub fn truncate(value: u128, size: Size) -> u128 {
429 let size = size.bits();
430 let shift = 128 - size;
431 // truncate (shift left to drop out leftover values, shift right to fill with zeroes)
432 (value << shift) >> shift