compiler/rustc_mir/src/const_eval/machine.rs

   1 use rustc_middle::mir;
   2 use rustc_middle::ty::{self, Ty};
   3 use std::borrow::Borrow;
   4 use std::collections::hash_map::Entry;
   5 use std::hash::Hash;
   6
   7 use rustc_data_structures::fx::FxHashMap;
   8 use std::fmt;
   9
  10 use rustc_ast::Mutability;
  11 use rustc_hir::def_id::DefId;
  12 use rustc_middle::mir::AssertMessage;
  13 use rustc_session::Limit;
  14 use rustc_span::symbol::{sym, Symbol};
  15 use rustc_target::abi::{Align, Size};
  16 use rustc_target::spec::abi::Abi;
  17
  18 use crate::interpret::{
  19     self, compile_time_machine, AllocId, Allocation, Frame, ImmTy, InterpCx, InterpResult, Memory,
  20     OpTy, PlaceTy, Pointer, Scalar, StackPopUnwind,
  21 };
  22
  23 use super::error::*;
  24
  25 impl<'mir, 'tcx> InterpCx<'mir, 'tcx, CompileTimeInterpreter<'mir, 'tcx>> {
  26     /// "Intercept" a function call to a panic-related function
  27     /// because we have something special to do for it.
  28     /// If this returns successfully (`Ok`), the function should just be evaluated normally.
  29     fn hook_panic_fn(
  30         &mut self,
  31         instance: ty::Instance<'tcx>,
  32         args: &[OpTy<'tcx>],
  33     ) -> InterpResult<'tcx> {
  34         let def_id = instance.def_id();
  35         if Some(def_id) == self.tcx.lang_items().panic_fn()
  36             || Some(def_id) == self.tcx.lang_items().panic_str()
  37             || Some(def_id) == self.tcx.lang_items().begin_panic_fn()
  38         {
  39             // &str
  40             assert!(args.len() == 1);
  41
  42             let msg_place = self.deref_operand(&args[0])?;
  43             let msg = Symbol::intern(self.read_str(&msg_place)?);
  44             let span = self.find_closest_untracked_caller_location();
  45             let (file, line, col) = self.location_triple_for_span(span);
  46             Err(ConstEvalErrKind::Panic { msg, file, line, col }.into())
  47         } else {
  48             Ok(())
  49         }
  50     }
  51 }
  52
  53 /// Extra machine state for CTFE, and the Machine instance
  54 pub struct CompileTimeInterpreter<'mir, 'tcx> {
  55     /// For now, the number of terminators that can be evaluated before we throw a resource
  56     /// exhaustion error.
  57     ///
  58     /// Setting this to `0` disables the limit and allows the interpreter to run forever.
  59     pub steps_remaining: usize,
  60
  61     /// The virtual call stack.
  62     pub(crate) stack: Vec<Frame<'mir, 'tcx, (), ()>>,
  63 }
  64
  65 #[derive(Copy, Clone, Debug)]
  66 pub struct MemoryExtra {
  67     /// We need to make sure consts never point to anything mutable, even recursively. That is
  68     /// relied on for pattern matching on consts with references.
  69     /// To achieve this, two pieces have to work together:
  70     /// * Interning makes everything outside of statics immutable.
  71     /// * Pointers to allocations inside of statics can never leak outside, to a non-static global.
  72     /// This boolean here controls the second part.
  73     pub(super) can_access_statics: bool,
  74 }
  75
  76 impl<'mir, 'tcx> CompileTimeInterpreter<'mir, 'tcx> {
  77     pub(super) fn new(const_eval_limit: Limit) -> Self {
  78         CompileTimeInterpreter { steps_remaining: const_eval_limit.0, stack: Vec::new() }
  79     }
  80 }
  81
  82 impl<K: Hash + Eq, V> interpret::AllocMap<K, V> for FxHashMap<K, V> {
  83     #[inline(always)]
  84     fn contains_key<Q: ?Sized + Hash + Eq>(&mut self, k: &Q) -> bool
  85     where
  86         K: Borrow<Q>,
  87     {
  88         FxHashMap::contains_key(self, k)
  89     }
  90
  91     #[inline(always)]
  92     fn insert(&mut self, k: K, v: V) -> Option<V> {
  93         FxHashMap::insert(self, k, v)
  94     }
  95
  96     #[inline(always)]
  97     fn remove<Q: ?Sized + Hash + Eq>(&mut self, k: &Q) -> Option<V>
  98     where
  99         K: Borrow<Q>,
 100     {
 101         FxHashMap::remove(self, k)
 102     }
 103
 104     #[inline(always)]
 105     fn filter_map_collect<T>(&self, mut f: impl FnMut(&K, &V) -> Option<T>) -> Vec<T> {
 106         self.iter().filter_map(move |(k, v)| f(k, &*v)).collect()
 107     }
 108
 109     #[inline(always)]
 110     fn get_or<E>(&self, k: K, vacant: impl FnOnce() -> Result<V, E>) -> Result<&V, E> {
 111         match self.get(&k) {
 112             Some(v) => Ok(v),
 113             None => {
 114                 vacant()?;
 115                 bug!("The CTFE machine shouldn't ever need to extend the alloc_map when reading")
 116             }
 117         }
 118     }
 119
 120     #[inline(always)]
 121     fn get_mut_or<E>(&mut self, k: K, vacant: impl FnOnce() -> Result<V, E>) -> Result<&mut V, E> {
 122         match self.entry(k) {
 123             Entry::Occupied(e) => Ok(e.into_mut()),
 124             Entry::Vacant(e) => {
 125                 let v = vacant()?;
 126                 Ok(e.insert(v))
 127             }
 128         }
 129     }
 130 }
 131
 132 crate type CompileTimeEvalContext<'mir, 'tcx> =
 133     InterpCx<'mir, 'tcx, CompileTimeInterpreter<'mir, 'tcx>>;
 134
 135 #[derive(Debug, PartialEq, Eq, Copy, Clone)]
 136 pub enum MemoryKind {
 137     Heap,
 138 }
 139
 140 impl fmt::Display for MemoryKind {
 141     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 142         match self {
 143             MemoryKind::Heap => write!(f, "heap allocation"),
 144         }
 145     }
 146 }
 147
 148 impl interpret::MayLeak for MemoryKind {
 149     #[inline(always)]
 150     fn may_leak(self) -> bool {
 151         match self {
 152             MemoryKind::Heap => false,
 153         }
 154     }
 155 }
 156
 157 impl interpret::MayLeak for ! {
 158     #[inline(always)]
 159     fn may_leak(self) -> bool {
 160         // `self` is uninhabited
 161         self
 162     }
 163 }
 164
 165 impl<'mir, 'tcx: 'mir> CompileTimeEvalContext<'mir, 'tcx> {
 166     fn guaranteed_eq(&mut self, a: Scalar, b: Scalar) -> bool {
 167         match (a, b) {
 168             // Comparisons between integers are always known.
 169             (Scalar::Int { .. }, Scalar::Int { .. }) => a == b,
 170             // Equality with integers can never be known for sure.
 171             (Scalar::Int { .. }, Scalar::Ptr(_)) | (Scalar::Ptr(_), Scalar::Int { .. }) => false,
 172             // FIXME: return `true` for when both sides are the same pointer, *except* that
 173             // some things (like functions and vtables) do not have stable addresses
 174             // so we need to be careful around them (see e.g. #73722).
 175             (Scalar::Ptr(_), Scalar::Ptr(_)) => false,
 176         }
 177     }
 178
 179     fn guaranteed_ne(&mut self, a: Scalar, b: Scalar) -> bool {
 180         match (a, b) {
 181             // Comparisons between integers are always known.
 182             (Scalar::Int(_), Scalar::Int(_)) => a != b,
 183             // Comparisons of abstract pointers with null pointers are known if the pointer
 184             // is in bounds, because if they are in bounds, the pointer can't be null.
 185             // Inequality with integers other than null can never be known for sure.
 186             (Scalar::Int(int), Scalar::Ptr(ptr)) | (Scalar::Ptr(ptr), Scalar::Int(int)) => {
 187                 int.is_null() && !self.memory.ptr_may_be_null(ptr)
 188             }
 189             // FIXME: return `true` for at least some comparisons where we can reliably
 190             // determine the result of runtime inequality tests at compile-time.
 191             // Examples include comparison of addresses in different static items.
 192             (Scalar::Ptr(_), Scalar::Ptr(_)) => false,
 193         }
 194     }
 195 }
 196
 197 impl<'mir, 'tcx> interpret::Machine<'mir, 'tcx> for CompileTimeInterpreter<'mir, 'tcx> {
 198     compile_time_machine!(<'mir, 'tcx>);
 199
 200     type MemoryKind = MemoryKind;
 201
 202     type MemoryExtra = MemoryExtra;
 203
 204     const PANIC_ON_ALLOC_FAIL: bool = false; // will be raised as a proper error
 205
 206     fn load_mir(
 207         ecx: &InterpCx<'mir, 'tcx, Self>,
 208         instance: ty::InstanceDef<'tcx>,
 209     ) -> InterpResult<'tcx, &'tcx mir::Body<'tcx>> {
 210         match instance {
 211             ty::InstanceDef::Item(def) => {
 212                 if ecx.tcx.is_ctfe_mir_available(def.did) {
 213                     Ok(ecx.tcx.mir_for_ctfe_opt_const_arg(def))
 214                 } else {
 215                     throw_unsup!(NoMirFor(def.did))
 216                 }
 217             }
 218             _ => Ok(ecx.tcx.instance_mir(instance)),
 219         }
 220     }
 221
 222     fn find_mir_or_eval_fn(
 223         ecx: &mut InterpCx<'mir, 'tcx, Self>,
 224         instance: ty::Instance<'tcx>,
 225         _abi: Abi,
 226         args: &[OpTy<'tcx>],
 227         _ret: Option<(&PlaceTy<'tcx>, mir::BasicBlock)>,
 228         _unwind: StackPopUnwind, // unwinding is not supported in consts
 229     ) -> InterpResult<'tcx, Option<&'mir mir::Body<'tcx>>> {
 230         debug!("find_mir_or_eval_fn: {:?}", instance);
 231
 232         // Only check non-glue functions
 233         if let ty::InstanceDef::Item(def) = instance.def {
 234             // Execution might have wandered off into other crates, so we cannot do a stability-
 235             // sensitive check here.  But we can at least rule out functions that are not const
 236             // at all.
 237             if !ecx.tcx.is_const_fn_raw(def.did) {
 238                 // Some functions we support even if they are non-const -- but avoid testing
 239                 // that for const fn!
 240                 ecx.hook_panic_fn(instance, args)?;
 241                 // We certainly do *not* want to actually call the fn
 242                 // though, so be sure we return here.
 243                 throw_unsup_format!("calling non-const function `{}`", instance)
 244             }
 245         }
 246         // This is a const fn. Call it.
 247         Ok(Some(match ecx.load_mir(instance.def, None) {
 248             Ok(body) => body,
 249             Err(err) => {
 250                 if let err_unsup!(NoMirFor(did)) = err.kind() {
 251                     let path = ecx.tcx.def_path_str(*did);
 252                     return Err(ConstEvalErrKind::NeedsRfc(format!(
 253                         "calling extern function `{}`",
 254                         path
 255                     ))
 256                     .into());
 257                 }
 258                 return Err(err);
 259             }
 260         }))
 261     }
 262
 263     fn call_intrinsic(
 264         ecx: &mut InterpCx<'mir, 'tcx, Self>,
 265         instance: ty::Instance<'tcx>,
 266         args: &[OpTy<'tcx>],
 267         ret: Option<(&PlaceTy<'tcx>, mir::BasicBlock)>,
 268         _unwind: StackPopUnwind,
 269     ) -> InterpResult<'tcx> {
 270         // Shared intrinsics.
 271         if ecx.emulate_intrinsic(instance, args, ret)? {
 272             return Ok(());
 273         }
 274         let intrinsic_name = ecx.tcx.item_name(instance.def_id());
 275
 276         // CTFE-specific intrinsics.
 277         let (dest, ret) = match ret {
 278             None => {
 279                 return Err(ConstEvalErrKind::NeedsRfc(format!(
 280                     "calling intrinsic `{}`",
 281                     intrinsic_name
 282                 ))
 283                 .into());
 284             }
 285             Some(p) => p,
 286         };
 287         match intrinsic_name {
 288             sym::ptr_guaranteed_eq | sym::ptr_guaranteed_ne => {
 289                 let a = ecx.read_immediate(&args[0])?.to_scalar()?;
 290                 let b = ecx.read_immediate(&args[1])?.to_scalar()?;
 291                 let cmp = if intrinsic_name == sym::ptr_guaranteed_eq {
 292                     ecx.guaranteed_eq(a, b)
 293                 } else {
 294                     ecx.guaranteed_ne(a, b)
 295                 };
 296                 ecx.write_scalar(Scalar::from_bool(cmp), dest)?;
 297             }
 298             sym::const_allocate => {
 299                 let size = ecx.read_scalar(&args[0])?.to_machine_usize(ecx)?;
 300                 let align = ecx.read_scalar(&args[1])?.to_machine_usize(ecx)?;
 301
 302                 let align = match Align::from_bytes(align) {
 303                     Ok(a) => a,
 304                     Err(err) => throw_ub_format!("align has to be a power of 2, {}", err),
 305                 };
 306
 307                 let ptr = ecx.memory.allocate(
 308                     Size::from_bytes(size as u64),
 309                     align,
 310                     interpret::MemoryKind::Machine(MemoryKind::Heap),
 311                 )?;
 312                 ecx.write_scalar(Scalar::Ptr(ptr), dest)?;
 313             }
 314             _ => {
 315                 return Err(ConstEvalErrKind::NeedsRfc(format!(
 316                     "calling intrinsic `{}`",
 317                     intrinsic_name
 318                 ))
 319                 .into());
 320             }
 321         }
 322
 323         ecx.go_to_block(ret);
 324         Ok(())
 325     }
 326
 327     fn assert_panic(
 328         ecx: &mut InterpCx<'mir, 'tcx, Self>,
 329         msg: &AssertMessage<'tcx>,
 330         _unwind: Option<mir::BasicBlock>,
 331     ) -> InterpResult<'tcx> {
 332         use rustc_middle::mir::AssertKind::*;
 333         // Convert `AssertKind<Operand>` to `AssertKind<Scalar>`.
 334         let eval_to_int =
 335             |op| ecx.read_immediate(&ecx.eval_operand(op, None)?).map(|x| x.to_const_int());
 336         let err = match msg {
 337             BoundsCheck { ref len, ref index } => {
 338                 let len = eval_to_int(len)?;
 339                 let index = eval_to_int(index)?;
 340                 BoundsCheck { len, index }
 341             }
 342             Overflow(op, l, r) => Overflow(*op, eval_to_int(l)?, eval_to_int(r)?),
 343             OverflowNeg(op) => OverflowNeg(eval_to_int(op)?),
 344             DivisionByZero(op) => DivisionByZero(eval_to_int(op)?),
 345             RemainderByZero(op) => RemainderByZero(eval_to_int(op)?),
 346             ResumedAfterReturn(generator_kind) => ResumedAfterReturn(*generator_kind),
 347             ResumedAfterPanic(generator_kind) => ResumedAfterPanic(*generator_kind),
 348         };
 349         Err(ConstEvalErrKind::AssertFailure(err).into())
 350     }
 351
 352     fn abort(_ecx: &mut InterpCx<'mir, 'tcx, Self>, msg: String) -> InterpResult<'tcx, !> {
 353         Err(ConstEvalErrKind::Abort(msg).into())
 354     }
 355
 356     fn ptr_to_int(_mem: &Memory<'mir, 'tcx, Self>, _ptr: Pointer) -> InterpResult<'tcx, u64> {
 357         Err(ConstEvalErrKind::PtrToIntCast.into())
 358     }
 359
 360     fn binary_ptr_op(
 361         _ecx: &InterpCx<'mir, 'tcx, Self>,
 362         _bin_op: mir::BinOp,
 363         _left: &ImmTy<'tcx>,
 364         _right: &ImmTy<'tcx>,
 365     ) -> InterpResult<'tcx, (Scalar, bool, Ty<'tcx>)> {
 366         Err(ConstEvalErrKind::NeedsRfc("pointer arithmetic or comparison".to_string()).into())
 367     }
 368
 369     fn box_alloc(
 370         _ecx: &mut InterpCx<'mir, 'tcx, Self>,
 371         _dest: &PlaceTy<'tcx>,
 372     ) -> InterpResult<'tcx> {
 373         Err(ConstEvalErrKind::NeedsRfc("heap allocations via `box` keyword".to_string()).into())
 374     }
 375
 376     fn before_terminator(ecx: &mut InterpCx<'mir, 'tcx, Self>) -> InterpResult<'tcx> {
 377         // The step limit has already been hit in a previous call to `before_terminator`.
 378         if ecx.machine.steps_remaining == 0 {
 379             return Ok(());
 380         }
 381
 382         ecx.machine.steps_remaining -= 1;
 383         if ecx.machine.steps_remaining == 0 {
 384             throw_exhaust!(StepLimitReached)
 385         }
 386
 387         Ok(())
 388     }
 389
 390     #[inline(always)]
 391     fn init_frame_extra(
 392         ecx: &mut InterpCx<'mir, 'tcx, Self>,
 393         frame: Frame<'mir, 'tcx>,
 394     ) -> InterpResult<'tcx, Frame<'mir, 'tcx>> {
 395         // Enforce stack size limit. Add 1 because this is run before the new frame is pushed.
 396         if !ecx.recursion_limit.value_within_limit(ecx.stack().len() + 1) {
 397             throw_exhaust!(StackFrameLimitReached)
 398         } else {
 399             Ok(frame)
 400         }
 401     }
 402
 403     #[inline(always)]
 404     fn stack(
 405         ecx: &'a InterpCx<'mir, 'tcx, Self>,
 406     ) -> &'a [Frame<'mir, 'tcx, Self::PointerTag, Self::FrameExtra>] {
 407         &ecx.machine.stack
 408     }
 409
 410     #[inline(always)]
 411     fn stack_mut(
 412         ecx: &'a mut InterpCx<'mir, 'tcx, Self>,
 413     ) -> &'a mut Vec<Frame<'mir, 'tcx, Self::PointerTag, Self::FrameExtra>> {
 414         &mut ecx.machine.stack
 415     }
 416
 417     fn before_access_global(
 418         memory_extra: &MemoryExtra,
 419         alloc_id: AllocId,
 420         allocation: &Allocation,
 421         static_def_id: Option<DefId>,
 422         is_write: bool,
 423     ) -> InterpResult<'tcx> {
 424         if is_write {
 425             // Write access. These are never allowed, but we give a targeted error message.
 426             if allocation.mutability == Mutability::Not {
 427                 Err(err_ub!(WriteToReadOnly(alloc_id)).into())
 428             } else {
 429                 Err(ConstEvalErrKind::ModifiedGlobal.into())
 430             }
 431         } else {
 432             // Read access. These are usually allowed, with some exceptions.
 433             if memory_extra.can_access_statics {
 434                 // Machine configuration allows us read from anything (e.g., `static` initializer).
 435                 Ok(())
 436             } else if static_def_id.is_some() {
 437                 // Machine configuration does not allow us to read statics
 438                 // (e.g., `const` initializer).
 439                 // See const_eval::machine::MemoryExtra::can_access_statics for why
 440                 // this check is so important: if we could read statics, we could read pointers
 441                 // to mutable allocations *inside* statics. These allocations are not themselves
 442                 // statics, so pointers to them can get around the check in `validity.rs`.
 443                 Err(ConstEvalErrKind::ConstAccessesStatic.into())
 444             } else {
 445                 // Immutable global, this read is fine.
 446                 // But make sure we never accept a read from something mutable, that would be
 447                 // unsound. The reason is that as the content of this allocation may be different
 448                 // now and at run-time, so if we permit reading now we might return the wrong value.
 449                 assert_eq!(allocation.mutability, Mutability::Not);
 450                 Ok(())
 451             }
 452         }
 453     }
 454 }
 455
 456 // Please do not add any code below the above `Machine` trait impl. I (oli-obk) plan more cleanups
 457 // so we can end up having a file with just that impl, but for now, let's keep the impl discoverable
 458 // at the bottom of this file.