src/librustc_mir/interpret/lvalue.rs

   1 use rustc::hir::Mutability as TyMutability;
   2 use rustc::mir;
   3 use rustc::ty::layout::{Size, Align};
   4 use rustc::ty::{self, Ty, TypeAndMut};
   5 use rustc_data_structures::indexed_vec::Idx;
   6 use syntax::ast::Mutability;
   7
   8 use error::{EvalError, EvalResult};
   9 use eval_context::EvalContext;
  10 use memory::{MemoryPointer, AccessKind};
  11 use value::{PrimVal, Pointer, Value};
  12
  13 #[derive(Copy, Clone, Debug)]
  14 pub enum Lvalue<'tcx> {
  15     /// An lvalue referring to a value allocated in the `Memory` system.
  16     Ptr {
  17         /// An lvalue may have an invalid (integral or undef) pointer,
  18         /// since it might be turned back into a reference
  19         /// before ever being dereferenced.
  20         ptr: Pointer,
  21         extra: LvalueExtra,
  22         /// Remember whether this lvalue is *supposed* to be aligned.
  23         aligned: bool,
  24     },
  25
  26     /// An lvalue referring to a value on the stack. Represented by a stack frame index paired with
  27     /// a Mir local index.
  28     Local {
  29         frame: usize,
  30         local: mir::Local,
  31     },
  32
  33     /// An lvalue referring to a global
  34     Global(GlobalId<'tcx>),
  35 }
  36
  37 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
  38 pub enum LvalueExtra {
  39     None,
  40     Length(u64),
  41     Vtable(MemoryPointer),
  42     DowncastVariant(usize),
  43 }
  44
  45 /// Uniquely identifies a specific constant or static.
  46 #[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
  47 pub struct GlobalId<'tcx> {
  48     /// For a constant or static, the `Instance` of the item itself.
  49     /// For a promoted global, the `Instance` of the function they belong to.
  50     pub(super) instance: ty::Instance<'tcx>,
  51
  52     /// The index for promoted globals within their function's `Mir`.
  53     pub(super) promoted: Option<mir::Promoted>,
  54 }
  55
  56 #[derive(Clone, Debug)]
  57 pub struct Global<'tcx> {
  58     pub(super) value: Value,
  59     /// Only used in `force_allocation` to ensure we don't mark the memory
  60     /// before the static is initialized. It is possible to convert a
  61     /// global which initially is `Value::ByVal(PrimVal::Undef)` and gets
  62     /// lifted to an allocation before the static is fully initialized
  63     pub(super) initialized: bool,
  64     pub(super) mutable: Mutability,
  65     pub(super) ty: Ty<'tcx>,
  66 }
  67
  68 impl<'tcx> Lvalue<'tcx> {
  69     /// Produces an Lvalue that will error if attempted to be read from
  70     pub fn undef() -> Self {
  71         Self::from_primval_ptr(PrimVal::Undef.into())
  72     }
  73
  74     pub(crate) fn from_primval_ptr(ptr: Pointer) -> Self {
  75         Lvalue::Ptr { ptr, extra: LvalueExtra::None, aligned: true }
  76     }
  77
  78     pub(crate) fn from_ptr(ptr: MemoryPointer) -> Self {
  79         Self::from_primval_ptr(ptr.into())
  80     }
  81
  82     pub(super) fn to_ptr_extra_aligned(self) -> (Pointer, LvalueExtra, bool) {
  83         match self {
  84             Lvalue::Ptr { ptr, extra, aligned } => (ptr, extra, aligned),
  85             _ => bug!("to_ptr_and_extra: expected Lvalue::Ptr, got {:?}", self),
  86
  87         }
  88     }
  89
  90     pub(super) fn to_ptr(self) -> EvalResult<'tcx, MemoryPointer> {
  91         let (ptr, extra, _aligned) = self.to_ptr_extra_aligned();
  92         // At this point, we forget about the alignment information -- the lvalue has been turned into a reference,
  93         // and no matter where it came from, it now must be aligned.
  94         assert_eq!(extra, LvalueExtra::None);
  95         ptr.to_ptr()
  96     }
  97
  98     pub(super) fn elem_ty_and_len(self, ty: Ty<'tcx>) -> (Ty<'tcx>, u64) {
  99         match ty.sty {
 100             ty::TyArray(elem, n) => (elem, n as u64),
 101
 102             ty::TySlice(elem) => {
 103                 match self {
 104                     Lvalue::Ptr { extra: LvalueExtra::Length(len), .. } => (elem, len),
 105                     _ => bug!("elem_ty_and_len of a TySlice given non-slice lvalue: {:?}", self),
 106                 }
 107             }
 108
 109             _ => bug!("elem_ty_and_len expected array or slice, got {:?}", ty),
 110         }
 111     }
 112 }
 113
 114 impl<'tcx> Global<'tcx> {
 115     pub(super) fn uninitialized(ty: Ty<'tcx>) -> Self {
 116         Global {
 117             value: Value::ByVal(PrimVal::Undef),
 118             mutable: Mutability::Mutable,
 119             ty,
 120             initialized: false,
 121         }
 122     }
 123
 124     pub(super) fn initialized(ty: Ty<'tcx>, value: Value, mutable: Mutability) -> Self {
 125         Global {
 126             value,
 127             mutable,
 128             ty,
 129             initialized: true,
 130         }
 131     }
 132 }
 133
 134 impl<'a, 'tcx> EvalContext<'a, 'tcx> {
 135     /// Reads a value from the lvalue without going through the intermediate step of obtaining
 136     /// a `miri::Lvalue`
 137     pub fn try_read_lvalue(&mut self, lvalue: &mir::Lvalue<'tcx>) -> EvalResult<'tcx, Option<Value>> {
 138         use rustc::mir::Lvalue::*;
 139         match *lvalue {
 140             // Might allow this in the future, right now there's no way to do this from Rust code anyway
 141             Local(mir::RETURN_POINTER) => Err(EvalError::ReadFromReturnPointer),
 142             // Directly reading a local will always succeed
 143             Local(local) => self.frame().get_local(local).map(Some),
 144             // Directly reading a static will always succeed
 145             Static(ref static_) => {
 146                 let instance = ty::Instance::mono(self.tcx, static_.def_id);
 147                 let cid = GlobalId { instance, promoted: None };
 148                 Ok(Some(self.globals.get(&cid).expect("global not cached").value))
 149             },
 150             Projection(ref proj) => self.try_read_lvalue_projection(proj),
 151         }
 152     }
 153
 154     fn try_read_lvalue_projection(&mut self, proj: &mir::LvalueProjection<'tcx>) -> EvalResult<'tcx, Option<Value>> {
 155         use rustc::mir::ProjectionElem::*;
 156         let base = match self.try_read_lvalue(&proj.base)? {
 157             Some(base) => base,
 158             None => return Ok(None),
 159         };
 160         let base_ty = self.lvalue_ty(&proj.base);
 161         match proj.elem {
 162             Field(field, _) => match (field.index(), base) {
 163                 // the only field of a struct
 164                 (0, Value::ByVal(val)) => Ok(Some(Value::ByVal(val))),
 165                 // split fat pointers, 2 element tuples, ...
 166                 (0...1, Value::ByValPair(a, b)) if self.get_field_count(base_ty)? == 2 => {
 167                     let val = [a, b][field.index()];
 168                     Ok(Some(Value::ByVal(val)))
 169                 },
 170                 // the only field of a struct is a fat pointer
 171                 (0, Value::ByValPair(..)) => Ok(Some(base)),
 172                 _ => Ok(None),
 173             },
 174             // The NullablePointer cases should work fine, need to take care for normal enums
 175             Downcast(..) |
 176             Subslice { .. } |
 177             // reading index 0 or index 1 from a ByVal or ByVal pair could be optimized
 178             ConstantIndex { .. } | Index(_) |
 179             // No way to optimize this projection any better than the normal lvalue path
 180             Deref => Ok(None),
 181         }
 182     }
 183
 184     /// Returns a value and (in case of a ByRef) if we are supposed to use aligned accesses.
 185     pub(super) fn eval_and_read_lvalue(&mut self, lvalue: &mir::Lvalue<'tcx>) -> EvalResult<'tcx, Value> {
 186         // Shortcut for things like accessing a fat pointer's field,
 187         // which would otherwise (in the `eval_lvalue` path) require moving a `ByValPair` to memory
 188         // and returning an `Lvalue::Ptr` to it
 189         if let Some(val) = self.try_read_lvalue(lvalue)? {
 190             return Ok(val);
 191         }
 192         let lvalue = self.eval_lvalue(lvalue)?;
 193         self.read_lvalue(lvalue)
 194     }
 195
 196     pub fn read_lvalue(&self, lvalue: Lvalue<'tcx>) -> EvalResult<'tcx, Value> {
 197         match lvalue {
 198             Lvalue::Ptr { ptr, extra, aligned } => {
 199                 assert_eq!(extra, LvalueExtra::None);
 200                 Ok(Value::ByRef(ptr, aligned))
 201             }
 202             Lvalue::Local { frame, local } => {
 203                 self.stack[frame].get_local(local)
 204             }
 205             Lvalue::Global(cid) => {
 206                 Ok(self.globals.get(&cid).expect("global not cached").value)
 207             }
 208         }
 209     }
 210
 211     pub(super) fn eval_lvalue(&mut self, mir_lvalue: &mir::Lvalue<'tcx>) -> EvalResult<'tcx, Lvalue<'tcx>> {
 212         use rustc::mir::Lvalue::*;
 213         let lvalue = match *mir_lvalue {
 214             Local(mir::RETURN_POINTER) => self.frame().return_lvalue,
 215             Local(local) => Lvalue::Local { frame: self.cur_frame(), local },
 216
 217             Static(ref static_) => {
 218                 let instance = ty::Instance::mono(self.tcx, static_.def_id);
 219                 Lvalue::Global(GlobalId { instance, promoted: None })
 220             }
 221
 222             Projection(ref proj) => {
 223                 let ty = self.lvalue_ty(&proj.base);
 224                 let lvalue = self.eval_lvalue(&proj.base)?;
 225                 return self.eval_lvalue_projection(lvalue, ty, &proj.elem);
 226             }
 227         };
 228
 229         if log_enabled!(::log::LogLevel::Trace) {
 230             self.dump_local(lvalue);
 231         }
 232
 233         Ok(lvalue)
 234     }
 235
 236     pub fn lvalue_field(
 237         &mut self,
 238         base: Lvalue<'tcx>,
 239         field_index: usize,
 240         base_ty: Ty<'tcx>,
 241         field_ty: Ty<'tcx>,
 242     ) -> EvalResult<'tcx, Lvalue<'tcx>> {
 243         let base_layout = self.type_layout(base_ty)?;
 244         use rustc::ty::layout::Layout::*;
 245         let (offset, packed) = match *base_layout {
 246             Univariant { ref variant, .. } => {
 247                 (variant.offsets[field_index], variant.packed)
 248             },
 249
 250             General { ref variants, .. } => {
 251                 let (_, base_extra, _) = base.to_ptr_extra_aligned();
 252                 if let LvalueExtra::DowncastVariant(variant_idx) = base_extra {
 253                     // +1 for the discriminant, which is field 0
 254                     (variants[variant_idx].offsets[field_index + 1], variants[variant_idx].packed)
 255                 } else {
 256                     bug!("field access on enum had no variant index");
 257                 }
 258             }
 259
 260             RawNullablePointer { .. } => {
 261                 assert_eq!(field_index, 0);
 262                 return Ok(base);
 263             }
 264
 265             StructWrappedNullablePointer { ref nonnull, .. } => {
 266                 (nonnull.offsets[field_index], nonnull.packed)
 267             }
 268
 269             UntaggedUnion { .. } => return Ok(base),
 270
 271             Vector { element, count } => {
 272                 let field = field_index as u64;
 273                 assert!(field < count);
 274                 let elem_size = element.size(&self.tcx.data_layout).bytes();
 275                 (Size::from_bytes(field * elem_size), false)
 276             }
 277
 278             // We treat arrays + fixed sized indexing like field accesses
 279             Array { .. } => {
 280                 let field = field_index as u64;
 281                 let elem_size = match base_ty.sty {
 282                     ty::TyArray(elem_ty, n) => {
 283                         assert!(field < n as u64);
 284                         self.type_size(elem_ty)?.expect("array elements are sized") as u64
 285                     },
 286                     _ => bug!("lvalue_field: got Array layout but non-array type {:?}", base_ty),
 287                 };
 288                 (Size::from_bytes(field * elem_size), false)
 289             }
 290
 291             FatPointer { .. } => {
 292                 let bytes = field_index as u64 * self.memory.pointer_size();
 293                 let offset = Size::from_bytes(bytes);
 294                 (offset, false)
 295             }
 296
 297             _ => bug!("field access on non-product type: {:?}", base_layout),
 298         };
 299
 300         // Do not allocate in trivial cases
 301         let (base_ptr, base_extra, aligned) = match base {
 302             Lvalue::Ptr { ptr, extra, aligned } => (ptr, extra, aligned),
 303             Lvalue::Local { frame, local } => match self.stack[frame].get_local(local)? {
 304                 // in case the type has a single field, just return the value
 305                 Value::ByVal(_) if self.get_field_count(base_ty).map(|c| c == 1).unwrap_or(false) => {
 306                     assert_eq!(offset.bytes(), 0, "ByVal can only have 1 non zst field with offset 0");
 307                     return Ok(base);
 308                 },
 309                 Value::ByRef(..) |
 310                 Value::ByValPair(..) |
 311                 Value::ByVal(_) => self.force_allocation(base)?.to_ptr_extra_aligned(),
 312             },
 313             Lvalue::Global(cid) => match self.globals.get(&cid).expect("uncached global").value {
 314                 // in case the type has a single field, just return the value
 315                 Value::ByVal(_) if self.get_field_count(base_ty).map(|c| c == 1).unwrap_or(false) => {
 316                     assert_eq!(offset.bytes(), 0, "ByVal can only have 1 non zst field with offset 0");
 317                     return Ok(base);
 318                 },
 319                 Value::ByRef(..) |
 320                 Value::ByValPair(..) |
 321                 Value::ByVal(_) => self.force_allocation(base)?.to_ptr_extra_aligned(),
 322             },
 323         };
 324
 325         let offset = match base_extra {
 326             LvalueExtra::Vtable(tab) => {
 327                 let (_, align) = self.size_and_align_of_dst(base_ty, base_ptr.to_value_with_vtable(tab))?;
 328                 offset.abi_align(Align::from_bytes(align, align).unwrap()).bytes()
 329             }
 330             _ => offset.bytes(),
 331         };
 332
 333         let ptr = base_ptr.offset(offset, &self)?;
 334
 335         let field_ty = self.monomorphize(field_ty, self.substs());
 336
 337         let extra = if self.type_is_sized(field_ty) {
 338             LvalueExtra::None
 339         } else {
 340             match base_extra {
 341                 LvalueExtra::None => bug!("expected fat pointer"),
 342                 LvalueExtra::DowncastVariant(..) =>
 343                     bug!("Rust doesn't support unsized fields in enum variants"),
 344                 LvalueExtra::Vtable(_) |
 345                 LvalueExtra::Length(_) => {},
 346             }
 347             base_extra
 348         };
 349
 350         Ok(Lvalue::Ptr { ptr, extra, aligned: aligned && !packed })
 351     }
 352
 353     fn val_to_lvalue(&mut self, val: Value, ty: Ty<'tcx>) -> EvalResult<'tcx, Lvalue<'tcx>> {
 354         Ok(match self.tcx.struct_tail(ty).sty {
 355             ty::TyDynamic(..) => {
 356                 let (ptr, vtable) = val.into_ptr_vtable_pair(&mut self.memory)?;
 357                 Lvalue::Ptr { ptr, extra: LvalueExtra::Vtable(vtable), aligned: true }
 358             },
 359             ty::TyStr | ty::TySlice(_) => {
 360                 let (ptr, len) = val.into_slice(&mut self.memory)?;
 361                 Lvalue::Ptr { ptr, extra: LvalueExtra::Length(len), aligned: true }
 362             },
 363             _ => Lvalue::Ptr { ptr: val.into_ptr(&mut self.memory)?, extra: LvalueExtra::None, aligned: true },
 364         })
 365     }
 366
 367     fn lvalue_index(&mut self, base: Lvalue<'tcx>, outer_ty: Ty<'tcx>, n: u64) -> EvalResult<'tcx, Lvalue<'tcx>> {
 368         // Taking the outer type here may seem odd; it's needed because for array types, the outer type gives away the length.
 369         let base = self.force_allocation(base)?;
 370         let (base_ptr, _, aligned) = base.to_ptr_extra_aligned();
 371
 372         let (elem_ty, len) = base.elem_ty_and_len(outer_ty);
 373         let elem_size = self.type_size(elem_ty)?.expect("slice element must be sized");
 374         assert!(n < len, "Tried to access element {} of array/slice with length {}", n, len);
 375         let ptr = base_ptr.offset(n * elem_size, self.memory.layout)?;
 376         Ok(Lvalue::Ptr { ptr, extra: LvalueExtra::None, aligned })
 377     }
 378
 379     fn eval_lvalue_projection(
 380         &mut self,
 381         base: Lvalue<'tcx>,
 382         base_ty: Ty<'tcx>,
 383         proj_elem: &mir::ProjectionElem<'tcx, mir::Operand<'tcx>>,
 384     ) -> EvalResult<'tcx, Lvalue<'tcx>> {
 385         use rustc::mir::ProjectionElem::*;
 386         let (ptr, extra, aligned) = match *proj_elem {
 387             Field(field, field_ty) => {
 388                 return self.lvalue_field(base, field.index(), base_ty, field_ty);
 389             }
 390
 391             Downcast(_, variant) => {
 392                 let base_layout = self.type_layout(base_ty)?;
 393                 // FIXME(solson)
 394                 let base = self.force_allocation(base)?;
 395                 let (base_ptr, base_extra, aligned) = base.to_ptr_extra_aligned();
 396
 397                 use rustc::ty::layout::Layout::*;
 398                 let extra = match *base_layout {
 399                     General { .. } => LvalueExtra::DowncastVariant(variant),
 400                     RawNullablePointer { .. } | StructWrappedNullablePointer { .. } => base_extra,
 401                     _ => bug!("variant downcast on non-aggregate: {:?}", base_layout),
 402                 };
 403                 (base_ptr, extra, aligned)
 404             }
 405
 406             Deref => {
 407                 let val = self.read_lvalue(base)?;
 408
 409                 let pointee_type = match base_ty.sty {
 410                     ty::TyRawPtr(ref tam) |
 411                     ty::TyRef(_, ref tam) => tam.ty,
 412                     ty::TyAdt(def, _) if def.is_box() => base_ty.boxed_ty(),
 413                     _ => bug!("can only deref pointer types"),
 414                 };
 415
 416                 trace!("deref to {} on {:?}", pointee_type, val);
 417
 418                 return self.val_to_lvalue(val, pointee_type);
 419             }
 420
 421             Index(ref operand) => {
 422                 // FIXME(solson)
 423                 let n_ptr = self.eval_operand(operand)?;
 424                 let usize = self.tcx.types.usize;
 425                 let n = self.value_to_primval(n_ptr, usize)?.to_u64()?;
 426                 return self.lvalue_index(base, base_ty, n);
 427             }
 428
 429             ConstantIndex { offset, min_length, from_end } => {
 430                 // FIXME(solson)
 431                 let base = self.force_allocation(base)?;
 432                 let (base_ptr, _, aligned) = base.to_ptr_extra_aligned();
 433
 434                 let (elem_ty, n) = base.elem_ty_and_len(base_ty);
 435                 let elem_size = self.type_size(elem_ty)?.expect("sequence element must be sized");
 436                 assert!(n >= min_length as u64);
 437
 438                 let index = if from_end {
 439                     n - u64::from(offset)
 440                 } else {
 441                     u64::from(offset)
 442                 };
 443
 444                 let ptr = base_ptr.offset(index * elem_size, &self)?;
 445                 (ptr, LvalueExtra::None, aligned)
 446             }
 447
 448             Subslice { from, to } => {
 449                 // FIXME(solson)
 450                 let base = self.force_allocation(base)?;
 451                 let (base_ptr, _, aligned) = base.to_ptr_extra_aligned();
 452
 453                 let (elem_ty, n) = base.elem_ty_and_len(base_ty);
 454                 let elem_size = self.type_size(elem_ty)?.expect("slice element must be sized");
 455                 assert!(u64::from(from) <= n - u64::from(to));
 456                 let ptr = base_ptr.offset(u64::from(from) * elem_size, &self)?;
 457                 let extra = LvalueExtra::Length(n - u64::from(to) - u64::from(from));
 458                 (ptr, extra, aligned)
 459             }
 460         };
 461
 462         Ok(Lvalue::Ptr { ptr, extra, aligned })
 463     }
 464
 465     pub(super) fn lvalue_ty(&self, lvalue: &mir::Lvalue<'tcx>) -> Ty<'tcx> {
 466         self.monomorphize(lvalue.ty(self.mir(), self.tcx).to_ty(self.tcx), self.substs())
 467     }
 468 }
 469
 470 // Validity checks
 471 impl<'a, 'tcx> EvalContext<'a, 'tcx> {
 472     pub(super) fn acquire_valid(&mut self, lvalue: Lvalue<'tcx>, ty: Ty<'tcx>, outer_mutbl: TyMutability) -> EvalResult<'tcx> {
 473         use rustc::ty::TypeVariants::*;
 474         use rustc::ty::RegionKind::*;
 475         use self::TyMutability::*;
 476
 477         trace!("Validating {:?} at type {}, outer mutability {:?}", lvalue, ty, outer_mutbl);
 478         match ty.sty {
 479             TyChar | TyInt(_) | TyUint(_) | TyRawPtr(_) => {
 480                 // TODO: Make sure these are not undef.
 481                 // We could do a bounds-check and other sanity checks on the lvalue, but it would be a bug in miri for this to ever fail.
 482                 Ok(())
 483             }
 484             TyBool | TyFloat(_) | TyStr => {
 485                 // TODO: Check if these are valid bool/float/UTF-8, respectively (and in particular, not undef).
 486                 Ok(())
 487             }
 488             TyRef(region, TypeAndMut { ty: pointee_ty, mutbl }) => {
 489                 // Acquire lock
 490                 let val = self.read_lvalue(lvalue)?;
 491                 let (len, _) = self.size_and_align_of_dst(pointee_ty, val)?;
 492                 let ptr = val.into_ptr(&mut self.memory)?.to_ptr()?;
 493                 let combined_mutbl = match outer_mutbl { MutMutable => mutbl, MutImmutable => MutImmutable };
 494                 let access = match combined_mutbl { MutMutable => AccessKind::Write, MutImmutable => AccessKind::Read };
 495                 let region = match *region {
 496                     ReScope(extent) => Some(extent),
 497                     _ => None,
 498                 };
 499                 self.memory.acquire_lock(ptr, len, region, access)?;
 500
 501                 // Recurse
 502                 let pointee_lvalue = self.val_to_lvalue(val, pointee_ty)?;
 503                 self.acquire_valid(pointee_lvalue, pointee_ty, combined_mutbl)
 504             }
 505             TySlice(elem_ty) => {
 506                 let len = match lvalue {
 507                     Lvalue::Ptr { extra: LvalueExtra::Length(len), .. } => len,
 508                     _ => bug!("acquire_valid of a TySlice given non-slice lvalue: {:?}", lvalue),
 509                 };
 510                 for i in 0..len {
 511                     let inner_lvalue = self.lvalue_index(lvalue, ty, i)?;
 512                     self.acquire_valid(inner_lvalue, elem_ty, outer_mutbl)?;
 513                 }
 514                 Ok(())
 515             }
 516             TyFnPtr(_sig) => {
 517                 // TODO: The function names here could need some improvement.
 518                 let ptr = self.read_lvalue(lvalue)?.into_ptr(&mut self.memory)?.to_ptr()?;
 519                 self.memory.get_fn(ptr)?;
 520                 // TODO: Check if the signature matches (should be the same check as what terminator/mod.rs already does on call?).
 521                 Ok(())
 522             }
 523             _ => unimplemented!("Unimplemented type encountered when checking validity.")
 524         }
 525     }
 526 }